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

Gegeben sei das folgende Ausgangsproblem $P_0$:

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

u.d.N.

(1) $4x_1 +4 x_2 \ge 10 $   

(2) $2x_1 +11 x_2 \ge 11$    

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

$x_1, x_2 \ge 0$    und ganzzahlig

Obere Schranke

Die obere globale Schranke liegt in diesem Fall bei einem Zielfunktionswert von $\underline{F} = \infty$. Der Zielfunktionswert soll zwar minimiert werden, aber eine genaue obere Schranke kann nicht gegebenen werden. 

Untere Schranke

Die untere Schranke ist der optimale Zielfunktionswert des angepassten Problems. Das bedeutet also, dass das obige ganzzahlige Problem zunächst mittels Simplexalgorithmus (oder grafisch) gelöst wird, indem die Ganzzahligkeitsbedingung aufgehoben wird. Es soll im folgenden gezeigt werden, wie man die optimale Lösung mittels Simplexalgorithmus erhält. Hierzu benötigt man die 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$

$x_1, x_2 \ge 0$

Nachdem nun die Standardform gegeben ist wird das Problem in die Normalform überführt (Einfügen von Schlupfvariablen):

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

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

Da die Werte der rechten Seite negative Werte aufweisen, muss hier also zunächst der duale Simplexalgorithmus angewandt werden um eine zulässige Lösung zu erhalten. Es müssen insgesamt 3 Simplexschritte mittels dualen Simplex durchgeführt werden, bis eine zulässige Ausgangslösung resultiert:

Da alle Werte der rechten Seite positiv sind, liegt eine zulässige Ausgangslösung vor. Der primale Simplexalgorithmus muss hier nicht angewandt werden, da bereits alle Werte in der Zielfunktionszeile positiv sind. Es liegt also gleichzeitig auch die optimale Lösung vor.

Die optimale Lösung des angepassten Problems $P'_0$ (ohne ganzzahligkeitsbedingung) beträgt:

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

$F = 19/6$.

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 stellt die untere Schranke für das Branch-and-Bound-Verfahren dar.

Die weitere Vorgehensweise erfolgt im nächsten Abschnitt.