Programacion Dinamica

Ing. Miguel Jiménez C. M.Sc.

SOLUCIONARIO
Sobre Programación Dinámica por

Ing. Miguel Jiménez Carrión M.Sc
mjimenezc@speedy.com.pe jim_car_miguel@hotmail.com

“En algún punto de la línea de desarrollo descubrimos lo que somos en realidad, y luego tomamos nuestra verdadera decisión por la cual somos responsables. Tome esa decisión principalmente por usted, ya que nunca se puede vivirrealmente la vida de otra persona.”

Modelo de la Diligencia Asignación de Recursos El modelo de la mochila Producción e Inventario Confiabilidad
R1 (D1, S2) R2 (D2, S3) R3 (D3, S4)

Eleanor Roosevelt

S1=6

Región 1

S2 = S1 - D1

Región 2

S3 = S2 - D2

Región 3

S4 = S3 - D3

D1 ¿Cuántos agentes asignar?

D2 ¿Cuántos agentes asignar?

D3 ¿Cuántos agentes asignar?

20042

Programación Dinámica. PROGRAMACIÓN DINÁMICA La programación dinámica es un método para resolver ciertos problemas de programación matemática, cuya característica de estos problemas es que los modelos matemáticos que los representan son complejos y por tanto requieren mucho procesamiento de cómputo para encontrar su solución, además pueden ser divididos en problemas más pequeños. Estacaracterística del problema de dividirse en subproblemas es aprovechada por la programación dinámica para encontrar la solución. La forma de operar de la programación dinámica es dividir el problema en problemas más pequeños llamados subproblemas, luego inicia el proceso de solución por etapas; en donde cada etapa del proceso resuelve un subproblema y al finalizar con todas las etapas, el problema escompletamente resuelto. Entre una etapa y la siguiente existe una liga que permite el nexo entre etapas esta liga se llama función recursiva. Los ejemplos que siguen muestran el proceso de solución describiendo al mismo tiempo la notación de la función recursiva, explicándose lo esencial y las características particulares de cada problema: Caso1: Problema de la Diligencia 1) Este problema estáreferido a encontrar la ruta óptima (ruta mínima o ruta más confiable), para viajar desde un punto llamado nodo inicial o fuente hacia otro llamado nodo final o destino a través de una red de caminos que los conecta dados los retornos (costos beneficios tiempo, etc), asociados con los arcos o ramas de la red.
3 5 2 11 4 9 3 4 6 7 4 11 6 6 5 10 9 8 5 8

Ing. Miguel Jiménez C. M.Sc. Ahora es posibleusar la función general de la programación dinámica y luego representar esa función en términos del problema como sigue: Función Recursiva General de PD. Función Recursiva para el Problema Donde:

f n* ( S n ) = g [ R n ( D n , S n +1 ) + f n*+1 ( S n +1 )]
f n* ( S n ) = Min [ R n ( D n , S n +1 ) + f n*+ 1 ( S n +1 )]
Dn ,S n

Rn (Dn , Sn+1 ) =
f n*+1 ( S n +1 ) = f n* ( S n ) =
(5, 6 y7) y S3+1

Representa la distancia por tomar la decisión Dn en la etapa n, para pasar del estado Sn al estado Sn+1 Representa el mejor valor en la etapa n+1, cuando el estado es Sn+1 Representa el mejor valor en la etapa n, cuando el estado es Sn

Nota: debe notar que tanto Sn, como Sn+1 toman un conjunto de valores, por ejemplo S3 toma los valores:
= S4, toma los valores (8, 9, 10 y 11).Utilizando la forma tabular de la PD tenemos, para las diferentes etapas:
9 3 7 6 13 3

2 5 1 2 3

11 8

8
9 12 4 14

Para n = 5

f 5* ( S 5 ) = Min [ R 5 ( D 5 , S 5 + 1 ) + f 5*+ 1 ( S 5 + 1 )]
D
5

,S

5 +1

Estado S5 12 13

DECISIÓN (D5) 14 4 3

f 5* (S5 )
4 3

* D5 ( S 5 )

14 14

1

2

3

4

5
Para n = 4

En este caso lo primero que hay que reconoceres, que al tomar una decisión para decidir que ruta seguir en forma general para todo el problema, involucra analizar toda la red esto hace que el problema sea complejo, por cuanto del nodo 1 al 14 existen múltiples alternativas en las que se encuentran varias ramas en la ruta. En segundo lugar, ver si es posible dividir el problema en subproblemas o etapas de manera que la decisión en cada...