Entscheidungsbaum für das Maximierungsproblem

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

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

$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

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

Der erste Ast Nr.1 wird nun wie folgt berechnet. Es wird dort die Variable $x_{1,max} = 1$ gesetzt. Außerdem geht die andere Variable $x_{2,max} = 3$ für die Berechnung der Zielfunktion mit ein:

$z = 2 \cdot 1 + 3 = 5$.

Das bedeutet einfach, dass dieser Ast und die weiteren Verzweigungen einen maximalen Zielfunktionswert von $z = 5$ erreichen können. Dies ist der Fall, wenn beide Kapazitäten bis zu ihrem Maximum produziert werden. Es werden dann die unteren Restriktionsschranken eingefügt, indem $x_1 = 1$ gesetzt wird und $x_2 = 0$. Damit wird geprüft, ob überhaupt genügend Kapazitäten verfügbar sind, wenn nur $x_1$ mit dem maximalen Wert produziert würde. Wenn hier bereits eine Kapazitätsüberschreitung erfolgt, dann wird der Ast nicht weiter verzweigt, weil die Kapazitäten nicht ausreichen würden, wenn $x_1$ in dieser Höhe produziert würde. Es müsste dann der 2. Ast in der obersten Ebene betrachtet werden, indem $x_1$ um eine Einheit reduziert wird. Da nun aber die Kapazitäten ausreichen, wird der Ast also verzweigt.

Es wird nun also nach unten verzweigt und geprüft, welchen Wert $x_2$ annehmen darf, damit die Kapazitäten nicht überschritten werden und der Zielfunktionswert maximiert wird. In der ersten Verzweigung (Nr. 2) wird $x_2$ gleich seiner oberen Schranke gesetzt, also $x_2 = 3$. Der Zielfunktionswert wird berechnet und die Restriktionen. Es wid deutlich, dass die Kapazitäten überschritten werden, demnach ist es nicht möglich 3 Einheiten von $x_2$ zu produzieren, wenn 1 Einheit von $x_1$ produziert wird. Also wird die nächste Verzweigung durchgeführt (Nr. 3) und $x_2$ eine Einheit nach unten gesetzt: $x_2 = 2$. Auch hier wird die Kapazität überschritten. Es ist also nicht möglich 2 Einheiten von $x_2$ zu produzieren, wenn 1 Einheit von $x_1$ produziert wird. Die nächste Verzweigung Nr. 4 ergibt dann für $x_2 = 1$ keine Überschreitung der Restriktionen. Es ist also möglich 1 Einheit von $x_1$ und 1 Einheit von $x_2$ zu produzieren. Der Zielfunktionswert liegt in diesem Fall bei $z = 3$.

Die Verzweigung wird für diesen Ast hier beendet, da eine weitere Reduktion von $x_2$ zu einem geringeren Zielfunktionswert führen würde. 

Es wird wieder die oberste Ebene betrachtet und ein zweiter Ast Nr. 5 eingefügt. Hier wird nun $x_1$ um eine Einheit reduziert, also auf $x_1 = 0$. Der maximal mögliche Zielfunktionswert wird dann mit dem oberen Schranke von $x_2$ gebildet und mit $x_1 = 0$.

$z = 2 \cdot 0 + 3 = 3$.

Das bedeutet einfach, dass dieser Ast und die weiteren Verzweigungen einen maximalen Zielfunktionswert von $z = 3$ erreichen können. Es ist deutlich zu erkennen, dass der berechnete Zielfunktionswert den gleichen Zielfunktionswert aufweist, wie mit der Verzweigung Nr. 4. Deswegen wird auch dieser Ast verfolgt (wäre der Zielfunktionswert kleiner, würde dieser Ast nicht weiter betrachtet werden).

Die unteren Restriktionsschranken werden dann berechnet, indem für $x_1 = 0$ geprüft wird, ob dieses Produkt bei Null Einheit die Kapazitäten übersteigt, wenn nur dieses Produkt betrachtet wird und $x_2$ nicht produziert würde ($x_2 = 0$). Da dann keine Einheiten produziert würden, sind die Kapazitäten natürlich unausgeschöpft. Es wird nun die 1. Verzweigung (Nr. 6) vorgenommen, wobei $x_1 = 0$ wieder konstant gehalten wird und $x_2$ mit der obersten Schranke berücksichtigt wird: $x_2 = 3$.  Die Kapazitäten werden nicht überschritten und der Zielfunktionswert liegt bei $z = 3$. Demnach wäre auch diese Kombination denkbar, da der selbe Zielfunktionswert wie bei Nr. 4 erreicht wird. Es ist also möglich 0 Einheit von $x_1$ und 3 Einheit von $x_1$ zu produzieren. Der Zielfunktionswert liegt in diesem Fall bei $z = 3$.