Sztochasztikus programozás

Sztochasztikus programozás (angol: stochastic programming) — a matematikai programozás azon ága, amely optimalizálási feladatok megoldásához dolgoz ki modelleket és módszereket bizonytalansági körülmények között, amikor a modell egyes paraméterei nem ismertek pontosan, hanem ismert vagy becsült valószínűségi eloszlású véletlen változókként vannak megadva.

Az determinisztikus feladatokkal ellentétben, ahol minden adat adott konstansnak tekintendő, a sztochasztikus programozás célja olyan megoldás (vagy döntési politika) megtalálása, amely valamely statisztikai értelemben optimális. Ez leggyakrabban a célfüggvény várható értékének minimalizálását vagy maximalizálását jelenti. A kulcsötlet az, hogy olyan döntési politikát keressünk, amely a véletlen paraméterek összes lehetséges realizációján átlagolva a legjobb eredményt adja; ez különösen fontos olyan feladatoknál, ahol a döntéseket ismételten, hasonló körülmények között hozzák (például készletgazdálkodásban vagy energiarendszerek irányításában).

A feladat matematikai megfogalmazása

Általános alakban a sztochasztikus programozási feladat a következőképpen fogalmazható meg: $\underset{x\in X}{min}𝔼[f(x,\xi )]$ ahol:

• $x$ — a meghatározandó irányítási változók (döntések) vektora.
• $X$ — a $x$ megengedett megoldásainak halmaza, amelyet determinisztikus korlátok határoznak meg.
• $\xi$ — a feladat bizonytalan paramétereit (például keresletet, árakat, időjárási feltételeket) képviselő véletlen vektor.
• $f(x,\xi )$ — a célfüggvény, amelynek értéke mind a $x$ döntéstől, mind a $\xi$ véletlen vektor realizációjától függ.
• $𝔼[\cdot ]$ — a várható érték operátora, amelyet a $\xi$ vektor valószínűségi eloszlása szerint számítunk.

A többlépéses sztochasztikus modellek alapját képező legfontosabb elv a nem-anticipativitás elve (angol: non-anticipativity principle). Ez kimondja, hogy bármely szakaszban hozott döntések csak az addig rendelkezésre álló információtól függhetnek, és nem „tekinthetnek a jövőbe".

Kétlépéses feladat kompenzálási joggal

A legelterjedtebb modell a kétlépéses sztochasztikus feladat kompenzálási joggal (angol: two-stage stochastic program with recourse). A döntéshozatali folyamat két szakaszra tagolódik:

1. Első szakasz: „Itt és most" (here-and-now) döntés születik — meghatározzák a $x$ vektort. Ezt a döntést még azelőtt kell meghozni, mielőtt a $\xi$ véletlen vektor konkrét realizációja ismertté válna.
2. Második szakasz: Miután a véletlen esemény bekövetkezett, kiigazító vagy kompenzáló döntést (recourse decision) hoznak — a $y(\xi )$ vektort —, amelynek célja az első szakasz $x$ döntése és a $\xi$ kimenetel együttes hatásából adódó negatív következmények minimalizálása vagy a kedvező lehetőségek kihasználása.

Matematikailag a kétlépéses sztochasztikus lineáris programozási feladat a következőképpen fogalmazható meg: $\underset{x\in {ℝ}^{n_1}}{min}\{c^{T}x+{𝔼}_{\xi }[Q(x,\xi )]\}$ az első szakasz korlátaival: $Ax=b,x\ge 0$. Itt $Q(x,\xi )$ a kompenzációs függvény (recourse function), amely a második szakasz feladatának optimális értékét jelenti: $Q(x,\xi )=\underset{y\in {ℝ}^{n_2}}{min}\{q(\xi {)}^{T}y\mid T(\xi )x+Wy=h(\xi ),y\ge 0\}$ ahol $\xi$ a $q(\xi ),T(\xi )$ és $h(\xi )$ paramétereket tartalmazó véletlen vektor; $c,A,b$ és $W$ pedig determinisztikus paraméterek.

Kulcstulajdonságok és tételek

• Konvexitás: Az elmélet egyik alapvető eredménye, hogy kétlépéses sztochasztikus lineáris programozási feladat esetén a várható kompenzációs függvény $Q(x)={𝔼}_{\xi }[Q(x,\xi )]$ konvex függvény. Ez a tulajdonság rendkívül jelentős, mivel garantálja, hogy az első szakasz összesített feladata konvex programozási feladat, amelyre hatékony megoldási módszerek léteznek, és a globális optimum egybeesik a lokális optimummal.
• Determinisztikus ekvivalens: Ha a $\xi$ véletlen vektornak véges számú lehetséges realizációja (forgatókönyve) ${\xi }_1,\dots ,{\xi }_K$ van $p_1,\dots ,p_K$ valószínűségekkel, akkor a sztochasztikus programozási feladat átfogalmazható egyetlen nagy determinisztikus optimalizálási feladatként. Ebben az esetben a várható értéket az összes forgatókönyv szerinti súlyozott összeg helyettesíti. Ez a feladat mérete azonban lineárisan nő a forgatókönyvek számával, ami „átokszerű dimenzionális robbantáshoz" vezet, és nagy számú forgatókönyv esetén számítási szempontból megoldhatatlanná teszi ezt a megközelítést.

Összehasonlítás a robusztus optimalizálással

A sztochasztikus programozás egyike a bizonytalansági körülmények közötti optimalizálás több megközelítésének. A robusztus optimalizálástól való legfontosabb különbsége a bizonytalanság modellezési módjában és az optimalitási kritériumban rejlik.

Bizonytalansági körülmények közötti optimalizálási megközelítések összehasonlítása

Kritérium	Sztochasztikus optimalizálás	Robusztus optimalizálás
A bizonytalanság megjelenítése	A paraméterek ismert valószínűségi eloszlású véletlen változók	A paraméterek egy adott bizonytalansági halmazba tartoznak, eloszlás nem szükséges
Optimalitási kritérium	A célfüggvény várható értékének optimalizálása	Optimalizálás a legrosszabb forgatókönyv szerint (minimax)
A megoldás jellege	Átlagosan optimális politika, amely ritka forgatókönyvek esetén nem feltétlenül megengedett	Minden realizációra garantáltan megengedett megoldás; konzervatív lehet

Példák

• Az újságárus feladata (angol: newsvendor problem): Klasszikus készletgazdálkodási feladat, ahol az eladónak el kell döntenie, mekkora mennyiségű árut szerezzen be anélkül, hogy a pontos jövőbeli keresletet ismerné. A megoldás egyensúlyt teremt a feleslegből eredő veszteség kockázata és a hiányból fakadó elmaradt haszon kockázata között.
• A gazda feladata: Egy gazda eldönti, hogy összterületén hány holdat osszon ki különböző növényekre anélkül, hogy ismerné a terméseredményt befolyásoló jövőbeli időjárást. Miután az időjárás ismertté válik, a gazda kiigazító intézkedéseket tehet (például feleslegét eladhatja, vagy a hiányzó termést piacon vásárolhatja meg).

Lásd még

• Matematikai programozás
• Operációkutatás
• Robusztus optimalizálás
• Dinamikus programozás
• Irányításelmélet