Modul RobOptv: Robuste Optimierung 2 - Exam

Aufgabe 1)

KontextRobuste Optimierung ist ein Ansatz zur Bewältigung von Unsicherheiten in den Eingabedaten. Ziel ist es, Lösungen zu finden, die gegen verschiedene Szenarien akzeptabel bleiben. Häufig wird dies durch die Formulierung eines Minimax- oder szenariobasierten Optimierungsproblems erreicht, wobei ein Kompromiss zwischen Optimallösung und Robustheit erforderlich ist. Ein typisches robustes Optimierungsproblem kann folgendermaßen formuliert werden:

• Zielfunktion: \( \min_{x \in X} \max_{u \in U} f(x,u) \)

.Robuste Optimierung findet Anwendung in verschiedenen Bereichen wie Finanzwesen, Logistik und Ingenieurwesen.

a)

Sub-Übung 1Gegeben sei ein robustes Optimierungsproblem mit den folgenden Parametern:

• Entscheidungsvariablen: \( x \in \mathbb{R}^n \)
• Unsicherheitsraum: \( u \in U \)
• Zielfunktion: \( f(x,u) \)

.Formuliere und löse das robuste Optimierungsproblem für den Fall, dass die Zielfunktion \( f(x,u) = x^2 + u \). Der Unsicherheitsraum \( U \) sei als \( U = [0,1] \) gegeben. Überlege, was Du über die Berechnung der robusten Lösung aussagen kannst und begründe Deine Antwort mathematisch.

Lösung:

Lösung der Sub-Übung 1

• Gegeben:Entscheidungsvariablen:
  • \( x \text{ in } \mathbb{R}^n \)
  Unsicherheitsraum:
  • \( u \text{ in } U \)
  Zielfunktion:
  • \( f(x,u) = x^2 + u \)
  Der Unsicherheitsraum ist gegeben als
  • \( U = [0,1] \)
  .

• Zielfunktion umformulieren:Die Zielfunktion des robusten Optimierungsproblems ist:
  • \( \text{minimiere}_{x \in X} \text{ maximiere}_{u \in U} f(x,u) \)
  .Für das gegebene
  • \( f(x,u) = x^2 + u \)
  lässt sich diese wie folgt umschreiben:
  • \( \text{minimiere}_{x} \text{ maximiere}_{u \in [0,1]} (x^2 + u) \)
  .

• Maximiere bezüglich des Parameters:Da die Zielfunktion
  • \( f(x,u) = x^2 + u \)
  linear in
  • \( u \)
  ist, wird die Funktion maximiert, wenn
  • \( u \)
  den größten Wert in
  • \( U \)
  annimmt. Da
  • \( U \)
  auf
  • \( [0,1] \)
  beschränkt ist, ist der maximale Wert von
  • \( u = 1 \)
  .Also haben wir:
  • \( \text{max}_{u \in [0,1]} (x^2 + u) = x^2 + 1 \)
  .

• Minimiere bezüglich der Entscheidungsvariable:Nun minimieren wir
  • \( x^2 + 1 \)
  bezüglich
  • \( x \)
  . Da
  • \( x^2 \)
  quadratisch ist, ist der minimale Wert, den
  • \( x^2 \)
  annehmen kann
  • \( 0 \)
  (wenn
  • \( x = 0 \)
  ).Also bekommen wir:
  • \( \text{min}_{x} (x^2 + 1) = 1 \)
  .

• Fazit:Die robuste Lösung für das gegebene robuste Optimierungsproblem ist
  • \( x = 0 \)
  , und der entsprechende Wert der Zielfunktion ist
  • \( 1 \)
  .Das bedeutet, dass unabhängig vom Wert von
  • \( u \)
  im Intervall
  • \( [0,1] \)
  der maximale Wert der Zielfunktion
  • \( f(x,u) = 1 \)
  bei der robusten Lösungentscheidungsvariablen ist. Dies ist der Kompromiss, bei dem eine akzeptable Lösung für alle möglichen Unsicherheiten innerhalb des angegebenen Bereichs gefunden wird.

.

b)

Sub-Übung 2Diskutiere die Vor- und Nachteile der robusten Optimierung im Vergleich zur klassischen Optimierung. Gehe dabei insbesondere auf den Aspekt der Robustheit versus Optimalität ein und illustriere mithilfe eines praktischen Beispiels aus einem Bereich Deiner Wahl (z.B. Logistik, Finanzwesen).

Lösung:

Lösung der Sub-Übung 2

• Vor- und Nachteile der robusten Optimierung im Vergleich zur klassischen Optimierung:

• Vorteile der robusten Optimierung:
  • Robustheit und Sicherheit: Robuste Optimierung liefert Lösungen, die unter verschiedenen Unsicherheiten akzeptabel bleiben. Dies ist besonders wichtig in realen Anwendungen, wo Eingabedaten oft ungenau oder variabel sind.
  • Stabilität der Lösung: Die Lösungen tendieren dazu, weniger empfindlich auf Schwankungen und Fehler in den Eingabedaten zu reagieren, was zu stabileren und zuverlässigeren Entscheidungen führt.

• Nachteile der robusten Optimierung:
  • Weniger optimal: Da robuste Optimierung vorsichtiger an Unsicherheiten herangeht, können die gefundenen Lösungen weniger optimal im Sinne der klassischen Zielfunktion sein. Dies ist der Preis für die erhöhte Robustheit.
  • Komplexität: Robuste Optimierungsprobleme sind oft komplexer zu formulieren und zu lösen als klassische Optimierungsprobleme. Das kann zu höheren Rechenaufwand führen.

• Beispiel aus der Logistik:Betrachten wir eine Firma, die Lieferungen zu verschiedenen Standorten plant. Die klassische Optimierung würde das Problem der Minimierung der Gesamtkosten unter der Annahme fester und bekannter Transportzeiten und -kosten lösen. In der Realität können jedoch gelegentlich unerwartete Verkehrsprobleme oder Wetterbedingungen auftreten, die zu Schwankungen führen.
• Klassische Optimierung:
  • Optimiert die Kosten basierend auf den besten Annahmen der bekannten Parameter.
  • Kann bei unvorhergesehenen Ereignissen suboptimale oder sogar unpraktische Lösungen liefern.
• Robuste Optimierung in der Logistik:
  • Berücksichtigt mögliche Variabilitäten in den Transportzeiten und -kosten.
  • Liefert Lösungen, die unter verschiedenen Szenarien akzeptabel sind, z.B. durch Auswahl von Routen, die auch bei Verkehrsstörungen noch zuverlässig sind.
• Die robuste Lösung könnte höhere durchschnittliche Transportkosten aufweisen, dafür aber sicherstellen, dass die Lieferungen pünktlich und zuverlässig erfolgen, selbst unter den ungünstigsten Annahmen. Somit akzeptiert die Firma einen geringeren Grad an Optimalität der Kosten zugunsten der Robustheit und Verlässlichkeit der Lösung.

• Schlussfolgerung:Robuste Optimierung bietet erhebliche Vorteile in Szenarien mit Unsicherheiten, indem sie stabile und verlässliche Lösungen sicherstellt. Der Hauptnachteil liegt jedoch darin, dass die Lösungen weniger optimal in Bezug auf die Zielfunktion sein können und die Probleme komplexer zu lösen sind. Die Wahl zwischen robuster und klassischer Optimierung hängt letztlich von der spezifischen Anwendung und den damit verbundenen Unsicherheiten ab.

Aufgabe 2)

Du hast zwei Optimierungsansätze, die klassische (deterministische) Optimierung und die robuste Optimierung. Die klassische Optimierung geht von feststehenden Parametern aus und nimmt präzise Daten an. Im Gegensatz dazu berücksichtigt die robuste Optimierung Unsicherheiten in den Parametern und verwendet Modelle, die Bandbreiten und Unsicherheitsmengen einbeziehen. Dies führt zu oft komplexeren Formulierungen der Probleme, aber zu Ergebnissen, die weniger sensitiv gegenüber Datenabweichungen sind. Die robuste Zielfunktion kann formal als minimize \(\text{sup}_{u \in U} f(x,u)\) beschrieben werden, während die klassische Zielfunktion einfach als minimize \(f(x)\) formuliert wird. Obwohl robuste Ansätze den Zielwert häufig erhöhen, führen sie zu stabileren und widerstandsfähigeren Lösungen.

a)

a) Vergleiche anhand eines einfachen Beispiels die Ergebnissensitivität einer klassischen Optimierung mit der einer robusten Optimierung. Verwende folgende Zielfunktion für die klassische Optimierung:

Zielfunktion: \[f(x) = x^2 - 6x + 9\]

Führe zunächst die klassische Optimierung durch und bestimme den Wert von \(x\), der \(f(x)\) minimiert. Führe dann die robuste Optimierung durch, indem Du eine Unsicherheitsmenge für den Parameter \(6\) in der Zielfunktion durchführst, z.B., der Wert kann zwischen \(5.5\) und \(6.5\) variieren, und bestimme den entsprechenden optimalen \(x\).

Lösung:

Um die Ergebnissensitivität einer klassischen Optimierung mit der einer robusten Optimierung zu vergleichen, analysieren wir die gegebene Zielfunktion:

Zielfunktion: \[f(x) = x^2 - 6x + 9\]

Schritt 1: Klassische Optimierung

• Um die Zielfunktion zu minimieren, finden wir den kritischen Punkt durch Nullsetzen der ersten Ableitung:

Erste Ableitung: \[f'(x) = 2x - 6\]

Setze die erste Ableitung gleich null:

\[2x - 6 = 0\]\[2x = 6\]\[x = 3\]

• Der optimale Wert von \(x\) ist 3. Um sicherzustellen, dass es sich um ein Minimum handelt, betrachten wir die zweite Ableitung:

Zweite Ableitung: \[f''(x) = 2\]

• Da die zweite Ableitung positiv ist, bestätigt dies ein Minimum bei \(x = 3\).
• Der minimale Wert von \(f(x)\) ist daher:

\[f(3) = 3^2 - 6(3) + 9 = 0\]

Schritt 2: Robuste Optimierung

• Gehe nun die robuste Optimierung an, indem wir den Wert des Parameters 6 unsicher machen, und zwar in der Bandbreite [5.5, 6.5].
• Die Zielfunktion wird daher als:

\[f(x, u) = x^2 - ux + 9\]

wobei \(u\) im Bereich [5.5, 6.5] variiert.

• Unser Ziel ist es, die maximale Zielfunktion zu minimieren:

\[\min_x \sup_{u \in [5.5, 6.5]} (x^2 - ux + 9)\]

• Untersuche die Wirkung von \(u\) auf \(x\).
• Der kritische Punkt für einen allgemeinen Parameter \(u\) ist bei:

\[f'(x) = 2x - u\]

Setze die erste Ableitung gleich null:

\[2x = u\]\[x = \frac{u}{2}\]

• Um robust zu optimieren, betrachten wir die Extremwerte von \(u\), also 5.5 und 6.5.

Für \(u = 5.5\):

\[x = \frac{5.5}{2} = 2.75\]

• Berechne den Zielfunktionswert:

\[f(2.75, 5.5) = (2.75)^2 - 5.5(2.75) + 9 = 0.0625\]

Für \(u = 6.5\):

\[x = \frac{6.5}{2} = 3.25\]

• Berechne den Zielfunktionswert:

\[f(3.25, 6.5) = (3.25)^2 - 6.5(3.25) + 9 = 0.0625\]

• Für maximale Robustheit sollten wir im Bereich von \(x = 2.75\) bis \(x = 3.25\) operieren.

Daher wäre der stabile, widerstandsfähige Wert von \(x\) irgendwo in diesem Bereich.

Fazit:

• Die klassische Optimierung ergibt einen exakten optimalen Punkt bei \(x = 3\).
• Die robuste Optimierung hingegen zeigt, dass der optimale Punkt zwischen \(x = 2.75\) und \(x = 3.25\) variiert, je nach Unsicherheit des Parameters.
• Dies verdeutlicht, dass robuste Optimierung stabilere und widerstandsfähige Lösungen bietet, obwohl sie möglicherweise weniger präzise sind.

b)

b) Zeige, dass die Lösung der robusten Optimierung weniger sensitiv gegenüber Abweichungen im Parameter ist, indem Du die Werte von \(f(x)\) sowohl für den optimalen \(x\) aus der klassischen als auch aus der robusten Optimierung evaluierst, wenn der Wert des Parameters \(6\) auf \(6.3\) geändert wird.

Lösung:

Um zu zeigen, dass die Lösung der robusten Optimierung weniger sensitiv gegenüber Abweichungen im Parameter ist, evaluieren wir die Werte der Zielfunktionswerte für den optimalen Wert von \(x\) aus der klassischen und der robusten Optimierung, wenn der Parameter von 6 auf 6.3 geändert wird. Wir betrachten sowohl den klassischen optimalen Wert \(x = 3\) als auch die Werte \(x = 2.75\) und \(x = 3.25\) aus der robusten Optimierung.

Schritt 1: Klassische Optimierung

• Der klassische optimale Wert von \(x = 3\):

Zielfunktion: \[f(x) = x^2 - 6.3x + 9\]

Evaluieren bei \(x = 3\):

\[f(3) = 3^2 - 6.3(3) + 9 = 9 - 18.9 + 9 = -0.9\]

Schritt 2: Robuste Optimierung

• Robuste Optimierung gibt uns einen Bereich von optimalen \(x\)-Werten, nämlich von \(2.75\) bis \(3.25\).

Untersuchen wir die Zielfunktion für \(x = 2.75\) und \(x = 3.25\).

Evaluieren bei \(x = 2.75\):

\[f(2.75) = 2.75^2 - 6.3(2.75) + 9 = 7.5625 - 17.325 + 9 = -0.7625\]

Evaluieren bei \(x = 3.25\):

\[f(3.25) = 3.25^2 - 6.3(3.25) + 9 = 10.5625 - 20.475 + 9 = -0.9125\]

Fazit:

• Für den klassischen optimalen Wert \(x = 3\) ergibt sich, wenn der Parameter von 6 auf 6.3 geändert wird, ein Zielfunktionswert von \(-0.9\).
• Für die robusten optimalen Werte \(x = 2.75\) und \(x = 3.25\) ergeben sich Zielfunktionswerte von \(-0.7625\) und \(-0.9125\), die beide nah bei \(-0.9\) liegen.
• Diese Werte sind weniger sensitiv gegenüber der Parameteränderung, da sie eng um den klassischen Wert von \(-0.9\) verteilt sind. Dies zeigt, dass die robuste Optimierung stabilere Lösungen liefert.

c)

c) Diskutiere die Vor- und Nachteile, die robuste Optimierung im Vergleich zur klassischen Optimierung in einem praktischen Anwendungsszenario haben könnte, wie z.B. bei der Bestimmung der optimalen Lagerbestände in einem Unternehmen unter Berücksichtigung von Nachfrageschwankungen.

Lösung:

Die Wahl zwischen klassischer (deterministischer) Optimierung und robuster Optimierung hängt von den spezifischen Anforderungen und Bedingungen eines praktischen Anwendungsszenarios ab. Ein Beispiel für ein solches Anwendungsszenario ist die Bestimmung der optimalen Lagerbestände in einem Unternehmen unter Berücksichtigung von Nachfrageschwankungen. Im Folgenden werden die Vor- und Nachteile der robusten Optimierung im Vergleich zur klassischen Optimierung diskutiert:

Vorteile der robusten Optimierung:

• Widerstandsfähigkeit gegenüber Unsicherheiten: Robust optimierte Lösungen sind weniger sensitiv gegenüber Schwankungen und Unsicherheiten in den Eingabedaten. In unserem Beispiel würde dies bedeuten, dass die Lagerbestände besser auf unerwartete Nachfrageschwankungen reagieren können.
• Stabilität der Lösungen: Die durch robuste Optimierung ermittelten Lösungen sind stabiler und widerstandsfähiger gegenüber Datenabweichungen. Dies führt zu einer höheren Zuverlässigkeit der Planungen und Entscheidungen.
• Risikomanagement: Robuste Optimierung ermöglicht es Unternehmen, Risiken besser zu managen, indem sie sich auf die schlimmsten Szenarien vorbereiten. Dies ist besonders wichtig in unsicheren und volatilen Märkten.
• Längere Planungshorizonte: Durch die Berücksichtigung von Unsicherheiten ermöglichen robuste Modelle eine langfristigere und nachhaltigere Planung.

Nachteile der robusten Optimierung:

• Komplexität der Formulierung: Robuste Optimierung erfordert komplexere Modelle und mathematische Formulierungen. Dies kann den Implementierungsaufwand erhöhen und die benötigte Rechenzeit verlängern.
• Konservativität: Robuste Optimierung kann zu konservativeren Ergebnissen führen. Dies bedeutet, dass die Lösung möglicherweise nicht optimal ist, wenn die Unsicherheiten weniger schwerwiegend sind als antizipiert. Im Beispiel der Lagerbestände kann dies höhere Lagerhaltungskosten bedeuten.
• Datenanforderungen: Um Unsicherheiten korrekt zu modellieren, werden umfassendere und genauere Daten über die möglichen Schwankungen benötigt. Dies kann den Datenbeschaffungsaufwand erhöhen.

Vorteile der klassischen Optimierung:

• Einfachheit und Geschwindigkeit: Klassische Optimierung ist oft einfacher zu formulieren und zu lösen, da sie von festen Parametern ausgeht. Dies kann schnellere Lösungen ermöglichen.
• Optimalität unter festen Bedingungen: Wenn die Eingangsdaten sicher und zuverlässig sind, liefert die klassische Optimierung die optimalen Ergebnisse ohne die Notwendigkeit, konservative Annahmen zu treffen.
• Weniger Datenbedarf: Klassische Optimierung erfordert weniger umfangreiche Datensätze, da keine Unsicherheitsmengen modelliert werden müssen.

Nachteile der klassischen Optimierung:

• Sensitivität gegenüber Datenabweichungen: Lösungen aus der klassischen Optimierung sind oft empfindlich gegenüber Änderungen in den Eingangsdaten. Dies kann zu unzuverlässigen und instabilen Entscheidungen führen.
• Risiko der Nicht-Bewältigung von Unsicherheiten: In unsicheren Umgebungen können klassische optimierte Lösungen unzureichend sein und das Unternehmen höheren Risiken und Kosten aussetzen, wenn die Realität von den Annahmen abweicht.
• Beschränkter Planungshorizont: Ohne Berücksichtigung von Unsicherheiten sind die Lösungen weniger robust und nachhaltiger, was die langfristige Planung erschweren kann.

Fazit:Die Wahl zwischen klassischer und robuster Optimierung hängt von den spezifischen Anforderungen und Gegebenheiten des Szenarios ab. In volatilen und unsicheren Märkten bietet die robuste Optimierung Vorteile wie Stabilität und Widerstandsfähigkeit gegenüber Unsicherheiten, während die klassische Optimierung in stabilen und gut bekannten Umgebungen effizienter und einfacher sein kann.

Aufgabe 3)

Betrachten wir ein lineares Optimierungsproblem mit Unsicherheiten in den Eingabeparametern. Die Zielfunktion sowie die Nebenbedingungen können durch diese Unsicherheiten beeinflusst werden. Es gibt verschiedene Ansätze, um mit diesen Unsicherheiten umzugehen:

• Strafkostenansatz: Hinzufügen von Strafkosten für Abweichungen.
• Robustes Optimierungsproblem: Verwendung worst-case Szenarien.
• Stochastische Programmierung: Einbezug von Wahrscheinlichkeitsverteilungen.
• Szenariotechnik: Verschiedene mögliche Zukunftsszenarien berücksichtigen.
• Ellipsoide Unsicherheitsmengen: Annahme ellipsoidaler Unsicherheitsmengen für die Parameter.

a)

Eine Firma plant die Produktion von zwei Produkten (Produkt A und Produkt B) mit einem linearen Optimierungsmodell. Die Produktionskosten sind jedoch unsicher. Angenommen, die Kosten für Produkt A können zwischen 50 und 70 Euro pro Einheit variieren, und die Kosten für Produkt B können zwischen 80 und 100 Euro pro Einheit variieren.

• Stelle ein robustes Optimierungsmodell auf, indem Du die worst-case Szenarien verwendest.

Lösung:

Um ein robustes Optimierungsmodell zu erstellen, das die Unsicherheiten bei den Produktionskosten berücksichtigt und worst-case Szenarien verwendet, gehen wir von den höchsten möglichen Kosten für beide Produkte aus. Das bedeutet:

• Kosten für Produkt A: 70 Euro pro Einheit (worst-case)
• Kosten für Produkt B: 100 Euro pro Einheit (worst-case)

Das Ziel ist es, die gesamten Produktionskosten unter den schlimmsten Annahmen zu minimieren. Außerdem müssen bestimmte Nebenbedingungen erfüllt sein. Angenommen, die Firma hat folgende Nebenbedingungen:

• Die Gesamtproduktionskapazität beträgt maximal 500 Einheiten.
• Es müssen mindestens 100 Einheiten von Produkt A produziert werden.
• Es müssen mindestens 150 Einheiten von Produkt B produziert werden.

Das robuste lineare Optimierungsmodell wird wie folgt formuliert:

• Zielfunktion: Minimiere die gesamten Produktionskosten:

 Minimiere: 70x_A + 100x_B 

Nebenbedingungen:

• Gesamtproduktionskapazität begrenzt auf 500 Einheiten: \[x_A + x_B \leq 500\]
• Minimale Produktion von Produkt A (mindestens 100 Einheiten): \[x_A \geq 100\]
• Minimale Produktion von Produkt B (mindestens 150 Einheiten): \[x_B \geq 150\]
• Produktionsmengen müssen nicht-negativ sein: \[x_A, x_B \geq 0\]

Das vollständige lineare Optimierungsmodell lautet somit:

  Minimiere: 70x_A + 100x_B  unter den Bedingungen:  1. x_A + x_B \leq 500  2. x_A \geq 100  3. x_B \geq 150  4. x_A, x_B \geq 0  

Dieses Modell stellt sicher, dass die Produktionskosten minimiert werden und gleichzeitig die Kapazitäts- und Mindestproduktionsanforderungen erfüllt werden, selbst unter den schlechtesten Kostenbedingungen.

b)

Erweitere das Modell, das Du in Teil (a) entwickelt hast, indem Du den Strafkostenansatz anwendest. Füge Strafkosten für die Abweichungen von den mittleren Produktionskosten hinzu (mittlere Produktionskosten: 60 Euro für Produkt A und 90 Euro für Produkt B).

• Beschreibe, wie Du die Strafkosten in das Modell integrierst.
• Formuliere das neue Optimierungsproblem mathematisch.

Lösung:

Um das Modell aus Teil (a) zu erweitern und den Strafkostenansatz anzuwenden, müssen wir Strafkosten für die Abweichungen von den mittleren Produktionskosten einbeziehen. Die mittleren Produktionskosten sind:

• 60 Euro pro Einheit für Produkt A
• 90 Euro pro Einheit für Produkt B

Die Strafkosten werden berücksichtigt, indem wir die Differenz zwischen den worst-case Kosten und den mittleren Kosten als zusätzliche Kosten in die Zielfunktion aufnehmen. Sei:

• \(d_A\) die Abweichung der Produktionskosten von Produkt A: \(d_A = 70 - 60 = 10\) Euro pro Einheit
• \(d_B\) die Abweichung der Produktionskosten von Produkt B: \(d_B = 100 - 90 = 10\) Euro pro Einheit

Angenommen, die Strafkostenfaktoren für diese Abweichungen sind \(\beta_A\) und \(\beta_B\). In diesem Beispiel setzen wir \(\beta_A = 1\) und \(\beta_B = 1\) für den einfachsten Fall (diese Faktoren können angepasst werden, um unterschiedliche Strafgrößen zu berücksichtigen).

Die bereinigte Zielfunktion unter Berücksichtigung der Strafkosten lautet dann:

\[\text{Minimiere:}\: 70x_A + 100x_B + \beta_A \times d_A \times x_A + \beta_B \times d_B \times x_B\]

Setzen wir \(\beta_A = 1\) und \(\beta_B = 1\), erhalten wir:

\[\text{Minimiere:}\: 70x_A + 100x_B + 10x_A + 10x_B\]

Diese vereinfachte Zielfunktion lautet dann:

\[\text{Minimiere:}\: 80x_A + 110x_B\]

Nun formulieren wir das vollständige lineare Optimierungsproblem, einschließlich der gegebenen Nebenbedingungen:

• Zielfunktion:

\[\text{Minimiere:}\: 80x_A + 110x_B\]

Nebenbedingungen:

1. Gesamtproduktionskapazität (maximal 500 Einheiten): \[x_A + x_B \leq 500\]

2. Minimale Produktion von Produkt A (mindestens 100 Einheiten): \[x_A \geq 100\]

3. Minimale Produktion von Produkt B (mindestens 150 Einheiten): \[x_B \geq 150\]

4. Produktionsmengen müssen nicht-negativ sein: \[x_A, x_B \geq 0\]

Das vollständige mathematische Optimierungsproblem lautet somit:

  Minimiere: 80x_A + 110x_B unter den Bedingungen: 1. x_A + x_B \leq 500 2. x_A \geq 100 3. x_B \geq 150 4. x_A, x_B \geq 0  

Aufgabe 4)

Betrachte das folgende robuste Optimierungsproblem, das sicherstellen soll, dass eine Lösung unter allen möglichen Variationen der unsicheren Parameter funktioniert:

• Standardoptimierungsproblem: \( \text{minimize } f(x) \text{subject to } x \in X \)
• Robustes Optimierungsproblem: \( \text{minimize } f(x) \text{subject to } x \in X \forall u \in \mathcal{U} \)
• Die Unsicherheitsmenge \( \mathcal{U} \) beschreibt mögliche Variationen der unsicheren Parameter. Nehmen wir an, dass \( \mathcal{U} \) als ein Ellipsoid beschrieben wird.
• Ansätze: Worst-Case-Optimierung, Stochastische Programmierung

a)

(a) Formelisiere das robuste Optimierungsproblem explizit, wenn es sich um ein lineares Programm handelt. Verwende dabei die folgenden Annahmen:

• Ziel ist es, die Funktion \( c^T x \) zu minimieren.
• Die Beschränkungen haben die Form \( A x \leq b \).
• Stelle das Problem sicher, sodass es für alle möglichen Unsicherheiten in einem Ellipsoid \( \mathcal{U} = \{ u \in \mathbb{R}^m : (u - \mu)^T Q^{-1} (u - \mu) \leq 1 \} \) robust ist.

Lösung:

Gegeben sei das robuste Optimierungsproblem mit den genannten Annahmen. Um das robuste Optimierungsproblem explizit zu formulieren, wenn es sich um ein lineares Programm handelt, geht man wie folgt vor:

• Ziel ist es, die Funktion \( c^T x \) zu minimieren.
• Die Beschränkungen haben die Form \( A x \leq b \).
• Das Problem muss robust gegen alle möglichen Unsicherheiten in einem Ellipsoid \( \mathcal{U} = \{ u \in \mathbb{R}^m : (u - \mu)^T Q^{-1} (u - \mu) \leq 1 \} \) sein.

Folgende Schritte und Überlegungen sind notwendig:

1. Die ursprünglichen Beschränkungen sind: \( A x \leq b \).
2. Betrachte die Unsicherheitsmenge \( \mathcal{U} \), die als Ellipsoid beschrieben wird:

• \[ \mathcal{U} = \{ u \in \mathbb{R}^m : (u - \mu)^T Q^{-1} (u - \mu) \leq 1 \} \]

Um Robustheit zu gewährleisten, müssen die Beschränkungen für alle \( u \in \mathcal{U} \) erfüllt sein. Dies bedeutet:

• \[ A x \leq b + u, \forall u : (u - \mu)^T Q^{-1} (u - \mu) \leq 1 \]

Wir müssen das worst-case Szenario für die Unsicherheiten maximieren:

Setze die Definition des Ellipsoids \( \mathcal{U} \) ein, um das Problem zu formulieren. Wir können dies als ein Maximierungsproblem über die Unsicherheitsmenge ansehen:

• \[ a_i^T x \leq b_i + \max_{(u - \mu)^T Q^{-1} (u - \mu) \leq 1} u_i \]

Da \( (u - \mu)^T Q^{-1} (u - \mu) \leq 1 \) das Ellipsoid beschreibt, entspricht dies dem Maximum unter den stochastischen Bedingungen innerhalb des Ellipsoids. Man verwendet oftmals den Satz von \textit{Hoelder}, um dies zu berechnen:

Die maximale Störung unter den Unsicherheiten in einer Richtung \( a_i \) kann durch folgende Bedingung approximiert werden:

• \[ u_i = \mu_i + \sqrt{q_{ii}} z_i \]
• Hier bezieht sich \( z_i \) auf den entsprechenden Wert innerhalb des Ellipsoids, der das Maximum erreicht.

Das robuste Optimierungsproblem lautet daher:

• Ziel:
• \[ \text{minimiere } c^T x \]
• Beschränkungen:
• \[ a_i^T x \leq b_i + \sqrt{a_i^T Q a_i}, \forall i \]
• Mithilfe der maximal möglichen Störungen in Richtung der Beschränkungen, formuliert durch:
• \[ \max_{(u - \mu)^T Q^{-1} (u - \mu) \leq 1} (a_i u) = \sqrt{a_i^T Q a_i} \]

Zusammengefasst können wir das robuste lineare Optimierungsproblem folgendermaßen formulieren:

• \[ \text{minimiere } c^T x \]
• \[ \text{unter den Nebenbedingungen:}\]
• \[ a_i^T x \leq b_i + \sqrt{a_i^T Q a_i}, \forall i \]

b)

(b) Gegeben sei ein unsicherer Parameter \( a \) in der Beschränkung \( A x \leq b \). Nimm an, dass \( a \) im Intervall \( [\underline{a}, \overline{a}] \) variiert. Stelle das robuste Optimierungsproblem in diesem Fall auf.

Lösung:

Das robuste Optimierungsproblem in diesem Fall nimmt an, dass der unsichere Parameter \( a \) im Intervall \( [\underline{a}, \overline{a}] \) variiert. Wir wollen das Problem so formulieren, dass die Lösung robust gegen alle möglichen Werte von \( a \) in diesem Intervall ist.

Gegeben sei die Optimierungsaufgabe:

• Minimiere \( c^T x \)
• Unter den Beschränkungen \( A x \leq b \)
• mit einem unsicheren Parameter \( a \), der im Intervall \( [\underline{a}, \overline{a}] \) variiert

Das robuste Optimierungsproblem muss sicherstellen, dass die Beschränkung \( A x \leq b \) für jeden möglichen Wert von \( a \) in diesem Intervall erfüllt ist.

Formulieren wir das robuste Optimierungsproblem explizit:

• Für jede Zeile von \( A \), sagen wir \( a_i \), muss folgendes gelten:
• \[ \text{a}_i^T x \leq b_i \]
• Um die Robustheit zu gewährleisten, berücksichtigen wir die extremen Werte von \( a \). Dies bedeutet, dass die Beschränkung \( \text{a}_i^T x \leq b_i \) für:
• \( a = \underline{a} \)
• \( a = \overline{a} \)
• und alle Werte dazwischen erfüllt sein muss.
• Somit ergibt sich die robuste Beschränkung:
• \[ \overline{a}_i^T x \leq b_i \]
• und
• \[ \underline{a}_i^T x \leq b_i \]

Das vollständige robuste Optimierungsproblem lautet daher:

• Minimiere \( c^T x \)
• Unter den robusten Beschränkungen:
• \[ \overline{a}_i^T x \leq b_i, \forall i \]
• \[ \underline{a}_i^T x \leq b_i, \forall i \]

Dies stellt sicher, dass die Lösung \( x \) robust gegen alle möglichen Variationen des unsicheren Parameters \( a \) im gegebenen Intervall \( [\underline{a}, \overline{a}] \) ist.

c)

(c) Vergleiche die beiden Methoden, Worst-Case-Optimierung und Stochastische Programmierung, in Bezug auf ihre Anwendung und die Eigenschaften der Lösungen. Gehe dabei besonders auf Vor- und Nachteile ein.

Lösung:

Um die beiden Methoden, Worst-Case-Optimierung und Stochastische Programmierung, zu vergleichen, betrachten wir ihre Anwendungsbereiche sowie die Eigenschaften der resultierenden Lösungen. Jede Methode hat spezifische Vor- und Nachteile, die im nachfolgenden Vergleich untersucht werden.

• Worst-Case-Optimierung:
• Anwendung:Worst-Case-Optimierung sucht nach der besten Lösung, die unter den schlechtesten möglichen Bedingungen funktioniert. Die Methode wird oft in sicherheitskritischen Bereichen wie der Luftfahrt, Verteidigung und im Finanzwesen angewandt, wo es wichtig ist, extrem negative Szenarien zu berücksichtigen.
• Eigenschaften der Lösungen:Die Lösungen tendieren dazu, konservativ zu sein, da sie darauf ausgelegt sind, die schlimmsten Fälle zu bewältigen. Man nimmt an, dass die unsicheren Parameter den größtmöglichen Einfluss haben.
• Vorteile:- Robust gegenüber Extremereignissen und Unsicherheiten.- Sorgt für Lösungen, die in den schlechtesten Fällen praktikabel sind.- Reduziert das Risiko von katastrophalen Ausfällen.
• Nachteile:- Kann übermäßig konservativ sein, was zu ineffizienten oder suboptimalen Lösungen in normalen Szenarien führt.- Kann hohe Kosten und Ressourcenaufwand erfordern, um die schlimmsten Fälle zu berücksichtigen.- Nicht immer notwendig, wenn die Unsicherheiten gering sind.
• Stochastische Programmierung:
• Anwendung:Stochastische Programmierung berücksichtigt die Wahrscheinlichkeitsverteilung der unsicheren Parameter. Die Methode wird oft in betrieblichen Entscheidungsfindungsprozessen, Supply Chain Management und bei der finanziellen Planung eingesetzt, wo Unsicherheiten durch historische Daten oder Wahrscheinlichkeitsmodelle beschrieben werden.
• Eigenschaften der Lösungen:Die Lösungen sind in der Regel weniger konservativ und berücksichtigen verschiedene wahrscheinliche Szenarien. Es wird eine Balance zwischen dem erwarteten Nutzen und den Kosten der Unsicherheit gesucht.
• Vorteile:- Nutzt probabilistische Informationen, um fundiertere Entscheidungen zu treffen.- Liefert oft effizientere und kostengünstigere Lösungen im Vergleich zur Worst-Case-Optimierung.- Ermöglicht die optimale Entscheidungsfindung unter Berücksichtigung von Wahrscheinlichkeiten.
• Nachteile:- Erfordert detaillierte und präzise Wahrscheinlichkeitsverteilungen, die nicht immer verfügbar sind.- Weniger robust gegenüber unvorhergesehenen extremen Ereignissen.- Kann komplex sein und erfordert fortgeschrittene mathematische und statistische Methoden.

Zusammenfassung:

Die Wahl zwischen Worst-Case-Optimierung und Stochastischer Programmierung hängt stark vom Anwendungskontext und dem Risikoappetit ab:

• Worst-Case-Optimierung ist ideal für sicherheitskritische Anwendungen, bei denen extreme Ereignisse möglicherweise auftreten und berücksichtigt werden müssen. Sie garantiert robuste Lösungen, kann jedoch ineffizient sein, wenn die Extremereignisse selten sind.
• Stochastische Programmierung ist besser geeignet für Szenarien, in denen Unsicherheiten probabilistisch modelliert werden können. Sie bietet eine effizientere Balance zwischen Risiko und Kosten, ist jedoch anfällig für Fehler in der Wahrscheinlichkeitsverteilung und weniger robust gegenüber extremen Ereignissen.

d)

(d) Erkläre, wie sich die Formulierung des robusten Optimierungsproblems ändern würde, wenn anstelle eines Ellipsoids die Unsicherheitsmenge \( \mathcal{U} \) als ein Polyeder definiert ist. Beschreibe den allgemeinen Ansatz für die Lösung eines solchen Problems.

Lösung:

Bisher haben wir betrachtet, dass die Unsicherheitsmenge \( \mathcal{U} \) als ein Ellipsoid beschrieben wird. Wenn wir jedoch annehmen, dass die Unsicherheitsmenge \( \mathcal{U} \) als ein Polyeder definiert ist, ändert sich die Formulierung des robusten Optimierungsproblems erheblich. Schauen wir uns an, wie diese Formulierung aussieht und wie sie gelöst werden kann.

Definieren der Unsicherheitsmenge als Polyeder:

• Sei \( \mathcal{U} \) ein Polyeder, beschrieben durch:
• \[ \mathcal{U} = \{ u \in \mathbb{R}^m : D u \leq d \} \]
• Hierbei sind \( D \) und \( d \) Matrizen und Vektoren geeigneter Dimension.

Bei der Formulierung des robusten Optimierungsproblems müssen wir sicherstellen, dass die Beschränkungen \( A x \leq b \) unter allen möglichen Unsicherheiten in \( \mathcal{U} \) erfüllt werden, d.h.

• \[ A x \leq b \]
• für alle \( u \in \mathcal{U} \), also \( D u \leq d \)

Formulierung des robusten Optimierungsproblems:

• Originalbeschränkung: \( A x \leq b \)
• Robuste Beschränkung: \( A x \leq b + u \)
• für alle \( u \) in \( \mathcal{U} \)

Da \( \mathcal{U} \) ein Polyeder ist, können wir dieses Problem als eine Reihe von linearen Ungleichungen ausdrücken.

• Das robuste Optimierungsproblem wird dann zu:
• \[ A x \leq b + u \enspace \forall u \enspace \text{mit} \enspace D u \leq d \]

Allgemeiner Ansatz zur Lösung:

1. Ersetzen der unsicheren Parameter \( u \) durch ihre obere Schranke, was bedeutet, dass wir die Maximierung über \( u \) innerhalb des Polyeders \( \mathcal{U} \) berücksichtigenn:

• \[ \text{maximiere} \enspace u \text{ unter} \enspace D u \leq d \]
• Dies kann als ein duales Problem zu einem linearen Programm formuliert werden.

Führen Sie die Robustifizierungsbedingung für jede Beschränkung ein. Für jede Zeile \( i \) von \( A \) gilt:

• \[ a_i^T x \leq b_i + \max_{u \mathcal{U}} u_i \]

Schreiben Sie das Problem als eine Reihe von linearen Programmen:

\[ \max (a_i^T x) \enspace \text{unter} \enspace D u \leq d \]

Dies führt zu einer Sammlung von linearen Programmen, die parallel oder sukzessiv gelöst werden können.

Das resultierende Problem ist ein LP (lineares Programm), das durch Standardmethoden wie den Simplex-Algorithmus gelöst werden kann.

Zusammenfassung:

Wenn die Unsicherheitsmenge \( \mathcal{U} \) als ein Polyeder beschrieben wird, ändert sich das robuste Optimierungsproblem dahingehend, dass die Unsicherheiten durch lineare Ungleichungen beschränkt werden. Diese Bedingung kann als eine Sammlung von linearen Programmen formuliert und durch Standardmethoden gelöst werden. Dies macht die robuste Optimierungsformulierung flexibler und potentiell effizienter zu lösen im Vergleich zur Ellipsoid-Annäherung, die oft quadratische Programmiertechniken erfordert.