Zum Inhalt
Anmelden
Alle Apps

Ganzzahlig ist anders: LP gegen IP

Über diese App

Warum ganzzahlige Programme nicht durch Runden der LP-Lösung entstehen: links das Gebiet mit Gitterpunkten, LP-Optimum an der Ecke und ganzzahligem Optimum weit davon, gerundete Nachbarn unzulässig oder schlecht, ganzzahlige Hülle mit der Fläche, die Schnittebenen wegschneiden. Rechts der Optimalwert über der rechten Seite b: Die LP-Gerade steigt mit dem Schattenpreis, das IP springt als Treppe. Fünf Schritte, drei Folienbeispiele, Maßstab ×1 bis ×10.

Mit Erklärmodus: Ein KI-Tutor führt dich durch die App, zeigt in der Szene, worauf es ankommt, und beantwortet deine Fragen.

Worum es geht

Ein lineares Programm hat ein konvexes Vieleck als zulässiges Gebiet; ein Optimum liegt an einer Ecke, und der Simplex sucht nur Ecken ab. Müssen die Variablen ganzzahlig sein, bleiben nur die Gitterpunkte im Gebiet. Das ganzzahlige Optimum ist dann im Allgemeinen keine Ecke und liegt nicht unbedingt neben dem LP-Optimum. Runden der LP-Lösung kann unzulässig sein oder weit vom Optimum landen. Der Wert der LP-Relaxation ist nur eine Schranke, und Schattenpreise gibt es im ganzzahligen Fall nicht.

Was die App zeigt

Links das Gebiet eines Problems mit zwei Variablen: die LP-Relaxation als Fläche, die Gitterpunkte, das LP-Optimum als Stern und das ganzzahlige Optimum als Kreis, dazu die Isolinie der Zielfunktion. Fünf Schritte führen von der reellen Lösung über das Gitter und die gerundeten Nachbarpunkte zur ganzzahligen Hülle, deren Ecken ganzzahlig sind; die Fläche zwischen Relaxation und Hülle ist schraffiert. Rechts steht der Optimalwert über der rechten Seite einer Nebenbedingung: beim LP eine Gerade mit dem Schattenpreis als Steigung, beim IP eine Treppe. Alle Werte werden exakt in Brüchen gerechnet.

Selbst ausprobieren

Im Grundbeispiel liegt das LP-Optimum bei (9/4, 15/4) mit F = 41¼, das ganzzahlige bei (0, 5) mit F = 40; gerundet erreicht man höchstens 39. Zieh an der rechten Seite b: Das LP-Optimum gleitet, das ganzzahlige springt von (2, 3) über (4, 2), (1, 4) und (3, 3) nach (0, 5). Die beiden Rundungsfallen der Folien sind als eigene Beispiele dabei. Mit dem Maßstab ×10 schrumpft die Lücke von 3,1 % auf 0,4 %, der Zielpfeil lässt sich drehen.

Häufige Fragen

Warum kann man die LP-Lösung nicht einfach runden?
Die gerundete Lösung kann gegen Nebenbedingungen verstoßen: Liegt das LP-Optimum bei (3/2, 2) an einer Spitze des Gebiets, sind (1, 2) und (2, 2) beide unzulässig. Ist sie zulässig, kann sie deutlich schlechter sein als das Optimum, etwa 7 statt 10, weil das ganzzahlige Optimum an einer ganz anderen Stelle liegt.
Was ist die LP-Relaxation eines ganzzahligen Programms?
Dasselbe Problem ohne Ganzzahligkeitsbedingung. Jede ganzzahlige Lösung ist auch für die Relaxation zulässig, deshalb ist ihr Optimalwert bei einer Maximierung eine obere Schranke. Ist die Lösung der Relaxation zufällig ganzzahlig, ist sie auch für das ganzzahlige Problem optimal.
Warum gibt es bei ganzzahligen Programmen keine Schattenpreise?
Der Optimalwert ändert sich mit einer rechten Seite nicht stetig, sondern springt: Eine zusätzliche Einheit bringt mal nichts, mal einen großen Zuwachs. Es gibt also keine feste Steigung, die man als Preis einer Ressource lesen könnte. Was-wäre-wenn-Fragen beantwortet man, indem man das Problem neu löst.
Was zeigt die ganzzahlige Hülle in der App?
Das kleinste konvexe Vieleck um alle zulässigen Gitterpunkte. Ein LP über dieser Hülle hätte das ganzzahlige Optimum als Ecke. Die schraffierte Fläche zwischen Relaxation und Hülle enthält keinen Gitterpunkt; Schnittebenen in Branch and Cut schneiden sie weg.

Fach: Lineare Probleme

Mehr aus Lineare Probleme

Eine VisuApp von heyprof: interaktiv, kostenlos im Browser, ohne Anmeldung. Was ist eine VisuApp? · Alle Apps