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.