En este tutorial se utilizará la librería lpSolve de R para resolver programas de optimización lineales, enteros y mixtos. Esta librería es especialmente útil para encontrar la política óptima en los Procesos de Decisión Markovianos, mediante programación lineal. En primer lugar, instalaremos el paquete lpSolve y lo llamaremos:
library(lpSolve)Realizaremos el Problema 1 del archivo Complementaria 14.pdf que se encuentra en Sicua Plus. Se modelará la situación como un proceso de decisión markoviano (MDP). Para esto, se deben definir los cinco componentes principales del problema: épocas de decisión, espacio de estados, espacio de decisiones, probabilidades de transición y recompensas.
Para esta situación se define la variable de estado como: \[X_t= \text{Lugar en donde atacaron los villanos en el } t-1 \text{ataque.}\]
Luego, el espacio de estados es: \(S= \{ac,as\}\), donde \(ac\) significa que los villanos atacan el centro y \(as\) que atacan los suburbios.
El espacio de decisiones es: \(A(s)=\{c,s\}\), en donde \(c\) indica que los súper héroes se queden en el centro y \(s\) que se queden en los suburbios. Además, se tiene una matriz de probabilidades de transición por cada una de estas decisiones:
Ya que se desea maximizar las batallas ganadas, se realizará un programa lineal de minimización.
\[{\text{min } V_{ac} +V_{as}}\\ s.a\] \[\begin{eqnarray*} &&V(ac)\geq 0.3 + 0.9*(0.3*V(ac)+0.7*V(as))\\ &&V(ac)\geq 0.5 + 0.9*(0.5*V(ac)+0.5*V(as))\\ &&V(as)\geq 0.4 + 0.9*(0.6*V(ac)+0.4*V(as))\\ &&V(as)\geq 0.8 + 0.9*(0.8*V(ac)+0.2*V(as))\\ \end{eqnarray*}\]Debemos, ahora, expresar el programa lineal de la forma:
\[\text{min} \ \ \textbf{C}^T \textbf{x}\\ s.a.\\ \textbf{A} \textbf{x} \geq \textbf{b} \\ \textbf{x} \geq 0\]
Entonces, tenemos:
\[{\text{min } V_{ac} +V_{as}}\\ s.a\] \[\begin{eqnarray*} &&V(ac)-0.9*(0.3*V(ac)+0.7*V(as)) \geq 0.3 \\ &&V(ac)- 0.9*(0.5*V(ac)+0.5*V(as))\geq 0.5\\ &&V(as)-0.9*(0.6*V(ac)+0.4*V(as)) \geq 0.4 \\ &&V(as)- 0.9*(0.8*V(ac)+0.2*V(as)) \geq 0.8 \\ \end{eqnarray*}\]Con esto, conocemos:
\[\textbf{b}= \begin{bmatrix} 0.3 \\ 0.5\\ 0.4\\ 0.8 \end{bmatrix} \ \ \textbf{C}^T= \begin{bmatrix} 1 & 1 \end{bmatrix} \ \ \textbf{A}= \begin{bmatrix} 0.73 & -0.63\\ 0.55 & -0.45\\ -0.54 & 0.64 \\ -0.72 & 0.82\\ \end{bmatrix} \] Creamos estos elementos en R:
CMDP=c(1,1)
bMDP=c(0.3,0.5,0.4,0.8)
AMDP=matrix(c(0.73,-0.63,0.55,-0.45,-0.54,0.64,-0.72,0.82),byrow=TRUE,ncol=2,nrow=4)Ahora, resolvemos el programa lineal:
MDP=lp(direction="min", objective.in=CMDP,const.mat=AMDP,const.dir=c(">="),const.rhs=bMDP, compute.sens = TRUE)MDP$solution## [1] 6.062992 6.299213MDP$objval## [1] 12.3622De este modo, el valor óptimo descontado en el largo plazo de batallas ganadas, dado el estado inicial (ac) es de 6.063. Por otro lado, el valor óptimo descontado en el largo plazo de batallas ganadas, dado el estado inicial (as) es de 6.299.
Para hallar la política óptima a implementar, debemos saber cuáles restricciones están activas (es decir, cuáles restricciones tienen una holgura de 0), pues éstas corresponderán a las decisiones a tomar. Para esto, podemos hallar el valor de las variables duales. Por las condiciones de optimalidad KKT conocemos que, si el valor de la variable dual de una restricción es diferente de 0, luego la holgura de dicha restricción será 0.
MDP$duals## [1] 0.000000 12.125984 0.000000 7.874016 0.000000 0.000000Los primeros cuatro valores corresponden a las variables duales de las cuatro restricciones. Las variables duales son diferentes de 0 para las restricciones 2 y 4. Por lo tanto, las restricciones 2 y 4 están activas y, así, la política óptima es quedarse en el centro cuando han atacado los suburbios anteriormente, y quedarse en los suburbios cuando han atacado el centro.