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
Enviado por Angie Ortiz Giraldo • 9 de Noviembre de 2015 • Tarea • 4.598 Palabras (19 Páginas) • 872 Visitas
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:
Pasos | Procedimiento | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Ejercicio N° 1 Enunciado | Una joven emprendedora experta en estadística cree haber desarrollado un sistema para ganar un popular juego en Las vegas. Sus colegas no piensan que este sistema sea tan bueno, por lo que le apuestan que si comienza con tres fichas, ella no tendrá al menos cinco fichas después de tres jugadas. Cada jugada incluye apostar cualquier cantidad de las fichas disponibles y ganar o perder este mismo número de fichas. La joven cree que su sistema dará probabilidad de 2/3 de ganar una jugada dada. Suponiendo que la experta estadística está en lo correcto se quiere usar programación dinámica para determinar su política óptima sobre cuántas fichas apostar (si apuesta alguna) en cada una de tres jugadas para determinar. La decisión en cada jugada deberá tomar en cuenta los resultados de las jugadas anteriores. El objetivo es maximizar la probabilidad de ganar la apuesta hecha a sus colegas: | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Objetivo | Maximizar la probabilidad de que la joven gane la apuesta | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Formulación | Etapas n=(1,2,3) Xn= Número de fichas que debe apostar en la etapa n Sn= Número de fichas que se tienen para comenzar la etapa n. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||
La función objetivo que debe maximizarse en cada etapa es la probabilidad con más de cinco fichas o con justo cinco fichas, ya que la apuesta se gana de las dos formas | fn(Sn,Xn)= Probabilidad de terminar las tres jugadas con cinco fichas o más. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Planteamiento matemático | [pic 1] | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Dado que la joven comienza la etapa n con con S fichas, su decisión inmediata es Xn y en adelante toma decisiones óptimas | [pic 2] [pic 3] | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||
La expresión , refleja el hecho de que un momento dado es posible acumular aun cuando pierda en la siguiente jugada.[pic 4] - Si pierde: El estado en la siguiente será y la probabilidad de terminar con menos de cinco fichas será .[pic 5] - Si gana: El estado del sistema será y la probabilidad correspondiente será [pic 6][pic 7] Así, se supone que la probabilidad de ganar una jugada dada es , se concluye que:Etapa [pic 8] n=3 | [pic 9]
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Etapa n=2 | [pic 16]
... Disponible sólo en Clubensayos.com
|