Stochastische Programmierung

Stochastische Programmierung (englisch stochastic programming) ist ein Teilgebiet der mathematischen Programmierung, das Modelle und Methoden zur Lösung von Optimierungsaufgaben unter Unsicherheit entwickelt, bei denen einige Modellparameter nicht exakt bekannt sind, sondern als Zufallsvariablen mit bekannten oder geschätzten Wahrscheinlichkeitsverteilungen dargestellt werden.

Im Gegensatz zu deterministischen Problemen, bei denen alle Daten als gegebene Konstanten betrachtet werden, zielt die stochastische Programmierung darauf ab, eine Lösung (oder eine Entscheidungsstrategie) zu finden, die in einem statistischen Sinne optimal ist. Meistens bedeutet dies die Minimierung oder Maximierung des Erwartungswertes der Zielfunktion. Die zentrale Idee besteht darin, eine Entscheidungsstrategie zu finden, die „im Durchschnitt“ über alle möglichen Realisierungen der Zufallsparameter am besten ist. Dies ist besonders relevant für Probleme, bei denen Entscheidungen wiederholt unter ähnlichen Bedingungen getroffen werden (z. B. im Bestandsmanagement oder bei der Steuerung von Energiesystemen).

Mathematische Formulierung des Problems

In allgemeiner Form kann ein stochastisches Programmierproblem wie folgt formuliert werden: $\underset{x\in X}{min}𝔼[f(x,\xi )]$ wo:

• $x$ – der Vektor der Entscheidungsvariablen (Entscheidungen) ist, die bestimmt werden müssen.
• $X$ – die zulässige Menge der Entscheidungen für $x$ ist, die durch deterministische Nebenbedingungen definiert wird.
• $\xi$ – ein Zufallsvektor ist, der die unsicheren Parameter des Problems darstellt (z. B. Nachfrage, Preise, Wetterbedingungen).
• $f(x,\xi )$ – die Zielfunktion ist, deren Wert sowohl von der getroffenen Entscheidung $x$ als auch von der Realisierung des Zufallsvektors $\xi$ abhängt.
• $𝔼[\cdot ]$ – der Erwartungswertoperator ist, der über die Wahrscheinlichkeitsverteilung des Vektors $\xi$ berechnet wird.

Ein wesentliches Prinzip, das mehrstufigen stochastischen Modellen zugrunde liegt, ist das Nicht-Antizipativitätsprinzip (englisch non-anticipativity principle). Es besagt, dass Entscheidungen, die in einer bestimmten Stufe getroffen werden, nur von den bis zu diesem Zeitpunkt verfügbaren Informationen abhängen dürfen und nicht „in die Zukunft blicken“ können.

Zweistufiges Problem mit Rückgriff

Das am weitesten verbreitete Modell ist das zweistufige stochastische Programm mit Rückgriff (englisch two-stage stochastic program with recourse). Der Entscheidungsprozess ist in zwei Stufen unterteilt:

1. Erste Stufe: Eine „Hier-und-Jetzt“-Entscheidung (here-and-now) wird getroffen – der Vektor $x$ wird bestimmt. Diese Entscheidung muss getroffen werden, bevor die spezifische Realisierung des Zufallsvektors $\xi$ bekannt ist.
2. Zweite Stufe: Nachdem das zufällige Ereignis eingetreten ist, wird eine korrigierende oder kompensatorische Entscheidung (recourse decision) getroffen – der Vektor $y(\xi )$, der darauf abzielt, negative Konsequenzen zu minimieren oder günstige Gelegenheiten zu nutzen, die sich aus der Kombination der Entscheidung der ersten Stufe $x$ und dem Ergebnis $\xi$ ergeben.

Mathematisch wird ein zweistufiges stochastisches lineares Programmierproblem wie folgt formuliert: $\underset{x\in {ℝ}^{n_1}}{min}\{c^{T}x+{𝔼}_{\xi }[Q(x,\xi )]\}$ unter den Nebenbedingungen der ersten Stufe: $Ax=b,x\ge 0$. Hierbei ist $Q(x,\xi )$ die Rückgriffsfunktion (recourse function), die den optimalen Wert des Problems der zweiten Stufe darstellt: $Q(x,\xi )=\underset{y\in {ℝ}^{n_2}}{min}\{q(\xi {)}^{T}y\mid T(\xi )x+Wy=h(\xi ),y\ge 0\}$ wobei $\xi$ ein Zufallsvektor ist, der die Parameter $q(\xi ),T(\xi )$ und $h(\xi )$ umfasst; und $c,A,b$ und $W$ deterministische Parameter sind.

Schlüsseleigenschaften und Theoreme

• Konvexität: Eines der fundamentalen Ergebnisse der Theorie ist, dass für ein zweistufiges stochastisches lineares Programmierproblem die erwartete Rückgriffsfunktion $Q(x)={𝔼}_{\xi }[Q(x,\xi )]$ eine konvexe Funktion ist. Diese Eigenschaft ist von großer Bedeutung, da sie garantiert, dass das Gesamtproblem der ersten Stufe ein konvexes Optimierungsproblem ist, für das effiziente Lösungsmethoden existieren und bei dem das globale Optimum mit dem lokalen Optimum übereinstimmt.
• Deterministisches Äquivalent: Wenn der Zufallsvektor $\xi$ eine endliche Anzahl möglicher Realisierungen (Szenarien) ${\xi }_1,\dots ,{\xi }_K$ mit den Wahrscheinlichkeiten $p_1,\dots ,p_K$ hat, kann das stochastische Programmierproblem als ein einziges großes deterministisches Optimierungsproblem umformuliert werden. In diesem Fall wird der Erwartungswert durch eine gewichtete Summe über alle Szenarien ersetzt. Die Größe dieses Problems wächst jedoch linear mit der Anzahl der Szenarien, was zum „Fluch der Dimensionalität“ führt und diesen Ansatz für eine große Anzahl von Szenarien rechnerisch unlösbar macht.

Vergleich mit robuster Optimierung

Die stochastische Programmierung ist einer von mehreren Ansätzen zur Optimierung unter Unsicherheit. Ihr Hauptunterschied zur robusten Optimierung liegt in der Art der Modellierung der Unsicherheit und dem Optimalitätskriterium.

Vergleich der Ansätze zur Optimierung unter Unsicherheit

Kriterium	Stochastische Optimierung	Robuste Optimierung
Darstellung der Unsicherheit	Parameter sind Zufallsvariablen mit bekannter Wahrscheinlichkeitsverteilung	Parameter gehören zu einer gegebenen Unsicherheitsmenge, eine Verteilung ist nicht erforderlich
Optimalitätskriterium	Optimierung des Erwartungswertes der Zielfunktion	Optimierung für das Worst-Case-Szenario (Minimax)
Art der Lösung	Eine im Durchschnitt optimale Strategie, die für seltene Szenarien unzulässig sein kann	Eine Lösung, die für alle Realisierungen garantiert zulässig ist; kann konservativ sein

Beispiele

• Zeitungsjungenproblem (englisch newsvendor problem): Ein klassisches Problem des Bestandsmanagements, bei dem ein Verkäufer entscheiden muss, wie viele Einheiten eines Produkts er einkaufen soll, ohne die genaue zukünftige Nachfrage zu kennen. Die Lösung balanciert zwischen dem Risiko von Verlusten durch Überbestände und dem Risiko entgangener Gewinne durch Fehlbestände.
• Problem des Landwirts: Ein Landwirt entscheidet, wie viele Acres Land er auf einer Gesamtfläche für verschiedene Kulturen zuteilen soll, ohne das zukünftige Wetter zu kennen, das den Ernteertrag beeinflusst. Nachdem das Wetter bekannt ist, kann der Landwirt korrigierende Maßnahmen ergreifen (z. B. Überschüsse verkaufen oder fehlende Ernte auf dem Markt zukaufen).

Siehe auch

• Mathematische Programmierung
• Operations research
• Robuste Optimierung
• Dynamische Programmierung
• Kontrolltheorie