Programacion dinamica

PROGRAMACION DINAMICA
˜La programación dinámica se utiliza tanto en problemas lineales como no lineales.
˜La programación dinámica es útil para resolver un problema donde se deben tomar una serie de decisiones interrelacionadas.

˜A diferencia de la P.L, la programación dinámica no tiene formulación matemática estándar. Se trata de un enfoque de tipo general para la solución de problemas, ylas ecuaciones se derivan de las condiciones individuales de los mismos.

El problema de la diligencia:
Un caza fortunas desea ir de Missouri a California en una diligencia, y quiere viajar de la forma más segura posible. Tiene los puntos de salida y destino conocidos, pero tiene múltiples opciones para viajar a través del territorio.
Se entera de la posibilidad de adquirir seguro de vidacomo pasajero de la diligencia.


¿Cual es la ruta que minimiza el costo total de la póliza de seguro?

1. Enumeración exhaustiva: Enumerar todas las rutas posibles, calcular su costo y elegir la de menor valor. En total son 18

2. Elegir la ruta más barata en cada etapa. Esta solución no conduce al óptimo global. Un pequeño sacrificio en una etapa puede permitir mayores ahorros más adelante.Algunas alternativas de solución.


3. Programación dinámica.
Estrategia de solución: Un problema complejo es desagregado en problemas simples que se resuelven etapa por etapa. En el caso de la diligencia un problema simple sería pensar qué pasaría si al viajero sólo le faltara una jornada de viaje.

Por P.D la solución sería entonces ir desde el estado actual (cualquiera que sea) yllegar a su destino final (estado J) al costo cij Se hace lo mismo para cada jornada (etapa), ensanchando el problema. Así encontramos
la solución óptima del lugar al que debe
dirigirse teniendo en cuenta la información
de la iteración anterior.
Veamos la formulación:

Sea Xn ( n = 1,2,3,4 ) las variables que representan el destino inmediato en la etapa
n.
Luego la ruta seleccionada será:Formulación.
A X1 X2 X3 X4
Donde X4 = J
sigue
19-10
Sea fn (S, Xn) el costo total de la mejor política global para las etapas restantes, dado que el agente se encuentra en el estado S, listo para iniciar la etapa n y se dirige a Xn
como destino inmediato.
Dados S y n , sea Xn
* el valor de Xn (no
necesariamente único), que minimiza fn (S , Xn) , y sea fn
*(S) el valor mínimo
correspondientede fn (S, Xn) entonces: sigue sigue fn(S, Xn) =
Costo
inmediato
(etapa n)
Mínimo costo
futuro (etapa
n+1 en adelante)
+
= cs , xn + fn+1 * (Xn) Costos por ir de la ciudad i al destino j Costo óptimo acumulado fn *(S) = Min Xn fn (S, Xn) = fn (S, Xn *)

Como el destino final (estado J) se alcanza al terminar la etapa 4, entonces f5
*(J) = 0
El objetivo es hallar f1 *(A) y su rutacorrespondiente. Cuando el cazafortunas tiene sólo una etapa por recorrer (n=4) , su ruta de ahí en adelante, estará determinada por el estado actual (H o I) y su destino
final X4 = J
La ruta será: S J donde S= H o I
Etapa n=4
Procedimiento de solución hacia atrás
3
19-13
f4 (H) = cH , J = 3
f4 (I) = c I , J = 4
= c S , J
S
H
I
f4 *(S) 3 4 X4 * J J
El cazafortunas tiene 2 etapas porrecorrer (n=3). Suponga que sale de E. Etapa n=3 E H I C E, H =1 C E, I =4 + f4 *(H) = f3(E)= cE ,H + f4 *(H) = 4 + f4 *(I) = f3(E)= cE ,I + f4 *(I) = 8 Luego f4 *(S) = c S , J + f5 *(J)

Luego f3
*(E) = 4 y X3
* = H En general para la etapa 3 se tiene:
S
E
F
f3 (S, X3)= cS ,X3+ f4
*( X3)
4
9
f3
*(S)
8
7
X3
G
X3
*
6 7
H I
4
7
6
H
I
H
19-15
Etapa n=2
En la segunda etapa, elcazafortunas tiene 3 jornadas por recorrer (n=2). Suponga que sale de C + f3 *(E) = f2(C)= cC ,E + f3 *(E) = 7 + f3 *(F) = f2(C)= cC ,F + f3 *(F) = 9 + f3 *(G) = f2(C)= cC ,G + f3 *(G) = 10 C E F G c C , E =3
c C, F =2 c C , G =4 19-16
Luego f2
*(C) = 7 y X2 * = E
En general para la etapa 2 se tiene:
S
B
C
f2 (S, X2)= cS ,X2 + f3
*( X2)
11
7
f2 *(S) 11 9 X2 D X2 * 8 8 E F 11 7 8 E o...