INVESTIGACIÓN OPERATIVA II

PROGRAMACIÓN DINÁMICA
Xi = Variable de decisión de la etapa i
Yi = Variable de estado al comienzo de la etapa i
Yi+1 = Variable de estado al final de la etapa i
ti = Regla de transformación de la etapa i Yi+1 = ti(Xi,Yi)
fi = Función de retorno de la etapa i
Fi = Función recursiva de la etapa i Fi = optXi { fi(Xi,Yi) o Fi+1(Yi+1)}

El objetivo del problema de programación dinámica es encontrar los valores de X 1,X2, .. , Xn que
optimizan el retorno global.

Este retorno global Z, es casi siempre la suma de los retornos de cada etapa, a veces es el producto de
ellos, y en general, es una composición de los retornos de cada etapa.
Es decir, en general: Z = f1 o f2 o … o fn

Las composiciones por etapas serán:

Fn = fn
Fn-1 = fn o Fn
Fn-2 = fn-2 o Fn-1 Xi
…….
F2 = f2 o F3 Yi i Yi+1
F1 = f1 o F2

Xi ,Xi+1 ,Xi+2,…Xn-1,Xn fi(Xi,Yi)

Yi ian Yn+1

Fi= fi o fi+1 o…o fn-1 o fn

Se puede descomponer en:

Xi+1 ,Xi+2,…Xn-1,Xn
Xi

Yi Yi+1 Yn+1
i+1 a n
i

fi Fi+1= fi+1 o…o fn-1 o fn

Se deben tomar las decisiones Xi+1 ,Xi+2,…Xn-1,Xn en forma óptima, para luego decidir Xi.
Esto permite calcular Yi+1 = ti(Xi,Yi) o también Yi = t’i(Xi,Yi+1)
y solo quedarían por decidir Xi ,X2,…Xi-2,Xi-1.

Principio de Optimalidad:
Una vez que se ha llegado a cierto estado, la política óptima para las siguientes etapas no depende del
camino que se haya elegido para llegar a ese estado, no dependen del pasado. Las decisiones restantes
constituyen una política óptima para ir, desde ese estado hasta el final, hacia adelante.
Los pasos a seguir son los siguientes:
Fn(Yn)= optXn { fn(Xn,Yn)} con Yn+1 = tn(Xn,Yn)
Luego se hace, recursivamente, para i, desde n hasta 1:
Fi= optXi { fi(Xi,Yi) o Fi+1(Yi+1)} con Yi+1 = ti(Xi,Yi).

Prof. Miguel Sierra pag. 1/5

 INVESTIGACIÓN OPERATIVA II

Problema No. 1
Asignación de recursos
Un inversionista tiene $6000 para invertir en 3 alternativas. La inversión se hace en miles de dólares enteros.
Determine la estrategia óptima de inversión, si el rendimiento de las alternativas depende de la cantidad
invertida, según la siguiente tabla:

Cantidad
Invertida A B C
(miles de $)
0 0.0 0.0 0.0
1 1.6 1.3 1.3
2 1.8 1.9 2.4
3 3 2.8 2.5
4 4 2.9 2.7
5 4.3 3.7 3.1
6 4.6 3.8 3.7
Solución:
Variables de decisión Xi : miles de dólares que se invierte en la alternativa i
i= 1, 2, 3 ( i=1=A, i=2=B, i=3=C)
Variables de estado Yi : miles de dólares disponibles antes de invertir en la alternativa i
Condiciones:
Y1 = 6 (También se incluye la condición Y4 = 0, ya que se invertirá todo, aunque a veces se debe
considerar la posibilidad de Y4>=0, es decir, que puede haber dinero sobrante)
Se define:
Y3= Y4 +X3 → Y4=Y3-X3 → asegurar que Y4 = 0 o Y4 ≥ 0
Y2= Y3+X2 → Y3=Y2-X2 → asegurar que Y3>=0
Y1= Y2+X1 → Y2= 6-X1 → asegurar que Y2>=0
X1 X2 X3

Y1 1 Y2 2 Y3 3 Y4

f1(X1,Y1) f2(X2,Y2) F3(X3,Y3)

Funciones de retorno:
fi(Xi, Yi) : Ganancia obtenida luego de invertir en la alternativa i, Xi miles de dólares, cuando se tenía
disponible Yi miles de dólares
Funciones recursivas:
F3(Y3)= max (f3(X3,Y3))
Fi (Yi) = max{ fi(Xi,Yi) + Fi+1(Yi+1) } i= 1, 2

Cálculos:
Etapa 3: Y3= Y4 +X3 Y4=Y3-X3 como Y4=0, entonces: Y3 = X3
X3
Y3 F3(Y3) X3 max
0 1 2 3 4 5 6
0 0.0 - - - - - - 0.0 0
1 - 1.3 - - - - - 1.3 1
2 - - 2.4 - - - - 2.4 2
3 - - - 2.5 - - - 2.5 3
4 - - - - 2.7 - - 2.7 4
5 - - - - - 3.1 - 3.1 5
6 - - - - - - 3.7 3.7 6

Continuar hasta obtener la solución e interpretarla.

Prof. Miguel Sierra pag. 2/5

 INVESTIGACIÓN OPERATIVA II

Problema No. 2
El problema de la mochila
Determine la cantidad de cada uno de los artículos Artículo Descripción Peso en kg Valor ($)
que deben incluirse en el cargamento de una
camioneta para servicio rural con capacidad para 1 tanque de aceite 200 300
1500 kg, tal que el valor del cargamento se 2 fardo de azúcar 300 500
maximice. 3 fardo de maíz 400 700
Solución: 4 fardo de frijoles 500 800
Variables de decisión Xi : cantidad de artículo i que se transportará en la camioneta, en Kg
i= 1, 2, 3, 4 ( i=1=aceite, i=2=azúcar, i=3=maíz, i=4=frijoles)
Variables de estado Yi : capacidad disponible en kg antes de asignarse el artículo i al cargamento
X1 X2 X3 X4

Y1 1 Y2 2 Y3 3 Y4 4 Y5

f1(X1,Y1) f2(X2,Y2) f3(X3,Y3) F4(X4,Y4)

Condiciones:
Y1 = 1500
Se define:
Y4= Y5 +X4 → Y5=Y4-X4 → asegurar que Y5>=0
Y3= Y4 +X3 → Y4=Y3-X3 → asegurar que Y4>=0
Y2= Y3+X2 → Y3=Y2-X2 → asegurar que Y3>=0
Y1= Y2+X1 → Y2=1500-X1 → asegurar que Y2>=0
Funciones de retorno:
fi(Xi, Yi) : Valor del cargamento luego de asignar el artículo tipo i, cuando se tenía
disponible Yi kilogramos en la camioneta
Funciones recursivas:
F4(Y4)= max (f4(X4,Y4))
Fi(Yi) = max{ fi(Xi,Yi) + Fi+1(Yi+1) } i= 1, 2, 3

Problema No. 3
Reemplazo de equipos
Un taller de motores debe tener siempre disponible un equipo analizador de motor. Un equipo analizador
nuevo cuesta $1000. El costo de mantenimiento se muestra en la tabla. El analizador se puede tener durante
1, 2 o 3 años. Después de usarlo i años (i=1, 2, 3) se puede vender para comprar uno nuevo. Por el equipo
usado se obtiene un Valor de Salvamento.
Considerando que hoy se tiene un equipo nuevo, se desea determinar la política de reemplazo o reposición
con el fin de minimizar los costos durante los siguientes 5 años:
(Costo de mantenimiento+ Costo de reposición – Valor de Salvamento o Rescate)
Asumir que se comprará un equipo al final del año 5. (X5=1)
Yi Año de Valor de Costo de
funcionamiento Salvamento $ mantenimiento $
0 1 800 80
1 2 700 100
2 3 500 120
X5=1
X1

X2

X3

X4

Y1=0 1 Y2 2 Y3 3 Y4 4 Y5 5 Y6=0

Prof. Miguel Sierra pag. 3/5

 INVESTIGACIÓN OPERATIVA II

Solución:
Variables de decisión Xi : decisión de reemplazar o no el equipo, al final del año i
i= 1, 2, 3, 4, 5 (Xi : 0 = no se reemplaza; 1= si se reemplaza)
Variables de estado Yi : edad del equipo a inicios del año i. Su reemplazo se decide al final del año i
i= 1, 2, 3, 4, 5 (Yi : 0, 1, 2)
Condiciones:
X0 = 1, por lo tanto: Y1=0 X5 = 1
Se define:
Yi+1=Yi +1 cuando Xi=0
Yi+1= 0 cuando Xi=1
Funciones de retorno:
fi(Xi, Yi) : Costo generado durante el año i, consecuencia de Xi y de la edad previa del equipo Yi
fi(Xi, Yi) = Costo de mantenimiento (Yi), si Xi=0
fi(Xi, Yi) = Costo de mantenimiento(Yi) + Costo de equipo – Valor de Salvamento(Yi), si Xi=1
Costo de equipo = 1000
Costo de mantenimiento(Yi). Yi=0 → 80; Yi=1 → 100; Yi=2 → 120
Valor de salvamento(Yi). Yi=0 → 800; Yi=1 → 700; Yi=2 → 500
Funciones recursivas:
F5(Y5)= min (f5(X5,Y5)) Fi(Yi) = min{ fi(Xi,Yi) + Fi+1(Yi+1) } i= 1, 2, 3, 4

Problema No. 4
El problema de programación de producción e inventarios
En general se puede resolver con P.D. problemas con las siguientes características:
➢ Se descompone en N períodos: 1, 2, .., N
➢ Se conoce la demanda en cada período, la cual se debe satisfacer con inventario y/o producción
➢ Por cada período se debe determinar cuánto se debe producir
➢ La capacidad de producción en cada período es limitada
➢ Puede haber costos de producción fijos y variables.
➢ Hay capacidades limitadas de almacenamiento. Esto se refleja limitando el inventario final de
cada período
➢ Si al final de un período se tiene inventario, se incurre en un costo unitario de almacenamiento
➢ Los niveles de inventario del período inicial y final son conocidos
➢ El objetivo es minimizar el costo total de satisfacer a tiempo la demanda de los N períodos

Caso: La demanda y los costos de producción de unos Demanda Costo de

dispositivos eléctricos se han estimado para los próximos 4 Mes (cientos de producción (por
meses, según la tabla. El costo de almacenamiento es $1 por unidades) ciento de unidades)
el ciento de unidades/mes. La producción se realiza en lotes 1 2 25
de 100 unidades y la capacidad máxima mensual es 500 2 4 30
unidades. El inventario inicial es 0 y se desea lo mismo al 3 6 35
final del 4to. mes. 4 3 30
La capacidad mensual de almacenamiento es 300 unidades.
Determine el plan óptimo de producción que minimice los costos totales para los próximos 4 meses.

Variables de decisión:
Xi : cantidad en cientos de dispositivos eléctricos producidos el mes i ( i= 1, 2, 3, 4)

Variables de estado:
Yi : nivel del inventario en cientos de máquinas eléctricas al inicio del mes i ( i= 1, 2, 3, 4, 5)
X1 d1 X2 d2 X3 d3 X4 d4

Y1 1 Y2 2 Y3 3 Y4 4 Y5

f1(X1,Y1) f2(X2,Y2) f3(X3,Y3) F4(X4,Y4)

Prof. Miguel Sierra pag. 4/5

 INVESTIGACIÓN OPERATIVA II

Parámetros:
di: demanda de cientos de máquinas durante el mes i ( i= 1, 2, 3, 4)
Condiciones:
Y1=Y5=0
Suposición importante: Se produce y se satisface la demanda el primer día de cada mes. Los productos
sobrantes pasan al inventario de inicios del mes siguiente.
Se define para cada período: Inventario final = Inventario inicial + Producción - Demanda
Yi+1 = Yi + Xi –di ≥ 0
Y5 = 0 = Y4 + X4 – d4 → 0 = Y4 + X4 – 3 → Y4 + X4 = 3
Y4= Y3 + X3 – 6 → asegurar que Y4>=0
Y3= Y2 + X2 – 4 → asegurar que Y3>=0
Y2= Y1 + X1 – 2 → asegurar que Y2>=0
Funciones de retorno:
fi(Xi, Yi) : Costos de producción + Costos de almacenamiento
fi(Xi, Yi) = Cpi (Xi) + Cai (Yi+1)
fi(Xi, Yi) = Cpi (Xi) + 1*(Yi+1)
Funciones recursivas:
F4(Y4)= min (30X4)
Fi(Yi) = min{ fi(Xi,Yi) + Fi+1(Yi+1) } (i= 3, 2, 1)
Rangos: Xi= 0, 1, 2, 3, 4, 5 Yi= 0, 1, 2, 3

Prof. Miguel Sierra pag. 5/5