Descarga la aplicación para disfrutar aún más
Vista previa del material en texto
Ing. Silvana Castillo Año 2020 Pasos 1. Definir Objetivo 2. Etapas 3. Variables de decisión(xi) 4. Estados----Variables de estado(si) 5. Función recursiva(Max, Min según el caso). Cada aplicación tiene una forma especial de función según el caso Aplicaciones Problema de la mochila Asignación Stock Políticas de mantenimiento etc. Objetivo: Maximizar la inversión o minimizar costos optimizando la carga Etapas: Productos clase A,B,C…. Variables de decisión (xi): cantidad de productos a cargar Variables de estado(si): cantidad (de toneladas, Kg etc) disponibles a cargar Función recursiva Fi *(si,xi)= Máxbi xi + Fi+1 *(si+1= si – pi.xi) (adaptarla a cada problema) donde bi = beneficio de xi pi=peso de xi(toneladas, Kg etc) Problema de la mochila 1 Un camión puede transportar un total de 10 toneladas de productos. Hay tres clases de productos para transportar. Sus pesos y beneficios se encuentran tabulados. Suponiendo que por lo menos debe transportar un artículo de cada clase. Determinar el cargamento que maximiza el valor total. Clase Beneficio($) Peso(Ton) A 20 1 B 50 2 C 60 2 Etapa 3= Producto clase C S3(Ton)/x3 1(2 Ton) 2(4 Ton) 3(6 Ton) x3* F3* 2 $60 1 $60 3 $60 1 $60 4 $60 $120 2 $120 5 $60 $120 2 $120 6 $60 $120 $180 3 $180 7 $60 $120 $180 3 $180 F3*(s3,x3)= Máx(bc * x3)= Máx($60 *x3) Límite Superior=10 Ton-3Ton(1 art clase A y 1 art clase B)=7 Ton Clase Beneficio($) Peso(Ton) A 20 1 B 50 2 C 60 2 Límite Inferior=2 Ton (1 artc clase C) Art clase C= 10 Ton -3 Ton=7 Ton---------3 art Clase C Etapa 2= Producto clase B S2(Ton)/x2 1(2 Ton) 2(4 Ton) 3(6 Ton) x2* F2* 4 $50+$60=$110 1 $110 5 $50+$60=$110 1 $110 6 $50+$120=$170 $100+$60=$160 1 $170 7 $50+$120=$170 $100+$60=$160 1 $170 8 $50+$180=$230 $100+$120=$220 $150+$60=$210 1 $230 9 $50+$180=$230 $100+$120=$220 $150+$60=$210 1 $230 F2*(s2,x2)= Máx(bb.x2+ F3*(s3=s2-2x2)= Máx(50.x2+ F3*(s3=s2-2x2) Clase Beneficio($) Peso(Ton) A 20 1 B 50 2 C 60 2 S3(Ton)/x3 1(2 Ton) 2(4 Ton) 3(6 Ton) x3* F3* 2 $60 1 $60 3 $60 1 $60 4 $60 $120 2 $120 5 $60 $120 2 $120 6 $60 $120 $180 3 $180 7 $60 $120 $180 3 $180 Límite Inferior=2 Ton (1 artc clase C)+2 Ton(1 artc clase B)= 4 Ton Límite Superior=10 Ton-1Ton(1 art clase A)=9 Ton Art clase B= 10 Ton -3 Ton=7 Ton---------3 art Clase B Etapa 1= Producto clase A S2(Ton)/x2 1(1 Ton) 2(2 Ton) 3(3 Ton) 4(4Ton) 5(5Ton) 6(6Ton) x1* F1* 10 $20+$230=$250 $40+$230=$270 $60+$170=$230 $80+$170=$250 $100+$110=$210 $120+$110=$210 2 $270 F1(s1,x1)= Máx(ba.x1+ F2*(s2=s1-1.x1)= Máx(20.x1+ F2*(s2=s1-1.x1) Clase Beneficio($) Peso(Ton) A 20 1 B 50 2 C 60 2 Se sugiere cargar: 2 productos clase A(2Ton), 1 producto clase B(2 Ton), 3 productos Clase C(6 ton) obteniendo un beneficio de $270 S2(Ton)/x2 1(2 Ton) 2(4 Ton) 3(6 Ton) x2* f2* 4 $50+$60=$110 1 $110 5 $50+$60=$110 1 $110 6 $50+$120=$170 $100+$60=$160 1 $170 7 $50+$120=$170 $100+$60=$160 1 $170 8 $50+$180=$230 $100+$120=$220 $150+$60=$210 1 $230 9 $50+$180=$230 $100+$120=$220 $150+$60=$210 1 $230 S3(Ton)/x3 1(2 Ton) 2(4 Ton) 3(6 Ton) x3* F3* 2 $60 1 $60 3 $60 1 $60 4 $60 $120 2 $120 5 $60 $120 2 $120 6 $60 $120 $180 3 $180 7 $60 $120 $180 3 $180 Art clase A= 10 Ton -4 Ton=6 Ton---------6 art Clase A Objetivo: Maximizar la inversión Etapas: Proyectos i(i=1,2,3) Variables de decisión (xi): cantidad a invertir en cada proyecto Variables de estado(si): cantidad disponible a invertir Función recursiva Fi *(si,xi)= Maxri+ Fi+1 *(si+1= si - xi) (adaptarla a cada problema) Donde ri= retorno en la etapa i Problema de Asignación 2 Un inversionista tiene $ 6000 para invertir en uno de tres proyectos. El debe invertir en unidades de $ 1000. El retorno potencial a partir de la inversión en cualquier riesgo depende de la cantidad invertida de acuerdo a la tabla: Cantidad invertida Proyecto A B C 0 0 0 0 1000 0.5 1.5 1.2 2000 1 2 2.4 3000 3 2.2 2.5 4000 3.1 2.3 2.6 5000 3.2 2.4 2.7 6000 3.3 2.5 2.8 Etapa 3= Proyecto C S3/x3 0 1000 2000 3000 4000 5000 6000 x3* F3* 0 0 - - - - - - 0 0 1000 0 1.2 - - - - - 1000 1.2 2000 0 1.2 2.4 - - - - 2000 2.4 3000 0 1.2 2.4 2.5 - - - 3000 2.5 4000 0 1.2 2.4 2.5 2.6 - - 4000 2.6 5000 0 1.2 2.4 2.5 2.6 2.7 - 5000 2.7 6000 0 1.2 2.4 2.5 2.6 2.7 2.8 6000 2.8 F3 *= Máx(rc) Cantidad invertida Proyecto A B C 0 0 0 0 1000 0.5 1.5 1.2 2000 1 2 2.4 3000 3 2.2 2.5 4000 3.1 2.3 2.6 5000 3.2 2.4 2.7 6000 3.3 2.5 2.8 Etapa 2= Proyecto B F2 *= Max(r2+ F3 *(s3= s2 – x2) S2/x2 0 1000 2000 3000 4000 5000 600 0 x2* F2* 0 0 - - - - - - 0 0 1000 1.2 1.5 - - - - - 1000 1.5 2000 2.4 1.5+1.2 2 - - - - 1000 2.7 3000 2.5 1.5+2.4 2+1.2 2.2 - - - 1000 3.9 4000 2.6 1.5+2.5 2+2.4 2.2+1.2 2.3 - - 2000 4.4 5000 2.7 1.5+2.6 2+2.5 2.2+2.4 2.3+1.2 2.4 - 3000 4.6 6000 2.8 1.5+2.7 2+2.6 2.2+2.5 2.3+ 2.4 2.4+1.2 2.5 3000 o 4000 4.7 Cantidad invertida Proyecto B 0 0 1000 1.5 2000 2 3000 2.2 4000 2.3 5000 2.4 6000 2.5 S3/x3 0 1000 2000 3000 4000 5000 6000 x3* F3* 0 0 - - - - - - 0 0 1000 0 1.2 - - - - - 1000 1.2 2000 0 1.2 2.4 - - - - 2000 2.4 3000 0 1.2 2.4 2.5 - - - 3000 2.5 4000 0 1.2 2.4 2.5 2.6 - - 4000 2.6 5000 0 1.2 2.4 2.5 2.6 2.7 - 5000 2.7 6000 0 1.2 2.4 2.5 2.6 2.7 2.8 6000 2.8 Etapa 1= Proyecto A F1 *= Max(r1+ F2 *(s2= s1 – x1) s1/x1 0 1000 2000 3000 4000 5000 6000 x1 F1* 6000 4.7 0.5+4.6 1+4.4 3+3.9 3.1+2.7 3.2+1.5 3.3 3000 6.9 La inversión óptima es invertir $3000 en el Riesgo A, $1000 en el Riesgo B y $2000 en el Riesgo C obteniendo un retorno de 6.9 Cantidad invertida Proyecto A 0 0 1000 0.5 2000 1 3000 3 4000 3.1 5000 3.2 6000 3.3 S3/x3 0 1000 2000 3000 4000 5000 6000 x3* F3* 0 0 - - - - - - 0 0 1000 0 1.2 - - - - - 1000 1.2 2000 0 1.2 2.4 - - - - 2000 2.4 3000 0 1.2 2.4 2.5 - - - 3000 2.5 4000 0 1.2 2.4 2.5 2.6 - - 4000 2.6 5000 0 1.2 2.4 2.5 2.6 2.7 - 5000 2.7 6000 0 1.2 2.4 2.5 2.6 2.7 2.8 6000 2.8 S2/x2 0 1000 2000 3000 4000 5000 6000 x2 f2 0 0 - - - - - - 0 0 1000 1.2 1.5 - - - - - 1000 1.5 2000 2.4 1.5+1.2 2 - - - - 1000 2.7 3000 2.5 1.5+2.4 2+1.2 2.2 - - - 1000 3.9 4000 2.6 1.5+2.5 2+2.4 2.2+1.2 2.3 - - 2000 4.4 5000 2.7 1.5+2.6 2+2.5 2.2+2.4 2.3+1.2 2.4 - 3000 4.6 6000 2.8 1.5+2.7 2+2.6 2.2+2.5 2.3+ 2.4 2.4+1.2 2.5 3000 o 4000 4.7 Objetivo: Minimizar Costos de Inventario Etapas: Cada uno de los periodos (Meses i(i=1,2,3)) Variables de decisión (xi): cantidad de artículos a comprar o producir Variables de estado(si): cantidad de artículos en stock al inicio de cada periodo Función recursiva Fi(si,xi) = Minpi xi+ hi.si +Fi+1 *(si+1= si - xi) (adaptarla a cada problema) donde pi=precio o ingreso del bien i Problema de Stock hi=costo de mantenimiento del bien i 4. Modelo de Stocks Para satisfacer el programa de producción, el servicio de compras de una empresa debe suministrar cada dos meses cantidades conocidas de cierta materia prima. Se conocen los precios, y las demandas bimestrales para los próximos 3 períodos (de 2 meses). Existe una limitación en la capacidad de almacenamiento: el stock no debe sobrepasar el valor de 9 unidades. El stock inicial es de 4 unidades y el stock final debe ser cero. Se quiere determinar las cantidades a adquirir al principio de cada periodo de modo que el costo total de compra sea mínimo. Interprete los resultados Período i 1 2 3 Demanda di 3 6 4 Precio de compra pi 15 25 30 Bim1 Bim 2 Bim 3 x1 x3x2 S1=4 S2 S3 S4=0 D1=3 D2=6 D3=4 En el mes 1, por ejemplo: S1+x1=D1+S2 Se sabe que la capacidad máxima de almacenamiento es de 9 unidades S1=4 S4=0 5. Por un precio de 1 U.M./litro, una cadena de Supermercados compró 6 litros de leche de una lechería local. Cada litro de leche se vende en las tres tiendas de la cadena en 2 U.M./litro. La lechería debe comprar de nuevo a 0.50U.M./litro la leche que queda al final del día. Infortunadamente para la cadena de supermercados, la demanda para cada una de las tres tiendas de la cadena es incierta. Los datospasados indican que la demanda diaria en cada tienda es como se detalla en la tabla. La cadena de supermercados quiere asignar los 6 litros de leche a las tres tiendas para maximizar la ganancia diaria neta esperada obtenida de la leche. Utilice la Programación dinámica para determinar cómo dicha cadena debe asignar los 6 litros de leche entre las tres tiendas Demanda diaria(litros) Probabilidad Tienda 1 1 0.6 2 0 3 0.4 Tienda 2 1 0.5 2 0.1 3 0.4 Tienda 3 1 0.4 2 0.3 3 0.3 Objetivo: Maximizar ingresos asignando de forma óptima Etapas: Cada una de las tiendas (Tiendas i(i=1,2,3)) Variables de decisión (xi): litros de leche a asignar en cada sucursal Variables de estado(si): litros de leche disponibles para asignar en cada sucursal Función recursiva Fi (si,xi) = Maxri(xi)+ Fi+1 *(si+1= si - xi) (adaptarla a cada problema) donde: ri(xi)= ganancia esperada de xi litros asignados a la tienda
Compartir