Programowanie stochastyczne

Programowanie stochastyczne (ang. stochastic programming) — dział programowania matematycznego, rozwijający modele i metody rozwiązywania zadań optymalizacyjnych w warunkach niepewności, gdy niektóre parametry modelu nie są dokładnie znane, lecz reprezentowane jako zmienne losowe o znanych lub oszacowanych rozkładach prawdopodobieństwa.

W odróżnieniu od zadań deterministycznych, gdzie wszystkie dane uznawane są za zadane stałe, programowanie stochastyczne ma na celu znalezienie rozwiązania (lub polityki podejmowania decyzji), które jest optymalne w pewnym sensie statystycznym. Najczęściej oznacza to minimalizację lub maksymalizację wartości oczekiwanej funkcji celu. Kluczowa idea polega na znalezieniu takiej polityki podejmowania decyzji, która będzie najlepsza „średnio" po wszystkich możliwych realizacjach losowych parametrów, co jest szczególnie istotne dla zadań, w których decyzje podejmowane są wielokrotnie w podobnych warunkach (np. w zarządzaniu zapasami lub systemami energetycznymi).

Matematyczne sformułowanie zadania

W ogólnej postaci zadanie programowania stochastycznego można sformułować jako: $\underset{x\in X}{min}𝔼[f(x,\xi )]$ gdzie:

• $x$ — wektor zmiennych sterujących (decyzyjnych), które należy wyznaczyć.
• $X$ — zbiór dopuszczalnych rozwiązań dla $x$, określony przez ograniczenia deterministyczne.
• $\xi$ — losowy wektor reprezentujący niepewne parametry zadania (np. popyt, ceny, warunki pogodowe).
• $f(x,\xi )$ — funkcja celu, której wartość zależy zarówno od podjętej decyzji $x$, jak i od realizacji losowego wektora $\xi$.
• $𝔼[\cdot ]$ — operator wartości oczekiwanej, obliczany względem rozkładu prawdopodobieństwa wektora $\xi$.

Najważniejszą zasadą leżącą u podstaw wieloetapowych modeli stochastycznych jest zasada nieanticypacji (ang. non-anticipativity principle). Głosi ona, że decyzje podejmowane na dowolnym etapie mogą zależeć wyłącznie od informacji dostępnych w danym momencie i nie mogą „zaglądać w przyszłość".

Dwuetapowe zadanie z prawem rekursu

Najbardziej rozpowszechnionym modelem jest dwuetapowe zadanie z prawem rekursu (ang. two-stage stochastic program with recourse). Proces podejmowania decyzji podzielony jest na dwa etapy:

1. Etap pierwszy: Podejmowana jest decyzja „tu i teraz" (here-and-now) — wyznaczany jest wektor $x$. Decyzja ta musi zostać podjęta zanim znana będzie konkretna realizacja losowego wektora $\xi$.
2. Etap drugi: Po tym, jak zdarzenie losowe nastąpiło, podejmowana jest decyzja korygująca lub kompensacyjna (recourse decision) — wektor $y(\xi )$, ukierunkowany na minimalizację negatywnych skutków lub wykorzystanie korzystnych możliwości wynikłych z połączenia decyzji pierwszego etapu $x$ i wyniku $\xi$.

Matematycznie dwuetapowe zadanie stochastycznego programowania liniowego formułuje się następująco: $\underset{x\in {ℝ}^{n_1}}{min}\{c^{T}x+{𝔼}_{\xi }[Q(x,\xi )]\}$ przy ograniczeniach pierwszego etapu: $Ax=b,x\ge 0$. Tutaj $Q(x,\xi )$ — funkcja rekursu (recourse function), stanowiąca optymalną wartość zadania drugiego etapu: $Q(x,\xi )=\underset{y\in {ℝ}^{n_2}}{min}\{q(\xi {)}^{T}y\mid T(\xi )x+Wy=h(\xi ),y\ge 0\}$ gdzie $\xi$ — losowy wektor obejmujący parametry $q(\xi ),T(\xi )$ i $h(\xi )$; natomiast $c,A,b$ i $W$ — parametry deterministyczne.

Kluczowe właściwości i twierdzenia

• Wypukłość: Jednym z fundamentalnych wyników teorii jest fakt, że dla dwuetapowego zadania stochastycznego programowania liniowego oczekiwana funkcja rekursu $Q(x)={𝔼}_{\xi }[Q(x,\xi )]$ jest funkcją wypukłą. Właściwość ta ma ogromne znaczenie, gdyż gwarantuje, że ogólne zadanie pierwszego etapu jest zadaniem programowania wypukłego, dla którego istnieją efektywne metody rozwiązania, a optimum globalne pokrywa się z lokalnym.
• Deterministyczny ekwiwalent: Jeśli losowy wektor $\xi$ ma skończoną liczbę możliwych realizacji (scenariuszy) ${\xi }_1,\dots ,{\xi }_K$ z prawdopodobieństwami $p_1,\dots ,p_K$, to zadanie programowania stochastycznego można przeformułować jako jedno duże deterministyczne zadanie optymalizacji. W tym przypadku wartość oczekiwana zastępowana jest ważoną sumą po wszystkich scenariuszach. Jednak rozmiar tego zadania rośnie liniowo z liczbą scenariuszy, co prowadzi do „przekleństwa wymiarowości" i sprawia, że takie podejście jest obliczeniowo niewykonalne dla dużej liczby scenariuszy.

Porównanie z optymalizacją robustawą

Programowanie stochastyczne jest jednym z kilku podejść do optymalizacji w warunkach niepewności. Jego kluczowa różnica w stosunku do optymalizacji robustawej polega na sposobie modelowania niepewności i kryterium optymalności.

Porównanie podejść do optymalizacji w warunkach niepewności

Kryterium	Optymalizacja stochastyczna	Optymalizacja robustawa
Reprezentacja niepewności	Parametry są zmiennymi losowymi o znanym rozkładzie prawdopodobieństwa	Parametry należą do zadanego zbioru niepewności; rozkład nie jest wymagany
Kryterium optymalności	Optymalizacja wartości oczekiwanej funkcji celu	Optymalizacja w najgorszym scenariuszu (minimax)
Charakter rozwiązania	Polityka optymalna „średnio", może być niedopuszczalna dla rzadkich scenariuszy	Rozwiązanie gwarantowanie dopuszczalne dla wszystkich realizacji; może być konserwatywne

Przykłady

• Zadanie gazeciarza (ang. newsvendor problem): Klasyczne zadanie zarządzania zapasami, w którym sprzedawca musi zdecydować, jaką ilość towaru zakupić, nie znając dokładnego przyszłego popytu. Rozwiązanie równoważy ryzyko strat wynikających z nadwyżek z ryzykiem utraconego zysku spowodowanego niedoborem.
• Zadanie farmera: Farmer decyduje, ile akrów ziemi przeznaczyć pod różne uprawy na łącznej powierzchni, nie znając przyszłej pogody wpływającej na plony. Po tym, jak pogoda staje się znana, farmer może podjąć działania korygujące (np. sprzedać nadwyżki lub dokupić brakujące plony na rynku).

Zobacz też

• Programowanie matematyczne
• Badania operacyjne
• Optymalizacja robustawa
• Programowanie dynamiczne
• Teoria sterowania