Prof. Dr. R. Laue                                                                            WS0001                                 Graphentheoretische Optimierung
                                Übungsblatt 11
                                Abgabe: 19.1 vor der Vorlesung

Aufgabe 21 Blocking Flow - (4 Punkte)

Man konstruiere ein Beispiel mit einem Blocking Flow, der nicht der maximale Fluss ist.

Aufgabe 22 Wir helfen der NASA - (5+3 Punkte)

(nach Ross)
Ein Raumschiff soll zu einem entfernten Planeten aufbrechen. Der Flightmanager muss entscheiden welche der m möglichen Ausrüstungsgegenstände A_i an Bord genommen werden soll. Jeder Ausrüstungsgegenstand verursacht Kosten c_i (natürlich >0). Mit den Ausrüstungsgegenständen kann man aber Experimente E_j durchführen. Jedes Experiment der insgesamt m möglichen bringt einen Gewinn von g_j (wieder >0). Für jedes Experiment ist eine Teilmenge der Menge aller Ausrüstungsgegenstände nötig. Der Flightmanager muss nun den Gesamtertrag der Mission maximieren, d.h. er muss Ausrüstungsgegenstände auswählen sodass die Summe über die Erträge der Experimente abzüglich der Summe über die Kosten der Ausrüstungsgegenstände maximal wird.

Wie kann hier max flow / min cut helfen?

Lösen Sie folgendes Problem:
Es gibt 5 Ausrüstungsgegenstände zu Kosten (c₁= 4,c₂=5,c₃=7,c₄=1,c₅=2) .
Experiment 1 bringt 3 Einheiten Gewinn und benötigt Ausrüstungsgegenstände 1 und 2.
Experiment 2 bringt 10 Einheiten Gewinn und benötigt Ausrüstungsgegenstände 3 und 2.
Experiment 3 bringt 6 Einheiten Gewinn und benötigt Ausrüstungsgegenstände 3, 4 und 2.
Experiment 4 bringt 8 Einheiten Gewinn und benötigt Ausrüstungsgegenstände 4 und 5.
Welche Ausrüstungsgegenstände soll der Flightmanager an Bord nehmen?