INVESTIGACION DE OPERACIONES

UNIDAD 1
PROGRAMACIÓN DINÁMICA

Programación dinámica

La programación dinámica es un enfoque general para la solución de problemas en los que es necesario tomar decisiones en etapas sucesivas. Las decisiones tomadas en una etapa condicionan la evolución futura del sistema, afectando a las situaciones en las que el sistema se encontrará en el futuro (denominadas estados), y a las decisiones quese plantearán en el futuro.

Conviene resaltar que a diferencia de la programación lineal, el modelado de problemas de programación dinámica no sigue una forma estándar. Así, para cada problema será necesario especificar cada uno de los componentes que caracterizan un problema de programación dinámica.

El procedimiento general de resolución de estas situaciones se divide en el análisis recursivode cada una de las etapas del problema, en orden inverso, es decir comenzando por la última y pasando en cada iteración a la etapa antecesora. El análisis de la primera etapa finaliza con la obtención del óptimo del problema.


1.1 Características de los problemas de la programación dinámica

CARACTERÍSTICAS DE LOS PROBLEMAS DE PROGRAMACIÓN DINÁMICA

Las características de la programacióndinámica se emplean para formular e identificar la estructura de los problemas de este tipo. A continuación se presentarán estas características básicas que distinguen a los problemas de programación dinámica.

1. El problema se puede dividir en etapas que requieren una política de decisión en cada una de ellas. En muchos problemas de programación dinámica, la etapa es la cantidad de tiempo que pasadesde el inicio del problema, en ciertos casos no se necesitan decisiones en cada etapa.

2. Cada etapa tiene un cierto número de estados asociados a ella. Por estado se entiende la información que se necesita en cualquier etapa para tomar una decisión óptima.

3. El efecto de la política de decisión en cada etapa es transformar el estado actual en un estado asociado con la siguiente etapa (tal vezde acuerdo a una distribución de probabilidad).

4. El procedimiento de solución está diseñado para encontrar una política óptima para el problema completo, es decir, una receta para las decisiones de la política óptima en cada etapa para cada uno de los estados posibles.

5. Dado el estado actual, una política óptima para las etapas restantes es independiente de la política adoptada en etapasanteriores. (Este es el principio de óptimalidad para la programación dinámica). En general en los problemas de PD, el conocimiento del estado actual del sistema expresa toda la información sobre su comportamiento anterior, y esta información es necesaria para determinar la política óptima de ahí en adelante.

6. El procedimiento de solución se inicia al encontrar la política óptima para la últimaetapa. La política óptima para la última etapa prescribe la política óptima de decisión para cada estado posible en esa etapa.

7.Se dispone de una relación recursiva que indica la política óptima para la etapa dada la política óptima para la etapa (n+1).

A pesar de esta característica, los problemas que pueden ser atacados con la PD tienen otras dos propiedades adicionales:

Sólo un númeroreducido de variables se debe conocer en cualquier etapa con el fin de describir al problema. En efecto, los problemas de la PD se caracterizan por la dependencia de los resultados derivados de decisiones sobre un número reducido de variables.

El resultado de una decisión en cualquier etapa altera los valores numéricos de un número reducido de variables relevantes al problema. La decisión actual niincrementa ni decremento el número de factores sobre los cuales depende el resultado. Así, para la siguiente decisión en la secuencia, el mismo número de variables se considera (Hillier, 1991).
En un problema de PD una serie de decisiones se deben tomar en una secuencia dada. Cuando esto se cumple, una política óptima se debe perseguir. No importa cuáles fueron los estados y decisiones...