Ein iteratives Verfahren zur Lösung linearer Programmierungsprobleme durch Bewegung entlang der Kanten des zulässigen Polyeders zwischen Basislösungen, bis ein optimaler Extrempunkt erreicht ist.

Prinzip

Ausnutzen der polyedrischen Struktur eines linearen Programms: Ecken entsprechen Basislösungen, und Optimalität kann durch lokale Pivot-Operationen erreicht werden, die das Ziel verbessern.

Demonstration

Ein Diätproblem lösen, indem man mit einer zulässigen Basislösung startet, reduzierte Kosten berechnet, zu benachbarten Ecken mit negativem reduziertem Kostenwert pivotiert und stoppt, wenn kein verbessernder Pivot mehr existiert.

Fehlanwendung

Die Simplex-Methode ohne Prüfung auf Degeneration oder ohne Anti-Zyklus-Maßnahmen anzuwenden kann zu Endlosschleifen oder wiederholten Tableaus führen, wenn mehrere Basen dieselbe Ecke teilen.

Konsequenz

Bei korrekter Anwendung liefert das Verfahren eine optimale Ecklösung und duale Informationen (Schattenpreise) sowie Zertifikate für Unzulässigkeit oder Unbeschränktheit, falls zutreffend.

Umkehrung

Statt entlang der Randstruktur zu laufen, durchqueren Innenpunktverfahren das zulässige Innere mithilfe von Barriereterminen; diese Methoden tauschen explizite Pivot-Schritte gegen ein Fortschreiten auf dem Zentralweg.

Abgrenzung

Gilt nur für lineare Programme (affine Nebenbedingungen und lineares Ziel); nichtlineare, ganzzahlige oder nichtkonvexe Probleme erfordern Änderungen oder andere Algorithmen.

Semantische Spannung

Spannung besteht zwischen 'kombinatorischem Pivotieren' (diskrete Basiswechsel) und 'kontinuierlichem Pfadfolgen' (Innenpunktverfahren) als alternativen Wegen zur Optimalität in konvexer Optimierung.

Synthese

Die Simplex-Methode fasst lineare Programmierung als kombinatorische Navigation eines konvexen Polyeders zusammen: führe algebraische Pivot-Schritte aus, die geometrische Bewegungen zwischen Ecken entsprechen, bis Optimalitätsbedingungen erfüllt sind.