ZU DEN KURSEN!

Operations Research 2 - Branch-and-Bound: Knapsack-Problem (Alternative)

Kursangebot | Operations Research 2 | Branch-and-Bound: Knapsack-Problem (Alternative)

Operations Research 2

Branch-and-Bound: Knapsack-Problem (Alternative)

In diesem Abschnitt soll eine alternative Vorgehensweise für das Branch-and-Bound Verfahren anhand eines Knapsack-Problems dargestellt werden. 

Gegeben sei das folgende Knapsack-Problem:

$F(x) = 14x_1 + 20x_2 + 18x_3 + 26x_4  $\rightarrow $ max!

u.d.N.

$8x_1 + 8x_2 + 6x_3 + 6x_4 \le 14$

$ x_j =\left\{\begin{array}{cl} 1 \\ 0 \end{array}\right. $

Es wird zunächst die Prioritätenreihenfolge festgelegt.

Prioritätenreihenfolge

Bevor mit der Aufstellung des Entscheidungsbaumes begonnen werden kann, wird zunächst die Reihenfolge der Variablen festgelegt, welche nach und nach abgearbeitet werden. Bei dem Knapsack-Problem berechnet man zunächst:

Methode

$\frac{c_j}{a_j}$       Quotient in absteigender Reihenfolge sortieren

und sortiert die resultierenden Werte dann in absteigender Reihenfolge. 

Für das hier angegebene Problem ergibt sich demnach die folgende Reihenfolge:

1. $\frac{26}{6} = 4,33$  für $x_4$

2. $\frac{18}{6} = 3$  für $x_3$

2. $\frac{20}{8} = 2,5$  für $x_2$

2. $\frac{14}{8} = 1,75$  für $x_1$

Es wird mit der Variable $x_4$ auf der obersten Ebene begonnen. Da die Variablen nur die Werte $0$ und $1$ annehmen können, wird die Verzweigung vorgenommen in $x_4 = 0$ und $x_4 = 1$. Für die unteren Ebenen wird $x_4$ konstant gehalten und die anderen Variablen variiert. Dabei wird die Prioritätenreihenfolge beachtet.

Für die oberste Ebene wird der Zielfunktionswert so gebildet, dass alle anderen Variablen den Wert $x_j = 1$ annehmen und $x_4$ mit dem verzweigten Wert eingeht. Dies zeigt den für die nachfolgenden Verzweigungen höchtsmöglich erzielbaren Zielfunktionswert an. Es muss nun mittels der Verzweigungen geprüft werden, ob dieser unter Berücksichtigung der Restriktion auch erreicht werden kann. Die Restriktion für die oberste Ebene wird so bestimmt, dass alle Variablen mit dem Wert $x_j = 0$ eingehen und $x_4$ mit dem verzweigten Wert. Dies zeigt die momentan tatsächlich in Anspruch genommene Restriktion an. 

Der Entscheidungsbaum wird rechtsorientiert erstellt. Das bedeutet, dass zunächst die rechten Verzweigungen solange abgearbeitet werden, bis diese ausgeschlossen werden können. Danach wird weiter von unten nach oben gearbeitet. Es ergibt sich der folgende Entscheidungsbaum nach dem Branch-and-Bound Verfahren:

Branch-and-Bound Knapsack-Problem rechtsorientiert

Das Ergebnis ist äquivalent zum Ergebnis aus dem vorherigen Abschnitt, allerdings sind hier mehr Verzweigungen zu untersuchen und damit der Rechenaufwand erheblich höher als mit dem Branch-and-Bound-Verfahren aus dem vorherigen Abschnitt.