Programación dinámica probabilística (II)

Debido a la estructura probabílistica, la relación entre fn(sn, xn) y f*2(sn+1) necesariamentees más complicada que para el caso determinístico. La forma exacta de esta relación dependerá de la forma global de la función objetivo.

Para ilustrar esto, supóngase que el objetivo es minimizar la suma esperada de las contribuciones de las etapas individuales. En este caso, fn(sn, xn) representa la suma esperada mínima de la etapa n  en adelante, dado que en la etapa n, el estado es sn y la política de decisión es xn. En consecuencia

Programación dinámica probabilística (I)

La programación dinámica probabilística difiere de la deterministica en que el estado de la siguiente etapa no está completamente determinado por el estado y la política de decisión de la etapa actual. En este caso, existe una distribución de probabilidad para determinar cuál será el estado en la siguiente etapa. Sin embargo, esta distribución de probabilidad sí queda bien determinada por el estado y la política de decisión en la etapa actual. En la figura 11.8 se describe la estructura básica que resulta en los problemas de programación dinámica probabílistica.

En lo que se refiere a este diagrama, sea S el número de estados posibles en la etapa n +1 que se etiquetan al lado derecho por 1,2,...., S. El sistema cambia al estado i con probabilidad pi(i=1,2,.....,S) dados el estado sn y la decisión xn en la etapa n. Si el sistema cambia al estado i, Ci es la contribución de la etapa n a la función objetivo.

Cuando se expande la figura 11.8 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. Si este árbol de decisión no es muy grande, proporciona una foma útil de resumir las distintas posibilidades que se tienen.

Solución Problema de la Wyndor Glass Company (VI)

Etapa I: Para resolver el problema de dos etapas (n=1), se sustituye la solución que se acaba de obtener para f*2(R1,R2, R3) en la ecuación (3). Para la etapa 2

Solución Problema de la Wyndor Glass Company (V)

Etapa 2

Formulación Problema de la Wyndor Glass Company (IV)

De manera parecida, para n = 1,2

La ecuación (1) se usará para resolver el problema de 2 etapas. La ecuación (2) muestra la estructura básica de programación dinámica para este problema, como puede ver en la figura 11.7. La ecuación (3) proporciona una relación recursiva entre f*1 y f*2 que se usará para resolver el problema de una etapa.

Formulación Problema de la Wyndor Glass Company (III)

Cada una de las tres variables de estado continua, por lo que, en lugar de considerar por separado las combinaciones posibles de valores, debe emplearse el método introducido en ele ejmplo 4 para obtener la información requerida como una función del estado del sistema.

Pese a estas complicaciones, el problema es lo suficientemente pequeño como para poder resolverse sin mucha dificultad. Para hacerlo es necesario introducir la notación usual de programación dinámica. Así.

fn(R1, R2, R3, x2) = contribución de la actividad 2 a Z si el sistema encuentra en el estado (R1, R2, R3) al inciar la etapa 2 y la decisión es x2

= 5x3.

Formulación Problema de la Wyndor Glass Company (II)

Pero al comenzar este problema en la etapa 2, todavía no se conoce el valor de x1 por lo que en ese momento se usa s2 = (R1, R2, R3).

Contrariamente a los ejemplos anteriores, este problema tiene tres variables de estado (es decir, es un vector estado con tres componentes) en lugar de una. Desde un punto de vista teórico, esta diferencia no es seria. Sólo significa que, en lugar de considerar todos los valores posibles de una variable de estado, deben considerarse todas las combinaciones posibles de valores de varias variables de estado. Sin embargo, desde un punto de vista de eficiencia computacional, esta diferencia tiende a ser una complicación muy seria. Como en general el número de combinaciones puede ser tan grande como el producto del número de valores posibles de las respectivas variables, la cantidad de cálculos que se requieren tiende a "explorar" muy rápido cuando se introducen variables de estado adicionales. Este fenómeno ha recibido el adecuado nombre de calamidad de la dimensión.