Entscheidungsbaum für das Minimierungsproblem

Nachdem die Vorüberlegungen getroffen worden sind, wird als nächstes der Entscheidungsbaum aufgestellt. Dabei wird die obere Ebene mit der Variable $x_2$ belegt. Das bedeutet, dass die Variable $x_2$ nur in der 1. Ebene variiert wird. Für die untere Ebene wird $x_2$ konstant gehalten und nur $x_1$ variiert. 

Die Aufstellung des Entscheidungsbaums erfolgt für das folgenden im vorherigen Abschnitt aufgeführte ganzzahlige Minimierungsproblem:

$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  \ge -1$

$x_1, x_2 \ge 0$    und ganzzahlig

In der folgenden Grafik ist der gesamte Entscheidungsbaum aufgeführt:

Der Zielfunktionswert der obersten Ebene wird immer mit dem angegebenen $x_2$ und mit dem maximalen $x_{1,max} = 5$ bestimmt. Die Zielfunktion in den Verzweigungen wird immer mit den angegebenen Variablenwerten berechnet. Es ist deutlich zu erkennen, dass hier nur eine Lösung existiert und zwar die Verzweigung Nr. 3. Mit dieser wird der Zielfunktionswert von

$z = 2 \cdot 1 + 2 = 4$

erzielt. Die Variablen nehmen die ganzzahligen Werte $x_1 = 1$ und $x_2 = 2$ an. Alle weiteren Verzweigungen sind unzulässig, da die Restriktionen unterschritten werden. Der letzte Ast Nr. 7 wird gar nicht weiter verfolgt, denn dort wird $x_2 = 0$ betrachtet und in diesem Ast wurden die Restriktionen mit dem maximalen $x_{1,max} = 5$ berechnet. Da hier die Nebenbedingungen bereits nicht erfüllt werden (Restriktion 2 wird unterschritten) muss der Ast nicht weiter verzweigt werden, da $x_1$ nicht überschritten werden darf (maximal 5 Einheiten) und jede Menge von $x_1$ weniger zu noch geringerer Kapazität führt.