- Algorithme Du Simplexe
-
Algorithme du simplexe
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 polytope dans l'espace à n dimensions (polygone en 2 dimensions et polyèdre en 3 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 polytope 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.
On peut montrer que le nombre d'itérations de l'algorithme est majoré par :
où ν est le plus petit nombre d'arêtes reliées à un même sommet du polytope parcouru par le simplexe et N est le nombre de sommets. On remarquera que ν est minoré par la dimension de l'espace dans lequel vit le polytope.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. Les autres algorithmes de résolution de programmes linéaires sont basés soit sur la méthode de l'ellipsoïde soit sur la méthode du point intérieur.
Voir aussi
Liens externes
- (en) Simplex Algorithm. Illustration détaillée de l'exécution de l'algorithme (version « tableau »).
- (fr) Exemple de l'algorithme du Simplexe. L’algorithme du simplexe appliqué de manière très didactique à un exemple (version « tableau ») - fichier pdf.
Catégories : Algorithme numérique | Algorithme d'optimisation
Wikimedia Foundation. 2010.
