pert

Tema 3
Aplicaciones de la programaci´n
o
din´mica
a

3.1.

Problemas de Inventario

Ejemplo 3.1. Sup´ngase que una empresa sabe que la demanda de un determinado
o
producto durante cada uno de los pr´ximos cuatro meses va a ser: mes 1, 1 unidad;
o
mes 2, 3 unidades; mes 3, 2 unidades; mes4, 4 unidades. Al principio de cada mes la
empresa debe determinar cuantas unidades deben deproducirse durante dicho mes.
Cada mes en el que se produce al menos una unidad la empresa incurre en un costo
inicial de 3$, m´s 1$ por cada unidad producida. Al final de cada mes cada unidad en
a
inventario (producidas y no vendidas) ocasiona un costo de 0.5$. La empresa tiene la
siguientes restricciones a la hora de planificar la producci´n:
o
- La limitaci´n de maquinaria provoca que no sepueden producir m´s de 5 unidades
o
a
del producto por mes.
- La limitaci´n de capacidad del almac´n restringe el inventario final de cada mes a un
o
e

31

32

Tema 3. Aplicaciones de la programaci´n din´mica
o
a

m´ximo de 4 unidades
a
La empresa desea determinar un calendario de producci´n para cada mes que cumpla
o
a tiempo con las demandas y que reduzca al m´
ınimo la sumade costes de producci´n y
o
almacenamiento durante los 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´n din´mica, donde
o
a
cada etapa representa un mes. En cada etapa la variable estado indicar´ el n´mero de
a
u
unidades en inventario al principio del correspondiente mes.De esta forma, el espacio
de de estados ξ ser´ {0, 1, 2, 3, 4}.
a
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 ultimo mes, como la
ı,
´
demanda debe ser totalmente satisfecha, habr´ que resolver, paracada posible valor
a
de E, el siguiente problema:
∗
f4 (E) = Min c(x4 )

s.a
x4 + E = 4
x4 ∈ {0, 1, 2, 3, 4, 5}

donde

si x = 0


3 + x

c(x) =



0

si x > 0

Sup´ngase que E son las unidades en inventario al inicio del tercer mes. Como la
o
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´s corto en un grafo
a

33

$. Al final del esta etapa habr´ en inventario E + x − 2 unidades, lo que producir´ un
a
a
gasto para la empresa de (0,5)(E + x − 2)$ en concepto de inventario, m´s un gasto de
a
∗
f4 (E + x − 2) $ que es el coste m´
ınimo para el ultimo mes cuando este comienza con
´

E + x − 2 unidades eninventario. Por tanto, en esta etapa habr´ que resolver, para
a
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´n ´ptima del
o o
problema consiste en producir una unidad durante el mes 1, 5 unidades durante el mes
2, 0 unidadesdurante el mes 3 y 4 unidades durante el mes 4, incurriendo todo ello en
un costo total de 20$.

3.2.

Camino m´s corto en un grafo
a

Consideramos un grafo dirigido G = (X, A), donce X es el conjunto de v´rtices
e
( 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´s
acorto entre un v´rtice inicial dado 0 y un subconjunto de v´rtices terminales T ⊂ X
e
e
(T podr´ ser un unico v´rtice).
ıa
´
e
Ejemplo 3.2. El problema del comerciante. Sup´ngase que un comerciante de
o
Madrid desea viajar a Praga realizando el viaje en tres etapas. En la primera tiene
oportunidad de hospedarse en Maresella, Par´ o Limoges; en la segunda lo har´ en
ıs
a

34

Tema...