INVOP2 Programación Dinámica Probabilística

PROBLEMA 1

Considere un sistema electrónico con cuatro componentes, cada uno de los cuales debe trabajar para que el sistema funcione. La confiabilidad del sistema se puede mejorar si se instalan varias unidades paralelas en uno o más de los componentes. La siguiente tabla muestra la probabilidad de que los respectivos componentes funcionen si constan de una, dos o tres unidades paralelas:

Unidades paralelas	Probabilidad de funcionamiento
	Componente 1	Componente 2	Componente 3	Componente 4
1	0.5	0.6	0.7	0.5
2	0.6	0.7	0.8	0.7
3	0.8	0.8	0.9	0.9

La probabilidad de que el sistema funcione es el producto de las probabilidades de que los componentes respectivos funcionen.

En la siguiente tabla se presenta el costo (en cientos de dólares) de instalar una, dos o tres unidades paralelas en los componentes respectivos:

Unidades paralelas	Costo
	Componente 1	Componente 2	Componente 3	Componente 4
1	1	2	1	2
2	2	4	3	3
3	3	5	4	4

Dadas las limitaciones de presupuesto, se puede gastar un máximo de $1000.

Use programación dinámica para determinar cuántas unidades paralelas instalar en cada uno de los cuatro componentes para maximizar la probabilidad de que el sistema funcione.

Solución:

x_n            : número de unidades paralelas a instalar del componente n

p_n(x_n)      : probabilidad de que el componente n funcione si se le instala x_n unidades paralelas

c_n(x_n)      : costo de instalar x_n unidades paralelas del componente n

s_n             : cientos de $ que quedan disponibles para gastar en componentes

f_n(s_n,x_n)  =  max { p_n(x_n) f_n+1^*(s_{n -} c_n(x_n))}

Etapa 4 (componente 4)
s4	f4(s4,x4)  =  p4(x4)			Solución óptima
	x4 = 1	x4 = 2	x4 = 3	f4*(s4)	x4*
200	0.5	-	-	0.5	1
300	0.5	0.7	-	0.7	2
400	0.5	0.7	0.9	0.9	3
500	0.5	0.7	0.9	0.9	3
600	0.5	0.7	0.9	0.9	3

Etapa 3 (componente 3)
s3	f3(s3,x3)  =  p3(x3) f4*(s3 - c3(x3))}			Solución óptima
	x3 = 1	x3 = 2	x3 = 3	f3*(s3)	x3*
300	(0.7)(0.5)=0.35	-	-	0.35	1
400	(0.7)(0.7)=0.49	-	-	0.49	1
500	(0.7)(0.9)=0.63	(0.8)(0.5)=0.40	-	0.63	1
600	(0.7)(0.9)=0.63	(0.8)(0.7)=0.56	(0.9)(0.5)=0.45	0.63	1
700	(0.7)(0.9)=0.63	(0.8)(0.9)=0.72	(0.9)(0.7)=0.63	0.72	2

Etapa 2 (componente 2)
s2	f2(s2,x2)  =  p2(x2) f3*(s2 - c2(x2))}			Solución óptima
	x2 = 1	x2 = 2	x2 = 3	f2*(s2)	x2*
500	(0.6)(0.35)=0.210	-	-	0.210	1
600	(0.6)(0.49)=0.294	-	-	0.294	1
700	(0.6)(0.63)=0.378	(0.7)(0.35)=0.245	-	0.378	1
800	(0.6)(0.63)=0.378	(0.7)(0.49)=0.343	(0.8)(0.35)=0.280	0.378	1
900	(0.6)(0.72)=0.432	(0.7)(0.63)=0.441	(0.8)(0.49)=0.392	0.441	2

Etapa 1 (componente 1)
s1	f1(s1,x1)  =  p1(x1) f2*(s1 - c1(x1))}			Solución óptima
	x1 = 1	x1 = 2	x1 = 3	f1*(s1)	x1*
1000	(0.5)(0.441)=0.2205	(0.6)(0.378)=0.2268	(0.8)(0.378)=0.3024	0.3024	3

El sistema tiene un 30.24% de probabilidad que funcione.

Solución óptima:                x₁=3, x₂=1, x₃=1, x₄=3

                               De los $1000 al colocar 3 unidades del componente 1 (costo=$300), me quedarían $700

                               De los $700 al colocar 1 unidad del componente 2 (costo=$200), me quedarían $500

                               De los $500 al colocar 1 unidad del componente 3 (costo=$100), me quedarían $400

                               De los $400 al colocar 3 unidades del componente 4 (costo=$400), no quedaría dinero.

PROBLEMA 2

Imagine que tiene $5000 para invertir y tendrá la oportunidad de hacerlo en cualquiera de dos inversiones (A o B) al principio de cada uno de los próximos tres años. Existe incertidumbre respecto del rendimiento de ambas inversiones. Si invierte en A, puede perder todo el dinero o (con probabilidad más alta) obtener $10000 (una ganancia de $5000) al final del año. Si  invierte en B, puede obtener los mismos $5000 que invierte o (con probabilidad más baja) $10000 al terminar el año. Las probabilidades para que sucedan estos eventos son las siguientes:

Inversión	Cantidad Obtenida ($)	Probabilidad
A	0	0.3
	10000	0.7
B	5000	0.9
	10000	0.1

Se le permite hacer (a lo sumo) una inversión al año y sólo puede invertir $5000 cada vez (cualquier cantidad adicional de dinero acumulada es inútil). Utilice programación dinámica para encontrar la política de inversión que maximice la cantidad de dinero esperada que tendrá después de los tres años.

Solución:

Objetivo: maximizar cantidad acumulada (esperada) después de los 3 años

Monto a invertir: solamente $5000

Estados: $ acumulados (no necesariamente se invierte todo)

Etapa 3
s3			Solución óptima
	A	B	f3*(s3)	x3*
0	0	0	0	0
5000	(0.3)(0)+(0.7)(10000)=7000	(0.9)(5000)+(0.1)(10000)=5500	7000	A
10000	5000+(0.3)(0)+(0.7)(10000)=12000	5000+(0.9)(5000)+(0.1)(10000)=10500	12000	A
15000	10000+(0.3)(0)+(0.7)(10000)=17000	10000+(0.9)(5000)+(0.1)(10000)=15500	17000	A

Etapa 2
s2			Solución óptima
	A	B	f2*(s2)	x2*
0	0	0	0	0
5000	(0.3)(0)+(0.7)(12000)=8400	(0.9)(7000)+(0.1)(12000)=7500	8400	A
10000	(0.3)(7000)+(0.7)(17000)=14000	(0.9)(12000)+(0.1)(17000)=12500	14000	A

Etapa 1
s1			Solución óptima
	A	B	f1*(s1)	x1*
5000	(0.3)(0)+(0.7)(14000)=9800	(0.9)(8400)+(0.1)(14000)=8960	9800	A

Recuerda:

La cantidad a invertir en cada año es de $5000.

El valor de $9800 es una cantidad referencial que sirve para tomar la decisión de inversión. No es la cantidad de dinero real que se puede obtener.

PROBLEMA 3

Una empresa ha recibido el encargo de fabricar un artículo, que, por las características exigidas por el cliente deberá pasar controles de calidad altos. Esto hace que la empresa estime que la probabilidad de que un artículo producido sea considerado bueno es 2/3 (66.6667%) y de 1/3 (33.3333%) que sea considerado malo sin posibilidad de recuperarlo o arreglarlo. El plazo que tiene la empresa para obtener al menos un artículo bueno es de 3 días, y la producción del artículo implica ocupar el día en hacer andar la línea de producción, fabricarlos y finalmente ver si salieron buenos; por lo que la empresa tiene 3 intentos de fabricación para obtener el artículo bueno.

Por contrato con el cliente se acuerda que si la empresa no obtiene el artículo bueno en los 3 días, en los 3 intentos, la empresa deberá pagar una multa de $200 al cliente por indemnización o pérdida de tiempo.

También la empresa sabe que cada día que decide elaborar ese producto incurre en un costo fijo de $20 por iniciar toda la línea de producción ese día, y tiene un costo de $5 por cada unidad que decida fabricar.

Se pide encontrar la política óptima a seguir por la empresa en cuanto a la producción de este artículo, para hacer mínimo el costo total de producción y obtener al menos un artículo de buena calidad, según lo exigido.

Solución:

Etapas: Días de producción. (3 etapas).

Estados: Número de artículos buenos que se tiene la obligación de obtener.

0 : indica que en esa etapa no se tiene la obligación de obtener un artículo bueno.

1 : indica que en esta etapa sí se tiene la obligación de obtener un artículo bueno.

Decisión: Cantidad de artículos que se deberán fabricar en esa etapa.

Costo por día: =  K(x_i)+5x_i , donde: K=0 si x_i=0, y K=20 si x_i>0

Para cada artículo que se produzca la probabilidad de que salga bueno es 2/3, y que salga malo es 1/3 (datos del problema). Por lo que, si produce 2 artículos la probabilidad de que los 2 salgan malos es: (1/3)*(1/3) = (1/3)². Si decide producir 3 artículos, la probabilidad de que los 3 salgan malos es de (1/3)³, Generalizando, si se decide fabricar x_i artículos, entonces la probabilidad de que todos salgan malos es: (1/3)^xi

Función recursiva:

Para cualquiera de las etapas contendrá lo que representa el costo de esa etapa más el costo probable de la etapa siguiente si todos hubiesen salido malos, y más el costo probable de la etapa siguiente si no todos hubiesen salidos malos (al menos uno salió bueno). Y en la etapa n-ésima tendremos el estado 0 y el estado 1. Tomemos el estado 1 para f.

f_n (1,x_n )=K(x_n )+5x_n+(1⁄3)^(x_n ) f_(n+1) (1)+〖(1-(1⁄3)〗^(x_n ))f_(n+1) (0)

donde:

K(x_n)                      : es el costo de producción fijo de $0 o de $200, según ese día produzca artículos o no.

5x_n                          : representa el costo de $5 por unidad que se decida producir.

(1/3)^xn                    : representa la probabilidad de que los x_n artículos salgan malos.

f_n+1(1)                                    : es el costo que se tendrá en la etapa siguiente, si se llega a ella con la obligación de

  obtener un artículo bueno. Este valor es: f^*_n+1(1).

(1/3)^xnf_n+1(1)          : es el costo probable desde la etapa siguiente en adelante, si todos los de esta etapa

                  salen malos.

(1-(1/3)^xn)              : es la probabilidad de que no todos los x_n artículos salgan malos; alguno sale bueno.

f_n+1(0)                     : es el costo en que se incurrirá desde la etapa siguiente, si se llega a ella al estado 0, es

                                 decir sin la necesidad de producir un artículo bueno, porque ya se obtuvo. Es f^*_n+1(0)

(1-(1/3)^xn)f_n+1(0)   : es el costo probable desde la etapa siguiente, si en esta etapa sale alguno de los

  artículos bueno.

En el problema aquí dado, se tiene que f^*_n+1(0) es cero, porque es cero el costo más bajo si no se tiene la obligación de producir un artículo bueno, en cualquiera de las etapas. La etapa 1 tiene como estado inicial: 1; es decir, en la etapa 1 se tiene la obligatoriedad de obtener un artículo bueno.

ETAPA 3
s3	f3(s3,x3) = K(x3)+5x3						Solución óptima
	x3=0	x3=1	x3=2	x3=3	x3=4	x3=5	f*3	x*3
0	0	-	-	-	-	-	0	0
1	200	91.6666667	52.2222222	42.4074074	42.4691358	45.8230453	42.4074074	3

Detalle de los cálculos:

f₃(1,0) =   0 + 5*0 + (1/3)⁰*200 = 200

f₃(1,1) = 20 + 5*1 + (1/3)¹*200 = 91.6666667

f₃(1,2) = 20 + 5*2 + (1/3)²*200 = 52.2222222

f₃(1,3) = 20 + 5*3 + (1/3)³*200 = 42.4074074 (el costo probable sólo se reduce hasta aquí)

f₃(1,4) = 20 + 5*4 + (1/3)⁴*200 = 42.4691358 (no considerar)

f₃(1,5) = 20 + 5*5 + (1/3)⁵*200 = 45.8230453 (no considerar)

ETAPA 2
s2	f2(s2,x2) = K(x2) + 5x2 + (1/3)x2f*3(1) + (1-(1/3)x2)f*3(0)						Solución óptima
	x2=0	x2=1	x2=2	x2=3	x2=4	x2=5	f*2	x*2
0	0	-	-	-	-	-	0	0
1	42.4074074	39.1358025	34.7119342	36.5706447	40.5235482	45.1745161	34.7119342	2

Detalle de los cálculos:

f₂(1,0) =   0 + 5*0 + (1/3)⁰*42.4074074 = 42.4074074

f₂(1,1) = 20 + 5*1 + (1/3)¹*42.4074074 = 39.1358025

f₂(1,2) = 20 + 5*2 + (1/3)²*42.4074074 = 34.7119342 (el costo probable sólo se reduce hasta aquí)

f₂(1,3) = 20 + 5*3 + (1/3)³*42.4074074 = 36.5706447 (no considerar)

f₂(1,4) = 20 + 5*4 + (1/3)⁴*42.4074074 = 40.5235482 (no considerar)

f₂(1,5) = 20 + 5*5 + (1/3)⁴*42.4074074 = 45.1745161 (no considerar)

ETAPA 1
s1	f1(s1,x1) = K(x1) + 5x1 + (1/3)x1f*2(1) + (1-(1/3)x1)f*2(0)						Solución óptima
	x1=0	x1=1	x1=2	x1=3	x1=4	x1=5	f*1	x*1
1	34.7119342	36.5706447	33.8568816	36.2856272	40.4285424	45.1428475	33.8568816	2

Detalle de los cálculos:

f₁(1,0) =   0 + 5*0 + (1/3)⁰*34.7119342 = 34.7119342

f₁(1,1) = 20 + 5*1 + (1/3)¹*34.7119342 = 36.5706447

f₁(1,2) = 20 + 5*2 + (1/3)²*34.7119342 = 33.8568816 (el costo probable sólo se reduce hasta aquí)

f₁(1,3) = 20 + 5*3 + (1/3)³*34.7119342 = 36.2856272 (no considerar)

f₁(1,4) = 20 + 5*4 + (1/3)⁴*34.7119342 = 40.4285424 (no considerar)

f₁(1,5) = 20 + 5*5 + (1/3)⁵*34.7119342 = 45.1428475 (no considerar)

Costo Mínimo Probable: 33.8568816

Solución óptima: x₁ = 2, x₂ = 2, x₃ = 3

PROBLEMA 4

Se debe fabricar un artículo con altas exigencias de calidad y se ha estimado que la probabilidad de que apruebe el nivel de calidad y salga bueno es de sólo 1/5 (20%) y los artículos malos son sin posibilidad de recuperación. Poner en marcha las maquinarias un día para producir tiene un costo de $700 y el costo por unidad que se decida producir es de $50, y se dispone de 3 días.

Si no se logra producir un artículo bueno en los 3 días, por contrato deberá pagarse una multa de $2100. ¿Cuál es la política de producción más conveniente a seguir durante estos 3 días para lograr al menos un artículo bueno? ¿Cuál debe ser el piso para el precio de venta de ese artículo bueno que se produzca?

ETAPA 3
s3	f3(s3,x3) = K(x3)+50x3											Solución óptima
	x3=0	x3=1	x3=2	x3=3	x3=4	x3=5	x3=6	x3=7	x3=8	x3=9	x3=10	f*3	x*3
0	0	-	-	-	-	-	-	-	-	-	-	0	0
1	2100	2430	2144	1925.2	1760.16	1638.128	1550.502	1490.402	1452.322	1431.857	1425.486	1425.5	10

ETAPA 2
s2	f2(s2,x2) = K(x2) + 50x2 + (4/5)x2f*3(1) + (1-(4/5)x2)f*3(0)									Solución óptima
	x2=0	x2=1	x2=2	x2=3	x2=4	x2=5	x2=6	x2=7	x2=8	f*2	x*2
0	0	-	-	-	-	-	-	-	-	0	0
1	1425.486	1890.389	1712.311	1579.849	1483.879	1417.103	1373.683	1348.946	1339.157	1339.157	8

ETAPA 1
s1	f1(s1,x1) = K(x1) + 50x1 + (4/5)x1f*2(1) + (1-(4/5)x1)f*2(0)									Solución óptima
	x1=0	x1=1	x1=2	x1=3	x1=4	x1=5	x1=6	x1=7	x1=8	f*1	x*1
1	1339.157	1821.325	1657.06	1535.648	1448.519	1388.815	1351.052	1330.842	1324.673	1324.673	8

Respuesta 1: La política de producción más conveniente a seguir durante estos 3 días para lograr al menos un artículo bueno es: Producir 8 artículos el día 1, y si salen todos malos, el día 2 producir 8 artículos, y si salen todos malos, producir 10 el día 3.

Respuesta 2: El piso para el precio de venta de ese artículo bueno que se produzca es: $1324.673

También podemos responder que:

El Costo Mínimo Probable es: $1324.673, y que la solución óptima es: x₁ = 8 ,  x₂ = 8 ,  x₃ = 10