ELEMENTOS DE PROGRAMACIÓN DINÁMICA

ELEMENTOS DE PROGRAMACIÓN

DINÁMICA

 INTRODUCCIÓN

Las dificultades que presentaba la resolución de determinados problemas de gestión de stocks determinaron el nacimiento, a comienzos de la década de los cincuenta, de la programación dinámica. R. Bellman descubrió el principio de optimización de esta gama de problemas, a los que denominó programas dinámicos. Los problemas de Programación dinámica son problemas de decisión por etapas o de carácter secuencial; problemas en los que la variable tiempo es relevante, y en los que las decisiones tomadas en un estado o fase del sistema condicionan las decisiones a tomar en los siguientes.

Si consideramos al tiempo como variable discreta, o sea t toma valores en el conjunto {0, 1,. . ., n,. . .}, la estructura recursiva del principio de optimalidad resulta sumamente útil. La idea es resolver para el último periodo, después para los dos últimos periodos, luego para los tres últimos y así sucesivamente. Cuando el número de periodos es grande, este mecanismo resulta extremadamente complejo, pero hoy en día una gran cantidad de problemas pueden resolverse mediante el uso de computadoras.

 ESTRUCTURA DEL PROBLEMA

Para simplificar la exposición, consideremos únicamente un estado x y un control u.

Sean:

F = {ft : D → R | D ⊆ R2, t = 0, ..., T},

G = {gt : E → R | E ⊆ R2, t = 0, ..., T},

Dos familias de funciones de clase C2, y sean:

x : {0, ..., T + 1} → R,

u : {0, ..., T} → R,

Dos funciones.

Denotemos por x(t) = xt y u(t) = ut y, como antes, decimos que x es la variable de estado y u la de control. Finalmente sea VT+1 una función con dominio e imagen en R, de clase C2. La estructura general del problema de programación dinámica es escoger u y x que resuelvan:

sujeto a xk+1 = gk(xk, uk), k = 0, ..., T,

x0 y xT+1 dados.

El equivalente de la función valor es ahora:

que representa, igual que antes, el máximo a partir del periodo t ∈ {0, ..., T}. El principio de optimalidad de Bellman se expresa con lo que usualmente se conoce como ecuación de Bellman, que es:

Vt(xt) = max{ft(xt, ut) + Vt+1(xt+1)}

 PROBLEMAS CON DESCUENTO TEMPORAL

Sea ρ la tasa de descuento temporal. El problema general, con el estado final libre, se puede plantear ahora como:

sujeto a: xk+1 = gk(xk, uk),

x0 dado, xT+1 libre.

De manera que la ecuación de Bellman es:

Vt(xt) = max{βtft(xt, ut) + Vt+1(xt+1)},

xt+1 = gt(xt, ut), xt dado.

en donde la función valor Vt(xt) se mide en unidades al tiempo t = 0 y es el factor de descuento temporal. Si expresamos a la función valor en unidades del periodo t, esta ecuación queda como:

Vt(xt) = max{ft(xt, ut) + β Vt+1(xt+1)},

La función Vt es la función valor en tiempo corriente t y se relaciona con la función valor en tiempo presente Vt (donde Vt se mide en unidades del tiempo inicial t = 0) mediante Vtβt = Vt. Siempre que exista el factor de descuento consideraremos la función valor y la ecuación de Bellman en tiempo corriente. Abusando de la notación, al igual que en el caso de los hamiltonianos en tiempo corriente y en tiempo presente, la denotaremos simplemente por Vt.

Las condiciones de primer orden se reescriben ahora como:

De esta forma se introduce el descuento temporal de manera trivial. Normalmente tendremos que ρ es la tasa subjetiva de descuento o bien la tasa real r. En economía, es común que las funciones fk y gk no dependan explícitamente del tiempo, de manera que el problema es “casi autónomo” pues el tiempo sólo aparece como potencia en el factor de descuento. Al igual que en el caso continuo, la función valor en tiempo corriente transforma al problema en uno autónomo. Por esta razón, de aquí en adelante omitiremos el subíndice t en la función valor en tiempo corriente.

 PROBLEMAS CON HORIZONTE INFINITO

Al igual que en el caso de tiempo continuo, cuando el horizonte es infinito se debe poder garantizar la convergencia de la serie . Si existe un factor de descuento β ∈ (0, 1), la convergencia se da si ft es acotada (misma cota para toda t) o creciente, siempre y cuando converja. Dado que en economía casi siempre aparece el factor de descuento, suponemos que el problema general está dado por

Sujeto a xt+1 = gt(xt, ut), x0 dado.

No tiene sentido empezar con el último periodo y proceder recursivamente hacia t = 0 dado que no hay un periodo terminal. No obstante, la función valor se define, igual que antes, como el máximo a partir del periodo t, es decir:

La ecuación de Bellman es, una vez más. Como ésta sólo involucra dos periodos de tiempo, las condiciones de primer orden son las mismas que en el teorema anterior. De las dos primeras condiciones se puede eliminar V’t

...