Problème à résoudre
Maximiser z = 3x1 + 2x2
Sous les contraintes :
x1 + x2 ≤ 5
2x1 + x2 ≤ 8
x1 , x2 ≥ 0
Étape 1 : Mettre sous forme standard
On transforme les inégalités en égalités en ajoutant des variables d’écart (s1 , s2 ) :
x1 + x2 + s 1 = 5
2x1 + x2 + s2 = 8
z = 3x1 + 2x2 (objectif à maximiser)
x1 , x2 , s 1 , s 2 ≥ 0
c1 = 3 (pour x1 ), c2 = 2 (pour x2 ), cs1 = 0 (pour s1 ), cs2 = 0 (pour s2 ).
Étape 2 : Construire le tableau initial
On choisit une solution de base initiale faisable en mettant les variables de décision à zéro :
x1 = 0, x2 = 0
s1 = 5, s2 = 8
Base initiale : s1 , s2 (variables d’écart).
Tableau initial :
Base x1 x2 s1 s2 b
s1 1 1 1 0 5
s2 2 1 0 1 8
z -3 -2 0 0 0
Explications :
Lignes :
+ x2 + s1 = 5).
Ligne s1 : première contrainte (x1
Ligne s2 : deuxième contrainte (2x1 + x2 + s2 = 8).
Ligne z : fonction objectif z − 3x1 − 2x2 = 0, donc −cj pour les variables hors base (
−3, −2) et 0 pour les variables de base (s1 , s2 ).
Colonnes : Une par variable (x1 , x2 , s1 , s2 ) plus b (termes de droite).
−rj dans z : On met −cj au départ car zj = 0 (base avec cs1 = 0, cs2 = 0), et ça évoluera
avec les pivots.
Valeur initiale : z = 3 ⋅ 0 + 2 ⋅ 0 = 0.
Étape 3 : Vérifier l’optimalité (itération 1)
On calcule les coûts réduits (rj = cj − zj ) pour les variables hors base (x1 , x2 ) :
zj = ∑k de base ck ⋅ a′k,j
Base : s1 (cs1 = 0), s2 (cs2 = 0).
x1 : z1 = 0 ⋅ 1 + 0 ⋅ 2 = 0, r1 = c1 − z1 = 3 − 0 = 3, ligne z : −r1 = −3.
x2 : z2 = 0 ⋅ 1 + 0 ⋅ 1 = 0, r2 = c2 − z2 = 2 − 0 = 2, ligne z : −r2 = −2.
Interprétation :
Ligne z montre −rj . Si −rj
< 0, alors rj > 0, donc on peut améliorer z .
−3 < 0 (r1 = 3 > 0), −2 < 0 (r2 = 2 > 0) → pas optimal.
Étape 4 : Choisir la variable entrante
Plus grand rj : r1 = 3 > r2 = 2 → x1 entre.
Colonne pivot : [1, 2] (colonne de x1 ).
Étape 5 : Choisir la variable sortante
Ratios bi /ai,j (où ai,j
> 0) :
Ligne s1 : 5/1
= 5.
Ligne s2 : 8/2 = 4.
Plus petit ratio : 4 (ligne s2 ) → s2 sort.
Élément pivot : a2,1 = 2 (intersection ligne s2 , colonne x1 ).
Étape 6 : Pivoter (itération 1)
1. Normaliser la ligne pivot :
Ligne s2 : [2, 1, 0, 1, 8]/2
= [1, 1/2, 0, 1/2, 4].
s2 devient x1 .
2. Mettre des 0 dans la colonne x1 :
Ligne s1 : [1, 1, 1, 0, 5] − 1 ⋅ [1, 1/2, 0, 1/2, 4]
= [0, 1/2, 1, −1/2, 1].
Ligne z : [−3, −2, 0, 0, 0] + 3 ⋅ [1, 1/2, 0, 1/2, 4] = [0, −1/2, 0, 3/2, 12].
Nouveau tableau :
Base x1 x2 s1 s2 b
s1 0 1/2 1 -1/2 1
x1 1 1/2 0 1/2 4
z 0 -1/2 0 3/2 12
Base : s1 , x1 .
z = 12 (valeur actuelle).
Étape 7 : Vérifier l’optimalité (itération 2)
Base : s1 (cs1 = 0), x1 (c1 = 3).
x2 : z2 = 0 ⋅ 1/2 + 3 ⋅ 1/2 = 0 + 3/2 = 3/2, r2 = 2 − 3/2 = 1/2, ligne z : −r2 = −1/2.
s2 : zs2 = 0 ⋅ (−1/2) + 3 ⋅ 1/2 = 0 + 3/2 = 3/2, rs2 = 0 − 3/2 = −3/2, ligne z :
−rs2 = 3/2.
−r2 = −1/2 < 0 → r2 = 1/2 > 0 → pas optimal.
Étape 8 : Choisir la variable entrante
r2 = 1/2 > 0 → x2 entre.
Colonne pivot : [1/2, 1/2] (colonne de x2 ).
Étape 9 : Choisir la variable sortante
Ratios :
Ligne s1 : 1/(1/2) = 1 ⋅ 2 = 2.
Ligne x1 : 4/(1/2) = 4 ⋅ 2 = 8.
Plus petit ratio : 2 (ligne s1 ) → s1 sort.
Élément pivot : a1,2
= 1/2.
Étape 10 : Pivoter (itération 2)
1. Normaliser la ligne pivot :
Ligne s1 : [0, 1/2, 1, −1/2, 1] ÷ 1/2
= [0, 1, 2, −1, 2].
2. Mettre des 0 dans la colonne x2 :
Ligne x1 : [1, 1/2, 0, 1/2, 4] − (1/2) ⋅ [0, 1, 2, −1, 2]
= [1, 0, −1, 1, 3].
Ligne z : [0, −1/2, 0, 3/2, 12] + (1/2) ⋅ [0, 1, 2, −1, 2] = [0, 0, 1, 1, 13].
Nouveau tableau :
Base x1 x2 s1 s2 b
x2 0 1 2 -1 2
x1 1 0 -1 1 3
z 0 0 1 1 13
Base : x2 , x1 .
z = 13.
Étape 11 : Vérifier l’optimalité (itération 3)
Base : x2 (c2 = 2), x1 (c1 = 3).
s1 : zs1 = 2 ⋅ 2 + 3 ⋅ (−1) = 4 − 3 = 1, rs1 = 0 − 1 = −1, ligne z : −rs1 = 1.
s2 : zs2 = 2 ⋅ (−1) + 3 ⋅ 1 = −2 + 3 = 1, rs2 = 0 − 1 = −1, ligne z : −rs2 = 1.
Tous −rj ≥ 0 (1, 1) → rj ≤ 0 → optimal.
Résultat final
x1 = 3 (ligne x1 , colonne b),
x2 = 2 (ligne x2 , colonne b),
s1 = 0, s2 = 0 (hors base),
z = 3 ⋅ 3 + 2 ⋅ 2 = 9 + 4 = 13.
Vérification :
x1 + x2 = 3 + 2 = 5 ≤ 5 ✓
2x1 + x2 = 6 + 2 = 8 ≤ 8 ✓
Résumé des étapes
1. Forme standard : Ajouter des variables d’écart.
2. Tableau initial : Base faisable avec −cj dans la ligne z .
= cj − zj (si −rj < 0 dans z , alors rj > 0).
3. Optimalité : Vérifier rj
4. Variable entrante : Plus grand rj .
5. Variable sortante : Plus petit ratio bi /ai,j .
6. Pivot : Normaliser la ligne pivot, ajuster les autres lignes.
7. Répéter jusqu’à rj ≤ 0 pour toutes les variables hors base pertinentes.