Algorithme du simplexe - Définition
L'algorithme du simplexe de George Dantzig est une technique à la fois fondamentale et très populaire pour les problèmes de programmation linéaire. Ainsi, étant donné un ensemble d'inégalités linéaires sur n variables réelles, l'algorithme permet de trouver la solution optimale pour une fonction objectif, qui est elle aussi linéaire (l'algorithme fonctionne encore quand la fonction est croissante en chacune de n variables).
En termes géométriques, l'ensemble des inégalités linéaires définit un polyèdre dans l'espace à n dimensions et il s'agit de trouver le sommet optimal pour la fonction de coût donnée. L'idée de l'algorithme consiste à partir d'un sommet quelconque du polyèdre et, à chaque itération, d'aller à un sommet adjacent s'il est possible d'en trouver un meilleur pour la fonction objectif. S'il n'y en a pas, l'algorithme s'arrête en concluant que le sommet courant est optimal. En général, il y a plusieurs sommets adjacents au sommet courant qui sont meilleurs pour l'objectif. Il faut en sélectionner un seul, la règle de sélection est appelée règle de pivotage.
Il a été montré pour les principales règles de pivotage employées que l'algorithme du simplexe pouvait prendre un temps de calcul exponentiel. En particulier, on ne sait pas s'il existe une règle de pivotage qui assurerait que l'algorithme se termine après un nombre polynomial d'étapes.
Néanmoins, l'algorithme du simplexe est très efficace en pratique et il est implémenté dans tous les solveurs de programmes linéaires. Il existe entre autres un algorithme basé sur la méthode de l'ellipsoïde, qui résout ces problèmes en un temps polynomial, mais qui est en pratique souvent moins performant que l'algorithme du simplexe.
