Einführung in die Optimierung - Exam.pdf

Aufgabe 1)

Ein Unternehmen produziert zwei Produkte, P1 und P2, unter Verwendung von zwei Rohstoffen, R1 und R2. Um diese Produkte zu produzieren, benötigt das Unternehmen jeweils Arbeitsstunden von R1 und R2. Die folgenden Angaben sind bekannt:

• Produkt P1 benötigt 2 Einheiten von R1 und 3 Einheiten von R2.
• Produkt P2 benötigt 4 Einheiten von R1 und 1 Einheit von R2.
• Der gesamte verfügbare Vorrat an R1 beträgt 8 Einheiten und an R2 beträgt 6 Einheiten.
• Der Gewinn für Produkt P1 beträgt 3 Einheiten und für Produkt P2 beträgt 2 Einheiten.

a)

Formuliere dieses Problem als ein lineares Optimierungsproblem. Bestimme die Zielfunktion und die linearen Nebenbedingungen.

Lösung:

Um das gegebene Problem als lineares Optimierungsproblem zu formulieren, müssen wir die Zielfunktion und die Nebenbedingungen definieren.

• Zielfunktion: Wir möchten den Gewinn maximieren. Der Gewinn für Produkt P1 beträgt 3 Einheiten und für Produkt P2 2 Einheiten. Wir können dies als:

Maximiere Z = 3x1 + 2x2

• Nebenbedingungen:

• Die verfügbare Menge an Rohstoff R1 beträgt 8 Einheiten. Dies übersetzt sich zu:

2x1 + 4x2 ≤ 8

• Die verfügbare Menge an Rohstoff R2 beträgt 6 Einheiten. Dies übersetzt sich zu:

3x1 + x2 ≤ 6

• Außerdem können negative Produktionsmengen nicht realisiert werden:

x1 ≥ 0 x2 ≥ 0

Zusammengefasst ergeben sich die folgenden Bedingungen:

• Maximiere Z = 3x1 + 2x2 unter den Nebenbedingungen:

• 2x1 + 4x2 ≤ 8
• 3x1 + x2 ≤ 6
• x1 ≥ 0
• x2 ≥ 0

b)

Wende den Simplex-Algorithmus an, um die optimale Lösung des linearen Optimierungsproblems zu finden. Zeige alle Zwischenschritte und erläutere die erhaltene Lösung.

Lösung:

Um den Simplex-Algorithmus anzuwenden und die optimale Lösung für das lineare Optimierungsproblem zu finden, definieren wir die Zielfunktion und die Nebenbedingungen. Das Problem lautet:

Zielfunktion:

Maximiere Z = 3x1 + 2x2

unter den Nebenbedingungen:

• 2x1 + 4x2 ≤ 8
• 3x1 + x2 ≤ 6
• x1 ≥ 0
• x2 ≥ 0

Um diese Ungleichungen in Gleichungen umzuwandeln, führen wir Schlupfvariablen (s1 und s2) ein:

• 2x1 + 4x2 + s1 = 8
• 3x1 + x2 + s2 = 6

Die Zielfunktion und die Nebenbedingungen werden dann:

Z = 3x1 + 2x2 + 0s1 + 0s2

Start-Simplex-Tableau:

|   Basis   |  x1  |  x2  |  s1  |  s2  |  RHS  |-------------------------------------------------||     s1    |  2   |  4   |  1   |  0   |   8   ||     s2    |  3   |  1   |  0   |  1   |   6   |-------------------------------------------------||     Z     | -3   | -2   |  0   |  0   |   0   |

Schritt 1: Wähle die Eingangsvariable (die Variable mit dem negativsten Wert in der Z-Reihe). Das ist x1.

Schritt 2: Berechne das Verhältnis der RHS-Werte zu den Pivot-Spalteneinträgen für jede Zeile:

• s1-Reihe: 8 / 2 = 4
• s2-Reihe: 6 / 3 = 2

Da 2 der kleinste Wert ist, wählen wir die s2-Reihe als Pivot-Reihe und 3 als Pivot-Element.

Schritt 3: Normalisiere das Pivot-Element:

|   Basis   |  x1  |  x2  |  s1  |  s2  |  RHS  |-------------------------------------------------||     s1    |  2   |  4   |  1   |  0   |   8   ||     x1    |  1   |  1/3 |  0   |  1/3 |   2   |   <-- Pivot-Reihe-------------------------------------------------||     Z     |  0   | -1   |  0   |  1   |   6   |

Schritt 4: Aktualisiere die anderen Zeilen:

|   Basis   |  x1  |  x2  |  s1  |  s2  |  RHS  |-------------------------------------------------||     s1    |  0   |  10/3 |  1   |  -2/3 |   4   ||     x1    |  1   |  1/3 |  0   |   1/3 |   2   |-------------------------------------------------||     Z     |  0   | -1   |  0   |  1   |   6   |

Schritt 5: Wähle die nächste Eingangsvariable, x2:

|   Basis   |  x1  |  x2  |  s1  |  s2  |  RHS  |-------------------------------------------------||     s1    |  0   |  10/3 |  1   |  -2/3 |   4   ||     x1    |  1   |  1/3 |  0   |   1/3 |   2   |-------------------------------------------------||     Z     |  0   | -1   |  0   |  1   |   6   |

Die Pivot-Reihe wird durch das Verhältnis der RHS-Werte zu den Pivot-Spalteneinträgen bestimmt:

• s1-Reihe: 4 / (10/3) = 1,2
• x1-Reihe: 2 / (1/3) = 6

Wir wählen die s1-Reihe als Pivot-Reihe und (10/3) als Pivot-Element.

Schritt 6: Normalisiere das Pivot-Element:

|   Basis   |  x1  |  x2  |  s1  |  s2  |  RHS  |-------------------------------------------------||     x2    |  0   |  1   |  3/10 |  -2/10 |   6/10 ||     x1    |  1   |  0   |  -1/10 |   1/10 |   4   |-------------------------------------------------||     Z     |  0   |  0   |   1/10 |  4/10 |  8   |

Ergebnis:

• Die optimale Produktmengen sind:
• x1 = 4 (maximale Produktion von P1)
• x2 = 2/3 (Teilweise Produktion von P2)
• Der maximale Gewinn ist Z = 8 Einheiten.

c)

Formuliere das duale Problem zu dem gegebenen linearen Optimierungsproblem. Erläutere die Beziehung zwischen der Lösung des primalen und des dualen Problems gemäß der Dualitätstheorie.

Lösung:

Um das duale Problem des gegebenen linearen Optimierungsproblems zu formulieren, identifizieren wir zunächst die Komponenten des primalen Problems:

Primal:

• Zielfunktion:

Maximiere Z = 3x1 + 2x2

• Nebenbedingungen:
• 2x1 + 4x2 ≤ 8
• 3x1 + x2 ≤ 6
• Nicht-Negativitätsbedingungen:
• x1 ≥ 0
• x2 ≥ 0

Die dualen Variablen y1 und y2 entsprechen den Nebenbedingungen des primalen Problems.

Im Dualen Problem gilt:

Dual:

• Zielfunktion:

Minimiere W = 8y1 + 6y2

• Nebenbedingungen:
• 2y1 + 3y2 ≥ 3
• 4y1 + y2 ≥ 2
• Nicht-Negativitätsbedingungen:
• y1 ≥ 0
• y2 ≥ 0

Beziehung zwischen der Lösung des primalen und des dualen Problems gemäß der Dualitätstheorie:

• Schwache Dualität: Der Wert der Zielfunktion des primalen Problems (Z) ist immer kleiner oder gleich dem Wert der Zielfunktion des dualen Problems (W) zu jedem zulässigen Punkt des primalen Problems und dualen Problems. Das heißt, Z ≤ W.
• Starke Dualität: Wenn das primale Problem eine optimale Lösung hat und das duale Problem ebenfalls eine Lösung hat, dann sind die Zielfunktionswerte gleich: Z = W. Das bedeutet, die maximale Zielfunktion des primalen Problems entspricht der minimalen Zielfunktion des dualen Problems.
• Komplementäre Schlupfbedingung: Für jede duale Variable gilt, dass entweder die duale Einschränkung aktiv ist (die Ungleichung wird zur Gleichung) oder die entsprechende primal Variable ist Null. Zum Beispiel, wenn 2y1 + 3y2 > 3, dann ist die zugehörige Variable x1 = 0.

Aufgabe 3)

Dualitätstheorie und SensitivitätsanalyseDualitätstheorie behandelt die Beziehung zwischen einem Optimierungsproblem (Primärproblem) und einem zugehörigen Dualproblem. Sensitivitätsanalyse untersucht, wie sich Änderungen der Parameter des Modells auf die optimale Lösung auswirken.

• Primärproblem:\[\min c^T x \quad \text{u.d.B.} \quad Ax \geq b, \; x \geq 0\]
• Dualproblem:\[\max b^T y \quad \text{u.d.B.} \quad A^T y \leq c, \; y \geq 0\]
• Schwache Dualität: \[ \text{Optimalwert des Dualproblems} \leq \text{Optimalwert des Primärproblems} \]
• Starke Dualität: Wenn eine optimale Lösung existiert, dann sind die Optimalwerte gleich.
• Sensitivitätsanalyse: Untersucht die Auswirkungen von Variationen in \(c, b\) oder \(A\) auf die Lösung.
• Schattenpreise: Ableitungen der Zielfunktion bezüglich der Nebenbedingungen.
• Reduced Costs: Zusätzlicher Gewinn pro Einheit einer nicht-basisvariablen Variable.

c)

Berechne die Schattenpreise für die Nebenbedingungen des Primärproblems und erkläre ihre Bedeutung.

Lösung:

Dualitätstheorie und SensitivitätsanalyseDualitätstheorie behandelt die Beziehung zwischen einem Optimierungsproblem (Primärproblem) und einem zugehörigen Dualproblem. Sensitivitätsanalyse untersucht, wie sich Änderungen der Parameter des Modells auf die optimale Lösung auswirken.

• Primärproblem:\[\min c^T x \quad \text{u.d.B.} \quad Ax \geq b, \; x \geq 0\]
• Dualproblem:\[\max b^T y \quad \text{u.d.B.} \quad A^T y \leq c, \; y \geq 0\]
• Schwache Dualität:\[ \text{Optimalwert des Dualproblems} \leq \text{Optimalwert des Primärproblems}\]
• Starke Dualität: Wenn eine optimale Lösung existiert, dann sind die Optimalwerte gleich.
• Sensitivitätsanalyse: Untersucht die Auswirkungen von Variationen in \(c, b\) oder \(A\) auf die Lösung.
• Schattenpreise: Ableitungen der Zielfunktion bezüglich der Nebenbedingungen.
• Reduced Costs: Zusätzlicher Gewinn pro Einheit einer nicht-basisvariablen Variable.

Subexercise:Berechne die Schattenpreise für die Nebenbedingungen des Primärproblems und erkläre ihre Bedeutung.Gegeben sei das folgende lineare Optimierungsproblem:\[\min 2x_1 + 3x_2 \quad \text{u.d.B.} \quad \begin{align*} -x_1 + 2x_2 & \geq 1, \ 3x_1 + x_2 & \geq 2, \ x_1, x_2 & \geq 0 \end{align*}\]Um die Schattenpreise zu berechnen, müssen wir das Dualproblem formulieren und lösen.Dualproblem:

• Zielfunktion: maximiere \( y_1 + 2y_2 \)
• Nebenbedingungen:
  • \(-y_1 + 3y_2 \leq 2\)
  • \(2y_1 + y_2 \leq 3\)
  • \(y_1, y_2 \geq 0\)

Berechnung der Schattenpreise:Um die Schattenpreise (\( y_1, y_2 \)) zu berechnen, lösen wir das Dualproblem. Dies kann auf verschiedene Arten erfolgen, zum Beispiel graphisch oder durch ein numerisches Verfahren wie Simplex. Für die Einfachheit nehmen wir an, dass die optimale Lösung des Dualproblems gegeben ist:

• \( y_1^* = 0.5 \)
• \( y_2^* = 1 \)

Bedeutung der Schattenpreise:Die Schattenpreise (dual variables) geben an, um wie viel sich der optimale Wert der Zielfunktion des Primärproblems ändern würde, wenn die rechte Seite der entsprechenden Nebenbedingung um eine Einheit erhöht wird.Interpretation der Schattenpreise:

• \( y_1^* = 0.5 \): Dies bedeutet, dass eine Erhöhung der rechten Seite der ersten Nebenbedingung \( -x_1 + 2x_2 \geq 1 \) um eine Einheit den Wert der Zielfunktion um 0.5 erhöhen würde.
• \( y_2^* = 1 \): Dies bedeutet, dass eine Erhöhung der rechten Seite der zweiten Nebenbedingung \( 3x_1 + x_2 \geq 2 \) um eine Einheit den Wert der Zielfunktion um 1 erhöhen würde.

Die Schattenpreise geben also direkt die Sensitivität der Zielfunktion des Primärproblems gegenüber Änderungen in den rechten Seiten der Nebenbedingungen an.

Aufgabe 4)

Verwende das Newton-Verfahren zur Optimierung: Betrachte die Funktion

• f(x) = x^3 - 3x^2 + 2x

Führe das Newton-Verfahren durch, um ein lokales Minimum oder Maximum zu bestimmen.