Programación dinámica

SOLUCIONARIO

Sobre Programación Dinámica por

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

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)

2004 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?

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

“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 vivir realmente la vida de otra persona.”

Eleanor Roosevelt

2

Ing. ¡ Programación Dinámica.

Miguel Jiménez C. M.Sc. PROGRAMACIÓN DINÁMICA

Ahora es posible usar la función general de la programación dinámica y luego representar esa función en términos del problema como sigue: 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

Función Recursiva General de PD.

SDRgSf

n *

),([)( n = n nn + 1

+ Sf n *

+ 1 )]( n + 1 su solución, además pueden ser divididos en problemas más pequeños. Esta característica del problema de dividirse en subproblemas es aprovechada por la programación dinámica para encontrar la solución.

Función Recursiva La forma de operar de la programación dinámica es dividir el problema en problemas más

para el Problema 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 es

Donde: completamente resuelto. Entre una etapa y la siguiente existe una liga que permite el nexo entre etapas esta liga se llama función recursiva.

Representa la distancia por tomar la decisión Dn en la etapa n, para pasar del estado Sn al estado Sn+1 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

Representa el mejor valor en la etapa n+1, cuando el estado es Sn+1 problema:

Representa el mejor valor en la etapa n, cuando el estado es Sn 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

Nota: debe notar que tanto Sn, como Sn+1 toman un conjunto de valores, por ejemplo S3 toma los valores: de una red de caminos que los conecta dados los retornos (costos beneficios tiempo, etc), asociados con los arcos o ramas de la red.

(5, 6 y 7) y S3+1 = S4, toma los valores (8, 9, 10 y 11).

2 11 5

2 3

8

8

9

11

3Utilizando la forma tabular de la PD tenemos, para las diferentes etapas:

Para n = 5

)( ,([ ) ( 15 )] 39

6 5

Estado

DECISIÓN (D5) S5 14 S S 4

94

Sf

n *

)( n = SDRMin SD nn

,

),([ n n n + 1 + Sf n *

+ 1 ( n + 1 )] SDR nnn ),( + 1 = Sf n *

+ 1 )( n + 1 = Sf

n * )( n = 58

2

4

Sf 5

*5

=

Min SD

5 , 15 + SDR 5 5 15 + + f 15 * + S + 3

12 4 4 14 13 3 3 14

Para n = 4 En este caso lo primero que hay que reconocer es, 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 subproblema sea más fácil; en este sentido se ha dividió el problema en 5 etapas, de la 1 a la 5 conforme se aprecia en la parte inferior de la red. Obsérvese que es más fácil tomar una decisión en cada etapa pues la decisión será directa; por ejemplo si estamos en la etapa 3 (subproblema 3) al inicio nos podemos encontrar en los nodos 5 , 6 ó 7 y podemos ir a los nodos 8, 9, 10 ú 11 la decisión es inmediata, pues solo existe una rama en cada alternativa. Esta característica es importante reconocer para tomar la decisión de aplicar la metodología de la programación dinámica.

...