Ejercicios De Investigacion Op. 2 Prog. Deterministica

Universidad de Chile
Facultad de Ciencias F´ısicas y Matem´aticas
Departamento de Ingenier´ıa Industrial
IN44A: INVESTIGACI ´ON OPERATIVA
Programaci´on Din´amica Determin´ıstica
Denis Saur¶e V.
Julio, 2003.
1
1. Problemas de Programaci¶on Din¶amica Determin¶³stica
1. Un conejo de pascua tiene N huevos de chocolate para repartir entre los M ni˜nos que el conejo superior
ha asignado a susdistrito. La felicidad de un ni˜no puede ser modelada como ui(xi) = ln(xi) donde xi
es la cantidad de huevos que recibe el ni˜no i (si el ni˜no i¡´esimo no recibe huevos se morir´a de tristeza).
Adicionalmente se sabe que los padres de los ni˜nos tienen restricciones sobre la cantidad de chocolates
que puede comer cada uno de ellos, siendo Nmax
i la cantidad m´axima de huevos que los padresdel ni˜no
i aceptar´an que les traigan. De exceder dicha cantidad, ser´an los padres que se comer´an los huevos.
Formule un modelo de programaci´on din´amica que permita al conejo decidir cu´antos huevos entregar
a cada ni˜no, de modo de maximizar la felicidad total de los ni˜nos del distrito.
2. (*) La familia Sampsons va a salir de vacaciones desde su ciudad natal Sprangfield. La familiadesea
visitar n ciudades y dispone de un total de M d´ıas para hacerlo, con M ¸ n. La familia desea saber
cuantos d´ıas permanecer en cada ciudad de modo de maximizar la satisfacci´on total de sus vacaciones
sabiendo que para cada ciudad i existe una funci´on de satisfacci´on gi que es funci´on del n´umero de
d´ıas de permanencia. Suponga que no se pierde un tiempo considerable en el traslado deuna ciudad a
otra.
a) Plantee un modelo de programaci´on din´amica para resolver la planificaci´on de las vacaciones de
los Sampsons.
b) Suponga que n = 3 y M = 5 y que las funciones de beneficio gk(xk) vienen dadas por:
g1(x1) g2(x2) g3(x3)
xk = 0 0 0 0
xk = 1 1 1 1
xk = 2 2 4 3
xk = 3 3 6 3
xk = 4 4 8 2
xk = 5 5 8 1
3. Considere el siguiente problema de programaci´on no lineal yutilice programaci´on din´amica para resolverlo:
m´axZ = 36 ¢ X1 + 9 ¢ X2
1 ¡ 6 ¢ X3
1 + 36 ¢ X2 ¡ 3 ¢ X3
2
s.a.
X1 + X2 · 3, X1 ^ X2 ¸ 0
4. (*) El gerente de sistemas de una compa˜n´ıa desea aumentar la confiabilidad de la computadora que
maneja los datos de ventas de la empresa. Para que esta computadora funcione, deben trabajar correctamente
cada uno de sus N subsistemas. Para aumentar laconfiabilidad 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-´esimo cuesta Ci. La probabilidad que cada subsistema
funcione correctamente es conocida e igual a Pi(n), donde n es el n´umero de unidades de reserva que
tenga el subsistema i (i=1 . . . N).
a) Planteeun modelo de programaci´on din´amica que permita encontrar la configuraci´on de unidades
de reserva que maximiza la probabilidad que la computadora funcione correctamente si Ud.
dispone de X pesos.
2
b) Considere que N = 3 (tres subsistemas), 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 2funcione correctamente con 2 unidades de reserva. Usando programaci´on din´amica encuentre la
configuraci´on de unidades de reserva que maximiza la probabilidad que la computadora funcione
correctamente si Ud. dispone de $600.
Unidades sub sub sub
de reserva sistema 1 sistema 2 sistema 3
0 0,85 0,60 0,70
1 0,90 0,85 0,90
2 0,95 0,95 0,98
5. Durante el mes t (t=1,...,T) una botiller´ıa seenfrenta a una demanda de dt unidades de su producto
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 ct(x) si se producen x unidades en el mes t.
Segundo, si el nivel de producci´on de la empresa durante el mes t ¡ 1 es xt¡1 y el nivel de producci´on
durante el mes t es xt, entonces se...