La méthode du Simplexe est un algorithme pour résoudre les problèmes de programmation linéaire. Elle a été développée par George Dantzig et consiste à se déplacer le long des sommets de la région réalisable (dans l'espace des variables), en améliorant la valeur de la fonction objectif à chaque étape jusqu'à atteindre l'optimum ou détecter que le problème est non borné ou infaisable.

Forme standard. Le Simplexe travaille avec des problèmes sous forme standard : maximisation (ou minimisation convertie en max), contraintes d'égalité et variables non négatives. Les inégalités sont transformées à l'aide de variables d'écart (≤), d'excédent et variables artificielles (≥ et =).

Méthode Big-M. Lorsqu'il y a des contraintes ≥ ou =, des variables artificielles sont ajoutées et pénalisées dans la fonction objectif par un coefficient -M (en maximisation) pour qu'elles quittent la base ; ainsi on obtient une base réalisable initiale ou on détecte l'infaisabilité.

Tableau et pivotage. L'algorithme s'applique sur un tableau représentant le système sous forme canonique par rapport à la base actuelle. À chaque itération, une variable entrante est choisie (par le coût réduit le plus négatif) et une variable sortante (par la règle du rapport minimal), et un pivotage de type Gauss-Jordan est effectué. Le processus se termine lorsqu'il n'y a plus de coûts réduits négatifs (optimum), plus de ligne sortante (non borné) ou des variables artificielles restent dans la base (infaisable).