Aplicaciones de la programacion dinamica

Tema 3

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 dicho mes.

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 5 unidades

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 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 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 del esta etapa habra en inventario E + x

...