El problema de Programación Dinámica

En matemáticas aplicadas, tenemos en ocasiones sistemas dinámicos como este

x_{k+1}=f_k(x_k,u_k,w_k), k=0,1,...,N-1

Donde k es el indicador de tiempo, en un periodo finito preestablecido que va desde cero hasta N. Aquí x_k es la variable de estado del sistema en el periodo k, u_k es la variable de control en este mismo periodo y w_k es un parámetro aleatorio.

En breve, lo que deseamos es controlar una función de costo

\mathbb{E} \left\{ g_N(x_N)+\sum_{k=0}^{N-1} g_k(x_k,u_k,w_k)\right\}

Note que estamos usando el operador de la esperanza y que hemos dividido las funciones de costo de los periodos desde 0 hasta N-1, dejando al final un costo terminal.

Un ejemplo clásico de la programación dinámica es el del control de inventarios. Si la variable de estado denota el inventario disponible en cada periodo, la de control son las órdenes pedidas y otorgadas en el mismo periodo y el parámetro aleatorio es la demanda en ese momento del tiempo (asumimos que w_0,w_1,...,w_{N-1} son variables aleatorias independientes entre si). Por lo tanto el sistema evoluciona de acuerdo a la siguiente ecuación en diferencias:

x_{k+1}=x_k+u_k-w_k

El costo se divide en dos partes, que consisten en un costo de que mantener inventarios en existencia o que haya faltante en los inventarios (el costo de oportunidad), y el costo de las órdenes mismas de inventario. Por lo tanto el objetivo es minimizar

\mathbb{E} \left\{ R(x_N)+\sum_{k=0}^{N-1} (r(x_k) + c u_k) \right\}

Con la limitante de que no pueden haber pedidos negativos, es decir, no se pueden regresar inventarios para reducir costos.

El problema es interesante porque no se trata de encontrar un número mínimo, sino mas bien una regla que optimice el sistema. Puesto de otra manera, tratamos de encontrar una secuencias de reglas o funciones \mu_k, k=0,...,N-1 que mapee de la variable de estado al control (esto tiene sentido porque el control depende de la retroalimentación que recibe del estado). A esta secuencia de reglas \pi=\{\mu_0,...,\mu_{N-1}\} se le conoce como política (en inglés es policy, pero aún no me acaba de convencer traducirlo literalmente de esta manera).

Para cada \pi, el costo correspondiente para un stock inicial de x_0 fijo es

J_\pi(x_0) =\mathbb{E} \left\{R(x_N)+\sum_{k=0}^{N-1}(r(x_k)+x\mu_x(x_k))\right\}

Queremos minimizar J_\pi(x_0) para un estado inicial x_0 dado sobre todas las políticas posibles. Sea S_k un umbral de stock aceptable, se puede demostrar que la secuencia de reglas óptimas son aquellas que igualan a S_k-x_k si x_k<S_k, y 0 en cualquier otra situación.

Bibliografia

Bertsekas, D. P., & Bertsekas, D. P. (1995). Dynamic programming and optimal control (Vol. 1, No. 2). Belmont, MA: Athena Scientific.

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s