Résolution Complète - Exercice 2
Optimisation Linéaire & Méthode du Simplexe
Ce document présente la résolution algorithmique rigoureuse du programme linéaire extrait de l'image
fournie.
1) Formulation et Forme Standard
Le problème initial est formulé de la manière suivante :
Max Z = -X1 + 3X2
s/c :
-3X1 + X2 ≤ 6
X1 + 2X2 ≤ 4
X2 ≥ -3
X1 variable libre
Changement de variables :
• Variable libre X : On la remplace par la différence de deux variables positives : X = X ' - X '' avec
1 1 1 1
X1', X1'' ≥ 0.
• Contrainte de borne X ≥ -3 : On pose X ' = X + 3, soit X = X ' - 3 avec X ' ≥ 0.
2 2 2 2 2 2
Substitution dans la fonction objectif :
Maximiser Z = -(X1' - X1'') + 3(X2' - 3) = -X1' + X1'' + 3X2' - 9.
Cela équivaut à maximiser Z' = -X1' + X1'' + 3X2' avec la relation constante Z = Z' - 9.
Forme Standard d'introduction du Simplexe :
En introduisant les variables d'écart S1, S2 ≥ 0, on obtient le système standardisé :
Max Z' = -X1' + X1'' + 3X2'
s/c :
-3X1' + 3X1'' + X2' + S1 = 9
X1' - X1'' + 2X2' + S2 = 10
X1', X1'', X2', S1, S2 ≥ 0
Recherche Opérationnelle - Exercice 2 Page 1 / 3
2) Résolution par la Méthode du Simplexe
Tableau 1 : Initialisation
Base X1' X1'' X2' S1 S2 Rms (D) Ratio
S1 -3 3 1 1 0 9 9/1=9
S2 1 -1 2 (Pivot) 0 1 10 10 / 2 = 5 (Min)
Z' 1 -1 -3 0 0 0 —
La variable entrante est X2' et la variable sortante est S2.
Tableau 2 : Deuxième itération
Base X1' X1'' X2' S1 S2 Rms (D) Ratio
S1 -7/2 7/2 (Pivot) 0 1 -1/2 4 4 / (7/2) = 8/7 (Min)
X2' 1/2 -1/2 1 0 1/2 5 —
Z' 5/2 -5/2 0 0 3/2 15 —
La variable entrante est X1'' et la variable sortante est S1.
Tableau 3 : Optimalité
Base X1' X1'' X2' S1 S2 Rms (D)
X1'' -1 1 0 2/7 -1/7 8/7
X2' 0 0 1 1/7 3/7 39/7
Z' 0 0 0 5/7 8/7 62/7
Tous les coefficients de la fonction objectif étant positifs ou nuls, l'optimum est atteint.
Recherche Opérationnelle - Exercice 2 Page 2 / 3
Solution Optimale Finale :
• X * = X ' - X '' = 0 - 8/7 = -8/7 ≈ -1,14
1 1 1
• X * = X ' - 3 = 39/7 - 3 = 18/7 ≈ 2,57
2 2
• Z* = Z'* - 9 = 62/7 - 9 = -1/7 ≈ -0,14
3) Identification des Prix Fictifs (Shadow Prices)
Les prix fictifs se lisent directement sur la ligne de la fonction objectif sous les variables d'écart
correspondantes :
• Prix fictif de la contrainte 1 (λ ) : 5/7
1
• Prix fictif de la contrainte 2 (λ ) : 8/7
2
4) Interprétation Économique
Sensibilité des ressources : Une augmentation marginale d'une unité de la ressource de la contrainte
1 (le terme de droite passant de 6 à 7) améliorera la valeur maximale de la fonction objectif de 5/7. De
façon similaire, une augmentation d'une unité de la ressource de la contrainte 2 améliorera Z de 8/7.
Saturation : Les variables d'écart étant nulles à l'optimum (S1 = 0 et S2 = 0), cela signifie que les deux
contraintes sont strictement saturées. Toutes les ressources disponibles sont consommées à la
solution optimale.
Recherche Opérationnelle - Exercice 2 Page 3 / 3