Lineare Optimierung

Komplexität und Lösungsverfahren

Das Finden einer Optimallösung bzw. die Feststellung, dass ein LP keine Lösung besitzt, ist mit Hilfe von Innere-Punkte-Verfahren oder der Ellipsoidmethode in Polynomialzeit möglich, so dass die Lineare Optimierung aus Sicht der Komplexitätstheorie ein leicht lösbares Problem ist. Aus praktischer Sicht ist jedoch oft das Simplex-Verfahren schneller, obwohl es theoretisch exponentielle Laufzeit besitzt. Es ist bis heute unbekannt, ob es einen streng polynomialen Algorithmus zur Lösung allgemeiner linearer Programme gibt, also einen Algorithmus, dessen Laufzeit nicht von der Größe der auftretenden Zahlen abhängt.

Simplex-Verfahren

Das Simplex-Verfahren läuft die Ecken des Polyeders ab, bis es an einer Optimallösung angekommen ist.

siehe Hauptartikel: Simplex-Verfahren

Das Simplex-Verfahren, das im Jahre 1947 von George Dantzig entwickelt und seitdem wesentlich verbessert wurde, ist der wichtigste Algorithmus zur Lösung linearer Programme in der Praxis. Die Grundidee besteht darin, von einer Ecke des Polyeders zu einer benachbarten Ecke mit besserem Zielfunktionswert zu laufen, bis dies nicht mehr möglich ist. Da es sich bei der linearen Optimierung um ein konvexes Optimierungsproblem handelt, ist die damit erreichte lokal optimale Ecke auch global optimal. Das Verfahren ist im nebenstehenden Bild illustriert: Ziel ist es, einen möglichst weit oben liegenden Punkt des Polyeders zu finden. In roter Farbe ist ein möglicher Pfad des Simplex-Verfahrens entlang der Ecken des Polyeders dargestellt, wobei sich der Zielfunktionswert mit jedem Schritt verbessert.

Aus komplexitätstheoretischer Sicht benötigt der Simplex-Algorithmus im schlechtesten Fall exponentielle Laufzeit. Für jede Variante des Algorithmus konnte bisher ein Beispiel konstruiert werden, bei dem der Algorithmus alle Ecken des Polyeders abläuft, meist basierend auf dem Klee-Minty-Würfel. Aus praktischer Sicht sind solche Fälle allerdings sehr selten. Bei sogenannten entarteten linearen Programmen, bei denen eine Ecke durch mehr Ungleichungen definiert wird als unbedingt nötig (beispielsweise durch drei Ungleichungen im zweidimensionalen Raum), kann es allerdings passieren, dass der Algorithmus, wie in diesem Beispiel, immer wieder dieselbe Ecke betrachtet, anstatt zur nächsten Ecke zu wechseln. Dieses Problem tritt bei praktischen Planungsproblemen häufig auf und kann dazu führen, dass der Algorithmus nicht terminiert oder der Zielfunktionswert sich über viele Iterationen hinweg nicht verbessert. Gute Simplex-Implementierungen entdecken solche Fälle und behandeln sie beispielsweise durch eine leichte Perturbation (absichtliche numerische Störung) des Problems, die später wieder rückgängig gemacht wird.

Unter der Voraussetzung, dass die Matrix A dünnbesetzt ist (d. h. nur wenige Koeffizienten ungleich Null enthält), was in der Praxis fast immer der Fall ist, können mit dem Simplex-Verfahren heute sehr große LPs in annehmbarer Zeit optimal gelöst werden. Ein großer Vorteil des Simplex-Verfahrens besteht darin, dass es nach dem Hinzufügen einer Ungleichung oder Variable im LP oder nach einer leichten Änderung der Koeffizienten einen „Warmstart“ von einer vorher bereits erreichten Ecke aus durchführen kann, so dass nur wenige Iterationen zum erneuten Finden einer Optimallösung notwendig sind. Dies ist insbesondere im Zusammenhang mit Schnittebenenverfahren oder Branch-and-Cut zur Lösung ganzzahliger linearer Programme von großer Bedeutung, wo sehr viele ähnliche LPs in Serie gelöst werden müssen.

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Lineare Optimierung 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