Operations Research

Branch and Bound

Du möchtest dich über das Branch and Bound Verfahren informieren? Dann bist du hier genau richtig! Im folgenden Beitrag stellen wir dir das Branch and Bound Verfahren vor und erklären es dir anhand eines Beispiels.

Branch and Bound Verfahren: Erklärung und Beispiel

Bei der Branch and Bound Methode dreht sich alles um die ganzzahlige und kombinatorische Optimierung. Viele Probleme in der Realität sind oft nur ganzzahlig lösbar. Bei der Produktion eines Flugzeugs ist es beispielsweise nicht möglich, 4,2 Flugzeuge herzustellen, sondern nur ganze Anzahlen. Diese Bedingung war bei unseren linearen Problemen in den vorherigen Beiträgen nicht gegeben. Um solche Probleme zu lösen, verwendet man sogenannte Branch and Bound Verfahren.

Branch and Bound – ein Beispiel

Wir haben hier wieder ein Optimierungsproblem mit der zusätzlichen Restriktion, dass x_1 und x_2 ganzzahlig sein müssen. In dem Koordinatensystem haben wir dir die Nebenbedingungen eingetragen und die zulässige Menge markiert: Sie wird durch das Branch and Bound Verfahren immer weiter auf diese möglichen ganzzahligen Punkte beschränkt und stoppt, sobald es den Punkt gefunden hat, der das beste Ergebnis darstellt.

Optimierungsproblem
Optimierungsproblem

Branch and Bound: Erster Schritt

Als erstes musst du die optimale Lösung des Problems ermitteln, falls diese nicht schon vorgegeben ist. Normalerweise kannst du sie einfach durch einsetzen und auflösen der Variablen berechnen. In unserem Fall ist sie (2.14; 1.143). Wie du siehst, sind das keine ganzen Zahlen.  Eingesetzt in die Zielfunktion ergibt das 7,57. Das ist jetzt die obere Schranke deiner Zielfunktion. Das bedeutet: Die 7,57 ist vorübergehend unser optimales Ergebnis, bis wir unseren neuen Zielfunktionswert bestimmt haben.

vorübergehende optimale Lösung
vorübergehende optimale Lösung

Als nächstes definierst du deine untere Schranke. Wenn diese nicht bereits vorgegeben ist, fangen wir mit (0;0) an. Von hier verzweigen wir das Problem P_0 in zwei weitere Teilprobleme. Das nennt man branching. Im ersten Schritt subtrahierst du die optimale Lösung von der nächstgrößeren ganzen Zahl. Wir erhalten: 3- 2,14 = 0,86 und 2-1,143= 0,857.

Definition untere Schranke
Definition untere Schranke

Verzweigen nach der LIFO-Regel

Die Zahl mit der größeren Differenz gibt unsere erste Verzweigung an. Für die erste Variable x_1 gibt es nun zwei Möglichkeiten: Der rechte Ast beschreibt den Fall, dass x_1 größer gleich 3 ist und der linke Ast, dass x_1 kleiner gleich 2 ist. Das nennt man bounding. Wir machen zwei Kreise für beide Teilprobleme. Da wir das linke zuletzt gezeichnet haben, fangen mit dem linken Teilproblem an und schreiben in den Kreis P_1. Diese Verzweigungsregel ist die Last In First Out oder auch LIFO-Regel. Das bedeutet: Wir verzweigen immer nach dem Teilproblem als erstes, das wir als letztes hinzugefügt haben.

Zielfunktion erneut berechnen

Jetzt berechnest du die Zielfunktion erneut – allerdings mit dem neuen Wert von x_1 gleich 2. In unserem Koordinatensystem siehst du wie P_1 die zulässige Menge weiter beschränkt. Unser x_2 müssen wir jetzt an die neue Einschränkung anpassen. Du findest es über den Schnittpunkt von P_1 mit einer Nebenbedingung. Wichtig ist, dass dieser immer innerhalb der zulässigen Wertemenge liegt. In unserem Fall ist das der Schnittpunkt mit der blauen Nebenbedingung.

Schnittpunkt berechnen
Schnittpunkt berechnen

Gleichgesetzt und aufgelöst nach x_2 erhältst du damit 1,2. Setzt du das in die Zielfunktion F ein, ergibt das 7,2. Da x_2 noch nicht ganzzahlig ist, müssen wir weiter verzweigen.

Neue Verzweigung durchführen

Wir teilen P_1 wieder in zwei Teilprobleme auf und verzweigen nach x_2 größer gleich 2 und x_2 kleiner gleich 1.

Aufteilung in neue Teilprobleme
Aufteilung in neue Teilprobleme

Wir beginnen wieder links aufgrund der LIFO-Regel. Unser x ist jetzt (2;1), da beide Restriktionen der Teilprobleme P_0 und P_1 gelten. Der Zielfunktionswert für P_2 ist damit 7. Das ist jetzt auch gleichzeitig unsere neue untere Schranke, da P_2 eine zulässige Lösung mit ganzzahligen Variablen und kleiner als 7,57 ist. Das heißt: Schlechter als 7 darf unsere Zielfunktion in den anderen Teilproblemen nicht mehr werden.

neue Schranke festlegen
Neue Schranke festlegen

Rechtes Teilproblem lösen

Da wir für dieses Ergebnis eine zulässige Lösung gefunden haben, gehen wir zum rechten Teilproblem von P_1 weiter und benennen es P_3. Hier soll unser x_2 größer gleich 2 sein. Wenn du einen Blick auf das Koordinatensystem wirfst, siehst du sofort, dass das nicht möglich ist, da es durch unser P_1 außerhalb des zulässigen Bereichs liegt.

unzulässiger Bereich
Unzulässiger Bereich

Ergebnisfindung:

Damit können wir zur ersten Verzweigungsebene zurückkehren. Den offenen Zweig benennen wir mit der nächsten Zahl, also P_4. Für die Berechnung von x_2 setzen wir die rote Nebenbedingung wieder mit unserem Zweig, also der Restriktion x eins größer gleich 3, gleich und erhalten x_2 gleich null. Der Zielfunktionswert für P_4 ist damit 9. Du siehst bestimmt schon, dass wir hier nicht mehr weiter verzweigen können und die bestmögliche Lösung gefunden haben.

Bestmögliche Lösung
Bestmögliche Lösung

Oftmals findet man diese schon bei einem der früheren Teilproblemen und muss dann überprüfen, ob es noch bessere Lösungen gibt. Manchmal kommst du sogar durch Ausprobieren schneller auf die Lösung. Bei zunehmender Anzahl der Variablen steigen die möglichen Lösungen aber exponentiell und es ist dann nicht mehr so einfach zu lösen.

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.

Branch and Bound – ein Beispiel

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
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
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
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
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
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
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.