TRABAJO PRÁCTICO Programacion Dinámica-

Vista previa del material en texto

TRABAJO PRÁCTICO Nº 6
 PROGRAMACION DINAMICA DETERMINISTICA y PROBABILISTICA
Problema Nº1: Aplicaciones al problema de la mochila
Un  camionero que trabaja por su cuenta tiene 8 m3 disponibles en un camión que saldrá a Buenos Aires. Un distribuidor que tiene grandes cantidades de tres artículos diferentes, todos destinados para esa ciudad, ha ofrecido al camionero los siguientes pagos por transportar tantos artículos como quepan en el camión:
	Artículo
	Pago($/artículo) 
	Volumen (m3/artículo.)
	I
	11
	2
	II
	32
	1
	III
	58
	3
a. Defina etapa, estado, decisión y refiéralos a este problema.
· Etapa: división del problema, con una decisión de la política requerida en cada etapa. 
En este problema existen 3 etapas, 
· la etapa 1 correspondiente al articulo I,
· la etapa 2 correspondiente al articulo II y 
· la etapa 3 referida al articulo III.
· Estado: refleja la condición de las restricciones y funciona como enlace entre las etapas,de modo que cuando cada etapa se optimiza por separado , la decisión resultante es automáticamente factible para todo el problema.
Para este problema , el estado Si estarádado por el volumen en m3 a ocupar ren el camión.
· S1: volumen disponible en m3 a ocupar en el camión en la etapa 1
· S2: volumen disponible en m3 a ocupar en el camión en la etapa 2
· S3: volumen disponible en m3 a ocupar en el camión en la etapa 3
· Decisión: el estado de decisión es transformar el estado actual en un estado asociado con la etapa siguiente. Para este problema las variables de decisión serán Xi , donde :
· X1: Cantidad de artículo tipo I a cargar en el camión
· X2: Cantidad de artículo tipo II a cargar en el camión 
· X3: Cantidad de artículo tipo III a cargar en el camión
b. Utilice PD para encontrar la política de asignación de las tres clases de productos en el barco.
Como x3 tiene un peso de 3m3 , los valores que esta variable puede tomar es 1 y 2 ya que si tomara el valor de 3 excedería el volumen disponible en el camión.
ETAPA 3: ARTÍCULO III : F3*(s3)= máx x3 { $58 x3}
Como hay disponible 8 m3 , la cantidad máxima de artículos tipo III que podría cargarse en el camión es de 2 porque cada uno de ellos ocupa un espacio de 3m3.
	S3/x3
	1(3m3)
	2(6m3)
	X3*
	F3*
	3
	58
	0
	1
	58
	4
	58
	 
	1
	58
	5
	58
	 
	1
	58
	6
	58
	116
	2
	116
	7
	58
	116
	2
	116
	8
	58
	116
	2
	116
ETAPA 2: ARTÍCULO II : F2*(s2, x2)= máx x2 { 32 x2 + F3*(s3- 1x2)}
Como hay disponible 8 m3 y cada articulo tipo II ocupa 1m3, la cantidad máxima de artículos tipo II que podría cargarse en el camión es de 8 .
	S2/x2
	0(1m3)
	1(1m3)
	2(2m3)
	3(3m3)
	4(4m3)
	5(5m3)
	6(6m3)
	7(7m3)
	8(8m3)
	X2*
	F2*
	0
	0
	 
	 
	 
	 
	 
	 
	 
	 
	0
	0
	1
	0
	32
	 
	 
	 
	 
	 
	 
	 
	1
	32
	2
	0
	32
	64
	 
	 
	 
	 
	 
	 
	2
	64
	3
	0+58
	32
	64
	96
	 
	 
	 
	 
	 
	3
	96
	4
	0+58
	32+58
	64
	96
	128
	 
	 
	 
	 
	4
	128
	5
	0+58
	32+58
	64+58
	96
	128
	160
	 
	 
	 
	5
	160
	6
	0+116
	32+58
	64+58
	96+58
	128
	160
	192
	 
	 
	6
	192
	7
	0+116
	32+116
	64+58
	96+58
	128+58
	160
	192
	224
	 
	7
	224
	8
	0+116
	32+116
	64+116
	96+58
	128+58
	160+58
	192
	224
	256
	8
	256
ETAPA 1: ARTÍCULO I : F1(s1)= máx x1 { 11 x1 + f2(s2- 2x1)}
Como hay disponible 8 m3, la cantidad máxima de artículos tipo I que podría cargarse en el camión es de 4 porque cada uno de ellos ocupa un espacio de 2m3.
	S1/x1
	0(2m3)
	1(2m3)
	2(4m3)
	3(6m3)
	4(8m3)
	X1*
	F1*
	8
	0+256
	11+224
	22+192
	33+160
	44+128
	0
	$256
Decisión:
En el camión se cargará:
· Artículo I: 0 unidades
· Articulo II: 8 unidades, las cuales ocupan los 8 m3 de volumen disponible.
· Articulo III: 0 unidades.
El máximo beneficio que se obtiene es de $256.
Problema Nº2: Aplicaciones al problema de la mochila
Un barco puede transportar un total de 15 tn. de ciertos productos. Existen tres clases de productos para transportar. Sus pesos y beneficio en el transporte están tabulados. Suponiendo que por lo menos debe transportar un artículo de cada clase, determinar el cargamento que maximiza el beneficio total. Interprete los resultados
	Clase
	Beneficio ($) 
	Peso (tn.)
	A
	40
	2
	B
	60
	1
	C
	30
	3
a) Defina etapa, estado, decisión y refiéralos a este problema. 
Etapa: división del problema, con una decisión de la política requerida en cada etapa.
En este problema existen 3 etapas, 
Etapa1 = Producto clase A
Etapa2 = Producto clase B
Etapa3 = Producto clase C
Estado: refleja la condición de las restricciones y funciona como enlace entre las etapas, de modo que cuando cada etapa se optimiza por separado, la decisión resultante es automáticamente factible para todo el problema.
Para este problema el estado que se debe observar es la cantidad de toneladas(Tn) disponibles en el barco para agregar los distintos tipos de producto (Si)
Decisión: las variables sobre las que se deben decidir son las cantidades de cada producto a cargar en el barco para optimizar el espacio disponible logrando el máximo beneficio posible (Xi)
b) Utilice PD para encontrar la política de de asignación de las tres clases de productos en el barco.
Como se debe cargar por lo menos un producto de cada clase, las Tn disponibles que tiene el problema para trabajar sin restricciones es : 15 Tn-(2+1+3)Tn= 9 Tn disponibles.
ETAPA 3: Producto Clase C : F3(s3)= máx x3 { 30 x3}
S3: 
Min S3 = 3 Tn que es el peso de este producto.
Máx S3 = 15 Tn – (2+1) = 12 Tn
X3 min= 1(3 Tn)
X3máx=15-2-1 Tn= 12, le resto el peso de los art A y B.
	S3/x3
	1(3Tn)
	2(6Tn)
	3( 9Tn)
	4(12Tn)
	X3*
	F3*
	3
	30
	 
	 
	 
	1
	30
	4
	30
	 
	 
	 
	1
	30
	5
	30
	 
	 
	 
	1
	30
	6
	30
	60
	 
	 
	2
	60
	7
	30
	60
	 
	 
	2
	60
	8
	30
	60
	 
	 
	2
	60
	9
	30
	60
	90
	 
	3
	90
	10
	30
	60
	90
	 
	3
	90
	11
	30
	60
	90
	 
	3
	90
	12
	30
	60
	90
	120
	4
	120
ETAPA 2: Producto Clase B: F2(s2) = máx x2 { 60 x2 + f3(s3- 1x2)}
Peso B = 1 Tn
Beneficio = 60$
	Min S2= 1+3 =4 Tn , es el peso del articulo B más el peso del art C
	Máx S2= 15-2 =13 , le resto el peso del art A.
Como cada articulo B tiene un peso de 1 Tn:
	X2= 1 (1Tn)
	X2 máx= 15-3-2= 10 Tn
	S2/x2
	1(1Tn)
	2
	3
	4
	5
	6
	7
	8
	9
	10
	X2*
	F2*
	4
	60+30
	 
	 
	 
	 
	 
	 
	 
	 
	 
	1
	90
	5
	60+30
	120+30
	 
	 
	 
	 
	 
	 
	 
	 
	2
	150
	6
	60+30
	120+30
	180+30
	 
	 
	 
	 
	 
	 
	 
	3
	190
	7
	60+60
	120+30
	180+30
	240+30
	 
	 
	 
	 
	 
	 
	4
	270
	8
	60+60
	120+60
	180+30
	240+30
	300+30
	 
	 
	 
	 
	 
	5
	330
	9
	60+60
	120+60
	180+60
	240+30
	300+30
	360+30
	 
	 
	 
	 
	6
	390
	10
	60+60
	120+60
	180+60
	240+60
	300+30
	360+30
	420+30
	 
	 
	 
	7
	450
	11
	60+90
	120+90
	180+60
	240+60
	300+60
	360+30
	420+30
	480+30
	 
	 
	8
	510
	12
	60+90
	120+90
	180+90
	240+60
	300+60
	360+60
	420+30
	480+30
	540+30
	 
	9
	570
	13
	60+120
	120+90
	180+90
	240+90
	300+60
	360+60
	420+60
	480+30
	540+30
	600+30
	10
	630
ETAPA 1: Producto Clase A: F1(s1)= máx x1 { 40 x1 + f2(s2- 2x1)}
Min S1=3+1+2=6 Tn, sumo el peso de cada uno de los 3 articulos.
Máx S1=15-3-1=11 Tn, sumo el peso de cada uno de los 3 articulos.
Como cada articulo A tiene un peso de 2 Tn:
X1min=1 (2Tn) 
X1máx=15-3-1= 10 Tn (5 unidades del articulo A)
	S1/x1
	1(2Tn)
	2(4Tn)
	3(6Tn)
	4(8Tn)
	5(10Tn)
	X1*
	F1*
	6
	40+90
	 
	 
	 
	 
	1
	130
	7
	40+150
	 
	 
	 
	 
	1
	190
	8
	40+210
	80+90
	 
	 
	 
	1
	250
	9
	40+270
	80+150
	 
	 
	 
	1
	310
	10
	40+330
	80+210
	120+90
	 
	 
	1
	370
	11
	40+390
	80+270
	120+150
	 
	 
	1
	430
	12
	40+450
	80+330
	120+210
	160+90
	 
	1
	490
	13
	40+510
	80+390
	120+270
	160+150
	 
	1
	550
	14
	40+570
	80+450
	120+330
	160+210
	200+90
	1
	610
	15
	40+630
	80+510
	120+390
	160+270
	200+150
	1
	670
Solución óptima:
Se deben subir al barco:
· X1= 1 unidad del artículo A, de 2Tn
· X2=10 unidades del artículo B , de 1 Tn cada uno.
· X3=1 unidad del artículo A, de 3 Tn.
Obteniendo un beneficio de $670.
Problema Nº3: Modelo de inversión
Una empresa tiene 4 millones de dólares para invertir en tres pozo petroleros. El rendimiento ganado del pozo i(i=1.2.3) depende de la cantidad de dinero invertido en el pozo i, según puede verse en la tabla.Si se supone que la cantidad invertida en un pozo debe ser múltiplo exacto de 1 millón de dólares, determine mediante programación dinámica, una estrategia de inversión que maximice el rendimiento que la empresa obtendrá con los tres pozos.
	Cantidad invertida
(millones de dólares)
	Rendimiento(millones de dólares)
	
	Pozo1
	Pozo2
	Pozo3
	0
	4
	3
	3
	1
	7
	6
	7
	2
	8
	10
	8
	3
	9
	12
	13
	4
	11
	14
	15
a. Analice y resuelva el problema, indicando en cada uno de los casos: etapas, estados, variables de decisión y función recursiva. 
b. Encuentre el óptimo y especifique en forma completa alternativas. Interprete los resultados obtenidos.
Fuente: Winston, W.- Investigación de Operaciones: Aplicaciones y Algoritmos- Ed.Thomson. 4ª Edición 2005. Pág.985
Problema Nº4: Un ingeniero ha recibido ofertas de tres diferentes clientes que desean sus servicios profesionales. A cada cliente le gustaría que el profesional trabajara para él tiempo completo; sin embargo, cada cliente está deseoso de emplear al señor tantos días semanales como él pueda hacerlo, por los honorarios que se muestran en la tabla. ¿Cuántos días deberá dedicar el Sr. A cada cliente para maximizar su ingreso semanal?
	Número de días
	Cliente 1($)
	Cliente 2($)
	Cliente 3($)
	0
	0
	0
	0
	1
	100
	125
	150
	2
	250
	250
	300
	3
	400
	375
	400
	4
	525
	500
	550
	5
	600
	625
	650
a. Analice y resuelva el problema, indicando en cada uno de los casos: etapas, estados, variables de decisión y función recursiva. 
Etapa
· Etapa 3= Cliente 3
· Etapa 2= Cliente 2
· Etapa 1= Cliente 1
Estado
· S1 = cantidad disponible de días en el cliente 1
· S2 = cantidad disponible de días en el cliente 2
· S3 = cantidad disponible de días en el cliente 3
Decisión
· X1= cantidad días con el Cliente 1
· X2= cantidad días con el Cliente 2
· X3= cantidad días con el Cliente 3
b. Encuentre el óptimo y especifique en forma completa alternativas. Interprete los resultados obtenidos.
Etapa 3: 	Cliente 3 
Función recursiva:		 F3*= Max(r3)
	S3/X3
	0
	1
	2
	3
	4
	5
	x3*
	F3*
	0
	0
	-
	-
	-
	-
	-
	0
	0
	1
	0
	150
	-
	-
	-
	-
	1
	$ 150
	2
	0
	150
	300
	-
	-
	-
	2
	$ 300
	3
	0
	150
	300
	400
	-
	-
	3
	$ 400
	4
	0
	150
	300
	400
	550
	-
	4
	$ 550
	5
	0
	150
	300
	400
	550
	650
	5
	$ 650
Etapa 2: 	Cliente 2
Función recursiva: 		F2*=Max(r2+F3*(S3=S2-X2))
	S2/X2
	0
	1
	2
	3
	4
	5
	X2*
	F2*
	0
	0
	-
	-
	-
	-
	-
	0
	0
	1
	150
	125
	-
	-
	-
	-
	0
	150
	2
	300
	125+150
	250
	-
	-
	-
	0
	300
	3
	400
	125+300
	250+150
	375
	-
	-
	1
	425
	4
	550
	125+400
	250+300
	375+150
	500
	-
	0 o 2
	550
	5
	650
	125+550
	250+400
	375+300
	500+150
	625
	1 o 3
	675
Etapa 1: 	Cliente 1
Función recursiva: 		F1* = Max (r1+F2*(S2=S1-X1)
	S1/x1
	0
	1
	2
	3
	4
	5
	X1*
	F1*
	5
	675
	100+550
	250+425
	400+300
	525+150
	600
	3
	700
Solución optima:
Trabajando :
· X1=3 días con el cliente 1
· X2= 0 días con el cliente 2
· X3= 2 dias con el cliente 3
Obtendrá un ingreso de $700 por semana.
Problema Nº5: Aplicaciones a problemas de inventario
Una empresa debe decidir su política de producción e inventario para los próximos tres meses, la empresa ha adquirido algunos compromisos importantes de entrega para los meses: 3, 2, y 4 unidades respectivamente.
En el proceso productivo se incurre en costos de producción y de almacenamiento, estos costos son:
· Costo de almacenamiento: corresponde al costo de oportunidad de mantener el material en bodega (capital inmovilizado, perdidas, etc) su valor es hi por unidad de producto-mes. 
· Costo de producción: corresponde al costo unitario de producción de mano de obra , materiales , equipos, etc 
· El valor inicial del inventario es cero. 
	Mes
	hi
	Ci
	1
	1
	12
	2
	3
	17
	3
	2
	22
a. Plantee el problema y formule el modelo 
Y1+x1=y2+3 y2=y1+x1-3
Y2+x2=y3+2 y3= y2+x2-2
Y3+x3=y4+4, pero y4=0 y4= y3+x3-4
b. Encuentre el óptimo y especifique en forma completa alternativas. Interprete los resultados obtenidos.
Etapa 3: Periodo del mes 3
Función:
F3(y3)=min x3{22*x3+2(y3+x3-4)+f4*(y4)
Y3+x3=y4+4, pero y4=0 x3= 4 – y3
Como x3 no puede ser negativo los valores posibles de y3 son 0,1,2,3 y 4.
	y3/x3
	0
	1
	2
	3
	4
	f3*(y3)
	x3*
	0
	-
	-
	-
	-
	88
	88
	4
	1
	-
	-
	-
	66
	-
	66
	3
	2
	-
	-
	44
	-
	-
	44
	2
	3
	-
	22
	-
	-
	-
	22
	1
	4
	0
	-
	-
	-
	-
	0
	0
Etapa 2: Periodo del mes 2
Función:
F2(y2)=min x2{17*x2+3(y2+x2-2)+f3*(y3)
Y2+x2=y3+2 y3= y2+x2-2
· Si y2=0 x2= y3+2 
Como y3=0,1,2,3 y 4; si y3=4 x2=6
F2(y2=0)= 17*6+3(0+6-2)+f3(y3=4)= 102+12+0=114
Si y3=3 x2= 5 
F2(y2=0)=17*5+3*(0+5-2)+f3(y3=3)=85+9+22= 116
· Si y2=6 x2= y3+2-6 , con y3= 0,1,2,3,4 
Si y3=4 x2=4+2-6=0
F2(y2=6)= 17*0+3*(6+0-2)+f3(y3=4)=0+12+0=12
Máximo valor de , porque .
Y máximo valor de 
 entonces, máximo .
	y2/x2
	0
	1
	2
	3
	4
	5
	6
	f2*(y2)
	X2*
	0
	-
	-
	122
	120
	118
	116
	114
	114
	6
	1
	-
	105
	103
	101
	99
	97
	-
	97
	5
	2
	88
	86
	84
	82
	80
	-
	-
	80
	4
	3
	69
	67
	65
	63
	-
	-
	-
	63
	3
	4
	50
	48
	46
	-
	-
	-
	-
	46
	2
	5
	31
	29
	-
	-
	-
	-
	-
	29
	1
	6
	12
	-
	-
	-
	-
	-
	-
	12
	0
Etapa 1: Periodo del mes 1
Función:
F1(y1)=min x1{12*x1+1(y1+x1-3)+f2*(y2)
Y1+x1=y2+3 x1= y2+3-y1
Como el stock inicial es cero: x1= y2+3 
Y2=0,1,2,3,4,5,6 por lo tanto el minimo valor de x1 es 3 y el máximo valor es 9
	y1/x1
	3
	4
	5
	6
	7
	8
	9
	f1*(y1)
	x1*
	0
	150
	146
	142
	138
	134
	130
	126
	126
	9
Solucion optima:
Se deben producir:
X1=9 unidades el mes 1
X2=0 unidades el mes 2
X3=0 unidades el mes 3
Siendo el costo de la política optima de $126 para los próximos tres meses. 
De la Etapa 1
X1 = 9, y1=0
Y1 + X1 = Y2 + 3 y2= 0+9-3=6
De la Etapa 2
X2 = 0 , y2=6 
Y2 + X2 = Y3 + 2 y3=6+0-2=4
De la Etapa 1 
 X3= y3-4 , como y3 =4 de la etapa anterior X3 = 0
La política óptima es producir 9 unidades en el mes 1, y los meses siguientes no producir, solo conviene almacenar inventario para satisfacer sus compromisos.
Problema Nº6: Aplicaciones al problema de Asignación
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 datos pasados 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
	Distribuciones de probabilidad para la demanda diaria de leche
	
	Demanda diaria(litros)
	Probabilidad
	Tienda 1
	1
	0.5
	
	2
	0.1
	
	3
	0.4
	Tienda 2
	1
	0.4
	
	2
	0.2
	
	3
	0.4
	Tienda 3
	1
	0.3
	
	2
	0.4
	
	3
	0.3
a. Defina etapa, estado, decisión y refiéralos a este problema.
	Capacidad =
	6
	l/diarios
	C unitario =
	1
	UM/l
	Pv =
	2
	UM/l
Etapas: cada una de las tiendas:
Tienda 1
Tienda 2
Tienda 3
Variables de decisión: Litros de leche asignados a cada tienda
Xi= Cantidad de litros destinados a la tienda i.
Variables de estado: litros de leche disponibles para asignar en cada tienda
Si= Cantidad de litros disponibles para distribuir.
ri= Ingresos esperados de los xi litros destinados a la tienda i.
fi(x)= Ingreso máximo esperado en la tienda i por los x litros de leches asignados la tienda i.
b. Utilice PD para encontrar la política de asignación de los 6 litros de leche entre las tres sucursales. Interprete los resultados
Si se asignan 2 L a la tienda 3 y se venden 2 o más litros el ingreso que se obtiene es de 2*2UM=4UM.
Si la demanda es de 1L, el ingreso es de 2UM y se devuelve 1L a 0,50UM por lo tanto el ingreso que se obtiene es de 2,5UM. Puesto que hay una probabilidad de 0,6 de que la demanda en latienda 3 sea de 2 o más L y una probabilidad de 0,4 de que lademanda en la Tienda 3 sea de 1L, se deduce que:
	r3(0)
	0
	r2(0)
	0
	r1(0)
	0
	r3(1)
	2
	r2(1)
	2
	r1(1)
	2
	r3(2)
	3,55
	r2(2)
	3,4
	r1(2)
	3,25
	r3(3)
	4,5
	r2(3)
	4,5
	r1(3)
	4,35
Etapa 3: Tienda 3
Función: F3(x)=r3(x)
	S3/x3
	0
	1
	2
	3
	F3*
	X3*
	0
	0
	 
	 
	 
	0
	0
	1
	 
	2
	 
	 
	2
	1
	2
	 
	 
	3,55
	 
	3,55
	2
	3
	 
	 
	 
	4,5
	4,5
	3
Etapa 2: Tienda 2
Función:	F2(x)=r2(x)+f3(s-x)
	s2/x2
	0
	1
	2
	3
	f2*
	x2*
	0
	0
	-
	-
	-
	0
	0
	1
	2
	2
	-
	-
	2
	0 o 1
	2
	3,55
	4
	3,4
	-
	3,55
	0
	3
	4,5
	5,55
	5,4
	4,5
	5,55
	1
	4
	-
	6,5
	6,95
	6,5
	6,95
	2
	5
	-
	-
	7,9
	8,05
	8,05
	3
	6
	-
	-
	-
	9
	9
	3
Etapa 1: Tienda 1
Función:	F1(x)=r1(x)+f2(s-x)
	s1/x1
	0
	1
	2
	3
	f1*
	x1*
	6
	0
	10,05
	10,2
	9,9
	10,2
	2
Si se asigna 2 litros a la tienda 1, entonces tenemos 6-2 =4 litros disponibles para la Tienda 2 y la Tienda 3. Como f2(4) se le asigna 2L , entonces quedan disponibles 4-2=2 L para la Tienda 3 ; a f3(3) se le asigna 2L.
Por lo tanto, se obtiene un ingreso máximo de 10,2UM si la demanda en cada tienda es de 2L.
Fuente: Winston, W.- Investigación de Operaciones: Aplicaciones y Algoritmos- Ed.Thomson. 4ª Edición 2005. Pág.985
Nota: Para poder resolver las consignas propuestas, se recomienda consultar:
· Ref. Bibliográfica 14,16
· Kauffman A, Programación Dinámica. CECSA
Fecha de realización: 10/06/20
Fecha de entrega: 30/06/20
x1x2x3
S1S2S3S4
x1x2x3
y1y2y3y4 = 0
d1 = 3d2 = 2d3 = 4