Un algorithme itératif pour résoudre des problèmes de programmation linéaire en se déplaçant le long des arêtes du polytope admissible entre solutions de base admissibles jusqu'à atteindre un point extrémal optimal.

Principe

Exploiter la structure polyédrique d'un programme linéaire : les sommets correspondent à des solutions de base admissibles et l'optimalité se atteint par des opérations de pivot locales qui améliorent l'objectif.

Démonstration

Résoudre un problème d'alimentation en initialisant une solution de base admissible, calculer les coûts réduits, effectuer des pivots vers des sommets adjacents présentant un coût réduit négatif et s'arrêter lorsqu'il n'existe plus de pivot améliorant.

Mauvaise application

Appliquer la méthode simplex sans vérifier la dégénérescence ou sans dispositifs anti-cyclage peut conduire à des boucles infinies ou à des tableaux répétés lorsque plusieurs bases partagent le même sommet.

Conséquence

Lorsqu'elle est correctement appliquée, la méthode fournit une solution optimale au sommet et des informations duales (prix d'ombre) ainsi que des certificats d'infaisabilité ou d'unboundedness si nécessaire.

Inversion

Plutôt que de parcourir la frontière, les algorithmes intérieurs traversent l'intérieur admissible en utilisant des termes barrière ; ces méthodes substituent aux pivots explicites un suivi du chemin central.

Limite

S'applique uniquement aux programmes linéaires (contraintes affines et objectif linéaire) ; les problèmes non linéaires, entiers ou non convexes demandent des modifications ou d'autres algorithmes.

Tension sémantique

Tension entre le 'pivotement combinatoire' (changements discrets de base) et le 'suivi de chemin continu' (méthodes intérieures) comme voies alternatives vers l'optimalité en optimisation convexe.

Synthèse

La méthode simplex présente la programmation linéaire comme une navigation combinatoire d'un polytope convexe : effectuer des pivots algébriques correspondant à des déplacements géométriques entre sommets jusqu'à satisfaire les conditions d'optimalité.