Stochastické programování

Stochastické programování (angl. stochastic programming) — odvětví matematického programování, které vyvíjí modely a metody řešení optimalizačních úloh v podmínkách neurčitosti, kdy některé parametry modelu nejsou přesně známy, ale jsou představeny jako náhodné veličiny se známými nebo odhadnutými pravděpodobnostními rozděleními.

Na rozdíl od deterministických úloh, kde jsou všechna data považována za zadané konstanty, stochastické programování si klade za cíl nalézt řešení (nebo politiku rozhodování), které je optimální v určitém statistickém smyslu. Nejčastěji to znamená minimalizaci nebo maximalizaci střední hodnoty účelové funkce. Klíčová myšlenka spočívá v nalezení takové politiky rozhodování, která bude nejlepší „v průměru" přes všechny možné realizace náhodných parametrů, což je zvláště důležité pro úlohy, kde se rozhodnutí přijímají opakovaně za podobných podmínek (například v řízení zásob nebo energetických systémů).

Matematická formulace úlohy

V obecném tvaru lze úlohu stochastického programování formulovat jako: $\underset{x\in X}{min}𝔼[f(x,\xi )]$ kde:

• $x$ — vektor řídících proměnných (rozhodnutí), které je třeba stanovit.
• $X$ — množina přípustných řešení pro $x$, definovaná deterministickými omezeními.
• $\xi$ — náhodný vektor představující nejisté parametry úlohy (například poptávka, ceny, počasí).
• $f(x,\xi )$ — účelová funkce, jejíž hodnota závisí jak na přijatém rozhodnutí $x$, tak na realizaci náhodného vektoru $\xi$.
• $𝔼[\cdot ]$ — operátor střední hodnoty, vypočítávaný podle pravděpodobnostního rozdělení vektoru $\xi$.

Nejdůležitějším principem, který leží v základu vícestupňových stochastických modelů, je princip nepředjímání (angl. non-anticipativity principle). Říká, že rozhodnutí přijímaná v jakékoli fázi mohou záviset pouze na informacích dostupných do daného okamžiku a nemohou „nahlížet do budoucnosti\".

Dvoustupňová úloha s právem kompenzace

Nejrozšířenějším modelem je dvoustupňová úloha s právem kompenzace (angl. two-stage stochastic program with recourse). Proces rozhodování je rozdělen do dvou fází:

1. První fáze: Je přijato rozhodnutí „tady a teď\" (here-and-now) — je stanoven vektor $x$. Toto rozhodnutí musí být přijato před tím, než je známa konkrétní realizace náhodného vektoru $\xi$.
2. Druhá fáze: Poté, co nastala náhodná událost, je přijato opravné nebo kompenzační rozhodnutí (recourse decision) — vektor $y(\xi )$, zaměřené na minimalizaci negativních důsledků nebo využití příznivých příležitostí vzniklých kombinací rozhodnutí první fáze $x$ a výsledku $\xi$.

Matematicky je dvoustupňová úloha stochastického lineárního programování formulována následovně: $\underset{x\in {ℝ}^{n_1}}{min}\{c^{T}x+{𝔼}_{\xi }[Q(x,\xi )]\}$ při omezeních první fáze: $Ax=b,x\ge 0$. Zde $Q(x,\xi )$ — funkce kompenzace (recourse function), představující optimální hodnotu úlohy druhé fáze: $Q(x,\xi )=\underset{y\in {ℝ}^{n_2}}{min}\{q(\xi {)}^{T}y\mid T(\xi )x+Wy=h(\xi ),y\ge 0\}$ kde $\xi$ — náhodný vektor zahrnující parametry $q(\xi ),T(\xi )$ a $h(\xi )$; a $c,A,b$ a $W$ — deterministické parametry.

Klíčové vlastnosti a věty

• Konvexnost: Jedním ze základních výsledků teorie je, že pro dvoustupňovou úlohu stochastického lineárního programování je očekávaná funkce kompenzace $Q(x)={𝔼}_{\xi }[Q(x,\xi )]$ konvexní funkcí. Tato vlastnost má zásadní význam, neboť zaručuje, že celková úloha první fáze je úlohou konvexního programování, pro niž existují efektivní metody řešení a globální optimum splývá s lokálním.
• Deterministický ekvivalent: Má-li náhodný vektor $\xi$ konečný počet možných realizací (scénářů) ${\xi }_1,\dots ,{\xi }_K$ s pravděpodobnostmi $p_1,\dots ,p_K$, lze úlohu stochastického programování přeformulovat jako jednu velkou deterministickou optimalizační úlohu. V tomto případě je střední hodnota nahrazena váženým součtem přes všechny scénáře. Velikost této úlohy však roste lineárně s počtem scénářů, což vede k „prokletí dimenzionality\" a činí tento přístup výpočetně nezvládnutelným pro velký počet scénářů.

Srovnání s robustní optimalizací

Stochastické programování je jedním z několika přístupů k optimalizaci v podmínkách neurčitosti. Jeho klíčový rozdíl od robustní optimalizace spočívá ve způsobu modelování neurčitosti a v kritériu optimality.

Srovnání přístupů k optimalizaci v podmínkách neurčitosti

Kritérium	Stochastická optimalizace	Robustní optimalizace
Reprezentace neurčitosti	Parametry jsou náhodné veličiny se známým pravděpodobnostním rozdělením	Parametry náleží danému množině neurčitosti, rozdělení není vyžadováno
Kritérium optimality	Optimalizace střední hodnoty účelové funkce	Optimalizace v nejhorším scénáři (minimax)
Charakter řešení	Politika optimální „v průměru\", může být nepřípustná pro vzácné scénáře	Řešení zaručeně přípustné pro všechny realizace; může být konzervativní

Příklady

• Úloha novinářova (angl. newsvendor problem): Klasická úloha řízení zásob, kde prodejce musí rozhodnout, jaké množství zboží nakoupit, aniž zná přesnou budoucí poptávku. Řešení vyvažuje riziko ztrát z přebytků a riziko ušlého zisku z nedostatku.
• Úloha farmáře: Farmář rozhoduje, kolik akrů půdy věnovat různým plodinám na celkové ploše, aniž zná budoucí počasí, které ovlivňuje výnosy. Poté, co je počasí známo, může farmář přijmout opravná opatření (například prodat přebytky nebo dokoupit chybějící úrodu na trhu).

Viz také

• Matematické programování
• Operační výzkum
• Robustní optimalizace
• Dynamické programování
• Teorie řízení