stochastische Programmierung, Theorie zur Lösung von Optimierungsproblemen, bei deren Formulierung gewisse Parameter eine Rolle spielen, die Zufallsgrößen sind.

Solche probabilistischen Situationen treten beispielsweise auf, wenn man Meßfehler begeht oder Aussagen über zukünftige Prozesse macht. Die zugehörigen beschreibenden Parameter sind dann nur in einem statistischen Sinne verfügbar.

Eine typische Modellierung derartiger Probleme sieht wie folgt aus. Basierend auf einer ersten Beobachtung \({w}_{1}\in {{\mathbb{R}}}^{{k}_{1}}\) einer Zufallsgröße wird eine Entscheidung \({x}_{1}\in {{\mathbb{R}}}^{{n}_{1}}\) getroffen. Dies bewirkt Kosten der Größe f₁ (x₁, w₁). Anschließend wird eine neue Beobachtung \({w}_{2}\in {{\mathbb{R}}}^{{k}_{2}}\) gemacht. Die neue Entscheidung \({x}_{2}\in {{\mathbb{R}}}^{{n}_{2}}\) kann jetzt von (w₁, w₂) abhängen und verursacht Kosten f₂ (x₁, x₂, w₁, w₂). Dieser Prozeß wird, unter Umständen unendlich oft, fortgesetzt. Von größtem Interesse sind allerdings Prozesse mit lediglich zwei oder drei Stufen.

Ziel ist nunmehr das Auffinden sogenannter Rekursfunktionen x₁ (w₁), x₂ (w₁, w₂), …, welche Entscheidungen liefern, die die erwarteten Kosten minimieren. Die x_i können dabei zusätzlich weiteren Nebenbedingungen unterliegen.

Als Beispiel folgt die Formulierung eines linearen stochastischen Programms in zwei Stufen. Üblicherweise nimmt man zusätzlich an, daß die erste Entscheidung x₁ nicht bereits durch Zufallsphänomene beeinflußt wird (d. h. w₁ oben entfällt in diesem Fall). Ein derartiges Problem lautet dann \begin{eqnarray}\min {c}^{T}\cdot {x}_{1}+E[Z({x}_{1},{w}_{2})]\end{eqnarray}

unter den Nebenbedingungen A · x₁ = b, x₁ ≥ 0. Hierbei bezeichnet c^T · x₁ die direkten Kosten der ersten Entscheidung und E[Z(x₁, w₂)] die erwarteten Kosten der zweiten Entscheidung unter Beachtung der Nebenbedingungen für x₁. Z selbst hat die Form Z(x₁, w₂) = min d(w₂)^T ·x₂ unter den Nebenbedingungen W · x₂ = p(w₂) − T(w₂) · x₁, x₂ ≥ 0. Dabei sind die Vektoren d und p sowie die Matrix T Zufallsgrößen. W ist i. allg. eine feste Matrix, kann aber ebenfalls von w₂ abhängig gemacht werden. Die Rekurskosten hängen von der anfänglichen Entscheidung x₁ und dem Zufallsergebnis w₂ ab. Das zweite obige lineare Programm beschreibt dann, wie man die zweite Entscheidung x₂ treffen muß. Die zugehörigen Nebenbedingungen können als Korrektur des Systems aufgefaßt werden, nachdem es durch ein Zufallsereignis verändert wurde.

[1] Birge, J.R.; Louveaux, F.: Introduction to Stochastic Programming. Springer Series in Operations Research, Springer, 1997.
[2] Dempster, M.: Stochastic Programming. Academic Press, London, 1980.