programacion dinamica deterministica

Universidad de Chile
Facultad de Ciencias F´
ısicas y Matem´ticas
a
Departamento de Ingenier´ Industrial
ıa

´
IN44A: INVESTIGACION OPERATIVA

Programaci´n Din´mica Determin´
o
a
ıstica

Denis Saur´ V.
e
Julio, 2003.

1

1.

Problemas de Programaci´n Din´mica Determin´stica
o
a
ı

1. Un conejo de pascua tiene N huevos de chocolate para repartir entre los M ni˜os queel conejo superior
n
ha asignado a sus distrito. La felicidad de un ni˜o puede ser modelada como ui (xi ) = ln(xi ) donde xi
n
es la cantidad de huevos que recibe el ni˜o i (si el ni˜o i−´simo no recibe huevos se morir´ de tristeza).
n
n
e
a
Adicionalmente se sabe que los padres de los ni˜os tienen restricciones sobre la cantidad de chocolates
n
que puede comer cada uno de ellos, siendoNimax la cantidad m´xima de huevos que los padres del ni˜o
a
n
i aceptar´n que les traigan. De exceder dicha cantidad, ser´n los padres que se comer´n los huevos.
a
a
a
Formule un modelo de programaci´n din´mica que permita al conejo decidir cu´ntos huevos entregar
o
a
a
a cada ni˜o, de modo de maximizar la felicidad total de los ni˜os del distrito.
n
n
2. (*) La familia Sampsons vaa salir de vacaciones desde su ciudad natal Sprangfield. La familia desea
visitar n ciudades y dispone de un total de M d´ para hacerlo, con M ≥ n. La familia desea saber
ıas
cuantos d´ permanecer en cada ciudad de modo de maximizar la satisfacci´n total de sus vacaciones
ıas
o
sabiendo que para cada ciudad i existe una funci´n de satisfacci´n gi que es funci´n del n´mero de
o
o
o
u
d´de permanencia. Suponga que no se pierde un tiempo considerable en el traslado de una ciudad a
ıas
otra.
a) Plantee un modelo de programaci´n din´mica para resolver la planificaci´n de las vacaciones de
o
a
o
los Sampsons.
b) Suponga que n = 3 y M = 5 y que las funciones de beneficio gk (xk ) vienen dadas por:
xk
xk
xk
xk
xk
xk

=0
=1
=2
=3
=4
=5

g1 (x1 )
0
1
2
3
4
5g2 (x2 )
0
1
4
6
8
8

g3 (x3 )
0
1
3
3
2
1

3. Considere el siguiente problema de programaci´n no lineal y utilice programaci´n din´mica para reo
o
a
solverlo:
3
3
2
m´x Z = 36 · X1 + 9 · X1 − 6 · X1 + 36 · X2 − 3 · X2
a

s.a.
X1 + X2 ≤ 3,

X1 ∧ X2 ≥ 0

4. (*) El gerente de sistemas de una compa˜´ desea aumentar la confiabilidad de la computadora que
nıa
maneja losdatos de ventas de la empresa. Para que esta computadora funcione, deben trabajar correctamente cada uno de sus N subsistemas. Para aumentar la confiabilidad de la computadora se pueden
agregar unidades de reserva a cada una de estos subsistemas, lo que modifica sus probabilidades de
falla.
Agregar una unidad de reserva al subsitema i-´simo cuesta Ci . La probabilidad que cada subsistema
efuncione correctamente es conocida e igual a Pi (n), donde n es el n´mero de unidades de reserva que
u
tenga el subsistema i (i=1 . . . N).
a) Plantee un modelo de programaci´n din´mica que permita encontrar la configuraci´n de unidades
o
a
o
de reserva que maximiza la probabilidad que la computadora funcione correctamente si Ud.
dispone de X pesos.

2
b) Considere que N = 3 (tressubsistemas), C1 = $100, C2 = $300, C3 = $200, y las probabilidades
Pi (n) de la tabla, donde, por ejemplo, P2 (2) = 0, 95 es la probabilidad que el subsistema 2
funcione correctamente con 2 unidades de reserva. Usando programaci´n din´mica encuentre la
o
a
configuraci´n de unidades de reserva que maximiza la probabilidad que la computadora funcione
o
correctamente si Ud. dispone de $600.
Unidadesde reserva
0
1
2

sub
sistema 1
0,85
0,90
0,95

sub
sistema 2
0,60
0,85
0,95

sub
sistema 3
0,70
0,90
0,98

5. Durante el mes t (t=1,...,T) una botiller´ se enfrenta a una demanda de dt unidades de su producto
ıa
artesanal “Pistol-Cola”. El costo de los insumos para producir tan singular brebaje durante el mes t
tiene dos componentes: Primero, se incurre en un costo de...