programacion dinamica

Pontificia Universidad Católica
Escuela de Ingeniería
Departamento de Ingeniería Industrial y de Sistemas

Clase 30 • Programaci´n Din´mica
o
a
ICS 1102 • Optimizaci´n
o
Profesor : Claudio Seebach
20 de noviembre de 2006

Apuntes de Clases • Optimizaci´n • Claudio Seebach
o

Programaci´n Din´mica • 2
o
a

Programaci´n Din´mica
o
a
• Transforma un problema de optimizaci´ncomplejo en una secuencia de
o
problemas m´s simples
a
• Generalmente se comienza con el final y se trabaja hacia atr´s
a
• Es aplicable a un rango muy amplio de problemas

• Est´ basado en la recursi´n y en el principio de optimalidad
a
o
• Fue desarrollado por Richard Bellman en 1953

Apuntes de Clases • Optimizaci´n • Claudio Seebach
o

Programaci´n Din´mica • 3
o
a

El juegode los f´sforos
o
• Supongamos que hay 30 f´sforos en una mesa.
o

• Yo comienzo eligiendo 1, 2 o 3 f´sforos. Luego mi contrincante debe
o
elegir 1, 2 o 3 f´sforos. Se sigue de esta forma hasta que alguien saca el
o
ultimo f´sforo. El jugador que toma el ultimo f´sforo pierde el juego.
´
o
´
o
• ¿como puedo yo (el primer jugador) asegurarme de ganar el juego ? ¿se
podr´ ?
aApuntes de Clases • Optimizaci´n • Claudio Seebach
o

Programaci´n Din´mica • 4
o
a

El juego de los f´sforos
o
• Yo gano si le dejo un f´sforo en la mesa a mi contrincante
o

• Retrocediendo un paso, yo gano si me toca jugar y quedan 2, 3 o 4
f´sforos en la mesa
o
• Retrocediendo otro paso, yo gano si dejo 5 f´sforos a mi contrincante
o

• Retrocediendo otro paso, yo gano si me tocajugar y quedan 6, 7 u 8,
para dejarle 5 a mi contrincante.
• Retrocediendo otro paso, yo gano si dejo 9 f´sforos a mi contrincante
o

• Conclusi´n: Yo gano si dejo 1, 5, 9, . . . , 4n + 1 f´sforos en la mesa al
o
o
jugar.
• Si hay 30 f´sforos, y juego yo, basta sacar uno y dejarle 29 (4 · 7 + 1)
o
f´sforos para ganar
o

Apuntes de Clases • Optimizaci´n • Claudio Seebach
oProgramaci´n Din´mica • 5
o
a

El problema de la diligencia

Apuntes de Clases • Optimizaci´n • Claudio Seebach
o

Programaci´n Din´mica • 6
o
a

El problema de la diligencia

• Observaci´n: Escoger siempre el arco m´s barato no es necesariamente
o
a
lo mejor:
A→B→F →I→J
A→D→F →?
• ¿c´mo modelar el problema con las metodolog´ ya vistas ?
o
ıas
Apuntes de Clases • Optimizaci´n •Claudio Seebach
o

Programaci´n Din´mica • 7
o
a

El problema de la diligencia
• Si estamos en H la decisi´n es obvia (y unica)
o
´
• Si estamos en F :

cF,H + cH,J o cF,I + cI,J
• o bien:
cF,H + costo ´ptimo de H a J o cF,I + costo ´ptimo de I a J
o
o

Apuntes de Clases • Optimizaci´n • Claudio Seebach
o

Programaci´n Din´mica • 8
o
a

El problema de la diligencia
• Enel problema hay 4 decisiones que tomar para las etapas: 1, 2, 3 ,4

• En cada etapa estaremos en un estado posible y deberemos tomar una
decisi´n
o
• Sea:
vn(s) = el costo m´
ınimo para las etapas n, n + 1, . . . , N
si en la etapa n estamos en el estado s
• Supongamos que d representa el siguiente destino escogido.
• Sea c(s, d) el costo asociado al arco s → d.
• Entonces:

vn(s) =min {c(s, d) + vn+1(d)}

d factibles

• Esta es la recursi´n b´sica de programaci´n din´mica.
o a
o
a

• Se resuelve de atr´s hacia adelante. Condici´n de borde: v5(J) = 0.
a
o
Apuntes de Clases • Optimizaci´n • Claudio Seebach
o

Programaci´n Din´mica • 9
o
a

Ejemplo asignaci´n de recursos a proyectos
o
• Hay 3 proyectos en los cuales invertir.

• Si invierto xi pesos(en millones) en el proyecto i, recibo un Valor Presente Neto (VPN) de ri(xi):
r1(x1)
r2(x2)
r3(x3)
r1(0)

=
=
=
=

7x1 + 2
x1 > 0
3x2 + 7
x2 > 0
4x3 + 5
x3 > 0
r2(0) = r3(0) = 0

• El monto invertido en cada proyecto debe ser un m´ltiplo entero de 1
u
mill´n.
o
• Se tiene en la actualidad un presupuesto de $ 6 millones (6 unidades de
un mill´n), ¿cu´nto y c´mo debo...