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: Maximierungsprobleme > Branch-and-Bound am Maximierungsproblem (optimale Lösung):

Beispiel: Branch and Bound am Maximierungsproblem (optimale Lösung)

WebinarTerminankündigung aus unserem Online-Kurs Technische Mechanik 3: Dynamik:
 Am 28.02.2017 (ab 16:00 Uhr) findet unser nächstes Webinar statt.
Newtonsche Gesetze
- Innerhalb des 60-minütigen Gratis-Webinars behandeln wir die 3 Newtonsche Gesetze.
[weitere Informationen] [Terminübersicht]

Das Branch-and-Bound-Verfahren am angepassten Problem soll in diesem Abschnitt anhand des Maximierungsproblems aus dem Abschnitt: Ganzzahlige lineare Optimierung veranschaulicht werden.

Gegeben sei das folgenden Ausgangsproblem $P_0$:

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

u.d.N.

(1) $3x_1 + 2x_2 \le 6 $   

(2) $5x_1 + 2 x_2 \le 8$    


$x_1, x_2 \ge 0$    und ganzzahlig

Untere Schranke

Die untere globale Schranke liegt in diesem Fall (aufgrund der Nichtnegativitätsbedingung) bei $x_1 = x_2 = 0$ und damit bei einem Zielfunktionswert von $\underline{F} = 0$. Dies stellt damit auch gleichzeitig die untere globale Schranke des Ausgangsproblems $P_0$ dar (die Zielfunktion kann aufgrund der Nichtnegativitätsbedingung nicht negativ werden).

Obere Schranke

Für das obige angegebene ganzzahlige lineare Optimierungsproblem wird nun zunächst die Ganzzahligkeitsbedingung aufgehoben und das Maximierungsproblem mittels primalen Simplex-Algorithmus oder grafisch gelöst. Das Maximierungsproblem ohne Ganzzahligkeitsbedingung wird dabei mit $P'_0$ bezeichnet, das Ausgangsproblem mit $P_0$. Die grafische Lösung erfolgte bereits im Abschnitt Ganzzahlige lineare Optimierung und ergab eine optimale Lösung für das Problem $P'_0$  (Ganzzahligkeitsbedingung nicht gegeben) von $(x_1, x_2) = (1, 1,5)$. Diese ermittelte optimale Lösung ist nicht ganzzahlig, deswegen für das obige Ausgangsproblem $P_0$ auch nicht zulässig. Der Zielfunktionswert dieser nichtganzzahligen Lösung beträgt $f(x_1, x_2) = 3,5$ und stellt die obere Schranke für das Branch-and-Bound-Verfahren dar. 

Die obere Schranken des Ausgangsproblems $P_0$ ist: $\overline{F}_0 = 3,5$. 

Diese obere Schranken resultierte für nichtganzzahlige Variablen und ist deshalb so nicht zulässig. Das Problem muss demnach verzweigt werden. Die Entscheidung mit welcher Variable begonnen wird in diesem Fall für $x_2$ getroffen, diese einen größeren Wert aufweist.

Verzweigung

Es wird nun das Problem $P_0$ verzweigt in die Teilprobleme $P_1$ und $P_2$. Dabei wird die obere Schranke des angepassten Problems $P'_0$ gewählt. Die untere Schranke ist dabei zunächst $\underline{F} = 0$. Dabei wird die Entscheidungsvariable $x_2$ betrachtet, da diese den größten Wert aufweist. Dabei liegt $x_2$ zwischen den ganzen Zahlen $1$ und $2$. Es werden also die Bedingungen $x_2 \le 1$ für das Problem $P_1$ hinzugefügt und $x_2 \ge 2$ für das Problem $P_2$. Für beide Probleme muss nun wieder die optimale Lösung mittels Simplexalgorithmus oder grafisch erfolgen, indem die angepassten Probleme $P'_1$ und $P'_2$ gelöst werden (Vernachlässigung der Ganzzahligkeitsbedingung). Es soll hier die grafische Vorgehensweise gewählt werden, da der Simplexalgorithmus zeitaufwendiger ist. Die optimale Lösung für die zusätzliche Bedingung von $P'_1$ ergibt sich wie folgt:

branch-and-bound Verfahren optimale Lösung

Es ist die Restriktion $x_2 \le 1$ hinzugefügt worden (schwarze Linie). Die optimale Lösung erhält man dann durch Verschiebung der Zielfunktionsgeraden parallel zu sich selbst bis sich diese gerade noch im zulässigen Bereich befindet. Die zulässige Lösung ergibt sich hier beim Punkt $(1,2 / 1)$. Einsetzen die die Zielfunktion:

$f(1,2/1) = 2 \cdot 1,2 +  1 = 3,4$ 

Für das Problem $P_1$ gilt die neue obere Schranke $\overline{F}_1 = 3,4$. Es handelt sich hierbei um keine zulässige Lösung für das Ausgangsproblem, da keine ganzzahlige Lösung vorliegt. 

Für das Problem $P'_2$ wird die Nebenbedingung $x_2 \ge 2$ hinzugefügt:

branch-and-bound Verfahren optimale Lösung

Die neue Nebenbedingung $x_2 \ge 2$ ist hinzugefügt worden. Hier muss beachtet werden, dass nur der Bereich oberhalb von $x_2 = 2$ betrachtet werden darf, aber unterhalb der beiden Nebenbedingungen (1) und (2) des Ausgangsproblems, da diese $\le$-Bedingungen darstellen. Der zulässige Bereich ist durch die schwarzen dicken Linien gekennzeichnet. Die Zielfunktion wird nun innerhalb dieses Bereiches (parallel zu sich selbst) verschoben, bis diese gerade noch in diesem Bereich liegt. Der Punkt $(0,67 /2)$ stellt die optimale Lösung dar. Einsetzen in die Zielfunktion ergibt:

$f(0,67/2) = 2 \cdot 0,67 + 2 = 3,34$ 

Für das Problem $P_2$ gilt die neue obere Schranke $\overline{F}_2 = 3,34$. Es handelt sich hierbei um keine zulässige Lösung für das Ausgangsproblem, da keine ganzzahlige Lösung vorliegt. 

Branch-and-Bound optimale Lösung Maximierungsproblem

Es wird nun das Problem $P_1$ weiter verzweigt, weil dieses einen höheren Zielfunktionswert aufweist.

Bei der weiteren Verzweigung wird als nächstes die Variable $x_1$ betrachtet. Diese liegt zwischen den ganzen Zahlen $1$ und $2$. Es wird demnach für $P_3$ die Bedingung $x_1 \le 1$ und für $P_4$ die Bedingung $x_1 \ge 2$ hinzugefügt.

Es wird nun wieder das angepasste Problem $P'_3$ gelöst mit zusätzlicher Berücksichtigung der Bedingung $x_1 \le 1$ und das Problem $P'_4$ mit $x_1 \ge 2$. Hier wird wieder die Grafik verwendet:

branch-and-bound Verfahren optimale Lösung

In der obigen Grafik sind nun die beiden Teilprobleme veranschaulicht. Zur Bestimmung der oberen Schranke für $P_3$ wurde als zusätzliche Restriktion $x_1 \le 1$ eingefügt. Die Restriktion $x_2 \le 1$ für $P_1$ musste dabei erhalten bleiben. Es ergibt sich also der rechteckige zulässige Bereich in welchem die Zielfunktionsgerade verschoben werden muss, bis diese den Bereich gerade noch berührt. Der optimale Punkt liegt bei $(1/1)$. Damit ergibt sich die erste ganzzahlige Lösung, die oberhalb der untersten Schranke $\underline{F} = 0$ liegt. Es handelt sich hierbei um den Fall b, denn $\overline{F}_3 > \underline{F}$, wobei die gegebene Lösung ganzzahlig und zulässig ist (innerhalb des zulässigen Bereiches liegt). Einsetzen der Werte $x_1 = 1$ und $x_2 = 1$ in die Zielfunktion ergibt die neue untere Schranke:

Methode

$\underline{F}_3 = 3$


Zur Bestimmung der oberen Schranke für $P_4$ wurde als zusätzliche Restriktion $x_1 \ge 2$ eingefügt. Die Restriktion $x_2 \le 1$ für $P_1$ musste dabei erhalten bleiben. Da es sich hierbei um eine größer-gleich-Bedingung handelt, die Variable $x_1$ also größer als $2$ werden muss ist das Problem nicht lösbar, da der Punkt dann nicht mehr im zulässigen Bereich liegt, sondern außerhalb. Es ist der Fall c gegeben. 

branch-and-bound Verfahren optimale Lösung

Die Verzweigung am linken Ast ist nun abgeschlossen. Es wird nun der rechte Ast $P_2$ betrachtet und dieser verzweigt. Dabei gilt für $P_5$ die Bedingung $x_1 \le 0$ und für $P_6$ die Bedingung $x_1 \ge 1$. Die optimale Lösung für die angepassten Probleme ergibt sich wie folgt:

branch-and-bound Verfahren optimale Lösung

In der obigen Grafik sind nun die beiden Teilprobleme veranschaulicht. Zur Bestimmung der oberen Schranke für $P_5$ wurde als zusätzliche Restriktion $x_1 \le 0$ eingefügt. Die Restriktion $x_2 \ge 2$ für $P_2$ musste dabei erhalten bleiben. Es ergibt sich also der Bereich auf der $y$-Achse ($x_1 = 0$) und oberhalb von $x_2 = 2$, aber unterhalb der grünen Restriktion. Es ergibt sich demnach der Punkt $(0/3)$, welcher gerade noch im zulässigen Bereich liegt. Damit ergibt sich eine ganzzahlige Lösung, die oberhalb der untersten Schranke $\underline{F} = 0$ liegt. Es handelt sich hierbei allerdings um den Fall a, da die untere Schranke $\underline{F}_3 = 3$ bereits größer/gleich diesem Wert ist.

Zur Bestimmung der oberen Schranke für $P_6$ wurde als zusätzliche Restriktion $x_1 \ge 1$ eingefügt. Die Restriktion $x_2 \ge 2$ für $P_2$ musste dabei erhalten bleiben. Da es sich hierbei um eine größer-gleich-Bedingung handelt, die Variable $x_1$ also größer als $1$ und $x_2$ größer als $2$ werden muss ist das Problem nicht lösbar, da der Punkt dann nicht mehr im zulässigen Bereich liegt, sondern außerhalb. Es ist der Fall c gegeben. 

branch-and-bound Verfahren optimale Lösung

Die beste zulässige Lösung des ganzzahligen Maximierungsproblems ist bei $x_1 = 1$ und $x_2 = 1$ mit $F_3 = 3$ gegeben. Es ist deutlich zu erkennen, dass das Ergebnis dasselbe ist, wie mit dem Branch-and-Bound Verfahren ohne Bestimmung der optimalen Lösung. Der Rechenaufwand für dieses hier gezeigte Verfahren ist um einiges höher, weshalb sich das Branch-and-Bound Verfahren ohne vorherige Ermittlung der optimalen Lösung empfiehlt. 

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:

  • Gute Bewertung für Operations Research 2

    Ein Kursnutzer am 30.01.2017:
    "Bis jetzt alles top. Danke! "

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

10% Coupon: lernen10

Zu den Online-Kursen