Investigacion De Operaciones

Introducción

La programación dinámica determinística se puede describir en forma de

diagrama como se muestra en la siguiente figura.

Etapa Etapa

n n+1

Etapa

Contribución

de xn

fn(sn, xn) f *

n+1(sn+1)

En la etapa n el proceso se encuentra en algún estado sn . Al tomar la decisión

xn se mueve a algún estado sn+1 en la etapa n+1. El valor de la función objetivo

para la política óptima de ese punto en adelante se calculó previamente como

f*

n+1(sn+1). La política de decisión también hace una contribución a la función

objetivo. Al combinar estas dos cantidades en la forma apropiada se

proporciona a la función objetivo fn(sn , xn ) la contribución de la etapa n en

adelante. La optimización respecto a xn proporciona entonces f*

n(sn)=fn(sn, x*

n).

Una vez encontrada x*

n y f*

n(sn) para cada valor posible de sn, el procedimiento

de solución se mueve hacia atrás una etapa.

Una manera de clasificar los problemas de programación dinámica

determinística es por la forma de la función objetivo. Por ejemplo, el objetivo

puede ser minimizar la suma de las contribuciones de cada una de las etapas

individuales, o maximizar esa suma, o bien minimizar el producto de los,

etcétera. Otra clasificación se puede hacer en términos de la naturaleza del

conjunto de estados en las respectivas etapas. En particular, los estados sn

pueden ser representados por una variable de estado discreta, o por una

variable de estado continua, o tal vez requiere un vector de estado (más de una

variable).

Para la elaboración de este documento se ha hecho uso extenso del trabajo de Frederick S. Hillier y Gerald J.

Lieberman (1997).

...