Einführung in die Optimierung - Exam.pdf

Aufgabe 1)

Lineare Programmierung:In dieser Aufgabe betrachten wir ein lineares Programmierungsproblem zur Optimierung der Produktionsplanung eines Unternehmens. Das Unternehmen stellt zwei Produkte her: Produkt A und Produkt B. Die Produktionskapazitäten und die benötigten Ressourcen sind wie folgt gegeben:

• Für die Herstellung von Produkt A werden 2 Stunden in Arbeitszentrum 1 und 1 Stunde in Arbeitszentrum 2 benötigt.
• Für die Herstellung von Produkt B werden 1 Stunde in Arbeitszentrum 1 und 3 Stunden in Arbeitszentrum 2 benötigt.
• Arbeitszentrum 1 hat insgesamt 100 Stunden zur Verfügung und Arbeitszentrum 2 hat insgesamt 90 Stunden zur Verfügung.
• Der Gewinn pro Einheit Produkt A beträgt 40 Euro und der Gewinn pro Einheit Produkt B beträgt 50 Euro.

a)

a) Formuliere die Zielfunktion und die Nebenbedingungen für das oben beschriebene Problem.

Lösung:

Subaufgabe a:

Um das Problem als lineare Programmierung zu formulieren, müssen wir die Zielfunktion und die Nebenbedingungen aufstellen.

Wir wollen den Gesamtgewinn maximieren. Der Gewinn pro Einheit von Produkt A beträgt 40 Euro und der Gewinn pro Einheit von Produkt B beträgt 50 Euro. Bezeichnen wir die Anzahl der hergestellten Einheiten von Produkt A mit x und die Anzahl der hergestellten Einheiten von Produkt B mit y, dann ergibt die Zielfunktion:

maximiere Z = 40x + 50y

Die Nebenbedingungen ergeben sich aus den verfügbaren Produktionskapazitäten in den beiden Arbeitszentren:

• Die gesamte Zeit, die in Arbeitszentrum 1 verwendet wird, darf 100 Stunden nicht überschreiten. Da 2 Stunden für jede Einheit von Produkt A und 1 Stunde für jede Einheit von Produkt B benötigt werden, ergibt sich folgende Nebenbedingung:

2x + y ≤ 100

• Die gesamte Zeit, die in Arbeitszentrum 2 verwendet wird, darf 90 Stunden nicht überschreiten. Da 1 Stunde für jede Einheit von Produkt A und 3 Stunden für jede Einheit von Produkt B benötigt werden, ergibt sich folgende Nebenbedingung:

x + 3y ≤ 90

• Die Anzahl der hergestellten Einheiten von Produkt A und Produkt B kann nicht negativ sein. Das bedeutet:
• x ≥ 0
• y ≥ 0

Zusammengefasst ergibt sich das folgende lineare Programm:

Zielfunktion:

maximiere Z = 40x + 50y

Nebenbedingungen:

• 2x + y ≤ 100
• x + 3y ≤ 90
• x ≥ 0
• y ≥ 0

b)

b) Zeichne das Machbarkeitsgebiet in einem 2D-Koordinatensystem und markiere die zulässigen Lösungen.

Lösung:

Subaufgabe b:

Um das Machbarkeitsgebiet in einem 2D-Koordinatensystem zu zeichnen, brauchen wir die Ungleichungen der Nebenbedingungen und setzen sie in ein Koordinatensystem um:

• 2x + y ≤ 100
• x + 3y ≤ 90
• x ≥ 0
• y ≥ 0

Folge den folgenden Schritten, um das Machbarkeitsgebiet zu zeichnen:

Zeichne die Ungleichungen als Gleichungen in ein Koordinatensystem:

• 2x + y = 100
• x + 3y = 90
• x = 0
• y = 0

Hier sind die Schnittpunkte der Linien mit den Achsen wichtig:

• Für 2x + y = 100: Wenn x = 0, dann ist y = 100. (Punkt: (0, 100))Wenn y = 0, dann ist x = 50. (Punkt: (50, 0))
• Für x + 3y = 90: Wenn x = 0, dann ist y = 30. (Punkt: (0, 30))Wenn y = 0, dann ist x = 90. (Punkt: (90, 0))

Zeichne die Linien in das Koordinatensystem. Orientiere Dich dabei an den Schnittpunkten der Linien mit den Achsen.

Bestimme das Machbarkeitsgebiet, indem du die Bereiche identifizierst, die alle Nebenbedingungen erfüllen. Die zulässigen Lösungen sind im Bereich, der von den Ungleichungen begrenzt wird.

Siehe Abbildung für eine grafische Darstellung des Machbarkeitsgebiets:

In der Abbildung markiere die Schnittpunkte, die innerhalb der begrenzenden Linien liegen. Diese markieren die zulässigen Lösungen:

• Punkt A: (0, 30)
• Punkt B: (50, 0)
• Punkt C: (45, 15)

Diese Punkte entsprechen den zulässigen Lösungen, die im Machbarkeitsgebiet liegen.

c)

c) Berechne die Eckenpunkte des Machbarkeitsgebiets und bestimme den optimalen Punkt durch Einsetzen in die Zielfunktion.

Lösung:

Subaufgabe c:

Um den optimalen Punkt zur Maximierung des Gesamtgewinns zu finden, müssen wir die Eckenpunkte des Machbarkeitsgebiets berechnen und diese in die Zielfunktion einsetzen. Die Eckenpunkte sind die Schnittpunkte der Ungleichungen.

Wir haben die folgenden Ungleichungen:

• 2x + y ≤ 100
• x + 3y ≤ 90
• x ≥ 0
• y ≥ 0

Die Schnittpunkte der Linien sind die Eckpunkte des Machbarkeitsgebiets. Lassen Sie uns die Punkte berechnen:

Punkt A: Schnittpunkt von 2x + y = 100 und x = 0Setze x = 0 in die Gleichung ein:y = 100⇒ Punkt A: (0, 100)

Punkt B: Schnittpunkt von 2x + y = 100 und x + 3y = 90Lösen wir das Gleichungssystem:

• 2x + y = 100
• x + 3y = 90

Multipliziere die zweite Gleichung mit 2:

• 2x + y = 100
• 2x + 6y = 180

Subtrahiere die erste Gleichung von der zweiten:

• (2x + 6y) - (2x + y) = 180 - 100
• 5y = 80
• y = 16

Setze y = 16 in x + 3y = 90 ein:

• x + 3(16) = 90
• x + 48 = 90
• x = 42
⇒ Punkt B: (42, 16)

Punkt C: Schnittpunkt von x + 3y = 90 und y = 0Setze y = 0 in die Gleichung ein:x = 90⇒ Punkt C: (90, 0)

Punkt D: Schnittpunkt von 2x + y = 100 und y = 0Setze y = 0 in die Gleichung ein:2x = 100x = 50⇒ Punkt D: (50, 0)

Zusammengefasst sind die Eckenpunkte: (0, 100), (42, 16), (90, 0) und (50, 0).

Schritt 2: Einsetzen der Eckenpunkte in die Zielfunktion

Die Zielfunktion lautet: Z = 40x + 50y

Berechnen wir den Wert der Zielfunktion für jeden Eckpunkt:

• Punkt A: (0, 100)Z = 40(0) + 50(100) = 0 + 5000 = 5000 Euro
• Punkt B: (42, 16)Z = 40(42) + 50(16) = 1680 + 800 = 2480 Euro
• Punkt C: (90, 0)Z = 40(90) + 50(0) = 3600 + 0 = 3600 Euro
• Punkt D: (50, 0)Z = 40(50) + 50(0) = 2000 + 0 = 2000 Euro
Schritt 3: Bestimmung des optimalen Punkts

Der maximale Wert der Zielfunktion wird bei Punkt A: (0, 100) erreicht. Somit ist der optimale Punkt (0, 100), und der maximale Gesamtgewinn beträgt 5000 Euro.

d)

d) Beschreibe den Simplex-Algorithmus und wende ihn auf das oben formulierte Problem an, um den optimalen Gewinn zu berechnen. Berücksichtige dabei die Startbasis und etwaige Pivot-Operationen.

Lösung:

Subaufgabe d:

Um den Simplex-Algorithmus zu verstehen und anzuwenden, müssen wir zunächst seine Funktionsweise und die einzelnen Schritte erklären.

Schritt-für-Schritt-Anleitung des Simplex-Algorithmus:

Der Simplex-Algorithmus ist eine iterative Methode zur Lösung linearer Programmierungsprobleme. Sein Ziel ist es, die Zielfunktion zu maximieren oder zu minimieren, indem er sich entlang der Ecken des Machbarkeitsgebiets bewegt, bis die optimale Lösung gefunden ist.

Schritt 1: Problemformulierung in Standardform

Formuliere das Problem in der Standardform:

• Zielfunktion: Maximiere Z = 40x + 50y
• Nebenbedingungen:
• 2x + y ≤ 100
• x + 3y ≤ 90
• x ≥ 0
• y ≥ 0

Wir müssen die Ungleichungen in Gleichungen umwandeln, indem wir Schlupfvariablen hinzufügen:

• 2x + y + s1 = 100
• x + 3y + s2 = 90
• x, y, s1, s2 ≥ 0

Die Standardform lautet somit:

• Zielfunktion: Maximiere Z = 40x + 50y + 0s1 + 0s2
• Nebenbedingungen:
• 2x + y + s1 = 100
• x + 3y + s2 = 90
Schritt 2: Initiale Simplex-Tabelle aufstellen

Die initiale Simplex-Tabelle sieht wie folgt aus:

| Basis | x  | y  | s1 | s2 | Rechte Seite   ||------|----|----|----|----|--------------||  s1  |  2 |  1 |  1 |  0 | 100          ||  s2  |  1 |  3 |  0 |  1 |  90          ||  Z   | -40| -50|  0 |  0 |  0           |

1. Wähle die Einstiegsvariable: Die Variable mit dem höchsten negativen Koeffizienten in der Zielfunktion. In diesem Fall ist es y mit -50.

2. Berechne die Pivot-Spalte: Für jede Zeile (außer die Zielfunktion), dividiere die rechte Seite durch den Koeffizienten der Pivot-Spalte. Wähle den kleinsten positiven Wert.

| Basis | x  | y  | s1 | s2 | Rechte Seite   ||------|----|----|----|----|--------------||  s1  |  2 |  1 |  1 |  0 | 100 / 1 = 100 ||  s2  |  1 |  3 |  0 |  1 |  90 / 3 = 30  ||  Z   | -40| -50|  0 |  0 |  0               |

Die kleinste positive Ratio ist 30, also ist s2 die Pivot-Zeile.

3. Pivotiere, um die neue Tabelle zu erhalten:

| Basis | x  | y  | s1 | s2 | Rechte Seite ||------|----|----|----|----|--------------|| y    | 1/3|  1 |  0 | 1/3|  30          || s1   | 5/3|  0 |  1 | -1/3| 40          || Z    | 10 |  0 |  0 | 50/3| 1500       |

In der neuen Table ist kein negativer Koeffizient mehr in der Zielfunktion vorhanden. Die Lösung ist somit optimal.

• Die optimale Lösung ist x = 0, y = 30, was einen maximalen Gewinn von 1500 Euro ergibt.

Zusammenfassung:

Durch Anwenden des Simplex-Algorithmus auf das gegebene Problem wurde ein maximaler Gewinn von 1500 Euro bei der Produktion von 30 Einheiten von Produkt B und null Einheiten von Produkt A erzielt.

Aufgabe 2)

Gegeben: Ein lineares Programm in Standardform:

• Zielfunktion: Maximiere \(z = c_1 x_1 + c_2 x_2 + c_3 x_3\)
• Beschränkungen:
  • \(a_{11}x_1 + a_{12}x_2 + a_{13}x_3 \leq b_1\)
  • \(a_{21}x_1 + a_{22}x_2 + a_{23}x_3 \leq b_2\)
• \(x_1, x_2, x_3 \geq 0\)

a)

a) Setze das lineare Programm zuerst in die Standardform um. Füge Schlupfvariablen ein, um die Ungleichungen in Gleichungen zu verwandeln. Zeige das zugehörige Initial-Tableau. Hinweise:

• Füge s1 und s2 als Schlupfvariablen zu den Ungleichungen hinzu.
• Stelle das Tableau dar.

Lösung:

Gegeben: Ein lineares Programm in Standardform:

• Zielfunktion: Maximiere \( z = c_1 x_1 + c_2 x_2 + c_3 x_3 \)
• Beschränkungen:
  • \( a_{11}x_1 + a_{12}x_2 + a_{13}x_3 \leq b_1 \)
  • \( a_{21}x_1 + a_{22}x_2 + a_{23}x_3 \leq b_2 \)
• \( x_1, x_2, x_3 \geq 0 \)

Verwende das Simplex-Verfahren, um die optimale Lösung zu finden.

a) Setze das lineare Programm zuerst in die Standardform um. Füge Schlupfvariablen ein, um die Ungleichungen in Gleichungen zu verwandeln. Zeige das zugehörige Initial-Tableau.

• Füge \( s_1 \) und \( s_2 \) als Schlupfvariablen zu den Ungleichungen hinzu.
• Stelle das Tableau dar.

Um das lineare Programm in die Standardform umzuwandeln und die Ungleichungen in Gleichungen zu verwandeln, fügen wir Schlupfvariablen \( s_1 \) und \( s_2 \) ein:

• Ersetze die Ungleichungen durch Gleichungen:

\[ \text{Beschränkungen:} \] \[ a_{11}x_1 + a_{12}x_2 + a_{13}x_3 + s_1 = b_1 \] \[ a_{21}x_1 + a_{22}x_2 + a_{23}x_3 + s_2 = b_2 \] \[ x_1, x_2, x_3, s_1, s_2 \geq 0 \] Zielfunktion: \[ z - c_1 x_1 - c_2 x_2 - c_3 x_3 = 0 \] Initial-Tableau:

 \begin{array}{c|cccccc} \text{Basisvariable} & x_1 & x_2 & x_3 & s_1 & s_2 & \text{Rechts} \ \text{Seite} \ \hline \ s_1 & a_{11} & a_{12} & a_{13} & 1 & 0 & b_1 \ s_2 & a_{21} & a_{22} & a_{23} & 0 & 1 & b_2 \ \hline \ z & -c_1 & -c_2 & -c_3 & 0 & 0 & 0 \ \end{array} 

So sieht das Initial-Tableau für das Simplex-Verfahren aus.

b)

b) Führe einen vollständigen Iterationsschritt des Simplex-Verfahrens durch, beginnend mit dem Initial-Tableau, dass Du in Teil (a) aufgestellt hast. Dokumentiere dabei genau die Pivot-Operationen und überprüfe die Abbruchkriterien. Bestimme, ob die aktuelle Lösung optimal ist oder nicht.Hinweise:

• Identifiziere die Pivotspalte und Pivotreihe.
• Führe die Pivot-Operation durch.
• Überprüfe, ob alle Koeffizienten der Zielfunktion nicht-negativ sind.
• Erläutere, warum die Lösung optimal ist oder ob weitere Schritte notwendig sind.

Lösung:

Gegeben: Ein lineares Programm in Standardform:

• Zielfunktion: Maximiere \( z = c_1 x_1 + c_2 x_2 + c_3 x_3 \)
• Beschränkungen:
  • \( a_{11}x_1 + a_{12}x_2 + a_{13}x_3 \leq b_1 \)
  • \( a_{21}x_1 + a_{22}x_2 + a_{23}x_3 \leq b_2 \)
• \( x_1, x_2, x_3 \geq 0 \)

Verwende das Simplex-Verfahren, um die optimale Lösung zu finden.

b) Führe einen vollständigen Iterationsschritt des Simplex-Verfahrens durch, beginnend mit dem Initial-Tableau, das Du in Teil (a) aufgestellt hast. Dokumentiere dabei genau die Pivot-Operationen und überprüfe die Abbruchkriterien. Bestimme, ob die aktuelle Lösung optimal ist oder nicht.

• Identifiziere die Pivotspalte und Pivotreihe.
• Führe die Pivot-Operation durch.
• Überprüfe, ob alle Koeffizienten der Zielfunktion nicht-negativ sind.
• Erläutere, warum die Lösung optimal ist oder ob weitere Schritte notwendig sind.

Schritte zur Durchführung eines vollständigen Iterationsschritts:

Hier ist unser Initial-Tableau aus Teil (a):

 \begin{array}{c|cccccc} \text{Basisvariable} & x_1 & x_2 & x_3 & s_1 & s_2 & \text{Rechts} \ \text{Seite} \ \hline \ s_1 & a_{11} & a_{12} & a_{13} & 1 & 0 & b_1 \ s_2 & a_{21} & a_{22} & a_{23} & 0 & 1 & b_2 \ \hline \ z & -c_1 & -c_2 & -c_3 & 0 & 0 & 0 \ \end{array} 

1. Pivotsäule identifizieren: Wähle die Spalte mit dem negativsten Wert in der Zielfunktion (Z-Zeile). Dies gibt die Variable an, die in die Basis kommen soll. Angenommen, \( -c_1 \) ist der negativste Wert, dann wählen wir die erste Spalte (\( x_1 \)).
2. Pivotreihe identifizieren: Berechne das Verhältnis der rechten Seite zur entsprechenden Eintrags in der Pivotspalte für alle positiven Einträge in der Pivotspalte. Wähle die kleinste nicht-negative Quote. Dies identifiziert die Variable, die die Basis verlässt.
   • \( \frac{b_1}{a_{11}} \)
   • \( \frac{b_2}{a_{21}} \)
   Angenommen \( \frac{b_1}{a_{11}} \) ist das kleinste Verhältnis, dann wählen wir die erste Zeile.
3. Pivot-Operation durchführen: Die Pivot-Operation normalisiert den Pivoteintrag auf 1 und jede andere Zeile wird so modifiziert, dass entweder 0 oder 1 in der Pivotspalte erhalten wird. Angenommen, unser Pivoteintrag ist \( a_{11} \):

    \begin{array}{c|cccccc} \text{Neue Basisvariable} & x_1 & x_2 & x_3 & s_1 & s_2 & \text{Rechts} \ \text{Seite} \ \hline \ x_1 & 1 & \frac{a_{12}}{a_{11}} & \frac{a_{13}}{a_{11}} & \frac{1}{a_{11}} & 0 & \frac{b_1}{a_{11}} \ s_2 & 0 & \text{(neuer Wert)} & \text{(neuer Wert)} & \text{(neuer Wert)} & 1 & \text{neuer Wert} \ \hline \ z & 0 & \text{(neuer Wert)} & \text{(neuer Wert)} & \text{(neuer Wert)} & 0 & \text{neuer Wert} \ \end{array} 

   **Aktualisierungen:**
   • Neue Zeile für \( s_1 \): \( \frac{s_1}{a_{11}} \) und \( \frac{b_1}{a_{11}} \)
   • Aktualisiere die zweite Zeile (\( s_2 \)): Neue \( s_2 = s_2 - a_{21} \times \text{(neue } s_1 \text{ Zeile)} \)
   • Aktualisiere die Zielfunktionszeile: \( z = z + c_1 \times \text{(neue } s_1 \text{ Zeile)} \)
4. Überprüfe die Abbruchkriterien: Überprüfe, ob alle Koeffizienten der Zielfunktion (Z-Zeile) nicht-negativ sind. Wenn ja, ist die Lösung optimal, andernfalls sind weitere Iterationen erforderlich.
5. Resultat interpretieren: Wenn nach der Pivot-Operation alle Koeffizienten in der Zielfunktionszeile nicht-negativ sind, haben wir eine optimale Lösung gefunden. Andernfalls ist eine weitere Iteration notwendig.

Veranschaulichung der Pivot-Operation:

Wir nehmen an, dass nach der Pivot-Operation das Tableau wie folgt aussieht:

 \begin{array}{c|cccccc} \text{Basisvariable} & x_1 & x_2 & x_3 & s_1 & s_2 & \text{Rechts} \ \text{Seite} \ \hline \ x_1 & 1 & \frac{a_{12}}{a_{11}} & \frac{a_{13}}{a_{11}} & \frac{1}{a_{11}} & 0 & \frac{b_1}{a_{11}} \ s_2 & 0 & \text{(neuer Wert)} & \text{(neuer Wert)} & \text{(neuer Wert)} & 1 & \text{neuer Wert} \ \hline \ z & 0 & \text{(neuer Wert)} & \text{(neuer Wert)} & \text{(neuer Wert)} & 0 & \text{neuer Wert} \ \end{array} 

Dies kennzeichnet unsere neue Basis.

Daher kann der iterative Prozess fortgesetzt werden, bis alle Koeffizienten der Zielfunktion nicht-negativ sind.

Aufgabe 3)

DualitätstheorieDie Dualitätstheorie bezieht sich auf das Konzept, dass jedem Optimierungsproblem ein Duales Problem zugeordnet ist. Lösungen des Dualen Problems liefern Grenzen für die Lösungen des Primärproblems.

• Für ein lineares Optimierungsproblem (Primärproblem) in Standardform gibt es ein entsprechendes Duales Problem.
• Primärproblem (Standardform):
  • \[ \min c^Tx \quad \text{s.t.} \quad Ax \geq b, \quad x \geq 0 \]
• Entsprechendes Duales Problem:
  • \[ \max b^Ty \quad \text{s.t.} \quad A^Ty \leq c, \quad y \geq 0 \]
• Schwache Dualität:
  • Wenn \(x\) zulässige Lösung für das Primärproblem und \(y\) zulässige Lösung für das Dualproblem ist, dann gilt \(c^Tx \, \geq \, b^Ty\).
• Starke Dualität:
  • Wenn \(x^*\) optimale Lösung für das Primärproblem und \(y^*\) optimale Lösung für das Dualproblem ist, dann gilt \(c^Tx^* \, = \, b^Ty^*\).
• Komplementäre Schlupfbedingungen:
  • \[ y_i (a_i^T x - b_i) = 0 \quad \forall i \]

b)

Überprüfen die Schwache Dualität für die zulässigen Lösungen \(x = (1, 1.5)\) und \(y = (0.5, 1)\) aus dem Primär- und Dualproblem, die Du im ersten Unterpunkt formuliert hast.

Lösung:

Um die schwache Dualität zu überprüfen, müssen wir die zulässigen Lösungen \( x = (1, 1.5) \) für das Primärproblem und \( y = (0.5, 1) \) für das Dualproblem in die jeweiligen Zielfunktionen einsetzen und prüfen, ob die Bedingung erfüllt ist:

Für das Primärproblem lautet die Zielfunktion:

• \( c^T x = 3x_1 + 5x_2 \)

Setzen wir die Werte von \( x \) ein:

• \( c^T x = 3(1) + 5(1.5) = 3 + 7.5 = 10.5 \)

Für das Dualproblem lautet die Zielfunktion:

• \( b^T y = 4y_1 + 6y_2 \)

Setzen wir die Werte von \( y \) ein:

• \( b^T y = 4(0.5) + 6(1) = 2 + 6 = 8 \)

Laut der schwachen Dualität sollte gelten:

• \( c^T x \geq b^T y \)

Einsetzen der berechneten Werte:

• \( 10.5 \geq 8 \)

Da dies zutrifft, ist die Bedingung der schwachen Dualität erfüllt.

Somit ist die schwache Dualität für die zulässigen Lösungen \( x = (1, 1.5) \) und \( y = (0.5, 1) \) gegeben.

c)

Angenommen, \(x^* = (1, 1.5)\) ist die optimale Lösung für das Primärproblem und \(y^* = (0.5, 1)\) ist die optimale Lösung für das Dualproblem. Überprüfe, ob diese Lösungen die starke Dualität erfüllen.

Lösung:

Die starke Dualität besagt, dass wenn \(x^*\) die optimale Lösung für das Primärproblem und \(y^*\) die optimale Lösung für das Dualproblem ist, dann gilt:

• \(c^T x^* = b^T y^*\)

Hier sind die gegebenen optimalen Lösungen:

• Primärproblem: \(x^* = (1, 1.5)\)
• Dualproblem: \(y^* = (0.5, 1)\)

Wir berechnen nun die Zielfunktionswerte für beide Probleme:

Zielfunktion des Primärproblems:

• \(c^T x^* = 3x_1 + 5x_2\)
• Setzen wir die Werte von \(x^*\) ein:
• \(c^T x^* = 3(1) + 5(1.5) = 3 + 7.5 = 10.5\)

Zielfunktion des Dualproblems:

• \(b^T y^* = 4y_1 + 6y_2\)
• Setzen wir die Werte von \(y^*\) ein:
• \(b^T y^* = 4(0.5) + 6(1) = 2 + 6 = 8\)

Um die starke Dualität zu überprüfen, muss gelten:

• \(c^T x^* = b^T y^*\)

Einsetzen der berechneten Werte:

• \(10.5 = 8\)

Da dies nicht zutrifft, erfüllen die gegebenen Lösungen \(x^* = (1, 1.5)\) und \(y^* = (0.5, 1)\) nicht die Bedingung der starken Dualität.

d)

Zeige, dass die komplementären Schlupfbedingungen für die gefundenen optimalen Lösungen \(x^*\) und \(y^*\) erfüllt sind.

Lösung:

Um nachzuweisen, dass die komplementären Schlupfbedingungen für die gefundenen optimalen Lösungen \(x^*\) und \(y^*\) erfüllt sind, müssen wir überprüfen, ob die Bedingung:

• \(y_i (a_i^T x - b_i) = 0 \quad \forall i\)

für alle \(i\) erfüllt ist. Die vorkommenden Elemente sind:

• \(x^* = (1, 1.5)\)
• \(y^* = (0.5, 1)\)
• \(A = \begin{bmatrix} 1 & 2 \ 3 & 2 \end{bmatrix}\)
• \(b = \begin{bmatrix} 4 \ 6 \end{bmatrix}\)

Berechnen wir nun die komplementären Schlupfbedingungen für jedes \(i\):

Für \(i = 1\):

• \(a_1^T x^* = 1 \cdot 1 + 2 \cdot 1.5 = 1 + 3 = 4\)
• \(b_1 = 4\)
• \(y_1 (a_1^T x^* - b_1) = 0.5 (4 - 4) = 0.5 \cdot 0 = 0\)

Für \(i = 2\):

• \(a_2^T x^* = 3 \cdot 1 + 2 \cdot 1.5 = 3 + 3 = 6\)
• \(b_2 = 6\)
• \(y_2 (a_2^T x^* - b_2) = 1 (6 - 6) = 1 \cdot 0 = 0\)

Da beide komplementären Schlupfbedingungen erfüllt sind, gilt:

• \(y_i (a_i^T x - b_i) = 0 \quad \forall i\)

Somit sind die komplementären Schlupfbedingungen für die optimalen Lösungen \(x^* = (1, 1.5)\) und \(y^* = (0.5, 1)\) erfüllt.