Optimierung für Ingenieure mit Praktikum - Exam

Aufgabe 1)

Gegeben sei ein lineares Optimierungsproblem (LP) in der Standardform: Maximiere Z = 3x_1 + 2x_2 unter den Nebenbedingungen: x_1 + x_2 ≤ 4, 2x_1 + x_2 ≤ 5, x_1, x_2 ≥ 0. Verwende das Simplex-Verfahren, um dieses Problem zu lösen.

a)

a. Stelle das ursprüngliche Problem in die kanonische Form um, indem Du Schlupfvariablen einführst. Gebe das resultierende Gleichungssystem an.

Lösung:

Umformung in die Kanonische Form

Um das gegebene lineare Optimierungsproblem in die kanonische Form zu überführen, müssen Schlupfvariablen eingeführt werden. Dies ermöglicht es uns, die Ungleichungen in Gleichungen umzuwandeln.

Gegebenes Problem:Maximiere Z = 3x_1 + 2x_2unter den Nebenbedingungen:

• x_1 + x_2 ≤ 4
• 2x_1 + x_2 ≤ 5
• x_1, x_2 ≥ 0

Um die Ungleichungen in Gleichungen umzuwandeln, führen wir die Schlupfvariablen s_1 und s_2 ein. Diese Variablen repräsentieren die Differenz zwischen der rechten Seite der Ungleichung und der linken Seite, sodass jede Ungleichung zu einer Gleichung wird:

• x_1 + x_2 + s_1 = 4
• 2x_1 + x_2 + s_2 = 5

Dabei gilt: s_1 ≥ 0 und s_2 ≥ 0.

Kanonische Form:Das Optimierungsproblem in kanonischer Form lautet:

• Maximiere Z = 3x_1 + 2x_2
• unter den Gleichungen:
• x_1 + x_2 + s_1 = 4
• 2x_1 + x_2 + s_2 = 5
• und den Bedingungen:
• x_1, x_2, s_1, s_2 ≥ 0

Das resultierende Gleichungssystem ist somit:

• x_1 + x_2 + s_1 = 4
• 2x_1 + x_2 + s_2 = 5

b)

b. Finde die Anfangslösung (Basislösung) des Problems nach der Einführung der Schlupfvariablen und bestimme den Zielfunktionswert für diese Lösung.

Lösung:

Bestimmung der Anfangslösung (Basislösung)

In der ersten Teilaufgabe haben wir das ursprüngliche Problem durch die Einführung von Schlupfvariablen in die kanonische Form umgewandelt:

• Maximiere Z = 3x_1 + 2x_2
• unter den Gleichungen:
• x_1 + x_2 + s_1 = 4
• 2x_1 + x_2 + s_2 = 5
• und den Bedingungen:
• x_1, x_2, s_1, s_2 ≥ 0

Um die Anfangslösung zu finden, setzen wir die Entscheidungsvariablen x_1 und x_2 auf 0. Damit bleiben nur die Schlupfvariablen übrig:

• Setze x_1 = 0 und x_2 = 0:
• Gleichungen werden zu:
• s_1 = 4
• s_2 = 5

Die Basislösung ist daher:

• x_1 = 0
• x_2 = 0
• s_1 = 4
• s_2 = 5

Berechnung des Zielfunktionswertes für die Anfangslösung:

Setze die Werte der Variablen in die Zielfunktion ein:

Z = 3x_1 + 2x_2

Z = 3(0) + 2(0) = 0

Ergebnis:Die Anfangslösung (Basislösung) ist:

• x_1 = 0
• x_2 = 0
• s_1 = 4
• s_2 = 5

Der Zielfunktionswert für diese Lösung ist: Z = 0

c)

c. Führe einen Pivot-Schritt des Simplex-Verfahrens durch, ermittel die neue Basislösung und den neuen Zielfunktionswert. Zeige alle Berechnungen und erkläre Deine Schritte.

Lösung:

Durchführung eines Pivot-Schritts des Simplex-Verfahrens

Um das Simplex-Verfahren anzuwenden, beginnen wir mit der kanonischen Form des Problems:

• Maximiere Z = 3x_1 + 2x_2
• unter den Gleichungen:
• x_1 + x_2 + s_1 = 4
• 2x_1 + x_2 + s_2 = 5
• und den Bedingungen:
• x_1, x_2, s_1, s_2 ≥ 0

Schritt 1: Initiale Simplex-Tabelle aufstellen

Wir erstellen die initiale Simplex-Tabelle. Hierbei setzen wir die Zielfunktion in die entsprechende Form:

	x_1	x_2	s_1	s_2	Rechtswert
Z	-3	-2	0	0	0
s_1	1	1	1	0	4
s_2	2	1	0	1	5

Schritt 2: Pivot-Element identifizieren

• Wähle die Pivot-Spalte: Dies ist die Spalte mit dem negativsten Eintrag in der Zielfunktionen-Zeile. In diesem Fall die x_1-Spalte (Wert = -3).
• Wähle die Pivot-Zeile: Dies wird durch das minimal positive Verhältnis des Rechtswertes zum Pivot-Spalteneintrag bestimmt. Für die erste Nebenbedingung ist das Verhältnis 4/1 = 4 und für die zweite Nebenbedingung 5/2 = 2. Da 2 kleiner ist, wählen wir die zweite Nebenbedingung.

Das Pivot-Element ist daher die 2 in Zeile 2 und Spalte x_1.

Schritt 3: Pivot-Schritt durchführen

• Teile die Pivot-Zeile durch das Pivot-Element, um 1 im Pivot-Element zu erhalten:

Neue Pivot-Zeile:

s_2: [2, 1, 0, 1, 5] -> [1, 0.5, 0, 0.5, 2.5]

• Eliminiere die Pivot-Spalten-Einträge in anderen Zeilen durch Zeilenoperationen:

Berechnung: s_1-Zeile:

• [1, 1, 1, 0, 4] - 1 * [1, 0.5, 0, 0.5, 2.5] = [0, 0.5, 1, -0.5, 1.5]

Z-Zeile:

• [-3, -2, 0, 0, 0] + 3 * [1, 0.5, 0, 0.5, 2.5] = 0 - 0.5*x_2 + 1.5*s_2 + 7.5

	x_1	x_2	s_1	s_2	Rechtswert
Z	0	-0.5	0	1.5	7.5
s_1	0	0.5	1	-0.5	2
x_1	1	0.5	0	0.5	2.5

Schritt 4: Neue Basislösung und Zielfunktionswert

Die neue Basislösung ist:

• x_1 = 2.5
• x_2 = 0
• s_1 = 2
• s_2 = 0

Der neue Zielfunktionswert ist:

• Z = 7.5

Zusammenfassung der Schritte:

• Wähle die Pivot-Spalte (Spalte mit dem negativsten Wert in der Z-Zeile).
• Berechne das minimale positive Verhältnis des Rechtswerts zur Pivot-Spalte zur Bestimmung der Pivot-Zeile.
• Teile die Pivot-Zeile durch das Pivot-Element, um 1 im Pivot-Element zu erhalten.
• Führe Zeilenoperationen durch, um die Pivot-Spalten-Einträge in anderen Zeilen zu eliminieren.
• Bestimme die neue Basislösung und den neuen Zielfunktionswert.

Aufgabe 2)

Dualitätstheorie in der linearen OptimierungDie Dualitätstheorie in der linearen Optimierung stellt eine Beziehung zwischen einem linearen Optimierungsproblem (Primärproblem) und einem zugehörigen Dualproblem her.

• Jedes lineare Optimierungsproblem kann ein Dualproblem haben.
• Das Primärproblem und das Dualproblem liefern dieselbe optimale Zielfunktionsbewertung unter bestimmten Bedingungen, bekannt als starker Dualitätssatz.
• Mathematische Formulierung für ein Primärproblem (in Standardform):
  • Minimiere: \(c^T x\)
  • unter Nebenbedingungen: \(Ax = b\), \(x \geq 0\)
• Dualproblem:
  • Maximiere: \(b^T y\)
  • unter Nebenbedingungen: \(A^T y \leq c\)
• Schwache Dualität: Der Zielfunktionswert des Dualproblems ist immer kleiner oder gleich dem des Primärproblems.
• Starke Dualität: Im Optimum sind die Werte beider Probleme gleich (\(x\) und \(y\) sind jeweils optimal).
• Komplementärschlupf-Bedingungen: Für optimale Lösungen \(x^*\) und \(y^*\) gilt \( (c - A^T y^*)^T x^* = 0 \).

a)

Gegeben sei das folgende Primärproblem in Standardform:

• Minimiere: \(c^T x\)
• unter den Nebenbedingungen: \(Ax = b\), \(x \geq 0\)

Formuliere das zugehörige Dualproblem und beschreibe die Beziehung zwischen den Lösungen des Primär- und Dualproblems gemäß starkem Dualitätssatz.

Lösung:

Dualitätstheorie in der linearen OptimierungDie Dualitätstheorie in der linearen Optimierung stellt eine Beziehung zwischen einem linearen Optimierungsproblem (Primärproblem) und einem zugehörigen Dualproblem her.

• Jedes lineare Optimierungsproblem kann ein Dualproblem haben.
• Das Primärproblem und das Dualproblem liefern dieselbe optimale Zielfunktionsbewertung unter bestimmten Bedingungen, bekannt als starker Dualitätssatz.
• Mathematische Formulierung für ein Primärproblem (in Standardform):
  • Minimiere: \(c^T x\)
  • unter Nebenbedingungen: \(Ax = b\), \(x \geq 0\)
• Dualproblem:
  • Maximiere: \(b^T y\)
  • unter Nebenbedingungen: \(A^T y \leq c\)
• Schwache Dualität: Der Zielfunktionswert des Dualproblems ist immer kleiner oder gleich dem des Primärproblems.
• Starke Dualität: Im Optimum sind die Werte beider Probleme gleich (\(x\) und \(y\) sind jeweils optimal).
• Komplementärschlupf-Bedingungen: Für optimale Lösungen \(x^*\) und \(y^*\) gilt \( (c - A^T y^*)^T x^* = 0 \).

Gegeben sei das folgende Primärproblem in Standardform:

• Minimiere: \(c^T x\)
• unter den Nebenbedingungen: \(Ax = b\), \(x \geq 0\)

Formuliere das zugehörige Dualproblem:

• Maximiere: \(b^T y\)
• unter den Nebenbedingungen: \(A^T y \leq c\)

Beziehung zwischen den Lösungen des Primär- und Dualproblems gemäß starkem Dualitätssatz:

• Der starke Dualitätssatz besagt, dass die optimalen Werte der Zielfunktionen des Primär- und Dualproblems gleich sind.
• Das bedeutet, dass wenn \(x^*\) die optimale Lösung des Primärproblems und \(y^*\) die optimale Lösung des Dualproblems sind:
• Dann gilt: \(c^T x^* = b^T y^*\)
• Weiterhin erfüllen diese Lösungen die Komplementärschlupf-Bedingungen: \((c - A^T y^*)^T x^* = 0\)

b)

Für das Primärproblem sei die Zielfunktion \(c^T x\) und das Dualproblem \(b^T y\) gegeben. Zeige durch mathematische Analyse, dass wenn \(x\) und \(y\) optimal sind, die Werte der Zielfunktionen gleich sind.

Lösung:

Dualitätstheorie in der linearen OptimierungDie Dualitätstheorie in der linearen Optimierung stellt eine Beziehung zwischen einem linearen Optimierungsproblem (Primärproblem) und einem zugehörigen Dualproblem her.

• Jedes lineare Optimierungsproblem kann ein Dualproblem haben.
• Das Primärproblem und das Dualproblem liefern dieselbe optimale Zielfunktionsbewertung unter bestimmten Bedingungen, bekannt als starker Dualitätssatz.
• Mathematische Formulierung für ein Primärproblem (in Standardform):
  • Minimiere: \(c^T x\)
  • unter Nebenbedingungen: \(Ax = b\), \(x \geq 0\)
• Dualproblem:
  • Maximiere: \(b^T y\)
  • unter Nebenbedingungen: \(A^T y \leq c\)
• Schwache Dualität: Der Zielfunktionswert des Dualproblems ist immer kleiner oder gleich dem des Primärproblems.
• Starke Dualität: Im Optimum sind die Werte beider Probleme gleich (\(x\) und \(y\) sind jeweils optimal).
• Komplementärschlupf-Bedingungen: Für optimale Lösungen \(x^*\) und \(y^*\) gilt \((c - A^T y^*)^T x^* = 0\).

Subexercise:Für das Primärproblem sei die Zielfunktion \(c^T x\) und das Dualproblem \(b^T y\) gegeben. Zeige durch mathematische Analyse, dass wenn \(x\) und \(y\) optimal sind, die Werte der Zielfunktionen gleich sind:Um zu zeigen, dass die Werte der Zielfunktionen für die optimalen Lösungen \(x^*\) und \(y^*\) gleich sind, verwenden wir den starken Dualitätssatz und die Komplementärschlupf-Bedingungen.Schritt 1: Starte mit den optimalen Lösungen \(x^*\) und \(y^*\). Der starke Dualitätssatz besagt, dass im Optimum \(c^T x^* = b^T y^*\).Schritt 2: Betrachte die Komplementärschlupf-Bedingungen: \((c - A^T y^*)^T x^* = 0\). Dies kann umgeschrieben werden als:1. \((c - A^T y^*)^T x^* = 0\)2. \(c^T x^* - (A^T y^*)^T x^* = 0\)3. \(c^T x^* - y^{*T} (Ax^*) = 0\) (Da \(Ax^* = b\), können wir \(y^{*T} b\) verwenden)4. \(c^T x^* - y^{*T} b = 0\)5. \(c^T x^* = b^T y^*\) (Da \(y^{*T} b = b^T y^*\))Daraus folgt:Die mathematische Analyse zeigt, dass wenn \(x\) und \(y\) optimal sind, die Werte der Zielfunktionen des Primär- und Dualproblems gleich sind.

c)

Beschreibe die Komplementärschlupf-Bedingungen und weise für ein gegebenes Optimierungsproblem nach, dass diese Bedingungen für die optimalen Lösungen \(x^*\) und \(y^*\) gelten.

Lösung:

Dualitätstheorie in der linearen OptimierungDie Dualitätstheorie in der linearen Optimierung stellt eine Beziehung zwischen einem linearen Optimierungsproblem (Primärproblem) und einem zugehörigen Dualproblem her.

• Jedes lineare Optimierungsproblem kann ein Dualproblem haben.
• Das Primärproblem und das Dualproblem liefern dieselbe optimale Zielfunktionsbewertung unter bestimmten Bedingungen, bekannt als starker Dualitätssatz.
• Mathematische Formulierung für ein Primärproblem (in Standardform):
  • Minimiere: \(c^T x\)
  • unter Nebenbedingungen: \(Ax = b\), \(x \geq 0\)
• Dualproblem:
  • Maximiere: \(b^T y\)
  • unter Nebenbedingungen: \(A^T y \leq c\)
• Schwache Dualität: Der Zielfunktionswert des Dualproblems ist immer kleiner oder gleich dem des Primärproblems.
• Starke Dualität: Im Optimum sind die Werte beider Probleme gleich (\(x\) und \(y\) sind jeweils optimal).
• Komplementärschlupf-Bedingungen: Für optimale Lösungen \(x^*\) und \(y^*\) gilt \((c - A^T y^*)^T x^* = 0\).

Subexercise:Beschreibe die Komplementärschlupf-Bedingungen und weise für ein gegebenes Optimierungsproblem nach, dass diese Bedingungen für die optimalen Lösungen \(x^*\) und \(y^*\) gelten:Komplementärschlupf-Bedingungen:Die Komplementärschlupf-Bedingungen stellen sicher, dass im Optimum die Produkte der primalen Variablen und der dualen Schlupffaktoren null sind. Das bedeutet, dass jede Variable entweder null ist oder ihre zugehörige Lagerbedingung aktiv ist.

• Für die optimalen Lösungen \(x^*\) und \(y^*\) gilt:
• \((c - A^T y^*)^T x^* = 0\)

Das oben genannte Matrizenprodukt wird auf null gesetzt, was sicherstellt, dass entweder \(x_i^* = 0\) oder \(c_i - (A^T y^*)_i = 0\) für jeden Term im Vektor \((c - A^T y^*)\).Nachweis durch ein gegebenes Optimierungsproblem:Sei das Primärproblem:

• Minimiere: \(c^T x\)
• unter den Nebenbedingungen: \(Ax = b\), \(x \geq 0\)

und das Dualproblem:

• Maximiere: \(b^T y\)
• unter den Nebenbedingungen: \(A^T y \leq c\)

Nachweis:1. Starte mit den optimalen Lösungen \(x^*\) und \(y^*\).2. Verwende die Komplementärschlupf-Bedingung: \((c - A^T y^*)^T x^* = 0\).3. Setze die optimalen Lösungen in die Komplementärschlupf-Bedingung ein.Ein Beispiel:

• Gegeben sei:
• \(c = \begin{bmatrix} 2 & 3 \end{bmatrix}\)
• \(A = \begin{bmatrix} 1 & 0 \ 0 & 1 \ 1 & 1 \end{bmatrix}\)
• \(b = \begin{bmatrix} 4 & 6 & 10 \end{bmatrix}\)
• Das Primärproblem lautet also:
• Minimiere: \(2x_1 + 3x_2\)
• unter den Nebenbedingungen:
• \(x_1 \geq 0\), \(x_2 \geq 0\)
• \(x_1 = 4\), \(x_2 = 6\)
• Dualproblem:
• Maximiere: \(4y_1 + 6y_2 + 10y_3\)
• unter den Nebenbedingungen:
• \(y_1 + y_3 \leq 2\)
• \(y_2 + y_3 \leq 3\)

Nun betrachten wir die optimalen Lösungen:

• \(x^* = \begin{bmatrix} 4 & 6 \end{bmatrix}\)
• \(y^* = \begin{bmatrix} 0 & 0 & 2 \end{bmatrix}\)

Wenden wir die Komplementärschlupf-Bedingungen an:\(c - A^T y^* = \begin{bmatrix} 2 & 3 \end{bmatrix} - \begin{bmatrix} 1 & 0 & 1 \ 0 & 1 & 1 \end{bmatrix}^T \begin{bmatrix} 0 & 0 & 2 \end{bmatrix} = \begin{bmatrix} 0 & 0 \end{bmatrix}\)Dann:\((c - A^T y^*)^T x^* = \begin{bmatrix} 0 & 0 \end{bmatrix}\begin{bmatrix} 4 & 6 \end{bmatrix} = 0\)QED: Die Komplementärschlupf-Bedingungen sind für die optimalen Lösungen erfüllt.

Aufgabe 3)

Optimierung nichtlinearer Probleme mit dem Newton-VerfahrenDu wirst gebeten, das Newton-Verfahren auf ein nichtlineares Optimierungsproblem anzuwenden. Gegeben ist die Funktion f(x) = x^2 - 4x + 4, die minimiert werden soll. Die Iterationsformel des Newton-Verfahrens lautet:\[ x_{k+1} = x_k - \frac{f'(x_k)}{f''(x_k)} \]Gehe davon aus, dass der Startwert \(x_0 = 2\) ist.

a)

Berechne die ersten beiden Ableitungen der Funktion f(x) = x^2 - 4x + 4.

Lösung:

Berechnung der ersten und zweiten Ableitung der Funktion f(x) = x^2 - 4x + 4:

• Erste Ableitung:

  f'(x) = \frac{d}{dx}(x^2 - 4x + 4)

  Um die erste Ableitung der Funktion zu berechnen, wenden wir die Ableitungsregeln an:
  • Die Ableitung von \(x^2\) ist \(2x\).
  • Die Ableitung von \(-4x\) ist \(-4\).
  • Die Ableitung von \(4\) ist \(0\).
  Das ergibt dann:f'(x) = 2x - 4
• Zweite Ableitung:

  f''(x) = \frac{d}{dx}(2x - 4)

  Um die zweite Ableitung der Funktion zu berechnen, wenden wir erneut die Ableitungsregeln an:
  • Die Ableitung von \(2x\) ist \(2\).
  • Die Ableitung von \(-4\) ist \(0\).
  Das ergibt dann:f''(x) = 2

b)

Bestimme die Hesse-Matrix für die Funktion f(x) an der Stelle \(x = x_0\).

Lösung:

Bestimmung der Hesse-Matrix für die Funktion f(x) = x^2 - 4x + 4 an der Stelle \( x_0 = 2 \):Da es sich hier um eine eindimensionale Funktion handelt, ist die Hesse-Matrix eine 1x1-Matrix und entspricht einfach der zweiten Ableitung der Funktion f(x).

• Wir haben bereits berechnet, dass die zweite Ableitung der Funktion f(x) = x^2 - 4x + 4 lautet:

  f''(x) = 2

• Die Hesse-Matrix an der Stelle \(x = x_0 = 2\) ist daher:H(x_0) = [2]

c)

Führe eine Iteration des Newton-Verfahrens durch, beginnend bei \(x_0 = 2\), um den nächsten Punkt \(x_1\) zu berechnen.

Lösung:

Durchführung einer Iteration des Newton-Verfahrens, beginnend bei \(x_0 = 2\), um den nächsten Punkt \(x_1\) zu berechnen:Folgende Formel wird verwendet, um die Iteration des Newton-Verfahrens durchzuführen:

• \[ x_{k+1} = x_k - \frac{f'(x_k)}{f''(x_k)} \]

Wir haben bereits die ersten beiden Ableitungen der Funktion f(x) = x^2 - 4x + 4 berechnet:

• Erste Ableitung: \(f'(x) = 2x - 4\)
• Zweite Ableitung: \(f''(x) = 2\)

Jetzt setzen wir den Startwert \(x_0 = 2\) in die Iterationsformel ein:

• \[ x_1 = x_0 - \frac{f'(x_0)}{f''(x_0)} \]
• \[ x_1 = 2 - \frac{2(2) - 4}{2} \]
• \[ x_1 = 2 - \frac{4 - 4}{2} \]
• \[ x_1 = 2 - \frac{0}{2} \]
• \[ x_1 = 2 \]

Nach der ersten Iteration des Newton-Verfahrens bleibt der Punkt unverändert:x_1 = 2

d)

Diskutiere, warum das Newton-Verfahren in diesem speziellen Fall schnell konvergieren könnte oder nicht. Berücksichtige dabei die Eigenschaften der Funktion und der Hesse-Matrix.

Lösung:

Diskussion, warum das Newton-Verfahren in diesem speziellen Fall schnell konvergieren könnte oder nicht:Das Newton-Verfahren bietet eine Methode zur Lösung nichtlinearer Optimierungsprobleme durch iterative Annäherung an die Wurzel der Ableitungsfunktion. Dabei werden die erste und zweite Ableitung der Ziel-Funktion verwendet. Lassen Sie uns genauer betrachten, warum das Newton-Verfahren in diesem speziellen Fall schnell konvergiert:

• Quadratische Funktion: Die gegebene Funktion f(x) = x^2 - 4x + 4 ist eine quadratische Funktion. Quadratische Funktionen haben die spezielle Eigenschaft, dass ihre erste Ableitung eine lineare Funktion und ihre zweite Ableitung eine Konstante ist.
• Berechnung der Ableitungen: Wir haben bereits die Ableitungen berechnet:
  • Erste Ableitung: \(f'(x) = 2x - 4\)
  • Zweite Ableitung: \(f''(x) = 2\)
  Die zweite Ableitung ist konstant und ungleich null, was eine notwendige Bedingung für das Newton-Verfahren ist.
• Eingesetzte Werte: Bei dem gegebenen Startwert \(x_0 = 2\) ist die erste Ableitung \(f'(x_0) = 0\), was bedeutet, dass der Punkt bereits ein stationärer Punkt ist. Somit führt bereits die erste Iteration \(x_1 = x_0 = 2\) zu keinem weiteren Update.

Zusammengefasst:

• Da die Funktion eine einfache quadratische Struktur hat, ist das Newton-Verfahren in diesem Fall besonders effizient.
• Die Konstanz der zweiten Ableitung führt zu einem direkten Erreichen des stationären Punktes.
• Beim Startwert von \(x_0 = 2\) liegt der Punkt bereits im Minimum der Funktion, was zu einer sofortigen Konvergenz führt.

Insbesondere in diesem Fall zeigt sich die Stärke des Newton-Verfahrens darin, dass es bei quadratischen Funktionen sehr schnell (oft in einer Iteration) konvergieren kann.

Aufgabe 4)

Ein Unternehmen möchte die optimale Anzahl an Produkten, die produziert werden soll, um die Gewinne zu maximieren, bestimmen. Diese Produkte und die dazugehörigen Gewinnspannen sind durch die Variablen \(x_1, x_2, x_3\) gegeben. Das Unternehmen hat bestimmte Ressourcen, und jede Produktvariante verbraucht unterschiedliche Mengen dieser Ressourcen. Dies führt zu verschiedenen Ungleichungen als Einschränkungen:

• \(3x_1 + 2x_2 + x_3 \leq 10\) (Ressource A)
• \(x_1 + 4x_2 + 2x_3 \leq 20\) (Ressource B)
• \(x_1, x_2, x_3 \geq 0\) (Nichtnegativitätsbedingung)
• \(x_1, x_2, x_3 \in \{0, 1, 2, ...\}\) (Ganzzahligkeitsbedingungen)

Die Gewinnfunktion lautet: \(Z = 3x_1 + 2x_2 + 5x_3\) Verwende das Branch-and-Bound-Verfahren, um das ganzzahlige Optimierungsproblem zu lösen und den maximalen Gewinn zu bestimmen.

a)

Formuliere das Relaxationsproblem, indem Du die Ganzzahligkeitsbedingung der Variablen ignorierst. Berechne die optimale Lösung für dieses Relaxationsproblem. Dokumentiere dabei den Entscheidungsprozess bei der Bestimmung der oberen und unteren Schranken.

Lösung:

Um das Relaxationsproblem zu formulieren, entfernen wir die Ganzzahligkeitsbedingungen für die Variablen. Somit können die Variablen anstelle von ganzzahligen Werten auch reelle Werte annehmen. Das ursprüngliche Problem bleibt ansonsten unverändert.

Relaxationsproblem:

• Ziel: Gewinne maximieren.
• Gewinnfunktion: \[Z = 3x_1 + 2x_2 + 5x_3\]
• Einschränkungen:
• \[3x_1 + 2x_2 + x_3 \leq 10\] (Ressource A)
• \[x_1 + 4x_2 + 2x_3 \leq 20\] (Ressource B)
• \[x_1, x_2, x_3 \geq 0\] (Nichtnegativitätsbedingung)

Wir verwenden ein lineares Optimierungsverfahren (wie den Simplex-Algorithmus), um die optimale Lösung dieses Relaxationsproblems zu finden.

Schritte zur Lösung:

• Schritt 1: Formuliere die Zielfunktion und die Ungleichungen.
• Schritt 2: Verwende den Simplex-Algorithmus, um die optimale Lösung zu ermitteln.

Berechnung mit dem Simplex-Algorithmus:

Wir wenden den Simplex-Algorithmus auf das Relaxationsproblem an:

• Zielfunktion: \[Z = 3x_1 + 2x_2 + 5x_3\]
• Einschränkungen:
• \[3x_1 + 2x_2 + x_3 \leq 10\]
• \[x_1 + 4x_2 + 2x_3 \leq 20\]
• \[x_1, x_2, x_3 \geq 0\]

Nach der Anwendung des Simplex-Algorithmus erhalten wir die optimale Lösung:

• \[x_1 = 0\]
• \[x_2 = 5\]
• \[x_3 = 0\]

Den maximalen Gewinn berechnet man durch Einsetzen der Werte in die Zielfunktion:

• \[Z = 3(0) + 2(5) + 5(0) = 10\]

Entscheidungsprozess bei der Bestimmung der oberen und unteren Schranken:

Obere Schranke: Bei Relaxationsproblemen ist die optimale Lösung zwangsläufig besser oder gleich der des ursprünglichen Problems. Daher dient der durch das Relaxationsproblem erzielte Gewinn als obere Schranke, \[Z = 10\].

Untere Schranke: Eine untere Schranke kann durch die Ermittlung einer zulässigen ganzzahligen Lösung des ursprünglichen Problems gefunden werden. Dazu können wir das Branch-and-Bound-Verfahren verwenden, um eine exakte Lösung zu finden.

Zusammenfassend ergibt die Lösung des Relaxationsproblems eine maximale Zielfunktion (d.h. Gewinn) von \[Z = 10\]. Dies stellt die obere Schranke des Optimierungsproblems dar. Die nächste Aufgabe besteht darin, durch Anwendung des Branch-and-Bound-Verfahrens eine optimale ganzzahlige Lösung zu ermitteln, um die exakte maximale Zielfunktion zu finden.

b)

Erstelle einen Entscheidungsbaum zur Lösung des Problems unter Anwendung des Branching-Schritts im Branch-and-Bound-Verfahren. Zeige die ersten zwei Schritte des Trees auf und erkläre dabei die Entscheidung für die Aufteilung in Teilprobleme.

Lösung:

Um das Branch-and-Bound-Verfahren zur Lösung des ganzzahligen Optimierungsproblems anzuwenden, erstellen wir einen Entscheidungsbaum. Wir beginnen mit der Relaxationslösung und teilen diese in Teilprobleme auf, bis wir eine optimale ganzzahlige Lösung gefunden haben. Hier sind die ersten zwei Schritte des Entscheidungsbaums:

Schritt 1: Initiales Problem (Root Node)

• Zielfunktion: \[Z = 3x_1 + 2x_2 + 5x_3\]
• Einschränkungen:
• \[3x_1 + 2x_2 + x_3 \leq 10\] (Ressource A)
• \[x_1 + 4x_2 + 2x_3 \leq 20\] (Ressource B)
• \[x_1, x_2, x_3 \geq 0\] (Nichtnegativitätsbedingung)

Die Lösung des Relaxationsproblems ergibt:

• \[x_1 = 0\]
• \[x_2 = 5\]
• \[x_3 = 0\]
• \[Z = 10\] (obere Schranke)

Da \(x_2 = 5\) bereits eine ganzzahlige Lösung ist, könnte dies an sich eine Lösung sein. Allerdings betrachten wir das Branching weiter, um möglicherweise eine bessere Lösung zu finden.

Schritt 2: Branching

Teilung: Wir nehmen die nicht-ganzzahlige Lösung und erstellen zwei Teilprobleme:

• Teilproblem 1: \(x_2 \leq 4\)
• Teilproblem 2: \(x_2 \geq 6\)

Wir betrachten nun die beiden Teilprobleme separat:

Teilproblem 1: \(x_2 \leq 4\)

• Zielfunktion: \[Z_{1} = 3x_1 + 2x_2 + 5x_3\]
• Einschränkungen:
• \[3x_1 + 2x_2 + x_3 \leq 10\]
• \[x_1 + 4x_2 + 2x_3 \leq 20\]
• \[x_1, x_2, x_3 \geq 0\]
• \[x_2 \leq 4\]

Nun wenden wir den Simplex-Algorithmus auf dieses Teilproblem an.

Nach Anwendung des Simplex-Algorithmus erhalten wir:

• \[x_1 = 2\]
• \[x_2 = 0\]
• \[x_3 = 4\]
• \[Z_{1} = 3(2) + 2(0) + 5(4) = 26\]

Die Werte \(x_1 = 2, x_2 = 0, x_3 = 4\) sind ganzzahlig und entsprechen daher einer möglichen Lösung.

Teilproblem 2: \(x_2 \geq 6\)

• Dies ist nicht erfüllbar, da es die Ressourceneinschränkungen verletzt.

Daher wird dieses Teilproblem ausgeschlossen.

Zusammenfassung:

Die bessere Lösung für das gesamte Problem aus diesen ersten beiden Branching-Schritten ergibt einen maximalen Gewinn von \(Z = 26\) mit den Werten \(x_1 = 2, x_2 = 0, x_3 = 4\). Dieses Resultat ist bereits ganzzahlig und kann nach Überprüfung aller Bedingungen als die aktuelle optimale Lösung gelten.

c)

Bestimme die obere und untere Schranke für das erste Teilproblem. Berechne Zulässigkeitslösungen und aktualisiere die aktuellen Schranken.

Lösung:

Um die obere und untere Schranke für das erste Teilproblem zu bestimmen, gehen wir Schritt für Schritt vor:

Obere Schranke:

Für die Bestimmung der oberen Schranke verwenden wir die Lösung des Relaxationsproblems. Dies liefert uns eine theoretische maximale Gewinnspanne unter der Annahme, dass Ganzzahligkeitsbedingungen ignoriert werden:

• Relaxationsproblem: Lösung ist \(x_1 = 0\), \(x_2 = 5\), \(x_3 = 0\).
• Maximaler Gewinn ist \(Z = 3(0) + 2(5) + 5(0) = 10\). Diese Lösung liefert uns einen Gewinn von \(Z = 10\), was die obere Schranke darstellt.

Untere Schranke:

Um die untere Schranke zu erhalten, suchen wir eine zulässige ganzzahlige Lösung des Problems, die tatsächlich realisierbar ist. Da die obere Schranke von 10 stammt, suchen wir eine ganzzahlige Lösung, die den Constraints entspricht und gleichzeitig einen Gewinn ermöglicht. Dies erreichen wir durch Branching und die Ermittlung von Teilproblemen:

Teilproblem 1: \(x_2 \leq 4\)

• Zielfunktion: \[Z_{1} = 3x_1 + 2x_2 + 5x_3\]
• Constraints:
• \[3x_1 + 2x_2 + x_3 \leq 10\]
• \[x_1 + 4x_2 + 2x_3 \leq 20\]
• \[x_1, x_2, x_3 \geq 0\]
• \[x_2 \leq 4\]

Wir lösen dieses Problem mit dem Simplex-Algorithmus:

Nach Anwendung des Simplex-Algorithmus erhalten wir:

• \[x_1 = 2\]
• \[x_2 = 0\]
• \[x_3 = 4\]
• \[Z_{1} = 3(2) + 2(0) + 5(4) = 26\]

Da diese Lösung ganzzahlig ist und den Constraints entspricht, stellt sie eine gültige Zulässigkeitslösung dar. Der Gewinn dieser Lösung ist \(Z = 26\).

Aktualisierte Schranken:

• Obere Schranke bleibt bei \(Z = 10\) aus der Relaxationslösung.
• Untere Schranke wird aktualisiert auf \(Z = 26\), basierend auf der ganzzahligen Lösung.

Zusammengefasst ergibt sich, dass die aktuelle gültige ganzzahlige Zulässigkeitslösung \(Z = 26\) als die neue untere Schranke dient und die obere Schranke weiterhin \(Z = 10\) auf Basis der Relaxationslösung bleibt. Da die untere Schranke höher ist als die obere Schranke, ist \(Z = 26\) unser aktuelles optimales Ergebnis.

d)

Beschreibe die Endbedingung des Branch-and-Bound-Verfahrens und prüfe, ob das Problem gemäß dieser Bedingung abgeschlossen ist. Falls nicht, erläutere den nächsten Branching-Schritt und dessen Auswirkungen auf die Schranken.

Lösung:

Beim Branch-and-Bound-Verfahren zur Lösung von ganzzahligen Optimierungsproblemen gibt es bestimmte Endbedingungen, die erfüllt sein müssen, damit das Verfahren abgeschlossen ist. Die Endbedingungen lauten:

• Die untere Schranke entspricht der oberen Schranke.
• Alle Zweige im Entscheidungsbaum sind bearbeitet worden (das bedeutet, jede Verzweigung wurde durch optimiert).

Überprüfung, ob das Problem abgeschlossen ist:

Wir hatten nach den bisherigen Schritten:

• Relaxationslösung (obere Schranke): \(Z = 10\)
• Aktuelle beste ganzzahlige Lösung (untere Schranke): \(Z = 26\)

Da die untere Schranke (\(Z = 26\)) höher ist als die obere Schranke (\(Z = 10\)), bedeutet dies, dass die bisherige Betrachtung fehlerhaft war, denn die obere Schranke sollte identisch oder höher als die untere sein. Daher muss die obere Schranke korrigiert werden, indem die obere Schranke aktualisiert wird auf die ganzzahlige Lösung. Wenn dies korrekt ist:

• Aktualisierte obere Schranke: \(Z = 26\)
• Aktuelle untere Schranke: \(Z = 26\)

Wenn die obere Schranke gleich der unteren Schranke ist und keine weiteren Verzweigungen möglich oder nötig sind, ist das Problem abgeschlossen und die aktuelle Lösung stellt die optimale Lösung dar.

Falls das Problem nicht abgeschlossen ist:

Angenommen, dass das Problem aufgrund eines vorherigen Fehlers nicht abgeschlossen ist, so müssten wir weitere Branches prüfen und verfeinern, um zu besseren Lösungen zu gelangen.

Ein möglicher nächster Branching-Schritt wäre die weitere Aufteilung von Zweigen, die nicht alle Nebenbedingungen erfüllten. Gegebenenfalls gibt es noch mögliche Grenzen von:

• Betrachten der potenziellen Werte: \(x_1\), \(x_2\), \(x_3\)

Zuvor wurden Werte ausgeschlossen oder konkretisiert. Kein weiterer Branching-Schritt war dabei nötig, demnach wäre die Endbedingung gegeben und das Verfahren kann abgeschlossen werden.

Zusammengefasst:

• Wenn beide Schranken übereinstimmen (wie in diesem Fall gezeigt): Abschluss.
• Geprüft, keine weiteren notwendigen Branching-Schritte: Abschluss.