ZU DEN KURSEN!

Operations Research 2 - Entscheidungsbaum für das Maximierungsproblem

Kursangebot | Operations Research 2 | Entscheidungsbaum für das Maximierungsproblem

Operations Research 2

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 belegt. Das bedeutet, dass die Variable nur in der 1. Ebene variiert wird. Für die weitere Ebene wird konstant gehalten und nur variiert. 

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

      max!

u.d.N.

(1)   

(2)    


   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 gesetzt. Außerdem geht die andere Variable für die Berechnung der Zielfunktion mit ein:

.

Das bedeutet einfach, dass dieser Ast und die weiteren Verzweigungen einen maximalen Zielfunktionswert von 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 gesetzt wird und . Damit wird geprüft, ob überhaupt genügend Kapazitäten verfügbar sind, wenn nur 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 in dieser Höhe produziert würde. Es müsste dann der 2. Ast in der obersten Ebene betrachtet werden, indem 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 annehmen darf, damit die Kapazitäten nicht überschritten werden und der Zielfunktionswert maximiert wird. In der ersten Verzweigung (Nr. 2) wird gleich seiner oberen Schranke gesetzt, also . 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 zu produzieren, wenn 1 Einheit von produziert wird. Also wird die nächste Verzweigung durchgeführt (Nr. 3) und eine Einheit nach unten gesetzt: . Auch hier wird die Kapazität überschritten. Es ist also nicht möglich 2 Einheiten von zu produzieren, wenn 1 Einheit von produziert wird. Die nächste Verzweigung Nr. 4 ergibt dann für keine Überschreitung der Restriktionen. Es ist also möglich 1 Einheit von und 1 Einheit von zu produzieren. Der Zielfunktionswert liegt in diesem Fall bei .

Die Verzweigung wird für diesen Ast hier beendet, da eine weitere Reduktion von 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 um eine Einheit reduziert, also auf . Der maximal mögliche Zielfunktionswert wird dann mit dem oberen Schranke von gebildet und mit .

.

Das bedeutet einfach, dass dieser Ast und die weiteren Verzweigungen einen maximalen Zielfunktionswert von 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 geprüft wird, ob dieses Produkt bei Null Einheit die Kapazitäten übersteigt, wenn nur dieses Produkt betrachtet wird und nicht produziert würde (). 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 wieder konstant gehalten wird und mit der obersten Schranke berücksichtigt wird: .  Die Kapazitäten werden nicht überschritten und der Zielfunktionswert liegt bei . 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 und 3 Einheit von zu produzieren. Der Zielfunktionswert liegt in diesem Fall bei .

Lerne erfolgreich mit unseren Online-Kursen

This browser does not support the video element.

Sichere dir jetzt das kompakte Wissen mit unserem Vollzugriff Komplettpaket für Ingenieurstudenten


  • Alle Lernmaterialien komplett mit 494 Videos, 5120 interaktiven Übungsaufgaben und 3108 Lerntexten
  • Günstiger als bei Einzelbuchung nur 14,90 € mtl. bei 1 Monaten Mindestvertragslaufzeit
Jetzt entdecken

This browser does not support the video element.

Einzelkurs: Operations Research 2


  • Die besten Lernmaterialien: 60 Texte, 105 Abbildungen, 13 Videos und 25 Übungsaufgaben.
Jetzt entdecken