Inhaltsverzeichnis
Bei einem Knapsack-Problem (auch: Rucksack-Problem) soll ein knappes Gut optimal verteilt werden. Knappsack-Probleme haben häufig nur eine einzige $\le$-Nebenbedingung gegeben, in welcher sich alle Entscheidungsvariablen befinden. Die Anzahl der Entscheidungsvariablen ist häufig sehr hoch.
Ein Knapsack-Problem lässt sich auf ein binäres Problem zurückführen. In diesem Abschnitt soll gezeigt werden, wie man ein solches Problem mittels Branch-and-Bound-Verfahren lösen kann.
Es sei das folgende ganzzahlige Maximierungsproblem gegeben:
$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. $
Das Ausgangsproblem $P_0$ wird in Teilprobleme zerlegt. Dafür wird für jedes Teilproblem $P_i$ eine obere und eine untere Schranke bestimmt.
Bestimmung der oberen Schranke
Die obere Schranke wird bestimmt, indem die Quotienten aus Koeffizient der Zielfunktion durch Koeffizient der Nebenbedingung in absteigender Reihenfolge sortiert werden:
Methode
$\frac{c_j}{a_j}$ Quotient in absteigender Reihenfolge sortieren
Danach wird für jede Variable nach dieser Reihenfolge der Wert $x_j = 1$ gewählt, solange die Restriktion $b = 14$ nicht überschritten wird. Die erste Variable, die nicht mehr voll aufgenommen werden kann, wird anteilig mit eingeplant.
Die Variablenwerte werden dann in die Zielfunktion eingesetzt und damit die obere Schranke des Teilproblems $P_i$ bestimmt.
Für das hier angegebene Beispiel werden zunächst die Quotienten gebildet und in absteigender Reihenfolge sortiert:
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$
Danach wird die obere Schranke festgelegt. Zunächst wird $x_4$ mit $x_4 = 1$ in der Restriktion berücksichtigt:
$R = 6 \le 14$
Danach $x_3 = 1$ hinzugefügt:
$R = 6 + 6 = 12 \le 14$
Danach $x_2 = 1$:
$R = 6 + 6 + 8 = 20 > 14$
Die Variable $x_2$ muss demnach anteilig berücksichtigt werden.
Wenn $x_4 = x_3 = 1$ eingeplant werden, dann ist:
$R = 6 + 6 = 12$
Es ist aber eine Kapazität vorhanden von $14$. Demnach gibt es eine Differenz von $2$. Die Variable $x_2$ besitzt aber $a_j = 8$:
$x_2 = \frac{2}{8} = 1/4$.
Die letzte Variable $x_1$ geht mit dem Wert $x_1 = 0$ ein, da keine Kapazität mehr vorhanden ist.
Es ergibt sich also der Punkt:
$x = (0, 1/4, 1, 1)$
Die obere Schranke ist demnach:
Methode
$\overline{F}_0 = 14 \cdot 0 + 20 \cdot 1/4 + 18 \cdot 1 + 26 \cdot 1 = 49$
Da es sich um eine nichtganzzahlige Lösung handelt, ist die Lösung nicht zulässig. Damit muss das Problem verzweigt werden.
Bestimmung der unteren Schranke
Die untere Schranke wird bestimmt, indem die nicht ganzzahlige Variable mit dem Wert $0$ in der Zielfunktion berücksichtigt wird.
Für dieses Beispiel ist die untere Schranke demnach:
Methode
$\underline{F} = 14 \cdot 0 + 20 \cdot 0 + 18 \cdot 1 + 26 \cdot 1 = 44$
Ein Teilproblem braucht nicht weiter betrachtet werden, wenn gilt:
Methode
Fall a: $\overline{F}_i \le \underline{F}$. Die ermittelte optimale Lösung (durch Simplex bei Weglassen der Ganzzahligkeitsbedingung) ist kleiner als die beste zulässige ganzzahlige Lösung (untere Schranke des Teilsproblems).
Fall b: $\overline{F}_i > \underline{F}$. Die optimale Lösung des Teilproblems ist größer als die bereits gefunde beste zulässige ganzzahlige Lösung. Diese Lösung ist zudem ganzzahlig und ebenfalls zulässig. Es wird
$\underline{F} = \overline{F}_i $
gesetzt. Es existiert demnach eine neue untere Schranke, welche die Ganzzahligkeitsbedingung erfüllt und zulässig ist.
Fall c: Es existiert keine zulässige Lösung.
Es wird immer diejenige Variable verzweigt, welche nichtganzzahlige Werte aufweist. In diesem Beispiel wird also mit der Variable $x_2 = 1/4$ begonnen und diese verzweigt in $x_2 = 0$ und $x_2 = 1$.
Für das Teilproblem $P_1$ wird $x_2 = 0$ gesetzt und wieder die obere Schranke bestimmt. Hierbei muss wieder die obige Reihenfolge eingehalten werden.
Zunächst wird $x_4$ mit $x_4 = 1$ in der Restriktion berücksichtigt:
$R = 6 \le 14$
Danach $x_3 = 1$ hinzugefügt:
$R = 6 + 6 = 12 \le 14$
Danach $x_2 = 0$:
$R = 6 + 6 = 12 \le 14$
Danach $x_1 = 1$:
$R = 6 + 6 + 8 = 20 > 14$
Die Variable $x_1$ muss demnach anteilig berücksichtigt werden:
$x_1 = \frac{2}{8} = 1/4$
Die obere Schranke für das Teilproblem ist demnach:
Methode
$\overline{F}_1 = 14 \cdot 1/4 + 20 \cdot 0 + 18 \cdot 1 + 26 \cdot 1 = 47,5$
Da es sich um eine nichtganzzahlige Lösung handelt, ist die Lösung nicht zulässig. Damit muss das Problem verzweigt werden.
Für das Teilproblem $P_1$ wird $x_2 = 1$ gesetzt und wieder die obere Schranke bestimmt. Hierbei muss wieder die obige Reihenfolge eingehalten werden.
Zunächst wird $x_4$ mit $x_4 = 1$ in der Restriktion berücksichtigt:
$R = 6 \le 14$
Danach $x_3 = 1$ hinzugefügt:
$R = 6 + 6 = 12 \le 14$
Danach $x_2 = 1$:
$R = 6 + 6 + 8 = 20 > 14$
Die Kapazität ist nicht ausreichend. Die Variable über $x_2$ (in der Reihenfolge hier) muss demnach zunächst unberücksichtigt bleiben. Es gilt $x_4 = x_2 = 1$:
$R = 6 + 8 = 14$
Da die Kapazität voll ausgeschöpft ist, wird $x_3 = x_1 = 0$ gesetzt.
Die obere Schranke ergibt also:
Methode
$\overline{F}_2 = 14 \cdot 0 + 20 \cdot 1 + 18 \cdot 0 + 26 \cdot 1 = 46$
Es handelt sich hierbei um eine zulässige Lösung, weil die Lösung ganzzahlig ist. Da diese ermittelte zulässige Lösung größer ist als die untere Schranke $\underline{F}_0 = 44$ liegt eine neue untere Schranke vor (Fall b):
$\underline{F} = 46$.
Das Problem $P_2$ muss nicht weiter verzweigt werden.
Weitere interessante Inhalte zum Thema
-
Branch-and-Bound-Verfahren
Vielleicht ist für Sie auch das Thema Branch-and-Bound-Verfahren (Ganzzahlige Optimierung) aus unserem Online-Kurs Operations Research 2 interessant.
-
Branch-and-Bound am Maximierungsproblem (optimale Lösung)
Vielleicht ist für Sie auch das Thema Branch-and-Bound am Maximierungsproblem (optimale Lösung) (Ganzzahlige Optimierung) aus unserem Online-Kurs Operations Research 2 interessant.
