Beispiel: Branch and Bound am Maximierungsproblem

In diesem Abschnitt soll das Branch-and-Bound-Verfahren am Ausgangsproblem anhand eines ganzzahligen Maximierungsproblems dargestellt werden, welches bereits im Abschnitt Verfahren von Gomory aufgeführt worden ist.

Gegeben sei das folgende ganzzahlige Maximierungsproblem:

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

u.d.N.

(1) $6x_1 + 5x_2 \le 30$   

(2) $4x_1 + 9 x_2 \le 36$    

Obere Schranken bestimmen

Es wird zunächst die obere Schranke der Variablen $x_1$ und $x_2$ bestimmt:

Die rechte Seite ist durch die Koeffizienten der Nebenbedingungen geteilt worden. Dabei wird der minimale Wert (abgerundet) als obere Schranke verwendet. Demnach besitzt $x_1$ die obere Schranke $x_{1,max} = 5$ und die Variable $x_2$ die obere Schranke $x_{2,max} = 4$. Als nächstes wird festgelegt, mit welcher Variable begonnen wird. Dazu wird die Prioritätenreihenfolge herangezogen.

Prioritätenreihenfolge beachten

Die 1. Priorität ist nicht anzuwenden, da keine negativen Koeffizienten in der Nebenbedingung gegeben sind.

Die 2. Priorität kann ebenfalls nicht angewandt werden, weil keine negativen Koeffizienten in der Zielfunktion gegeben sind.

Die 3. Priorität kann angewandt werden, da positive Koeffizienten in der Zielfunktion gegeben sind. Hier wird der maximale Wert gewählt. Dieser beträgt $2$ und gilt für $x_2$. Es wird also mit $x_2$ begonnen.

Untere Schranken für Restriktionen bestimmen

Es wird nun also mit $x_2$ begonnen. Zunächst müssen die unteren Schranken bestimmt werden. Diese werden bestimmt, indem die obere Schranke $x_{2max} = 4$ in die Nebenbedingungen bzw. Restriktionen $R_i$ eingesetzt werden, wobei $x_1 = 0$ gesetzt wird:

$R_1 = 6 \cdot 0 + 5 \cdot 4 = 20 < 30$   

$R_2 = 4 \cdot 0 + 9 \cdot 4 = 36 \le 36$  

Da die Kapazitäten in den Nebenbedingungen nicht überschritten werden, wird der Baum nun nach unten verzweigt. Normalerweise würde man nun (bei Konstanthaltung von $x_2 = 4$) die Variable $x_1$ solange variieren, bis die beste Kombination gefunden wurde, d.h. bis die Restriktionen nicht mehr überschritten werden. Man würde dabei mit der oberen Schranke von $x_{1,max} = 5$ beginnen und diese dann immer um eine Einheit nach unten setzen. Da aber in der zweiten Restriktion $R_2$ die Kapazität bereits voll ausgeschöpft ist, wenn $x_1$ den Wert Null annimmt, wird nur diese Verzweigung vorgenommen. Denn ein höheres $x_1$ würde zu einer Überschreitung der Restriktion $R_2$ führen und diese Verzweigung wäre demnach unzulässig:

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

$z = 5 + 2 \cdot 4 = 13$.

Das bedeutet einfach, dass dieser Ast und die weiteren Verzweigungen höchstes den Zielfunktionswert von $z = 13$ erreichen können. Es werden dann die unteren Restriktionsschranken eingefügt, indem $x_2 = 4$ gesetzt wird und $x_1 = 0$. Damit wird geprüft, ob überhaupt genügend Kapazitäten verfügbar sind, wenn $x_2$ den Wert $4$ annimmt. Dafür wird die Variable $x_1 $ dann Null gesetzt. Es sind genügend Kapazitäten vorhanden, wenn $x_2 = 4$ und $x_2 = 0$. Es wird nun also nach unten verzweigt und sukzessiv geprüft, welchen Wert $x_1$ annehmen darf, damit die Kapazitäten nicht überschritten werden und der Zielfunktionswert maximiert wird. Wie bereits oben erwähnt ist die Restriktion 2 bereits mit $x_1 = 0$ an ihrem Limit. Deswegen wird hier nur dieser Fall betrachtet. Der Zielfunktionswert erreicht in diesem Fall den Wert:

$z = 0 + 2 \cdot 4 = 8$.

Das weitere Vorgehen ist die Bildung eines neuen Astes, indem $x_2$ mit einer Einheit nach unten gesetzt wird, also $x_2 = 3$ und dann wieder verzweigt wird, wobei $x_1$ nach und nach varriert wird, begonnen mit der oberen Schranke $x_{1,max} = 5$. 

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

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

Das bedeutet einfach, dass dieser Ast und die weiteren Verzweigungen höchstes den Zielfunktionswert von $z = 13$ erreichen können. Dieser liegt über dem bereits ermittelten Zilefunktionswert der zulässige Verzweigung Nr.2. Demnach wird dieser Ast weiter betrachtet. Es werden dann die unteren Restriktionsschranken eingefügt, indem $x_2 = 3$ gesetzt wird und $x_1 = 0$. Es sind genügend Kapazitäten vorhanden, wenn 3 Einheiten von $x_2$ produziert würden. Dieser Ast wird also verzweigt und $x_1$ solange varriert bis eine zulässige Lösung resultiert (Kapazitäten werden nicht überschritten bzw. der Zielfunktionswert fällt nicht unter $z = 8$). In diesem Fall ist die Verzweigung Nr. 7 zulässig, da die Kapazitäten nicht überschritten werden. Außerdem liegt der Zielfunktionswert nicht unterhalb des bereits gefunden (Verzweigung Nr. 2). Er liegt aber auch nicht über diesem Zielfunktionswert, sondern beide sind gleich. Beide Lösungen sind also für diesen Fall als gleich zu bewerten. Es wird nun der nächste Ast Nr. 8 betrachtet usw. Das Verfahren endet, wenn die beste Lösung gefunden worden ist bzw. alle weiteren Verzweigungen ausgeschlossen werden können:

In der obigen Grafik sind die weiteren Äste und ihre Verzweigungen aufgezeigt. Es ist deutlich zu erkennen, dass kein Ast bzw. keine Verzweigung mit einer zulässigen Lösung mehr gefunden wurde, die den Zielfunkionswert von $z = 8$ übersteigt bzw. gleich diesem ist. Demnach sind die besten Ergebnisse mit den Verzweigungen Nr. 2 und und Nr.7 gefunden worden. Für die Lösung sind beide Ergebnisse gleich zu bewerten. Für ein Unternehmen hingegen muss dies nicht der Fall sein. Das Unternehmen muss nun für sich prüfen, für welche Alternative es sich entscheidet. Handelt es sich zum Beispiel um zwei Produkte, so muss das Unternehmen entscheiden, ob es nun beide Produkte herstellt (Nr. 7) oder ob es nur ein Produkt herstellt (Nr. 2). Für diese Entscheidung fließen eine Vielzahl an Faktoren ein. Zum Beispiel die Fixkosten die ein Produkt verursacht. Ist es günstiger nur ein Produkt herzustellen anstelle von zwei Produkten? Aber es spielt auch die Diversifikation auf dem Markt eine Rolle. Ist es besser zwei Prodkte am Markt anzubieten und eventuelle Risiken zu streuen also zu diversifizieren, als sich auf ein einziges Produkt zu konzentrieren? All diese Faktoren müssen dann bei der Wahl der besten Lösung berücksichtigt werden.

Bei dem Gomory-Schnitt (Abschnitt: Verfahren von Gomory) ist nur das Ergebnis Nr.2 herausgekommen, also $x_1 = 0$ und $x_2 = 4$. Man sieht also deutlich, dass der Gomory-Schnitt zwar zum selben Ergebnis geführt hat, aber die Alternative Nr.7 nicht aufgezeigt wurde. Das Verfahren von Branch-and-Bound ist somit in jedem Fall dem Verfahren von Gomory vorzuziehen, wenn wenige Variablen vorhanden sind.