• Author / Uploaded
• Alexander

Citation preview

INVESTIGACION DE OPERACIONES II

PROGRAMACION DINAMICA DETERMINISTICA CASOS ESPECIALES: MODELO DE LA MOCHILA / MODELO DE INVENTARIO Instrucciones:



Resolver los siguientes problemas considerando el uso de la recursividad en la programación dinámica.

PROBLEMA 1 (Volumen de carga) Solución:

Artículo n 1 2 3

Etapa: Cada tipo de artículo representa a una etapa. Estado: La disponibilidad respecto a la capacidad del barco. Decisión: Cuántas unidades de cada tipo de artículo llevar Función recursiva: Representa el total de ingreso que se quiere maximizar.

Peso pn 2 3 1

Ingreso in 31 47 14

s3=0; significa que el barco está lleno, disponibilidad cero. s3=4; significa que el barco está vacío, disponibilidad 4 ton.

s3 0 1 2 4

x3 =0 14(0)=0 -

s2 0 2 4

s1 4

Etapa 3 (Artículo 3) f3(s3,x3)=14x3 x3 =1 x3 =2 x3 =3 x3 =4 14(1)=14 14(2)=28 14(4)=56

Solución óptima f3*(s3) x3* 0 0 14 1 28 2 56 4

Etapa 2 (Artículo 2) f2(s2,x2)=47x2 + f3*(s2-3x2) Solución óptima x2 =0 x2 =1 f2*(s2) x2* 47(0)+0=0 0 0 47(0)+28=28 28 0 47(0)+56=56 47(1)+14=61 61 1

Etapa 1 (Artículo 1) f1(s1,x1)=31x1 + f2*(s1-2x1) x1 =0 x1 =1 x1 =2 31(0)+61=61 31(1)+28=59 31(2)+0=62

Solución óptima f1*(s1) x1* 62 2

Para obtener la solución óptima, se observa que el máximo ingreso generado en la etapa 1, es decir $62 mil, se produce cuando se decide llevar 2 unidades del artículo 1. Con esto se ha ocupado toda la capacidad de carga. Ingreso total=62; llevar 2 unidades del artículo 1; peso acumulado = 4 toneladas

Ing. Manuel Sánchez Terán

INVESTIGACION DE OPERACIONES II

PROBLEMA 2 (Inventarios) Solución: Sean: xn el nivel de producción en el mes n sn el inventario inicial en el mes n dn la demanda en el mes n

Mes 1 2 3 4

Demanda 1 3 2 4

CP(xn) el costo de producción de xn docenas, CP(xn)=30+10xn Lo que tenga en almacén el siguiente mes, será lo que produje más lo que tenía en inventario menos la demanda de dicho mes: si+1 = si + xi - di ; entonces CI(si+1)=5(si + xi - di) Función recursiva: Costo mínimo de cumplir las demandas fn(sn ,xn) = min {CI(si+1) + CP(xn) + fn+1(sn+1)}

s4 0 1 2 3 4

x4 = 0 0+0

Etapa 4 (demanda=4) f4(s4,x4)=30+10x4 x4 = 1 x4 = 2 x4 = 3 x4 = 4 30+40 30+30 30+20 30+10 -

Solución óptima f4*(s4) x4* 70 4 60 3 50 2 40 1 0 0

Etapa 3 (demanda=2)

x3 = 5 15+80+40=135 20+80+0=100 -

Solución óptima f3*(s3) x3* 120 2 100 5 70 0 65 0 60 0

x2 = 5 10+80+70=160 15+80+65=160 20+80+60=160 -

Solución óptima f2*(s2) x2* 160 5 150 4 140 3 120 0 105 0

f3(s3,x3)= 5(s3+x3-d3)+30+10x3+f4*(s3+x3-d3) s3 0 1 2 3 4

x3 = 0 0+0+70=70 5+0+60=65 10+0+50=60

x3 = 1 0+40+70=110 5+40+60=105 10+40+50=100 15+40+40=95

x3 = 2 0+50+70=120 5+50+60=115 10+50+50=110 15+50+40=105 20+50+0=70

x3 = 3 5+60+60=125 10+60+50=120 15+60+40=115 20+60+0=80 -

x3 = 4 10+70+50=130 15+70+40=125 20+70+0=90 -

Etapa 2 (demanda=3) f2(s2,x2)= 5(s2+x2-d2)+30+10x2+f3*(s2+x2-d2) s2 0 1 2 3 4

x2 = 0 0+0+120=120 5+0+100=105

x2 = 1 0+40+120=160 5+40+100=145 10+40+70=120

x2 = 2 0+50+120=170 5+50+100=155 10+50+70=130 15+50+65=130

x2 = 3 0+60+120=180 5+60+100=165 10+60+70=140 15+60+65=140 20+60+60=140

x2 = 4 5+70+100=175 10+70+70=150 15+70+65=150 20+70+60=150 -

Etapa 1 (demanda=1) f1(s1,x1)= 5(s1+x1-d1)+30+10x1+f2*(s1+x1-d1) s1 0

x1 = 0 -

x1 = 1 0+40+160=200

x1 = 2 5+50+150=205

x1 = 3 10+60+140=210

x1 = 4 15+70+120=205

x1 = 5 20+80+105=205

Solución óptima f1*(s1) x1* 200 1

Mes1: producir 1 docena, cumplir con la demanda Mes2: producir 5 docenas, entregar 3 guardar 2 Mes3: no producir, cumplir con la demanda con lo que hay en inventario Mes4: producir 4 docenas para cubrir la demanda.

Ing. Manuel Sánchez Terán