Produktion & Logistik

Branch and Bound II

Im ersten Teil des Beitrags haben wir dir bereits gezeigt, wie man ein kombinatorisches ganzzahliges Problem lösen kann. In diesem Beitrag betrachten wir ein binäres kombinatorisches ganzzahliges Problem.

Inhaltsübersicht

Branch and Bound – Beispielrechnung

Stell dir vor, du willst deinen Koffer für den Urlaub packen und hast eine Auswahl an Sachen, die du gerne mitnehmen möchtest. Jeder Gegenstand hat ein bestimmtes Gewicht und einen bestimmten Nutzen für dich. Dein Koffer darf für den Flug aber nicht schwerer als 15 Kilogramm sein. Jetzt willst du den Koffer optimal packen und dabei das maximal zulässige Gewicht einhalten. Da du ja nur ganze Gegenstände und nicht nur einen Bruchteil mitnehmen kannst, musst du entscheiden, ob du den Gegenstand einpackst oder zu Hause lässt

Erklärung der Voraussetzungen

Das Problem sieht also folgendermaßen aus: Du siehst in der Zielfunktion deine Gegenstände x_j gleich 1 bis 3, die du einpacken kannst, multipliziert mit ihrem jeweiligen Nutzen für dich. Du hast zwei Nebenbedingungen. Die erste zeigt die Gewichte der jeweiligen Gegenstände in Kilogramm und soll zusammenaddiert weniger oder gleich 15 Kilogramm wiegen. Die zweite Nebenbedingung sagt, dass jeder Gegenstand x_j nur Element der Zahlen 0 oder 1 sein kann, also eine binäre Variable ist. Null steht dafür, dass der Gegenstand nicht eingepackt wird und 1, dass er eingepackt wird. Um gleich im Branch and Bound Verfahren bestimmen zu können, nach welcher Variable verzweigt werden soll, musst du eine Priorität der Sachen festlegen. Diese bestimmt sich durch den relativen Nutzen. Dieser setzt sich zusammen aus dem Nutzen des jeweiligen Gegenstandes geteilt durch sein Gewicht. Die Prioritäten sehen damit so aus:

relative Nutzen der Gegenstände
direkt ins Video springen
Relative Nutzen der Gegenstände

Branch and Bound Methode durchführen

Jetzt können wir das Branch and Bound Verfahren starten. Unsere untere Schranke ist 0. Unsere obere Schranke ist die nach Priorität hinzugefügten Gegenstände bis der Koffer voll ist. x_1 ist damit 1 und wir haben schon 4kg in unserem Koffer. Die zweithöchste Priorität hat Gegenstand x_2 und wiegt 5 kg. Zusammen mit x_1 sind das schon 9 kg. Als nächstes ist x_3 dran, der 10 kg wiegt. Das passt jetzt aber nicht mehr komplett in unseren Koffer, da wir dann bei 19 kg wären. Deshalb nehmen wir von x_3 nur 6/10 in x auf und haben damit genau 15 kg erreicht.  Unsere Zielfunktion ist dann: 8+6+6/10*10=20. Wir haben damit unsere obere Schranke ermittelt.

Obere Schranke ermitteln
direkt ins Video springen
Obere Schranke ermitteln

Verzweigen nach der MUB-Regel

Diesmal verzweigen wir nach der Maximum Upper Bound- oder auch MUB-Regel. Das bedeutet: Anders als bei der LIFO-Regel berechnen wir direkt die Schranken aller Teilprobleme. Ausgehend von P_0 verzweigen wir jetzt nach abfallender Priorität – also zuerst x_1. Links verzweigen wir nach x_1 gleich 1 und benennen das Teilproblem P_1 und rechts nach x_1 gleich 0 und nennen es P_2. Wir starten mit P_1 und berechnen x. Dadurch, dass x in P_0 bereits 1 ist, ändert sich an x sowie an der Zielfunktion nichts.

Verzweigen nach der MUB-Regel
direkt ins Video springen
Verzweigen nach der MUB-Regel

Da wir die MUB-Regel verwenden, teilen wir P_1 jetzt nicht auf, sondern berechnen erst P_2. Hier soll x_1 gleich 0 sein. Demnach nehmen wir x_2 und x_3 auf und kommen auf genau 15 kg. Das ist unsere erste zulässige Lösung. Wir berechnen unsere Nutzenzielfunktion und kommen auf einen Nutzen von 16. Das ist jetzt unsere untere Schranke. Unser Nutzen darf also nicht weniger als 16 in den folgenden Teilproblemen betragen. Jetzt verzweigen wir P_1 weiter und zwar nach dem Gegenstand mit der nächsten Priorität nach x_1 – also x_2. Für p_3 gilt x_2 gleich 1. Dabei verändert sich an den Gegenständen, die wir einpacken, und an der Zielfunktion wieder nichts.

Für P_4 ist das allerdings anders. x_2 ist hier 0 und es gilt die Bedingung von vorher, dass x_1 gleich 1 ist. Dadurch erhalten wir diese Kombination:

Verzweigung fortführen
direkt ins Video springen
Verzweigung fortführen

Ergebnisfindung:

Der Zielfunktionswert ist 18. Nach der MUB-Regel machen wir jetzt mit dem Teilproblem weiter, das die höhere obere Schranke hat, also P_5. P_5 erhält x_3 gleich 1 und ist damit unzulässig, da die 15 Kilogramm bei dieser Option überschritten werden. Für P_6 muss x_3 gleich 0, x_2 gleich 1 und x1 gleich 1 sein und wir erhalten einen Zielfunktionswert von 14.

Ergebnisfindung
direkt ins Video springen
Ergebnisfindung

Wir müssten an dieser Stelle noch weiter verzweigen. Da der Zielfunktionswert aber schon niedriger ist als unsere höchste obere Schranke, können wir an dieser Stelle abbrechen. Unser maximaler Nutzen ist demnach 18. Für dich ist es also am besten, wenn du die Uhr und deine Schuhe einpackst.

Ergebnisfindung
direkt ins Video springen
Ergebnisfindung

Du siehst: Es kommt immer ganz auf das Beispiel an, ob man eher die LIFO- oder die MUB-Regel verwenden sollte.

Hallo, leider nutzt du einen AdBlocker.

Auf Studyflix bieten wir dir kostenlos hochwertige Bildung an. Dies können wir nur durch die Unterstützung unserer Werbepartner tun.

Schalte bitte deinen Adblocker für Studyflix aus oder füge uns zu deinen Ausnahmen hinzu. Das tut dir nicht weh und hilft uns weiter.

Danke!
Dein Studyflix-Team

Wenn du nicht weißt, wie du deinen Adblocker deaktivierst oder Studyflix zu den Ausnahmen hinzufügst, findest du hier eine kurze Anleitung. Bitte lade anschließend die Seite neu.