PDD-PDP clase invop

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áxbi 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)= Maxri+ 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) = Minpi 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) = Maxri(xi)+ Fi+1
*(si+1= si - xi)
(adaptarla a cada problema)
donde:
ri(xi)= ganancia esperada de xi litros asignados a la tienda