Aplicaciones de la programacion dinamica
Enviado por francoxa123 • 12 de Junio de 2013 • 399 Palabras (2 Páginas) • 333 Visitas
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
...