Les équations du programme auxiliaire peuvent s'écrire (en supprimant 2 contraintes évidemment inutiles)
x1+x2+y | = | 60 | (1) |
x1+x3+y | = | 100 | (2) |
x2+x3+y | = | 120 | (3) |
x1+x2+x3 | = | 200 | (4) |
x1 | = | 0 | (5) |
x2 | = | 0 | (6) |
x3 | = | 0 | (7) |
y | = | 0 | (8) |
Première itération: on essaie les 16 systèmes:
(1,5,6,7) solution [0,0,0,60] non réalisable
(2,5,6,7) solution [0,0,0,100] non réalisable
(4,5,6,7) aucune solution
(5,6,7,8) solution [0,0,0,0] non réalisable
(1,3,6,7) solution [-60,0,0,120] non réalisable
(2,3,6,7) solution [-20,0,0,120] non réalisable
(3,4,6,7) solution [200,0,0,120] non réalisable
(3,6,7,8) aucune solution
(1,3,5,7) aucune solution
(2,3,5,7) solution [0,20,0,100] réalisable
(3,4,5,7) solution [0,200,0,-80] non réalisable
(3,5,7,8) solution [0,120,0,0] non réalisable
(1,3,5,6) solution [0,0,60,60] réalisable
(2,3,5,6) aucune solution
(3,4,5,6) solution [0,0,200,-80] non réalisable
(3,5,6,8) solution [0,0,120,0] non réalisable
Si je choisis la solution (2,3,5,7), la seconde itération commence
avec:
(1,3,5,7) aucune solution
(3,4,5,7) solution [0,200,0,-80] non réalisable
(3,5,6,7) solution [0,0,0,120] réalisable
(3,5,7,8) solution [0,120,0,0] non réalisable
(1,2,5,7) solution [0,-40,0,100] non réalisable
(2,4,5,7) solution
[0,200,0,-100] non réalisable
(2,5,6,7) solution [0,0,0,100] non réalisable
(1,2,3,7) solution
[-60,-40,0,160] non réalisable
(2,3,4,7) solution [90,110,0,10] réalisable
etc.
Et la troisième itération pourrait commencer à (2,3,4,7)
et trouver enfin:
(2,3,4,8) solution [80,100,20,0] réalisable et optimale
(du programme auxiliaire)
Donc les équations (2,3,4) (mais sans y) donnent la solution
réalisable de base [80,100,20] du programme initial.
Il faut ajouter les équations des 2 nouvelles contraintes:
x1+x2-x3 = 0 (9)
-3x1+2x2+4x3 = 0 (10).
La solution initiale [0,0,0,120] est l'intersection des 6 équations (3,5,6,7,9,10). Un sous-ensemble de ces 6 mais sans l'équation (3) ne peut pas avoir une solution unique (aucune occurrence de y); donc il y a 10 représentations de ce point comme intersection de 4 contraintes, à savoir (3) et (5,6,7), (5,6,9), (5,6,10), (5,7,9), (5,7,10), (5,9,10), (6,7,9), (6,7,10), (6,9,10) ou (7,9,10).
Il y a les sommets voisins avec une meilleure valeur de -y:
[0,20,20,80] (intersection de (2,3,5,9)
[0,20,0,100] (2,3,5,7)
[114.3, 0,85.7,34.3] (3,4,6,10)
[100,0,100,20] (3,4,6,9).
L'intersection (3,7,9,10) est la seule qui n'est pas voisin d'au moins un de ces sommets et l'algorithme va trouver une sortie de la solution initiale à la deuxième itération dans le pire des cas.