Algorithme du simplexe en bref

Le but de ce cours n'est pas de vous apprendre comment on résoud les programmes linéaires, mais comment on les modélise. Ces problèmes se résolvent, en pratique, en temps polynomial. Un des algorithmes les plus connus est l'algorithme du simplexe. Je n'expliquerai ici que le principe, pour plus de détails, voir [5]. Les contraintes peuvent être représentées par des demi-plans. L'ensemble des solutions réalisables est l'intersection de ces demi-plans, cette intersection forme un polygone convexe. Soit $z$ un réel, l'ensemble des couples $(x, y)$ tel que la fonction objectif prend la valeur $z$ est une droite $d_z$.

En Augmentant la valeur de $z$, on ``déplace'' $d_z$. On cherche donc la plus grande valeur de $z$ telle qu'au moins un point de $d_z$ se trouve dans l'ensemble des solutions réalisables. Il se trouve qu'à l'optimum, la droite $d_z$ passe par un des sommets du polygone des solutions réalisables. L'algorithme du simplexe parcours les sommets de ce polygone jusqu'à atteindre cet optimum. Cette méthode se généralise facilement à un nombre de variables et de contraintes arbitraires.