Généralités sur la programmation linéaire
39
Or, si
, les autres variables hors base restant nulles, la nouvelle
valeur
de la fonction économique est :
-
et alors
On a bien réussi par cette opération à augmenter la valeur de la fonction économique.
Tout le principe de l'algorithme du simplexe est là :
1- partir d'une solution de base,
2- passer à une autre solution de base en faisant entrer une variable hors base dans
la base et sortir une variable de base pour la mettre hors base, et en s'assurant
que l'on améliore ainsi la fonction économique,
3- s'arrêter lorsque l'on ne peut plus améliorer la fonction économique.
En ce qui concerne le test d'arrêt, il est le suivant :
lorsque, pour tout
on a atteint l'optimum qui est donné par la solution
de base I.
Ce test est parfaitement évident si l'on prend le P.L sous la forme donnée par les
équations (7) et (8) :
En effet, encore une fois, ce programme est équivalent au programme initial (1). La
solution de ce programme, si
pour tout
est bien évidemment
et donc
i
c'est-à-dire la solution de base considérée.
Les principes de l'algorithme du simplexe sont résumés dans l'ordinogramme de la page
suivante.
Remarque importante : lorsque l'on passe d'un sommet à un autre, la fonction
économique devient comme on l'a vu :
avec
valeur de la variable entrée dans la base et
étant finis, on
est sûr que, si l'on ne rencontre jamais de dégénérescences de premier type (variables de
base nulles) l'algorithme du simplexe est convergent, puisqu'à chaque itération, la
fonction économique s'accroît d'une quantité finie. Dans le cas contraire, il peut y avoir
(dans des circonstances très rares) non convergence.