Programacion dinamicaю

...

[pic 10]

PROGRAMACIÓN DINÁMICA DETERMINÍSTICA

Esta sección profundiza en el enfoque de programación dinámica en los problemas de terminanticos, en los cuales el estado de la siguiente etapa está determinado por completo por el estado y la política de decisión de la etapa actual. El caso probabilístico en el que existe una distribución de probabilidad del valor posible del siguiente estado se analizará en la sección siguiente. La programación dinámica determinística se puede describir en un diagrama. En la etapa n el proceso está en algún estado sn. Al tomar la decisión xn se mueve a algún estado sn11 en la etapa n 1 1. La contribución a la función objetivo de ese punto en adelante se calculó como f *n 1 1(sn 1 1). La política de decisión xn también con tribuye a la función objetivo. Al combinar estas dos cantidades en la forma apropiada se obtiene f n(sn, xn), la contribución de la etapa n en adelante. De la optimización respecto de xn se obtiene entonces f *n(sn) 5 f n(sn, xn *). Una vez determinados xn * y f *n(sn) para cada valor posible de sn, el procedimiento de solución se mueve hacia atrás una etapa.

En la programación determinística el estado en la siguiente etapa está Completamente determinado por el estado y la política de decisión de la etapa actual.

Manera de Clasificar los Problemas de Programación Dinámica:

Forma de la función objetiva. Minimizar la suma de las contribuciones en cada una de las etapas individuales, o maximizar esa suma, o bien minimizar el producto de los términos, etc.

Naturaleza del conjunto de estados en las respectivas etapas. Los estados si pueden estar representados por:

1- Una variable discreta

2- Una variable de estado Continua

3- O un vector de estado (mas de una variable)

Para resolver un problema de programación dinámica debemos al menos: Identificación de etapas, estados y variable de decisión:

Cada etapa debe tener asociado una o más decisiones (problema de 0ptimizacion), cuya dependencia de las decisiones anteriores está dada exclusivamente por las variables de estado.

- Cada estado debe contener toda la información relevante para la toma de decisión asociada al período.

- Las variables de decisión son aquellas sobre las cuales debemos definir su valor de modo de optimizar el beneficio acumulado y modificar el estado de la próxima etapa.

- Descripción de ecuaciones de recurrencia: Nos deben indicar como se acumula la función de beneficios a optimizar (función objetivo) y como varían las funciones de estado de una etapa a otra.

- Resolución Debemos optimizar cada subproblema por etapas en función de los resultados de la resolución del subproblema siguiente.

- Notar que las para que las recurrencias estén bien definidas requerimos de condiciones de borde.[pic 11]

EJEMPLO DETERMINÍSTICA

[pic 12][pic 13]

===[pic 14]

[pic 15][pic 16]

[pic 17]

PROGRAMACION DINÁMICA PROBABILÍSTICA

La programación dinámica probabilística difiere de la determinística en que el estado de la siguiente etapa no está determinado por completo por el estado y la política de decisión de la etapa actual, en su lugar, existe una distribución de probabilidad para determinar cuál será el siguiente estado. Sin embargo, esta distribución de probabilidad queda completamente determinada por el estado y la política de decisión de la etapa actual. Se describe la estructura básica que resulta para los problemas de programación dinámica probabilística en lo que se refiere a este diagrama, sea s el número de estados posibles en la etapa n=1 y etiquete estos estados en el lado derecho con 1,2,….s. el sistema cambia al estado i con probabilidad p ( i – 1,2,….,s) dados el estado sn y la decisión xn en la etapa n. si el sistema cambia al estado i, c, es la contribución de la etapa n a la función objetivo.

Cuando se expande para incluir todos los estados y las decisiones posibles en todas las etapas, se obtiene lo que con frecuencia se conoce como árbol de decisión, el cual, si no es muy grande proporciona una forma útil de resumir las distintas posibilidades Para ilustrar lo anterior, suponga que el objetivo es minimizar las suma esperada de las contribuciones de las etapas individua les. En este caso, FN(SN, XN) representa la suma esperada mínima de la etapa n en adelante[pic 18]

[pic 19]

EJEMPLO PROBABILÍSTICA

[pic 20]

[pic 21]

[pic 22]

[pic 23]

[pic 24]

BIBLIOGRAFIA: