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:

Beispiel: Branch and Bound am Maximierungsproblem

WebinarTerminankündigung:
 Am 20.12.2016 (ab 16:00 Uhr) findet unser nächstes Webinar statt.
Gratis-Webinar (Operations Research) Primaler Simplexalgorithmus
- Das 60-minütige Gratis-Webinar behandelt den primalen Simplexalgorithmus.
[weitere Informationen] [Terminübersicht]

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:

$x_1$ $x_2$
$30/6 = 5$ $30/5 = 6$
$36/4 = 9$ $36/9 = 4$
$x_{1,max} = 5$ $x_{2,max} = 4$

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:

Branch-and-Bound Maximierungsproblem Beispiel

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:

Branch-and-Bound Maximierungsproblem Beispiel

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.

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)
    • Verfahren der vorsichtigen Annäherung
  • 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)
  • 61
  • 7
  • 25
  • 64
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