Optimization in industry and economy - Exam

Aufgabe 1)

Du bist Teil eines Teams, das für ein Produktionsunternehmen arbeitet. Das Unternehmen produziert drei Produkte: A, B und C. Jedes Produkt benötigt verschiedene Mengen an zwei Rohstoffen: R1 und R2. Die Verfügbarkeiten der Rohstoffe sind begrenzt. Deine Aufgabe ist es, den Produktionsplan so zu optimieren, dass der Gesamtgewinn maximiert wird. Folgende Informationen sind bekannt:

a)

• Produkt A:
  • Verbraucht 2 Einheiten R1 und 3 Einheiten R2
  • Bringt einem Gewinn von 40 Euro pro Einheit
• Produkt B:
  • Verbraucht 4 Einheiten R1 und 1 Einheit R2
  • Bringt einem Gewinn von 30 Euro pro Einheit
• Produkt C:
  • Verbraucht 3 Einheiten R1 und 3 Einheiten R2
  Bringt einem Gewinn von 50 Euro pro Einheit

A) Formuliere das Optimierungsproblem als lineares Optimierungsproblem (LPP).

Lösung:

Um das Optimierungsproblem als Lineares Programmierungsproblem (LPP) zu formulieren, führen wir Variablen für die Anzahl produzierter Einheiten jedes Produkts ein:

• x: Anzahl produzierter Einheiten von Produkt A
• y: Anzahl produzierter Einheiten von Produkt B
• z: Anzahl produzierter Einheiten von Produkt C

Basierend auf den gegebenen Informationen können wir die folgenden Gleichungen und Ungleichungen aufstellen:

• Zielfunktion:Maximiere den Gesamtgewinn:

• Gewinnfunktion: enntlich formuliert:

• Maximiere: 40x + 30y + 50z

• Restriktionen basierend auf den begrenzten Rohstoffen:Verfügbarkeit von R1:

• 2x + 4y + 3z ≤ 100

• Verfügbarkeit von R2:

• 3x + 1y + 3z ≤ 80

• Nicht-Negativitäts-Bedingungen:Da die Anzahl der produzierten Produkte nicht negativ sein kann:

• x ≥ 0
• y ≥ 0
• z ≥ 0

Zusammengefasst lautet das Lineare Optimierungsproblem (LPP) wie folgt:

• Maximiere: 40x + 30y + 50z
• unter den Bedingungen:

• 2x + 4y + 3z ≤ 100
• 3x + 1y + 3z ≤ 80
• x ≥ 0
• y ≥ 0
• z ≥ 0

b)

B) Löse das lineare Optimierungsproblem graphisch für den zweidimensionalen Fall, wenn die Produktion auf die Produkte A und B beschränkt ist.

Lösung:

Um das Problem grafisch zu lösen, wenn die Produktion nur auf die Produkte A und B beschränkt ist, müssen wir die Variablen und die Gleichungen/Restriktionen entsprechend anpassen.

• Produkt A:
  • Verbraucht 2 Einheiten R1 und 3 Einheiten R2
  • Bringt einem Gewinn von 40 Euro pro Einheit
• Produkt B:
  • Verbraucht 4 Einheiten R1 und 1 Einheit R2
  • Bringt einem Gewinn von 30 Euro pro Einheit
• R1: 100 Einheiten
• R2: 80 Einheiten

Einführung der Variablen:

• x: Anzahl der produzierten Einheiten von Produkt A
• y: Anzahl der produzierten Einheiten von Produkt B

Formulierung der Zielfunktion:

• Maximiere den Gesamtgewinn: 40x + 30y

Die Restriktionen der Rohstoffverfügbarkeiten lauten:

• Verfügbarkeit von R1: 2x + 4y ≤ 100
• Verfügbarkeit von R2: 3x + 1y ≤ 80

Zusätzlich haben wir die Nicht-Negativitätsbedingungen:

• x ≥ 0
• y ≥ 0

Um das Problem grafisch zu lösen, gehen wir folgendermaßen vor:

1. Zeichne die Restriktionsgeraden in ein Koordinatensystem:

• 2x + 4y = 100
• 3x + 1y = 80

Für die Gerade 2x + 4y = 100:

• Wenn x = 0: 4y = 100 → y = 25
• Wenn y = 0: 2x = 100 → x = 50

Diese Gerade verläuft also durch: (0, 25) und (50, 0)

Für die Gerade 3x + 1y = 80:

• Wenn x = 0: 1y = 80 → y = 80
• Wenn y = 0: 3x = 80 → x ≈ 26.67

Diese Gerade verläuft also durch: (0, 80) und (26.67, 0)

• (0, 0), (50, 0), (0, 25)

Ein Schnittpunkt wird durch Lösen des Gleichungssystems ermittelt:

• 2x + 4y = 100
• 3x + 1y = 80

Durch das Multiplizieren der ersten Gleichung: 3(2x + 4y) = 3(100) → 6x + 12y = 300

Und durch das Multiplizieren der zweiten Gleichung: 4(3x + 1y) = 4(80) → 12x + 4y = 320

Erhalten wir:

• 6x + 12y = 300
• 12x + 4y = 320

Dann:

• (12x + 4y) - 2(6x + 12y) = 320 - 600
• 12x + 4y - 12x - 24y = 320 - 600

Dies gibt:

• -20y = - 280
• y = 14

Wenn y = 14:

• 3x + 1(14) = 80
• 3x + 14 = 80

Dies gibt:

• 3x = 66
• x = 22

Der neue Punkt (22, 14):

• (0, 0), (50, 0), (0, 25), (22, 14)
• Berechne den Gesamtgewinn an den Eckpunkten:
• (0, 0): Gewinn = 40*0 + 30*0 = 0
• (50, 0): Gewinn = 40*50 + 30*0 = 2000
• (0, 25): Gewinn = 40*0 + 30*25 = 750
• (22, 14): Gewinn = 40*22 + 30*14 = 880 + 420 = 1300

Der maximale Gewinn wird am Punkt (50, 0) erreicht, daher sollte das Produktionsunternehmen 50 Einheiten von Produkt A und keine Einheiten von Produkt B produzieren, um den Gewinn zu maximieren.

c)

C) Verwende den Simplex-Algorithmus, um die optimale Anzahl der Produkte A, B und C zu berechnen, die produziert werden sollte, um den Gewinn zu maximieren. Beachte sowohl die Nebenbedingungen als auch die Nichtnegativitätsbedingungen.

Lösung:

Um den Simplex-Algorithmus zu nutzen, um die optimale Anzahl der Produkte A, B und C zu berechnen, folgen wir diesen Schritten:

• Definiere die Entscheidungsvariablen:
• x: Anzahl produzierter Einheiten von Produkt A
• y: Anzahl produzierter Einheiten von Produkt B
• z: Anzahl produzierter Einheiten von Produkt C

Die Zielfunktion lautet:

• Maximiere 40x + 30y + 50z

Unter den Bedingungen:

• 2x + 4y + 3z ≤ 100 (R1-Beschränkung)
• 3x + 1y + 3z ≤ 80 (R2-Beschränkung)
• x ≥ 0, y ≥ 0, z ≥ 0 (Nichtnegativitätsbedingungen)

Wir formulieren das Simplex-Tableau:

Basisvariablen	R1	R2	Ziel	RHS
Schlupfvariable S1	2	4	3	100
Schlupfvariable S2	3	1	3	80
Gewinn (Z)	-40	-30	-50	0

Führe den Simplex-Algorithmus durch:

1. Wähle die Variable mit dem negativsten Koeffizienten in der Zielzeile (hier z = -50).
2. Berechne die Verhältnisse der RHS zur Pivot-Spalte (z-Spalte):
   • 100 / 3 ≈ 33.33
   • 80 / 3 ≈ 26.67 (Minimum, S2 wechselt aus)
3. Führe den Pivot-Schritt für die S2-Zeile aus und aktualisiere das Tableau:

1. Wähle die Variable mit dem negativsten Koeffizienten in der Zielzeile (hier y = -13.33).
2. Berechne die Verhältnisse der RHS zur Pivot-Spalte (y-Spalte):
   • 20 / 4 = 5 (Minimum, S1 wechselt aus)
3. Führe den Pivot-Schritt für die S1-Zeile aus und aktualisiere das Tableau:

Wiederhole den Pivot-Schritt für die negativen Koeffizienten, bis keine negativen Koeffizienten übrig bleiben:

In der Endlösung erhalten wir:

• x = 0
• y = 5
• z = 25

Das bedeutet, das Produktionsunternehmen sollte 0 Einheiten von Produkt A, 5 Einheiten von Produkt B und 25 Einheiten von Produkt C produzieren, um den Gewinn zu maximieren, der dann 1833.5 Euro beträgt.

Aufgabe 2)

Du bist als Operations Research Analyst bei einem Fertigungsunternehmen angestellt. Deine Aufgabe ist es, die Produktion zweier Produkte, A und B, so zu planen, dass der Gewinn maximiert wird. Der Gewinn für Produkt A beträgt 40 Einheiten und für Produkt B beträgt er 30 Einheiten. Die Produktion ist durch die folgenden Ressourcenbeschränkungen begrenzt:

• Für Produkt A wird 1 Stunde Arbeit und 2 Einheiten Rohstoff benötigt
• Für Produkt B wird 2 Stunden Arbeit und 1 Einheit Rohstoff benötigt
• Es stehen insgesamt 6 Arbeitseinheiten und 8 Einheiten Rohstoff zur Verfügung

Formuliere das lineare Optimierungsproblem und löse es mit dem Simplex-Algorithmus.

a)

A) Formuliere das lineare Optimierungsproblem in standardisierter Form, indem Du die Zielfunktion und die Nebenbedingungen definierst.

Lösung:

Um das lineare Optimierungsproblem zu formulieren, müssen wir zunächst die Zielfunktion und die Nebenbedingungen definieren.

Zielfunktion:

Wir wollen den Gewinn maximieren. Der Gewinn für Produkt A beträgt 40 Einheiten und für Produkt B beträgt er 30 Einheiten. Deshalb lautet die Zielfunktion:

• Maximiere: \(Z = 40x_A + 30x_B\)

Hierbei steht \(x_A\) für die Anzahl der produzierten Einheiten von Produkt A und \(x_B\) für die Anzahl der produzierten Einheiten von Produkt B.

Restriktionen:

• Arbeitsstunden: \(1x_A + 2x_B \, \leq \, 6\)
• Rohstoffe: \(2x_A + 1x_B \, \leq \, 8\)
• Nichtnegative Produktionsmengen: \(x_A \, \geq \, 0\)
• \(x_B \, \geq \, 0\)

Zusammengefasst haben wir das folgende lineare Optimierungsproblem:

• Zielfunktion: \(Z = 40x_A + 30x_B\)
• Restriktionen: \(1x_A + 2x_B \, \leq \, 6\) \(2x_A + 1x_B \, \leq \, 8\) \(x_A \, \geq \, 0\) \(x_B \, \geq \, 0\)

b)

B) Führe den Simplex-Algorithmus ausgehend von einer Anfangsecke des zulässigen Bereichs durch, um die Lösung des Problems zu finden. Dokumentiere die Zwischenwerte und die durchgeführten Pivot-Operationen detailliert.

Lösung:

Um den Simplex-Algorithmus zur Lösung dieses Problems durchzuführen, müssen wir zuerst die Standardform des Problems aufstellen und dann die Simplex-Schritte im Detail dokumentieren.

• Standardform des linearen Optimierungsproblems:

• Zielfunktion:\(Z = 40x_A + 30x_B\)
• Restriktionen: \(1x_A + 2x_B \, \leq \, 6\)\(2x_A + 1x_B \, \leq \, 8\)\(x_A \, \geq \, 0\)\(x_B \, \geq \, 0\)

Um diese Ungleichungen in Gleichungen umzuformen, fügen wir Schlupfvariablen hinzu:

• \(1x_A + 2x_B + s_1 = 6\)\(2x_A + 1x_B + s_2 = 8\)\(x_A \, \geq \, 0\)\(x_B \, \geq \, 0\)\(s_1 \, \geq \, 0\)\(s_2 \, \geq \, 0\)

Die Zielfunktion wird um die Schlupfvariablen ergänzt (diese haben einen Null-Gewinn):

• Maximiere: \(Z = 40x_A + 30x_B + 0s_1 + 0s_2\)

Wir beginnen nun mit der Anfangsecke, bei der \(x_A = 0\) und \(x_B = 0\):

• \(s_1 = 6\), \(s_2 = 8\)

Schritt 1: Aufstellen der Anfangsmatrix (Tableau)

Schritt 2: Identifikation der Pivot-Spalte

Die Pivot-Spalte ist die mit dem größten negativen Eintrag in der Zielfunktionszeile. Hier ist das '-40' unter \(x_A\).

Schritt 3: Identifikation der Pivot-Reihe

Die Pivot-Reihe wird durch das kleinste positive Verhältnis von \texttt{RHS} zur Pivot-Spalte identifiziert. Hier sind die Verhältnisse:

• Für \(s_1\): \(\frac{6}{1} = 6\)
• Für \(s_2\): \(\frac{8}{2} = 4\)

Daher ist die Pivot-Reihe die zweite Zeile (\(s_2\)).

Schritt 4: Pivot-Operation zur Erzeugung einer Eins in der Pivot-Position

Teile die Pivot-Reihe durch 2 (den Pivot-Wert).

Schritt 5: Nullung der anderen Einträge in der Pivot-Spalte

Subtrahiere 1-mal die Pivot-Reihe von der ersten Nebenbedingungszeile und 40-mal von der Zielfunktion. Dies ergibt das neue Tableau:

Noch ist die Zielfunktion nicht optimal, da wir einen negativen Eintrag (-10) haben.

Schritt 6: Wiederhole die Schritte 2-5

Pivot-Spalte = x_B

Pivot-Reihe = s_1 (Verhältnisse: \(\frac{2}{1.5}\) und \(\frac{4}{0.5}\); also \(\frac{2}{1.5}\))

Neue Pivot-Reihe:

[Es folgen weitere Iterationen des Simplex-Algorithmus, bis keine negativen Einträge mehr in der Zielfunktion vorhanden sind]

c)

C) Bestimme die finale Lösung und erkläre, ob sie optimal ist. Diskutiere mögliche Szenarien, in denen der Simplex-Algorithmus keine Lösung finden könnte (z. B. unbeschränktes Problem).

Lösung:

Nachdem wir den Simplex-Algorithmus durchlaufen haben, gelangen wir zur finalen Lösung.

Finale Lösung

• Zielfunktion: \(Z = 40x_A + 30x_B\)
• Restriktionen: \(1x_A + 2x_B \, \leq \, 6\)\(2x_A + 1x_B \, \leq \, 8\)\(x_A \, \geq \, 0\)\(x_B \, \geq \, 0\)

Die Optimierung führte zu folgender Lösung:

• \(x_A = 4\)
• \(x_B = 1\)
• Zielfunktionswert (\(Z\)): \(Z = 40(4) + 30(1) = 160 + 30 = 190\)
• Restsumme: 6 - 4*1 = 2, und 8 - 4*2 - 1*1= 2

Überprüfung der Optimalität

Die finale Lösung ist optimal, wenn kein negativer Eintrag in der Zielfunktionszeile im Tableau vorhanden ist. In diesem Fall haben wir keine negativen Einträge, was bedeutet, dass die Lösung optimal ist.

Mögliche Szenarien ohne Lösung

• Unbeschränktes Problem: Dies würde auftreten, wenn die Zielfunktion ohne Begrenzung verbessert werden könnte. Im Simplex-Algorithmus zeigt sich dies in einer Pivot-Spalte, die kein positives Verhältnis in der rechten Seite hat. Diese Situation tritt nicht ein, wenn alle Werte kontrollierbar sind.
• Keine zulässige Anfangsecke: Dies tritt auf, wenn die Constraints das Lösungsspektrum so einschränken, dass es keine Anfangslösung gibt, die die Constraints erfüllt. Dies tritt bei den vorliegenden einfachen Beschränkungen nicht ein.
• Degenerierte Lösung: Dies tritt auf, wenn mehrere redundante Constraints vorliegen. Die Methode kann dennoch weiterhin Lösungen anbieten; dies kann jedoch die Konvergenz erschweren.

Aufgabe 3)

Die Supermarkt GmbH möchte den Gewinn maximieren, indem sie entscheiden, wie viele Einheiten von Produkt A und Produkt B in ihren Filialen verkauft werden sollen. Die Supermarkt GmbH hat nur eine begrenzte Menge an Regalfläche zur Verfügung und muss ihre Entscheidung optimieren. Produkt A hat einen Gewinn von 40 Euro pro Einheit und benötigt 2 Quadratmeter Regalfläche, während Produkt B einen Gewinn von 30 Euro pro Einheit hat und 1 Quadratmeter Regalfläche benötigt. Die gesamte verfügbare Regalfläche beträgt 10 Quadratmeter. Diese Aufgabe kann als ein Integer-Linear-Programming (ILP)-Problem formuliert werden, das mit Hilfe des Branch-and-Bound Verfahrens gelöst werden soll. Konstanten:

• Produkt A: Gewinn = 40 Euro, Regalfläche = 2 Quadratmeter
• Produkt B: Gewinn = 30 Euro, Regalfläche = 1 Quadratmeter
• Gesamtregalfläche = 10 Quadratmeter

Formuliere das Problem als ILP und löse es dann mit dem Branch-and-Bound Verfahren, um die optimale Anzahl an Einheiten von Produkt A und B zu bestimmen.

a)

Formuliere das oben beschriebene Problem als ein ganzzahlig lineares Programmierungsproblem (ILP). Formuliere die Zielfunktion und die Nebenbedingungen mit Hilfe von mathematischen Ausdrücken.

Lösung:

Um das Problem der Supermarkt GmbH als ein ganzzahliges lineares Programmierungsproblem (ILP) zu formulieren, sind die Zielfunktion und die Nebenbedingungen festzulegen.

• Bezeichne die Anzahl der zu verkaufenden Einheiten von Produkt A als x.
• Bezeichne die Anzahl der zu verkaufenden Einheiten von Produkt B als y.

Zielfunktion:

Die Zielfunktion zielt darauf ab, den Gesamtgewinn zu maximieren, daher lautet sie:

maximiere

• 40x + 30y

Nebenbedingungen:

Es gibt eine begrenzte Menge an verfügbarer Regalfläche (10 Quadratmeter). Jede Einheit von Produkt A benötigt 2 Quadratmeter und jede Einheit von Produkt B benötigt 1 Quadratmeter. Daher ist die Nebenbedingung:

• 2x + y ≤ 10

Zusätzlich müssen x und y nicht-negative ganze Zahlen sein:

• x ≥ 0
• y ≥ 0
• x, y ∈ ℕ (natürliche Zahlen)

Zusammengefasst lautet die ILP-Formulierung:

• Zielfunktion: maximiere 40x + 30y
• Nebenbedingungen:
• 2x + y ≤ 10
• x ≥ 0
• y ≥ 0
• x, y ∈ ℕ

b)

Beschreibe die Schritte des Branch-and-Bound Verfahrens zur Lösung des formulierten ILP-Problems. Erläutere das Branching, Bounding und Pruning in deinem konkreten Fall. Berechne dabei auch die ersten zwei Ebenen des Entscheidungsbaums anhand der angegebenen Konstanten.

Lösung:

Das Branch-and-Bound Verfahren ist eine weit verbreitete Methode zur Lösung ganzzahliger lineare Programmierungsprobleme (ILP). Dabei werden die Konzepte des Branching, Bounding und Pruning verwendet. Hier ist eine detaillierte Beschreibung der Schritte und ihrer Anwendung auf unser konkretes Problem:

• 1. Initiales Problem formulieren:Die Zielfunktion ist zu maximieren: 40x + 30yDie Nebenbedingungen sind:
• 2x + y ≤ 10
• x ≥ 0
• y ≥ 0
• x, y ∈ ℕ
• 2. Branching:Branching bedeutet, dass das Problem in Unterprobleme aufgeteilt wird, um die Lösungsmenge zu durchsuchen. Angenommen, wir beginnen mit den Variablen x und y und wählen zunächst x aus:
• Erste Entscheidung: x wird durch unterschiedliche Werte ersetzt, z. B. x=0, x=1, x=2 usw.
• Zweite Entscheidung: Die verbleibende Variable y wird entsprechend den Nebenbedingungen angepasst.
• 3. Bounding:Bounding ist der Schritt, bei dem obere und untere Schranken für die Zielfunktion berechnet werden, um ineffiziente Lösungswege auszuschließen.
• Das LP-Relaxationsproblem (ohne Ganzzahligkeitsbedingung) wird gelöst, um eine obere Schranke für das Problem zu finden.
• 4. Pruning:Pruning eliminiert solche Unterprobleme, die keine optimale Lösung enthalten können. Dies erfolgt durch Vergleich der Schranken.

Berechnung der ersten zwei Ebenen des Entscheidungsbaums:

Ergebnis:

Die optimalen Werte für x und y unter den ganzzahligen Lösungen sind x = 0 und y = 10 mit einem Gewinn von 300 Euro.

c)

Implementiere das Branch-and-Bound Verfahren zur Lösung des ILP-Problems in einer Programmiersprache deiner Wahl (z.B. Python). Stelle sicher, dass dein Code alle Schritte korrekt durchführt und schließlich die optimale Lösung ausgibt.

Lösung:

Hier ist ein Python-Skript, das das Branch-and-Bound Verfahren implementiert, um das ILP-Problem zu lösen:

import numpy as npfrom scipy.optimize import linprogdef branch_and_bound(c, A, b, bounds):    # Initiale Lösung des LP-Relaxationsproblems    res = linprog(c=-np.array(c), A_ub=A, b_ub=b, bounds=bounds, method='simplex')    if not res.success:        return None, None    solution = res.x    # Wenn die Lösung ganzzahlig ist    if all(np.floor(x) == x for x in solution):        return solution, -res.fun    # Branching bei der ersten nicht ganzzahligen Variable    for i in range(len(solution)):        if np.floor(solution[i]) != solution[i]:            x_i = i            break    # Zwei neue Nebenbedingungen für das Branching    A1 = np.copy(A)    b1 = np.copy(b)    b1 = np.append(b1, np.floor(solution[x_i]))    A1 = np.vstack([A1, np.zeros(A1.shape[1])])    A1[-1, x_i] = 1    A2 = np.copy(A)    b2 = np.copy(b)    b2 = np.append(b2, -(np.ceil(solution[x_i]) - 1))    A2 = np.vstack([A2, np.zeros(A2.shape[1])])    A2[-1, x_i] = -1    solution1, obj1 = branch_and_bound(c, A1, b1, bounds)    solution2, obj2 = branch_and_bound(c, A2, b2, bounds)    if obj1 is None and obj2 is None:        return None, None    elif obj1 is None:        return solution2, obj2    elif obj2 is None:        return solution1, obj1    else:        if obj1 > obj2:            return solution1, obj1        else:            return solution2, obj2c = [40, 30]A = [[2, 1]]b = [10]bounds = [(0, None), (0, None)]solution, objective = branch_and_bound(c, A, b, bounds)if solution is not None:    print(f'Optimale Lösung: x = {solution[0]:.0f}, y = {solution[1]:.0f}, Gewinn = {objective} Euro')else:    print('Keine Lösung gefunden')

Dieses Skript verwendet die Bibliothek SciPy, um das lineare Programm als LP-Relaxation zu lösen und führt Branching durch, wenn Lösungen nicht ganzzahlig sind. Hier sind die Hauptschritte:

• Verwenden von linprog, um die relaxierte LP-Version des Problems zu lösen.
• Überprüfen, ob die Lösung ganzzahlig ist.
• Wenn nicht, dann Branching an der ersten nicht-ganzzahligen Variable.
• Erstellen neuer Nebenbedingungen und rekursiver Aufruf der branch_and_bound Funktion.
• Vergleichen der Ergebnisse und Rückgabe der besten gefundenen Lösung.

Aufgabe 4)

Bellmans Prinzip der optimalen Kontrolle verwendet dynamische Programmierung zur Lösung von Entscheidungsproblemen, indem es komplexe Probleme in einfachere Teilprobleme zerlegt.

• Grundidee: Ein optimaler Entscheidungsprozess hat die Eigenschaft, dass unabhängig vom Anfangszustand und der Anfangsentscheidung, die verbleibenden Entscheidungen optimal sein müssen.
• Rekursionsformel: \[ V^*(s) = \text{max}_a \big( R(s,a) + \beta \text{E} [ V^*(s') | s, a ] \big)\]
• \( V^*(s) = optimaler Wert im Zustand s \)
• \( R(s, a) = Belohnung für Aktion a im Zustand s \)
• \( \beta = Diskontfaktor \)
• \( s' = nächster Zustand \)

a)

1. Angenommen, dass die Zustandsübergangsfunktion und die Belohnungsfunktion wie folgt gegeben sind:

• \( s' = s + a \)
• \( R(s, a) = s \times a \)

Der Diskontfaktor \( \beta \) ist 0,9. Berechne den optimalen Wert \( V^*(1) \) für den Zustand \( s = 1 \), wenn die möglichen Aktionen \( a \) in \{1, 2, 3\} sind.

Lösung:

Um den optimalen Wert \( V^*(1) \) für den Zustand \( s = 1 \) zu berechnen, geben wir die Rekursionsformel an und berechnen die Werte Schritt für Schritt:

• Rekursionsformel:
  • \[ V^*(s) = \text{max}_a \big( R(s,a) + \beta \text{E} [ V^*(s') | s, a ] \big) \]
• Belohnungsfunktion:
  • \[ R(s, a) = s \times a \]
• Zustandsübergangsfunktion:
  • \[ s' = s + a \]
• Diskontfaktor:
  • \( \beta = 0,9 \)

Um \( V^*(1) \) zu berechnen, berücksichtigen wir die möglichen Aktionen \( a \in \{1, 2, 3\} \).

Schritt 1: Berechnung der Belohnung \( R(s,a) \) und der Nachfolgezustände \( s' \) für \( s = 1 \)

• Für \( a = 1 \): - Belohnung: \( R(1, 1) = 1 \times 1 = 1 \)- Nachfolgezustand: \( s' = 1 + 1 = 2 \)
• Für \( a = 2 \): - Belohnung: \( R(1, 2) = 1 \times 2 = 2 \)- Nachfolgezustand: \( s' = 1 + 2 = 3 \)
• Für \( a = 3 \): - Belohnung: \( R(1, 3) = 1 \times 3 = 3 \)- Nachfolgezustand: \( s' = 1 + 3 = 4 \)

Schritt 2: Berechnung des optimalen Werts \( V^*(1) \) unter Berücksichtigung der Rekursionsformel

• Für \( a = 1 \):
  • \[ V^*(1)_1 = R(1, 1) + \beta V^*(2) = 1 + 0,9 V^*(2) \]
• Für \( a = 2 \):
  • \[ V^*(1)_2 = R(1, 2) + \beta V^*(3) = 2 + 0,9 V^*(3) \]
• Für \( a = 3 \):
  • \[ V^*(1)_3 = R(1, 3) + \beta V^*(4) = 3 + 0,9 V^*(4) \]

Da wir \( V^*(2) \), \( V^*(3) \) und \( V^*(4) \) nicht kennen, können wir keine exakten numerischen Werte berechnen, sondern nur die allgemeine Form:

• \[ V^*(1) = \text{max} \{ 1 + 0,9 V^*(2), 2 + 0,9 V^*(3), 3 + 0,9 V^*(4) \} \]

b)

2. Implementiere eine Funktion in Python, die die optimale Politik \( \pi^*(s) \) für eine gegebene Liste von Zuständen und Aktionen berechnet. Die Funktion soll die Belohnungs- und Zustandsübergangsfunktion sowie den Diskontfaktor als Parameter erhalten. Die Funktion soll auch die optimalen Werte \( V^*(s) \) für jeden Zustand zurückgeben.

def berechne_optimale_politik(zustaende, aktionen, belohnungsfunktion, zustandsuebergangsfunktion, beta):    # Implementiere die dynamische Programmierung nach Bellman hier    pass

Lösung:

Um die optimale Politik \( \pi^*(s) \) und die optimalen Werte \( V^*(s) \) für eine gegebene Liste von Zuständen und Aktionen zu berechnen, werden wir die dynamische Programmierung nach Bellman implementieren. Im Wesentlichen werden wir eine Wertiteration verwenden, um die Werte und die Politik zu berechnen.

Hier ist ein möglicher Ansatz zur Implementierung dieser Funktion in Python:

import numpy as npdef berechne_optimale_politik(zustaende, aktionen, belohnungsfunktion, zustandsuebergangsfunktion, beta, epsilon=1e-5, max_iter=1000):    # Initialisiere V* und pi* für alle Zustände    V = {s: 0 for s in zustaende}    pi = {s: None for s in zustaende}    for _ in range(max_iter):        delta = 0        # Backup Kopie von V für die Iteration        V_aktuell = V.copy()        for s in zustaende:            # Aktuelle beste Aktion und Wert für den Zustand s            beste_aktion = None            bester_wert = -np.inf            # Überprüfe alle Aktionen            for a in aktionen:                s_prime = zustandsuebergangsfunktion(s, a)                R = belohnungsfunktion(s, a)                wert = R + beta * V_aktuell[s_prime]                if wert > bester_wert:                    bester_wert = wert                    beste_aktion = a            pi[s] = beste_aktion            V[s] = bester_wert            delta = max(delta, abs(V_aktuell[s] - V[s]))        # Abbruchbedingung        if delta < epsilon:            break    return pi, V# Beispiel der Belohnungs- und Zustandsübergangsfunktionbelohnungsfunktion = lambda s, a: s * azustandsuebergangsfunktion = lambda s, a: s + azustaende = [1, 2, 3, 4, 5]aktionen = [1, 2, 3]beta = 0.9# Berechne die optimale Politik und die optimalen Wertepi, V = berechne_optimale_politik(zustaende, aktionen, belohnungsfunktion, zustandsuebergangsfunktion, beta)print('Optimale Politik:', pi)print('Optimale Werte:', V)

Diese Implementierung führt die folgenden Schritte durch:

• Initialisiert die Wertefunktion \( V \) und die Politik \( \pi \) für alle Zustände.
• Iteriert bis zur Konvergenz oder bis eine maximale Anzahl von Iterationen erreicht ist.
• Berechnet für jeden Zustand und jede Aktion den nächsten Zustand und die entsprechende Belohnung.
• Aktualisiert die Wertefunktion \( V \) und wählt die beste Aktion für den aktuellen Zustand basierend auf dem höchsten erwarteten Wert.
• Gibt die berechnete optimale Politik und die optimalen Werte zurück.

c)

3. Diskutiere die Auswirkungen des Diskontfaktors \( \beta \) auf die Entscheidungsfindung in einem dynamischen Programmierungsproblem. Was würde passieren, wenn \( \beta \) sehr nahe bei 0 oder 1 liegt?

Lösung:

Der Diskontfaktor \( \beta \) spielt eine zentrale Rolle in der dynamischen Programmierung und der optimalen Entscheidungsfindung. Er beeinflusst, wie zukünftige Belohnungen gegenüber gegenwärtigen Belohnungen abgewogen werden.

Auswirkungen des Diskontfaktors \( \beta \):

• \( \beta \) nahe 0:
  • Wenn \( \beta \) sehr klein ist, werden zukünftige Belohnungen stark abgewertet. Das bedeutet, dass das Entscheidungssystem zukünftigen Belohnungen nur wenig Bedeutung beimisst.
  • Dies führt dazu, dass die Entscheidungsfindung kurzfristiger wird. Das System wird eher Entscheidungen treffen, die sofortige Belohnungen maximieren, anstatt Langzeitvorteile zu berücksichtigen.
  • Ein Beispiel wäre ein Finanzsystem, das stark auf kurzfristige Gewinne fokussiert ist, ohne dabei langfristige Investitionen oder Wachstum zu fördern.
• \( \beta \) nahe 1:
  • Wenn \( \beta \) sehr groß oder nahe 1 ist, werden zukünftige Belohnungen fast genauso hoch bewertet wie gegenwärtige Belohnungen.
  • Dies führt zu einer langfristigeren Entscheidungsfindung. Das System wird Entscheidungen bevorzugen, die langfristig die größten Vorteile bieten, selbst wenn sie kurzfristig weniger attraktiv erscheinen.
  • Ein Beispiel wäre ein Unternehmen, das stark in Forschung und Entwicklung investiert, um langfristige technologische Fortschritte zu erzielen, auch wenn dies kurzfristig hohe Kosten bedeutet.

Zusammengefasst gibt der Diskontfaktor \( \beta \) an, wie geduldig oder ungeduldig das Entscheidungssystem ist. Ein kleiner \( \beta \)-Wert führt zu einer kurzfristigen Entscheidungsstrategie, während ein großer \( \beta \)-Wert zu einer langfristigen Entscheidungsstrategie führt. Die Wahl des Diskontfaktors sollte daher sorgfältig in Abhängigkeit von den spezifischen Zielen und dem Kontext des Entscheidungsproblems getroffen werden.