Optimierung für Ingenieure - Exam

Aufgabe 1)

Ein Produktionsunternehmen plant die Herstellung zweier Produkte (Produkt A und Produkt B) unter bestimmten Bedingungen. Es gibt eine maximale Anzahl an verfügbaren Arbeitsstunden (200 Stunden pro Woche) und Rohmaterialien (500 Einheiten pro Woche). Produkt A erfordert 2 Stunden und 5 Einheiten Rohmaterial pro Stück, Produkt B erfordert 3 Stunden und 7 Einheiten Rohmaterial. Der Gewinn pro Einheit von Produkt A beträgt 50 Euro und der Gewinn pro Einheit von Produkt B beträgt 70 Euro. Das Unternehmen möchte den Gesamtgewinn maximieren.

b)

Löse das lineare Optimierungsproblem mathematisch und bestimme die Anzahl der Produkte A und B, die hergestellt werden sollen, um den Gewinn zu maximieren.

Lösung:

• Um das lineare Optimierungsproblem mathematisch zu lösen und die Anzahl der Produkte A und B zu bestimmen, die hergestellt werden sollen, um den Gewinn zu maximieren, folgen wir diesen Schritten:

1. Das Optimierungsproblem formulieren:Zielfunktion:\[\text{Maximiere } Z = 50x_A + 70x_B\]Nebenbedingungen:

• Arbeitsstunden:\[2x_A + 3x_B \leq 200\]
• Rohmaterialien:\[5x_A + 7x_B \leq 500\]
• Keine negativen Produktionsmengen:\[x_A \geq 0\]\[x_B \geq 0\]

2. Die Constraints in Ungleichungen umwandeln und die Gleichungen lösen:Die einfachste Methode zur Lösung des Problems besteht darin, die zulässige Menge an Produkten A und B zu finden, die die Bedingungen erfüllen.Um die möglichen Kombinationen zu finden, betrachten wir die Schnittpunkte der Nebenbedingungen:Schnittpunkt der beiden Ungleichungen:\[2x_A + 3x_B = 200\]\[5x_A + 7x_B = 500\]3. System linearer Gleichungen lösen:Multipliziere die erste Gleichung mit 7 und die zweite mit 3, um die Koeffizienten von x_B gleich zu machen:\[7(2x_A + 3x_B) = 7(200)\]\[14x_A + 21x_B = 1400\]\[3(5x_A + 7x_B) = 3(500)\]\[15x_A + 21x_B = 1500\]Subtrahiere die erste Gleichung von der zweiten:\[15x_A + 21x_B - 14x_A - 21x_B = 1500 - 1400\]\[x_A = 100\]Jetzt setzen wir x_A in eine der ursprünglichen Gleichungen ein, um x_B zu berechnen:\[2(100) + 3x_B = 200\]\[200 + 3x_B = 200\]\[3x_B = 0\]\[x_B = 0\]4. Ergebnis überprüfen:

• Arbeitsstunden:\[2(100) + 3(0) = 200\] (erfüllt)
• Rohmaterialien:\[5(100) + 7(0) = 500\] (erfüllt)

Daher maximiert das Unternehmen den Gewinn, indem es 100 Einheiten von Produkt A und 0 Einheiten von Produkt B produziert.Optimales Produktionsprogramm:

• Produkt A: x_A = 100
• Produkt B: x_B = 0

Maximaler Gewinn:\[Z = 50(100) + 70(0) = 5000\]

d)

Stelle das genannte Optimierungsproblem graphisch dar. Zeichne die Machbarkeitsmenge und identifiziere den Optimalpunkt.

Lösung:

Graphische Darstellung des linearen Optimierungsproblems:Zunächst müssen wir die Nebenbedingungen graphisch darstellen und die Machbarkeitsmenge sowie den Optimalpunkt finden.1. Nebenbedingungen aufstellen:

• Verfügbare Arbeitsstunden:\[2x_A + 3x_B \leq 200\]
• Verfügbare Rohmaterialien:\[5x_A + 7x_B \leq 500\]
• Keine negativen Produktionsmengen:\[x_A \geq 0\]\[x_B \geq 0\]

2. Graphische Darstellung:Um die Nebenbedingungen zu zeichnen, bestimmen wir die Schnittpunkte der Geraden mit den Achsen:

• Für die Arbeitsstunden-Bedingung:\[2x_A + 3x_B = 200\]
• Wenn \(x_A = 0\), dann \(x_B = \frac{200}{3} ≈ 66.67\)
• Wenn \(x_B = 0\), dann \(x_A = 100\)
• Für die Rohmaterialien-Bedingung:\[5x_A + 7x_B = 500\]
• Wenn \(x_A = 0\), dann \(x_B = \frac{500}{7} ≈ 71.43\)
• Wenn \(x_B = 0\), dann \(x_A = 100\)

Diese Punkte helfen uns, die Gleichungen in ein Koordinatensystem zu zeichnen:3. Koordinatensystem erstellen:

• Die x-Achse repräsentiert \(x_A\) und die y-Achse \(x_B\).
• Zeichne die Gerade für die Arbeitsstunden-Bedingung von (100, 0) zu (0, 66.67).
• Zeichne die Gerade für die Rohmaterialien-Bedingung von (100, 0) zu (0, 71.43).

4. Zulässige Lösungsmenge (Machbarkeitsmenge):Die Machbarkeitsmenge ist der Bereich, in dem beide Bedingungen gleichzeitig erfüllt sind. Dies ist die Schnittmenge der beiden halbräumigen Bereich nach den Geraden.5. Optimalpunkt identifizieren:Der Optimalpunkt liegt in der Ecke der Machbarkeitsmenge, wo der Gewinn maximiert wird.6. Berechnung der Eckpunkte:Es gibt vier mögliche Eckpunkte:

• (0, 0)
• (100, 0)
• (0, 66.67)
• (20, 53.33): Schnittpunkt der beiden Geraden

Um den Schnittpunkt der beiden Geraden zu finden:- Setze die beiden Gleichungen gleich:\[2x_A + 3x_B = 200\]\[5x_A + 7x_B = 500\]- Nutze ein Gleichungssystem:Multipliziere die erste Gleichung mit 7 und die zweite mit 3:\[14x_A + 21x_B = 1400\]\[15x_A + 21x_B = 1500\]Subtrahiere die erste Gleichung von der zweiten:\[x_A = 100\]Setze \(x_A = 100\) in eine der ursprünglichen Gleichungen ein:\[2(100) + 3x_B = 200\]\[200 + 3x_B = 200\]\[3x_B = 0\]\[x_B = 0\]Die Lösung ist also:

• \(x_A = 100\)
• \(x_B = 0\)

Maximaler Gewinn:

• \(Z = 50(100) + 70(0) = 5000\)

Aufgabe 2)

Du hast ein lineares Optimierungsproblem in der kanonischen Form gegeben:

• Ziel: Maximiere die Zielfunktion z = c₁x₁ + c₂x₂ + ... + c_nx_n
• Einschränkungen: Das System von linearen Gleichungen in der Form Ax ≤ b. Hierbei sind A eine Matrix, b ein Vektor und x sind die Entscheidungsvariablen.

Benutze den Simplex-Algorithmus, um dieses lineare Optimierungsproblem zu lösen.

a)

Führe die initiale Aufstellung der Simplex-Tableau für das folgende Optimierungsproblem durch:

Ziel: Maximiere z = 3x₁ + 2x₂

mit den Einschränkungen:

• 2x₁ + x₂ ≤ 4
• x₁ + 2x₂ ≤ 3
• x₁, x₂ ≥ 0

Stelle die erweiterte Matrix (Tableau) auf und definiere die Basisvariablen.

Lösung:

Um das gegebene lineare Optimierungsproblem mit dem Simplex-Algorithmus zu lösen, führen wir zunächst die initiale Aufstellung der Simplex-Tableau durch. Hier sind die einzelnen Schritte:

Ziel: Maximiere z = 3x₁ + 2x₂

mit den Einschränkungen:

• 2x₁ + x₂ ≤ 4
• x₁ + 2x₂ ≤ 3
• x₁, x₂ ≥ 0

Um das Problem in Form eines Simplex-Tableaus zu bringen, fügen wir Schlupfvariablen (S₁ und S₂) zu den Ungleichungen hinzu, um diese zu Gleichungen zu machen:

• 2x₁ + x₂ + S₁ = 4
• x₁ + 2x₂ + S₂ = 3

Die Schlupfvariablen (S₁ und S₂) repräsentieren die zusätzlichen Variablen, die in der anfänglichen Basis sein werden. Das Ziel ist es, z direkt in die Tableau zu integrieren.

Die initiale Simplex-Tableau sieht wie folgt aus:

Basis	x1	x2	S1	S2	B
S1	2	1	1	0	4
S2	1	2	0	1	3
z	-3	-2	0	0	0

Hierbei:

• Basis: Die aktuellen Basisvariablen (S₁ und S₂).
• x₁ und x₂: Die Entscheidungsvariablen.
• S₁ und S₂: Die Schlupfvariablen.
• B: Die Konstanten auf der rechten Seite der Gleichungen.

Die initiale Basis besteht aus den Schlupfvariablen S₁ und S₂.

b)

Setze den Simplex-Algorithmus fort, indem Du die Pivot-Operationen durchführst und das Tableau bis zur Optimallösung transformierst. Dokumentiere jeden Schritt sorgfältig. Erkläre Deine Wahl des Pivotelements in jedem Schritt und berechne die entsprechenden Änderungen im Tableau.

Lösung:

Um das lineare Optimierungsproblem vollständig zu lösen, setzen wir die Pivot-Operationen weiterhin fort und dokumentieren jeden Schritt.

Aktuelles Simplex-Tableau nach dem ersten Pivot-Schritt:

Basis	x1	x2	S1	S2	B
x1	1	\(\frac{1}{2}\)	\(\frac{1}{2}\)	0	2
S2	0	\(\frac{3}{2}\)	\(\frac{1}{2}\)	1	1
z	0	\(\frac{1}{2}\)	\(\frac{3}{2}\)	0	6

Schritt 3: Wahl des nächsten Pivotelements

Wir wählen wieder die Spalte mit dem negativsten Koeffizienten in der Zielfunktion (z), das nächste Pivotelement. In diesem Fall gibt es keinen negativen Wert in der Zielfunktion mehr, das bedeutet, die aktuelle Lösung ist optimal.

Optimale Lösung

Das Tableau zeigt, dass die optimale Lösung erreicht ist, da es keine negativen Einträge mehr in der z-Zeile gibt. Daher ist die Lösung:

• x₁ = 2
• x₂ = 0
• z = 6

Das bedeutet, dass die optimale Lösung für die Zielfunktion z = 3x₁ + 2x₂ unter den gegebenen Einschränkungen bei x₁ = 2, x₂ = 0 erreicht wird, was zu einem maximalen Wert von z = 6 führt.

Da der Simplex-Algorithmus keine weiteren negativen Einträge in der Zielfunktion (z) findet, haben wir die optimale Lösung erreicht.

c)

Nach Erreichen der Optimallösung, interpretiere die Ergebnisse:

• Was sind die optimalen Werte der Entscheidungsvariablen x₁ und x₂?
• Was ist der optimale Wert der Zielfunktion z?
• Diskutiere, was passieren würde, wenn eine der Randbedingungen verschärft würde (z.B. 2x₁ + x₂ ≤ 3 anstelle von 4).

Lösung:

Nach Erreichen der Optimallösung interpretieren wir die Ergebnisse des Simplex-Algorithmus:

Optimale Werte der Entscheidungsvariablen:

• x₁ = 2
• x₂ = 0

Optimaler Wert der Zielfunktion:

Der optimale Wert der Zielfunktion z ist:

• z = 3x₁ + 2x₂ = 3(2) + 2(0) = 6

Diskussion zur Verschärfung einer Randbedingung:

Betrachten wir, was passieren würde, wenn eine der Randbedingungen verschärft würde, beispielsweise 2x₁ + x₂ ≤ 3 anstelle von ≤ 4:

• Die ursprüngliche Einschränkung 2x₁ + x₂ ≤ 4 bedeutete, dass x₁ und x₂ auf bestimmte Weise kombiniert werden mussten, um die rechte Seite zu erfüllen (≤ 4).
• Wenn wir die Bedingung auf 2x₁ + x₂ ≤ 3 verschärfen, bedeutet dies, dass der Raum der zulässigen Lösungen eingeschränkt wird. Dies könnte die derzeitige optimale Lösung verändern, da die Lösung, die wir erreicht haben (x₁ = 2 und x₂ = 0), möglicherweise die neue Bedingung nicht erfüllen würde.
• Tatsächlich, basiert auf der neuen Randbedingung 2x₁ + x₂ ≤ 3, wäre der Ausdruck 2(2) + 0 = 4. Diese Lösung erfüllt die neue Randbedingung nicht, somit wird eine neue Zulässigkeitsprüfung notwendig.

Zusammengefasst würde die ursprüngliche optimale Lösung durch die Verschärfung der Randbedingung unzulässig; daher wäre eine erneute Anwendung des Simplex-Algorithmus erforderlich, um eine neue zulässige und optimale Lösung zu finden.

Aufgabe 3)

Hintergrund: Du hast ein nichtlineares Optimierungsproblem, das durch die folgenden Gleichungen und Ungleichungen beschrieben wird:

• Zielfunktion: Maximieren von f(x, y) = xy - x^2 - y^2
• Nebenbedingungen:
• g1(x, y) = x + 2y = 4
• g2(x, y) = x ≥ 0
• g3(x, y) = y ≥ 0

Die KKT-Bedingungen sollen auf dieses Problem angewendet werden.

a)

Formuliere die Lagrange-Funktion für das gegebene Optimierungsproblem.

Lösung:

Lagrange-Funktion:Die Formulierung der Lagrange-Funktion für das gegebene Optimierungsproblem umfasst die Integration der Zielfunktion und der Nebenbedingungen mit Hilfe von Lagrange-Multiplikatoren. Hier ist der Schritt-für-Schritt-Prozess:

• Zielfunktion: \( f(x, y) = xy - x^2 - y^2 \)
• Gleichheitsnebenbedingung: \( g_1(x, y) = x + 2y - 4 = 0 \)
• Ungleichheitsnebenbedingungen: \( g_2(x, y) = x \ge 0 \) \( g_3(x, y) = y \ge 0 \)

Die Lagrange-Funktion \(\mathcal{L}(x, y, \lambda, \mu_2, \mu_3)\) ist wie folgt definiert:

• \(\mathcal{L}(x, y, \lambda, \mu_2, \mu_3) = f(x, y) + \lambda \cdot g_1(x, y) + \mu_2 \cdot g_2(x, y) + \mu_3 \cdot g_3(x, y)\)

Durch Einsetzen der entsprechenden Funktionen ergibt sich:

• \(\mathcal{L}(x, y, \lambda, \mu_2, \mu_3) = (xy - x^2 - y^2) + \lambda \cdot (x + 2y - 4) + \mu_2 \cdot x + \mu_3 \cdot y\)

Zusammengefasst:

• \(\mathcal{L}(x, y, \lambda, \mu_2, \mu_3) = xy - x^2 - y^2 + \lambda (x + 2y - 4) + \mu_2 x + \mu_3 y\)

Hier sind \(\lambda\), \(\mu_2\) und \(\mu_3\) die Lagrange-Multiplikatoren für die Nebenbedingungen.

b)

Leite die KKT-Bedingungen für dieses Optimierungsproblem her. Schreibe die Gleichungen für die Stationaritätsbedingung, die Primale Durchführbarkeitsbedingung, die Duale Durchführbarkeitsbedingung und die Komplementäre Schlupfbedingung auf.

Lösung:

KKT-Bedingungen:Die Karush-Kuhn-Tucker (KKT)-Bedingungen für ein nichtlineares Optimierungsproblem umfassen die Stationaritätsbedingung, die Primale Durchführbarkeitsbedingung, die Duale Durchführbarkeitsbedingung und die Komplementäre Schlupfbedingung. Hier ist der detaillierte Prozess für das gegebene Problem:

• Zielfunktion: \(f(x, y) = xy - x^2 - y^2\)
• Nebenbedingungen: \(g_1(x, y) = x + 2y - 4 = 0\) \(g_2(x) = x \geq 0\) \(g_3(y) = y \geq 0\)

Wir definieren die Lagrange-Funktion \(\mathcal{L}(x, y, \lambda, \mu_2, \mu_3)\) als:

• \(\mathcal{L}(x, y, \lambda, \mu_2, \mu_3) = f(x, y) + \lambda g_1(x, y) + \mu_2 g_2(x) + \mu_3 g_3(y)\)

Herleitung der KKT-Bedingungen:

• 1. Stationaritätsbedingung: \(\frac{\partial \mathcal{L}}{\partial x} = 0\) \(\frac{\partial \mathcal{L}}{\partial y} = 0\) \(\frac{\partial \mathcal{L}}{\partial x} = y - 2x + \lambda + \mu_2 = 0\) \(\frac{\partial \mathcal{L}}{\partial y} = x - 2y + 2\lambda + \mu_3 = 0\)
• 2. Primale Durchführbarkeitsbedingung: \(g_1(x, y) = 0\) \(x + 2y - 4 = 0\)
• 3. Duale Durchführbarkeitsbedingung: \(\mu_2 \geq 0\) \(\mu_3 \geq 0\)
• 4. Komplementäre Schlupfbedingung: \(\mu_2 g_2(x) = 0\) \(\mu_3 g_3(y) = 0\) \(\mu_2 x = 0\) \(\mu_3 y = 0\)

Zusammengefasst:

• \(y - 2x + \lambda + \mu_2 = 0\)
• \(x - 2y + 2\lambda + \mu_3 = 0\)
• \(x + 2y - 4 = 0\)
• \(\mu_2 \geq 0\)
• \(\mu_3 \geq 0\)
• \(\mu_2 x = 0\)
• \(\mu_3 y = 0\)

c)

Löse das System der KKT-Bedingungen, um die optimalen Werte von x und y und der Lagrange-Multiplikatoren zu finden.

Lösung:

Lösung des Systems der KKT-Bedingungen:Um die optimalen Werte von \(x\) und \(y\) sowie der Lagrange-Multiplikatoren \(\lambda\), \(\mu_2\) und \(\mu_3\) zu finden, lösen wir das System der KKT-Bedingungen. Die KKT-Bedingungen sind:

• 1. Stationaritätsbedingung: \(y - 2x + \lambda + \mu_2 = 0\) (1) \(x - 2y + 2\lambda + \mu_3 = 0\) (2)
• 2. Primale Durchführbarkeitsbedingung: \(x + 2y - 4 = 0\) (3)
• 3. Duale Durchführbarkeitsbedingung: \(\mu_2 \geq 0\) \(\mu_3 \geq 0\)
• 4. Komplementäre Schlupfbedingung: \(\mu_2 x = 0\) (4) \(\mu_3 y = 0\) (5)

Lösen des Gleichungssystems: Schritt 1: Betrachte die Komplementäre Schlupfbedingung. Es gibt zwei Fälle zu untersuchen:

• Fall 1: \(x = 0\)
Setze \(x = 0\) in die primale Durchführbarkeitsbedingung ein: \(0 + 2y - 4 = 0\) \(2y = 4\) \(y = 2\) Setze \(x = 0\) und \(y = 2\) in die Stationaritätsbedingungen ein: (1): \(2 - 0 + \lambda + \mu_2 = 0\) \(\lambda + \mu_2 = -2\) (6) (2): \(0 - 4 + 2\lambda + \mu_3 = 0\) \(2\lambda + \mu_3 = 4\) (7) Setze \(x = 0\) in die komplementäre Schlupfbedingung ein: \(\mu_2 \cdot 0 = 0\), \(\mu_2\) ist beliebig. Nehmen wir an \(\mu_2 = 0\) Daher aus Gleichung (6): \(\lambda = -2\) (7): \(2\cdot(-2) + \mu_3 = 4\) \(-4 + \mu_3 = 4\) \(\mu_3 = 8\) Überprüfe, ob diese Werte die duale Durchführbarkeitsbedingung erfüllen: \(\mu_2 = 0\), \(\mu_3 = 8\) (beides nicht negativ), also ist die Lösung gültig. Die optimalen Werte in diesem Fall sind: \(x = 0\), \(y = 2\), \(\lambda = -2\), \(\mu_2 = 0\), \(\mu_3 = 8\).
• Fall 2: \(y = 0\)
Setze \(y = 0\) in die primale Durchführbarkeitsbedingung ein: \(x + 0 - 4 = 0\) \(x = 4\) Setze \(x = 4\) und \(y = 0\) in die Stationaritätsbedingungen ein: (1): \(0 - 8 + \lambda + \mu_2 = 0\) \(\lambda + \mu_2 = 8\) (8) (2): \(4 - 0 + 2\lambda + \mu_3 = 0\) \(4 + 2\lambda + \mu_3 = 0\) (9) Setze \(y = 0\) in die komplementäre Schlupfbedingung ein: \(\mu_3\cdot 0 = 0\), \(\mu_3\) ist beliebig. Nehmen wir an \(\mu_3 = 0\) Daher aus Gleichung (9): \(4 + 2\lambda + 0 = 0\) \(2\lambda = -4\) \(\lambda = -2\) (8): \(-2 + \mu_2 = 8\) \(\mu_2 = 10\) Überprüfe, ob diese Werte die duale Durchführbarkeitsbedingung erfüllen: \(\mu_2 = 10\), \(\mu_3 = 0\) (beides nicht negativ), also ist die Lösung gültig. Die optimalen Werte in diesem Fall sind: \(x = 4\), \(y = 0\), \(\lambda = -2\), \(\mu_2 = 10\), \(\mu_3 = 0\).

Endgültige Lösung: Es gibt zwei mögliche Lösungen für das gegebene Optimierungsproblem:

1. \(x = 0\), \(y = 2\), \(\lambda = -2\), \(\mu_2 = 0\), \(\mu_3 = 8\)
2. \(x = 4\), \(y = 0\), \(\lambda = -2\), \(\mu_2 = 10\), \(\mu_3 = 0\)

d)

Überprüfe, ob alle Voraussetzungen (wie Differenzierbarkeit und Konvexität der Zielfunktion und der Nebenbedingungen) für die Anwendung der KKT-Bedingungen in diesem Fall erfüllt sind.

Lösung:

Überprüfung der Voraussetzungen für die Anwendung der KKT-Bedingungen:Um die KKT-Bedingungen auf ein Optimierungsproblem anwenden zu können, müssen bestimmte Voraussetzungen erfüllt sein. Dazu gehören die Differenzierbarkeit und Konvexität der Zielfunktion und der Nebenbedingungen. Lass uns diese Voraussetzungen prüfen:

• 1. Differenzierbarkeit:
Die Zielfunktion und die Nebenbedingungen müssen in den betrachteten Bereichen differenzierbar sein.
• Zielfunktion: \(f(x, y) = xy - x^2 - y^2\) Diese Funktion ist polynomisch und damit im gesamten Raum \(\mathbb{R}^2\) differenzierbar.
• Nebenbedingungen:
  • \(g_1(x, y) = x + 2y - 4\) Dies ist eine lineare Gleichung und damit überall differenzierbar.
  • \(g_2(x) = x \geq 0\) Dies ist eine lineare Ungleichung und damit differenzierbar überall dort, wo \(x \geq 0\).
  • \(g_3(y) = y \geq 0\) Dies ist eine lineare Ungleichung und damit differenzierbar überall dort, wo \(y \geq 0\).
Daher sind sowohl die Zielfunktion als auch die Nebenbedingungen differenzierbar.
• 2. Konvexität:
Die KKT-Bedingungen setzen voraus, dass die Zielfunktion konkav und die Nebenbedingungen konvex sind, wenn die Funktion maximiert wird.
• Zielfunktion: \(f(x, y) = xy - x^2 - y^2\) Um die Konkavität zu überprüfen, berechnen wir die Hessematrix der Zielfunktion: \(H = \begin{pmatrix} \frac{\partial^2 f}{\partial x^2} & \frac{\partial^2 f}{\partial x \partial y} \ \frac{\partial^2 f}{\partial y \partial x} & \frac{\partial^2 f}{\partial y^2} \end{pmatrix} = \begin{pmatrix} -2 & 1 \ 1 & -2 \end{pmatrix}\) Die Eigenwerte der Hessematrix sind \(-1\) und \(-3\), beide negativ, was bedeutet, dass die Hessematrix negativ definit ist. Daher ist die Zielfunktion streng konkav.
• Nebenbedingungen:
  • \(g_1(x, y) = x + 2y - 4\) Diese Bedingung stellt eine affine Funktion dar, die immer konvex ist.
  • \(g_2(x) = x \geq 0\) Diese lineare Ungleichung stellt einen konvexen Bereich dar.
  • \(g_3(y) = y \geq 0\) Diese lineare Ungleichung stellt einen konvexen Bereich dar.
Daher sind die Nebenbedingungen ebenfalls konvex.

Schlussfolgerung: Alle Voraussetzungen für die Anwendung der KKT-Bedingungen sind in diesem Fall erfüllt, da die Zielfunktion differenzierbar und streng konkav ist und die Nebenbedingungen differenzierbar und konvex sind.

Aufgabe 4)

Betrachte ein Robotersystem, das autonom in einem Gitter von 5x5 Feldern navigiert. Jedes Feld des Gitters kann entweder frei begehbar oder ein Hindernis sein. Das Ziel des Roboters ist es, von einem Startfeld \((1,1)\) zu einem Zielgeld \((5,5)\) zu gelangen, wobei die Gesamtkosten minimiert werden. Die Bewegung im Gitter erfolgt in den vier Hauptrichtungen (oben, unten, links, rechts). Der Roboter kann auf ein begehbares Nachbarfeld wechseln, was eine Bewegungskosten von 1 verursacht. Ist ein Hindernis im Weg, sind die Kosten 3 für eine Bewegung, wobei er auf das Hindernisfeld nicht wechseln, sondern nur an Ort und Stelle die Kosten auf sich nehmen kann. Nutze die Bellman-Gleichung zur Lösung des Problems und berücksichtige sowohl deterministische als auch stochastische Szenarien.

a)

Formuliere die deterministische Bellman-Gleichung für den gegebenen Kontext. Bestimme die Wertfunktion \( V(x) \) für einen Zustand \( x \) und drücke sie in Bezug auf die Kosten- oder Nutzenfunktion \( L(x, u) \) und Zustandsübergangsfunktion \( f(x, u) \) aus.

Lösung:

Im Kontext des Robotersystems, das in einem 5x5-Gitter navigieren muss, wollen wir die deterministiche Bellman-Gleichung formulieren. Dafür müssen wir die Wertfunktion, die Kostenfunktion und die Zustandsübergangsfunktion klar definieren.

1. Wertfunktion: Die Wertfunktion V(x) stellt die minimalen Kosten dar, die erforderlich sind, um vom aktuellen Zustand x zum Zielzustand (5,5) zu gelangen.

2. Kostenfunktion: Die Kosten- oder Nutzenfunktion L(x, u) gibt die Kosten einer Aktion u im Zustand x an. Es ist wichtig zu beachten, dass diese Kosten je nach Art des Feldes variieren:

• Kosten von Bewegung auf ein begehbares Feld: 1
• Kosten bei einem Hindernis im Weg: 3

L(x, u) =

• 1, wenn u auf ein begehbares Feld führt
• 3, wenn u ein Hindernis beinhaltet (unter Annahme, dass der Roboter die Bewegung nicht ausführt und die Kosten an Ort und Stelle erträgt)

3. Zustandsübergangsfunktion: Die Zustandsübergangsfunktion f(x, u) bestimmt den nächsten Zustand basierend auf dem aktuellen Zustand x und der gewählten Aktion u. In einem einfachen Gittermodell können die möglichen Zustände durch Bewegungen in vier Hauptrichtungen beschrieben sein (oben, unten, links, rechts).

Die deterministische Bellman-Gleichung kann also als folgt geschrieben werden:

V(x) = min(L(x, u) + V(f(x, u))) wobei

• u eine mögliche Aktion im Zustand x ist,
• L(x, u) die Kostenfunktion ist und V(f(x, u)) der zukünftige Kostenwert des Systems im neuen Zustand f(x, u) nach der Aktion u ist.

Diese Gleichung besagt im Wesentlichen, dass die Kosten im aktuellen Zustand x gleich den minimalen unmittelbaren Kosten L(x, u) zuzüglich der zukünftigen Kosten V(f(x, u)) sind, wenn die optimale Aktion u gewählt wird.

c)

Implementiere einen Algorithmus in Python für das deterministische Szenario unter Verwendung der Value Iteration. Dein Algorithmus sollte die Wertfunktion iterativ aktualisieren, bis er konvergiert. Initialisiere die Wertfunktion mit 0 für das Zielfeld \((5,5)\) und unendlich für alle anderen Felder.

Lösung:

Um das deterministische Szenario mit Hilfe der Value Iteration in Python zu lösen, können wir den folgenden Algorithmus implementieren. Zuerst initialisieren wir die Wertfunktion, setzen alle Werte außer dem Zielfeld auf unendlich, und aktualisieren die Werte iterativ, bis die Funktion konvergiert.

Hier ist der Python-Code, der dies implementiert:

import numpy as np# Dimensions des Gittersn, m = 5, 5ziel = (4, 4)# Initialisiere die WertfunktionV = np.full((n, m), float('inf'))V[ziel] = 0  # Zielfeld# Bewegungsrichtungen: oben, unten, links, rechtsrichtungen = [(-1, 0), (1, 0), (0, -1), (0, 1)]# Kosten für eine Bewegungbewegungskosten = 1hinderniskosten = 3def ist_valide(position):    return 0 <= position[0] < n and 0 <= position[1] < m# Beispielhindernisse im Gitterhindernisse = {(2, 2), (3, 3)}def value_iteration(V, max_iter=1000, tol=1e-5):    for _ in range(max_iter):        V_alt = V.copy()        max_delta = 0        for i in range(n):            for j in range(m):                if (i, j) == ziel:                    continue                kosten = []                for r in richtungen:                    neuer_zustand = (i + r[0], j + r[1])                    if ist_valide(neuer_zustand):                        if neuer_zustand in hindernisse:                            kosten.append(hinderniskosten + V_alt[i, j])  # Kosten an Ort und Stelle                        else:                            kosten.append(bewegungskosten + V_alt[neuer_zustand])                V[i, j] = min(kosten)                max_delta = max(max_delta, abs(V[i, j] - V_alt[i, j]))        if max_delta < tol:            break    return V# Führe Value Iteration ausV_konvergiert = value_iteration(V)# Ausgabe der resultierende Wertfunktiondrucke(V_konvergiert.round(2))

Der obige Code implementiert die Value Iteration für das deterministische Szenario:

• Wir beginnen mit der Initialisierung der Wertfunktion, indem alle Felder mit unendlich und das Zielfeld mit 0 belegt werden.
• Wir definieren die Bewegungsrichtungen (oben, unten, links, rechts) und deren Kosten.
• Die Funktion ist_valide überprüft, ob eine Position innerhalb der Grenzen des Gitters liegt.
• Die value_iteration-Funktion wird iterativ ausgeführt, wobei die Wertfunktion V durch die Mindestkosten der möglichen Bewegungen aktualisiert wird.
• Die Schleife endet, wenn die Wertänderung unter einem definierten Toleranzwert liegt oder die maximale Anzahl von Iterationen erreicht ist.
• Am Ende wird die konvergierte Wertfunktion ausgegeben.

d)

Diskutiere, wie der Policy-Iteration-Algorithmus genutzt werden könnte, um eine optimale Politik für den Roboter zu finden. Beschreibe die Hauptschritte des Algorithmus und hebe die Unterschiede zur Value Iteration hervor.

Lösung:

Um eine optimale Politik (Policy) für den Roboter in einem 5x5-Gitter zu finden und die Gesamtkosten zu minimieren, kann der Policy-Iteration-Algorithmus verwendet werden. Diese Methode besteht im Wesentlichen aus zwei Hauptschritten: der Politikbewertung und der Politikverbesserung. Im Folgenden wird der Policy-Iteration-Algorithmus erläutert und im Vergleich zur Value Iteration hervorgehoben.

Policy-Iteration-Algorithmus:

Hauptschritte:

• 1. Initialisierung: Initialisiere die Politik \(\pi(x)\) zufällig für jeden Zustand \( x \) und die Wertfunktion \( V(x) \) für alle Zustände \( x \).
• 2. Politikbewertung (Policy Evaluation): Schätze die Wertfunktion \( V^{\pi}(x) \) für die aktuelle Politik \( \pi \), indem wiederholt die Bellman-Gleichung für die Politik gelöst wird, bis Konvergenz erreicht ist.

  V^{\pi}(x) = L(x, \pi(x)) + \sum_{x'} P(x'|x, \pi(x)) V^{\pi}(x')

• 3. Politikverbesserung (Policy Improvement): Aktualisiere die Politik, indem für jeden Zustand \( x \) die Aktion gewählt wird, die die zukünftigen Kosten minimiert:

  \pi'(x) = \arg\min_u \bigg(L(x, u) + \sum_{x'} P(x'|x, u) V^{\pi}(x')\bigg)

  Falls die neue Politik \( \pi' \) gleich der alten Politik \( \pi \) ist, dann habe eine optimale Politik gefunden und der Algorithmus endet. Andernfalls setze \( \pi \) auf \( \pi' \) und gehe zurück zu Schritt 2.

Unterschiede zur Value Iteration:

• Iterative Schritte: In der Policy Iteration wird zunächst eine Politik festgelegt und bewertet, und anschließend wird die Politik verbessert. Diese beiden Schritte werden iterativ wiederholt. Hingegen aktualisiert die Value Iteration in jedem Schritt sowohl die Wertfunktion als auch indirekt die Politik.
• Konvergenzgeschwindigkeit: Policy Iteration konvergiert oft schneller als Value Iteration, da sie dazu neigt, mit jeder Iteration größere Fortschritte zu machen. Die Politikbewertung kann jedoch rechenintensiv sein, da sie mehrere Iterationen erfordert, um die Wertfunktion zu konvergieren.
• Komplexität: Die Wertiteration ist einfacher zu implementieren, da sie nur eine einzige iterierte Schleife benötigt, um die Wertfunktion und die implizite Politik zu aktualisieren.

Zusammenfassung: Der Policy-Iteration-Algorithmus enthält beide Schritte, Politikbewertung und Politikverbesserung, die iterativ ausgeführt werden, um eine optimale Politik für den Roboter zu finden. Im Gegensatz dazu konzentriert sich die Value Iteration darauf, die Wertfunktion direkt zu aktualisieren, wobei die Politik implizit verbessert wird. Policy Iteration tendiert dazu, schneller zu konvergieren, während Value Iteration aufgrund ihrer Einfachheit leichter zu implementieren ist. Welche Methode verwendet wird, hängt von den spezifischen Anforderungen und Ressourcen ab, die zur Verfügung stehen.