PROGRAMACIÓN DINÁMICA

Investigación

Operativa II

ESCUELA PROFESIONAL:

. INGENIERÍA INDUSTRIAL

. INGENIERÍA DE COMPUTACIÓN Y SISTEMAS

Adolfo Prado

2014

Una compañía sabe que la demanda de su producto durante cada uno de

los próximos cuatro meses es como se indica:

La Compañía debe determinar cuantas unidades tiene que fabricar en el

mes corriente. Durante un mes en el cual se producen algunas unidades, se

incurre en un costo de $3. Además hay un costo variable de $1 por cada

unidad que se fabrica. Al final de cada mes se genera un costo de

almacenamiento de 50 céntimos por cada unidad disponible.

Las limitaciones de capacidad permiten producir durante cada mes un

máximo de 5 unidades. Las dimensiones de la bodega de la compañía

restringen el inventario final de cada mes a 4 unidades como mucho.

La empresa desea determinar un plan de producción que cumpla con toda

la demanda a tiempo y minimice sus costos totales durante los custro

meses. Suponga que se dispone de 0 unidades al principio del primer mes

CASO 6 : INVENTARIO

1 2 3 4

Demanda 1 3 2 4

Etapas

Alternativas

Estado

Función Recursiva

Modelo: Producción Inventario

Sistema de Revisión Periódica

Programación

dinámica

Demanda

Producción

Inventario

Costos Almacenamiento

Costos de Producción

Problema Inventario

¿Que elementos,

conceptos, variables

identificamos?

En el mes 4 (solución trivial último mes)

Producción mes 4 = Demanda mes 4

Producción mes 4=Demanda mes 4- Inventario mes 3

Función de Costo C(x) donde x unidades a producir: C(0) = 0

y C(x) = 3 + x para X>0

Estados {0,1,2,3,4} capacidad de almacenamiento

Demanda del mes

Producción en el mes

Capacidad max de almacenaje

Capacidad max de producción

Inventario

Costos Almacenamiento

Costo Fijos de Producción

Costo Variables de Producción

Etapas

Alternativas

Estado

Función Recursiva

Modelo

Producción

Inventarios

CASO 6 : INVENTARIOS

Solución por Programación Dinámica.

La etapa i representa el tiempo (mes) i : i = 1, 2 , 3, 4

Las alternativas (decisión) en la etapa i es la cantidad de producción en el mes i. Denominemos este valor como xi

El estado si representa la cantidad de producto en inventario al inicio del mes i : { 0,1, 2, 3, 4 }

CASO 6 : INVENTARIOS

Fórmula recursiva

Sea fi(xi) es el costo al producir xi unidades en el mes i y el resto de meses ( i+1, …, n)

[costo etapa actual ]+ costo etapa anteriores

[Costo Producción + Costo Inventario]

fi(xi) = min {[ci(xi) + 0.5 * (si+ xi- di) ] + fi+1(xi+1)} etapa 4,3,2,1

CASO 6 : INVENTARIOS

Fórmula recursiva

Sea fi(xi) es el costo al producir xi unidades en

el mes i y el resto de meses ( i+1, …, n)

fi(xi) = min {[ci(xi) + 0.5 * (si+ xi- di) ] + fi+1(xi+1)}

etapa 4,3,2,1

Restricción

Producción

Capacidad Almacenaje

Inventario es mayor que cero

xi<=5

0<=si<=4

si-xi-di>=0

CASO 6 : INVENTARIOS

Fórmula recursiva

Sea fi(xi) es el costo al producir xi unidades en

el mes i y el resto de meses ( i+1, …, n)

fi(xi) = min {[ci(xi) + 0.5 * (si+ xi- di) ] + fi+1(xi+1)}

etapa 4,3,2,1

fi(xi) = min {[ci(xi) + 0.5 * (si+ xi- di) ] + fi+1(si+ xi- di)}

xi<=5

0<=si<=4

si-xi-di>=0

Vincular resto en función del Estado

y Alternativa actual

CASO 6 : INVENTARIOS

Fórmula recursiva

Sea fi(xi) es el costo al producir xi unidades en el mes i y el resto de meses ( i+1, …, n)

f5(x5) = 0 i=5

f4(x4) = min {c4(x4)} i=4

fi(xi) = min {[ci(xi) + 0.5 * (si+ xi- di) ] + fi+1(si+ xi- di)} i=4,3,2,1

Solución

última etapa

0<=xi<=5

0<=si<=4

si-xi-di>=0

0<= x4<=5

0<=s4<=4

s4-x4-d4=0

X4

f*4(S4) x*4

S4

0 7 4

1 6 3

2 5 2

3 4 1

4 3 0

Etapa 4

Demanda mes 4 = 4 f4(x4) = max {c(x4)} x4=4-s4

Producción = Demanda – Inventario = 4 4 0 C(4) = 3 + 1 * 4=7

Producción = Demanda – Inventario = 3 4 1 C(3) = 3 + 1 * 3=6

Producción = Demanda – Inventario = 2 4 2 C(2) = 3 + 1 * 2=5

Producción = Demanda – Inventario = 0 4 4 C(0) = 0

Producción = Demanda – Inventario = 1 4 3 C(1) = 3 + 1 * 1 = 4

f3(x3)=max{[c3(x3) + 0.5*(s3 +x3 - 2)] + f4(s3 +x3 - 2)}

X3

0 1 2 3 4 5 f*3(S) x*3

S3

0 [5+0]+7=

12 [6+0.5]+6=12.5

[7+1]+5=13

[8+1.5]+4=13.5

12 2

1 [4+0]+7

=11 [5+0.5]+6=11.5

[6+1]+5=12

[7+1.5]+4=12.5

[8+2]+0=10

10 5

2 [0+0]+

7=7 [4+0.5]+6=10.5

[5+1]+5=11

[6+1.5]+4=11.5

[7+2]+0=9

7 0

3 [0+0.5]+6=6.5

[4+1]+5=10

[5+1.5]+4=10.5

[6+2]+0=8

6.5 0

4 [0+1]+

5=6 [4+1.5]+

4=9.5 [5+2]+0=

7 6 0

Etapa 3 (mes 3)

Demanda = 2 unidades

f2(x2)=max{[c2(x2) + 0.5*(s2 +x2 - 3)] + f3(s2 +x2 - 3)}

X2

0 1 2 3 4 5 f*2(S) x*2

S2

0 [6+0]

+12=18 [7+0.5]+10=17.5

[8+1]+7=16

16 5

1 [5+0]+12

=17 [6+0.5]+10=16.5

[7+1]

+7=15

[8+1.5]+6.5=16

15 4

2 [4+0]

+12=16

[5+0.5]+10=15.5

[6+1]

+7=14

[7+1.5]+6.5=15

[8+2]+6=16

14 3

3 [0+0]+12=12

[4+0.5]+10=14.5

[5+1]

+7=13

[6+1.5]+6.5=14

[7+2]+6=15

12 0

4 [0+0.5]+10=10

.5

[4+1]

+7=12

[5+1.5]+6.5=13

[6+2]+6=14

10.5 0

Etapa 2 (mes 2)

Demanda = 3 unidades

Etapa 1 (mes 1)

Demanda = 1 unidades

f1(x1)=max{[c1(x1) + 0.5*(s1 +x1 - 1)] + f2(s1 +x1 - 1)}

X1

0 1 2 3 4 5 f*1(S1) x*1

S1

0 [4+0]+16=20

[5+0.5]+15=20

.5

[6+1]

+14=21

[7+1.5]+12

=20.5

[8+2]+10.5=20.5

20 1

Solución

Para costo total optimo es 20

Solución:

Para el mes 1 (Etapa 1) producción es 1 inventario final

(S2) = 1-1 = 0

Para el mes 2 (Etapa 2) producción es 5 inventario final

(S3) = 5-3 = 2

Para el mes 3 (Etapa 3) producción es 0 inventario final

(S4) = 2-2 = 0

Para el mes 4 (Etapa 4) producción es 4 inventario final

(S5) = 4-4 = 0

Solve and Analyze

Costo Fijo

por Producir

Costo Variable

P: Producción

H: Almacenamiento

B :Backorder

Costo Max

Almacenaje

Cap.Max

Producción

Demanda

Solución

Detallada

Resumen

de la

Solución