La programmation linéaire - publié le 15/06/2023

Thèmes abordés

Recherche opérationnelle, aide à la décision, statistique, algorithme, solution optimale, prise de décision, programmation linéaire, PPL Problème de Programmation Linéaire, problème de maximisation, méthode de résolution, graphique, méthode générale du Simplexe, matrice unitaire, critère d'optimalité, méthode la base artificielle, méthdode de transport

Résumé du document

La Recherche opérationnelle est une discipline moderne qui utilise des modèles mathématiques, statistiques et des algorithmes pour modeler et résoudre des problèmes complexes, en déterminant la solution optimale et en améliorant la prise de décisions. Cette matière reçoit aussi le nom de Recherche opérationnelle ou Aide à la Décision.
Donc l'objet de cette discipline est de fournir des bases rationnelles à la prise de décisions, habituellement dans un but de contrôle ou d'optimisation (améliorer l'efficacité, diminuer les coûts, etc.).

Extraits

[...] Exercice 2 : une entreprise dépose trois ressources R1, R2 et R3 en quantité limité et 700 unités pour qu'elle fabrique deux produits P1 et P2 qu'il assure un bénéfice unitaire respectivement du 60 et 40 unité monétaire, ● Une unité de P1 nécessite 6 unités de R1 et une unité de R2 ● Une unité de P2 nécessite 4 unités de R1 et une unité de R3 L'entreprise cherche à déterminer les quantités à produire de P1 et P2 qui assurent un bénéfice total maximum. Exercice 3 : Déterminer la solution optimale au modèle mathématique suivant par la résolution graphique : [𝑀𝐴𝑋]𝐹(𝑋) = 𝑋 + 𝑋 Les contraintes : 𝑋 + 2𝑋 5𝑋 + 2𝑋 3𝑋 + 2𝑋 Exercice 4 : Un restaurant universitaire tente de composer un repas contenant deux types d'aliments, les besoins quotidiens de l'étudiant sont au moins 9 mg de vitamine V1 et 8 mg de vitamine V2 et 12 mg de vitamine V3. [...]

[...] + 𝑎 𝑋 = 𝑏 𝑚 𝑚 𝑚𝑛 𝑛 𝑚 avec : 𝑋 𝑗 on note : 𝑋𝑗: 𝑙𝑒𝑠 𝑞𝑢𝑎𝑛𝑡𝑖𝑡é𝑠 à 𝑑é𝑡𝑒𝑟𝑚𝑖𝑛𝑒𝑟 𝐶 : 𝑐𝑜𝑒𝑓𝑓𝑖𝑐𝑖𝑒𝑛𝑡 𝑐𝑜𝑛𝑠𝑡𝑎𝑛𝑡 𝑟é𝑒𝑙 𝑎𝑝𝑝𝑒𝑙é 𝑐𝑜û𝑡 𝑗 𝑎 : 𝑐𝑜𝑒𝑓𝑓𝑖𝑐𝑖𝑒𝑛𝑡 𝑐𝑜𝑛𝑠𝑡𝑎𝑛𝑡 𝑟é𝑒𝑙 𝑎𝑝𝑝𝑒𝑙é 𝑡𝑒𝑐ℎ𝑛𝑜𝑙𝑜𝑔𝑖𝑞𝑢𝑒 𝑖𝑗 𝑏 : 𝑐𝑜𝑒𝑓𝑓𝑖𝑐𝑖𝑒𝑛𝑡 𝑐𝑜𝑛𝑠𝑡𝑎𝑛𝑡 𝑟é𝑒𝑙 𝑎𝑝𝑝𝑒𝑙é 𝑑𝑖𝑠𝑝𝑜𝑛𝑖𝑏𝑙𝑒 𝑗 Problème de programmation linéaire “PPL”peut se présenter l'une des formes suivantes : Toutes les = = contraintes = = = = La forme Canonique Standard Mixte Les méthodes de résolution de PPL 1. La méthode de graphique : Cette méthode n'est applicable que dans le cas où il n'y a que deux variables. [...]

[...] La programmation linéaire Définition : La Recherche Opérationnelle est une discipline moderne qui utilise des modèles mathématiques, statistiques et des algorithmes pour modeler et résoudre des problèmes complexes, en déterminant la solution optimale et en améliorant la prise de décisions. Cette matière reçoit aussi le nom de Recherche Opérationnelle ou Aide à la Décision. Donc l'objet de cette discipline est de fournir des bases rationnelles à la prise de décisions, habituellement dans un but de contrôle ou d'optimisation (améliorer l'efficacité, diminuer les coûts, etc.). [...]

[...] 6ème étape : critère de l'entrée de la base On sélectionne la variable entrante dans la façon suivante : ★ Dans un problème de maximisation : la variable entrante est la variable qui correspond à la plus petite valeur négative ( 𝑀𝐴𝑋→𝑀𝑖𝑛 𝐹𝑗 − 𝐶𝑗 0 𝑗 𝑗 ) Dans l'exercice, la valeur la plus petite est alors la variable entrante est 𝑋 1 7ème étape : critère de sortie de la base On sélectionne la variable sortante de la façon suivante : 𝐵 On devise terme-à-terme les éléments de la colonne 𝑋 par les éléments de la colonne correspondante à la variable entrante, nous obtenons des valeurs qu'appeler(θ). On sélectionne la plus petite valeur positive de la variable correspondante en ligne est la variable sortante de la base. [...]

[...] 𝑚 ● Méthode de coût minimum : Magasin B1 Usine A1 B Demande 100 40 50 Offre 90 30 B B B tonnes 𝐹(𝑥) = 16900 𝑢. 𝑚 Exemple : soit le plan de transport suivant : Magasin B1 B2 B3 Usine A A A Offre Demande tonnes - Déterminer le plan de transport optimal par la méthode de coût minimum ? Solution Le plan initial de base : Magasin B1(V1) Usine A1 11 B2 8 A2 - A3 - B3 - Offre Demande tonnes 8620 DA Vérification de l'optimalité du plan de transport : Les cases pleines : 𝐴 𝐵 :𝑈 + 𝑉 = 𝐶 = 𝐴 𝐵 :𝑈 + 𝑉 = 𝐶 = 𝐴 𝐵 : 𝑈 + 𝑉 = 𝐶 = 𝐴 𝐵 : 𝑈 + 𝑉 = 𝐶 = 𝐴 𝐵 :𝑈 + 𝑉 = 𝐶 = 𝑈 = 0 𝑈 =− 12 ; 𝑈 =− 6 ; 𝑉 = 6 ; 𝑉 = 10 ;𝑉 = Les cases vides : ( 1 𝐴 𝐵 : 𝐸 = 𝐶 − ( 𝑈 + 𝑉) = 8 − (− 12 + 10) 𝐴 𝐵 : 𝐸 = 𝐶 − ( 𝑈 + 𝑉) = 8 − (− 6 + 𝐴 𝐵 : 𝐸 = 𝐶 − ( 𝑈 + 𝑉) = 10 − (− 6 + 17) =− 𝐴 𝐵 :𝐸 = 𝐶 𝐸 11 − 𝑈 + 𝑉 = 11 − (− 12 + 17 ' 33 > 0 𝑑𝑜𝑛𝑐 𝑙𝑒 𝑝𝑙𝑎𝑛 𝑛 𝑒𝑠𝑡 𝑝𝑎𝑠 𝑜𝑝𝑡𝑖𝑚𝑎𝑙𝑒 Recherche du plan optimale de transport : Magasin B1(V1) Usine A1 11 B2 A2 6 B3 10 Demande A3 Offre tonnes 8580 u.m 𝑈 +𝑉 =𝐶 = 𝑈 +𝑉 =𝐶 = 𝑈 + 𝑉 = 𝐶 = 𝑈 +𝑉 =𝐶 = 𝑈 + 𝑉 = 𝐶 = 𝑈 = 0 𝑈 = 11 ; 𝑈 = 𝑉 =− 5 ; 𝑉 =− 1 ; 𝑉 = 𝐸 11 =𝐶 11 𝐸 23 ( 12 =𝐶 𝐸 ) ) − 𝑈 + 𝑉 = 8 − − 9 =𝐶 12 𝐸 ( − 𝑈 + 𝑉 = 11 − − 16 ( ) − 𝑈 + 𝑉 = 17 − (11 + 1 =𝐶 ( 3 ) − 𝑈 + 𝑉 = 8 − − Exercice : Soit le modèle de transport suivant représente la marchandise de quatre magasins de stockage et les quantités demandées de la même marchandise vers trois consommateurs B1, B2, B3 et le coût de transport unitaire de chaque magasin vers chaque consommateur : Consommateurs B1 B2 B3 Magasins de stockage A A A A Demande ● Offre tonnes Définissez le schéma de transport de cette marchandise des magasins vers les consommateurs et qui réalise le coût minimum de transport par la méthode du coût minimum. [...]