Simplex-Verfahren

Das Simplex-Verfahren ist der von George B. Dantzig 1947 entwickelte Algorithmus für die lineare Programmierung und das Fundament des Operations Research. Kernidee: der zulässige Bereich eines LP in Standardform max c^T x s.t. Ax = b, x ≥ 0 ist ein konvexes Polytop, und eine lineare Zielfunktion nimmt ihr Optimum an einer Ecke an; jede Ecke entspricht einer Basislösung (BFS), in der m Basisvariablen positiv und n-m Nichtbasisvariablen null sind. Ablauf: (1) initiale BFS finden (Big-M- oder Zweiphasen-Methode); (2) reduzierte Kosten c_j - c_B^T B^(-1) A_j berechnen; gilt ≥ 0 für alle Nichtbasisvariablen, ist die aktuelle BFS optimal; (3) eintretende Variable mit negativer reduzierter Kostenfunktion wählen (Dantzig-Regel: kleinste/negativste), austretende Variable per Mindestquotientenregel bestimmen, pivotieren und zu Schritt (2) zurück. Geometrisch wandert das Verfahren von einer Polytopecke zur benachbarten Ecke. Komplexität: Klee und Minty (1972) zeigten anhand des Klee-Minty-Würfels die exponentielle Worst-Case-Laufzeit; Durchschnitts- und Smoothed Analysis (Spielman und Teng 2004) belegen jedoch polynomielle Laufzeit im Mittel — eine Erklärung für die überragende praktische Geschwindigkeit. Varianten: (a) revidiertes Simplex mit Sparse-Matrix-Faktorisierung für große Probleme; (b) duales Simplex (Lemke 1954) verfährt über duale Zulässigkeit; (c) Netzwerk-Simplex löst Transport- und Zuordnungsprobleme über Baumstrukturen in Sekunden. Cycling — Endlosschleife an einer degenerierten Ecke — wird durch Blands Regel (1977) oder lexikographisches Pivoting verhindert. In modernen LP-Lösern wird das Simplex neben Innere-Punkte-Verfahren angeboten und dominiert insbesondere im Warm-Start-Kontext, vor allem im MILP-Branch-and-Cut.