Warum ist ganzzahlig schwerer?
Eine ganzzahlige Optimierung verlangt, dass jede Variable eine ganze Zahl ist. Ein Lieferwagen nimmt ein Paket ganz mit oder gar nicht, nie zu vier Fünfteln.
Das macht das Problem viel schwerer als ein gewöhnliches lineares Programm, und Runden der Lösung führt in die Irre. Sie sehen, warum, und lösen dann ein Rucksackproblem mit einer Tabelle.
Am Ende dieser Lektion
Notiz
Ich kann sagen, warum ganzzahlige Probleme schwerer sind als gewöhnliche lineare Programme.
Schlüsselwörter
| Begriff | Was er bedeutet |
|---|---|
| Ganzzahlige Optimierung | Optimieren, wenn die Variablen ganze Zahlen sein müssen |
| Rucksackproblem | aus Gegenständen mit Platzbedarf und Wert die besten für einen begrenzten Platz wählen |
| Relaxation | dasselbe Modell, aber mit erlaubten Bruchteilen |
| Teilmenge | eine Auswahl einiger Gegenstände |
| Dynamische Programmierung | ein großes Problem durch Tabellen kleiner Teilprobleme lösen |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Ein Rucksackproblem wählt unter begrenztem Platz
Ein Lieferwagen hat 10 Platz. Drei Pakete wollen mit. Paket A braucht 6 Platz und bringt 36 Euro. Die Pakete B und C brauchen je 5 Platz und bringen je 25 Euro.
Jedes Paket fährt ganz mit oder bleibt da. Das ist ein Rucksackproblem: gewählt wird die Teilmenge mit dem größten Wert, die noch hineinpasst.
Beispiel: drei Pakete für zehn Platz
| Paket | Platz | Wert in Euro | Wert je Platz |
|---|---|---|---|
| A | 6 | 36 | 6 |
| B | 5 | 25 | 5 |
| C | 5 | 25 | 5 |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Mit Bruchteilen wäre es ein gewöhnliches Programm
Erlaubt man Bruchteile, ist das Problem ein lineares Programm, die Relaxation. Der Lieferwagen nähme A ganz und vier Fünftel von B. Das sind 36 plus 20, also 56 Euro.
Die Relaxation liefert immer einen Wert, der mindestens so groß ist wie der beste ganzzahlige Plan.
Die Relaxation mit linprog lösen
docker exec jupyter python3 -c "from scipy.optimize import linprog; r = linprog([-36, -25, -25], A_ub=[[6, 5, 5]], b_ub=[10], bounds=(0, 1)); print(round(-r.fun, 1))"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Alle acht Teilmengen durchprobieren
docker exec jupyter python3 -c "import itertools; print(max(36*a + 25*b + 25*c for a, b, c in itertools.product([0, 1], repeat=3) if 6*a + 5*b + 5*c <= 10))"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Ein ganzzahliges Programm mit milp lösen
docker exec jupyter python3 -c "from scipy.optimize import milp, LinearConstraint, Bounds; r = milp([-36, -25, -25], constraints=LinearConstraint([[6, 5, 5]], ub=10), integrality=[1, 1, 1], bounds=Bounds(0, 1)); print(-r.fun)"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Runden der Lösung liefert nicht den besten Plan
Die Relaxation nimmt A ganz und vier Fünftel eines Pakets von 5 Platz. Rundet man ab, bleibt nur A mit 36 Euro. Rundet man auf, passt es nicht mehr, denn 6 plus 5 sind 11.
Der beste ganze Plan nimmt B und C, zusammen 50 Euro, und lässt das teure A zu Hause.
Ein häufiger Fehler
Warnung
Viele denken, man löse erst mit Bruchteilen und runde dann. Der gerundete Plan ist oft schlechter oder gar nicht zulässig. Die beste ganze Lösung kann ganz anders aussehen als die Lösung mit Bruchteilen.
Teilmengen wachsen mit 2 hoch n
Jedes Paket ist entweder dabei oder nicht. Bei n Paketen gibt es deshalb 2 mal 2 mal bis n Teilmengen, kurz 2 hoch n.
Mit 3 Paketen sind das 8, mit 30 Paketen schon über eine Milliarde. Durchprobieren wird schnell zu langsam.
Beispiel: Pakete und mögliche Teilmengen
| Pakete | Teilmengen |
|---|---|
| 3 | 8 |
| 10 | 1.024 |
| 20 | 1.048.576 |
| 30 | 1.073.741.824 |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Die Teilmengen von 30 Paketen zählen
docker exec jupyter python3 -c "print(2 ** 30)"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Eine Tabelle löst das Rucksackproblem ohne Probieren
Die dynamische Programmierung merkt sich für jeden Platz von 0 bis 10 den besten Wert. Dann nimmt sie ein Paket nach dem anderen dazu.
Für ein Paket mit Platz p und Wert w prüft sie jeden Platz k. Ist der Wert bei k minus p, plus w, besser als der alte Wert bei k, ersetzt sie ihn. Sie geht von hinten nach vorn, damit ein Paket nur einmal zählt.
Beispiel: die besten Werte nach jedem Paket
| Nach Paket | Platz 5 | Platz 6 | Platz 9 | Platz 10 |
|---|---|---|---|---|
| Start | 0 | 0 | 0 | 0 |
| A | 0 | 36 | 36 | 36 |
| B | 25 | 36 | 36 | 36 |
| C | 25 | 36 | 36 | 50 |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Die Tabelle in Python aufbauen
# Ein Transporter mit 8 Platz und drei Kisten.
gewichte = [3, 4, 5]
werte = [40, 50, 70]
kapazitaet = 8
beste = []
for k in range(kapazitaet + 1):
beste.append(0)
for kiste in range(len(gewichte)):
# Von hinten nach vorn, damit jede Kiste nur einmal zählt.
for k in range(kapazitaet, gewichte[kiste] - 1, -1):
mit = beste[k - gewichte[kiste]] + werte[kiste]
if mit > beste[k]:
beste[k] = mit
print("Nach Kiste", kiste + 1, ":", beste)
print("Bester Wert:", beste[kapazitaet])
# Ändern Sie kapazitaet in 12 und starten Sie erneut.
# Welche Kisten passen jetzt alle hinein?