Glossar · approach
Stochastische Programmierung
Mathematischer Programmieransatz, der bei bekannter Wahrscheinlichkeitsverteilung unsicherer Parameter (Nachfrage, Preis, Ertrag) die erwarteten Kosten oder den erwarteten Nutzen minimiert, typischerweise als zweistufiges Recourse- oder mehrstufiges Szenariobaum-Modell.
Stochastic ProgrammingSPZweistufige Recourse-ProgrammierungMehrstufige stochastische OptimierungSzenariobasierte Optimierung
Die stochastische Programmierung wurde unabhängig von Dantzig (1955) und Beale (1955) eingeführt und beschreibt den Zweig der mathematischen Optimierung, in dem Unsicherheit durch eine bekannte Wahrscheinlichkeitsverteilung modelliert wird. Die kanonische Form ist zweistufig: In der ersten Stufe werden Here-and-now-Entscheidungen (Kapazität, Standort, Bestellung) getroffen, bevor die Unsicherheit aufgelöst wird; in der zweiten Stufe folgen Recourse-Entscheidungen (Korrekturmassnahmen — Überstunden, Notbeschaffung, Pönalenakzeptanz). Die Zielfunktion summiert Erststufenkosten und erwartete Recoursekosten. Die mehrstufige Erweiterung ist auf einem Szenariobaum definiert, wobei Non-Anticipativity-Restriktionen die Knoten verbinden. Risikoaverse Varianten ersetzen den Erwartungswert durch CVaR oder Nutzenfunktionen. Lösungsverfahren umfassen das deterministische Äquivalent, Benders-Dekomposition (L-shaped, Van Slyke und Wets 1969), stufenweise Lagrange-Relaxation, Progressive Hedging (Rockafellar und Wets 1991) und Sample Average Approximation (SAA, Shapiro und Homem-de-Mello 1998). Szenarioreduktion ist in der Praxis unverzichtbar. Stochastische Programmierung ist robuster Optimierung vorzuziehen, wenn Verteilungen verlässlich vorliegen. Literatur: Birge und Louveaux (2011), Shapiro Dentcheva Ruszczynski (2009).
Örnek
Eine Mühle muss den Weizeneinkauf für den kommenden Monat unter Nachfrageunsicherheit festlegen, modelliert mit drei Szenarien — niedrig (200 t, 30 %), mittel (320 t, 50 %), hoch (420 t, 20 %). Das zweistufige Modell empfiehlt 310 t Einkauf; im niedrigen Szenario fallen 90 t Lagerkosten an, im hohen 110 t Spot-Nachkauf mit Strafkosten. Die erwarteten Gesamtkosten betragen 1.420.000 TRY, rund 8 Prozent unter der deterministischen Lösung (Nachfrage = 320 t).