¿Cómo resolver este problema de LP como un problema de Programación Dinámica?

Question

La forma estándar del problema LP es

$$\min -3x_1-7x_2-10x_3 \text{ s.t. }$$ $$x_3\leq 2$$ $$40x_3+40x_2+20x_1\leq 180$$ $$x_1,x_2,x_3\geq 0$$

Mi última conferencia cubrió la ecuación de Bellman con el caso estacionario descontado obteniendo $J^*(x)=\min_u\left\{g(x,u)+\alpha J^*(f(x,u))\right\}$ y la forma general del algoritmo DP: $J_N(x_N)=g_N(x_N)$ y $J_k(x_k)=\min_{u_k}\left\{g_k(x_k,u_k)+J_{k+1}(f_k(x_k,u_k))\right\}$ donde $k=0,1,...,N-1$ .

Estoy intentando resolver este LP como problema de Programación Dinámica pero no veo por dónde empezar. ¿Es el $g(x)=-3x_1-7x_2-10x_3$ ? ¿Cuál es la $J_k(x_k)$ ¿Aquí? ¿Se mantiene esto $J_k(x_k)=J(x)$ ?

Solución del problema resuelto como LP

Por simplex el óptimo es $x_B=(x_2,x_3)=(2.5,2)$ con el $c_B'B^{-1}b=-37.5$ .

Answer 1

La idea básica es utilizar la inducción hacia atrás. Los beneficios marginales son $b=(b_1,b_2,b_3)=(0.15,0.175,0.25)$ . Así que primero veremos $x_3$ con la mayor ganancia marginal, entonces $x_2$ y por último $x_1$ . La optimización se basa en el principio de optimalidad de la programación dinámica en los siguientes ejemplos: supongamos que a-b-c es óptimo desde el estado A hasta el estado C, entonces b-c debe ser óptimo desde el estado B hasta el estado C.

Supongamos que 1-2-3 es óptimo, entonces 1-2 y 2-3 deben ser óptimos. 2-3 significa que la elección de $x_3$ cuando $x_3\leq 2$ así que $40*2\leq 180$ por lo que esta es la opción óptima. Ahora con 100 recursos, 1-2 es óptimo porque $2*40\leq 100$ y $3*40\not \leq 100$ . Ahora bien, como todos los recursos se utilizan al final cuando $x_1=1$ Hemos encontrado la solución óptima, el ejemplo con los números enteros - de manera similar con los números reales.

Problema de números enteros

Utilizamos todo de $x_3$ así que $x_3=2$ a causa de la restricción $x_3\leq 2$ . A continuación, examinaremos $x_2$ y utilizar esas 2 unidades porque de lo contrario $40*2+40*2=200\leq 180$ rompiendo una restricción. Así que la última unidad es $x_1=1$ por lo que $x=(1,2,2)$ cuando $x\in\mathbb Z^3$ .

Problema real

De forma similar a la anterior, pero el paso 2 es diferente, ya que podemos utilizar 2,5 unidades en lugar de sólo 2 unidades. Si $x\in\mathbb R^3$ entonces $x=(0,2.5,2)$ el mismo resultado que obtuviste con el Simplex.