Das Simplex-Verfahren (auch Simplex-Algorithmus) ist ein Optimierungsverfahren zur Lösung linearer Optimierungsprobleme. Nach endlich vielen Schritten liefert es ein Produkt oder stellt dessen Unlösbarkeit fest. Die Grundidee des Simplex-Verfahrens wurde 1947 von George Dantzig vorgestellt. Seitdem hat es sich durch zahlreiche Verbesserungen zum wichtigsten Lösungsverfahren der linearen Optimierung in der Praxis entwickelt.
Die geometrische Grundidee des Algorithmus besteht darin, von einer beliebigen Ecke des Polyeders, das durch das lineare Programm definiert wird, entlang seiner Kanten zu einer optimalen Ecke zu laufen. 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.
Geschichtliches und Hintergrund
Der russische Mathematiker Leonid Witaljewitsch Kantorowitsch lieferte 1939 die ersten Grundlagen der linearen Optimierung. In seinem Buch „Mathematische Methoden in der Organisation und Planung der Produktion“ legte er die Grundbausteine.
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 G.J. Stigler. Er wollte die kostengünstigste Nahrungszusammensetzung für Soldaten, die bestimmte Mindest- und Höchstmengen an Vitaminen und anderen Inhaltsstoffen erfüllen musste, optimieren. 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. Das amerikanische Militär zeigt sich an dieser Arbeit interessiert, speziell die US Air Force, die militärische Einsätze optimieren wollte.
Seit Mitte der 1970er bis Anfang der 1990er Jahre wurde das deutlich verbessert. Durch die rasche Entwicklung der Computertechnologie verringerten sich die anfänglichen Sorgen der Entwickler über die Komplexität. Da leistungsfähigere Rechner und Speicher erschwinglich sind.
Grundidee des Simplex-Verfahrens
Das Simplex-Verfahren dient zur Lösung linearer Programme der Form Simplex Ausgangsgleichung
wobei A ∈ ℜmxn eine Matrix mit reellen Einträgen, c ∈ ℜn der sogenannte Zielfunktionsvektor und b ∈ ℜm ein Vektor mit Beschränkungen ist. Ziel ist es, einen Punkt x zu finden, der das lineare Gleichungssystem erfüllt und einen möglichst hohen Zielfunktionswert F(x) = cTx hat.
Jedes lineare Programm kann durch einfache Umformungen in diese Form gebracht werden. Insbesondere lässt sich ein Minimierungsproblem durch Multiplikation der Zielfunktion mit (-1) in ein Maximierungsproblem verwandeln.
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. Simplex Lösung 1).
das LP ist unbeschränkt, d. h. es gibt Lösungen mit beliebig hohem Zielfunktionswert (z. B. Simplex Lösung 2).
es gibt genau eine oder unendliche viele Optimallösungen, die dann alle auf einer gemeinsamen Seitenfläche (Ecke, Kante,…) des Polyeders P 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.
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 2n Ecken. Man konstruierte im Jahre 1972 einen verzerrten Einheitswü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 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 durch absichtliche numerische Störungen verhindern.
In der Praxis hängt die Laufzeit des Simplex-Verfahren oft im Wesentlichen linear von der Anzahl der Zeilen ab. Tatsächlich zeigten Mathematiker 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 des Verfahrens
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
Phase I
Man führt eine künstliche Variable zi ein um dann folgendes lineares Programm zu betrachten:
Gleichung zu Phase 1
In einer Optimallösung dieses Hilfsproblems sind die künstlichen Variablen so klein wie möglich, wobei sie immer nichtnegativ bleiben müssen. Das ursprüngliche Problem besitzt genau dann eine zulässige Lösung, wenn es eine Lösung des Hilfsproblems mit z = 0 gibt, bei der also keine künstlichen Variablen verwendet werden.
Phase II
Phase 2 ist ein iteratives Verfahren, das in jedem Schritt versucht, aus einer zulässigen Lösung eine neue Lösung mit besserem Zielfunktionswert zu konstruieren, bis dies nicht mehr möglich ist.
Als ersten Schritt zur Annäherung an das Optimum geht man vom naivsten Fall aus. Man setzt die Variablen (X und Y) gleich null. Dadurch erhält man das einfachste lineare Gleichungssystem und hat somit eine Basis, worauf man aufbauen kann. Da diese Lösung aber unbefriedigend ist, versucht man mit den folgenden Schritten das Ergebnis an das Maximum oder Minimum anzupassen. Man vereinfacht sich das Problem, indem man sich ein Produkt aus der Aufgabenstellung herausnimmt und dieses einzelne Produkt löst. Diesen Schritt führt man dann für alle anderen Produkte dann auch aus.
Das Ergebnis mit dem höchsten Nutzen, aus der vorgehenden Rechnung, dient als Basis. Ausgehend vom besten Ergebnis versucht man jetzt an einem möglichen Optimum zu gelangen, indem man offene Ressourcen möglichst günstig belegt. Dadurch gelangt man dann in mehreren Schritten an einen Wert, das dem gesuchten entspricht.
Diese Schritte muss man, im Internetzeitalter, nicht mehr händisch Lösen, da es viele kostenlose Rechner auf Mathematik-Portalen zur Verfügung stehen. Lediglich muss man Phase 1 noch händisch bewältigen, da Textinterpretation noch in den Sternen steht.
Zusammenfassung
Worum geht es?
Es ist eine lineare Gleichung f gegeben, sowie ein System von Ungleichungen, die nähere Aussagen über die Unbekannten von f geben. Durch das Simplexverfahren ist es möglich, diese Unbekannten zu ermitteln, für den Fall dass f ein Maximum oder Minimum annimmt
Benötigtes Vorwissen?
Um Phase 1 zu meistern, reichen Algebra-Kenntnisse
Um Phase 2 händisch zu lösen, wäre ein Mathematikstudium von Vorteil
Wie gehe ich am besten vor?
Schritt 1 : Ungleichungen erstellen
Schritt 2 : Ungleichungen umformen
Schritt 3 : Erstellen der ersten Simplextabelle
Schritt 4.1 : Nach einer besseren Lösung suchen
Schritt 4.2 : Schritt 4.1 wiederholen, bis nichts besseres erreicht werden kann
Schritt 5 : Lösung ablesen
→ Schritt 4 kann man durch das einsetzen in einen (Online-) Rechner ersparen.
Literatur
George B. Dantzig: Lineare Programmierung und Erweiterungen. Springer-Verlag 1966 ISBN 0-691-05913-6 www.simplexme.com: Online Simplex-Rechner http://de.wikipedia.org/wiki/Simplex-Verfahren
Martin Grötschel, Vorlesungsskript Algorithmische Diskrete Mathematik II: Lineare Optimierung
