Programació estocàstica

En el camp de l'optimització matemàtica, la programació estocàstica és un marc per modelar problemes d'optimització que impliquen incertesa. Un programa estocàstic és un problema d'optimització en el qual alguns o tots els paràmetres del problema són incerts, però segueixen distribucions de probabilitat conegudes.^[1][2] Aquest marc contrasta amb l'optimització determinista, en la qual se suposa que tots els paràmetres del problema es coneixen exactament. L'objectiu de la programació estocàstica és trobar una decisió que optimitzi alguns criteris escollits per qui pren la decisió i tingui en compte adequadament la incertesa dels paràmetres del problema. Com que moltes decisions del món real impliquen incertesa, la programació estocàstica ha trobat aplicacions en una àmplia gamma d'àrees que van des de les finances fins al transport i l'optimització energètica.

• Mètodes basats en escenaris, inclosa l'aproximació mitjana de la mostra
• Programació estocàstica de nombres enters per a problemes en què algunes variables han de ser enters
• Programació restringida d'atzar per fer front a les restriccions que s'han de satisfer amb una probabilitat determinada
• Programació dinàmica estocàstica
• Procés de decisió de Markov
• Descomposició de dobladors

La idea bàsica de la programació estocàstica en dues etapes és que les decisions (òptimes) s'han de basar en les dades disponibles en el moment en què es prenen les decisions i no poden dependre d'observacions futures. La formulació en dues etapes s'utilitza àmpliament en la programació estocàstica. La formulació general d'un problema de programació estocàstica en dues etapes ve donada per: $${\displaystyle \min _{x\in X}\{g(x)=f(x)+E_{\xi }[Q(x,\xi )]\}}$$ on ${\displaystyle Q(x,\xi )}$ és el valor òptim del problema de la segona etapa

$${\displaystyle \min _{y}\{q(y,\xi )\,|\,T(\xi )x+W(\xi )y=h(\xi )\}.}$$Els problemes clàssics de programació estocàstica lineal de dues etapes es poden formular com

$${\displaystyle {\begin{array}{llr}\min \limits _{x\in \mathbb {R} ^{n}}&g(x)=c^{T}x+E_{\xi }[Q(x,\xi )]&\\{\text{subject to}}&Ax=b&\\&x\geq 0&\end{array}}}$$on ${\displaystyle Q(x,\xi )}$ és el valor òptim del problema de la segona etapa $${\displaystyle {\begin{array}{llr}\min \limits _{y\in \mathbb {R} ^{m}}&q(\xi )^{T}y&\\{\text{subject to}}&T(\xi )x+W(\xi )y=h(\xi )&\\&y\geq 0&\end{array}}}$$

En tal formulació ${\displaystyle x\in \mathbb {R} ^{n}}$ és el vector variable de decisió de la primera etapa, ${\displaystyle y\in \mathbb {R} ^{m}}$ és el vector variable de decisió de la segona etapa, i ${\displaystyle \xi (q,T,W,h)}$ conté les dades del problema de la segona etapa. En aquesta formulació, en la primera etapa hem de prendre una decisió "aquí i ara". ${\displaystyle x}$ abans de la constatació de les dades incertes ${\displaystyle \xi }$, vist com un vector aleatori, és conegut. En la segona etapa, després d'una realització de ${\displaystyle \xi }$ està disponible, optimitzem el nostre comportament resolent un problema d'optimització adequat.

En la primera etapa optimitzem (minimitzem en la formulació anterior) el cost ${\displaystyle c^{T}x}$ de la decisió de la primera etapa més el cost esperat de la decisió de la segona etapa (òptima). Podem veure el problema de la segona etapa simplement com un problema d'optimització que descriu el nostre comportament suposadament òptim quan es revelen les dades incertes, o podem considerar la seva solució com una acció de recurs on el terme ${\displaystyle Wy}$ compensa una possible incoherència del sistema ${\displaystyle Tx\leq h}$ i ${\displaystyle q^{T}y}$ és el cost d'aquesta acció de recurs.

El problema de dues etapes considerat és lineal perquè les funcions objectius i les restriccions són lineals. Conceptualment això no és essencial i es poden considerar programes estocàstics de dues etapes més generals. Per exemple, si el problema de la primera etapa és enter, es podrien afegir restriccions d'integralitat al problema de la primera etapa perquè el conjunt factible sigui discret. També es podrien incorporar objectius i limitacions no lineals si cal.^[3]

Per resoldre numèricament el problema estocàstic de dues etapes, sovint cal suposar que el vector aleatori ${\displaystyle \xi }$ té un nombre finit de possibles realitzacions, anomenats escenaris, per exemple ${\displaystyle \xi _{1},\dots ,\xi _{K}}$, amb masses de probabilitat respectives ${\displaystyle p_{1},\dots ,p_{K}}$. Aleshores, l'expectativa en la funció objectiu del problema de la primera etapa es pot escriure com la suma:

$${\displaystyle E[Q(x,\xi )]=\sum \limits _{k=1}^{K}p_{k}Q(x,\xi _{k})}$$i, a més, el problema de dues etapes es pot formular com un gran problema de programació lineal (això s'anomena l'equivalent determinista del problema original, vegeu la secció § Deterministic equivalent of a stochastic problem).

Quan ${\displaystyle \xi }$ té un nombre infinit (o molt gran) de possibles realitzacions, l'enfocament estàndard és llavors representar aquesta distribució per escenaris. Aquest plantejament planteja tres preguntes, a saber:

1. Com construir escenaris, vegeu § Scenario construction;
2. Com resoldre l'equivalent determinista. Els optimitzadors com CPLEX i GLPK poden resoldre grans problemes lineals/no lineals. El servidor NEOS,^[4] allotjat a la Universitat de Wisconsin, Madison, permet l'accés gratuït a molts solucionadors moderns. L'estructura d'un equivalent determinista és particularment susceptible d'aplicar mètodes de descomposició,^[5] com la descomposició de Benders o la descomposició d'escenaris;
3. Com mesurar la qualitat de la solució obtinguda respecte a l'òptim "vertader".

Aquestes preguntes no són independents. Per exemple, el nombre d'escenaris construïts afectarà tant la tractabilitat de l'equivalent determinista com la qualitat de les solucions obtingudes.

Un programa estocàstic lineal és una instància específica del programa estocàstic clàssic de dues etapes. Un LP estocàstic es construeix a partir d'una col·lecció de programes lineals (LP) de diversos períodes, cadascun amb la mateixa estructura però amb dades una mica diferents. El ${\displaystyle k^{n}}$ LP de dos períodes, que representa el ${\displaystyle k^{n}}$ escenari, es pot considerar que té la forma següent:

${\displaystyle {\begin{array}{lccccccc}{\text{Minimize}}&f^{T}x&+&g^{T}y&+&h_{k}^{T}z_{k}&&\\{\text{subject to}}&Tx&+&Uy&&&=&r\\&&&V_{k}y&+&W_{k}z_{k}&=&s_{k}\\&x&,&y&,&z_{k}&\geq &0\end{array}}}$

Els vectors ${\displaystyle x}$ i ${\displaystyle y}$ conté les variables del primer període, els valors de les quals s'han de triar immediatament. El vector ${\displaystyle z_{k}}$ conté totes les variables per als períodes posteriors. Les limitacions ${\displaystyle Tx+Uy=r}$ només inclouen variables del primer període i són iguals en tots els escenaris. Les altres limitacions impliquen variables de períodes posteriors i difereixen en alguns aspectes d'un escenari a un altre, reflectint la incertesa sobre el futur.

La programació dinàmica estocàstica s'utilitza amb freqüència per modelar el comportament dels animals en camps com l'ecologia del comportament. Les proves empíriques de models d'alimentació òptima, transicions de la història de la vida, com ara l'envol en aus i la posta d'ous en vespes parasitoides, han demostrat el valor d'aquesta tècnica de modelització per explicar l'evolució de la presa de decisions conductuals. Aquests models solen ser de moltes etapes, en lloc de dues etapes.

La programació dinàmica estocàstica és una eina útil per entendre la presa de decisions sota incertesa. L'acumulació de capital sota incertesa n'és un exemple; sovint és utilitzat pels economistes de recursos per analitzar problemes bioeconòmics on entra la incertesa com ara el temps, etc.