Lineare Optimierung

Lösbarkeit aus theoretischer Sicht

Ein lineares Programm hat nicht immer eine Optimallösung. Drei Fälle sind zu unterscheiden:

1. Das LP ist unzulässig, weil sich Ungleichungen widersprechen (z. B. und ). In diesem Fall gibt es keine Lösung, die alle Ungleichungen erfüllt, d. h. das zugehörige Polyeder ist die leere Menge.
2. Das LP ist unbeschränkt, d. h. es gibt unendlich viele zulässige Lösungen mit beliebig hohen Zielfunktionswerten (z. B. ).
3. Das LP besitzt mindestens eine Optimallösung. Dies ist beispielsweise gegeben, falls das zugehörige Polyeder beschränkt, also ein Polytop, und nichtleer ist.

Die Menge der Optimallösungen bildet eine Seitenfläche (Ecke, Kante,…) des Polyeders, so dass es entweder keine, genau eine oder unendlich viele Optimallösungen gibt. Letzteres bedeutet anschaulich, dass die Zielfunktion parallel zu einer beschränkenden Hyperebene liegt. Wenn das LP lösbar und beschränkt ist, gibt es immer eine optimale Ecke, also einen optimalen Punkt, der nicht aus anderen Punkten des Polyeders konvex kombiniert werden kann. Diese Eigenschaft macht sich unter anderem das primale Simplex-Verfahren zunutze.

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