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

Nachdem im vorherigen Abschnitt das gegebene Minimierungsproblem zunächst unter Vernachlässigung der Ganzzahligkeitsbedingung mittels Simplexalgorithmus gelöst wurde, wird nun das Branch-and-Bound-Verfahren für das ganzzahlige Optimierungsproblem angewandt. Nach Anwendung des Simplexalgorithmus auf das angepasste Problem $P'_0$ resultierte die folgende optimale Lösung:

$x_1 = 0,67$ und $x_2 = 1,83$ mit dem Zielfunktionswert:

$F = 3,167$.

Die untere Schranke für das Problem $P_0$ ist dabei die optimale Lösung des angepassten Problems $P'_0$:

$\underline{F}_0 = 3,167$

Diese untere Schranke 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, da diese einen größeren Wert aufweist.

Für die Teilprobleme $P_1$ und $P_2$ muss nun wieder für das angepasste Problem $P'_1$ und $P'_2$ (Vernachlässigung der Ganzzahligkeitsbedingung) die optimale Lösung bestimmt werden. Für $P'_1$ muss dabei das Ausgangsproblem betrachtet werden und die Nebenbedingung $x_2 \le 1$ hinzugefügt werden. Für das angepasste Teilrpoblem $P'_2$ wird die Nebenbedingung $x_2 \ge 2$ mit berücksichtigt. 

Verzweigung 1

Für das angepasste Teilproblem $P'_1$ gilt (Standardform):

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

u.d.N.

(1) $-4x_1 - 4 x_2 \le -10 $   

(2) $-2x_1 - 11 x_2 \le -11$    

(3) $-4x_1 + 2x_2  \le 1$

(4) $x_2 \le 1$

$x_1, x_2 \ge 0$

Umformen in die Normalform:

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

u.d.N.

(1) $-4x_1 - 4 x_2  + y_1                            = -10 $   

(2) $-2x_1 - 11 x_2          + y_2                  =  -11$    

(3) $-4x_1 + 2x_2                     + y_3         = 1$

(4) $x_2                                          + y_4 = 1$

$x_1, x_2, y_1, y_2, y_3, y_4 \ge 0$

Es wird nun wieder der duale Simplexalgorithmus angewandt um eine zulässige Lösung zu erhalten und danach der primale Simplexalgorithmus für eine optimale Lösung:

Das duale Simplexverfahren endet hier, da alle Werte auf der rechten Seite positiv sind. Es liegt also eine zulässige Lösung vor, die auch die optimale Lösung darstellt, da die Werte in der Zielfunktionszeile positiv sind. Die optimale Lösung für das angepasste Teilproblem ergibt sich demnach zu:

$x_1 = 3/2$ und $x_2 = 1$ mit dem Zielfunktionswert:

$\underline{F}_1 = 4$.

(Einsetzen der optimalen Lösung in die Zielfunktion des Minimierungsproblems).

Der ermittelte Zielfunktionswert stellt gleichzeitig die untere Schranke des Teilproblems $P_1$ dar. Die optimale Lösung ist nicht ganzzahlig ($x_1 = 3/2$) damit liegt keine zulässige Lösung für das Ausgangsproblem $P_0$ vor. Das Problem muss in jedem Fall noch verzweigt werden, allerdings muss erst die untere Schranke für das Teilproblem $P_2$ bestimmt werden, um herauszufinden, ob eventuell $P_2$ als erstes verzweigt werden muss (oder nicht verzweigt wird). 

Verzweigung 2

Für das Teilproblem $P'_2$ gilt (Standardform):

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

u.d.N.

(1) $-4x_1 - 4 x_2 \le -10 $   

(2) $-2x_1 - 11 x_2 \le -11$    

(3) $-4x_1 + 2x_2  \le 1$

(4) $x_2 \le -2$

$x_1, x_2 \ge 0$

Umformen in die Normalform:

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

u.d.N.

(1) $-4x_1 - 4 x_2  + y_1                            = -10 $   

(2) $-2x_1 - 11 x_2          + y_2                  =  -11$    

(3) $-4x_1 + 2x_2                     + y_3         = 1$

(4) $x_2                                          + y_4 = -2$

$x_1, x_2, y_1, y_2, y_3, y_4 \ge 0$

Es kann nun wieder der duale Simplexalgorithmus angewandt um eine zulässige Lösung zu erhalten und danach der primale Simplexalgorithmus für eine optimale Lösung.