Simplex-Verfahren

Laufzeit

Die Zahl der Ecken eines Polyeders kann exponentiell in der Anzahl der Variablen und Ungleichungen sein. Beispielsweise lässt sich der n-dimensionale Einheitswürfel durch 2n lineare Ungleichungen beschreiben, besitzt aber 2ⁿ Ecken. Klee und Minty konstruierten im Jahre 1972 einen verzerrten Einheitswürfel, den sogenannten Klee-Minty-Würfel, bei dem die von Dantzig vorgestellte Variante des Simplex-Verfahrens tatsächlich alle diese Ecken besuchte. Ähnliche Beispiele wurden bisher für alle Zeilen- und Spaltenauswahlregeln gefunden. Dies bedeutet, dass der Simplex-Algorithmus in allen bisher bekannten Varianten im schlechtesten Fall exponentielle Laufzeit besitzt.

Bei degenerierten linearen Programmen, wie sie in der Praxis häufig auftreten, kann es zu sogenannten Zyklen kommen, bei dem das Simplex-Verfahren immer wieder dieselbe Ecke betrachtet und dadurch nicht terminiert. Dies lässt sich aber durch Anwendung der lexikographischen Zeilenauswahlregel oder durch absichtliche numerische Störungen verhindern.

Aus theoretischer Sicht ist das Simplex-Verfahren daher beispielsweise den Innere-Punkte-Verfahren mit polynomialer Laufzeit unterlegen. Aus praktischer Sicht hat es sich aber in vielen Fällen als schneller erwiesen. Der größte Vorteil des Simplex-Algorithmus gegenüber anderen Verfahren liegt jedoch darin, dass es bei kleinen Änderungen der Eingabedaten im Laufe des Algorithmus einen „Warmstart“ erlaubt, also die letzte berechnete Basis als Ausgangspunkt für wenige weitere (primale oder duale) Iterationen nehmen kann, während beispielsweise Innere-Punkte-Verfahren in solch einem Fall von vorne anfangen müssen. Dieser Fall tritt sehr häufig auf, wenn sehr viele ähnliche lineare Programme in Folge gelöst werden müssen, beispielsweise im Rahmen von Schnittebenenverfahren, Branch-and-Bound oder Branch-and-Cut.

In der Praxis hängt die Laufzeit des Simplex-Verfahren oft im Wesentlichen linear von der Anzahl der Zeilen ab. Tatsächlich zeigten Borgwardt und andere in den 1980er Jahren, dass solche Fälle wie der Klee-Minty-Würfel extrem selten sind und dass einige Varianten des Simplex-Algorithmus unter bestimmten Annahmen an den Input im Mittel nur polynomiale Laufzeit benötigen. Es ist aber bis heute unklar, ob es eine Variante mit polynomialer Laufzeit für alle Instanzen gibt.

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Simplex-Verfahren aus der freien Enzyklοpädιe Wιkιpedιa und steht unter der Lizenz Creative Commons CC-BY-SA 3.0 Unported (Kurzfassung). Liste der Autoren

Anbieterkennzeichnung