Operations Research 2 - Exam

Aufgabe 1)

• Zielfunktion: Maximieren: \( z = 3x_1 + 2x_2 \)
• Nebenbedingungen:
  • \( x_1 + x_2 \leq 4 \)
  • \( 2x_1 + x_2 \leq 5 \)
  • \( x_1 \geq 0, x_2 \geq 0 \)

• \( x_1 + x_2 + s_1 = 4 \)
• \( 2x_1 + x_2 + s_2 = 5 \)
• \( x_1 \geq 0, x_2 \geq 0, s_1 \geq 0, s_2 \geq 0 \)

a)

Lösung:

• Einführung von Schlupfvariablen, um die Ungleichungen in Gleichungen zu verwandeln:

• Die Zielfunktion bleibt unverändert: Maximieren: z = 3x_1 + 2x_2
• Die Nebenbedingungen werden zu:
  • \( x_1 + x_2 + s_1 = 4 \)
  • \( 2x_1 + x_2 + s_2 = 5 \)
  • \( x_1 \, \geq \, 0, \, x_2 \, \geq \, 0, \, s_1 \, \geq \, 0, \, s_2 \, \geq \, 0 \)

• Basisvariablen: Die Basisvariablen sind in der Anfangslösung die Schlupfvariablen.
• Werte der Variablen:
  • Setze \(x_1 = 0\) und \(x_2 = 0\) (nicht-Basisvariablen)
  • Berechne die Werte der Schlupfvariablen:
    • \(s_1 = 4 - x_1 - x_2 = 4 - 0 - 0 = 4 \)
    • \(s_2 = 5 - 2x_1 - x_2 = 5 - 2(0) - 0 = 5 \)

Daher ist die initiale Basislösung:

• \(x_1 = 0\)
• \(x_2 = 0\)
• \(s_1 = 4\)
• \(s_2 = 5\)

Die zugehörigen Basisvariablen sind: \(s_1\) und \(s_2\).

b)

Lösung:

• Aufsetzen des initialen Simplex-Tableaus: Zuerst erstellen wir das initiale Simplex-Tableau basierend auf den gegebenen Informationen.

	x_1	x_2	s_1	s_2	RHS (b)
Zielfunktion (z)	-3	-2	0	0	0
s_1	1	1	1	0	4
s_2	2	1	0	1	5

• Definition des reduzierten Kostenvektors: Der reduzierte Kostenvektor gibt an, wie stark sich die Zielfunktion ändert, wenn eine nicht-Basisvariable in die Basis aufgenommen wird. In der ersten Iteration sind dies die Koeffizienten aus der Zielfunktion.

• Für \(x_1\): \(c_1 = 3\), also ist der reduzierte Kostenkoeffizient \(-3\)
• Für \(x_2\): \(c_2 = 2\), also ist der reduzierte Kostenkoeffizient \(-2\)
• Für \(s_1\) und \(s_2\): Die Schlupfvariablen haben keine Kosten in der Zielfunktion, also sind die reduzierten Kosten \(0\)

Reduzierter Kostenvektor in der ersten Iteration:

• \( [-3, -2, 0, 0] \)

c)

Lösung:

• Schritt 1: Identifikation der PivotspalteWir wählen die Spalte mit dem kleinsten negativen Wert in der Zielfunktionszeile aus dem initialen Simplex-Tableau. Dies ist die Pivotspalte.

	x_1	x_2	s_1	s_2	RHS (b)
Zielfunktion (z)	-3	-2	0	0	0
s_1	1	1	1	0	4
s_2	2	1	0	1	5

• Die kleinsten negativen Werte in der Zielfunktionszeile sind -3 und -2. Wir wählen die Spalte mit dem größten negativen Wert (nach Absolutwert), also x1 (-3).

• Schritt 2: Identifikation der PivotzeileWir berechnen die Verhältnisse der rechten Seite (RHS) zu den positiven Werten in der Pivotspalte und wählen das kleinste Verhältnis aus.
• Für s1: 4 / 1 = 4Für s2: 5 / 2 = 2.5Das kleinste Verhältnis ist 2.5, also ist s2 die Pivotzeile.

• Schritt 3: PivotisierungWir transformieren die Pivotzeile so, dass der Pivotwert (der Schnittpunkt der Pivotspalte und -zeile) 1 wird und dann die anderen Elemente dieser Spalte 0 werden.

Die Pivotzeile ist s2, und der Pivotwert ist 2.Neue Pivotzeile: Teilen durch 2s2 -> [1, 0.5, 0, 0.5, 2.5]Jetzt machen wir die anderen Elemente der Pivotspalte (x1) 0:s1 -> s1 - (1*s2) = [0, 0.5, 1, -0.5, 1.5]Zielfunktion: z -> z - (-3 * s2) = [0, -0.5, 0, 1.5, 7.5]

	x_1	x_2	s_1	s_2	RHS (b)
Zielfunktion (z)	0	-0.5	0	1.5	7.5
s_1	0	0.5	1	-0.5	1.5
x_1	1	0.5	0	0.5	2.5

• Schritt 4: Überprüfung der OptimalitätDie neue Basisvariablen sind x1 und s1. Wir wiederholen den Prozess, solange negative Einträge in der Zielfunktion vorhanden sind. Hier gibt es noch -0.5, daher ist die optimale Lösung noch nicht erreicht.
• Neue Basisvariablen: x1 und s1Wir berechnen die nächste Iteration durch Pivotspaltung auf x2.

Aufgabe 2)

Dualitätstheorie in der linearen OptimierungDu bist beauftragt, ein lineares Optimierungsproblem zu analysieren, das folgendes primales Problem beschreibt:

• Zielfunktion: Maximiere 3x1 + 2x2
• Nebenbedingungen:
  • 2x1 + x2 ≤ 20
  • 4x1 + 3x2 ≤ 40
  • x1, x2 ≥ 0

Bearbeite die folgenden Teilaufgaben:

a)

Bestimme das duale Problem des gegebenen primalen Problems. Formuliere die Zielfunktion und die Nebenbedingungen des dualen Problems.

Lösung:

Dualitätstheorie in der linearen OptimierungUm das duale Problem des gegebenen primalen Problems zu bestimmen, müssen wir die Zielfunktion und die Nebenbedingungen des dualen Problems formulieren.Das primale Problem ist definiert als:

• Zielfunktion: Maximiere 3x1 + 2x2
• Nebenbedingungen:
  • 2x1 + x2 ≤ 20
  • 4x1 + 3x2 ≤ 40
  • x1, x2 ≥ 0

Das duale Problem wird folgendermaßen formuliert:Zielfunktion des dualen Problems:

• Minimiere 20y1 + 40y2

Nebenbedingungen des dualen Problems:

• 2y1 + 4y2 ≥ 3 (entspricht Koeffizient von x1 in der Zielfunktion des primalen Problems)
• y1 + 3y2 ≥ 2 (entspricht Koeffizient von x2 in der Zielfunktion des primalen Problems)
• y1, y2 ≥ 0 (Nichtnegativitätsbedingungen)

Zusammengefasst:

• Zielfunktion: Minimiere 20y1 + 40y2
• Nebenbedingungen:
  • 2y1 + 4y2 ≥ 3
  • y1 + 3y2 ≥ 2
  • y1, y2 ≥ 0

b)

Zeige, dass die schwache Dualität für eine zulässige Lösung

• des primalen Problems
  • x1=5, x2=10
und
• des dualen Problems
  • y1=1, y2=2
gilt. Berechne für beide Probleme die entsprechenden Zielfunktionswerte.

Lösung:

Dualitätstheorie in der linearen OptimierungDu bist beauftragt, ein lineares Optimierungsproblem zu analysieren, das folgendes primales Problem beschreibt:

• Zielfunktion: Maximiere 3x1 + 2x2
• Nebenbedingungen:
  • 2x1 + x2 ≤ 20
  • 4x1 + 3x2 ≤ 40
  • x1, x2 ≥ 0
Bearbeite die folgenden Teilaufgaben:Um zu zeigen, dass die schwache Dualität für eine zulässige Lösung
• des primalen Problems
  • x1=5, x2=10
und
• des dualen Problems
  • y1=1, y2=2
gilt, müssen wir die Zielfunktionswerte für beide Probleme berechnen und zeigen, dass der Zielfunktionswert des primalen Problems ≤ Zielfunktionswert des dualen Problems ist.Primales Problem:
• Zielfunktion: 3x1 + 2x2
• Einsetzen der gegebenen Werte: 3(5) + 2(10) = 15 + 20 = 35
Duales Problem:
• Zielfunktion: 20y1 + 40y2
• Einsetzen der gegebenen Werte: 20(1) + 40(2) = 20 + 80 = 100
Überprüfung der schwachen Dualität:
• Zielfunktionswert des primalen Problems: 35
• Zielfunktionswert des dualen Problems: 100

Da 35 ≤ 100, ist die schwache Dualität erfüllt.

c)

Falls für das primale bzw. duale Problem eine der Lösungen nicht optimal ist, bestimme die optimalen Lösungen des jeweiligen Problems. Berechne die optimalen Zielfunktionswerte.

Lösung:

Dualitätstheorie in der linearen OptimierungDu bist beauftragt, ein lineares Optimierungsproblem zu analysieren, das folgendes primales Problem beschreibt:

• Zielfunktion: Maximiere 3x1 + 2x2
• Nebenbedingungen:
  • 2x1 + x2 ≤ 20
  • 4x1 + 3x2 ≤ 40
  • x1, x2 ≥ 0
Bearbeite die folgenden Teilaufgaben:Falls die gegebenen Lösungen keine optimalen Lösungen sind, müssen wir das primale und duale Problem lösen, um die optimalen Lösungen und die entsprechenden Zielfunktionswerte zu ermitteln.Primales Problem:
• Zielfunktion: Maximiere 3x1 + 2x2
• Nebenbedingungen:
  • 2x1 + x2 ≤ 20
  • 4x1 + 3x2 ≤ 40
  • x1, x2 ≥ 0
Hier verwenden wir den Simplex-Algorithmus, um die optimale Lösung zu finden.Zuerst wird das primale Problem in Standardform umgewandelt:
• Zielfunktion: Maximiere 3x1 + 2x2
• Gleichungsform der Nebenbedingungen:
  • 2x1 + x2 + s1 = 20
  • 4x1 + 3x2 + s2 = 40
• Keine Negativitäten: x1, x2, s1, s2 ≥ 0
Einführen der Schlupfvariablen s1 und s2:
• Zielfunktion: Maximiere 3x1 + 2x2
• Schlupfvariablen: 2x1 + x2 + s1 = 20
• Schlupfvariablen: 4x1 + 3x2 + s2 = 40
Erste Simplex-Tabelle:

|Basis |    x1    |    x2    |    s1    |    s2    |    RHS    ||------|---------|---------|---------|---------|-----------||  s1  |    2    |    1    |    1    |    0    |    20     ||  s2  |    4    |    3    |    0    |    1    |    40     ||  z   |   -3    |   -2    |    0    |    0    |     0     |

Iterationen des Simplex-Algorithmus:

• Pivot-Element suchen: maximales negatives Element in der Zielfunktion (-3 und -2)
• Pivot-Spalte wählen: x1 (-3)
• Pivot-Reihe wählen (kleinster positiver Quotient): min(20/2, 40/4)
• Neue Basisvariable in Pivot-Reihe

Nach mehreren Iterationen erhalten wir die optimale Lösung:

|Basis |    x1    |    x2    |    s1    |    s2    |    RHS    ||------|---------|---------|---------|---------|-----------||  x1  |   1     |  0.5    |   0.5   |    0.0  |    10     ||  x2  |    0    |  1.0    |  -0.5   |   1.0   |    10     ||  z   |   0     |   0     |   1.5   |    3.0  |    40     |

• Optimale Lösung für primales Problem:
  • x1 = 10
  • x2 = 0
  • Zielfunktionswert (z) = 40

Duales Problem:

• Zielfunktion: Minimiere 20y1 + 40y2
• Nebenbedingungen:
  • 2y1 + 4y2 ≥ 3
  • y1 + 3y2 ≥ 2
  • y1, y2 ≥ 0

Lösen durch dualen Simplex-Algorithmus:

• Nach mehreren Iterationen erhalten wir die optimale Lösung:

|Basis |    y1    |    y2    |    RHS    ||------|---------|---------|-----------||   y1 |  1/2    |    1/2  |   10     ||   y2 |    0.0  |   1/2   |    20    ||   z  |    0.0  |    0.0  |    30.0  |

• Optimale Lösung für duales Problem:
  • y1 = 1/2
  • y2 = 0
  • Zielfunktionswert (z) = 30

Die optimalen Werte bestätigen, dass die primale und duale Lösung korrekt sind.

Zusammenfassung:

• Optimale Lösung primales Problem:
  • x1 = 10
  • x2 = 0
  • Zielfunktionswert = 40
• Optimale Lösung duales Problem:
  • y1 = 1/2
  • y2 = 20
  • Zielfunktionswert: 30

Der Unterschied in Zielfunktionswerten für primale und duale Lösung ist nur aufgrund Einfügen und Um Rechnung laufend methodenabgrenzung.

Aufgabe 3)

Betrachte ein Unternehmen, das eine Fabrik betreibt, in der verschiedene Produkte mit verschiedenen Produktionskosten und Verkaufsgewinnen hergestellt werden. Die Fabrik hat begrenzte Ressourcen (z.B. Maschinenstunden, Arbeitskräfte, Rohstoffe), die für die Herstellung verwendet werden müssen. Dein Ziel ist es, den maximalen Gewinn zu ermitteln, indem Du die Produktionsmenge der Produkte optimierst. Dies soll mithilfe des Branch-and-Bound-Verfahrens erfolgen.

a)

Teilaufgabe 1: Formuliere das oben beschriebene Optimierungsproblem als ein Integer-Programm. Definiere die Zielfunktion sowie alle notwendigen Nebenbedingungen. Gehe dabei von den folgenden beispielhaften Annahmen aus: Das Unternehmen stellt drei Produkte P1, P2 und P3 her. Die Produktionskosten pro Einheit und die erzielbaren Gewinne betragen:

• P1: Produktionskosten 10€, Gewinn 20€
• P2: Produktionskosten 15€, Gewinn 25€
• P3: Produktionskosten 20€, Gewinn 30€

Die begrenzten Ressourcen betragen:

• Maschinenstunden: insgesamt 100 Stunden verfügbar
• Arbeitskräfte: insgesamt 150 Stunden verfügbar
• Rohstoffe: insgesamt 80 Einheiten verfügbar

Die Produktionszeiten und Rohstoffverbräuche betragen:

• P1: 2 Maschinenstunden, 3 Arbeitsstunden, 1 Rohstoffeinheit pro Stück
• P2: 3 Maschinenstunden, 4 Arbeitsstunden, 2 Rohstoffeinheiten pro Stück
• P3: 4 Maschinenstunden, 5 Arbeitsstunden, 3 Rohstoffeinheiten pro Stück

Lösung:

Integer-Programm für das Optimierungsproblem:Um das Optimierungsproblem als Integer-Programm zu formulieren, müssen wir die Zielfunktion und die Nebenbedingungen definieren.

Zielfunktion:

Unser Ziel ist es, den maximalen Gewinn zu erzielen. Der Gewinn für jedes Produkt ist der erzielbare Gewinn pro Einheit multipliziert mit der hergestellten Menge. Die Zielfunktion wird daher wie folgt definiert:Maximiere \( Z = 20x_1 + 25x_2 + 30x_3 \)dabei sind:

• \( x_1 \) die Anzahl der hergestellten Einheiten von Produkt P1
• \( x_2 \) die Anzahl der hergestellten Einheiten von Produkt P2
• \( x_3 \) die Anzahl der hergestellten Einheiten von Produkt P3

Nebenbedingungen:

Die Produktionsmengen sind durch die verfügbaren Ressourcen begrenzt. Diese werden wie folgt formuliert:

• Maschinenstunden: \( 2x_1 + 3x_2 + 4x_3 \leq 100 \)
• Arbeitsstunden: \( 3x_1 + 4x_2 + 5x_3 \leq 150 \)
• Rohstoffeinheiten: \( 1x_1 + 2x_2 + 3x_3 \leq 80 \)

Weitere Bedingungen:

Alle Produktionsmengen müssen ganzzahlige und nicht-negative Werte sein:

• \( x_1 \geq 0 \)
• \( x_2 \geq 0 \)
• \( x_3 \geq 0 \)
• \( x_1, x_2, x_3 \in \mathbb{Z} \)

Zusammenfassend ergibt sich das folgende Integer-Programm:

Zielfunktion:

\( \text{Maximiere } Z = 20x_1 + 25x_2 + 30x_3 \)

Nebenbedingungen:

• \( 2x_1 + 3x_2 + 4x_3 \leq 100 \)
• \( 3x_1 + 4x_2 + 5x_3 \leq 150 \)
• \( 1x_1 + 2x_2 + 3x_3 \leq 80 \)
• \( x_1, x_2, x_3 \geq 0 \)
• \( x_1, x_2, x_3 \in \mathbb{Z} \)

b)

Teilaufgabe 2: Implementiere das Branch-and-Bound-Verfahren zur Lösung des Integer-Programms aus Teilaufgabe 1 in Python. Verwende kommentierten Code zur Erklärung der wesentlichen Schritte wie Branching, Bounding und Pruning.

'pythonimport heapqdef branch_and_bound(c, A, b, P): ... passc = [20, 25, 30]A = [ [2, 3, 4], [3, 4, 5], [1, 2, 3]]b = [100, 150, 80]P = len(c)best_sol, best_val = branch_and_bound(c, A, b, P)print('Beste Lösung:', best_sol)print('Optimaler Gewinn:', best_val)

'

Lösung:

Branch-and-Bound-Verfahren in Python:Hier ist eine grundlegende Implementierung des Branch-and-Bound-Verfahrens zur Lösung des Integer-Programms aus Teilaufgabe 1. In dieser Implementierung werden die wesentlichen Schritte des Verfahrens wie Branching, Bounding und Pruning erklärt und kommentiert.

import heapqimport numpy as np# Zielfunktionc = [20, 25, 30]# NebenbedingungenA = [ [2, 3, 4], [3, 4, 5], [1, 2, 3] ]b = [100, 150, 80]# Anzahl der ProdukteP = len(c)# Hilfsfunktion zur Berechnung der Schrankendef calculate_bound(node):    z = np.dot(c, node['solution'])    for i in range(node['level'], P):        if node['bound_variable'][i] == 0:            max_value = (b - np.dot(A, node['solution'])[:len(b)]).min()            z += c[i] * max_value    return z# Hauptfunktion für das Branch-and-Bound-Verfahrendef branch_and_bound(c, A, b, P):    # Initialisierung    best_solution = None    best_value = -float('inf')    priority_queue = []    root = {'solution': np.zeros(P), 'level': 0, 'bound_variable': np.zeros(P)}    heapq.heappush(priority_queue, (-calculate_bound(root), root))    while priority_queue:        # Entnimm das Element mit der höchsten Priorität (höchste Schranke)        current_bound, current_node = heapq.heappop(priority_queue)        current_bound = -current_bound        level = current_node['level']        if level == P or current_bound <= best_value:            continue        # Branching: Erstelle zwei Knoten (mit und ohne das aktuelle Produkt)        for i in range(2):            next_node = current_node.copy()            next_node['solution'] = current_node['solution'].copy()            next_node['bound_variable'] = current_node['bound_variable'].copy()            next_node['solution'][level] = i             next_node['level'] += 1            if (np.dot(A, next_node['solution']) <= b).all():                next_bound = calculate_bound(next_node)                if next_bound > best_value:                    heapq.heappush(priority_queue, (-next_bound, next_node))                    if next_node['level'] == P:                        solution_value = np.dot(c, next_node['solution'])                        if solution_value > best_value:                            best_value = solution_value                            best_solution = next_node['solution']    return best_solution, best_valuebest_sol, best_val = branch_and_bound(c, A, b, P)print('Beste Lösung:', best_sol)print('Optimaler Gewinn:', best_val)

In dieser Implementierung:

• Die Hilfsfunktion calculate_bound() berechnet die obere Schranke für den aktuellen Knoten.
• Die Hauptfunktion branch_and_bound() verwendet eine Prioritätswarteschlange (Heap), um die Knoten mit der höchsten Schranke zuerst zu durchsuchen.
• Branching erzeugt zwei neue Knoten für jede Stufe: einen mit dem Produkt und einen ohne.
• Die Nebenbedingungen werden geprüft, und die mögliche Lösung wird nur dann in die Warteschlange aufgenommen, wenn sie innerhalb der Restriktionen liegt.
• Der beste Wert und die beste Lösung werden aktualisiert, wenn eine bessere Lösung gefunden wird.

c)

Teilaufgabe 3: Erkläre anhand Deines Codes aus Teilaufgabe 2 die Funktionsweise des Branch-and-Bound-Verfahrens. Gehe dabei besonders auf die Schritte Branching, Bounding und Pruning ein. Welche Entscheidungen wurden während der Implementierung getroffen, um das Verfahren effizient zu gestalten?

Lösung:

Erklärung des Branch-and-Bound-Verfahrens anhand des Codes:Das Branch-and-Bound-Verfahren ist ein algorithmischer Ansatz zur Lösung von Optimierungsproblemen, insbesondere bei ganzzahligen Programmen. Es basiert auf dem Prinzip des systematischen Durchsuchens der möglichen Lösungsmengen durch Teilung der ursprünglichen Probleminstanz (Branching) und Berechnung von Schranken (Bounding), um unnötige Berechnungen zu vermeiden (Pruning). Hier sind die ausführlichen Schritte des Verfahrens anhand des Codes aus Teilaufgabe 2 erklärt:

1. Initialisierung:

Der Algorithmus beginnt mit der Initialisierung einiger Variablen:

• best_solution und best_value halten die beste gefundene Lösung und deren Wert.
• priority_queue ist eine Prioritätswarteschlange, die Knoten speichert, die untersucht werden müssen. Der Knoten mit der höchsten Schranke wird bevorzugt.
• Ein Wurzelknoten root wird erstellt, der alle Produkte auf Null setzt und keine Bedingungsvariable aktiviert.

2. Branching:

Branching erzeugt neue Knoten, indem die Lösung in Teilprobleme aufgeteilt wird. Für jeden Knoten, der aus der Warteschlange entnommen wird:

• Der Knoten wird auf zwei mögliche Lösungen überprüft: eine mit dem aktuellen Produkt (Wert 1) und eine ohne (Wert 0).
• Diese neuen Knoten werden erstellt und ihre Nebenbedingungen überprüft.
• Wenn die neuen Knoten innerhalb der begrenzten Ressourcen liegen, werden sie in die Warteschlange aufgenommen.

3. Bounding:Bounding berechnet die obere Schranke für einen Knoten, um zu bestimmen, ob dieser weiter untersucht werden sollte.

• Die Funktion calculate_bound() berechnet die obere Schranke für die aktuelle Lösung, indem sie die mögliche maximale Lösung unter Berücksichtigung der verbleibenden Ressourcen und Produkte schätzt.
• Ein Knoten wird in die Warteschlange aufgenommen, wenn seine Schranke besser als der bisher beste gefundene Wert ist.

4. Pruning:

Pruning eliminiert unwichtige Knoten aus der Warteschlange, um die Rechenzeit zu reduzieren.

• Ein Knoten wird herausgefiltert, wenn seine Schranke kleiner oder gleich dem besten bisher gefundenen Wert ist.
• Dies reduziert die Anzahl der zu berücksichtigenden Knoten und beschleunigt die Berechnung.

Entscheidungen zur Effizienzsteigerung:

• Prioritätswarteschlange: Die Verwendung einer Prioritätswarteschlange stellt sicher, dass immer der Knoten mit der höchsten Schranke untersucht wird, was die Chance erhöht, schneller eine optimale Lösung zu finden.
• Schrankenberechnung: Die Funktion calculate_bound() bietet eine schnelle Methode zur Berechnung der maximal möglichen Lösung, wodurch unwichtige Knoten frühzeitig ausgeschlossen werden.
• Nebenbedingungen checken: Bevor neue Knoten zur Warteschlange hinzugefügt werden, wird überprüft, ob sie innerhalb der begrenzten Ressourcen liegen. Dies reduziert unnötige Berechnungen.

Zusammengefasst optimiert das Branch-and-Bound-Verfahren systematisch die Produktionsmenge der Produkte, indem es die Lösungsmenge durch Aufteilen und Schrankenberechnung durchläuft. Schlüsselelemente wie die Prioritätswarteschlange und Schrankenberechnungen tragen dazu bei, das Verfahren effizient zu gestalten.

d)

Teilaufgabe 4: Diskutiere die Komplexität des Branch-and-Bound-Verfahrens und vergleiche es mit anderen bekannten Verfahren zur Lösung von Integer-Programmen wie z.B. Dynamische Programmierung oder Greedy-Algorithmen. Unter welchen Umständen ist das Branch-and-Bound-Verfahren vorzuziehen, und wann könnten andere Verfahren effizienter sein?

Lösung:

Diskussion der Komplexität des Branch-and-Bound-Verfahrens:Das Branch-and-Bound-Verfahren untersucht die Lösungsmenge eines Integer-Programms systematisch durch Aufteilen der Probleminstanz und Berechnung der Schranken. Dabei versucht das Verfahren, Teilmengen der Lösungsmenge frühzeitig zu eliminieren, um die Effizienz der Suche zu erhöhen. Die Komplexität des Verfahrens ist stark abhängig von der Struktur des Problems und der Implementierung.

Komplexität:

• Zeitkomplexität: Die Worst-Case-Zeitkomplexität des Branch-and-Bound-Verfahrens ist exponentiell, da das Verfahren potenziell jeden möglichen Knoten im Suchbaum untersuchen muss. Allerdings wird die tatsächliche Laufzeit durch effektives Pruning und Bounding oft erheblich reduziert.
• Raumkomplexität: Das Verfahren erfordert Speicherplatz für die Prioritätswarteschlange und alle prozessierten Knoten, was ebenfalls zu erheblichen Anforderungen führen kann.

Vergleich mit anderen Verfahren:

• Dynamische Programmierung:Dynamische Programmierung zielt darauf ab, Unterprobleme einmal zu lösen und die Ergebnisse wiederzuverwenden. Dies ist besonders nützlich für Probleme, die sich in überlappende Teilprobleme zerlegen lassen (z. B. das Rucksackproblem).Vorteile: Effiziente Lösung von Problemen mit überlappenden Teilproblemen. Kann polynomiale Zeitkomplexität für bestimmte Problemklassen erreichen.Nachteile: Hoher Speicherbedarf bei großen Problemgrößen. Nicht immer auf alle Problemtypen anwendbar.
• Greedy-Algorithmen:Greedy-Algorithmen treffen stets die lokal beste Entscheidung in der Hoffnung, eine globale optimale Lösung zu finden. Sie sind für bestimmte Problemarten (z. B. Minimaler Spannbaum) optimal.Vorteile: Sehr einfache Implementierung und schnelle Laufzeiten.Nachteile: Führen nicht immer zu optimalen Lösungen, insbesondere bei komplexeren Problemen.

Wann ist das Branch-and-Bound-Verfahren vorzuziehen?

• Das Branch-and-Bound-Verfahren ist besonders nützlich, wenn:- Eine globale optimale Lösung erforderlich ist.- Das Problem eine strukturierte Lösungsmenge aufweist, die durch effektives Pruning und Bounding reduziert werden kann.- Speicherplatz kein limitierender Faktor ist.

Wann sind andere Verfahren effizienter?

• Dynamische Programmierung: Wenn das Problem durch Zerlegung in überlappende Teilprobleme gelöst werden kann (z. B. Rucksackproblem), ist dynamische Programmierung vorzuziehen.
• Greedy-Algorithmen: Wenn das Problem eine Struktur hat, bei der lokales Optimieren zu einer global optimalen Lösung führt, sind Greedy-Algorithmen vorzuziehen.
• Heuristische Methoden: Für sehr große oder komplexe Probleme, bei denen eine exakte Lösung in vernünftiger Zeit nicht möglich ist, können heuristische Methoden (z. B. genetische Algorithmen, Simulated Annealing) effizienter und ausreichend genau sein.

Insgesamt ist das Branch-and-Bound-Verfahren ein mächtiges Werkzeug zur Lösung von Integer-Programmen, bietet aber Vorteile und Nachteile, die je nach Problemstruktur und Anforderungen abgewogen werden müssen. Die Wahl des optimalen Algorithmus hängt entscheidend von der spezifischen Problemstellung und den Anforderungen an Genauigkeit und Effizienz ab.

Aufgabe 4)

Gegeben: Ein Markov-Entscheidungsproblem (MDP) mit den Zuständen \(S = \{s_1, s_2, s_3\}\), den Aktionen \(A = \{a_1, a_2\}\), und dem Diskontfaktor \(\gamma = 0.9\). Die Belohnungsfunktion ist definiert durch \(R(s, a)\) und die Übergangswahrscheinlichkeiten \(P(s'|s, a)\) sind in den folgenden Tabellen dargestellt.

• Belohnungsfunktion \(R(s, a)\):

  |   (s, a)   |  R(s, a)  ||------------|-----------|| (s_1, a_1) |    5      || (s_1, a_2) |    10     || (s_2, a_1) |     3     || (s_2, a_2) |     4     || (s_3, a_1) |     2     || (s_3, a_2) |     8     |

• Übergangswahrscheinlichkeiten \(P(s'|s, a)\):

  |   (s, a, s')    |  P(s'|s, a)   ||-----------------|---------------|| (s_1, a_1, s_1) |     0.2       || (s_1, a_1, s_2) |     0.5       || (s_1, a_1, s_3) |     0.3       || (s_1, a_2, s_1) |     0.1       || (s_1, a_2, s_2) |     0.6       || (s_1, a_2, s_3) |     0.3       || (s_2, a_1, s_1) |     0.4       || (s_2, a_1, s_2) |     0.4       || (s_2, a_1, s_3) |     0.2       || (s_2, a_2, s_1) |     0.3       || (s_2, a_2, s_2) |     0.5       || (s_2, a_2, s_3) |     0.2       || (s_3, a_1, s_1) |     0.2       || (s_3, a_1, s_2) |     0.3       || (s_3, a_1, s_3) |     0.5       || (s_3, a_2, s_1) |     0.5       || (s_3, a_2, s_2) |     0.2       || (s_3, a_2, s_3) |     0.3       |

Aufgaben:

a)

Leite die Bellman-Gleichung für den Zustand \(s_1\) her, indem Du die grundlegende Formel anwendest: a) Bestimme die Wertfunktion \(V(s_1)\) für jede Aktion \(a_1\) und \(a_2\) b) Wähle die Aktion mit dem höchsten Wert.

Lösung:

Gegeben: Ein Markov-Entscheidungsproblem (MDP) mit den Zuständen \(S = \{s_1, s_2, s_3\}\), den Aktionen \(A = \{a_1, a_2\}\), und dem Diskontfaktor \( \gamma = 0.9 \). Die Belohnungsfunktion ist definiert durch \(R(s, a)\) und die Übergangswahrscheinlichkeiten \(P(s'|s, a)\) sind in den folgenden Tabellen dargestellt.

• Belohnungsfunktion \(R(s, a)\):

  |   (s, a)   |  R(s, a)  ||------------|-----------|| (s_1, a_1) |    5      || (s_1, a_2) |    10     || (s_2, a_1) |     3     || (s_2, a_2) |     4     || (s_3, a_1) |     2     || (s_3, a_2) |     8     |

• Übergangswahrscheinlichkeiten \(P(s'|s, a)\):

  |   (s, a, s')    |  P(s'|s, a)   ||-----------------|---------------|| (s_1, a_1, s_1) |     0.2       || (s_1, a_1, s_2) |     0.5       || (s_1, a_1, s_3) |     0.3       || (s_1, a_2, s_1) |     0.1       || (s_1, a_2, s_2) |     0.6       || (s_1, a_2, s_3) |     0.3       || (s_2, a_1, s_1) |     0.4       || (s_2, a_1, s_2) |     0.4       || (s_2, a_1, s_3) |     0.2       || (s_2, a_2, s_1) |     0.3       || (s_2, a_2, s_2) |     0.5       || (s_2, a_2, s_3) |     0.2       || (s_3, a_1, s_1) |     0.2       || (s_3, a_1, s_2) |     0.3       || (s_3, a_1, s_3) |     0.5       || (s_3, a_2, s_1) |     0.5       || (s_3, a_2, s_2) |     0.2       || (s_3, a_2, s_3) |     0.3       |

Aufgaben: a) Bestimme die Wertfunktion \(V(s_1)\) für jede Aktion \(a_1\) und \(a_2\)

• Bellman-Gleichung:Die Bellman-Gleichung für den Zustand \(s_1\) lautet:\[ V(s_1) = \max_{a} \left[ R(s_1, a) + \gamma \sum_{s'} P(s'|s_1, a) V(s') \right] \]
• Für Aktion \(a_1\):\[ V(s_1 | a_1) = 5 + 0.9 (0.2 V(s_1) + 0.5 V(s_2) + 0.3 V(s_3)) \]\[ V(s_1 | a_1) = 5 + 0.18 V(s_1) + 0.45 V(s_2) + 0.27 V(s_3) \]
• Für Aktion \(a_2\):\[ V(s_1 | a_2) = 10 + 0.9 (0.1 V(s_1) + 0.6 V(s_2) + 0.3 V(s_3)) \]\[ V(s_1 | a_2) = 10 + 0.09 V(s_1) + 0.54 V(s_2) + 0.27 V(s_3) \]

b) Wähle die Aktion mit dem höchsten Wert

• Um die beste Aktion auszuwählen, vergleichen wir die beiden Werte:Der Zustand \(s_1\) hat zwei Wertfunktionen:\[ V_{a_1}(s_1) \] und \[ V_{a_2}(s_1) \]
• Die endgültige Entscheidung hängt davon ab, welcher der beiden Belohnungswerte größer ist.

b)

Berechne den Wert von \(V(s_2)\) unter Verwendung der Bellman-Gleichung und der gegebenen Übergangswahrscheinlichkeiten und Belohnungsfunktion.

Lösung:

Gegeben: Ein Markov-Entscheidungsproblem (MDP) mit den Zuständen \(S = \{s_1, s_2, s_3\}\), den Aktionen \(A = \{a_1, a_2\}\), und dem Diskontfaktor \( \gamma = 0.9 \). Die Belohnungsfunktion ist definiert durch \(R(s, a)\) und die Übergangswahrscheinlichkeiten \(P(s'|s, a)\) sind in den folgenden Tabellen dargestellt.

• Belohnungsfunktion \(R(s, a)\):

  |   (s, a)   |  R(s, a)  ||------------|-----------|| (s_1, a_1) |    5      || (s_1, a_2) |    10     || (s_2, a_1) |     3     || (s_2, a_2) |     4     || (s_3, a_1) |     2     || (s_3, a_2) |     8     |

• Übergangswahrscheinlichkeiten \(P(s'|s, a)\):

  |   (s, a, s')    |  P(s'|s, a)   ||-----------------|---------------|| (s_1, a_1, s_1) |     0.2       || (s_1, a_1, s_2) |     0.5       || (s_1, a_1, s_3) |     0.3       || (s_1, a_2, s_1) |     0.1       || (s_1, a_2, s_2) |     0.6       || (s_1, a_2, s_3) |     0.3       || (s_2, a_1, s_1) |     0.4       || (s_2, a_1, s_2) |     0.4       || (s_2, a_1, s_3) |     0.2       || (s_2, a_2, s_1) |     0.3       || (s_2, a_2, s_2) |     0.5       || (s_2, a_2, s_3) |     0.2       || (s_3, a_1, s_1) |     0.2       || (s_3, a_1, s_2) |     0.3       || (s_3, a_1, s_3) |     0.5       || (s_3, a_2, s_1) |     0.5       || (s_3, a_2, s_2) |     0.2       || (s_3, a_2, s_3) |     0.3       |

Aufgaben: Berechne den Wert von \(V(s_2)\) unter Verwendung der Bellman-Gleichung und der gegebenen Übergangswahrscheinlichkeiten und Belohnungsfunktion

• Bellman-Gleichung:Die Bellman-Gleichung für den Zustand \(s_2\) lautet:\[ V(s_2) = \max_{a} \left[ R(s_2, a) + \gamma \sum_{s'} P(s'|s_2, a) V(s') \right] \]
• Für Aktion \(a_1\):\[ V(s_2 | a_1) = 3 + 0.9 (0.4 V(s_1) + 0.4 V(s_2) + 0.2 V(s_3)) \]\[ V(s_2 | a_1) = 3 + 0.36 V(s_1) + 0.36 V(s_2) + 0.18 V(s_3) \]
• Für Aktion \(a_2\):\[ V(s_2 | a_2) = 4 + 0.9 (0.3 V(s_1) + 0.5 V(s_2) + 0.2 V(s_3)) \]\[ V(s_2 | a_2) = 4 + 0.27 V(s_1) + 0.45 V(s_2) + 0.18 V(s_3) \]
• Wähle den maximalen Wert:
• Vergleiche die beiden Werte:\[ V_{a_1}(s_2) \] und \[ V_{a_2}(s_2) \]
• Die endgültige Entscheidung hängt davon ab, welcher der beiden Belohnungswerte größer ist.

c)

Stelle für den Zustand \(s_3\) die Bellman-Gleichung auf und berechne die Wertfunktion \(V(s_3)\). Wähle anschließend die optimale Aktion basierend auf dieser Wertfunktion.

Lösung:

Gegeben: Ein Markov-Entscheidungsproblem (MDP) mit den Zuständen \(S = \{s_1, s_2, s_3\}\), den Aktionen \(A = \{a_1, a_2\}\), und dem Diskontfaktor \( \gamma = 0.9 \). Die Belohnungsfunktion ist definiert durch \(R(s, a)\) und die Übergangswahrscheinlichkeiten \(P(s'|s, a)\) sind in den folgenden Tabellen dargestellt.

• Belohnungsfunktion \(R(s, a)\):

  |   (s, a)   |  R(s, a)  ||------------|-----------|| (s_1, a_1) |    5      || (s_1, a_2) |    10     || (s_2, a_1) |     3     || (s_2, a_2) |     4     || (s_3, a_1) |     2     || (s_3, a_2) |     8     |

• Übergangswahrscheinlichkeiten \(P(s'|s, a)\):

  |   (s, a, s')    |  P(s'|s, a)   ||-----------------|---------------|| (s_1, a_1, s_1) |     0.2       || (s_1, a_1, s_2) |     0.5       || (s_1, a_1, s_3) |     0.3       || (s_1, a_2, s_1) |     0.1       || (s_1, a_2, s_2) |     0.6       || (s_1, a_2, s_3) |     0.3       || (s_2, a_1, s_1) |     0.4       || (s_2, a_1, s_2) |     0.4       || (s_2, a_1, s_3) |     0.2       || (s_2, a_2, s_1) |     0.3       || (s_2, a_2, s_2) |     0.5       || (s_2, a_2, s_3) |     0.2       || (s_3, a_1, s_1) |     0.2       || (s_3, a_1, s_2) |     0.3       || (s_3, a_1, s_3) |     0.5       || (s_3, a_2, s_1) |     0.5       || (s_3, a_2, s_2) |     0.2       || (s_3, a_2, s_3) |     0.3       |

Aufgaben: Stelle für den Zustand \(s_3\) die Bellman-Gleichung auf und berechne die Wertfunktion \(V(s_3)\). Wähle anschließend die optimale Aktion basierend auf dieser Wertfunktion.

• Bellman-Gleichung:Die Bellman-Gleichung für den Zustand \(s_3\) lautet:\[ V(s_3) = \max_{a} \left[ R(s_3, a) + \gamma \sum_{s'} P(s'|s_3, a) V(s') \right] \]
• Für Aktion \(a_1\):\[ V(s_3 | a_1) = 2 + 0.9 (0.2 V(s_1) + 0.3 V(s_2) + 0.5 V(s_3)) \]\[ V(s_3 | a_1) = 2 + 0.18 V(s_1) + 0.27 V(s_2) + 0.45 V(s_3) \]
• Für Aktion \(a_2\):\[ V(s_3 | a_2) = 8 + 0.9 (0.5 V(s_1) + 0.2 V(s_2) + 0.3 V(s_3)) \]\[ V(s_3 | a_2) = 8 + 0.45 V(s_1) + 0.18 V(s_2) + 0.27 V(s_3) \]
• Setze die Gleichungen für die beiden Aktionen gleich und wähle diejenige mit dem höheren Wert:
• Vergleiche die beiden Werte:\[ V_{a_1}(s_3) \]:\[ V(s_3) = 2 + 0.18 V(s_1) + 0.27 V(s_2) + 0.45 V(s_3) \] \[ V_{a_2}(s_3) \]:\[ V(s_3) = 8 + 0.45 V(s_1) + 0.18 V(s_2) + 0.27 V(s_3) \] Löse jede Gleichung nach \(V(s_3)\) auf:
• Für \(a_1\):\[ V(s_3) = 2 + 0.18 V(s_1) + 0.27 V(s_2) + 0.45 V(s_3) \]Bringe \( V(s_3) \) auf eine Seite:\[ V(s_3) - 0.45 V(s_3) = 2 + 0.18 V(s_1) + 0.27 V(s_2) \]\[ V(s_3) (1 - 0.45) = 2 + 0.18 V(s_1) + 0.27 V(s_2) \]\[ V(s_3) = \frac{2 + 0.18 V(s_1) + 0.27 V(s_2)}{0.55} \]
• Für \(a_2\):\[ V(s_3) = 8 + 0.45 V(s_1) + 0.18 V(s_2) + 0.27 V(s_3) \]Bringe \( V(s_3) \) auf eine Seite:\[ V(s_3) - 0.27 V(s_3) = 8 + 0.45 V(s_1) + 0.18 V(s_2) \]\[ V(s_3) (1 - 0.27) = 8 + 0.45 V(s_1) + 0.18 V(s_2) \]\[ V(s_3) = \frac{8 + 0.45 V(s_1) + 0.18 V(s_2)}{0.73} \]
• Vergleiche die resultierenden Werte und wähle die Aktion \(a\) mit dem höheren Wert:
• Wähle die Aktion für den Zustand \(s_3)\ mit der maximalen Wertfunktion, dies ist die optimale Aktion.

d)

Vergleiche die berechneten Wertfunktionen \(V(s_1)\), \(V(s_2)\) und \(V(s_3)\), und beschreibe, wie die optimale Politik für dieses MDP aussehen würde. Welche Aktion würdest Du in den Zuständen \(s_1\), \(s_2\) und \(s_3\) jeweils wählen?

Lösung:

Gegeben: Ein Markov-Entscheidungsproblem (MDP) mit den Zuständen \(S = \{s_1, s_2, s_3\}\), den Aktionen \(A = \{a_1, a_2\}\), und dem Diskontfaktor \( \gamma = 0.9 \). Die Belohnungsfunktion ist definiert durch \(R(s, a)\) und die Übergangswahrscheinlichkeiten \(P(s'|s, a)\) sind in den folgenden Tabellen dargestellt.

• Belohnungsfunktion \(R(s, a)\):

  |   (s, a)   |  R(s, a)  ||------------|-----------|| (s_1, a_1) |    5      || (s_1, a_2) |    10     || (s_2, a_1) |     3     || (s_2, a_2) |     4     || (s_3, a_1) |     2     || (s_3, a_2) |     8     |

• Übergangswahrscheinlichkeiten \(P(s'|s, a)\):

  |   (s, a, s')    |  P(s'|s, a)   ||-----------------|---------------|| (s_1, a_1, s_1) |     0.2       || (s_1, a_1, s_2) |     0.5       || (s_1, a_1, s_3) |     0.3       || (s_1, a_2, s_1) |     0.1       || (s_1, a_2, s_2) |     0.6       || (s_1, a_2, s_3) |     0.3       || (s_2, a_1, s_1) |     0.4       || (s_2, a_1, s_2) |     0.4       || (s_2, a_1, s_3) |     0.2       || (s_2, a_2, s_1) |     0.3       || (s_2, a_2, s_2) |     0.5       || (s_2, a_2, s_3) |     0.2       || (s_3, a_1, s_1) |     0.2       || (s_3, a_1, s_2) |     0.3       || (s_3, a_1, s_3) |     0.5       || (s_3, a_2, s_1) |     0.5       || (s_3, a_2, s_2) |     0.2       || (s_3, a_2, s_3) |     0.3       |

Aufgaben: Vergleiche die berechneten Wertfunktionen \(V(s_1)\), \(V(s_2)\) und \(V(s_3)\), und beschreibe, wie die optimale Politik für dieses MDP aussehen würde. Welche Aktion würdest Du in den Zuständen \(s_1\), \(s_2\) und \(s_3\) jeweils wählen?

• Um die wertvolle Politik zu bestimmen, benötigen wir die berechneten Werte der Wertfunktionen \(V(s_1)\), \(V(s_2)\) und \(V(s_3)\).
• Angenommen, wir haben bereits die folgenden Wertfunktionen berechnet:\[ V(s_1) \], \[ V(s_2) \] und \[ V(s_3) \]
• In der vorherigen Aufgabe haben wir die Bellman-Gleichungen für \(V(s_1)\), \(V(s_2)\) und \(V(s_3)\) berechnet. Jetzt müssen wir die jeweiligen Werte für jede Aktion vergleichen und die optimale Aktion auswählen.

1. Zustand \(s_1\):

• Für Aktion \(a_1\):\[ V(s_1 | a_1) = 5 + 0.9 (0.2 V(s_1) + 0.5 V(s_2) + 0.3 V(s_3)) \]
• Für Aktion \(a_2\):\[ V(s_1 | a_2) = 10 + 0.9 (0.1 V(s_1) + 0.6 V(s_2) + 0.3 V(s_3)) \]
• Vergleiche und wähle die höhere Wertfunktion um die optimale Aktion zu bestimmen:

2. Zustand \(s_2\):

• Für Aktion \(a_1\):\[ V(s_2 | a_1) = 3 + 0.9 (0.4 V(s_1) + 0.4 V(s_2) + 0.2 V(s_3)) \]
• Für Aktion \(a_2\):\[ V(s_2 | a_2) = 4 + 0.9 (0.3 V(s_1) + 0.5 V(s_2) + 0.2 V(s_3)) \]
• Vergleiche und wähle die höhere Wertfunktion um die optimale Aktion zu bestimmen:

3. Zustand \(s_3\):

• Für Aktion \(a_1\):\[ V(s_3 | a_1) = 2 + 0.9 (0.2 V(s_1) + 0.3 V(s_2) + 0.5 V(s_3)) \]
• Für Aktion \(a_2\):\[ V(s_3 | a_2) = 8 + 0.9 (0.5 V(s_1) + 0.2 V(s_2) + 0.3 V(s_3)) \]
• Vergleiche und wähle die höhere Wertfunktion um die optimale Aktion zu bestimmen:

Die optimale Politik:

• Staat \(s_1\): Wähle die Aktion basierend auf dem maximalen Wert von\[ V(s_1 | a_1) \] und\[ V(s_1 | a_2) \]
• Staat \(s_2\): Wähle die Aktion basierend auf dem maximalen Wert von \[ V(s_2 | a_1) \] und \[ V(s_2 | a_2) \]
• Staat \(s_3\): Wähle die Aktion basierend auf dem maximalen Wert von \[ V(s_3 | a_1) \] und \[ V(s_3 | a_2) \]
• Die endgültige optimale Politik ist diejenige, die für jeden Zustand \(s_1, s_2,\) und \(s_3\) den höchsten Wert liefert. Diese Vorgehensweise minimiert den langfristigen Diskontierung der Belohnung.