méthode du simplexe
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 la revue 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 vous 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 algorithme du simplexe.
Applications
La méthode du simplexe est utilisée pour éliminer les problèmes de programmation linéaire. Vérifiez les nœuds voisins de l'ensemble des possibles pour vous assurer que la fonction objectif augmente ou non à chaque nouveau nœud.
En général, la méthode du simplexe est extrêmement puissante, nécessite au plus 2 à 3 m itérations (m représente ici l'intervalle des contraintes d'égalité) et converge dans le temps polynomial attendu pour des distributions spécifiées d'entrées aléatoires.
La stratégie
La méthode du simplexe utilise une approche systématique pour créer et tester des solutions de sommets candidates pour un programme linéaire. À chaque itération, sélectionnez la variable qui peut faire le plus grand changement par rapport à la plus petite solution. Cette variable remplace alors l'une de ses covariables, ce qui la contraint sévèrement, déplaçant la méthode du simplexe ailleurs dans l'ensemble de solutions et vers la solution finale.
De plus, la méthode du simplexe peut évaluer s'il n'y a vraiment pas de solution. Nous pouvons voir que l'algorithme est gourmand, puisqu'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 structure de données principale appliquée par la méthode du simplexe est appelée un dictionnaire. Les dictionnaires contiennent une illustration des équations qui correspondent correctement à 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 de données.