ingenieurkurse
online lernen

Besser lernen mit Online-Kursen

NEU! Jetzt online lernen:
Operations Research 2
Den Kurs kaufen für:
einmalig 39,00 €
Zur Kasse
Ganzzahlige Optimierung > Branch-and-Bound-Verfahren:

Branch-and-Bound: Knapsack-Problem

WebinarTerminankündigung aus unserem Online-Kurs Technische Mechanik 3: Dynamik:
 Am 31.01.2017 (ab 16:00 Uhr) findet unser nächstes Webinar statt.
Gradlinige Bewegung eines Massenpunktes
- In diesem 60-minütigen Webinar werden die kinematischen Grundaufgaben behandelt.
[weitere Informationen] [Terminübersicht]

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$.

Branch and Bound Knapsack Problem

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.

Kommentare zum Thema: Branch-and-Bound: Knapsack-Problem

  • Jan Morthorst schrieb am 05.04.2016 um 19:26 Uhr
    Hallo Herr Quast, vielen Dank für den Hinweis. Wir haben den Fehler behoben. Viel Erfolg für Ihre bevorstehende Klausur!!
  • Eckehard Quast schrieb am 05.04.2016 um 18:20 Uhr
    Hallo, leider kann man man den Text nicht richtig lesen und damit arbeiten, da SEHR viele Funktionen und mathematische Formeln nicht ordentlich angezeigt werden. Sehr ärgerlich in der Klausurphase!
Vorstellung des Online-Kurses Operations Research 2Operations Research 2
Dieser Inhalt ist Bestandteil des Online-Kurses

Operations Research 2

Ingenieurkurse (ingenieurkurse.de)
Diese Themen werden im Kurs behandelt:

[Bitte auf Kapitelüberschriften klicken, um Unterthemen anzuzeigen]

  • Operations Research 2: Überblick
    • Einleitung zu Operations Research 2: Überblick
  • Grundlagen des Operations Research 1
    • Einleitung zu Grundlagen des Operations Research 1
    • Definition: Lineares Programm
    • Standardform: Maximierungsproblem
      • Einleitung zu Standardform: Maximierungsproblem
      • Grafische Lösung des Maximierungsproblems
    • Primaler Simplexalgorithmus
      • Einleitung zu Primaler Simplexalgorithmus
      • Lösung des Maximierungsproblems mittels primalen Simplexalgorithmus
    • Dualer Simplexalgorithmus
    • Umformung in die Standardform
    • Umformung in die Normalform
  • Ganzzahlige Optimierung
    • Einleitung zu Ganzzahlige Optimierung
    • Grafisches Verfahren
    • Verfahren von Gomory
      • Einleitung zu Verfahren von Gomory
      • Beispiel: Verfahren von Gomory
    • Branch-and-Bound-Verfahren
      • Einleitung zu Branch-and-Bound-Verfahren
      • Branch-and-Bound: Maximierungsprobleme
        • Einleitung zu Branch-and-Bound: Maximierungsprobleme
        • Branch-and-Bound am Maximierungsproblem
          • Einleitung zu Branch-and-Bound am Maximierungsproblem
          • Festlegung der oberen/unteren Schranke, Prioritätenfestlegung
          • Entscheidungsbaum für das Maximierungsproblem
          • Beispiel: Branch and Bound am Maximierungsproblem
        • Branch-and-Bound am Maximierungsproblem (optimale Lösung)
          • Einleitung zu Branch-and-Bound am Maximierungsproblem (optimale Lösung)
          • Beispiel: Branch and Bound am Maximierungsproblem (optimale Lösung)
      • Branch-and-Bound: Minimierungsprobleme
        • Einleitung zu Branch-and-Bound: Minimierungsprobleme
        • Branch-and-Bound am Minimierungsproblem
          • Einleitung zu Branch-and-Bound am Minimierungsproblem
          • Festlegung der unteren/oberen Schranke, Prioritätenfestlegung
          • Entscheidungsbaum für das Minimierungsproblem
          • Beispiel: Branch and Bound am Minimierungsproblem
        • Branch-and-Bound am Minimierungsproblem (optimale Lösung)
          • Einleitung zu Branch-and-Bound am Minimierungsproblem (optimale Lösung)
          • Beispiel: Branch and Bound am Minimierungsproblem (optimale Lösung) 1
          • Beispiel: Branch and Bound am Minimierungsproblem (optimale Lösung) 2
          • Beispiel: Branch and Bound am Minimierungsproblem (optimale Lösung) 3
      • Branch-and-Bound: Knapsack-Problem
      • Branch-and-Bound: Knapsack-Problem (Alternative)
  • Kombinatorische Optimierung
    • Einleitung zu Kombinatorische Optimierung
    • Traveling-Salesman-Problem
      • Einleitung zu Traveling-Salesman-Problem
      • Vollständige Enumeration
        • Einleitung zu Vollständige Enumeration
        • Beispiel: Vollständige Enumeration (Reduktion der Matrix)
        • Beispiel: Vollständige Enumeration (Anwendung des Verfahrens)
      • Heuristische Verfahren
        • Einleitung zu Heuristische Verfahren
        • Verfahren des besten Nachfolgers
          • Einleitung zu Verfahren des besten Nachfolgers
          • Verfahren des besten Nachfolgers (Ausgangsmatrix)
          • Verfahren des besten Nachfolgers (reduzierte Matrix)
        • Verfahren der sukzessiven Einbeziehung von Stationen
          • Einleitung zu Verfahren der sukzessiven Einbeziehung von Stationen
          • Einbeziehung von Stationen (Ausgangsmatrix)
      • Entscheidungsbaumverfahren
        • Einleitung zu Entscheidungsbaumverfahren
        • Begrenzte Enumeration
        • Branch-and-Bound Verfahren am Traveling-Salesman-Problem
          • Einleitung zu Branch-and-Bound Verfahren am Traveling-Salesman-Problem
          • Branch-and-Bound (TSP): 1. Iteration
          • Branch-and-Bound (TSP): Weitere Iterationen
    • Fertigungsablaufplanung
      • Einleitung zu Fertigungsablaufplanung
      • Flow-Shop-Probleme
      • Johnson-Algorithmus
  • Nichtlineare Optimierung
    • Grundlagen der nichtlinearen Optimierung
      • Einleitung zu Grundlagen der nichtlinearen Optimierung
      • Konkave und konvexe Funktionen
        • Einleitung zu Konkave und konvexe Funktionen
        • Beispiel: Nachweis konvexer/konkaver Funktionen auf direktem Weg
        • Beispiel: Nachweis konvexer/konkaver Funktionen über Differenzierbarkeit
    • Nichtlineare Optimierung unter Nebenbedingungen
      • Einleitung zu Nichtlineare Optimierung unter Nebenbedingungen
      • Methode der zulässigen Richtung
        • Einleitung zu Methode der zulässigen Richtung
        • Beispiel: Methode der zulässigen Richtungen (1. Iteration)
        • Beispiel: Methode der zulässigen Richtungen (2. Iteration)
        • Beispiel: Methode der zulässigen Richtungen (3. Iteration)
  • 60
  • 7
  • 25
  • 67
einmalig 39,00
umsatzsteuerbefreit gem. § 4 Nr. 21 a bb) UStG
Online-Kurs Top AngebotTrusted Shop

Unsere Nutzer sagen:

  • Phillipp Grünewald

    Phillipp Grünewald

    "ingenieurkurse.de hat mir besonders bei den Mathe-Themen geholfen. Super Erklärungen!"
  • Martina Pfeiffer

    Martina Pfeiffer

    "Klasse für den Einstieg ins Ingenieurstudium."
  • Marcel Eberhardt

    Marcel Eberhardt

    "Ich mache mir dank euch keine Sorgen für die Prüfungen. Danke!"

NEU! Sichere dir jetzt die perfekte Prüfungsvorbereitung und spare 10% bei deiner Kursbuchung!

10% Coupon: lernen10

Zu den Online-Kursen