Inhaltsverzeichnis
XXXXXDie Aufstellung des Entscheidungsbaums soll anhand des folgenden Beispiels dargestellt werden. Es sei das folgende ganzzahlige Maximierungsproblem gegeben:
u.d.N.
(1)
(2)
Es ist sinnvoll das hier gegebene Problem in ein Maximierungsproblem umzuwandeln, da die Nebenbedingungen bereits alle
Es ergibt sich das folgende ganzzahlige Maximierungsproblem:
u.d.N.
(1)
(2)
Wahl der oberen Schranke
Es wird zunächst die obere Schranke der Variablen
Die rechte Seite ist durch die Koeffizienten der Nebenbedingungen geteilt worden. Dabei wird der minimale Wert (abgerundet) als obere Schranke verwendet. Demnach besitzt
Prioritätenreihenfolge beachten
Die 1. Priorität ist nicht anzuwenden, da keine negativen Koeffizienten in der Nebenbedingung gegeben sind.
Die 2. Priorität kann hier angewandt werden, weil negative Koeffizienten in der Zielfunktion gegeben sind. Der negative Koeffizient befindet sich in der 3. Nebenbedingung und beträgt
Untere Schranken für Restriktionen bestimmen
Es wird nun also mit
Da die Kapazitäten in den Nebenbedingungen nicht unterschritten werden, wenn beide Variablen mit ihren maximalen Werten eingehen, wird der Baum nun nach unten verzweigt und es wird im Weiteren
Die Zielfunktion für den ersten Ast wird dabei so bestimmt, dass
Die Zielfunktion soll minimiert werden, weshalb hier
Der Zielfunktionswert der obersten Ebene wird immer mit dem angegebenen
erzielt. Die Variablen nehmen die ganzzahligen Werte
Weitere interessante Inhalte zum Thema
-
Entscheidungsbaum für das Minimierungsproblem
Vielleicht ist für Sie auch das Thema Entscheidungsbaum für das Minimierungsproblem (Ganzzahlige Optimierung) aus unserem Online-Kurs Operations Research 2 interessant.
-
Branch-and-Bound am Minimierungsproblem
Vielleicht ist für Sie auch das Thema Branch-and-Bound am Minimierungsproblem (Ganzzahlige Optimierung) aus unserem Online-Kurs Operations Research 2 interessant.