Inhalt
Ganzzahlige lineare Optimierung| Beispiel | |
Ganzzahlige lineare Optimierung
Beispiel
Im nebenstehenden Bild ist das ganzzahlige lineare Programm
dargestellt. Die zulässigen ganzzahligen Punkte sind rot eingezeichnet, und die rot gestrichelten Linien kennzeichnen ihre konvexe Hülle, also das kleinste Polyeder, das alle diese Punkte enthält. Über diesem Polyeder soll eigentlich optimiert werden, aber es ist meist nicht genau bekannt. Die blauen Linien zusammen mit den Koordinatenachsen begrenzen das Polyeder P der LP-Relaxierung, das durch das Ungleichungssystem ohne Ganzzahligkeitsbedigungen gegeben ist. Ziel der Optimierung ist es, die schwarz gestrichelte Linie so weit parallel nach oben (in Richtung des Vektors c = (0;1)) zu verschieben, dass sie das jeweilige Polyeder gerade noch berührt. Die Optimallösungen des ganzzahligen Problems sind also die Punkte (1;2) und (2;2) mit dem Zielfunktionswert cT x = (0;1)T (1;2) = 2. Die – in diesem Fall eindeutige – optimale Lösung der LP-Relaxierung mit dem Zielfunktionswert 2,8 ist der blau markierte Punkt LPopt = (1, 8;2, 8), der nicht ganzzahlig und damit auch nicht zulässig für das IP ist.
Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Ganzzahlige 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