Aplicaciones De La ProgramaciOn DinAmica

Aplicaciones de la programacion
dinamica
3.1. Problemas de Inventario
Ejemplo 3.1. Supongase que una empresa sabe que la demanda de un determinado
producto durante cada uno de los proximos cuatro meses va a ser: mes 1, 1 unidad;
mes 2, 3 unidades; mes 3, 2 unidades; mes4, 4 unidades. Al principio de cada mes la
empresa debe determinar cuantas unidades deben de producirse durante dichomes.
Cada mes en el que se produce al menos una unidad la empresa incurre en un costo
inicial de 3$, mas 1$ por cada unidad producida. Al nal de cada mes cada unidad en
inventario (producidas y no vendidas) ocasiona un costo de 0.5$. La empresa tiene la
siguientes restricciones a la hora de planicar la produccion:
- La limitacion de maquinaria provoca que no se pueden producir mas de 5unidades
del producto por mes.
- La limitacion de capacidad del almacen restringe el inventario nal de cada mes a un
31
32 Tema 3. Aplicaciones de la programacion dinamica
maximo de 4 unidades
La empresa desea determinar un calendario de produccion para cada mes que cumpla
a tiempo con las demandas y que reduzca al mnimo la suma de costes de produccion y
almacenamiento durante loscuatro meses. Se supone que no hay unidades en inventario
al principio del primer mes.
Indicaciones
Se puede plantear el problema como un problema de programacion dinamica, donde
cada etapa representa un mes. En cada etapa la variable estado indicara el numero de
unidades en inventario al principio del correspondiente mes. De esta forma, el espacio
de de estados  sera f0; 1; 2; 3; 4g.Utilizando la idea del algoritmo "Backward", en cada etapa se representa por f i (E)
como el costo mnimo de satisfacer las demandas para los meses i; i + 1; :::; 4, si al
principio del mes i hay E unidades en inventario. As, para el ultimo mes, como la
demanda debe ser totalmente satisfecha, habra que resolver, para cada posible valor
de E, el siguiente problema:
f 4 (E) = Min c(x4)s.a
x4 + E = 4
x4 2 f0; 1; 2; 3; 4; 5g
donde
c(x) =
8><
>:
0 si x = 0
3 + x si x > 0
Supongase que E son las unidades en inventario al inicio del tercer mes. Como la
empresa debe satisfacer para ese mes una demanda de dos unidades, se deben producir
x unidades de forma que E + x  2. Esto produce un coste para la empresa de c(x)
3.2. Camino mas corto en un grafo 33
$. Al nal delesta etapa habra en inventario E + x 2 unidades, lo que producira un
gasto para la empresa de (0;5)(E +x2)$ en concepto de inventario, mas un gasto de
f 4 (E + x 2) $ que es el coste mnimo para el ultimo mes cuando este comienza con
E + x 2 unidades en inventario. Por tanto, en esta etapa habra que resolver, para
cada valor de E el siguiente problema:
f 3 (E) = Min (
1
2
)(E +x3 2) + c(x3) + f 4 (E + x 2)
s.a
x3 + E  2
x3 2 f0; 1; 2; 3; 4; 5g
Aplicando la misma idea se obtienen el resto de las etapas. La solucion optima del
problema consiste en producir una unidad durante el mes 1, 5 unidades durante el mes
2, 0 unidades durante el mes 3 y 4 unidades durante el mes 4, incurriendo todo ello en
un costo total de 20$.
3.2. Camino mas corto en un grafoConsideramos un grafo dirigido G = (X;A), donce X es el conjunto de vertices
(kXk = M) y A es el conjunto de arcos (kAk = N). Con cada arco a = (i; j) viene
asociada una distancia l(a) = l(i; j). El problema consiste en encontrar el camino mas
corto entre un vertice inicial dado 0 y un subconjunto de vertices terminales T  X
(T podra ser un unico vertice).
Ejemplo 3.2. El problema delcomerciante. Supongase que un comerciante de
Madrid desea viajar a Praga realizando el viaje en tres etapas. En la primera tiene
oportunidad de hospedarse en Maresella, Pars o Limoges; en la segunda lo hara en
34 Tema 3. Aplicaciones de la programacion dinamica
Zurich, Munich o Milan, para desde ah trasladarse directamente a Praga. El comerciante
desea saber donde debe hospedarse...