Programacion Dinamica

17/07/2012

PROCESOS ESTOCASTICOS

Programación Dinámica
La Programación Dinámica (PD) intenta mejorar la eficiencia del cálculo de problemas descomponiéndolos en subproblemas de menor tamaño, más fáciles de de resolver. La PD está basada en el principio de optimalidad de Bellman: “Cualquier subsecuencia de decisiones de una secuencia óptima de decisiones que resuelve un problema tambiéndebe ser óptima respecto al suproblema resuelto.” La PD resuelve el problema en etapas (problemas multietápicos). En cada etapa interviene una variable de optimización. Los cálculos de las diferentes etapas se enlazan de forma recursiva para generar la solución óptima.

Prog. Prog. Dinámica

Dra. Norka Bedregal Alpaca

Programación Dinámica
La Programación Dinámica (PD) sigue el razonamientoinductivo:

Programación Dinámica
La solución de un problema de programación dinámica requiere de ingenio y de diseño de los detalles Las decisiones para cada una de las etapas constituyen una política óptima, sin importar cuál haya sido la política adoptada en las otras etapas El principio de optimalidad establece el marco de referencia para unificar los n – subproblemas o n – etapas de losproblemas de programación dinámica

Prog. Prog. Dinámica

¿cómo resolver un problema combinando soluciones para problemas más pequeños? Determina la solución óptima de un problema de n-variables descomponiéndolo en n-etapas Utiliza el criterio del principio de optimalidad La naturaleza de las etapas difiere dependiendo del problema de optimización En consecuencia la metodología de los cálculospara optimizar cada etapa también difiere. Dra. Norka Bedregal Alpaca

Prog. Prog. Dinámica

Dra. Norka Bedregal Alpaca

1

17/07/2012

Programación Dinámica

Programación Dinámica
La idea es la misma que en divide y vencerás... pero aplicando una estrategia distinta.
Programación Dinámica Similitudes Descomposición recursiva del problema Se obtiene aplicando un razonamiento inductivoDiferencias Resuelve primero los problemas más pequeños, guardando los resultados en una tabla programa iterativo Divide y Vencerás Descomposición recursiva del problema Se obtiene aplicando un razonamiento inductivo Aplica directamente la fórmula recursiva

Problema Original

Programación Dinámica Descomposición

Prog. Prog. Dinámica

n variables 1 etapa

1 variable n etapas

1 7 8 62 3 5 4

Prog. Prog. Dinámica

programa recursivo

Dra. Norka Bedregal Alpaca

Dra. Norka Bedregal Alpaca

Programación Dinámica
Determina Determina

Programación Dinámica

Prog. Prog. Dinámica

Prog. Prog. Dinámica

Decisión d Entrada x Salida y

dn
x n +1 xn

d n −1
x n −1 x i +1

di
xi
x3

d2
x2

d1
x1

n

n-1

i

2

1

Transformación y=h(x;d)fn

f n −1

fi

f2

f1

Estado n

Estado n-1

Estado i

Estado 2

Estado 1

Retorno f=f(x,d)

Dra. Norka Bedregal Alpaca

Dra. Norka Bedregal Alpaca

2

17/07/2012

Recursividad en los Cálculos de la PD
Los cálculos de PD se hacen recursivamente

Recursividad en los Cálculos de la PD
A medida que se avanza de un subproblema a otro, hay que dar la razón de laviabilidad de estas restricciones Los problemas de la programación dinámica ocupan recursiones tanto hacia adelante como hacia atrás En ambas direcciones se debe producir la misma solución Aún cuando el procedimiento hacia delante parece más lógico, la programación dinámica utiliza generalmente la recursión hacia atrás, dado que es más eficiente en los cálculos

Prog. Prog. Dinámica

Lasolución óptima de un subproblema se utiliza como una entrada para el siguiente subproblema. Al resolver el último subproblema, se tendrá la solución óptima para todo el problema La forma de los cálculos recursivos depende de la descomposición del problema original. En general, los subproblemas se unen a través de algunas restricciones comunes.

Dra. Norka Bedregal Alpaca

Prog. Prog. Dinámica...