Die Simplex-Methode ist ein Algorithmus zur Lösung von Problemen der linearen Programmierung. Sie wurde von George Dantzig entwickelt und besteht darin, sich entlang der Ecken des zulässigen Bereichs (im Variablenraum) zu bewegen und den Zielfunktionswert bei jedem Schritt zu verbessern, bis das Optimum erreicht oder Unbeschränktheit bzw. Unlösbarkeit erkannt wird.

Standardform. Simplex arbeitet mit Problemen in Standardform: Maximierung (oder Minimierung umgewandelt in Max), Gleichheitsrestriktionen und nichtnegative Variablen. Ungleichungen werden mit Schlupfvariablen (≤), Überschuss und künstlichen Variablen (≥ und =) umgewandelt.

Big-M-Methode. Bei ≥ oder = Restriktionen werden künstliche Variablen hinzugefügt und in der Zielfunktion mit einem Koeffizienten -M (bei Maximierung) bestraft, damit sie die Basis verlassen; so erhält man eine zulässige Ausgangsbasis oder erkennt Unlösbarkeit.

Tableau und Pivotierung. Der Algorithmus wird auf einem Tableau angewendet, das das System in kanonischer Form bezüglich der aktuellen Basis darstellt. In jeder Iteration wird eine eintretende Variable (nach negativstem reduziertem Kosten) und eine austretende Variable (nach der Minimal-Quotienten-Regel) gewählt, und Gauß-Jordan-Pivotierung durchgeführt. Der Prozess endet, wenn es keine negativen reduzierten Kosten (Optimum), keine austretende Zeile (unbeschränkt) oder künstliche Variablen in der Basis (unlösbar) gibt.