|
| ||||||||||||||||||||||||||||||||||
InhaltGanzzahlige lineare Optimierung
| Ganzzahlige lineare OptimierungKomplexität und LösungsverfahrenDuale Schranken und OptimalitätsbeweisAlle praktisch relevanten exakten Verfahren beruhen auf der iterativen Lösung und Modifikation einer Relaxierung, also eines einfacheren Problems, dessen Lösungsmenge alle Lösungen des Ursprungsproblems enthält. Beispielsweise verwenden Branch-and-Bound und Schnittebenenverfahren die LP-Relaxierung, lassen also zunächst die Ganzzahligkeitsbedingungen weg. Dies lässt sich auch geometrisch interpretieren: Eigentlich ist eine optimale Ecke des IP-Polyeders PI (im obigen Bild rot gestrichelt) gesucht, das von allen zulässigen ganzzahligen Punkten aufgespannt wird. Da dieses Polyeder meist nicht genau bekannt ist, wird stattdessen eine optimale Ecke des Polyeders P der LP-Relaxierung gesucht, das PI enthält (im obigen Beispiel blau umrandet). Dies geht verhältnismäßig einfach, z. B. mit dem Simplex-Verfahren.Da in der Relaxierung mehr Lösungen zugelassen sind als im Ausgangsproblem, ist ihr Optimalwert mindestens so hoch (bei einem Maximierungsproblem) wie der – unbekannte – Optimalwert des IPs, liefert also für diesen eine obere (allgemein: duale) Schranke. Gleichzeitig definiert der Wert jeder zulässigen ganzzahligen Lösung L eine untere (allgemein: primale) Schranke für den Wert einer Optimallösung, da diese ja per Definition mindestens so gut ist wie L. Durch Vergleich der oberen und unteren Schranken kann ein maximaler relativer Abstand, der sogenannte Optimalitätsgap, zwischen dem Wert einer gefundenen Lösung und dem Optimalwert angegeben werden, ohne diesen genau zu kennen. Im obigen Beispiel beträgt der optimale Wert der LP-Relaxierung 2,8. Der Optimalwert des ganzzahligen Problems kann nicht höher sein, da dort weniger Lösungen zugelassen sind als in der LP-Relaxierung. Der Punkt (1;1) (den man beispielsweise durch Raten oder über eine Heuristik gefunden haben kann) ist eine zulässige Lösung des ganzzahligen Problems und hat den Zielfunktionswert 1. Eine optimale Lösung ist per Definition mindestens genauso gut wie die gefundene Lösung. Der Optimalwert des ganzzahligen Problems muss also zwischen 1 und 2,8 liegen. Der absolute Optimalitätsgap ist die Differenz zwischen der oberen und unteren Schranke, hier also (2, 8 - 1) = 1, 8 Der häufiger angegebene relative Optimalitätsgap ergibt sich durch Normierung dieses Wertes mit der unteren Schranke, in diesem Fall also als 1, 8/1 = 1, 8 = 180% Er besagt, dass der Optimalwert des ganzzahligen Programms um höchstens 180% höher liegt als der Wert der Lösung (1;1). Dies erlaubt eine (in diesem Fall nicht besonders gute) Qualitätsabschätzung der Lösung. Der tatsächliche Unterschied beträgt (2-1)/1 = 1 = 100%, d. h. der Optimalwert ist doppelt so hoch wie der Wert der gefundenen Lösung. Im Laufe des Algorithmus wird die Relaxierung schrittweise verschärft (beispielsweise durch Hinzufügen zusätzlicher Ungleichungen), so dass die sich daraus ergebende obere Schranke immer kleiner wird. Gleichzeitig wird versucht, bessere zulässige Lösungen zu finden, um die untere Schranke anzuheben. Dies ist in der nebenstehenden Abbildung illustriert. Sind der Wert einer gefundenen Lösung und die duale Schranke gleich (im Beispiel beim Wert 2), ist dies der Beweis, dass die gefundene Lösung optimal ist. Im folgenden werden einige wichtige exakte und heuristische Lösungsverfahren etwas genauer vorgestellt.
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 |
| ||||||||||||||||||||||||||||||||
Load: 16; Render: 0; Total: 16