Table des matières:
Définition - Que signifie la méthode Simplex?
La méthode simplex, 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 cours du 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 permet de 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.
Techopedia explique la méthode Simplex
La méthode simplex est utilisée pour éradiquer les problèmes de programmation linéaire. Il examine les sommets adjacents de l'ensemble réalisable en séquence pour s'assurer que, à chaque nouveau sommet, la fonction objectif augmente ou n'est pas affectée. En général, la méthode simplex est extrêmement puissante, ce 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 vertex candidates à un programme linéaire. À 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 simplex 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 d'itérations antérieures 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 qui sont correctement ajustées à la base existante. Les dictionnaires peuvent être utilisés pour offrir une compréhension intuitive de la raison pour laquelle toutes les variables entrent et sortent de la base.
