Robust optimization II - Exam

Aufgabe 1)

Stellen Sie sich vor, Sie leiten ein Unternehmen, das Fahrräder herstellt. Die Herstellungskosten und Verkaufserlöse unterliegen Schwankungen aufgrund von Materialkosten und Marktbedingungen. Sie möchten eine robuste Optimierung durchführen, um die Gesamtgewinne in diesem unsicheren Umfeld zu maximieren.

b)

Betrachten Sie eine beispielhafte Unsicherheitsmenge: \( \mathcal{U} = \{(c, p) \mid |c - c_0| \leq \Delta c, |p - p_0| \leq \Delta p\} \). Erklären Sie, was dies in Bezug auf die Schwankungen in den Kosten \( c \) und den Verkaufserlösen \( p \) bedeutet. Gehen Sie darauf ein, wie diese Schwankungen die Gewinnfunktion beeinflussen.

Lösung:

Um die gegebene Unsicherheitsmenge \(\mathcal{U}\) und ihre Bedeutung zu erklären, betrachten wir die Definition der Unsicherheitsmenge:

 \(\mathcal{U} = \{(c, p) \mid |c - c_0| \leq \Delta c, |p - p_0| \leq \Delta p\}\) 

Diese Menge beschreibt die Unsicherheiten in den Materialkosten \(c\) und den Verkaufserlösen \(p\). Die Parameter \(c_0\) und \(p_0\) stellen die nominalen (mittleren) Werte für Materialkosten und Verkaufspreise dar, während \(\Delta c\) und \(\Delta p\) die maximalen Schwankungen um diese nominalen Werte sind.

• Materialkosten (\(c\)): \( |c - c_0| \leq \Delta c \) bedeutet, dass die Materialkosten \(c\) innerhalb des Intervalls \([c_0 - \Delta c, c_0 + \Delta c]\) variieren können. Dies repräsentiert die Unsicherheit in den Materialkosten. Zum Beispiel, wenn \(c_0\) die durchschnittlichen Materialkosten für ein Fahrrad sind, dann können diese Materialkosten um einen Betrag von bis zu \(\Delta c\) nach oben oder unten schwanken.
• Verkaufserlöse (\(p\)): \( |p - p_0| \leq \Delta p \) bedeutet, dass die Verkaufserlöse \(p\) innerhalb des Intervalls \([p_0 - \Delta p, p_0 + \Delta p]\) variieren können. Dies repräsentiert die Unsicherheit in den Verkaufserlösen. Zum Beispiel, wenn \(p_0\) der durchschnittliche Verkaufspreis pro Fahrrad ist, dann kann der tatsächliche Verkaufspreis um einen Betrag von bis zu \(\Delta p\) nach oben oder unten schwanken.

Nun betrachten wir, wie diese Schwankungen die Gewinnfunktion beeinflussen:

 \(f(X, (c, p)) = \text{Gesamterlös} - \text{Herstellungskosten} - \text{Sonstige Kosten}\) 

Der Gesamterlös und die Herstellungskosten, die durch die Unsicherheiten beeinflusst werden, können wie folgt beschrieben werden:

• Gesamterlös: Der Gesamterlös hängt vom Verkaufspreis und der produzierten Menge ab. Falls der Verkaufspreis \(p\) schwankt, werden auch die Gesamterlöse entsprechend schwanken.
• Herstellungskosten: Die Herstellungskosten hängen von den Materialkosten und den Produktionsmengen ab. Falls die Materialkosten \(c\) schwanken, ändern sich auch die gesamten Herstellungskosten entsprechend.

Somit können wir die Gewinnfunktion unter Einbeziehung der Unsicherheiten darstellen:

 \( f(X, (c, p)) = (p_0 \pm \Delta p) \times \text{Produzierte Menge} - (c_0 \pm \Delta c) \times \text{Produzierte Menge} - \text{Sonstige Kosten}\) 

Die Schwankungen \(\Delta c\) und \(\Delta p\) führen zu einer Änderung der Gesamterlöse und der Herstellungskosten, wodurch sich die Gewinne ebenfalls ändern. Das Ziel der robusten Optimierung ist es, die Entscheidungen so zu treffen, dass die gesamten Gewinne maximiert werden, selbst unter den gegebenen Unsicherheiten.

c)

Für den Fall, dass die Herstellungskosten \( c \) und der Verkaufserlös \( p \) als lineare Funktionen eines Unsicherheitsparameters \( u \in \mathcal{U} \) modelliert werden können, formulieren Sie die Gewinnfunktion \( f(x, u) \) und das daraus resultierende robuste Optimierungsproblem. Verwenden Sie die Definition \( c = c_0 + u_1 \) und \( p = p_0 + u_2 \).

Lösung:

Für den Fall, dass die Herstellungskosten \(c\) und der Verkaufserlös \(p\) als lineare Funktionen eines Unsicherheitsparameters \( u \in \mathcal{U} \) modelliert werden können, können wir die folgende Formulierung verwenden:

• \( c = c_0 + u_1 \)
• \( p = p_0 + u_2 \)

Hierbei sind \( c_0 \) die nominalen Herstellungskosten und \( p_0 \) die nominalen Verkaufspreise. \( u_1 \) und \( u_2 \) sind die Unsicherheitsparameter, die die Abweichungen von den nominalen Werten beschreiben. Die Unsicherheitsmenge \(\mathcal{U}\) wird dann definiert als:

 \(\mathcal{U} = \left\{ (u_1, u_2) \mid -\Delta c \leq u_1 \leq \Delta c, -\Delta p \leq u_2 \leq \Delta p \right\} \) 

Die Gewinnfunktion \( f(x, u) \) unter Berücksichtigung der Variablen sowie der Unsicherheitsparameter lässt sich dann wie folgt definieren:

 \[ f(X, u) = \text{Gesamterlös} - \text{Herstellungskosten} - \text{Sonstige Kosten} \] \[ \text{Gesamterlös} = (p_0 + u_2) \times x \] \[ \text{Herstellungskosten} = (c_0 + u_1) \times x \] \[ \text{Sonstige Kosten} = S \] \[ \text{Also ist} \] \[ f(X, u) = (p_0 + u_2) \times x - (c_0 + u_1) \times x - S \] \[ f(X, u) = x \times (p_0 + u_2 - c_0 - u_1) - S \] 

Das Ziel des robusten Optimierungsproblems ist es, die Gewinnfunktion \( f(X, u) \) zu maximieren, wobei die Unsicherheitsmenge \(\mathcal{U}\) berücksichtigt wird. Das robuste Optimierungsproblem lautet also:

 \[ \text{Maximiere} \; \min_{u \in \mathcal{U}} \; f(X, u) \] \[ \text{unter der Nebenbedingung, dass} \; x \geq 0 \] 

Mit anderen Worten, wir suchen die Produktionsmenge \(x\), die den Gewinn maximiert, unter Berücksichtigung der schlimmsten möglichen Abweichungen der Herstellungskosten und Verkaufserlöse innerhalb der vorher definierten Unsicherheitsmenge \(\mathcal{U}\).

d)

Lösen Sie das robuste Optimierungsproblem unter der Annahme, dass \( c_0 = 50 \) Euro, \( p_0 = 150 \) Euro, \Delta c = 10 \ und \Delta p = 20 \ Euro. Verwenden Sie die formale Methode zur Entscheidungsfindung unter Unsicherheit und bestimmen Sie die optimalen Herstellungsmengen \( x \) für den schlimmstmöglichen Fall.

Lösung:

Um das robuste Optimierungsproblem zu lösen, unter der Annahme, dass die nominalen Werte und Unsicherheiten wie folgt gegeben sind:

• \( c_0 = 50 \) Euro
• \( p_0 = 150 \) Euro
• \( \Delta c = 10 \) Euro
• \( \Delta p = 20 \) Euro

Verwenden wir die folgenden Unsicherheitsparameter innerhalb ihrer definierten Schwankungsbereiche:

• \(c = c_0 + u_1 \)
• \(p = p_0 + u_2 \)

wobei \( u_1 \in [-10, 10] \) und \( u_2 \in [-20, 20] \). Der schlimmstmögliche Fall tritt ein, wenn die Herstellungskosten maximal und die Verkaufserlöse minimal sind. Das bedeutet:

• Maximale Herstellungskosten: \(c = c_0 + \Delta c = 50 + 10 = 60 \) Euro
• Minimale Verkaufserlöse: \(p = p_0 - \Delta p = 150 - 20 = 130 \) Euro

Die Gewinnfunktion \( f(x, u) \) für den schlimmstmöglichen Fall lautet dann:

 \[ f(X, u) = x(p - c) - S \] \[ f(X, u) = x(130 - 60) - S \] \[ f(X, u) = x(70) - S \] 

Um den Gewinn zu maximieren, setzen wir dabei \( S \) als die sonstigen fixen Kosten. Um die optimalen Herstellungsmengen zu bestimmen, betrachten wir die Nebenbedingung:

 \[ \text{Maximiere} \; x(70) - S \; \text{unter der Bedingung} \; x \geq 0 \] 

Da sich die Ableitung der Gewinnfunktion nach \( x \) leicht berechnen lässt:

 \[ f'(x) = 70 \] 

Da \( f'(x) = 70 \) positiv ist, bedeutet dies, dass der Gewinn unbegrenzt wächst, je mehr wir produzieren. In der Realität gibt es jedoch Kapazitätsbeschränkungen für die Produktion sowie Markt- und Ressourcenbegrenzungen. Wenn wir die einfache Interpretation des Worst-Case-Szenarios ohne zusätzliche Nebenbedingungen betrachten, ergibt sich:

 \[ \text{Optima x}\rightarrow \infty \] 

Dies ist jedoch praktisch nicht machbar. Unter realistischen Bedingungen müssen wir nun zusätzliche Beschränkungen und Faktoren berücksichtigen, um die praktikable Anzahl an herzustellenden Fahrrädern zu bestimmen. Ein realistischer Ansatz wäre, spezifische Kapazitätsbeschränkungen zu definieren, z.B.:

• Produktionskapazität
• Marktnachfrage
• Ressourcenverfügbarkeit

Unter Annahme einer Maximalkapazität von \( x_{max} \) Fahrrädern, kann die optimale Herstellungsmengen \(x\) als:

 \[ f_{max}(X, u) = x_{max} \] 

oder abhängig von den zusätzlichen betrieblichen Kenndaten definiert werden. Dies sollte noch spezifischer geprüft werden, um die praktikabelste Lösung zu identifizieren.

Aufgabe 3)

In einem Produktionsunternehmen sollen verschiedene Produkte hergestellt werden. Die Produktionsprozesse unterliegen unterschiedlichen Material-, Kapazitäts- und Arbeitszeiteinschränkungen. Ziel ist es, den Gewinn zu maximieren. Die mathematische Formulierung des Optimierungsproblems ist notwendig, um die beste Produktionsstrategie zu bestimmen.

• Die Produkte sind durch Entscheidungsvariablen dargestellt: x₁, x₂, ..., x_n (Anzahl der herzustellenden Einheiten der verschiedenen Produkte).
• Die Gewinnfunktion lautet: G = c₁x₁ + c₂x₂ + ... + c_nx_n (wobei c_i den Gewinn pro Einheit des i-ten Produkts darstellt).
• Die Materialeinschränkungen sind als: a_i1x₁ + a_i2x₂ + ... + a_inx_n ≤ b_i (wobei a_ij die Materialmengen der i-ten Ressource pro Einheit des j-ten Produkts und b_i die verfügbare Menge der i-ten Ressource darstellt).
• Kapazitäts- und Arbeitszeiteinschränkungen werden ebenfalls in ähnlicher Weise formuliert: d_i1x₁ + d_i2x₂ + ... + d_inx_n ≤ e_i (wobei d_ij die benötigte Kapazität bzw. Arbeitszeit der i-ten Art pro Einheit des j-ten Produkts und e_i die verfügbare Kapazität bzw. Arbeitszeit der i-ten Art darstellt).

a)

Formuliere die allgemeine Optimierungsaufgabe für das beschriebene Produktionsproblem in mathematischer Form. Achte darauf, die Zielsetzung und sämtliche Einschränkungen korrekt zu berücksichtigen.

Lösung:

Um das beschriebene Produktionsproblem in mathematischer Form zu formulieren, müssen die Zielfunktion und alle Einschränkungen berücksichtigt werden. Hier ist die allgemeine Darstellung:

• Zielfunktion:

Das Ziel ist es, den Gewinn zu maximieren. Die Zielfunktion lautet:

Maximiere G:

\[ \text{G} = c_1 x_1 + c_2 x_2 + \dots + c_n x_n \]

• Einschränkungen:

1. Materialeinschränkungen:

\[ a_{11} x_1 + a_{12} x_2 + \dots + a_{1n} x_n \leq b_1 \]\[ a_{21} x_1 + a_{22} x_2 + \dots + a_{2n} x_n \leq b_2 \]\[ \vdots \]\[ a_{m1} x_1 + a_{m2} x_2 + \dots + a_{mn} x_n \leq b_m \]

2. Kapazitäts- und Arbeitszeiteinschränkungen:

\[ d_{11} x_1 + d_{12} x_2 + \dots + d_{1n} x_n \leq e_1 \]\[ d_{21} x_1 + d_{22} x_2 + \dots + d_{2n} x_n \leq e_2 \]\[ \vdots \]\[ d_{m1} x_1 + d_{m2} x_2 + \dots + d_{mn} x_n \leq e_m \]

3. Nicht-Negativitätsbedingungen:

\[ x_1, x_2, \dots, x_n \geq 0 \]

b)

Angenommen, das Unternehmen produziert nur zwei Produkte. Die Gewinnfunktion ist wie folgt gegeben: G = 5x₁ + 7x₂. Gegeben sind die folgenden Material- und Kapazitätseinschränkungen:

• Materialeinschränkungen:
  • 2x₁ + 3x₂ ≤ 100
• Kapazitätseinschränkungen:
  • 4x₁ + 2x₂ ≤ 80

Stelle das konkrete Optimierungsproblem in mathematischer Form dar.

Lösung:

Das konkrete Optimierungsproblem für das Unternehmen, das nur zwei Produkte herstellt, kann wie folgt formuliert werden:

• Zielfunktion:

Maximiere G:

\[ G = 5x_1 + 7x_2 \]

• Einschränkungen:

1. Materialeinschränkungen:

\[ 2x_1 + 3x_2 \leq 100 \]

2. Kapazitätseinschränkungen:

\[ 4x_1 + 2x_2 \leq 80 \]

3. Nicht-Negativitätsbedingungen:

\[ x_1 \geq 0 \]

\[ x_2 \geq 0 \]

Aufgabe 4)

Du entwickelst ein System für ein Logistikunternehmen, das in einem unsicheren Umfeld agiert. Um die Zuverlässigkeit und Effizienz des Systems zu gewährleisten, möchtest Du robuste Optimierungstechniken anwenden. Im Folgenden wirst Du mehrere Schritte durchführen, um die Unsicherheiten zu modellieren und geeignete Lösungen zu finden.

a)

Beschreibe die Unterschiede zwischen stochastischen und nicht-stochastischen Unsicherheiten. Gib dabei jeweils ein praktisches Beispiel aus dem Logistikumfeld an.

Lösung:

• Stochastische Unsicherheiten:Stochastische Unsicherheiten sind Unsicherheiten, die sich durch zufällige Variablen und Wahrscheinlichkeitsverteilungen modellieren lassen. Sie basieren auf bekannten oder schätzbaren Wahrscheinlichkeitsverteilungen und lassen sich somit statistisch analysieren.Beispiel aus dem Logistikumfeld: Die Lieferzeit eines Pakets kann als stochastische Unsicherheit betrachtet werden. Faktoren wie Verkehr, Wetterbedingungen oder Zwischenfälle auf der Route können variieren und führen zu einer variablen, aber statistisch analysierbaren Lieferzeit. Die Verteilung dieser Lieferzeiten kann z.B. normal- oder poissonverteilten sein.
• Nicht-stochastische Unsicherheiten:Nicht-stochastische Unsicherheiten, auch als Unsicherheiten vom schlimmsten Fall oder robuste Unsicherheiten bekannt, sind solche, bei denen keine genaue Wahrscheinlichkeitsverteilung zur Beschreibung der Unsicherheit vorhanden ist. Stattdessen wird ein deterministischerer Ansatz genutzt, oft mit vorgegebenen unsicheren Parametern, die in bestimmten Intervallen variieren können.Beispiel aus dem Logistikumfeld: Eine plötzlich auftretende Straßensperrung aufgrund von Bauarbeiten stellt eine nicht-stochastische Unsicherheit dar. Es ist schwierig, eine genaue Verteilung für das Auftreten solcher Ereignisse zu erstellen, aber man kann sie durch eine Worst-Case-Betrachtung einschätzen, indem man z.B. Verzögerungen im schlimmsten Fall in die Routenplanung mit einbezieht.

c)

Erkläre die Technik der Sensitivitätsanalyse im Kontext der Logistik. Wie hilft diese Technik, Unsicherheiten zu managen? Nenne dazu ein konkretes Beispiel.

Lösung:

• Technik der Sensitivitätsanalyse im Kontext der Logistik:Die Sensitivitätsanalyse ist eine Technik, die eingesetzt wird, um die Auswirkungen von Veränderungen in den Eingabeparametern eines Modells auf die Ergebnisse dieses Modells zu untersuchen. In der Logistik kann diese Technik verwendet werden, um zu verstehen, wie verschiedene Unsicherheiten – wie z.B. Lieferzeiten, Transportkosten oder Nachfrage – die Systemleistung beeinflussen.
• Wie hilft diese Technik, Unsicherheiten zu managen?Durch die Sensitivitätsanalyse können Logistikmanager feststellen, welche Parameter am sensibelsten auf Änderungen reagieren und somit die größte Unsicherheit verursachen. Dies ermöglicht es ihnen, gezielt Maßnahmen zu ergreifen, um diese Unsicherheiten zu minimieren oder deren Einfluss auf das System zu reduzieren. Diese Technik hilft auch bei der Identifikation von Szenarien, die potenziell problematisch sind, und ermöglicht eine bessere Vorbereitung und Planung.
• Konkretes Beispiel:Stell Dir vor, ein Logistikunternehmen möchte die Sensitivität der Gesamtkosten hinsichtlich der Schwankungen in den Kraftstoffpreisen analysieren. Durch die Sensitivitätsanalyse könnte das Unternehmen unterschiedliche Szenarien modellieren, z.B. einen Anstieg oder Rückgang der Kraftstoffpreise um 10%, 20% oder 30%. Die Analyse würde zeigen, wie empfindlich die Gesamtkosten des Unternehmens auf diese Änderungen reagieren. Sollte die Analyse zeigen, dass die Gesamtkosten stark von den Kraftstoffpreisen abhängen, könnte das Unternehmen Maßnahmen ergreifen, um diese Unsicherheit zu managen, z.B. durch langfristige Kraftstoffverträge oder Investitionen in effizientere Fahrzeuge.

d)

Betrachte ein Szenario, in dem der Kraftstoffpreis aufgrund geopolitischer Spannungen stark variiert. Beschreibe, wie Du mit der Methode der Szenarioanalyse robuste Entscheidungen hinsichtlich der Routenplanung treffen würdest. In deiner Antwort sollten mindestens drei verschiedene Szenarien berücksichtigt werden.

Lösung:

• Robuste Entscheidungen mit der Methode der Szenarioanalyse:In einem Umfeld, in dem der Kraftstoffpreis stark variiert, ist es wichtig, robuste Entscheidungen für die Routenplanung zu treffen, um die Unsicherheiten zu minimieren. Die Methode der Szenarioanalyse ermöglicht es, verschiedene Zukunftsszenarien zu betrachten und die möglichen Auswirkungen auf die Routenplanung zu analysieren. Hier sind die Schritte, die Du unternehmen würdest:
• Schritt 1: Definition der SzenarienIdentifiziere und definiere mindestens drei unterschiedliche Szenarien basierend auf möglichen geopolitischen Entwicklungen:
• Szenario 1: Niedrige KraftstoffpreiseDieses Szenario nimmt an, dass die geopolitischen Spannungen nachlassen und die Kraftstoffpreise sinken. Dies könnte durch vermehrte Produktionskapazitäten oder Friedensabkommen verursacht werden. Angenommener Kraftstoffpreis: z.B. 1,20 €/Liter.
• Szenario 2: Moderate KraftstoffpreiseDies ist das Basisszenario, bei dem die Kraftstoffpreise stabil bleiben und nur geringfügige Schwankungen aufweisen. Angenommener Kraftstoffpreis: z.B. 1,50 €/Liter.
• Szenario 3: Hohe KraftstoffpreiseDieses Szenario berücksichtigt eine Eskalation der geopolitischen Spannungen, die zu einem erheblichen Anstieg der Kraftstoffpreise führt. Angenommener Kraftstoffpreis: z.B. 2,00 €/Liter.
• Schritt 2: Analyse der SzenarienFür jedes der definierten Szenarien wird eine detaillierte Kostenanalyse der Routenplanung durchgeführt. Dabei werden die direkten Kraftstoffkosten sowie potenzielle indirekte Kosten (z.B. Verzögerungen, Änderungen der Routenführung) berücksichtigt.
• Schritt 3: Bewertung und Vergleich der RoutenVergleiche die Ergebnisse der Kostenanalyse für jede Route unter den verschiedenen Szenarien. Identifiziere Routen, die unter allen Szenarien die geringsten Gesamtkosten verursachen oder zumindest akzeptable Kosten aufweisen. Diese Routen gelten als robust.
• Schritt 4: Entscheidung treffenBasierend auf den Analysen und Vergleichen wählst Du die Routen aus, die unter möglichst vielen Szenarien gut abschneiden. Zudem kannst Du Strategien wie die Diversifizierung der Routen anwenden, um das Risiko weiter zu minimieren.
• Beispiel für robuste Routenplanung:Angenommen, Du analysierst drei Routen zwischen zwei Städten:
• Route A: Direkt, aber kraftstoffintensiv
• Route B: Mittellange Route mit moderaten Kraftstoffkosten
• Route C: Längere Route mit niedrigeren Kraftstoffkosten
Nach der Szenarioanalyse stellst Du fest, dass Route B in allen drei Szenarien moderate bis niedrige Gesamtkosten verursacht, während Route A bei hohen Kraftstoffpreisen sehr teuer wird und Route C bei niedrigen Kraftstoffpreisen ungünstig ist. Daher entscheidest Du Dich für Route B als robuste Route.