Méthode du simplexe
La présente feuille implémente la méthode du simplexe pour maximiser une forme linéaire sur un polyèdre convexe, en suivant la présentation faite par Schrijver (Theiry of linear and integer programming). Il n'y a aucun effort de fait pour l'efficacité de l'implémentation; on essaie par contre de rester proche de la description géométrique.
Le problème est le suivant: trouver le maximum de c·x où c est un vecteur ligne fixé à n composantes et x un vecteur colonne dans ℝn assujetti aux contraintes A·x ≤ b, où A est une matrice m×n et b un vecteur à m composantes (cette notation matricielle représente un système de m inégalités linéaires sur x). Ces contraintes définissent un polyèdre convexe P dans ℝn, et le maximum, s'il existe, sera atteint en un sommet (ou point extrémal) de P.
L'hypothèse qui sera toujours faite est que la matrice A est de rang n. Sinon, P n'a pas de sommet. L'hypothèse est trivialement vérifiée quand les contraintes incluent le fait que toutes les composantes de x sont ≥ 0.
Recherche du maximum à partir d'un sommet
Trouver un sommet d'où partir
On met tout ensemble