Lineare Optimierung

Anwendungen

Nichtlineare und ganzzahlige Optimierung

Viele Anwendungsprobleme lassen sich mit kontinuierlichen Variablen nicht sinnvoll modellieren, sondern erfordern die Ganzzahligkeit einiger Variablen. Beispielsweise können keine 3,7 Flugzeuge gekauft werden, sondern nur eine ganze Anzahl, und ein Bus kann nur ganz oder gar nicht fahren, aber nicht zu zwei Dritteln. Bei der Verwendung von Branch-and-Cut zur Lösung eines solchen ganzzahligen linearen Optimierungsproblems müssen sehr viele ähnliche lineare Programme hintereinander als Unterproblem gelöst werden. Eine optimale ganzzahlige Lösung eines linearen Programms zu finden ist NP-vollständig, aber parametrisierbar in der Anzahl der Variablen. Es ist sogar NP-vollständig, irgendeine ganzzahlige Lösung eines linearen Programms zu finden.Auch zur Lösung nichtlinearer Optimierungsprobleme gibt es Algorithmen, in denen lineare Programme als Unterproblem gelöst werden müssen (z. B. Sequential Linear Programming).

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