Simplex-Méthode, pour la programmation linéaire.

Simplex-Méthode

Qu'est-ce que la méthode Simplex ? En optimisation mathématique, la méthode du simplexe est un algorithme bien connu utilisé pour la programmation linéaire. Selon le journal Computing in Science

La méthode du simplexe présente une stratégie organisée pour évaluer les sommets d'une région réalisable. Cela permet de trouver la valeur optimale de la fonction objectif.

George Dantzig a développé la méthode du simplexe en 1946. Cette méthode est, également, appelée l'algorithme du simplexe.

Les applications

La méthode du simplexe est utilisée pour éliminer les problèmes de la programmation linéaire. Il vérifie les nœuds voisins de l'ensemble réalisable afin de s'assurer que la fonction objectif est augmentée ou non à chaque nouveau nœud.

En général, la méthode du simplexe est extrêmement puissante, elle nécessite au maximum 2 m à 3 m itérations (m désigne ici la gamme des contraintes d'égalité) et elle converge en temps polynomial attendu pour des distributions spécifiques d'entrées aléatoires.

La stratégie

La méthode du simplexe utilise une stratégie systématique pour créer et tester des solutions de sommets candidats pour un programme linéaire. À chaque itération, il sélectionne la variable qui peut apporter le plus grand changement par rapport à la solution minimale. Cette variable remplace alors l'une de ses covariables, ce qui la contraint de manière drastique, déplaçant la méthode du simplexe vers une autre partie de l'ensemble de solutions et vers la solution finale.

De plus, la méthode du simplexe peut évaluer si aucune solution n'existe réellement. On peut observer que l'algorithme est gourmand, car il choisit la meilleure option à chaque itération sans avoir besoin des informations des itérations précédentes ou suivantes.

Structure de données

Parfois, la principale structure de données appliquée par la méthode du simplexe est appelée dictionnaire. Les dictionnaires contiennent une illustration des équations qui sont correctement adaptées à la base disponible. Les dictionnaires peuvent être utilisés pour fournir une compréhension intuitive de la raison pour laquelle toutes les variables entrent et sortent de la base.