En la programación dinámica probabilística, el estado en la etapa siguiente nos queda completamente determinado por el estado y la decisión de la subpolítica en el estado actual

EJERCICIOS

PROGRAMACIÓN DINÁMICA PROBABILÍSTICA

Octubre de 2015

Investigación de Operaciones II-Grupo 9 

Mónica Patricia Novoa      Cód: 20131020072

Angie Lorena Cárdenas    Cód: 20131020082

Steve Aguilar Uribe           Cód: 20122020032

  Angie Ortiz Giraldo           Cód: 20112020071

Objetivo: 

Proponer, plantear y desarrollar ejercicios de Programación Dinámica Probabilística  mostrando paso a paso el proceso para abordar y solucionar el problema planteado.

Programación Dinámica Probabilística:

En la programación dinámica probabilística, el estado en la etapa siguiente nos queda completamente determinado por el estado y la decisión de la subpolítica en el estado actual, sino que existe una distribución de probabilidad para lo que sería el estado siguiente

Carácter probabilístico: El carácter probabilístico se ve reflejado en que los retornos y estados adoptados en cada etapa tienen asociada una probabilidad de ocurrencia; esto quiere decir que el estado en la siguiente etapa no estará completamente determinado por el estado y la política de decisiones en la etapa actual, en cambio hay una distribución de probabilidad para determinar un grado probabilidad de ocurrencia en el estado siguiente basado en el estado y política del estado actual.  

Recursividad Los cálculos de programación dinámica se hacen en forma recursiva, ya que la solución óptima de un sub-problema se usa como condición inicial para el siguiente subproblema. Para cuando se resuelve el último subproblema queda a la mano la solución óptima de todo el problema la cual contempla una política de decisiones etapa a etapa, en donde considera el resultado obtenido (el cual depende de su probabilidad de ocurrencia y sobre él se construye dicha política).

Con las recursiones en avance y en reversa se obtiene la misma solución. Aunque el procedimiento en avance parece más lógico, en las publicaciones sobre programación dinámica se usa la recursión en reversa de modo invariable. La razón de esta preferencia es que, en general, la recursión en reversa es más eficiente, desde el punto de vista computacional

Algoritmo solución:

1)División del problema en subproblemas

2)Planteamiento de la relación recursiva

3) Inicio en la etapa n (siendo n un sub-problema), considerando las limitaciones que den lugar en dicha etapa, para tomar la decisión correspondiente, escogiendo aquella que represente el retorno óptimo

4) Desarrollar el problema hasta la n-ésima etapa reconstruyendo los retornos de acuerdo a la etapa  anterior

5)Desarrollar hasta la etapa 1 (generalmente se desarrolla en retroceso )y concluir con los retornos de las etapas anteriores para poder hallar la solución óptima de acuerdo con los requerimientos del problema

Ejercicios:

Conclusiones:

• A diferencia de la programación dinámica determinística en la programación dinámica probabilística se consideran los resultados posibles que arroje el problema dados por las probabilidades asociadas al problema.
• La PDP es una herramienta útil a la hora de predecir resultados debido a que se manejan probabilidades en vez de valores determinados.
• Esta programación resulta muy útil cuando los problemas tienen un nivel de incertidumbre alto.

Referencias:

• http://htomadedecisiones.blogspot.com.co/2013/09/ejercicio-2.html
• Notas de clase. Profesora: Lilian Astrid Bejarano Garzón.