Algorithme du simplex
61
Il convient alors d'éliminer au plus vite
de la base, et donc de l'annuler; si
est nul,
en effet, la solution de base trouvée avec
respectera obligatoirement
les contraintes (9).
Pour éliminer , on va l'introduire dans la fonction économique avec un poids négatif
très grand.
6
5
4
3
2
1
0
0
=
x
M
x
x
x
x
x
Z
avec
et très grand .
Ainsi, la variable
doit en principe sortir rapidement de la base. Si à la fin de
l'algorithme du simplexe, la variable
est toujours dans la base, c'est que le système
d'inéquations du P.L (8) est incompatible. En effet, s'il était compatible, il y aurait des
solutions réalisables finies et donc la valeur optimale de serait inférieurement bornée.
Or, si
est variable de base positive (on exclut le cas des dégénérescences) à
l'optimum, on voit que l'on peut faire tendre la valeur optimale de vers moins l'infini
en augmentant indéfiniment.
Si le système d'inéquations du P.L est compatible,
doit donc sortir de la base à une
itération ou une autre du calcul; à partir de ce moment, on élimine purement et
simplement
suffisant à transformer la deuxième contrainte en égalité.
Traitons l'exemple :
On a le tableau suivant :
1
2
3
4
5
6
0
4
1
1
1
1
0
0
4
-M
6
2
1
-1
0
-1
+1
2
1
1
1
0
0
-M
Z
Une difficulté surgit dans la mesure où n'est pas exprimée uniquement en fonction des
variables hors base ( est de base). Il faut alors utiliser les formules
j
j
j
I
j
o
x
z
c
Z
Z
)
(
=
i
i
I
i
o
j
i
i
I
i
j
x
c
Z
t
c
z
=
=
pour calculer la ligne des gains marginaux.