Algorithme du simplex
57
Avec
Si l'on résume le programme en tableaux, comme on l'a fait précédemment, on a la
disposition suivante
j
i
125
i
+1
75
0
zavec
Cherchons à améliorer la solution obtenue en passant à une autre solution de base. Pour
cela, décrivons les mêmes phases de calcul que pour le petit exemple que nous venons
de traiter :
1) on regarde si tous les (gains marginaux) sont négatifs ou nuls. Si oui, on est à
l'optimum et on arrête le calcul. Sinon :
2) on choisit
tel que
est la variable entrant dans la base. En général,
on choisit
de telle façon que
(premier critère de Dantzig).
3) on détermine
tel que
0
le trouvé est tel que
est la variable sortant de la base (second critère de Dantzig).
4) on transforme le tableau central de façon que pour la colonne correspondant à
:
soit remplacé par 1
soit remplacé par 0.