Programare stochastică

Programarea stochastică (engl. stochastic programming) — ramură a programării matematice care elaborează modele și metode de rezolvare a problemelor de optimizare în condiții de incertitudine, când anumiți parametri ai modelului nu sunt cunoscuți cu exactitate, ci sunt reprezentați ca variabile aleatoare cu distribuții de probabilitate cunoscute sau estimate.

Spre deosebire de problemele deterministe, unde toate datele sunt considerate constante date, programarea stochastică urmărește găsirea unei soluții (sau a unei politici de luare a deciziilor) care să fie optimă într-un anumit sens statistic. Cel mai frecvent, aceasta înseamnă minimizarea sau maximizarea valorii așteptate a funcției obiectiv. Ideea cheie constă în găsirea unei politici de luare a deciziilor care să fie cea mai bună „în medie" pentru toate realizările posibile ale parametrilor aleatori, ceea ce este deosebit de relevant pentru problemele în care deciziile se iau în mod repetat în condiții similare (de exemplu, în gestionarea stocurilor sau a sistemelor energetice).

Formularea matematică a problemei

În formă generală, problema programării stochastice poate fi formulată astfel: $\underset{x\in X}{\min }\mathbb{𝔼}[f(x,\xi )]$ unde:

• $x$ — vectorul variabilelor de decizie (soluțiilor) care trebuie determinate.
• $X$ — mulțimea soluțiilor admisibile pentru $x$, definită prin constrângeri deterministe.
• $\xi$ — vectorul aleator care reprezintă parametrii incerți ai problemei (de exemplu, cererea, prețurile, condițiile meteorologice).
• $f(x,\xi )$ — funcția obiectiv, a cărei valoare depinde atât de decizia luată $x$, cât și de realizarea vectorului aleator $\xi$.
• $\mathbb{𝔼}[\cdot ]$ — operatorul valorii așteptate, calculat după distribuția de probabilitate a vectorului $\xi$.

Principiul fundamental care stă la baza modelelor stochastice multi-etapă este principiul non-anticipativității (engl. non-anticipativity principle). Acesta stipulează că deciziile luate la orice etapă pot depinde doar de informațiile disponibile până în acel moment și nu pot „privi în viitor\".

Problema în două etape cu recurs

Cel mai răspândit model este problema în două etape cu recurs (engl. two-stage stochastic program with recourse). Procesul de luare a deciziilor este împărțit în două etape:

1. Prima etapă: Se ia o decizie „aici și acum\" (here-and-now) — se determină vectorul $x$. Această decizie trebuie luată înainte ca realizarea concretă a vectorului aleator $\xi$ să fie cunoscută.
2. A doua etapă: După ce evenimentul aleator s-a produs, se ia o decizie de corecție sau de recurs (recourse decision) — vectorul $y(\xi )$, orientat spre minimizarea consecințelor negative sau valorificarea oportunităților favorabile apărute ca urmare a combinației dintre decizia din prima etapă $x$ și rezultatul $\xi$.

Matematic, problema de programare liniară stochastică în două etape este formulată astfel: $\underset{x\in {\mathbb{ℝ}}^{n_1}}{\min }\{c^{T}x+{\mathbb{𝔼}}_{\xi }[Q(x,\xi )]\}$ cu constrângerile primei etape: $Ax=b,x\ge 0$. Aici $Q(x,\xi )$ — funcția de recurs (recourse function), reprezentând valoarea optimă a problemei din a doua etapă: $Q(x,\xi )=\underset{y\in {\mathbb{ℝ}}^{n_2}}{\min }\{q(\xi {)}^{T}y\mid T(\xi )x+Wy=h(\xi ),y\ge 0\}$ unde $\xi$ — vectorul aleator care include parametrii $q(\xi ),T(\xi )$ și $h(\xi )$; iar $c,A,b$ și $W$ — parametri deterministici.

Proprietăți cheie și teoreme

• Convexitate: Unul dintre rezultatele fundamentale ale teoriei este că, pentru problema de programare liniară stochastică în două etape, funcția de recurs așteptată $Q(x)={\mathbb{𝔼}}_{\xi }[Q(x,\xi )]$ este o funcție convexă. Această proprietate are o importanță deosebită, deoarece garantează că problema globală a primei etape este o problemă de programare convexă, pentru care există metode eficiente de rezolvare și optimul global coincide cu cel local.
• Echivalentul determinist: Dacă vectorul aleator $\xi$ are un număr finit de realizări posibile (scenarii) ${\xi }_1,\dots ,{\xi }_K$ cu probabilitățile $p_1,\dots ,p_K$, atunci problema programării stochastice poate fi reformulată ca o singură problemă de optimizare deterministă de dimensiuni mari. În acest caz, valoarea așteptată este înlocuită de o sumă ponderată pe toate scenariile. Cu toate acestea, dimensiunea acestei probleme crește liniar cu numărul de scenarii, ceea ce conduce la „blestemul dimensionalității\" și face această abordare imposibil de rezolvat computațional pentru un număr mare de scenarii.

Comparație cu optimizarea robustă

Programarea stochastică este una dintre mai multe abordări ale optimizării în condiții de incertitudine. Diferența sa esențială față de optimizarea robustă constă în modul de modelare a incertitudinii și în criteriul de optimalitate.

Compararea abordărilor de optimizare în condiții de incertitudine

Criteriu	Optimizare stochastică	Optimizare robustă
Reprezentarea incertitudinii	Parametrii sunt variabile aleatoare cu o distribuție de probabilitate cunoscută	Parametrii aparțin unei mulțimi de incertitudine date; distribuția nu este necesară
Criteriul de optimalitate	Optimizarea valorii așteptate a funcției obiectiv	Optimizarea în cel mai defavorabil scenariu (minimax)
Caracterul soluției	Politică optimă „în medie\", poate fi inadmisibilă pentru scenarii rare	Soluție garantat admisibilă pentru toate realizările; poate fi conservatoare

Exemple

• Problema vânzătorului de ziare (engl. newsvendor problem): Problemă clasică de gestionare a stocurilor, în care un vânzător trebuie să decidă ce cantitate de marfă să achiziționeze, fără a cunoaște cererea viitoare exactă. Soluția echilibrează riscul pierderilor din surplus cu riscul pierderii profitului din cauza deficitului.
• Problema fermierului: Un fermier decide câte hectare de teren să aloce diferitelor culturi pe o suprafață totală, fără a cunoaște condițiile meteorologice viitoare, care influențează productivitatea. După ce condițiile meteorologice devin cunoscute, fermierul poate lua măsuri de corecție (de exemplu, să vândă surplusul sau să cumpere recolta lipsă de pe piață).

Vezi și

• Programare matematică
• Cercetarea operațională
• Optimizare robustă
• Programare dinamică
• Teoria controlului