Prdt3

Tema 3
Aplicaciones de la programaci´
on
din´
amica

3.1.

Problemas de Inventario

Ejemplo 3.1. Sup´ongase que una empresa sabe que la demanda de un determinado
producto durante cada uno de los pr´oximos 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 durantedicho mes.
Cada mes en el que se produce al menos una unidad la empresa incurre en un costo
inicial de 3$, m´as 1$ por cada unidad producida. Al final 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 planificar la producci´on:
- La limitaci´on de maquinaria provoca que no se pueden producir m´as de5 unidades
del producto por mes.
- La limitaci´on de capacidad del almac´en restringe el inventario final de cada mes a un

31

32

Tema 3. Aplicaciones de la programaci´on din´amica

m´aximo de 4 unidades
La empresa desea determinar un calendario de producci´on para cada mes que cumpla
a tiempo con las demandas y que reduzca al m´ınimo la suma de costes de producci´on y
almacenamiento durantelos cuatro meses. Se supone que no hay unidades en inventario
al principio del primer mes.
Indicaciones
Se puede plantear el problema como un problema de programaci´on din´amica, donde
cada etapa representa un mes. En cada etapa la variable estado indicar´a el n´
umero de
unidades en inventario al principio del correspondiente mes. De esta forma, el espacio
de de estados ξ ser´a {0, 1, 2, 3, 4}.Utilizando la idea del algoritmo ”Backward”, en cada etapa se representa por fi∗ (E)
como el costo m´ınimo 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 u
´ltimo mes, como la
demanda debe ser totalmente satisfecha, habr´a que resolver, para cada posible valor
de E, el siguiente problema:
f4∗ (E) = Min c(x4 )
s.a
x4 +E = 4
x4 ∈ {0, 1, 2, 3, 4, 5}

donde
c(x) =



0

si x = 0


3 + x

si x > 0

Sup´ongase 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 m´
as corto en un grafo

33

$. Al final del esta etapahabr´a en inventario E + x − 2 unidades, lo que producir´a un
gasto para la empresa de (0,5)(E + x − 2)$ en concepto de inventario, m´as un gasto de
f4∗ (E + x − 2) $ que es el coste m´ınimo para el u
´ltimo mes cuando este comienza con
E + x − 2 unidades en inventario. Por tanto, en esta etapa habr´a que resolver, para
cada valor de E el siguiente problema:
1
f3∗ (E) = Min ( )(E + x3 − 2) + c(x3) + f4∗ (E + x − 2)
2
s.a
x3 + E ≥ 2
x3 ∈ {0, 1, 2, 3, 4, 5}

Aplicando la misma idea se obtienen el resto de las etapas. La soluci´on ´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 m´
as corto en un grafo

Consideramos ungrafo dirigido G = (X, A), donce X es el conjunto de v´ertices
( X = M ) y A es el conjunto de arcos ( A = N ). Con cada arco a = (i, j) viene
asociada una distancia l(a) = l(i, j). El problema consiste en encontrar el camino m´as
corto entre un v´ertice inicial dado 0 y un subconjunto de v´ertices terminales T ⊂ X
(T podr´ıa ser un u
´nico v´ertice).
Ejemplo 3.2. El problema del comerciante.Sup´ongase que un comerciante de
Madrid desea viajar a Praga realizando el viaje en tres etapas. En la primera tiene
oportunidad de hospedarse en Maresella, Par´ıs o Limoges; en la segunda lo har´a en

34

Tema 3. Aplicaciones de la programaci´on din´amica

Z´
urich, M´
unich o Mil´an, para desde ah´ı trasladarse directamente a Praga. El comerciante desea saber donde debe hospedarse en cada etapa para...