Beispiel: Branch and Bound am Maximierungsproblem (optimale Lösung)

Das Branch-and-Bound-Verfahren am angepassten Problem soll in diesem Abschnitt anhand des Maximierungsproblems aus dem Abschnitt: Ganzzahlige lineare Optimierung veranschaulicht werden.

Gegeben sei das folgenden Ausgangsproblem $P_0$:

$f(x_1, x_2) = 2x_1 +  x_2$    $\rightarrow$   max!

u.d.N.

(1) $3x_1 + 2x_2 \le 6 $   

(2) $5x_1 + 2 x_2 \le 8$    

$x_1, x_2 \ge 0$    und ganzzahlig

Untere Schranke

Die untere globale Schranke liegt in diesem Fall (aufgrund der Nichtnegativitätsbedingung) bei $x_1 = x_2 = 0$ und damit bei einem Zielfunktionswert von $\underline{F} = 0$. Dies stellt damit auch gleichzeitig die untere globale Schranke des Ausgangsproblems $P_0$ dar (die Zielfunktion kann aufgrund der Nichtnegativitätsbedingung nicht negativ werden).

Obere Schranke

Für das obige angegebene ganzzahlige lineare Optimierungsproblem wird nun zunächst die Ganzzahligkeitsbedingung aufgehoben und das Maximierungsproblem mittels primalen Simplex-Algorithmus oder grafisch gelöst. Das Maximierungsproblem ohne Ganzzahligkeitsbedingung wird dabei mit $P'_0$ bezeichnet, das Ausgangsproblem mit $P_0$. Die grafische Lösung erfolgte bereits im Abschnitt Ganzzahlige lineare Optimierung und ergab eine optimale Lösung für das Problem $P'_0$  (Ganzzahligkeitsbedingung nicht gegeben) von $(x_1, x_2) = (1, 1,5)$. Diese ermittelte optimale Lösung ist nicht ganzzahlig, deswegen für das obige Ausgangsproblem $P_0$ auch nicht zulässig. Der Zielfunktionswert dieser nichtganzzahligen Lösung beträgt $f(x_1, x_2) = 3,5$ und stellt die obere Schranke für das Branch-and-Bound-Verfahren dar. 

Die obere Schranken des Ausgangsproblems $P_0$ ist: $\overline{F}_0 = 3,5$. 

Diese obere Schranken resultierte für nichtganzzahlige Variablen und ist deshalb so nicht zulässig. Das Problem muss demnach verzweigt werden. Die Entscheidung mit welcher Variable begonnen wird in diesem Fall für $x_2$ getroffen, diese einen größeren Wert aufweist.

Verzweigung

Es wird nun das Problem $P_0$ verzweigt in die Teilprobleme $P_1$ und $P_2$. Dabei wird die obere Schranke des angepassten Problems $P'_0$ gewählt. Die untere Schranke ist dabei zunächst $\underline{F} = 0$. Dabei wird die Entscheidungsvariable $x_2$ betrachtet, da diese den größten Wert aufweist. Dabei liegt $x_2$ zwischen den ganzen Zahlen $1$ und $2$. Es werden also die Bedingungen $x_2 \le 1$ für das Problem $P_1$ hinzugefügt und $x_2 \ge 2$ für das Problem $P_2$. Für beide Probleme muss nun wieder die optimale Lösung mittels Simplexalgorithmus oder grafisch erfolgen, indem die angepassten Probleme $P'_1$ und $P'_2$ gelöst werden (Vernachlässigung der Ganzzahligkeitsbedingung). Es soll hier die grafische Vorgehensweise gewählt werden, da der Simplexalgorithmus zeitaufwendiger ist. Die optimale Lösung für die zusätzliche Bedingung von $P'_1$ ergibt sich wie folgt:

Es ist die Restriktion $x_2 \le 1$ hinzugefügt worden (schwarze Linie). Die optimale Lösung erhält man dann durch Verschiebung der Zielfunktionsgeraden parallel zu sich selbst bis sich diese gerade noch im zulässigen Bereich befindet. Die zulässige Lösung ergibt sich hier beim Punkt $(1,2 / 1)$. Einsetzen die die Zielfunktion:

$f(1,2/1) = 2 \cdot 1,2 +  1 = 3,4$ 

Für das Problem $P_1$ gilt die neue obere Schranke $\overline{F}_1 = 3,4$. Es handelt sich hierbei um keine zulässige Lösung für das Ausgangsproblem, da keine ganzzahlige Lösung vorliegt. 

Für das Problem $P'_2$ wird die Nebenbedingung $x_2 \ge 2$ hinzugefügt:

Die neue Nebenbedingung $x_2 \ge 2$ ist hinzugefügt worden. Hier muss beachtet werden, dass nur der Bereich oberhalb von $x_2 = 2$ betrachtet werden darf, aber unterhalb der beiden Nebenbedingungen (1) und (2) des Ausgangsproblems, da diese $\le$-Bedingungen darstellen. Der zulässige Bereich ist durch die schwarzen dicken Linien gekennzeichnet. Die Zielfunktion wird nun innerhalb dieses Bereiches (parallel zu sich selbst) verschoben, bis diese gerade noch in diesem Bereich liegt. Der Punkt $(0,67 /2)$ stellt die optimale Lösung dar. Einsetzen in die Zielfunktion ergibt:

$f(0,67/2) = 2 \cdot 0,67 + 2 = 3,34$ 

Für das Problem $P_2$ gilt die neue obere Schranke $\overline{F}_2 = 3,34$. Es handelt sich hierbei um keine zulässige Lösung für das Ausgangsproblem, da keine ganzzahlige Lösung vorliegt. 

Es wird nun das Problem $P_1$ weiter verzweigt, weil dieses einen höheren Zielfunktionswert aufweist.

Bei der weiteren Verzweigung wird als nächstes die Variable $x_1$ betrachtet. Diese liegt zwischen den ganzen Zahlen $1$ und $2$. Es wird demnach für $P_3$ die Bedingung $x_1 \le 1$ und für $P_4$ die Bedingung $x_1 \ge 2$ hinzugefügt.

Es wird nun wieder das angepasste Problem $P'_3$ gelöst mit zusätzlicher Berücksichtigung der Bedingung $x_1 \le 1$ und das Problem $P'_4$ mit $x_1 \ge 2$. Hier wird wieder die Grafik verwendet:

In der obigen Grafik sind nun die beiden Teilprobleme veranschaulicht. Zur Bestimmung der oberen Schranke für $P_3$ wurde als zusätzliche Restriktion $x_1 \le 1$ eingefügt. Die Restriktion $x_2 \le 1$ für $P_1$ musste dabei erhalten bleiben. Es ergibt sich also der rechteckige zulässige Bereich in welchem die Zielfunktionsgerade verschoben werden muss, bis diese den Bereich gerade noch berührt. Der optimale Punkt liegt bei $(1/1)$. Damit ergibt sich die erste ganzzahlige Lösung, die oberhalb der untersten Schranke $\underline{F} = 0$ liegt. Es handelt sich hierbei um den Fall b, denn $\overline{F}_3 > \underline{F}$, wobei die gegebene Lösung ganzzahlig und zulässig ist (innerhalb des zulässigen Bereiches liegt). Einsetzen der Werte $x_1 = 1$ und $x_2 = 1$ in die Zielfunktion ergibt die neue untere Schranke:

Zur Bestimmung der oberen Schranke für $P_4$ wurde als zusätzliche Restriktion $x_1 \ge 2$ eingefügt. Die Restriktion $x_2 \le 1$ für $P_1$ musste dabei erhalten bleiben. Da es sich hierbei um eine größer-gleich-Bedingung handelt, die Variable $x_1$ also größer als $2$ werden muss ist das Problem nicht lösbar, da der Punkt dann nicht mehr im zulässigen Bereich liegt, sondern außerhalb. Es ist der Fall c gegeben. 

Die Verzweigung am linken Ast ist nun abgeschlossen. Es wird nun der rechte Ast $P_2$ betrachtet und dieser verzweigt. Dabei gilt für $P_5$ die Bedingung $x_1 \le 0$ und für $P_6$ die Bedingung $x_1 \ge 1$. Die optimale Lösung für die angepassten Probleme ergibt sich wie folgt:

In der obigen Grafik sind nun die beiden Teilprobleme veranschaulicht. Zur Bestimmung der oberen Schranke für $P_5$ wurde als zusätzliche Restriktion $x_1 \le 0$ eingefügt. Die Restriktion $x_2 \ge 2$ für $P_2$ musste dabei erhalten bleiben. Es ergibt sich also der Bereich auf der $y$-Achse ($x_1 = 0$) und oberhalb von $x_2 = 2$, aber unterhalb der grünen Restriktion. Es ergibt sich demnach der Punkt $(0/3)$, welcher gerade noch im zulässigen Bereich liegt. Damit ergibt sich eine ganzzahlige Lösung, die oberhalb der untersten Schranke $\underline{F} = 0$ liegt. Es handelt sich hierbei allerdings um den Fall a, da die untere Schranke $\underline{F}_3 = 3$ bereits größer/gleich diesem Wert ist.

Zur Bestimmung der oberen Schranke für $P_6$ wurde als zusätzliche Restriktion $x_1 \ge 1$ eingefügt. Die Restriktion $x_2 \ge 2$ für $P_2$ musste dabei erhalten bleiben. Da es sich hierbei um eine größer-gleich-Bedingung handelt, die Variable $x_1$ also größer als $1$ und $x_2$ größer als $2$ werden muss ist das Problem nicht lösbar, da der Punkt dann nicht mehr im zulässigen Bereich liegt, sondern außerhalb. Es ist der Fall c gegeben. 

Die beste zulässige Lösung des ganzzahligen Maximierungsproblems ist bei $x_1 = 1$ und $x_2 = 1$ mit $F_3 = 3$ gegeben. Es ist deutlich zu erkennen, dass das Ergebnis dasselbe ist, wie mit dem Branch-and-Bound Verfahren ohne Bestimmung der optimalen Lösung. Der Rechenaufwand für dieses hier gezeigte Verfahren ist um einiges höher, weshalb sich das Branch-and-Bound Verfahren ohne vorherige Ermittlung der optimalen Lösung empfiehlt.