Investigacion de Operaciones
Páginas: 32 (7881 palabras)
Publicado: 16 de junio de 2013
Ing. Miguel Jiménez C. M.Sc.
SOLUCIONARIO
Sobre Programación Dinámica
por
“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.”
Ing. Miguel Jiménez Carrión M.Scmjimenezc@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)
S1=6
Región 1
R2 (D2, S3)
S2 = S1 - D1
D1
¿Cuántos agentes
asignar?
Región 2
Eleanor Roosevelt
R3 (D3, S4)
S3 = S2 - D2
D2
¿Cuántos agentes
asignar?
Región 3
S4 = S3 - D3
D3
¿Cuántos agentesasignar?
2004
2
Programación Dinámica.
Ing. Miguel Jiménez C. M.Sc.
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:
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 losmodelos 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. Esta caracterí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 enproblemas 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 es
completamente 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 desolució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 decaminos que los conecta dados los retornos (costos beneficios tiempo, etc),
asociados con los arcos o ramas de la red.
11
2
5
2
1
5
8
11
4
3
6
9
7
f n* ( S n ) = Min [ R n ( D n , S n +1 ) + f n*+ 1 ( S n +1 )]
Rn (Dn , Sn+1 ) =
Representa la distancia por tomar la decisión Dn en la etapa n, para pasar
del estado Sn al estado Sn+1
f n*+1 ( S n +1 ) =Representa el mejor valor en la etapa n+1, cuando el estado es Sn+1
f n* ( S n ) =
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:
(5, 6 y 7) y S3+1
= S4, toma los valores (8, 9, 10 y 11).
8
f 5* ( S 5 ) = Min [ R 5 ( D 5 , S 5 + 1 ) + f 5*+ 1 ( S 5 + 1 )]
D14
13
Estado
S5
12
13
3
5
4
Dn ,S n
Donde:
4
6
5
3
4
12
7
10
Función Recursiva
para el Problema
Para n = 5
3
9
6
6
9
9
8
2
f n* ( S n ) = g [ R n ( D n , S n +1 ) + f n*+1 ( S n +1 )]
Utilizando la forma tabular de la PD tenemos, para las diferentes etapas:
8
3
Función Recursiva
General de PD.
5
,S5 +1
DECISIÓN (D5)
14
4
3
f 5* (S5 )
4
3
*
D5 ( S 5 )
14
14
11
1
2
3
4
5
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...
SOLUCIONARIO
Sobre Programación Dinámica
por
“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.”
Ing. Miguel Jiménez Carrión M.Scmjimenezc@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)
S1=6
Región 1
R2 (D2, S3)
S2 = S1 - D1
D1
¿Cuántos agentes
asignar?
Región 2
Eleanor Roosevelt
R3 (D3, S4)
S3 = S2 - D2
D2
¿Cuántos agentes
asignar?
Región 3
S4 = S3 - D3
D3
¿Cuántos agentesasignar?
2004
2
Programación Dinámica.
Ing. Miguel Jiménez C. M.Sc.
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:
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 losmodelos 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. Esta caracterí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 enproblemas 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 es
completamente 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 desolució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 decaminos que los conecta dados los retornos (costos beneficios tiempo, etc),
asociados con los arcos o ramas de la red.
11
2
5
2
1
5
8
11
4
3
6
9
7
f n* ( S n ) = Min [ R n ( D n , S n +1 ) + f n*+ 1 ( S n +1 )]
Rn (Dn , Sn+1 ) =
Representa la distancia por tomar la decisión Dn en la etapa n, para pasar
del estado Sn al estado Sn+1
f n*+1 ( S n +1 ) =Representa el mejor valor en la etapa n+1, cuando el estado es Sn+1
f n* ( S n ) =
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:
(5, 6 y 7) y S3+1
= S4, toma los valores (8, 9, 10 y 11).
8
f 5* ( S 5 ) = Min [ R 5 ( D 5 , S 5 + 1 ) + f 5*+ 1 ( S 5 + 1 )]
D14
13
Estado
S5
12
13
3
5
4
Dn ,S n
Donde:
4
6
5
3
4
12
7
10
Función Recursiva
para el Problema
Para n = 5
3
9
6
6
9
9
8
2
f n* ( S n ) = g [ R n ( D n , S n +1 ) + f n*+1 ( S n +1 )]
Utilizando la forma tabular de la PD tenemos, para las diferentes etapas:
8
3
Función Recursiva
General de PD.
5
,S5 +1
DECISIÓN (D5)
14
4
3
f 5* (S5 )
4
3
*
D5 ( S 5 )
14
14
11
1
2
3
4
5
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...
Leer documento completo
Regístrate para leer el documento completo.