mini|240px|Das Primalsimplex-Verfahren läuft von einer Ecke eines LP-Polyeders zur nächsten, bis keine Verbesserung mehr möglich ist Ein Simplex-Verfahren (auch Simplex-Algorithmus) ist ein Optimierungsverfahren der Numerik zur Lösung linearer Optimierungsprobleme, auch als Lineare Programme (LP) bezeichnet. Es löst ein solches Problem nach endlich vielen Schritten exakt oder stellt dessen Unlösbarkeit oder Unbeschränktheit fest. Die Grundidee der Simplex-Verfahren wurde 1947 von George Dantzig vorgestellt; seitdem haben sie sich durch zahlreiche Verbesserungen zu den wichtigsten Lösungsverfahren der linearen Optimierung in der Praxis entwickelt. Simplex-Verfahren sind Pivotverfahren.
Obwohl bisher für jede Variante des Verfahrens ein Beispiel konstruiert werden konnte, bei dem der Algorithmus exponentielle Laufzeit benötigt, läuft ein Simplex-Algorithmus in der Praxis meist schneller als andere Verfahren, obwohl es zur Lösung einzelner linearer Programme auch andere konkurrenzfähige Methoden gibt, wie z. B. Innere-Punkte-Verfahren. Der große Vorteil eines Simplex-Algorithmus liegt jedoch darin, dass er bei leichter Veränderung des Problems – beispielsweise dem Hinzufügen einer zusätzlichen Bedingung – einen „Warmstart“ von der letzten verwendeten Lösung durchführen kann und daher meist nur wenige Iterationen zur erneuten Lösung benötigt, während andere Verfahren von vorne beginnen müssen. Darüber hinaus nutzt ein Simplex-Verfahren die engen Zusammenhänge zwischen einer linearen Optimierungsaufgabe und seiner dualen Aufgabe aus und löst grundsätzlich beide Probleme gleichzeitig. Beide Eigenschaften sind in der ganzzahligen linearen oder auch nichtlinearen Optimierung dort von Bedeutung, wo sehr viele ähnliche lineare Aufgaben in Folge gelöst werden müssen.
Die geometrische Grundidee des Algorithmus besteht darin, von einer beliebigen Ecke eines Polytops, das durch die lineare Optimierungsaufgabe definiert wird, entlang seiner Kanten zu einer optimalen Ecke zu laufen. Der Name des Verfahrens rührt daher, dass die nichtnegativen Linearkombinationen der Basisspalten in jeder Iteration einen simplizialen Kegel (d. h. einen Simplex) beschreiben. Ein Namensvetter dieses Verfahrens namens Downhill-Simplex-Verfahren (Nelder und Mead 1965) basiert ebenfalls auf einem Simplex, ist aber ein iteratives Verfahren zur nichtlinearen Optimierung.
Geschichte
Die Grundlagen der linearen Optimierung wurden 1939 von dem russischen Mathematiker Leonid Witaljewitsch Kantorowitsch in seinem Buch „Mathematische Methoden in der Organisation und Planung der Produktion“ gelegt. Kurz danach (1941) präsentierte der US-Amerikaner Frank L. Hitchcock (1875–1957) eine Arbeit zu einem Transportproblem. Im Jahre 1947 veröffentlichte George Dantzig das Simplex-Verfahren, mit dem lineare Programme erstmals systematisch gelöst werden konnten. Eine der ersten dokumentierten Anwendungen der neuen Methode war das Diäten-Problem von George Stigler, dessen Ziel eine möglichst kostengünstige Nahrungszusammensetzung für Soldaten war, die bestimmte Mindest- und Höchstmengen an Vitaminen und anderen Inhaltsstoffen erfüllte. An der optimalen Lösung dieses linearen Programms mit neun Ungleichungen und 77 Variablen waren damals neun Personen beschäftigt, die zusammen etwa 120 Manntage Rechenarbeit benötigten.Robert Bixby: Solving real-world linear programs: A decade and more of progress. In: Operations Research. Band 50, Nr. 1, 2002, S. 3–15. Interesse an dieser Arbeit zeigte zunächst das amerikanische Militär, speziell die US Air Force, die militärische Einsätze optimieren wollte. In den Folgejahren entwickelten John von Neumann und Oskar Morgenstern das Verfahren weiter.
Mit dem Aufkommen von Computern Mitte der 1950er Jahre konnten auch größere Probleme gelöst werden. Es wurden spezielle Varianten der Simplexmethode entwickelt, wie das revidierte Simplex-Verfahren, das sehr sparsam mit dem damals knappen und teuren Hauptspeicher umging. Im Jahre 1954 brachte William Orchard-Hays die erste kommerzielle Implementierung dieses Verfahrens auf den Markt. Im selben Jahr veröffentlichten Carlton Lemke und E. M. L. Beale das duale Simplex-Verfahren, das sich heute – nach weiteren Verbesserungen – zu einer der Standardmethoden zur Lösung linearer Programme entwickelt hat.
Die theoretische Komplexität des Simplex-Verfahrens war lange Zeit unklar. Erst im Jahre 1972 konstruierten Victor Klee und George Minty ein Beispiel, bei dem der Algorithmus alle exponentiell vielen Ecken eines Polyeders abläuft, und zeigten damit die exponentielle Laufzeit des Verfahrens. Ähnliche Beispiele wurden bisher für alle bekannten Varianten des Verfahrens gefunden.
Ab den 1970er Jahren profitierte der Simplex-Algorithmus – wie auch andere Verfahren der Linearen Optimierung – von algorithmischen Fortschritten der numerischen linearen Algebra, insbesondere bei der Lösung großer linearer Gleichungssysteme. Vor allem die Entwicklung numerisch stabiler LR-Zerlegungen für dünnbesetzte Matrizen trug maßgeblich zum Erfolg und der Verbreitung des Simplex-Verfahrens bei.
Seit Mitte der 1970er bis Anfang der 1990er Jahre wurde das Verfahren durch die Entwicklung neuer Pivotstrategien deutlich verbessert. Vor allem die wachsende Bedeutung der ganzzahligen linearen Optimierung in den 1980er Jahren sowie die Entwicklung des dual steepest edge pricing in der Implementierung von J. J. Forrest und Donald Goldfarb (1992) machten das duale Simplex-Verfahren zum ernsthaften Konkurrenten für andere Lösungsmethoden. Umgekehrt hatte diese Verbesserung des dualen Simplex-Algorithmus einen maßgeblichen Anteil am Erfolg von Schnittebenenverfahren und Branch-and-Cut zur Lösung ganzzahliger linearer Programme. Darüber hinaus sorgten neue Preprocessing-Methoden in den 1990er Jahren dafür, dass immer größere LPs gelöst werden konnten. Unter der – in praktischen Anwendungen fast immer erfüllten – Voraussetzung, dass die auftretenden LP-Matrizen dünnbesetzt sind, können heute lineare Programme mit mehreren hunderttausend Variablen oder Ungleichungen innerhalb weniger Stunden optimal gelöst werden.
Grundidee
Die Simplex-Verfahren dienen zur Lösung linearer Optimierungsaufgaben, das ist die Suche nach reellen Variablenwerten, die ein System linearer Ungleichungen und Gleichungen erfüllen und dabei eine lineare Zielfunktion maximieren oder minimieren. Ausgegangen wird dabei von der Form (LP) wobei eine Matrix mit reellen Einträgen ist, der sogenannte Zielfunktionsvektor, und ein Spaltenvektor mit nichtnegativen Einträgen . Ziel ist es, einen Punkt zu finden, der das lineare Ungleichungssystem erfüllt und einen möglichst hohen Zielfunktionswert hat.
Jedes lineare Programm kann durch einfache Umformungen in die Form (LP) gebracht werden, bei welcher die Vorzeichen in freilich immer noch beliebig sind. Das geschieht wie folgt: Ein Minimierungsproblem kann durch Multiplikation der Zielfunktion mit in ein Maximierungsproblem verwandelt werden. Ungleichungen können als geschrieben werden. Vorhandene Gleichungsgruppen können in Ungleichungsgruppen mit aufgespalten werden. Variablengruppen mit beliebigem Wertebereich können über eine zusätzliche Variable und durch nichtnegative Variablen ersetzt werden. Im Gegensatz zu diesen Umformungen ist die immer vorausgesetzte Startbedingung nur über die Lösung einer Hilfsaufgabe in einer sogenannten „Phase 1“ zu erreichen; dabei ist diese Hilfsaufgabe grundsätzlich ebenso aufwendig wie die eigentliche Optimierung.
Geometrisch lässt sich die Menge der zulässigen Lösungen, also die Menge der Punkte mit nichtnegativen Koordinaten, die das lineare Ungleichungssystem erfüllen, als konvexes Polyeder (mehrdimensionales Vieleck) interpretieren, dessen Dimension durch die Anzahl der Variablen nach oben begrenzt ist. Ziel ist es, einen Punkt in mit möglichst hohem Zielfunktionswert zu finden. Anschaulich entspricht dies der Verschiebung der Hyperebene so weit wie möglich in Richtung des Vektors , so dass sie gerade noch das Polyeder berührt. Alle Berührungspunkte sind dann optimal.
Für die Menge der zulässigen Lösungen gibt es drei Möglichkeiten: das LP besitzt keine zulässigen Lösungen, d. h., das Polyeder ist leer (z. B. ). das LP ist unbeschränkt, d. h., es gibt Lösungen mit beliebig hohem Zielfunktionswert (z. B. ). es gibt genau eine oder unendlich viele Optimallösungen, die dann alle auf einer gemeinsamen Seitenfläche (Ecke, Kante, …) des Polyeders liegen.
Man kann zeigen, dass es immer eine optimale Ecke gibt, falls das Optimierungsproblem überhaupt zulässige Lösungen besitzt und beschränkt ist. Man kann sich also bei der Suche nach Optimallösungen auf die Ecken des Polyeders beschränken, von denen es allerdings sehr viele geben kann.
Die anschauliche Grundidee des Simplex-Verfahrens besteht nun darin, sich schrittweise von einer Ecke des Polyeders zu einer benachbarten Ecke mit besserem Zielfunktionswert zu hangeln, bis es keinen besseren Nachbarn mehr gibt. Da es sich bei der linearen Optimierung um ein konvexes Optimierungsproblem handelt, ist die so gefundene lokal optimale Ecke dann auch global optimal, d. h., es gibt in ganz keine andere Ecke mit besserem Zielfunktionswert mehr.
Laufzeit
Die Zahl der Ecken eines Polyeders kann exponentiell in der Anzahl der Variablen und Ungleichungen sein. Beispielsweise lässt sich der -dimensionale Einheitswürfel durch lineare Ungleichungen beschreiben, besitzt aber 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.Harvey J. Greenberg: (PDF) University of Colorado at Denver, 1997. Ä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-Verfahrens 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.
Mathematische Beschreibung
Das Simplex-Verfahren setzt sich aus zwei Phasen zusammen: Phase I bestimmt eine zulässige Startlösung oder stellt fest, dass das Problem keine Lösung besitzt, Phase II verbessert eine bestehende Lösung immer weiter, bis keine Verbesserung der Zielfunktion mehr möglich ist oder die Unbeschränktheit des Problems festgestellt wird.