Définition - Que signifie la méthode Simplex?
La méthode du simplexe, en optimisation mathématique, est un algorithme bien connu utilisé pour la programmation linéaire. Selon la revue Computing in Science & Engineering, cette méthode est considérée comme l'un des 10 meilleurs algorithmes nés au XXe siècle.
La méthode simplex présente une stratégie organisée pour évaluer les sommets d'une région réalisable. Cela aide à déterminer la valeur optimale de la fonction objectif.
George Dantzig a développé la méthode simplex en 1946.
La méthode est également connue sous le nom d'algorithme simplex.
Definir Tech explique la méthode Simplex
La méthode simplex est utilisée pour éliminer les problèmes de programmation linéaire. Il examine les sommets adjacents de l'ensemble des faisables en séquence pour s'assurer qu'à chaque nouveau sommet, la fonction objectif augmente ou n'est pas affectée. En général, la méthode du simplexe est extrêmement puissante, qui prend généralement 2 à 3 m d'itérations au maximum (ici, m désigne la plage de contraintes d'égalité), et elle converge en temps polynomial anticipé pour des distributions spécifiques d'entrée aléatoire.
La méthode simplex utilise une stratégie systématique pour générer et tester des solutions de sommets candidats à un programme linéaire. A chaque itération, il choisit la variable qui peut apporter la plus grande modification vers la solution minimale. Cette variable remplace alors l'une de ses covariables, ce qui la limite le plus radicalement, déplaçant ainsi la méthode du simplexe vers une autre partie de l'ensemble de solutions et vers la solution finale.
De plus, la méthode simplex est capable d'évaluer si aucune solution n'existe réellement. On peut observer que l'algorithme est gourmand car il opte pour la meilleure option à chaque itération, sans demande d'informations provenant des itérations précédentes ou à venir.
Parfois, la structure de données principale appliquée par la méthode simplex est appelée dictionnaire. Les dictionnaires incluent une illustration de l'ensemble d'équations correctement ajusté à la base existante. Les dictionnaires peuvent être utilisés pour offrir une compréhension intuitive des raisons pour lesquelles toutes les variables entrent et sortent de la base.