Stokastikong programming

Stokastikong programming (Ingles: stochastic programming) — isang sangay ng matematikong programming na nagbubuo ng mga modelo at pamamaraan para sa paglutas ng mga optimizasyon na gawain sa ilalim ng kawalan ng katiyakan, kung saan ang ilang mga parameter ng modelo ay hindi eksaktong kilala, kundi kinakatawan bilang mga random na dami na may kilala o tinatantiyang mga probabilistikong distribusyon.

Kaiba sa mga deterministikong gawain, kung saan ang lahat ng datos ay itinuturing na mga ibinigay na konstante, ang stokastikong programming ay naglalayong mahanap ang isang solusyon (o patakaran sa paggawa ng desisyon) na optimal sa ilang estadistikong kahulugan. Kadalasan, nangangahulugan ito ng pagliit o pagpapalaki ng mathematical expectation ng objective function. Ang pangunahing ideya ay mahanap ang naturang patakaran sa paggawa ng desisyon na magiging pinakamabuti "sa karaniwan" sa lahat ng posibleng pagpapatupad ng mga random na parameter, na partikular na may kaugnayan sa mga gawaing kung saan ang mga desisyon ay paulit-ulit na ginagawa sa magkakatulad na kondisyon (halimbawa, sa pamamahala ng imbentaryo o mga sistema ng enerhiya).

Matematikong Pagbabalangkas ng Gawain

Sa pangkalahatang anyo, ang gawain ng stokastikong programming ay maaaring ibalangkas bilang: $\underset{x\in X}{min}𝔼[f(x,\xi )]$ kung saan:

• $x$ — vector ng mga kontroling variable (desisyon) na kailangang tukuyin.
• $X$ — ang hanay ng mga katanggap-tanggap na solusyon para sa $x$, na tinutukoy ng mga deterministikong limitasyon.
• $\xi$ — random na vector na kumakatawan sa mga hindi tiyak na parameter ng gawain (halimbawa, demand, presyo, kondisyon ng panahon).
• $f(x,\xi )$ — objective function, na ang halaga ay nakasalalay kapwa sa tinanggap na desisyon $x$ at sa pagpapatupad ng random na vector $\xi$.
• $𝔼[\cdot ]$ — operator ng mathematical expectation, na kinakalkula ayon sa distribusyon ng probabilidad ng vector $\xi$.

Ang pinakamahalagang prinsipyo na nagsisilang pundasyon ng multi-stage na mga stokastikong modelo ay ang prinsipyo ng non-anticipativity (Ingles: non-anticipativity principle). Sinasabi nito na ang mga desisyong ginagawa sa anumang yugto ay maaari lamang umasa sa impormasyon na magagamit sa sandaling iyon, at hindi maaaring "sulyapan ang hinaharap".

Dalawang-Yugtong Gawain na may Karapatang Kompensasyon

Ang pinakakaraniwang modelo ay ang dalawang-yugtong gawain na may karapatang kompensasyon (Ingles: two-stage stochastic program with recourse). Ang proseso ng paggawa ng desisyon ay nahahati sa dalawang yugto:

1. Unang yugto: Ang desisyon ay ginagawa "dito at ngayon" (here-and-now) — tinutukoy ang vector $x$. Ang desisyong ito ay dapat gawin bago maging kilala ang tiyak na pagpapatupad ng random na vector $\xi$.
2. Ikalawang yugto: Pagkatapos mangyari ang random na kaganapan, isang corrective o compensatory na desisyon (recourse decision) ay ginagawa — vector $y(\xi )$, na naglalayong mabawasan ang mga negatibong kahihinatnan o samantalahin ang mga kanais-nais na pagkakataon na lumabas bilang resulta ng kumbinasyon ng desisyon sa unang yugto $x$ at ng kinalabasan $\xi$.

Matematikal na ang dalawang-yugtong gawain ng stokastikong linear programming ay binubalangkas tulad ng sumusunod: $\underset{x\in {ℝ}^{n_1}}{min}\{c^{T}x+{𝔼}_{\xi }[Q(x,\xi )]\}$ sa mga limitasyon ng unang yugto: $Ax=b,x\ge 0$. Dito ang $Q(x,\xi )$ — recourse function (recourse function), na kumakatawan sa pinakamainam na halaga ng gawain sa ikalawang yugto: $Q(x,\xi )=\underset{y\in {ℝ}^{n_2}}{min}\{q(\xi {)}^{T}y\mid T(\xi )x+Wy=h(\xi ),y\ge 0\}$ kung saan ang $\xi$ — random na vector na kinabibilangan ng mga parameter $q(\xi ),T(\xi )$ at $h(\xi )$; at ang $c,A,b$ at $W$ — mga deterministikong parameter.

Mga Pangunahing Katangian at Teorema

• Convexity: Isa sa mga pundamental na resulta ng teorya ay ang para sa dalawang-yugtong gawain ng stokastikong linear programming, ang inaasahang recourse function $Q(x)={𝔼}_{\xi }[Q(x,\xi )]$ ay isang convex na function. Ang katangiang ito ay may malaking kahalagahan, dahil ginagarantiyahan nito na ang kabuuang gawain sa unang yugto ay isang gawain ng convex programming, kung saan may mga epektibong pamamaraan ng solusyon at ang global na optimum ay naaayon sa lokal.
• Deterministikong katumbas: Kung ang random na vector $\xi$ ay may limitadong bilang ng posibleng pagpapatupad (senaryo) ${\xi }_1,\dots ,{\xi }_K$ na may mga probabilidad $p_1,\dots ,p_K$, ang gawain ng stokastikong programming ay maaaring muling ibalangkas bilang isang malaking deterministikong gawain ng optimizasyon. Sa kasong ito, ang mathematical expectation ay pinapalitan ng may timbangang kabuuan sa lahat ng senaryo. Gayunpaman, ang laki ng gawaing ito ay lumalaki nang linear sa bilang ng mga senaryo, na humahantong sa "sumpa ng dimensyon" at ginagawang hindi mapaglutas sa pagkalkula ang naturang diskarte para sa malaking bilang ng mga senaryo.

Paghahambing sa Robust Optimization

Ang stokastikong programming ay isa sa ilang mga diskarte sa optimizasyon sa ilalim ng kawalan ng katiyakan. Ang pangunahing pagkakaiba nito mula sa robust optimization ay nasa paraan ng pagmomolde ng kawalan ng katiyakan at sa pamantayan ng optimalidad.

Paghahambing ng mga diskarte sa optimizasyon sa ilalim ng kawalan ng katiyakan

Pamantayan	Stokastikong optimizasyon	Robust optimization
Representasyon ng kawalan ng katiyakan	Ang mga parameter ay mga random na dami na may kilalang probabilistikong distribusyon	Ang mga parameter ay kabilang sa isang ibinigay na hanay ng kawalan ng katiyakan; hindi kailangan ang distribusyon
Pamantayan ng optimalidad	Optimizasyon ng mathematical expectation ng objective function	Optimizasyon sa pinakamasamang senaryo (minimax)
Katangian ng solusyon	Patakaran na optimal "sa karaniwan", maaaring hindi katanggap-tanggap para sa mga bihirang senaryo	Solusyong garantisadong katanggap-tanggap para sa lahat ng pagpapatupad; maaaring konserbatibo

Mga Halimbawa

• Gawain ng nagbebenta ng pahayagan (Ingles: newsvendor problem): Isang klasikong gawain sa pamamahala ng imbentaryo, kung saan ang isang nagbebenta ay dapat magdesisyon kung gaano karaming produkto ang bibilhin nang hindi alam ang eksaktong hinaharap na demand. Ang solusyon ay nagbabalanse sa pagitan ng panganib ng pagkalugi mula sa labis na imbentaryo at ng panganib ng pagkawala ng kita mula sa kakulangan ng produkto.
• Gawain ng magsasaka: Ang isang magsasaka ay nagdedesisyon kung gaano karaming ektarya ng lupa ang ilalaan sa iba't ibang pananim sa kabuuang lugar, nang hindi alam ang hinaharap na panahon na nakakaimpluwensya sa ani. Pagkatapos maging kilala ang panahon, ang magsasaka ay maaaring gumawa ng mga corrective na aksyon (halimbawa, ibenta ang labis o bilhin ang nawawalang pananim sa merkado).

Tingnan Din

• Matematikong programming
• Pananaliksik ng operasyon
• Robust optimization
• Dynamic programming
• Teorya ng kontrol

Mga Tala

</references>