Die stochastische Optimierung (oder stochastische Programmierung) erweitert das Gebiet der mathematischen Programmierung um Modelle und Methoden zur optimalen Entscheidungsfindung bei unsicheren Eingangsdaten. Diese werden in den Modellen der stochastischen Programmierung durch Zufallsvariablen mit bekannten Zufallsverteilungen abgebildet.
Dadurch wird eine realitätsnähere Modellierung vieler wirtschaftlichen Fragestellungen ermöglicht, in denen die Eingangsdaten wie beispielsweise Preise, Produktnachfrage, Ressourcen oder Kapazitäten oft zum Zeitpunkt der Entscheidungsfindung nicht genau bekannt sind. Einführende Standardwerke sind die Bücher von Kall und Wallace [Kall, Wallace 1994], sowie von Birge und Louveaux [Birge, Louveaux 1997].
Optimale Entscheidungsfindung unter Unsicherheit
Es haben sich drei Ansätze zum Umgang mit Unsicherheit in Entscheidungsproblemen etabliert [Madanski 1960]:
-
„expected-value“ – In diesem Ansatz wird für jedes unsichere Datum der Erwartungswert der zugrundeliegenden Zufallsverteilung bestimmt. Für diese „gemittelten“ Daten wird das deterministische Optimierungsmodell gelöst (das sog. expected-value problem (EV)). Die optimale Lösung dieses Problems kann dann wiederum für alle möglichen Ausprägungen der unsicheren Parameter (Szenarien) evaluiert werden, was zum sog. Erwartungswert der Lösung des EV Problems (EEV) führt.
-
„wait-and-see“ – Die Grundannahme dieses Ansatzes ist es, dass der Entscheidungsträger die Möglichkeit hat, solange abzuwarten, bis sich die Unsicherheit aufgelöst hat, und dann die optimale Entscheidung zu treffen. Das „wait-and-see“-Problem besteht also darin, die Verteilung der optimalen Zielfunktionswerte des deterministischen Modells für jedes mögliche Szenario zu berechnet. Der Erwartungswert dieser Verteilung heißt „wait-and-see“-Wert (WS). Der Nachteil des WS-Problems besteht darin, dass es keine Planungslösung liefert, die zum eigentlichen Zeitpunkt der Entscheidungsfindung umsetzbar ist.
-
„here-and-now“ – Die Lösung des „here-and-now“-Problems (HN) liefert die zum Zeitpunkt der Entscheidungsfindung optimale Entscheidung, die für jedes mögliche Szenario zulässig ist. Optimalität wird meist über den Erwartungswert der Zielfunktion über alle Szenarien definiert. Es sind aber auch andere Optimalitätsbegriffe denkbar, beispielsweise, wenn Risikomaße mitberücksichtigt werden sollen. Dann entsteht ein multikriterielles Optimierungsproblem.
Durch den Vergleich von EEV-, WS-, und HN-Wert kann der sog. Wert der vollständigen Information (EVPI) und der Wert der stochastischen Lösung (VSS) berechnet werden. Diese Werte geben Aufschluss über den Mehrwert, der durch eine explizite Berücksichtigung der Unsicherheit bei der Entscheidungsfindung erzielt wird.
Modelle und Lösungsverfahren der stochastischen Programmierung
Die Modelle und Lösungsverfahren der stochastischen Optimierung beschäftigen sich vorwiegend mit dem HN-Problem. Die verschiedenen Modellklassen ergeben sich aus der Typologie der mathematischen Programmierung (linear, nicht-linear, ganzzahlig etc.), aus der zeitlichen Struktur der Entscheidungsfindung und der Zulässigkeitsdefinition der Lösung. Die wichtigsten Modellklassen sind:
-
Zwei- und mehrstufige stochastische Programme mit Kompensation – Bei diesem Modelltyp, der auf Dantzig [Dantzig 1955] zurückgeht, werden die Entscheidungsvariablen denjenigen diskreten Zeitpunkten innerhalb des Planungszeitraumes zugeordnet, an denen die Entscheidungsfindung stattfindet. Stufe-1 Entscheidungen müssen immer zu Beginn des Planungszeitraumes getroffen werden und sind dann für alle weiteren Stufen fixiert. Zweistufige lineare stochastische Programme können für eine diskrete Menge von Szenarien in vielen Fällen effizient gelöst werden. Die verwendeten Lösungsverfahren bauen dabei auf Dekompositionsverfahren der linearen Programmierung auf (Benders-Dekomposition). Mehrstufige-, ganzzahlige und nicht-lineare stochastische Programme sind oft nicht oder nur unter hohem Aufwand (spezialisierte Lösungsverfahren) für praktisch relevante Problemgrößen lösbar.
-
Stochastische Programme mit probabilistischen Nebenbedingungen – Bei diesem von Charnes und Cooper [Charnes, Cooper 1959] entwickelten Modelltyp wird die Forderung fallengelassen, dass die Lösung für alle Nebenbedingungen und möglichen Szenarien zulässig sein muss. Stattdessen können sog. probabilistische Nebenbedingungen definiert werden, die in einem Teil der Szenarien verletzt sein dürfen. Die effiziente Lösbarkeit dieses Modelltyps hängt davon ab, ob ein effizient lösbares äquivalentes deterministisches Modell abgeleitet werden kann. Ist dies nicht der Fall, dann sind diese Modelle sehr schwer lösbar.
Literatur
Birge, J. R.; Louveaux, F.: Introduction to stochastic programming : Springer, 1997.
Charnes, A.; Cooper, W.W.: Chance-constrained programming: Management Science 5:73-79, 1959.
Dantzig, G.B.: Linear Programming under uncertainty: Management Science 1:197-206, 1955.
Kall, P; Wallace, S.W.: Stochastic Programming : John Wiley and Sons, 1994.
Madanski, M.: Inequalities for stochastic linear programming problems: Management Science 6:197-204, 1960
