Lineare Optimierung

Geschichte

Die Methode der linearen Optimierung wurde 1939 von dem sowjetischen Mathematiker Leonid Witaljewitsch Kantorowitsch in seinem Aufsatz „Mathematische Methoden für die Organisation und Planung der Produktion“ eingeführt.http://www.feg.unesp.br/~mapereira/PL_arquivos/ManSci-v6_n4-366_422-1960.pdf Kurz danach veröffentlichte der Amerikaner Frank L. Hitchcock eine Arbeit zu einem Transportproblem. Damals erkannte man noch nicht die Bedeutung dieser Arbeiten. Unter anderem für seinen Beitrag zur linearen Optimierung bekam Kantorowitsch aber 1975 den Nobelpreis für Wirtschaftswissenschaften.

Mitte der 1940er Jahre erkannte George Dantzig, dass sich viele praktische Beschränkungen durch lineare Ungleichungen beschreiben ließen, und ersetzte erstmals die bis dahin vorherrschenden Faustregeln zur Lösung von Planungsproblemen durch eine (lineare) Zielfunktion. Insbesondere etablierte er damit eine klare Trennung zwischen dem Ziel der Optimierung und den Mitteln zur Lösung des Planungsproblems.

Den Durchbruch für die lineare Optimierung schaffte Dantzig 1947, als er eine Arbeit über das Simplex-Verfahren veröffentlichte, das heute eines der meistgenutzten Verfahren zur Lösung linearer Programme ist. Interesse an dieser Arbeit zeigten zunächst die amerikanischen Militärs, speziell die US Air Force, die militärische Einsätze optimieren wollten. In den Folgejahren entwickelten Dantzig, John von Neumann, Oskar Morgenstern, Tjalling Koopmans und andere das Verfahren und die zugehörige Theorie weiter und stellten Zusammenhänge zur Spieltheorie her. Mit dem Aufkommen von Computern Mitte der 1950er Jahre konnte man auch größere Probleme lösen. Etwa ab 1950 entdeckte die Wirtschaft, insbesondere Ölraffinerien, die Anwendungsmöglichkeiten der linearen Optimierung. Ab den 1970er Jahren profitierte der Simplex-Algorithmus von algorithmischen Fortschritten der numerischen linearen Algebra. Insbesondere die Entwicklung numerisch stabiler LR-Zerlegungen zur Lösung großer linearer Gleichungssysteme trugen maßgeblich zum Erfolg und der Verbreitung des Simplex-Verfahrens bei.

Im Jahre 1979 veröffentlichte Leonid Khachiyan die Ellipsoidmethode, mit der lineare Programme erstmals – zumindest theoretisch – in Polynomialzeit gelöst werden konnten. 1984 begannen Narendra Karmarkar und andere mit der Entwicklung von Innere-Punkte-Verfahren zur Lösung linearer Programme. Diese Algorithmen, die als erste polynomiale Lösungsmethoden auch das Potential zum praktischen Einsatz hatten, wurden innerhalb des nachfolgenden Jahrzehnts noch wesentlich verbessert. Parallel dazu wuchs die Bedeutung des Simplex-Verfahrens zur Lösung von Unterproblemen in der ganzzahligen linearen Optimierung. Anfang der 1990er Jahre wurden hier noch einmal große Fortschritte durch die Entwicklung neuer Pivotstrategien für den dualen Simplex-Algorithmus erzielt, insbesondere durch das dual steepest edge pricing von John Forrest und Donald Goldfarb.

Sowohl das Simplex-Verfahren als auch verschiedene Innere-Punkte-Verfahren sind nach wie vor Gegenstand aktueller Forschung. Die lineare Optimierung wird heute in sehr vielen Bereichen zur Lösung praktischer Probleme eingesetzt. Unter der in praktischen Anwendungen fast immer erfüllten Voraussetzung, dass die auftretenden LP-Matrizen dünnbesetzt sind (also nur wenige Nicht-Null-Einträge besitzen), können heute lineare Programme mit mehreren Hunderttausend Variablen oder Ungleichungen innerhalb weniger Minuten bis Stunden optimal gelöst werden. Die tatsächliche Lösungszeit hängt dabei neben dem verwendeten Lösungsverfahren auch stark von der Anzahl und Anordnung der Nicht-Null-Einträge in der beteiligten Matrix und von der Wahl der Startlösung ab.

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