Log out Zur App
Zur App

Lerninhalte finden

Features

Entdecke

Lineare und Kombinatorische Optimierung - Exam.pdf

Herunterladen Save
Lineare und Kombinatorische Optimierung - Exam
Lineare und Kombinatorische Optimierung - Exam Aufgabe 1) Gegeben sei das lineare Optimierungsproblem mit den zwei Entscheidungsvariablen x1 und x2 : Zielfunktion: z = 3x1 + 2x2 Nebenbedingungen: x1 + x2 ≤ 4 2x1 + x2 ≤ 5 x1 ≥ 0 x2 ≥ 0 Verwende graphische Lösungsmethoden, um dieses Optimierungsproblem zu lösen. a) Zeichne alle Nebenbedingungen in das x1x2 -Koordinatensystem. Bestimme den zulässigen...

© StudySmarter 2024, all rights reserved.

Lineare und Kombinatorische Optimierung - Exam

Aufgabe 1)

Gegeben sei das lineare Optimierungsproblem mit den zwei Entscheidungsvariablen x1 und x2:

  • Zielfunktion: z = 3x1 + 2x2
  • Nebenbedingungen:
    • x1 + x2 ≤ 4
    • 2x1 + x2 ≤ 5
    • x1 ≥ 0
    • x2 ≥ 0
  • Verwende graphische Lösungsmethoden, um dieses Optimierungsproblem zu lösen.

a)

Zeichne alle Nebenbedingungen in das x1x2-Koordinatensystem. Bestimme den zulässigen Bereich, welcher durch die Schnittpunkte der Nebenbedingungen gebildet wird. Achte darauf, diesen Bereich korrekt zu kennzeichnen.

Lösung:

Um dieses Optimierungsproblem zu lösen und alle Nebenbedingungen im x1x2-Koordinatensystem zu zeichnen, folge diesen Schritten:

  1. Zeichne die Zielfunktion: z = 3x1 + 2x2.
  2. Nebenbedingungen:
  • x1 + x2 ≤ 4 Setze x1 auf Null: x2 = 4 und setze x2 auf Null: x1 = 4. Zeichne die Gerade, die durch die Punkte (4, 0) und (0, 4) verläuft.
  • 2x1 + x2 ≤ 5 Setze x1 auf Null: x2 = 5 und setze x2 auf Null: x1 = 2.5. Zeichne die Gerade, die durch die Punkte (2.5, 0) und (0, 5) verläuft.
  • x1 ≥ 0 und x2 ≥ 0 Diese Bedingungen treten auf, wenn sich die Lösung im ersten Quadranten befindet.
  • Finde die Schnittpunkte der Geraden:
    • Setze x1 + x2 = 4 und 2x1 + x2 = 5:
  • Setze x1 + x2 = 4 in 2x1 + x2 = 5 ein:
  • Setze x2 = 4 - x1 in 2x1 + x2 = 5 ein:
    •  2x1 + (4 - x1) = 5 2x1 + 4 - x1 = 5 x1 + 4 = 5 x1 = 1
  • Setze x1 = 1 in x1 + x2 = 4 ein:
    • 1 + x2 = 4 x2 = 3
  • Der Schnittpunkt ist also (1, 3).
  • Weitere Schnittpunkte:
    • (4, 0): Schnittpunkt der beiden Punktangaben (4,0) und (0,4).
    • (2.5, 0) und (0, 5): Schnittpunkt der zweiten Linearen Nebenbedingung.
  • Bestimme den zulässigen Bereich:
    • Der Bereich wird durch die Schnittpunkte: (0,0), (4,0), (1,3) und (2.5,0) definiert.
    • Zeichne den Bereich in das Koordinatensystem.
      • Mit oben genannten Schritten wird die graphische Lösungsmethode korrekt umgesetzt, den zulässigen Bereich darzustellen.

    b)

    Stelle die Zielfunktion z = 3x1 + 2x2 als Gerade im Koordinatensystem dar und verschiebe diese entlang des Vektors c = (3, 2). Beschreibe den Prozess der Verschiebung und wie sie dabei hilft, den optimalen Punkt zu finden.

    Lösung:

    Um die Zielfunktion z = 3x1 + 2x2 als Gerade im Koordinatensystem darzustellen und sie entlang des Vektors c = (3, 2) zu verschieben, folge diesen Schritten:

    1. Stelle die Zielfunktion als Gleichung einer Geraden dar:
      2. 3x1 + 2x2 = z
    2. Setze verschiedene Werte für z ein, um verschiedene Parallelen zu zeichnen, z.B.:
      3. Wenn z = 6: 3x1 + 2x2 = 6 Wenn z = 12: 3x1 + 2x2 = 12
    3. Zeichne die Geraden in das x1x2-Koordinatensystem:
    • Für z = 6:
      • Setze x1 auf Null: x2 = 3 (Punkt (0, 3))
      • Setze x2 auf Null: x1 = 2 (Punkt (2, 0))
      • Zeichne die Gerade durch die Punkte (0, 3) und (2, 0).
    • Für z = 12:
      • Setze x1 auf Null: x2 = 6 (Punkt (0, 6))
      • Setze x2 auf Null: x1 = 4 (Punkt (4, 0))
      • Zeichne die Gerade durch die Punkte (0, 6) und (4, 0).
  • Verschiebe die Zielfunktion entlang des Vektors c = (3, 2):
    • Der Gradient der Zielfunktion ist c = (3, 2) (dies zeigt die Richtung der Verschiebung an).
    • Beginne mit einer beliebigen Gerade der Zielfunktion und verschiebe sie parallel, bis du den Rand des zulässigen Bereichs erreichst.
    • An dem Punkt, an dem die Linie den zulässigen Bereich tangiert, findest du den optimalen Punkt.
  • Im zulässigen Bereich (gebildet durch die Nebenbedingungen x1 + x2 ≤ 4, 2x1 + x2 ≤ 5, x1 ≥ 0, x2 ≥ 0), bewege die Zielfunktion parallel in Richtung des Vektors c:
    • Setze Punkte, bei denen die Zielfunktion den zulässigen Bereich berührt:
      • Bei einer Verschiebung wird klar, dass der Punkt (2, 1) der optimale Punkt ist.
      • Berechnung: 
        z = 3(2) + 2(1) = 6 + 2 = 8
  • Der Prozess der Verschiebung:
    • Bestimme den optimalen Punkt (2, 1), an welchem z den maximalen Wert (8) erreicht.
    • Dies ist der maximale Wert innerhalb des zulässigen Bereichs.

    c)

    Bestimme den optimalen Punkt und den zugehörigen Zielfunktionswert. Erkläre Schritt für Schritt, wie Du diesen Punkt im zulässigen Bereich gefunden hast und weshalb dieser Punkt den Extremwert der Zielfunktion darstellt.

    Lösung:

    Um den optimalen Punkt und den zugehörigen Zielfunktionswert für das gegebene lineare Optimierungsproblem zu bestimmen, verwenden wir die graphische Lösungsmethode in mehreren präzisen Schritten:

    1. Zeichne die Nebenbedingungen im x1x2-Koordinatensystem:
      • x1 + x2 ≤ 4: Setze x1 = 0 und berechne x2 (Punkt (0, 4)). Setze x2 = 0 und berechne x1 (Punkt (4, 0)). Zeichne die Gerade durch diese Punkte im Koordinatensystem.
      • 2x1 + x2 ≤ 5: Setze x1 = 0 und berechne x2 (Punkt (0, 5)). Setze x2 = 0 und berechne x1 (Punkt (2.5, 0)). Zeichne die Gerade durch diese Punkte im Koordinatensystem.
      • x1 ≥ 0 und x2 ≥ 0 beschränken den Bereich auf den ersten Quadranten.
    2. Bestimme die Schnittpunkte der Nebenbedingungen:
      • Punkt (4, 0)
      • Punkt (0, 4)
      • Punkt (2.5, 0)
      • Schnittpunkt der Gleichungen x1 + x2 = 4 und 2x1 + x2 = 5:
       \begin{aligned} x1 + x2 &= 4 \ 2x1 + x2 &= 5 \ \text{Subtrahiere die erste Gleichung von der zweiten:} \ (2x1 + x2) - (x1 + x2) &= 5 - 4 \ x1 &= 1 \ \text{Setze } x1 = 1 \text{ in } x1 + x2 = 4: \ 1 + x2 &= 4 \ x2 &= 3 \
      Somit ist der Schnittpunkt (1, 3).
    3. Markiere den zulässigen Bereich:
      • Der zulässige Bereich wird durch die Punkte (0, 0), (4, 0), (0, 4), (2.5, 0) und (1, 3) begrenzt.
    4. Zeichne die Zielfunktion im Koordinatensystem:
      • Setze zum Beispiel z = 12 für die Zielfunktion z = 3x1 + 2x2: 
         \begin{aligned} 3x1 + 2x2 &= 12 \ \text{Für } x1 = 0: x2 = 6 \text{ (Punkt (0, 6))} \ \text{Für } x2 = 0: x1 = 4 \text{ (Punkt (4, 0))} \ \text{Zeichne die Gerade durch die Punkte (0, 6) und (4, 0).} \
    5. Verschiebe die Zielfunktion entlang des Vektors c = (3, 2):
      • Bewege die Gerade parallel, bis sie den zulässigen Bereich tangiert.
    6. Bestimme den optimalen Punkt und berechne den Zielfunktionswert: Durch die Untersuchung der Ecken des zulässigen Bereichs:
      • Punkt (4, 0): 
         \begin{aligned} z &= 3(4) + 2(0) = 12 \end{aligned}
      • Punkt (1, 3): 
         \begin{aligned} z &= 3(1) + 2(3) = 3 + 6 = 9 \end{aligned}
      • Punkt (0, 4): 
         \begin{aligned} z &= 3(0) + 2(4) = 8 \end{aligned}
      • Punkt (2.5, 0): 
         \begin{aligned} z &= 3(2.5) + 2(0) = 7.5 \end{aligned}
    7. Analyse:
      • Der höchste Zielfunktionswert wird bei Punkt (4, 0) erreicht und beträgt z = 12.
      • Da dieser Punkt den höchsten Wert der Zielfunktion innerhalb des zulässigen Bereichs liefert und auf der Grenzlinie des zulässigen Bereichs liegt, ist er der optimale Punkt.

    Der optimale Punkt ist daher (4, 0) und der zugehörige Zielfunktionswert beträgt z = 12. Dieser Punkt stellt den Extremwert der Zielfunktion dar, weil kein anderer Punkt im zulässigen Bereich einen höheren Zielfunktionswert erzeugt.

    Aufgabe 2)

    Tableau-Formen des Simplex-AlgorithmusGegeben sei das folgende Lineare Optimierungsproblem (LOP) und sein initiales Simplex-Tableau:

    • Zielfunktion: maximiere Z = 3x1 + 2x2
    • Restriktionen:
      • 2x1 + x2 ≤ 4
      • x1 + 2x2 ≤ 3
      • x1, x2 ≥ 0
    Das initiale Simplex-Tableau sei gegeben durch:
    \t|Basis   | Cb | x1 | x2 | s1 | s2 |  RHS |\t|--------|----|----|----|----|----|------|\t|  s1    | 0  | 2  | 1  | 1  | 0  |   4  |\t|  s2    | 0  | 1  | 2  | 0  | 1  |   3  |\t|  Z     |    | -3 | -2 | 0  | 0  |   0  |\t

    a)

    Führe eine Pivot-Operation durch, um das Simplex-Tableau zu aktualisieren. Bestimme die Eintritts- und die Austrittsvariable. Zeige die Berechnungen und konstruiere das neue Tableau.

    Lösung:

    Pivot-Operation im Simplex-AlgorithmusUm das Simplex-Tableau zu aktualisieren, folgen wir diesen Schritten Schritt für Schritt.

    • Bestimme die Eintrittsvariable:Die Eintrittsvariable wird durch die Variable in der Zielfunktionszeile (Z-Reihe) mit dem höchsten negativen Koeffizienten bestimmt. In unserem Fall haben wir:
       Z = -3 x1 -2 x2
      Hier ist der höchste negative Wert -3, daher wählen wir die Eintrittsvariable x1.
    • Bestimme die Austrittsvariable:Um die Austrittsvariable zu bestimmen, berechnen wir das Verhältnis (RHS/Eintrittswert) für jede Zeile:
      • Für s1 (erste Zeile): \(\frac{4}{2} = 2\)
      • Für s2 (zweite Zeile): \(\frac{3}{1} = 3\)
      Der kleinste Wert ist 2. Daher ist die Austrittsvariable s1.
    • Pivot-Operation:Wir aktualisieren das Tableau, indem wir die Pivot-Operation durchführen. Dazu normalisieren wir die Pivotzeile (erste Zeile) und passen die anderen Zeilen entsprechend an.
    • Normiere die Pivotzeile (erste Zeile):

      x1 wird die neue Basis:

    • Teile die erste Zeile durch den Pivot-Wert 2:
     |Basis   | Cb | x1 | x2 | s1 | s2 |  RHS | |--------|----|----|----|----|----|------| |  x1    | 3  | 1  | 0.5| 0.5| 0  |   2  |
  • Aktualisiere die zweite Zeile (s2), indem du sie anpasst:Neue zweite Zeile = alte zweite Zeile - (1 * neue erste Zeile)
     Alte zweite Zeile = 0 x1 + 1 x2 + 2 x2 + 0 s1 + 1 s2 = 3  Neue zweite Zeile = 0 - 1*1 x1 + 1 x2 - 1*0.5 x2 + 2 x2 - 1*0.5 s1 + 1 - 1*0 s2 = 3 - 1* 2  |Basis   | Cb | x1 | x2 | s1 | s2 |  RHS | |--------|----|----|----|----|----|------| |  x1    | 3  | 1  | 0.5| 0.5| 0  |   2  | |  s2    | 0  | 0  | 1.5| -0.5| 1 | 1  |
  • Aktualisiere die Zielfunktionzeile (Z-Reihe): Neue Z-Reihe = alte Z-Reihe + 3 * neue erste Zeile
       | Z     |    | 0  | -0.5| 1.5| 0 | 6  |
    • Das neue Simplex-Tableau nach der Pivot-Operation:
       |Basis   | Cb | x1 | x2 | s1 | s2 | RHS |  ------------------------------------  |  x1    | 3  | 1  | 0.5 | 0.5| 0  |   2  |  |  s2    | 0  | 0  | 1.5 | -0.5| 1  |  1  |  |  Z     |    | 0  | -0.5| 1.5| 0  |  6  |
      Das neue Tableau zeigt die Aktualisierung nach der Pivot-Operation. Beachte, dass x1 jetzt in der Basis ist und s1 entfernt wurde.

    Aufgabe 4)

    Branch-and-Bound Methode in der ganzzahligen OptimierungBranch-and-Bound (B&B) ist ein Algorithmus zur Lösung von ganzzahligen Optimierungsproblemen, der systematisch den Lösungsraum durch Suchen aufteilt und bewertet.

    • Eingeschränkter Baum (Branch): Der Lösungsraum wird rekursiv in kleinere Teilprobleme gegliedert.
    • Schranken (Bound): Für jedes Teilproblem werden Schranken aufgestellt, um unvorteilhafte Pfade frühzeitig abzubrechen.
    • LP-Relaxation: Oft wird zunächst das entsprechende lineare Programm gelöst, um Bounds zu berechnen.
    • Bounding: Vergleich der aktuellen Lösung mit der besten bekannten ganzzahligen Lösung zur Optimierung.
    • Ausschlusskriterien: Wenn die Schranke eines Teilproblems schlechter als die bisher beste Lösung ist, wird der entsprechende Zweig verworfen.
    • Ziel: Finden der optimalen ganzzahligen Lösung durch effiziente Reduktion des Suchraumes.

    a)

    1. Definiere das Konzept der LP-Relaxation im Kontext des Branch-and-Bound Verfahrens und erkläre, wie es zur Berechnung von Schranken genutzt wird. Unterstütze Deine Antwort mit einem mathematischen Beispiel.

    • Gib die allgemeine Form eines ganzzahligen linearen Optimierungsproblems an.
    • Erläutere, wie die LP-Relaxation aus diesem Problem abgeleitet wird.
    • Beschreibe, wie die Lösung der LP-Relaxation als Schranke für das Branch-and-Bound Verfahren dient, und illustriere dies an einem Beispiel, in dem Du ein einfaches ILP durch LP-Relaxation löst und die Schranken berechnest.

    Lösung:

    1. Definiere das Konzept der LP-Relaxation im Kontext des Branch-and-Bound Verfahrens und erkläre, wie es zur Berechnung von Schranken genutzt wird.

    • Allgemeine Form eines ganzzahligen linearen Optimierungsproblems:Ein typisches ganzzahliges lineares Optimierungsproblem (ILP) kann durch folgendes Modell dargestellt werden:
    • Minimiere\[ c^T x \]
    • Unter den Nebenbedingungen:\[ Ax \leq b \]\[ x \in \mathbb{Z}^n \]
    • Hierbei ist \( c \) ein Vektor von Kostenkoeffizienten, \( A \) eine Matrix von Nebenbedingungskoeffizienten, \( x \) der Lösungsvektor und \( b \) der Vektor der rechten Seiten.
    • LP-Relaxation ableiten:Um die LP-Relaxation eines ILP zu erhalten, entfernt man die Ganzzahligkeitsbeschränkung \( x \in \mathbb{Z}^n \), sodass nur noch die Nebenbedingungen \( Ax \leq b \) und \( x \in \mathbb{R}^n \) gelten. Das resultierende lineare Programm (LP) hat folgende Form:
    • Minimiere\[ c^T x \]
    • Unter den Nebenbedingungen:\[ Ax \leq b \]\[ x \in \mathbb{R}^n \]
    • LP-Relaxation als Schranke im Branch-and-Bound Verfahren:Die Lösung der LP-Relaxation dient als obere Schranke für Minimierungsprobleme, da die Lösung des ursprünglichen ILP nicht kleiner sein kann als die beste Lösung der LP-Relaxation. Diese Schranke wird verwendet, um unnötige Pfade im Branch-and-Bound-Baum abzuschneiden.
    • Mathematisches Beispiel:
    • Betrachte das folgende einfache ILP:
    • Minimiere\[ z = 3x_1 + 4x_2 \]Unter den Nebenbedingungen:\[ 2x_1 + x_2 \leq 4 \]\[ x_1 + 2x_2 \leq 3 \]\[ x_1, x_2 \geq 0 \]\[ x_1, x_2 \in \mathbb{Z} \]
    • Die LP-Relaxation dieses Problems lautet:
    • Minimiere\[ z = 3x_1 + 4x_2 \]Unter den Nebenbedingungen:\[ 2x_1 + x_2 \leq 4 \]\[ x_1 + 2x_2 \leq 3 \]\[ x_1, x_2 \geq 0 \]\[ x_1, x_2 \in \mathbb{R} \]
    • Die Lösung der LP-Relaxation kann durch lineare Programmiertechniken wie den Simplex-Algorithmus bestimmt werden. Angenommen, die optimale Lösung der LP-Relaxation ist \( x_1 = 1, x_2 = 1 \).
    • Der zugehörige Zielfunktionswert beträgt:\[ z = 3(1) + 4(1) = 7 \]
    • Diese Lösung ist keine ganzzahlige Lösung, gibt jedoch eine Schranke von 7 an. Wir verwenden diese Schranke, um Zweige des Baums zu eliminieren.
    • Angenommen, wir finden eine ganzzahlige Lösung, beispielsweise \( x_1 = 2, x_2 = 0 \) mit einem Zielfunktionswert von 6. Da dieser Wert besser als die LP-Relaxation ist, können wir alle Zweige eliminieren, deren Schranken schlechter als 6 sind.
    • Fazit: Die LP-Relaxation hilft beim Setzen von Schranken, die helfen, den Suchbaum zu reduzieren und so die Effizienz des Branch-and-Bound Verfahrens zu steigern.

    b)

    2. Betrachte das folgende ganzzahlige Optimierungsproblem:

    maximiere: z = 3x + 2y
    unter den Nebenbedingungen:
    4x + y ≤ 9
    2x + 3y ≤ 8
    x, y ≥ 0
    x, y ∈ ℤ
    • Zeichne das Machbarkeitsgebiet dieses Problems und erkläre, wie Du die LP-Relaxation löst.
    • Nutze die Branch-and-Bound Methode, um die optimale ganzzahlige Lösung zu finden. Zeige jeden Schritt und erkläre das Ausschlusskriterium zur Reduktion des Suchraumes.

    Lösung:

    2. Betrachte das folgende ganzzahlige Optimierungsproblem:

    maximiere: z = 3x + 2y
    unter den Nebenbedingungen:
    4x + y ≤ 9
    2x + 3y ≤ 8
    x, y ≥ 0
    x, y ∈ ℤ
    • Zeichne das Machbarkeitsgebiet dieses Problems und erkläre, wie Du die LP-Relaxation löst:
    • Um das Machbarkeitsgebiet zu zeichnen, setzen wir erst einmal die Ungleichungen gleich und bestimmen die Schnittpunkte:
    • Gleichung 1: \[ 4x + y = 9 \] - Für \( x = 0 \): \( y = 9 \) (Punkt A = (0,9)) - Für \( y = 0 \): \( x = 2.25 \) (Punkt B = (2.25,0))
    • Gleichung 2: \[ 2x + 3y = 8 \] - Für \( x = 0 \): \( y = 2.67 \) (Punkt C = (0,2.67)) - Für \( y = 0 \): \( x = 4 \) (Punkt D = (4,0))
    • Nun zeichnen wir diese Linien in ein Koordinatensystem und bestimmen das Machbarkeitsgebiet, das durch die Schnittpunkte der Linien und die Achsen begrenzt wird.
    • Die LP-Relaxation entfernt die Ganzzahligkeitsbedingungen, so dass wir die Ungleichungen unter linearen Bedingungen lösen können:
    • LP-Relaxation:Maximieren:\[ z = 3x + 2y \]Unter den Nebenbedingungen:\[ 4x + y \leq 9 \]\[ 2x + 3y \leq 8 \]\[ x, y \geq 0 \]
    • Setze die Ecke des Machbarkeitsgebiets ein, um den optimalen Punkt zu finden. Der Schnittpunkt der beiden Geraden ist durch:
    • Gleichung 1: \[ y = 9 - 4x \]Einsetzen in Gleichung 2: \[ 2x + 3(9 - 4x) = 8 \] \[ 2x + 27 - 12x = 8 \] \[ -10x = -19 \] \[ x = 1.9 \] \[ y = 9 - 4(1.9) = 1.4 \]
    • Maximiere: \[ z = 3(1.9) + 2(1.4) = 9.5 \]
    • Branch-and-Bound Methode:
    • Starte mit dem Relaxationswert: \( x=1.9, y=1.4 \), \( z=9.5 \)
    • Branch: Setze: \( x \leq 1 \) und \( x \geq 2 \)
    • 1. Teilproblem:Für \( x=1 \) lösen:\[ 4(1) + y \leq 9 \]\[ y \leq 5 \]\[ 2(1) + 3y \leq 8 \]\[ 3y \leq 6 \]\[ y \leq 2 \]Maximiere: \( z = 3(1) + 2(y) = 3 + 2y \)Da y eine ganze Zahl ist, sind die möglichen Werte 0, 1 und 2. Der maximale Wert für 2y ergibt sich bei y=2:\( z = 3(1) + 2(2) = 7 \)
    • 2. Teilproblem:Für \( x=2 \) lösen:\[ 4(2) + y \leq 9 \]\[ y \leq 1 \]\[ 2(2) + 3y \leq 8 \]\[ y \leq 0.67 \]Maximiere: \( z = 3(2) + 2(y) = 6 + 2y \)Da y eine ganze Zahl ist, ist der maximale Wert für 2y bei y=0:\( z = 3(2) + 2(0) = 6 \)
    • Da der Wert 7 höher als der Branch-Wert 6 liegt, eliminieren wir den Branch-Wert 6 und die optimale Lösung liegt bei x=1 und y=2:\( z = 3(1) + 2(2) = 7 \)
    • Fazit: Die Branch-and-Bound Methode hilft uns, die optimale ganzzahlige Lösung (x=1, y=2) mit einem Zielfunktionswert (z=7) zu bestimmen, indem sie unvorteilhafte Teilprobleme effektiv wegwirft.

    c)

    3. Diskutiere die Rolle des Bounding im Branch-and-Bound Verfahren. In welchem Fall kann eine Lösung als suboptimal ausgeschlossen werden und wie hilft dies, den Suchraum zu reduzieren?

    • Erkläre die mathematische Bedeutung von oberen und unteren Schranken im Kontext der ganzzahligen Optimierung.
    • Gib ein Beispiel mit einer erklärten Berechnung, wie Bounding zum Ausschluss eines Zweiges führen kann.
    • Diskutiere die Auswirkung von Bounding auf die Effizienz des Branch-and-Bound Algorithmus.

    Lösung:

    3. Diskutiere die Rolle des Bounding im Branch-and-Bound Verfahren. In welchem Fall kann eine Lösung als suboptimal ausgeschlossen werden und wie hilft dies, den Suchraum zu reduzieren?

    • Erkläre die mathematische Bedeutung von oberen und unteren Schranken im Kontext der ganzzahligen Optimierung:
    • Im Kontext der ganzzahligen Optimierung dienen obere und untere Schranken dazu, die Qualität der gefundenen Lösungen zu bewerten und unnötige Berechnungen zu vermeiden:
    • Obere Schranke (Upper Bound): Bei einem Maximierungsproblem ist die obere Schranke der höchste Wert, der durch die LP-Relaxation eines Teilproblems erreicht werden kann. Sie dient dazu, die bestmögliche Lösung innerhalb eines bestimmten Teilbereichs des Lösungsraums abzuschätzen.
    • Untere Schranke (Lower Bound): Dies ist der Wert der besten bisher gefundenen ganzzahligen Lösung. Sie dient als Referenz, um zu entscheiden, ob ein Teilbereich weiter untersucht werden muss oder aufgrund einer schlechteren oberen Schranke verworfen werden kann.
    • Gib ein Beispiel mit einer erklärten Berechnung, wie Bounding zum Ausschluss eines Zweiges führen kann:
    • Betrachte das folgende Maximierungsproblem:
    maximiere: z = 3x + 4y
    unter den Nebenbedingungen:
    x + y ≤ 4
    2x + y ≤ 5
    x, y ≥ 0
    x, y ∈ ℤ
    • Löse die LP-Relaxation:
      • LP-Relaxation:Maximiere:\[ z = 3x + 4y \]Unter den Nebenbedingungen:\[ x + y \leq 4 \]\[ 2x + y \leq 5 \]\[ x, y \geq 0 \]
      • Gelöst mit dem Simplex-Algorithmus ergäbe dies eine Lösung (z.B. \( x = 1.5, y = 2.5 \)), wobei \( z = 3(1.5) + 4(2.5) = 15.5 \). Diese ist unsere obere Schranke.
      • Setzen wir anfangs eine untere Schranke basierend auf einer ganzzahligen Lösung z.B. \( x = 1, y = 2 \), was \( z = 3(1) + 4(2) = 11 \) ergibt.
      • Branch-and-Bound Methode:
      • Branch: Aufteilung in zwei Teilprobleme:
      • Teilproblem 1: Setze \( x \leq 1 \)
        • Führe LP-Relaxation durch. Angenommen, die Lösung ist \( x = 1, y = 3 \), was \( z = 15 \) ergibt. Da \( 15 > 11 \), wird der Zweig weiter verfolgt.
        • Teilproblem 2: Setze \( x \geq 2 \)
          • Führe LP-Relaxation durch. Angenommen, die Lösung ist \( x = 2, y = 1 \), was \( z = 10 \) ergibt. Da \( 10 \leq 11 \), wird dieser Zweig verworfen.
          • Diskutiere die Auswirkung von Bounding auf die Effizienz des Branch-and-Bound Algorithmus:
          • Bounding ist entscheidend für die Effizienz des Branch-and-Bound Algorithmus. Durch das Setzen von Schranken können Teilprobleme, die schlechter sind als die bereits bekannten Lösungen oder die besten möglichen Lösungen ihres Bereichs, ausgeschlossen werden. Dies reduziert den Suchraum signifikant und spart Rechenressourcen.
          • Fazit:Durch das systematische Setzen und Vergleichen von oberen und unteren Schranken können viele unnötige Berechnungen vermieden und so die Effizienz des Branch-and-Bound Verfahrens drastisch gesteigert werden.
    • Sign Up

    Melde dich kostenlos an, um Zugriff auf das vollständige Dokument zu erhalten

    Mit unserer kostenlosen Lernplattform erhältst du Zugang zu Millionen von Dokumenten, Karteikarten und Unterlagen.

    Kostenloses Konto erstellen

    Du hast bereits ein Konto? Anmelden