El objetivo de este tutorial es que aprendan a definir y solucionar problemas de programación dinámica en R.
A continuación resolveremos un problema tipo knapsack de programación dinámica determinística. El problema está descrito en el archivo Complementaria 12 (Q).pdf en SICUA+. Para implementar la solución de este problema haremos uso de matrices en R.
Definimos entonces las épocas de decisión, la variable de estado y el espacio de estados:
\[E = \{ \text{Bloqueador, Agua, Enlatados} \}\]
\[X_n: \text{Espacio disponible en la maleta al inicio de la época de decisión }n\] \[S_x = \{ 3000,2500,2000,1500,1000,500,0\}\]
Vemos que el espacio de estados está definido por múltiplos de 500, pues nunca tomará un valor diferente de acuerdo a los pesos de los diferentes objetos (todos son múltiplos de 500).
El valor de las ganancias inmediatas está dado por los beneficios obtenidos al incluir cada objeto en la mochila.
Ahora bien, definimos todos los elementos del problema en R
e = c(1,2,3) #Épocas (1: Bloqueador, 2: Agua, 3: Enlatados)
s = c(3000,2500,2000,1500,1000,500,0) #Espacio de estados
w = c(500,1000,1500) #Pesos
b = c(8,15,20) #Beneficios
x = 3000 #Espacio disponible en la mochilaComenzamos a hacer la recursión por la última etapa de decisión Enlatados. Sabemos para esta etapa que el número máximo de enlatados que podríamos ingresar a la mochila es 2 \(\left(\frac{3000}{1500} = 2\right)\), y, de tener espacio, el mínimo es 1, pues al ser la última etapa intentamos llenar la mochila para obtener el máximo beneficio.
fenl = cbind(s, rep(0,length(s)),rep(0,length(s)),rep(0,length(s)), rep(0,length(s)))
colnames(fenl) = c("Estados", "A:1", "A:2", "ValueMax", "Decisión a tomar")
fenl[,2] = ifelse(w[3]*1>fenl[,1],0,1*b[3])
fenl[,3] = ifelse(w[3]*2>fenl[,1],0,2*b[3])
fenl[,4] = apply(fenl[,2:3],1,max)
fenl[,5] = apply(fenl[,2:3],1,which.max)
fenl## Estados A:1 A:2 ValueMax Decisión a tomar
## [1,] 3000 20 40 40 2
## [2,] 2500 20 0 20 1
## [3,] 2000 20 0 20 1
## [4,] 1500 20 0 20 1
## [5,] 1000 0 0 0 1
## [6,] 500 0 0 0 1
## [7,] 0 0 0 0 1Así, tenemos una matriz con el valor de la recursión y la decisión a tomar para cada posible estado en el que se puede estar en la última etapa de decisión. Así, continuamos con la penúltima etapa de decisión Agua. Para este objeto podemos llevar máximo 3 objetos cuando tenemos suficiente espacio \(\left( \frac{3000}{1000}=3\right)\) y mínimo 0. Por ende, el espacio de decisiones depende del valor de la variable de estado en esta época.
fagu = cbind(s, rep(0,length(s)),rep(0,length(s)),rep(0,length(s)),rep(0,length(s)),rep(0,length(s)), rep(0,length(s)))
colnames(fagu) = c("Estados", "A:0", "A:1", "A:2", "A:3", "ValueMax", "Decisión a tomar")
fagu[,2] = 0*b[2] + fenl[,4]
fagu[,3] = ifelse(w[2]*1>fagu[,1],0,1*b[2])+ifelse(fagu[,1] - w[2]*1<0,0,fenl[match(fagu[,1]-w[2]*1,fenl),4])
fagu[,4] = ifelse(w[2]*2>fagu[,1],0,2*b[2])+ifelse(fagu[,1] - w[2]*2<0,0,fenl[match(fagu[,1]-w[2]*2,fenl),4])
fagu[,5] = ifelse(w[2]*3>fagu[,1],0,3*b[2])+ifelse(fagu[,1] - w[2]*3<0,0,fenl[match(fagu[,1]-w[2]*3,fenl),4])
fagu[,6] = apply(fagu[,2:5],1,max)
fagu[,7] = apply(fagu[,2:5],1,which.max)-1
fagu## Estados A:0 A:1 A:2 A:3 ValueMax Decisión a tomar
## [1,] 3000 40 35 30 45 45 3
## [2,] 2500 20 35 30 0 35 1
## [3,] 2000 20 15 30 0 30 2
## [4,] 1500 20 15 0 0 20 0
## [5,] 1000 0 15 0 0 15 1
## [6,] 500 0 0 0 0 0 0
## [7,] 0 0 0 0 0 0 0Finalmente, hacemos la última recursión para la primera decisión que se toma: Bloqueador. Aquí, sabemos que el estado inicial es 3000, por lo que sólo tenemos que evaluar las decisiones en este estado. Además, tenemos que el número máximo de objetos que podemos llevar es de \(\left( \frac{3000}{500}= 6\right)\).
fblo =c(3000, 0,0,0,0,0,0,0)
fblo[2] = 0*b[1]+fagu[match(fblo[1]-w[1]*0,fagu),6]
fblo[3] = 1*b[1]+fagu[match(fblo[1]-w[1]*1,fagu),6]
fblo[4] = 2*b[1]+fagu[match(fblo[1]-w[1]*2,fagu),6]
fblo[5] = 3*b[1]+fagu[match(fblo[1]-w[1]*3,fagu),6]
fblo[6] = 4*b[1]+fagu[match(fblo[1]-w[1]*4,fagu),6]
fblo[7] = 5*b[1]+fagu[match(fblo[1]-w[1]*5,fagu),6]
fblo[8] = 6*b[1]+fagu[match(fblo[1]-w[1]*6,fagu),6]
fblo## [1] 3000 45 43 46 44 47 40 48print(paste0("Mi beneficio será:" ,max(fblo[2:8])))## [1] "Mi beneficio será:48"print(paste0("Debo empacar ",which.max(fblo[2:8])-1, " bloqueadores"))## [1] "Debo empacar 6 bloqueadores"De este modo, la estrategia para maximizar el beneficio es:
El beneficio al implementar esta política de decisión es de 48.
Ahora bien, en el literal b se plantea una evaluación del modelo cambiando el parámetro de entrada del beneficio del bloqueador. Esto equivale a cambiar en nuestro modelo el parámetro \(b[2] = 5\) y volver a correr la programación dinámica.
e = c(1,2,3) #Épocas (1: Bloqueador, 2: Agua, 3: Enlatados)
s = c(3000,2500,2000,1500,1000,500,0) #Espacio de estados
w = c(500,1000,1500) #Pesos
b = c(5,15,20) #Beneficios
x = 3000 #Espacio disponible en la mochilaSi existe una disminución de 3 unidades en el beneficio inmediato obtenido por empacar cada bloqueador, la estrategia que maximiza el beneficio es:
En este caso, el beneficio total al implementar esta política de decisión es de 45. Se concluye entonces que el beneficio total obtenido disminuye en 3 unidades al disminuir en 3 unidades la ganancia inmediata de empacar un bloqueador y la política de decisión cambia.
Peso total de la mochila: 3000.
| Objeto | Beneficio | Peso |
|---|---|---|
| Agua | 18 | 1200 |
| Bloqueador | 7 | 400 |
| Enlatados | 12 | 8000 |