Investigación Operativa II. 1ª Edición

INVESTIGACIÓN OPERATIVA II 1ª Edición Juan Eloy Ruiz Castro Doctor en Ciencias Matemáticas INVESTIGACIÓN OPERATIVA II 1ª Edición Juan Eloy Ruiz Castro Edita: GODEL Impresiones Digitales SL I.S.B.N.: 978-84-17970-93-2 Depósito Legal: GR 134-2020 C/ Severo Ochoa-Campus Fuentenueva Teléfono: 676430427 e-mail.: [email protected] A mi familia Esta publicación es fruto de la impartición de la asignatura Investigación Operativa II durante años. No pretende ser un libro como tal, es la presentación de dicha asignatura que sirve como apoyo al alumno con un carácter inminentemente práctico. El autor ÍNDICE Capítulo 1. Programación dinámica determinística 1.1. Introducción 1.2. El problema de la mochila/equipo de vuelo/carga del conector 1.3. Modelo para determinar número de trabajadores 1.4. Modelo de reposición de equipo 1.5. Modelo de inversión 1.6. Resolución de un problema lineal mediante programación dinámica Capítulo 2. PROGRAMACIÓN DINÁMICA PROBABILÍSTICA 2.1. Ganadora en Las Vegas 2.2. Optimización del valor esperado. Un juego aleatorio 2.3. PROBLEMA DE INVERSIÓN 2.4. Maximización de la probabilidad de lograr un ingreso 2.5. Más ejercicios 1 1 8 21 35 46 69 87 87 100 108 120 126 Juan Eloy Ruiz Castro 4 Etapa 3: nodo extremo 7 f3(7) = min{ f2(5) + d(5, 7), f2(6) + d(6, 7) }= min{ 12 + 9, 17 + 6} = 21 Y este mínimo se alcanza desde el nodo 5. Por lo tanto se tiene en global, desde el nodo inicial que tras esta etapa La distancia más corta al nodo 7 viene dada por f3(7) = 21 estando el camino formado por los nodos 1→4→5→7. Juan Eloy Ruiz Castro 5 Expresión mediante tablas d(x0, x1) x1 = 2 x1 = 3 x1 = 4 x0=1 7 8 5 Solución Óptima f1(x1) 7 8 5 1 1 1 Etapa 1 Etapa 2 Etapa 3 f1(x1)+d(x1, x2) x2 = 5 x2 = 6 x1 = 2 x1 = 3 x1 = 4 7 + 12 8 + 8 5 + 7 −−−−−− 8 + 9 5 + 13 Solución Óptima f2(x2) 12 17 4 3 * 1 x f2(x2)+d(x2, x3) x3 = 7 x2 = 5 x2 = 6 12 + 9 17 + 6 Solución Óptima f3(x3) 21 5 * 2 x * 0 x Juan Eloy Ruiz Castro 6 Cálculos recursivos para el problema ( ) ( ) ( ) ( )   1 1 1 1 odas las rutas , posibles min , ; 1 ii i i i i i i txx f x f x d x x i − − − − = +  siendo f0(x0) = 0. Principio de optimalidad.La política óptima futura es independiente de las políticas pasadas. •La resolución de este ejercicio se ha realizado de forma directa (forward), los cálculos se hacen de la etapa 1 a la 3. •Pero, aunque este procedimiento parece más lógico, es habitual resolver de forma inversa (backward) el problema. •En ambos casos la solución es la misma. •Motivo: la recursión es más eficiente desde el punto vista computacional. Juan Eloy Ruiz Castro 7 ( ) ( ) ( ) ( )   1 1 1 1 odas las rutas , posibles min , ; 3,2,1. ii i i i i i i txx f x f x d x x i + + + + = + = siendo f4(x4) = 0. Etapa 3. d(x3, x4)Solución óptima x3x4=7 f3(x3) 5 6 9 6 9 6 7 7 * 4 x Etapa 2. d(x2, x3)+ f3(x3)Solución óptima x2x3=5 x3=6 f2(x2) 2 3 4 12 + 9=21 8 + 9=17 7 + 9=16 --------- 9 + 6=15 13 + 6=19 21 15 16 5 6 5 * 3 x Etapa 1. d(x1, x2)+ f2(x2)Solución óptima x1x2=2 x2=3 x2=4 f1(x1) 1 7 + 21 = 28 8 + 15=23 5 + 16=21 21 4 * 2 x 1→4→5→7 x1 x2x3 x4 Juan Eloy Ruiz Castro 8 1.2. El problema de la mochila/equipo de vuelo/carga del conector Este problema es un modelo de asignación de recursos con distintas alternativas con objeto de maximizar el ingreso total. Por ejemplo, qué artículos deben considerarse meter en una mochila limitada para obtener un beneficio máximo. Consideramos una mochila de peso máximo Wcon capacidad para ntipos de artículos. Sea mila cantidad de unidades de tipo ien la mochila y riywiel ingreso y el peso por unidad del artículo irespectivamente. El problema que se presenta es el siguiente Maximizar z=r1m1+r2m2+…+ rnmn s.a. w1m1+w2m2+…+ wnmn≤W mi≥ 0 enteros para todo i. Juan Eloy Ruiz Castro 9 Elementos del modelo •La etapa ies el artículo i. (netapas) • Las alternativas en la etapa ison mi= 0, 1, …, Ent(W/wi) •El estado de la etapa i(xi)es el peso total asignado a las etapas de ien adelante (artículos). Es decir 1i i i i x x wm + =+ . fi(xi) : ingreso máximo para los artículos i,i+ 1 … ndado el estado xi(peso). Algoritmo recursivo ( ) ( )   ( ) 11 0,1, , 11 max ; 1,2, , 0 ii i i i i i i i W m Ent w xW nn f x rm f x i n fx ++  =   ++ = + = = Juan Eloy Ruiz Castro 10 Por definición: 1i i i i x x wm + =+ ( ) ( )   ( ) 11 0,1, , 11 max ; 1,2, , 0 ii i i i i i i i W m Ent w xW nn f x rm f x i n fx ++  =   ++ = + = = ( ) ( )   ( ) 1 0,1, , 11 max ; 1,2, , 0 ii i i i i i i i i i W m Ent w xW nn f x rm f x wm i n fx +  =   ++ = + − = = Juan Eloy Ruiz Castro 11 Ejemplo. Un barco de 4 toneladas se carga con uno o más de tres artículos. La siguiente tabla muestra el peso unitario en toneladas (wi) y el ingreso en miles de euros por unidad, ri, del artículo i. ¿Cómo se deberá cargar el barco para obtener el máximo beneficio? Artículo i wiri 1 2 3 2 3 1 31 47 14 Solución Etapa 3. Artículo 3. El peso total exacto del artículo 3 no es conocido, por lo que x3ym3puede tomar los valores enteros 0, 1, 2, 3, 4 que es la capacidad del barco. Por lo tanto, ¿cuántos artículos pueden tomarse del artículo 3? Cada artículo 3 tiene un peso w3=1, por lo que a lo sumo puede haber Ent(4/1) = 4 artículos tipo 3. El cuadro siguiente muestra las alternativas para esta etapa. Juan Eloy Ruiz Castro 12 r3m3= 14m3 Solución óptima x3m3=0 m3=1 m3=2 m3=3 m3=4 f3(x3) 0 1 2 3 4 0 0 0 0 0 --- 14 14 14 14 --- --- 28 28 28 --- --- --- 42 42 --- --- --- --- 56 0 14 28 42 56 0 1 2 3 4 * 3 m Etapa 2. Artículo 2 r2m2+f3(x2-w2m2) 47m2+f3(x2-3m2) Solución óptima x2m2=0 m2=1 f2(x2) 0 1 2 3 4 0 + 0 0+14 0+28 0+42 0+56 --- --- --- 47 + 0 47 + 14 0 14 28 47 61 0 0 0 1 1 * 2 m Etapa 1. Artículo 1 r1m1+f2(x1-w1m1) = 31m1+f2(x1-2m1) Solución óptima x1m1=0 m1=1 m1=2 f1(x1) 0 1 2 3 4 0 0+14 0+28 0+47 0+61 --- --- 31+0=31 31+14=45 31+28=59 --- --- --- --- 62+0 0 14 31 47 62 0 0 1 0 2 * 1 m Etapa 3. Artículo 3. Juan Eloy Ruiz Castro 13 Ejercicio. Realizar el ejercicio anterior considerando la capacidad del barco igual a 3 toneladas W=3. * 3 m Etapa 2. Artículo 2 r2m2+f3(x2-w2m2) 47m2+f3(x2-3m2) Solución óptima x2m2=0 m2=1 f2(x2) 0 1 2 3 0 14 28 42 --- --- --- 47+0=47 0 14 28 47 0 0 0 1 * 2 m Etapa 1. Artículo 1 r1m1+f2(x1-w1m1) = 31m1+f2(x1-2m1) Solución óptima x1m1=0 m1=1 f1(x1) 0 1 2 3 0 14 28 47 --- --- 31+0=31 31+14=45 0 14 31 47 0 0 1 0 * 1 m Un artículo tipo 2 Beneficio: 47 r3m3= 14m3 Solución óptima x3m3=0 m3=1 m3=2 m3=3 f3(x3) 0 1 2 3 0 ---- ---- ---- ---- 14 ---- ---- --- --- 28 ---- --- --- --- 42 0 14 28 42 0 1 2 3 Etapa 3. Artículo 3. Juan Eloy Ruiz Castro 20 x1f1(x1) 1.75 2 2.25 2.5 2.75 3 12 16 17 21 22 26 1 1 1 1 1 1 Etapa 1. Artículo 1. Alimentos: 1 Botiquines: 2 Ropa: 3 Beneficio: 26 Etapa 2. Artículo 2. x2f2(x2) 2 2.25 2.5 2.75 3 23 24 28 29 33 2 1 2 1 2 * 1 m * 2 m Artículos wiri 1: Alimentos 1 3 2: Botiquín 0.25 4 3: Ropa 0.5 5 x3 f 3(x3 ) 0.5 1 1.5 2 2. 5 3 5 10 15 20 25 30 1 2 3 4 5 6 * 3 m Etapa 3. Artículo 3. Juan Eloy Ruiz Castro 21 1.3. Modelo para determinar número de trabajadores En una empresa, contrataciones y despidos se realizan de forma que las necesidades se mantengan. Tanto contrataciones como despidos implican costos adicionales, entonces, ¿cuál es la política a seguir? Supongamos que analizamos el comportamiento durante un tiempo ndiscreto (n semanas), y que durante la semana ise requiere al menos una cantidad de trabajo bi(en unidades de personal) y hay xitrabajadores. En esta semana se producen dos tipos de costos: costo de mantenimiento de exceso de personal, C1(xi − bi), y costo de contratación, C2(xi − xi−1). Juan Eloy Ruiz Castro 22 Elementos del modelo •La etapa ies la semana. (nsemanas) • Las alternativas en la etapa ison xi •El estado de la etapa ies la cantidad de trabajadores disponibles en la etapa i-1; 1i x− . fi(xi−1) : costo mínimo dado el estado xi − 1(número de trabajadores la semana i−1). Algoritmo recursivo ( ) ( ) ( ) ( )   ( ) 1 1 2 1 1 1 mín ; 1,2, , 0 ii i i i i i i i i xb nn f x C x b C x x f x i n fx − − +  + = − + − + = = Juan Eloy Ruiz Castro 23 Ejemplo. Un constructor estima que en las próximas semanas necesitará como mínimo 5, 7, 8, 4 y 6 trabajadores respectivamente. Cada trabajador en exceso tiene un coste semanal de 300 euros y la contratación nueva tiene un coste fijo de 400 euros (independiente del número de trabajadores que se contrate) más 200 euros para cada trabajador nuevo contratado. ¿Cuántos trabajadores debe contratar y despedir semanalmente? Solución. En este caso se tienen los siguientes valores para los parámetros: b1= 5 ; b2= 7 ; b3= 8 ; b4= 4 ; b5= 6 C1(xi−bi) = 3(xi−bi), xi>bipara i= 1,2 …, 5. C2(xi−xi−1) = 4+2(xi−xi−1), xi>xi−1para i= 1,2 …, 5. Juan Eloy Ruiz Castro 24 Solución óptima x4x5=6 f5(x4) 4 5 6 4+4=8 4+2=6 0 8 6 0 6 6 6 ( ) ( ) ( ) 1 5 5 2 5 4 6 5 C x b C x x f x− + − + ( ) ( ) 5 5 4 3 6 4 2x x x− + + − * 5 x Etapa 5. b5= 6 Solución óptima x3x4=4 x4=5 x4=6 f4(x3) 8 3*0+0+8=8 3+6=9 6+0=6 6 6 ( ) ( ) ( ) 1 4 4 2 4 3 5 4 C x b C x x f x− + − + ( ) ( ) ( ) 4 4 3 5 4 3 4 4 2x x x f x− + + − + * 4 x Etapa 4. b4= 4 b1= 5 ; b2= 7 ; b3= 8 ; b4= 4 ; b5= 6 Juan Eloy Ruiz Castro 25 Etapa 3. b3= 8 Solución óptima x2x3=8 f3(x2) 7 8 0+6+6=12 0+0+6=6 12 6 8 8 ( ) ( ) ( ) 1 3 3 2 3 2 4 3 C x b C x x f x− + − + ( ) ( ) ( ) 3 3 2 4 3 3 8 4 2x x x f x− + + − + * 3 x Etapa 2. b2= 7 Solución óptima x1x2=7 x2=8 f2(x1) 5 6 7 8 8+12=20 6+12=18 12 12 3+10+6=19 3+8+6=17 3+6+6=15 3+6=9 19 17 12 9 8 8 7 8 ( ) ( ) ( ) 1 2 2 2 2 1 3 2 C x b C x x f x− + − + ( ) ( ) ( ) 2 2 1 3 2 3 7 4 2x x x f x− + + − + * 2 x b1= 5 ; b2= 7 ; b3= 8 ; b4= 4 ; b5= 6 Juan Eloy Ruiz Castro 26 Etapa 1. b1= 5 Solución óptima x0x1=5 x1=6 x1=7 x1=8 f1(x0) 0 14+19=33 3+16+17 =36 6+18+12 =36 9+20+9= 38 33 5 ( ) ( ) ( ) 1 1 1 2 1 0 2 1 C x b C x x f x− + − + ( ) ( ) ( ) 1 1 0 2 1 3 5 4 2x x x f x− + + − + * 1 x Por lo tanto, se contratan para la primera semana a 5, la segunda semana a 3 más, la tercera semana nos quedamos igual, la cuarta semana se despiden 2 trabajadores y la última semana tampoco se cambia. b1= 5 ; b2= 7 ; b3= 8 ; b4= 4 ; b5= 6 Juan Eloy Ruiz Castro 27 Ejercicio. Un constructor estima que en las próximas semanas necesitará como mínimo 5, 7, 8, 4 y 6 trabajadores respectivamente. Cada trabajador en exceso tiene un coste semanal de 300 euros y la contratación nueva tiene un coste fijo de 400 euros (independiente del número de trabajadores que se contrate). Cada semana un trabajador cobra un sueldo de 200 euros. ¿Cuántos trabajadores debe contratar y despedir semanalmente? Solución. b1= 5 ; b2= 7 ; b3= 8 ; b4= 4 ; b5= 6 C1(xi−bi) = 3(xi−bi), xi>bipara i= 1,2 …, 5. C2= 4 si xi>xi -1;C3(xi) = 2xi, para i= 1,2 …, 5. Juan Eloy Ruiz Castro 28 Solución óptima x4x5=6 f5(x4) 4 5 6 4+12 = 16 4+12 = 16 12 16 16 12 6 6 6 * 5 x Etapa 5. b5= 6 Solución óptima x3x4=4 x4=5 x4=6 f4(x3) 88+16=24 3+10+16=29 6+12+12=30 24 4 * 4 x Etapa 4. b4= 4 b1= 5 ; b2= 7 ; b3= 8 ; b4= 4 ; b5= 6 ( ) ( ) ( ) 1 5 5 2 3 5 6 5 C x b C C x f x− + + + ( ) ( ) ( ) 1 4 4 2 3 4 5 4 C x b C C x f x− + + + Juan Eloy Ruiz Castro 29 Etapa 3. b3= 8 Solución óptima x2x3=8 f3(x2) 7 8 4+16+24 = 44 16+24 = 40 44 40 8 8 * 3 x Etapa 2. b2= 7 Solución óptima x1x2=7 x2=8 f2(x1) 5 6 7 8 4+14+44 = 62 4+14+44 = 62 14+44 = 58 14+44 = 58 3+4+16+40 =63 3+4+16+40 = 63 3+4+16+40 = 63 3+16+40 = 59 62 62 58 58 7 7 7 7 * 2 x b1= 5 ; b2= 7 ; b3= 8 ; b4= 4 ; b5= 6 ( ) ( ) ( ) 1 3 3 2 3 3 4 3 C x b C C x f x− + + + ( ) ( ) ( ) 1 2 2 2 3 2 3 2 C x b C C x f x− + + + Juan Eloy Ruiz Castro 36 Elementos del modelo •La etapa ies el período (año) • Las alternativas en la etapa ison reemplazar o conservar la máquina al comienzo del período •El estado de la etapa ies la antigüedad de la máquina al comienzo del período i . fi(t) : ingreso neto máximo para los años i, i+1, …, ndado que la máquina tiene t años de antigüedad al comienzo del período i. Algoritmo recursivo ( ) ( ) ( ) ( ) 1 1 1 ( ) ( ) 1 ; si se conserva máx (0) ( ) (0) 1 ; si se reemplaza 0 i i i n r t c t f t ft r s t I c f f + + + − + +   =+ − − +   = Juan Eloy Ruiz Castro 37 Ejemplo Un empresa debe determinar la política óptima, durante los próximos cuatro años, de reemplazo de una máquina que en la actualidad tiene 3 años. Toda máquina que tenga 6 años debe reemplazarse siendo el costo de una máquina igual a 100000 euros. La siguiente tabla recoge más datos: Tiempo taños Ingreso r(t) Costo c(t) Ingreso por venta s(t) 0 1 2 3 4 5 6 20000 19000 18500 17200 15500 14000 12200 200 600 1200 1500 1700 1800 2200 −− 80000 60000 50000 30000 10000 5000 Juan Eloy Ruiz Castro 38 Solución Gráfico con la trayectoria de los tiempos Etapa 4. Si actualmente la máquina tiene 3 años, al comienzo de la última etapa (transcurridos 3 años) la máquina resultante debe tener 6 años, 3, 2 o 1 año según si se reemplaza transcurridos 3, 1, 2 u ocurren dos reemplazamientos NR RSolución óptima t r(t)+s(t+1)-c(t)r(0)+s(t)+s(1)-c(0)-I f4(t) Decisión 1 2 3 6 19+60-0.6=78.4 18.5+50-1.2=67.3 17.2+30-1.5=45.7 Se debe reemplazar 20+80+80−0.2−100=79.8 20+60+80−0.2−100=59.8 20+50+80−0.2−100=49.8 20+5+80−0.2−100=4.8 79.8 67.3 49.8 4.8 R NR R R Juan Eloy Ruiz Castro 39 NR RSolución óptima t r(t)−c(t)+f4(t+1) r(0)+s(t) -c(0)-I+f4(1) f3(t) Decisión 1 2 5 19−0.6+67.3=85.7 18.5−1.2+49.8=67.1 14−1.8+4.8=17 20+80 −0.2− 100+79.8=79.6 20+60 −0.2− 100+79.8=59.6 20+10−0.2−100+79.8=9.6 85.7 67.1 17 NR NR NR Etapa 3. NR RSolución óptima t r(t)−c(t)+f3(t+1) r(0)+s(t) -c(0)-I+f3(1) f2(t) Decisión 1 4 19−0.6+67.1=85.5 15.5−1.7+17=30.8 20+80 −0.2− 100+85.7=85.5 20+30−0.2-100+85.7=35.5 85.5 35.5 R ó NR R Etapa 2. NR RSolución óptima t r(t)−c(t)+f2(t+1) r(0)+s(t) -c(0)-I+f2(1) f1(t) Decisión 3 17.2−1.5+35.5=54.2 20+50−0.2−100+85.5=55.3 55.3 R Etapa 1. Beneficio máximo final: 55300 euros Solución: R→R→NR→NR→Vender R→NR→NR→NR→Vender Juan Eloy Ruiz Castro 40 Ejercicio. Una empresa posee un tractor de 2 años de antigüedad y desea establecer una política de reemplazamiento durante los 5 años siguientes. Estos tractores deben estar en servicio al menos durante 3 años pero tras 5 años deben ser desechados. El precio actual de un tractor es de 40000 euros disminuyendo un 10% por año. El beneficio anual de un tractor nuevo es de 30000 euros disminuyendo por año de antigüedad un 10%. El costo anual de operación de un tractor nuevo es de 1300 euros esperando un aumento anual por antigüedad del 10%. ¿Cómo debe actuar la empresa? 2 1 3 4 5 6 1 2 3 4 5 6 Año de decisión Años de la máquina 2 1 3 4 3 2 1 4 1 3 5 1 22Vendo Juan Eloy Ruiz Castro 41 T antigüedad s(t)c(t)r(t) 0 1 2 3 4 5 40 36 32.4 29.16 26.244 23.6196 1.3 1.43 1.573 1.7303 1.90333 2.093663 30 27 24.3 21.87 19.683 17.7147 I = 40 NR RSolución óptima tr(t)+s(t+1)-c(t)r(0)+s(t)+s(1)-c(0)-I f5(t) Decisión 1 2 3 27+32.4-1.43=57,97 24.3+29.16-1.573=51,887 21.87+26.244 - 1.7303=46.3837 No se reemplaza No se reemplaza 30+29,16+36-1.3-40=53,86 57.97 51.887 53,86 NR NR R Etapa 5 Juan Eloy Ruiz Castro 42 NR RSolución óptima t r(t)−c(t)+f5(t+1) r(0)+s(t) -c(0)-I+f5(1)f4(t) Decisión 1 2 5 27-1.43+51.887=77.457 24.3 - 1.573+53.86=76.587 Se reemplaza No se reemplaza No se reemplaza 30+23.6196 -1.3- 40+57.97= 70.2896 77.457 76.587 70.2896 NR NR R Etapa 4 T antigüedad s(t)c(t)r(t) 0 1 2 3 4 5 40 36 32.4 29.16 26.244 23.6196 1.3 1.43 1.573 1.7303 1.90333 2.093663 30 27 24.3 21.87 19.683 17.7147 I = 40 f5(t) 57.97 51.887 53,86 t 1 2 3 Juan Eloy Ruiz Castro 43 NR RSolución óptima t r(t)−c(t)+f4(t+1)r(0)+s(t) -c(0)-I+f4(1)f3(t) Decisió n 1 4 27-1.43+76.587=102.157 19.683- 1.90333+70.2896=88.06927 No se reemplaza 30+26.244-1.3- 40+77.457=92.401 102.157 92.401 NR R Etapa 3 T antigüedad s(t)c(t)r(t) 0 1 2 3 4 5 40 36 32.4 29.16 26.244 23.6196 1.3 1.43 1.573 1.7303 1.90333 2.093663 30 27 24.3 21.87 19.683 17.7147 I = 40 f4(t) 77.457 76.587 70.2896 t 1 2 5 Juan Eloy Ruiz Castro 44 NR RSolución óptima t r(t)−c(t)+f3(t+1)r(0)+s(t) -c(0)-I+f3(1)f2(t) Decisió n 3 21.87- 1.7303+92.401=112.540 7 30+29.16-1.3- 40+102.157=120.017 120.01 7 R Etapa 2 T antigüedad s(t)c(t)r(t) 0 1 2 3 4 5 40 36 32.4 29.16 26.244 23.6196 1.3 1.43 1.573 1.7303 1.90333 2.093663 30 27 24.3 21.87 19.683 17.7147 I = 40 f3(t) 102.157 92.401 t 1 4 Juan Eloy Ruiz Castro 45 NR RSolución óptima t r(t)−c(t)+f2(t+1)r(0)+s(t) -c(0)-I+f2(1)f1(t) Decisió n 2 24.3- 1.573+120.017=142.744 No se puede reemplazar 142.744 NR Etapa 1 T antigüedad s(t)c(t)r(t) 0 1 2 3 4 5 40 36 32.4 29.16 26.244 23.6196 1.3 1.43 1.573 1.7303 1.90333 2.093663 30 27 24.3 21.87 19.683 17.7147 I = 40 f2(t) 120.01 7 t 3 Beneficio máximo final: 142744 euros Solución: NR→R→NR→NR→R →Vender Juan Eloy Ruiz Castro 52 ( ) ( )   33 3 3 3 4 4 0Ix f x máx s f x  =+ ( ) ( ) ( ) ( ) ( ) 2 2 2 3 1 2 3 2 3 2 2 2 33 33 1 1 1 1.08 1.078 1.078 0.00432 1.162084 s r r I r x Ix Ix = + − + + + = − + =+ Etapa 3 siendo La cantidad de capital disponible para el año 4 es: xi= Pi+ qi−1,1Ii−1+ qi−1,2 (xi−1−Ii−1) = Pi+ (qi−1,1−qi−1,2) Ii−1+qi−1,2 xi−1 x4= P4+ (q3,1−q3,2)I3+ q3,2 x3 = 2000 −0.005 I3 + 0.026x3 ( )   33 3 3 4 4 00.00432 1.162084 Ix máx I x f x  = + + Juan Eloy Ruiz Castro 53 3 2216 1.1909x+ La cantidad de capital disponible para el año 4 es: xi= Pi+ qi−1,1Ii−1+ qi−1,2 (xi−1−Ii−1) = Pi+ (qi−1,1−qi−1,2) Ii−1+qi−1,2 xi−1 x4= P4+ (q3,1−q3,2)I3+ q3,2 x3 = 2000 −0.005 I3 + 0.026x3 Por lo tanto ( ) ( )   33 3 3 3 3 4 3 3 00.00432 1.162084 2000 0.005 0.026 Ix f x máx I x f I x  = + + − + ( )   33 3 3 3 3 3 3 00.00432 1.162084 2216 0.00554 0.028808 Ix f x máx I x I x  = + + − + El máximo se alcanza en I3= 0. Solución óptima Estado f3(x3) x30 ( )   33 3 3 3 3 02216 0.00122 1.1909 Ix f x máx I x  = − + ( ) ( )   33 3 3 3 3 3 3 00.00432 1.162084 1.108 2000 0.005 0.026 Ix f x máx I x I x  = + +  − + * 3 I Juan Eloy Ruiz Castro 54 ( ) ( )   22 2 2 2 3 3 0Ix f x máx s f x  =+ ( ) ( ) ( ) ( ) ( ) 3 3 3 2 1 2 2 2 2 3 3 3 22 22 1 1 1 1.08 1.078 1.078 0.0069854481 1.252726552 s r r I r x Ix Ix = + − + + + = − + =+ Etapa 2 siendo La cantidad de capital disponible para el año 3 es: xi=Pi+ (qi−1,1−qi−1,2)Ii−1+qi−1,2 xi−1 x3=P3+ (q2,1−q2,2)I2+q2,2 x2=2000 −0.005 I2+ 0.022x2 ( )   22 2 2 3 3 00.0069854481 1.252726552 Ix máx I x f x  = + + Juan Eloy Ruiz Castro 55 La cantidad de capital disponible para el año 3 es: xi=Pi+ (qi−1,1−qi−1,2)Ii−1+qi−1,2 xi−1 x3=P3+ (q2,1−q2,2)I2+q2,2 x2=2000 −0.005 I2+ 0.022x2 ( ) ( )   22 2 2 2 2 3 2 2 00.006985 1.25273 2000 0.005 0.022 Ix f x máx I x f I x  = + + − + ( ) ( )   22 2 2 2 2 2 2 00.006985 1.25273 2216 1.1909 2000 0.005 0.022 Ix f x máx I x I x  = + + + − + ( )   22 2 2 2 2 04597.8 0.0010305 1.27893 Ix f x máx I x  = + + Por lo tanto El máximo se alcanza en I2=x2. Solución óptima Estado f2(x2) x2x2 * 2 I 2 4597.8 1.27996x+ Juan Eloy Ruiz Castro 56 ( ) ( )   11 1 1 1 2 2 0Ix f x máx s f x  =+ ( ) ( ) ( ) ( ) ( ) 4 4 4 1 1 2 1 2 1 4 4 4 11 11 1 1 1 1.08 1.078 1.078 0.010049737 1.350439223 s r r I r x Ix Ix = + − + + + = − + =+ Etapa 1 siendo ( ) ( )   11 1 1 1 1 2 1 1 00.010049737 1.350439223 2000 0.005 0.023 Ix f x máx I x f I x  = + + − + ( )   11 1 1 1 1 07157.7 0.00365 1.37984 Ix f x máx I x  = + + La cantidad de capital disponible para el año 2 es: xi= Pi+ (qi−1,1−qi−1,2) Ii−1+ qi−1,2 xi−1 x2= P2+ (q1,1−q1,2)I1+ q1,2 x1= 2000 −0.005 I1+ 0.023x1 Por lo tanto ( )   11 1 1 2 2 00.010049737 1.350439223 Ix máx I x f x  = + + ( ) 2 2 2 4597.8 1.27996f x x=+ Juan Eloy Ruiz Castro Por lo tanto se tiene que: I1= 4000; I2= x2; I3= 0; I4= 0 x1= 4000 x2= 2000 −0.005 I1+ 0.023x1= 2072 x3= 2000 −0.005 I2 + 0.022x2= 2035.22 x4= 2000 + 0.026x3= 2052.92 Acumulación final: s1+s2+s3+s4= 12691.70 euros 57 El máximo se alcanza en I1=x1. Solución óptima Estado f1(x1) x1=4000 7157.7+1.38349x1x1=4000 * 1 I ( )   11 1 1 1 1 07157.7 0.00365 1.37984 Ix f x máx I x  = + + x1= 4000 Juan Eloy Ruiz Castro 58 Ejercicio propuesto. Extender el caso anterior a tres bancos. ¿Puedes generalizarlo a mbancos? Elementos del modelo •La etapa ies el período (año) • Las alternativas en la etapa ison las cantidades invertidas en el primer, segundo y tercer banco Ii, JiyWirespectivamente •El estado de la etapa i,xi,es la cantidad de capital disponible para inversión al iniciar al año i . Claramente se observa que Wi=xi−Ii−JiPor lo tanto, x1=P1 xi=Pi+qi−1,1 Ii−1+qi−1,2 Ji−1+qi−1,3 (xi−1−Ii−1−Ji−1) =Pi+ (qi−1,1−qi−1,3)Ii−1+ (qi−1,2−qi−1,3)Ji−1+qi−1,3 xi−1;i= 2,…, n La cantidad a poder reinvertir xiincluye los bonos por inversiones realizadas en el año i−1. Llamamos fi(xi)al valor óptimo de las inversiones para los años i,i+1,…, n, dado xi. Llamamos siala suma acumulada al final del año ndesde el año ipor el ingreso desde este año. Entonces el problema se puede formular como sigue: Juan Eloy Ruiz Castro 59 fi(xi) : valor óptimo de las inversiones para los años i, i+1, …, ndado que al comienzo de este año se tiene para poder invertir la cantidad xi. Maximizar z=s1+s2+…+ sn donde ( ) ( ) ( )( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )( ) ( ) 1 1 1 1 2 3 1 1 1 1 1 1 3 2 3 3 1 1 2 2 3 3 1 1 3 3 2 2 3 1 1 1 1 1 1 1 1 ; 1,2,..., 1 1 1 1 1 1 1 1 n i n i n i i i i i i i n i n i n i n i n i i i i n n n n n n n n n n n n n s I r J r x I J r r r I r r J r x i n s I r q J r q x I J r q r q r q I r q r + − + − + − + − + − + − + − + − = + + + + − − + = + − + + + − + + + = − = + + + + + + − − + + = + + − − − + + + − − ( ) ( ) 3 3 3 1 n n n n q J r q x− + + + Llamamos siala suma acumulada al final del año ndesde el año ipor el ingreso desde este año. Entonces el problema se puede formular como sigue: Juan Eloy Ruiz Castro 60 Algoritmo recursivo ( ) ( )   ( ) 11 0 0 11 máx ; 1,2, , 1 0 ii i i i i i i i i Ix J x I nn f x s f x i n fx ++    − ++ = + = − = fi(xi) : valor óptimo de las inversiones para los años i, i+1, …, ndado que al comienzo de este año se tiene para poder invertir la cantidad xi. Juan Eloy Ruiz Castro 61 Ejemplo.Se desea invertir ahora 4000 euros y 2000 euros en los años 2, 3 y 4. La tasa de interés que ofrece B1 es del 8% anual compuesto y los bonos durante los 4 años siguientes serán del 1.8%, 1.7%, 2.1% y 2.5%, respectivamente. El banco B2 ofrece un interés un 0.2 inferior a B1 pero su bono es un 0.5 mayor cada año. La tasa de interés que ofrece B3 es del 9% anual compuesto y los bonos durante los 4 años siguientes son del 2%, 2%, 3% y 4%, respectivamente. Maximizar el capital acumulado al final de 4 años. Solución 1 2 3 4 1 2 3 11 21 31 41 12 22 32 42 13 2 4000 ; 2000 0.08 ; 0.078 ; 0.09 0.018 ; 0.017 ; 0.021 ; 0.025 0.023 ; 0.022 ; 0.026 ; 0.030 0.02 ; P P P P r r r q q q q q q q q qq = = = = = = = = = = = = = = = =3 33 43 0.02 ; 0.03 ; 0.04qq= = = Juan Eloy Ruiz Castro 68 Por lo tanto se tiene que: x1= 4000; I1= 0 = J1; Z1=x1 x2= 2080; I2= 0 = J2; Z2=x2 x3= 2041.6; J3= 0 = I3; Z3=x3 x4= 2061.248; I4= 0 = J4; Z4=x4 Acumulación final: s1+s2+s3+s4= 13094,822 euros El máximo se alcanza en I1= 0 y J1= 0 Solución óptima Estado f1(x1) x1=4000 7342.938+1.43797099x10 0 * 1 J ( )   11 1 1 1 1 1 1 1 1 0 0 7342.938 0.05373159 0,05718398 1.43797099 Ix J x I f x máx I J x    − = − − + * 1 I x1= 4000 Juan Eloy Ruiz Castro 69 1.6. Resolución de un problema lineal mediante programación dinámica Máx z= 2x1+5x2s.a. 2x1+x2≤ 430 x2≤ 230 x1, x2≥ 0 Elementos del modelo •La etapa ies el número de variable • Las alternativas en la etapa ison xi •El estado de la etapa ies la holgura en las restricciones funcionales. Viene dado para la etapa 2 por (R2,Q2) y representa los recursos 1 y 2 que se usan en esta etapa. Para la etapa 1 viene dado por (R1,Q1) representando los recursos 1 y 2 que se usan en las etapas 1 y 2. . Juan Eloy Ruiz Castro 70 Solución Etapa 2. Los recursos que se usan en esta etapa 2 por parte de x2son (R2, Q2). Llamamos f2(R2, Q2) a la utilidad máxima para la etapa 2 dado el estado expuesto. Por lo tanto, ( )       2 2 2 2 22 2 2 2 2 2 0 0 min ,230 0 230 , máx 5 máx 5 x R x R xQ f R Q x x       = == Solución óptima Estado x2 (R2=430-2x1, Q2=230) 5 mín{R2=430-2x1,230} mín {R2=430-2x1 , 230} ( ) 2 2 2 ,f R Q Máx z= 2x1+5x2s.a. 2x1+x2≤ 430 x2≤ 230 x1, x2≥ 0 Este máximo se alcanza en el máximo de x2y esto ocurre cuando x2=mín{R2,Q2}. Juan Eloy Ruiz Castro 71 ( ) ( )   ( )   1 2 1 1 1 1 1 2 1 1 1 0 2 430 0 215 , máx 2 430 2 ,230 máx 2 5mín 430 2 ,230 x R x f R Q x f x x x   =   = + − = + − ( ) 1 1 11 230 ; 0 100 mín 430 2 ,230 430 2 ; 100 215 x xxx   −= −    ( ) ( ) 1 11 10 215 1 1 1 2 5*230 ; 0 100 430,230 máx 2 5 430 2 ; 100 215 x xx fx x x  +    =+ −    Etapa 1. En este caso los recursos totales de x1 y x2 son (R1, Q1)=(430, 230). En esta etapa es claro que: Expresamos en primer lugar la función mínimo para los distintos valores de x1. Por lo tanto: Máx z= 2x1+5x2s.a. 2x1+x2≤ 430 x2≤ 230 x1, x2≥ 0 Juan Eloy Ruiz Castro 72 Solución óptima Estado x1 (430, 230) 1350 100 ( ) 1 1 1 ,f R Q Por lo tanto el óptimo se alcanza para x1=100. Desde la etapa 1 se tiene que ( ) 1 mín 430 2 ,230x− ( ) = mín 430 200,230 230−= x2= mín{R2, Q2}= tomando la función objetivo el valor 1350. Máx z= 2x1+5x2s.a. 2x1+x2≤ 430 x2≤ 230 x1, x2≥ 0 Juan Eloy Ruiz Castro 73 Ejercicio Máx z= 3x1+5x2 s.a. x1 ≤ 4 2x2≤ 12 3x1+2x2≤ 18 x1, x2≥ 0 Juan Eloy Ruiz Castro 74 Solución Etapa 2. Los recursos que se usan en esta etapa 2 por parte de x2son (R2, Q2,W2). Llamamos f2(R2, Q2,W2) a la utilidad máxima para la etapa 2 dado el estado expuesto. Por lo tanto, ( )       2 2 2 2 22 2 2 2 2 2 0 /2 12/2 6 0 min 6, /2 0 /2 , , máx 5 máx 5 x Q x W xW f Q W x x   = =    −− = = Solución óptima Estado x2 (Q2=12, W2=18-3x1)5 mín{Q2/2=6, W2/2=9-3x1/2} mín{Q2/2=6, W2/2=9-3x1/2} ( ) 2 2 2 ,f R Q Este máximo se alcanza en el máximo de x2y esto ocurre cuando x2= mín{Q2/2, W2/2}. Máx z= 3x1+5x2 s.a. x1 ≤ 4 2x2≤ 12 3x1+2x2≤ 18 x1, x2≥ 0 Juan Eloy Ruiz Castro Máx z= 3x1+5x2 s.a. x1 ≤ 4 2x2≤ 12 3x1+2x2≤ 18 x1, x2≥ 0 75 ( ) ( )   11 1 1 1 1 2 1 1 1 0 4 0 4 3 , , máx 3 ,12,18 3 máx 3 5mín 6,9 2 xx f R W x f x x x       −− = + −− − = + −     1 1 11 6 ; 0 2 3 mín 6,9 3 29 ; 2 4 2 x xxx     −=   −      ( ) 1 11 104 11 3 30 ; 0 2 4, ,18 máx 9 45 ; 2 4 2 x xx fxx  +     −− = −     Etapa 1. En este caso los recursos totales de x1 y x2 son (R1, Q1, W1) = (4, 12, 18). En esta etapa es claro que: Expresamos en primer lugar la función mínimo para los distintos valores de x1. Por lo tanto: Juan Eloy Ruiz Castro 76 Solución óptima Estado x1 (4,18) 36 2 ( ) 1 1 1 ,f R Q Por lo tanto el óptimo se alcanza para x1=2. Desde la etapa 1 se tiene que 1 33 mín 6,9 mín 6,9 2 6 22 x     − = − =         x2= mín{Q2/2, W2/2}= tomando la función objetivo el valor 36. Máx z= 3x1+5x2 s.a. x1 ≤ 4 2x2≤ 12 3x1+2x2≤ 18 x1, x2≥ 0 Juan Eloy Ruiz Castro 77 Ejercicio. Resolver el siguiente ejercicio de programación lineal mediante programación dinámica. Máx z= 4x1+14x2 s.a. 2x1+7x2 ≤ 21 7x1+2x2 ≤ 21 x1, x2≥ 0 Solución Etapa 2. Los recursos que se usan en esta etapa 2 por parte de x2son (R2, Q2). Llamamos f2(R2, Q2) a la utilidad máxima para la etapa 2 dado el estado expuesto. Por lo tanto, Juan Eloy Ruiz Castro 84 Ejercicio. Resolver el siguiente ejercicio de programación lineal mediante programación dinámica. Máx z= 2x1-3x2 s.a. x1+x2 ≤ 6 x1+3x2 ≤ 12 x1≥ 0, x2≥ 2 Juan Eloy Ruiz Castro 85 Solución Etapa 2. Los recursos que se usan en esta etapa 2 por parte de x2son (R2, Q2). Llamamos f2(R2, Q2) a la utilidad máxima para la etapa 2 dado el estado expuesto. Por lo tanto, ( )   22 22 2 2 2 2 2 2 /3 , máx 3 xR xQ f R Q x   =− Este máximo se alcanza en el máximo de x2y esto ocurre cuando x2=mín{R2,Q2/3}. Solución óptima Estado x2 (R2, Q2) -6 2 ( ) 2 2 2 ,f R Q ( ) ( ) 2 2 1 1 , 6 ,12R Q x x= − − Juan Eloy Ruiz Castro 86 ( ) ( )     11 1 1 1 1 1 2 2 2 1 0 4 0 4 06 , máx 2 , máx 2 6 2 xx x f R Q x f R Q x      = + = − = Etapa 1. En este caso los recursos totales de x1 y x2 son (R1, Q1) = (4, 6). En esta etapa es claro que: Solución óptima Estado x1 (R2, Q2) 2 4 ( ) 1 1 1 ,f R Q Juan Eloy Ruiz Castro 87 Capítulo 2. PROGRAMACIÓN DINÁMICA PROBABILÍSTICA Diferencia principal con la determinística: “Los estados y retornos de cada etapa son probabilísticos.” 2.1 Ganadora en Las Vegas Una joven emprendedora experta en estadística cree haber desarrollado un sistema para ganar un popular juego en Las Vegas. Sus colegas no piensan que este sistema sea tan bueno, por lo que le apuestan que si comienza con tres fichas, ella no tendrá cinco fichas después de tres jugadas. Cada jugada incluye apostar cualquier cantidad de las fichas disponibles y ganar o perder este mismo número de fichas. La joven cree que su sistema le dará una probabilidad de 2/3 de ganar una jugada dada. Suponiendo que la experta en estadística está en lo correcto, se quiere determinar su política óptima respecto a cuántas fichas apostar (si apuesta) en cada una de las tres jugadas. La decisión en cada jugada deberá tener en cuenta los resultados de las jugadas anteriores. El objetivo es maximizar la probabilidad de ganar la apuesta hecha a sus colegas. Juan Eloy Ruiz Castro 88 Elementos del modelo •La etapa ies la i-ésima jugada que realiza, i= 1, 2, 3 • Las alternativas son el número de fichas que debe apostar en cada etapa i(ai) •El estado xide la etapa ies el número de fichas disponibles para apostar. Objetivo final: maximizar la probabilidad de que la joven gane la apuesta, por lo tanto, la función objetivo que debe maximizarse en cada etapa es la probabilidad de terminar las tres jugadas con cinco fichas o más. ( ) ii fx = probabilidad máxima de terminar las tres jugadas con cinco o más fichas, dado que la joven comienza la etapa icon xifichas. Juan Eloy Ruiz Castro 89 Suponemos que la probabilidad de ganar una jugada dada es 2/3, como decía la experta. Algoritmo recursivo ( ) ( ) ( ) ( ) ( ) ( ) ( ) 11 11 4 44 4 12 ,33 12 máx , 1,2,3. 33 0 ; 5 1 ; 5 i i i i i i i i i i i i i i i i i i a f x a f x a f x a f x f x a f x a i x fx x ++ ++ = − + +  = − + + =     =  Juan Eloy Ruiz Castro 90 Etapa 3 Solución Óptima x3a3= 0 a 3 = 1 a3= 2 a3= 3 a3= 4 a3= 5 a3= 6 a3= 7 0 1 2 3 4 5 6 7 8 9 10 11 12 0 0 0 0 0 1 1 1 1 1 1 1 1 --- 0 0 0 2/3 2/3 1 1 1 1 1 1 1 --- --- 0 2/3 2/3 2/3 2/3 1 1 1 1 1 1 --- --- --- 2/3 2/3 2/3 2/3 2/3 1 1 1 1 1 --- --- --- --- 2/3 2/3 2/3 2/3 2/3 1 1 1 1 --- --- --- --- --- 2/3 2/3 2/3 2/3 2/3 1 1 1 --- --- --- --- --- --- 2/3 2/3 2/3 2/3 2/3 1 1 --- --- --- --- --- --- --- 2/3 2/3 2/3 2/3 2/3 1 0 0 0 2/3 2/3 1 1 1 1 1 1 1 1 0 ≤ 1 ≤ 2 2 ó 3 1, 2, 3 ó 4 0 ≤ 1 ≤ 2 ≤ 3 ≤ 4 ≤ 5 ≤ 6 ≤ 7 ( ) ( ) ( ) 3 3 3 4 3 3 4 3 3 12 ,33 f x a f x a f x a= − + + ( ) 33 fx * 3 a Juan Eloy Ruiz Castro 91 Etapa 3 Solución Óptima x3 0 1 2 3 4 5 6 7 8 9 10 11 12 0 0 0 2/3 2/3 1 1 1 1 1 1 1 1 0 ≤ 1 ≤ 2 2 ó más 1 ó más 0 ≤ 1 ≤ 2 ≤ 3 ≤ 4 ≤ 5 ≤ 6 ≤ 7 ( ) 33 fx * 3 a Etapa 3 Solución Óptima x3 0 1 2 3 4 5 ó más 0 0 0 2/3 2/3 1 0 ≤ 1 ≤ 2 2 ó más 1 ó más ≤ x3 −5 ( ) 33 fx * 3 a Juan Eloy Ruiz Castro 92 Etapa 2 Solución Óptima x2a2= 0 a 2 = 1 a2= 2 a2= 3 a2= 4 a2= 5 a2= 6 0 1 2 3 4 5 6 0 0 0 2/3 2/3 1 1 --- 0 4/9 4/9 8/9 8/9 1 --- --- 4/9 2/3 2/3 8/9 8/9 --- --- --- 2/3 2/3 2/3 8/9 --- --- --- --- 2/3 2/3 2/3 --- --- --- --- --- 2/3 2/3 --- --- --- --- --- --- 2/3 0 0 4/9 2/3 8/9 1 1 0 ≤1 1 ó 2 0, 2, 3 1 0 ≤ 1 ( ) ( ) ( ) 2 2 2 3 2 2 3 2 2 12 ,33 f x a f x a f x a= − + + ( ) 22 fx * 2 a Juan Eloy Ruiz Castro 93 Etapa 2 Solución Óptima x2a2= 0 a 2 = 1 a2= 2 a2= 3 a2= 4 a2= 5 a2= 6 0 1 2 3 4 5 6 0 0 0 2/3 2/3 1 1 --- 0 4/9 4/9 8/9 8/9 1 --- --- 4/9 2/3 2/3 8/9 8/9 --- --- --- 2/3 2/3 2/3 8/9 --- --- --- --- 2/3 2/3 2/3 --- --- --- --- --- 2/3 2/3 --- --- --- --- --- --- 2/3 0 0 4/9 2/3 8/9 1 1 0 ≤1 1 ó 2 0, 2, 3 1 0 ≤ 1 ( ) ( ) ( ) 2 2 2 3 2 2 3 2 2 12 ,33 f x a f x a f x a= − + + ( ) 22 fx * 2 a Solución Óptima x2a2= 0 a 2 = 1 a2= 2 a2= 3 a2= 4 0 1 2 3 4 ≥ 5 0 0 0 2/3 2/3 1 --- 0 4/9 4/9 8/9 --- --- 4/9 2/3 2/3 --- --- --- 2/3 2/3 --- --- --- --- 2/3 0 0 4/9 2/3 8/9 1 0 ≤1 1 ó 2 0, 2, 3 1 ≤ x2−5 ( ) ( ) ( ) 2 2 2 3 2 2 3 2 2 12 ,33 f x a f x a f x a= − + + ( ) 22 fx * 2 a Juan Eloy Ruiz Castro 100 2.2 Optimización del valor esperado. Un juego aleatorio Se gira una rueda con marcas de nnúmeros consecutivos: 1 a n. Por experiencia previa se sabe que la probabilidad de que se detenga la rueda en un número ies pi. Un jugador paga xeuros por lanzar la rueda a lo sumo mveces, pudiendo parar cuando lo desee antes de girar. El jugador gana siempre el doble de la cantidad obtenida en el último giro. Si se lanza a lo sumo mveces la ruleta, ¿cuál es la estrategia óptima para obtener el máximo ingreso esperado? Juan Eloy Ruiz Castro 101 Elementos del modelo •La etapa ies el número de giro, i= 1,…, m •Las alternativas son hacer girar una vez más la rueda o terminar el juego. La decisión se toma al final de la etapa. •El estado jde la etapa ies el número obtenido en el giro. fi(j): ingreso máximo esperado desde etapa ihasta el final siendo el resultado del giro j. Ingreso esperado desde la etapa ihasta fin del juego siendo el resultado del último giro j 1 1 2 ; si termina el juego ( ) ; si continúa el juego n ki k j p f k + =      Juan Eloy Ruiz Castro 102 Ecuación recursiva 1 1 ( ) 2 ( ) 2 , ( ) ; 2,..., 1 m n i k i k f j j f j máx j p f k i m + = =  = = −    . Ejemplo Supongamos una rueda con los números del 1 al 5. La probabilidad de detenerse en el número ies p1= 0.3, p2= 0.25,p3= 0.2, p4= 0.15,p5= 0.1. El jugador paga 5 euros para realizar un máximo de 4 lanzamientos. Obtener la estrategia óptima para cada giro y el ingreso esperado. Juan Eloy Ruiz Castro 103 Ejemplo Supongamos una rueda con los números del 1 al 5. La probabilidad de detenerse en el número ies p1= 0.3, p2= 0.25, p3= 0.2, p4= 0.15,p5= 0.1. El jugador paga 5 euros para realizar un máximo de 4 lanzamientos. Obtener la estrategia óptima para cada giro y el ingreso esperado. Solución Etapa 4 f4(j) = 2j Solución óptima Resultado del giro 4 f4(j) = 2jDecisión 1 2 3 4 5 2 4 6 8 10 TERMINAR (impuesto) TERMINAR (impuesto) TERMINAR (impuesto) TERMINAR (impuesto) TERMINAR (impuesto) Juan Eloy Ruiz Castro 104 Etapa 3 Ingreso Solución óptima Resultado del giro 3 Terminar Girar Decisión 1 2 3 4 5 2 4 6 8 10 5 5 5 5 5 5 5 6 8 10 Girar Girar Terminar Terminar Terminar     5 31 2,..., 1 ( ) 2 , ( ) 2 ,0.3*2 0.25*4 0.2*6 0.15*8 0.1*10 2 ,5 ki im k f j máx j p f k máx j máx j += =  = = + + + +   =    3( ) 2 ,5f j máx j= Juan Eloy Ruiz Castro 105 Ingreso Solución óptima Resultado del giro 2 Terminar Girar Decisión 1 2 3 4 5 2 4 6 8 10 6.15 6.15 6.15 6.15 6.15 6.15 6.15 6.15 8 10 Girar Girar Girar Terminar Terminar Etapa 2     21 2,..., 1 ( ) 2 , ( ) 2 ,0.3*5 0.25*5 0.2*6 0.15*8 0.1*10 2 ,6.15 n ki im k f j máx j p f k máx j máx j += =  = = + + + +   =    2( ) 2 ,6.15f j máx j= Juan Eloy Ruiz Castro 106 Ingreso Solución óptima Resultado del giro 1 Terminar Girar Decisión 1 2 3 4 5 2 4 6 8 10 6.8125 6.8125 6.8125 6.8125 6.8125 6.8125 6.8125 6.8125 8 10 Girar Girar Girar Terminar Terminar Etapa 1     11 1 ( ) 2 , ( ) 2 ,0.3*6.15 0.25*6.15 0.2*6.15 0.15*8 0.1*10 2 ,6.8125 n ki k f j máx j p f k máx j máx j + =  = = + + + +   =    1( ) 2 ,6.8125f j máx j= Juan Eloy Ruiz Castro 107 Giro número Estrategia óptima a seguir después del giro 1 2 3 4 Girar si sale 1,2,3. Girar si sale 1,2,3. Girar si sale 1,2. Terminar Al final la ganancia neta esperada es: 7.309375 – 5 = 2.309375 euros 1 1 Ganancia esperada desde el inicio ( ) 0.3*6.8125 0.25*6.8125 0.2*6.8125 0.15*8 0.1*10 7.309375 n k k p f k = = = + + + + =  Estrategia óptima Ejercicio Propuesto Considerando el ejemplo anterior. ¿Qué ocurriría si todos los números fuesen equiprobables? Juan Eloy Ruiz Castro 108 2.3. Problema de inversión Una persona invierte hasta C euros en bolsa durante los naños siguientes. Se compran acciones a comienzo de año y se venden al finalizar ese mismo año. El dinero acumulado se puede utilizar para reinvertirlo cada año, todo o en parte. El grado de riesgo se expresa probabilísticamente. Un estudio de mercado indica que el retorno sobre la inversión está afectado por mcondiciones del mercado, que pueden ser favorables o desfavorables, produciendo la condición iun ingreso en proporción sobre lo invertido de ricon probabilidad pi. ¿Cómo se debe invertir las cantidades a lo largo de los años? Juan Eloy Ruiz Castro 109 Elementos del modelo • La etapa ies el año al inicio • Las alternativas son yi: cantidades invertidas al comenzar el año i. • El estado de la etapa ies xi: cantidad de fondos disponibles para invertir al comenzar el año. El inicio es x1=C. fi(xi): fondos esperados máximos para los años i, i+1,…, ncuando al comenzar el año ise tiene para poder invertir xi. Para la condición kdel mercado (que se presenta con probabilidad pk)se tiene que: ( ) ( ) 11 i k i i i i k i x r y x y x r y += + + − = + ;k= 1,…, m Juan Eloy Ruiz Castro 116 Solución 0.6r= ( ) 4 4 4 1.6f x x= Etapa 4 Solución Óptima Estado f4(x4) x41.6 x4x4 * 4 y Año r1r2r3p1p2p3 4 0.8 0.4 0.2 0.6 0.2 0.2 Juan Eloy Ruiz Castro 117 Solución Óptima Estado f3(x3) x31.6 x30≤ y3 ≤ x3 ( ) ( ) ( ) ( )   ( ) ( ) ( )   ( ) ( ) ( )     33 33 33 33 3 3 1 4 3 1 3 2 4 3 2 3 3 4 3 3 3 0 4 3 3 4 3 3 4 3 3 0 3 3 3 3 3 3 0 3 0 0.2 4 0.4 0.4 0.2*1.6 4 0.4*1.6 0.4*1.6 1.6 yx yx yx yx f x máx p f x r y p f x r y p f x r y máx f x y f x y f x y máx x y x y x y máx x     = + + + + + = + + − + − = + + − + − = ( ) 3 3 3 1.6f x x= * 3 y Por lo tanto Etapa 3 Año r1r2r3p1p2p3 3 4 -1 -1 0.2 0.4 0.4 ( ) 4 4 4 1.6f x x= Juan Eloy Ruiz Castro 118 Solución Óptima Estado f3(x3) x21.92 x2x2 ( ) ( ) ( ) ( )   ( ) ( ) ( )   ( ) ( )     22 22 22 22 2 2 1 3 2 1 2 2 3 2 2 2 3 3 2 3 2 0 3 2 2 3 2 3 2 2 0 2 2 2 2 2 0 22 0 0.4 0.4 0.2 0.4*1.6 0.4*1.6 0.2*1.6 1.6 0.32 yx yx yx yx f x máx p f x r y p f x r y p f x r y máx f x y f x f x y máx x y x x y máx x y     = + + + + + = + + + − = + + + − =+ ( ) 2 2 2 1.92f x x= * 2 y Por lo tanto el máximo vale Etapa 2 Año r1r2r3p1p2p3 2 1 0 -1 0.4 0.4 0.2 ( ) 3 3 3 1.6f x x= Juan Eloy Ruiz Castro 119 Solución Óptima Estado f3(x3) x13.552 x1x1 ( ) ( ) ( ) ( )   ( ) ( ) ( )   ( ) ( ) ( )     11 11 11 11 1 1 1 2 1 1 1 2 2 1 2 1 3 2 1 3 1 0 2 1 1 2 1 1 2 1 1 0 1 1 1 1 1 1 0 11 0 0.1 2 0.4 0.5 0.5 0.1*1.92 2 0.4*1.92 0.5*1.92 0.5 1.92 1.632 yx yx yx yx f x máx p f x r y p f x r y p f x r y máx f x y f x y f x y máx x y x y x y máx x y     = + + + + + = + + + + + = + + + + + =+ ( ) 1 1 1 3.552f x x= * 1 y Por lo tanto el máximo vale Etapa 1 Año r1r2r3p1p2p3 1 2 1 0.5 0.1 0.4 0.5 La política óptima es: Año 1: 10000 euros Año 2: Todos los fondos Año 3: Cualquier cantidad de lo que dispongo Año 4: Todos los fondos Dividendos finales esperados: 35520 euros. ( ) 2 2 2 1.92f x x= Juan Eloy Ruiz Castro 120 2.4. Maximización de la probabilidad de lograr un ingreso Consideramos el caso anterior pero ahora deseamos maximizar la probabilidad de lograr cierta cantidad de ingreso. Las etapas, alternativas y estados no varían. Llamamos fi(xi) a la probabilidad de obtener la cantidad S, dado que xies la cantidad de fondos disponibles al inicial el año i, dado que se implementa una política óptima para los años i,i+1, …, n. Ecuación recursiva ( ) ( ) ( ) ( ) 1 01 01 ; 1,..., 1 ii nn m i i k i i k i yx k m n n k n k n yx k f x máx p f x r y i n f x máx p P x r y S +  =  =  = + = −    = +      Juan Eloy Ruiz Castro 121 Ejemplo Una persona desea invertir 2000 euros. Tiene dos opciones: duplicar lo invertido (probabilidad 0.3) o perder todo lo invertido (probabilidad 0.7). Las inversiones se venden al final de cada año y se reinvierte al comienzo. El proceso se repite durante tres años. Maximizar la probabilidad de obtener 4000 euros al final del período de tiempo. Etapa 3 Solución En esta etapa, comienzo del tercer año, el estado x3puede estar entre 0 y 8000 (los dos años anteriores ha doblado). La ecuación recursiva resulta (los números de las inversiones se dan en miles de euros): ( ) ( ) ( ) ( )   3 3 3 3 3 3 3 3 3 3 3 3 00 1 4 0.3 4 0.7 4 m kk y x y x k f x máx p P x r y máx P x y P x y     =  = +  = +  + −     siendo x3=0, 1, …, 8. Juan Eloy Ruiz Castro 122 Óptimo x3 y 3 =0 1 2 3 4 5 6 7 8 f3y3 0 1 2 3 4 5 6 7 8 0 0 0 0 1 1 1 1 1 0 0 0.3 0.3 1 1 1 1 0.3 0.3 0.3 0.3 1 1 1 0.3 0.3 0.3 0.3 1 1 0.3 0.3 0.3 0.3 1 0.3 0.3 0.3 0.3 0.3 0.3 0.3 0.3 0.3 0.3 0 0 0.3 0.3 1 1 1 1 1 0 ≤ 1 2 1,2,3 0 ≤ 1 ≤ 2 ≤ 3 ≤ 4 ( ) ( ) 3 3 3 3 0.3 4 0.7 4P x y P x y+  + −  Juan Eloy Ruiz Castro 123 Etapa 2 ( ) ( ) ( )   22 2 2 3 2 2 3 2 2 00.3 0.7 yx f x máx f x y f x y  = + + − , siendo x2=0, 1, …, 4. Óptimo x2 y 2 =0 1 2 3 4 f2y2 0 1 2 3 4 0 0 0.3 0.3 1 0.09 0.09 0.51 0.51 0.3 0.3 0.51 0.3 0.3 0.3 0 0.09 0.3 0.51 1 0 1 0, 2 1 0 ( ) ( ) 3 2 2 3 2 2 0.3 0.7f x y f x y+ + − f3y3 0 0 0.3 0.3 1 1 1 1 1 0 ≤ 1 2 1,2,3 0 ≤ 1 ≤ 2 ≤ 3 ≤ 4 x3 0 1 2 3 4 5 6 7 8 Juan Eloy Ruiz Castro 124 Etapa 1 ( ) ( ) ( )   1 1 1 2 1 1 2 1 1 02 0.3 0.7 y f x máx f x y f x y  = + + − , siendo x1=2. Óptimo x 1y1=0 1 2 f 1y1 2 0.3 0.3*0.51+0.7*0.09=0.21 6 0.3 0. 3 0, 2 ( ) ( ) 2 1 1 2 1 1 0.3 0.7f x y f x y+ + − f2y2 0 0.09 0.3 0.51 1 0 1 0, 2 1 0 x2 0 1 2 3 4 Juan Eloy Ruiz Castro 125 Esta cantidad se obtiene con probabilidad máxima de f1(2)=0.3 Solución: Año 1 Año 2 Año 3 INVIERTO INVIERTO INVIERTO x 1=2 y 1=0 doblo x 2=2 y 2=0 doblo x3=2 y 3=2 S ó N pierdo x 3=2 y 3=2 S ó N pierdo x 2=2 y 2=2 doblo x 3=4 y 3=0 S pierdo x 3=0 y 3=0 N y 1=2 doblo x 2=4 y 2=0 doblo x 3=4 y 3=0 S pierdo x 3=4 y 3=0 S pierdo x 2=0 y 2=0 doblo x 3=0 y 3=0 N pierdo x 3=0 y 3=0 N Juan Eloy Ruiz Castro 132 Óptimo x1y1=0 y1=1 y1=2 f1y1 0 1 2 0.4+1.4=1.8 0.4+1.1=1.5 0.4+0.9=1.3 --- 0.2+1.4=1.6 0.2+1.1=1.3 --- --- 0.15+1.4=1.55 1.8 1.5 1.3 0 0 0-1 Etapa 1   ( ) 1 2 1 1 fracasar el equipo 1 cuando se añaden P y f x y+− Rutas óptimas Equipo 1: +0 →Equipo 2: +0 →Equipo 3: +2 Equipo 1: +0 →Equipo 2: +1 →Equipo 3: +1 Equipo 1: +1 →Equipo 2: +0 →Equipo 3: +1 Juan Eloy Ruiz Castro 133 Ejemplo Un proyecto de investigación sobre cierto problema de ingeniería tiene 3 equipos de investigadores que buscan resolver el problema desde 3 puntos de vista diferentes. Se estima que en las circunstancias actuales la probabilidad de que los respectivos equipos 1, 2, 3 fracasen es de 0.4, 0.6 y 0.8 respectivamente. El objetivo es minimizar la probabilidad de fracaso de los 3 equipos y por ello se asignarán al proyecto 2 nuevos científicos de alto nivel, pero no se sabe en qué equipo es mejor integrarlos. Según la asignación a los equipos, la probabilidad de fracaso cambia según la tabla siguiente ¿Cómo deben asignarse los 2 nuevos científicos para minimizar la probabilidad de que algún equipo fracase? Nº de científicos asignados Probabilidad de fracaso de los equipos 1 2 3 0 1 2 0.40 0.20 0.15 0.60 0.40 0.20 0.80 0.50 0.30 Juan Eloy Ruiz Castro 134 Elementos del modelo • La etapa ies el equipo de investigación (1, 2, 3) • Las alternativas son yi: número de científicos que añado al equipo i. • El estado de la etapa ies xi: cantidad de científicos que dispongo para añadir en el equipo i Fi :“Fallar el equipo i” ; i= 1, 2, 3 Yi :“Nº de científicos que se añaden al equipo i” ; i= 1, 2, 3 ( ) ( ) 1 2 3 1 2 3 1 2 3 1 2 3 1P F F F Y Y Y P F F F Y Y Y    = −     ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 1 2 3 1 2 3 3 1 2 3 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 3 1 2 3 2 1 2 1 1 En nuestro caso se tiene que P F F F Y Y Y P F Y Y Y P F F Y Y Y P F F F Y Y Y P F F F Y Y Y P F Y Y Y P F Y Y P F Y     = =              =    Juan Eloy Ruiz Castro 135 Se tiene que xi +1 = xi –yi x1 = 2 Por lo tanto x2 = x1–y1 x3 = x1–y1–y2 fi(xi): probabilidad máxima de no fracasar el equipo i, i=1…, 3 Ecuación recursiva ( )   ( )   ( ) 1 0 44 no fracasar el equipo cuando se añaden 1 ii i i i i i i yx f x máx P i y f x y fx +  =  − = Juan Eloy Ruiz Castro 136 Óptimo x3y3=0 y3=1 y3=2 f3y3 0 1 2 0.2 0.2 0.2 0.5 0.5 0.7 0.2 0.5 0.7 0 1 2 Etapa 3   3 no fracasar el equipo 3 cuando se añaden Py Nº de científicos asignados Probabilidad de no fracaso de los equipos 1 2 3 0 1 2 0.60 0.80 0.85 0.40 0.60 0.80 0.20 0.50 0.70   3 1 2 3 | , ,P F Y Y Y Juan Eloy Ruiz Castro 137 Óptimo x2y2=0 y2=1 y2=2 f2y2 0 1 2 0.4 * 0.2 = 0.08 0.4 * 0.5 =0.20 0.4 * 0.7 = 0.28 --- 0.6 * 0.2 = 0.12 0.6 * 0.5 = 0.30 --- --- 0.8 * 0.2 = 0.16 0.08 0.20 0.30 0 0 1 Etapa 2   ( ) 2 3 2 2 no fracasar el equipo 2 cuando se añaden P y f x y− f3y3 0.2 0.5 0.7 0 1 2 x3 0 1 2 Nº de científicos asignados Probabilidad de no fracaso de los equipos 1 2 3 0 1 2 0.60 0.80 0.85 0.40 0.60 0.80 0.20 0.50 0.70     2 1 2 3 | , | , 1,2,3 iii y P F Y Y máxP F Y y i = = Juan Eloy Ruiz Castro 138 Óptimo x 1y1=0 y1=1 y1=2 f1y1 20.6 * 0.3 = 0.18 0.8 * 0.2 = 0.16 0.85 * 0.08 =0.068 0.18 0 Etapa 1   ( ) 1 2 1 1 no fracasar el equipo 1 cuando se añaden P y f x y− f2y2 0.08 0.20 0.30 0 0 1 x2 0 1 2 Nº de científicos asignados Probabilidad de no fracaso de los equipos 1 2 3 0 1 2 0.60 0.80 0.85 0.40 0.60 0.80 0.20 0.50 0.70         1 1 2 1 1 2 2 3 1 1 2 2 3 3 | | , | , , i y P F Y máx P F Y y Y y P F Y y Y y Y y = = = = = Juan Eloy Ruiz Castro 139 Rutas óptimas Equipo 1: +0 →Equipo 2: +1 →Equipo 3: +1 Óptimo x 1y1=0 y1=1 y1=2 f1y1 20.6 * 0.3 = 0.18 0.8 * 0.2 = 0.16 0.85 * 0.08 =0.068 0.18 0 Etapa 1   ( ) 1 2 1 1 no fracasar el equipo 1 cuando se añaden P y f x y− Probabilidad mínima de que algún equipo fracase : 1- 0.18 = 0.82 Juan Eloy Ruiz Castro 140 Ejemplo Una cadena de supermercados tiene 3 locales. La cadena compra diariamente 6 litros de leche a un proveedor y los distribuye en sus locales. Si un local vende un litro de leche recibe un beneficio de 2 €, obteniendo por cada litro sobrante diario un beneficio de 0.5 € al devolverlo al proveedor. La demanda de leche en cada local no es conocida con anterioridad mostrando la siguiente tabla los valores posibles y su probabilidad de ocurrencia: Demanda di (litros) Prob. (local 1) Prob. (local 2) Prob. (local 3) 1 0.6 0.5 0.4 2 0 0.1 0.3 3 0.4 0.4 0.3 Calcular el valor óptimo del número de litros de leche en cada local en un día Juan Eloy Ruiz Castro 141 Demanda di (litros) Prob. (local 1) Prob. (local 2) Prob. (local 3) 1 0.6 0.5 0.4 2 0 0.1 0.3 3 0.4 0.4 0.3 Óptimo x3y3=0 y3=1 y3=2 y3=3 y3=4 y3=5 y 3 =6 f3y3 0 1 2 3 4 5 6 0 0 0 0 0 0 0 2 2 2 2 2 2 3.4 3.4 3.4 3.4 3.4 4.35 4.35 4.35 4.35 4.85 4.85 4.85 5.35 5.35 5.85 0 2 3.4 4.35 4.85 5.35 5.85 0 1 2 3 4 5 6 Etapa 3 ( )     ( ) 3 3 3 3 3 3 3 3 3 3 1 2min , 0.5max ,0 d f x d y y d P D d = = + − =    Juan Eloy Ruiz Castro 244 ( ) 100 11 1 1 ; nn i nii i mi n c p p p i    − == −+   = =  ( ) 00 ! !! nn m mr p r p n m n n  ==  − ( ) ( ) 1 100 11 11 ; n c n i ni i i c i m i m i c n K p p p ic      − − = = = − + − +   = = =    ( ) ( ) ( ) ( ) 11 0 1 1! ! 1 ! 1 ! ! c n c nc mc mr r p m c c c m n − − + −+ −+ =− + − − 0 ! ! n nc mnrp ncc −  =  Calculamos p0 1 00 1m c m n n n n n n c p p p − = = = = = +    1 00 0 ! ! cm nn nc n n c mm n r p r p nn cc − − ==     =+          1 1 0 0 ! ! cm nn nc n n c mm n p r r nn cc − − − ==      =+            Juan Eloy Ruiz Castro 245 Razón media de llegadas al sistema ( ) ( ) 11 00 'mm n n n nn p m n p m L     −− == = = − = −  Número medio de máquinas en el sistema 1 00 00 1 0 0 ! ! ! ! m c m nn nnc n n n c cm nn nc n n c mm n L np n r p n r p nn cc mm n p n r n r nn cc − − = = = − − ==     = = +              =+               Número medio de máquinas en cola ( ) m qn nc L n c p = =−  mm nn n c n c np c p == =−  1 0 cm nn n n c L np c p − == = − −  1 1 1 1 0 0 0 0 1 c c c c n n n n n n n n L np c p L np c c p − − − − = = = =  = − − − = − − +       ( ) 1 0 c n n L c c n p − = = − + −  Juan Eloy Ruiz Castro 246 Quedando ( ) 1 0 0 cn qn m L L c p c n r n − =  = − + −    Tiempo medio de espera en el sistema ( ) 1 0 0 ! ! ' cm nn nc n n c mm n p n r n r nn cc L WmL  − − ==      +           == −  Fórmula de Little Tiempo medio de espera en cola ( ) ( ) 1 0 0 ' cn n q q m L c p c n r Ln WmL  − =  − + −   == −  Fórmula de Little Juan Eloy Ruiz Castro 247 Ejemplo Una fábrica de semiconductores usa cinco robots para la fabricación de sus placas de circuitos. Los robots se estropean periódicamente, y la compañía tiene dos reparadores para las reparaciones. Cuando un robot es arreglado, el tiempo hasta que se rompe de nuevo se cree que es una exponencial distribuida con una media de 30 horas. La empresa tiene suficiente trabajo en cola para asegurarse que todos los robots en condiciones de trabajar estarán funcionando. El tiempo de reparación se distribuye según una exponencial de media 3 horas. Al encargado le gustaría saber el número medio de robots operativos en cualquier momento, el tiempo que un robot tarda en ser reparado desde que se rompe, el porcentaje de tiempo que algún operario está parado. Juan Eloy Ruiz Castro 248 ( ) 'mL  =− 1 0 0 ! ! cm nn nc n n c mm n L p n r n r nn cc − − ==      =+            ( ) 1 0 0 cn qn m L L c p c n r n − =  = − + −    ' L W  = ' q q L W  = 1 1 0 0 ! ! cm nn nc n n c mm n p r r nn cc − − − ==      =+            M/M/c/m/m 1 ; nc 0 n n m p r p n  =  ; c n K 0 ! ! n nnc mn p r p ncc −  =  Juan Eloy Ruiz Castro 249 ( ) 'mL  =− 15 01 02 55 ! 2 nn n nn n L p n r n r nn − ==      =+            ( ) 1 0 0 5 22 n qn L L p n r n =  = − + −    ' L W  = ' q q L W  = 1 15 01 02 55 ! 2 nn n nn n p r r nn − − ==      =+            M/M/2/5/5 1 2 ; n 0 5n n p r p n  =  2 5 ; n 0 2 5! 22 n nn n p r p n−  =   Juan Eloy Ruiz Castro 250 ( ) 5 0.4648 ' 0.1511 30 mL  − = − = = 15 2 3 4 5 00 1 02 55 ! 3 75 5 20 30 20 3 0.4648 2 2 2 nn n nn n L p n r n r p r r r r r nn − ==       = + =  +  +  +  + =              ( )   1 00 0 5 2 2 2 2 5 0.01127 n qn L L p n r L p r n =  = − + − = − + + =    3.0746 ' L W  == 0.07458 ' q q L W  == 11 15 2 3 4 5 01 02 55 ! 3 15 1 5 10 10 5 3 0.6186 2 2 2 nn n nn n p r r r r r r r nn −− − ==       = + = +  +  +  +  + =              M/M/2/5/5 11 30 0.1 110 3 r   = = = = Juan Eloy Ruiz Castro 251 3.6. SISTEMA M/G/1 El Modelo Consideremos un sistema de colas con un solo servidor, tiempos de entre llegadas exponenciales (media 1/) y tiempos de servicio independientes e idénticamente distribuidas con función de distribución B(t), densidad si la hay b(t) y media 1/ Número medio de clientes que llegan durante el tiempo de servicio de otro cliente    = Juan Eloy Ruiz Castro 252 ( ) 2 2 2 21 S L     + =+ − Fórmula de Pollaczek-Khinchine Número esperado de clientes en el sistema ( ) 2 2 2 11 21 Sq WW         + = + = +  −  ( ) ( ) 2 2 2 2 2 2 11 2 1 2 1 SS q W              ++ = + − =  −−  ( ) 2 2 2 21 S qq LW     + ==− Juan Eloy Ruiz Castro 253 Ejemplo Un chip está en funcionamiento hasta que se produce un fallo en el mismo. Cuando esto ocurre, comienza inmediatamente a funcionar otro pasando a reparación el primero y así sucesivamente. El tiempo medio de funcionamiento del chip sometido a estrés es de 720 horas. Cuando pasa al canal de reparación el chip atraviesa dos etapas secuencialmente. La primera etapa es la reparación propiamente dicha y la segunda el ajuste final. El tiempo medio en la primera y segunda etapa es de 100 y 20 horas respectivamente. Si todos los tiempos son exponenciales y hay un solo servicio de reparación. ¿Cuál es el número esperado de chip en el canal de reparación? ¿y en cola de reparación? ¿Cuánto tiempo estará una unidad no operativa? ( ) 2 2 2 21 S L     + =+ − 1/ 720  = 1 120  = 2 2 2 20 100 10400  = + = 22 1 10400 1 31200 1 13 1 1 1 1 18 13 6 720 12 518400 12 216 5 6 6 5 6 5 6 1080 3 1 31 180 31 211 0.1954 6 1080 1080 1080 + + + + = + = + = + = + + = + = = = 120 1 720 6  == Juan Eloy Ruiz Castro 260 Ejemplo.En la Universidad se cambian las bombillas a razón de 100 unidades diarias. Estas luces se piden de forma periódica costando 9 euros el iniciar cada pedido de compra. Cada luz en el almacén cuesta 0.02 euros diarios, siendo el tiempo de entrega inmediato. Determinar una política óptima . D: 100 unidades diarias K: 9 euros por pedido h: 0.02 euros por unidad y día La cantidad óptima a pedir es: 2300 bombillas DK yh == Longitud del ciclo y punto de reorden: 23 días yK D hD == Juan Eloy Ruiz Castro 261 Si se considera el mismo modelo anterior pero la entrega no es inmediata, transcurre un tiempo L, entonces en el modelo anterior hay que realizar el pedido cuando el nivel de inventario baja a LD unidades. Número de unidades consumidas en un tiempo L. 2DK yh = 0 2K t L L hD − = − Unidades a pedir y tiempo hasta punto de reorden desde entrega de unidades Juan Eloy Ruiz Castro 262 Ejemplo.En la Universidad se cambian las bombillas a razón de 100 unidades diarias. Estas luces se piden de forma periódica costando 9 euros el iniciar cada pedido de compra. Cada luz en el almacén cuesta 0.02 euros diarios, siendo el tiempo de entrega de 1 día. Determinar una política óptima . D: 100 unidades diarias K: 9 euros por pedido h: 0.02 euros por unidad y día La cantidad óptima a pedir es: 2300 bombillas DK yh == Longitud del ciclo: 0 23 días yK tD hD = = = Punto de reorden: 0 22 días tras llegada de pedido K t L L hD − = − = 100 bombillasLD = Juan Eloy Ruiz Castro 263 Esta expresión es válida si 0 2yK Lt D hD  = = En otro caso se actúa como sigue: Se define: siendo nel mayor entero menor que 0 2 e K L L nt L n hD = − = − 02 LL tK hD = En este caso el punto de reorden está en LeDunidades e inicialmente (n+1)t0D 2DK yh = 0 2K t L L hD − = − Unidades a pedir y tiempo hasta punto de reorden desde entrega de unidades 0 es decir 2 LL Ent Ent tK hD     =      Tras n+1 ciclos, el tiempo desde que se pide hasta que se recibe es Le Juan Eloy Ruiz Castro 264 Le L LeLe t0t0 … n+1 ... t0t0 t0 Punto de reorden posterior: LeD unidades Se pide inicialmente en los tiempos mt0-Lepara m=1,…, n+1 Inicialmente hay (n+1)t0Dunidades 0 0 e L L L Ent t t  =−   0e L L nt=+ Juan Eloy Ruiz Castro 265 Ejemplo.En la Universidad se cambian las bombillas a razón de 200 unidades diarias. Estas luces se piden de forma periódica costando 75 euros el iniciar cada pedido de compra. Cada luz en el almacén cuesta 0.02 euros diarios, siendo el tiempo de entrega, desde petición hasta colocación, de 15 días. Determinar una política óptima . D: 200 unidades diarias K: 75 euros por pedido h: 0.02 euros por unidad y día L: 15 días La cantidad óptima a pedir es: 21224.74 bombillas DK yh == Longitud del ciclo: 0 26.12 días yK tD hD = = = Como el pedido se gastaría en 6.12 días y la revisión es cada 15 días, entonces la cantidad de ciclos incluidos en Les: 2 2 L nE K hD    ==    Juan Eloy Ruiz Castro 266 215 2*6.12 2.76 días e Ky L L n L n hD D = − = − = − = Punto de reorden: 552 unidades e LD= Cuando se baja a 552 unidades hay que pedir 1224.74 bombillas (1225). Costo diario: ( ) 75*200 0.02*1224.74 24.49 euros 2 1224.74 2 KD hy TCU y y = + = + = Inicialmente hay (n+1)t0D= 3672 unidades Se pide inicialmente en los tiempos mt0-Lepara m=1,…, n+1 Tiempo de petición 1: 3.36 días Tiempo de petición 2: 9.48 días Tiempo de petición 3: 15,6 días Juan Eloy Ruiz Castro 267 4.1.2.2 CEP con discontinuidades de precio Consideremos el modelo anterior pero en este caso si el tamaño del pedido, y, es mayor que un determinado límite qentonces se obtiene un descuento. El precio de la compra unitario viene dado por: 1 12 2 ; ; ; c y q c c c c y q   =   Precio de compra por unidad de tiempo 11 1 0 22 2 0 ; / ; / c y c y Dc y q t y D c y c y Dc y q t y D = =     = =    Juan Eloy Ruiz Castro 268 Costo total por unidad de tiempo: ( ) ( ) ( ) 11 22 ; 2 ; 2 KD h TCU y Dc y y q y TCU y KD h TCU y Dc y y q y = + +    = = + +    Las funciones 1 y 2 alcanzan el mínimo en el punto 2 m DK yh = Gráficamente Calculamos Q: número de unidades para el que la función 2 alcanza el costo mínimo de la 1 21 ( ) ( ) m TCU Q TCU y= Juan Eloy Ruiz Castro 269 Calculamos Q: número de unidades para el que la función 2 alcanza el costo mínimo de la 1 21 ( ) ( ) m TCU Q TCU y= 21 2 22 2 DK h KD hQ KD h Dc Dc QDK h + + = + + ( ) ( ) ( ) 11 22 ; 2 ; 2 KD h TCU y Dc y y q y TCU y KD h TCU y Dc y y q y = + +    = = + +    21 2 2 22 2 20 KD h DK Q Dc Dc h DK KD h Qhh    − − −    + + = Juan Eloy Ruiz Castro 276 ( ) ( ) 11 1 11 , , , , , 2 n n n i i i nn i i i i ii yi i L y y TCU y y a y A K D h y a y A y   = ==  = − −     = + − −       donde  < 0 es un multiplicador de Lagrange. Los valores óptimos de  ,yise obtienen desde la siguiente condición necesaria dado que la función de Lagrange es convexa. 2 1 0 2 0 i i i i ii n ii i K D h La yy La y A   = = − + − =  = − + =  De la primera y segunda ecuación se tiene que y * * 2 2 ii i ii KD yha  =− Para *=0 se obtiene la solución sin restricciones. Si no se verifica la restricción, se obtienen los resultados aproximados dándole valores pequeños negativos a *hasta que se verifique la restricción, asociando en ese caso valores a los * i y * 1 n ii i a y A = =  Juan Eloy Ruiz Castro 277 Ejemplo. Analizar el siguiente inventario. Artículo i Ki(€) Di(uni. por día) hi(€) ai(m2) 1 2 3 10 5 15 2 4 4 0.30 0.10 0.20 1 1 1 Área total disponible para almacenamiento: 25 m2 Solución *11 1 1 22 10 2 11.55 0.30 KD yh  = = = *22 2 2 22 5 4 20 0.10 KD yh  = = = *33 3 3 22 15 4 24.49 0.20 KD yh  = = = Estas unidades ocupan: 56.04 m2 Juan Eloy Ruiz Castro 278 *11 1 11 22 10 2 6.34 2 0.348 0.30 2 0.348 1 KD yha  = = = +   +   Se realiza algoritmo computacional para el cálculo, con valores de  negativos pequeños, de forma que se verifique las restricción. Si se toma  = −0.348 *22 2 22 22 5 4 7.09 2 0.348 0.10 2 0.348 1 KD yha  = = = +   +   *33 3 33 22 15 4 11.57 2 0.348 0.20 2 0.348 1 KD yha  = = = +   +   Estas unidades ocupan: 25 m2 Juan Eloy Ruiz Castro 279 4.1.3 Modelos dinámicos de CEP Los modelos que a continuación se presentan difieren de los anteriores es dos aspectos: el nivel de inventario se revisa de forma periódica y la demanda puede cambiar de un periodo a otro. Un caso en el que se presenta la demanda dinámica determinista es el llamado planificación de los requerimientos de materiales (MRP). Veamos dos modelos: uno sin costo de preparación de pedido y otro con él. 4.1.3.1. Modelo sin costo de preparación Se tiene una planificación con nperiodos iguales. Cada periodo tiene una capacidad de producción limitada que puede incluir varios niveles de producción. En un momento se puede producir más que la demanda inmediata produciéndose un costo por almacenamiento. Juan Eloy Ruiz Castro 280 Supuestos: •No hay costo de preparación •No se permiten faltas • Función de costo unitario de producción es constante en cualquier periodo o tiene costos marginales crecientes. • Costo unitario de almacenamiento es constante. El problema de nperiodos se puede formular como un modelo de transporte con kn fuentes y ndestinos, donde kes la cantidad de niveles de producción por periodo. La capacidad de producción de cada una de las kn fuentes de nivel de producción proporciona las cantidades de oferta. Las cantidades de demanda son la demanda de cada periodo. La solución del problema como modelo de transporte determina las cantidades de producción con costo mínimo, en cada nivel de producción. Juan Eloy Ruiz Castro 281 Ejemplo. Exeldo produce compuertas para chimeneas domésticas que se usan durante los meses de diciembre a marzo. La demanda comienza lenta, llega a un máximo a la mitad de la estación y desaparece al final. Exeldo puede usar tiempo extra para satisfacer la demanda. La tabla siguiente muestra la producción y las demandas en los cuatro meses invernales. Capacidad Mes Normal (unidades) Extra (unidades) Demanda (unidades) 1 2 3 4 90 100 120 110 50 60 80 70 100 190 210 160 El costo unitario de producción en cualquier periodo es de 6€ durante el tiempo normal yde 9€ durante el tiempo extra. El costo mensual de almacenamiento es de 0.1€ por unidad. Juan Eloy Ruiz Castro 282 Mes Oferta acumulada Demanda acumulada 1 2 3 4 140 300 500 680 100 290 500 660 Para asegurar que el modelo no tiene faltantes “la oferta acumulada hasta determinado mes debe ser igual como mínimo a la demanda acumulada correspondiente”. Así, Solución Llamamos RiyOia los niveles de producción en tiempo normal y extra respectivamente en los distintos periodos. Como la oferta acumulada final es mayor que la demanda acumulada, se agrega un destino ficticio. Los costos unitarios de “transporte” son la suma de los costos de producción y almacenamiento. Obviamente, los costos de destino del excedente son cero. Juan Eloy Ruiz Castro 283 Excedente Costo Total: 4685 euros Capacidad Mes Normal (unidades) Extra (unidades) Demanda (unidades) 1 2 3 4 90 100 120 110 50 60 80 70 100 190 210 160 Juan Eloy Ruiz Castro 284 4.1.3.2. Modelo con costo de preparación Estamos en el supuesto anterior pero en este caso hay un costo de preparación cada vez que se inicia un lote de producción. Llamamos para los distintos periodos: zi: cantidad del pedido periodo i Di: demanda en el periodo i xi: inventario al inicio del periodo i Ki: costo de preparación en el periodo i hi: costo unitario de almacenamiento del periodo ide la cantidad del pedido Función costo de producción y preparación de pedido (el almacenamiento va por otro lado en la función a minimizar) para el periodo i ( ) ( ) 0 ; 0 ;0 i ii i i i i z Cz K c z z =  =+  siendo la función ci(zi)la función de costo marginal para zi. Juan Eloy Ruiz Castro 285 Algoritmo de programación dinámica El modelo se basa en minimizar la suma de los costos de producción y almacenamiento para los nperiodos. Para simplificar suponemos que el costo de almacenamiento para el periodo ise basa en el inventario de final del periodo que se define como xi+1 =xi+zi−Di. El estado de la etapa ise define como xi,el inventario al inicio del periodo. En este caso se tiene que 0i i n x D D  + + En el caso extremo al comienzo del periodo idebe haber un inventario que cubra la demanda completa restante. Sea fi(xi)el mínimo costo del inventario para los periodos ial último, dado el inventario de comienzo de periodo i,xi. Ecuación recursiva ( ) ( ) ( )   ( ) 1 0 11 1 ; 1,2,3,..., 0 0 n i j i ji i i i i i i i i i i z D x nn n f x mín C z h x f x z D i n fx x = +   − ++ + = + + + − =  = = Juan Eloy Ruiz Castro 292 z4=0 67 Solución óptima x4f4(x4) 0 67 --- 67 204 --- 204 67 67 0 Etapa 4 ( ) 4 4 4 4 C z h x+ * 4 z Periodo iDemanda DiCosto preparación KiCosto almacenamiento hi(€) 467 70 1 Juan Eloy Ruiz Castro 293 z3=0 67 90 157 Solución óptima x3f3(x3) 0 90 157 --- 294 224 --- 476 --- 569 --- --- 566 --- --- 566 294 224 157 0 0 * 3 z Etapa 3 ( ) ( ) 3 3 3 3 4 3 3 90C z h x f x z+ + + − Periodo iDemanda DiCosto preparación KiCosto almacenamiento hi(€) 3 4 90 67 185 70 1 1 f4(x4) 204 67 x4 0 67 Juan Eloy Ruiz Castro 294 z2=0 26 67 90 116 157 183 Solución óptima x2 f 2(x2 ) 0 26 116 183 --- 592 410 407 732 --- --- --- --- --- 588 --- --- 614 --- --- 640 --- --- --- --- 678 --- --- 704 --- --- --- 640 592 410 407 116 0 0 0 * 2 z Etapa 2 ( ) ( ) 2 2 2 2 3 2 2 26C z h x f x z+ + + − Periodo iDemanda DiCosto preparación KiCosto almacenamiento hi(€) 2 3 4 26 90 67 114 185 70 1 1 1 f3(x3) 566 294 224 x3 0 190 157 Juan Eloy Ruiz Castro 295 z 1 =61 87 177 244 Solución óptima x1 f 1(x1 ) 15 875 879 877 1008 875 61 * 1 z Etapa 1 ( ) ( ) 1 1 1 1 2 1 1 76C z h x f x z+ + + − Periodo iDemanda DiCosto preparación KiCosto almacenamiento hi(€) 1 2 3 4 76 26 90 67 98 114 185 70 1 1 1 1 f2(x2) 640 592 410 407 x2 0 26 116 183 Costo final: 875 euros Solución: Periodo 1 se piden 61 Periodo 2 se piden 116 Periodo 3 se piden 0 Periodo 4 se piden 67 Juan Eloy Ruiz Castro 296 Ejemplo (simplificado). Sea el siguiente modelo de inventario con cuatro periodos. Periodo iDemanda DiCosto preparación KiCosto almacenamiento hi(€) 1 2 3 4 76 26 90 67 98 114 185 70 1 1 1 1 Inicialmente se tiene 15 unidades. El costo unitario de producción es de 2€, y el costo unitario de almacenamiento es de 1€ en todos los periodos. Solución ( ) 0 ; 0 2 ; 0 i ii i i i z Cz K z z =  =+  ( ) ( ) ( )   ( ) 1 0 11 1 ; 1,2,3,..., 0 0 n i j i ji i i i i i i i i i i z D x nn n f x mín C z h x f x z D i n fx x = +   − ++ + = + + + − =  = = Juan Eloy Ruiz Castro 297 z4=0 67 Solución óptima x4f4(x4) 0 67 --- 67 204 --- 204 67 67 0 Etapa 4 ( ) 4 4 4 4 C z h x+ * 4 z Periodo iDemanda DiCosto preparación KiCosto almacenamiento hi(€) 467 70 1 Juan Eloy Ruiz Castro 298 z3=0 90 157 Solución óptima x3f3(x3) 0 90 157 --- 294 224 569 --- --- 566 --- --- 566 294 224 157 0 0 * 3 z Etapa 3 ( ) ( ) 3 3 3 3 4 3 3 90C z h x f x z+ + + − Periodo iDemanda DiCosto preparación KiCosto almacenamiento hi(€) 3 4 90 67 185 70 1 1 f4(x4) 204 67 x4 0 67 Juan Eloy Ruiz Castro 299 z2=0 26 116 183 Solución óptima x2 f 2(x2 ) 0 26 116 183 --- 592 410 407 732 --- --- --- 640 --- --- --- 704 --- --- --- 640 592 410 407 116 0 0 0 * 2 z Etapa 2 ( ) ( ) 2 2 2 2 3 2 2 26C z h x f x z+ + + − Periodo iDemanda DiCosto preparación KiCosto almacenamiento hi(€) 2 3 4 26 90 67 114 185 70 1 1 1 f3(x3) 566 294 224 x3 0 90 157 Juan Eloy Ruiz Castro 300 z 1 =61 87 177 244 Solución óptima x1 f 1(x1 ) 15 875 879 877 1008 875 61 * 1 z Etapa 1 ( ) ( ) 1 1 1 1 2 1 1 76C z h x f x z+ + + − Periodo iDemanda DiCosto preparación KiCosto almacenamiento hi(€) 1 2 3 4 76 26 90 67 98 114 185 70 1 1 1 1 f2(x2) 640 592 410 407 x2 0 26 116 183 Solución: Periodo 1 se piden 61 Periodo 2 se piden 116 Periodo 3 se piden 0 Periodo 4 se piden 67 Costo final: 875 euros Juan Eloy Ruiz Castro 301 Ejemplo. Determinar la política óptima del siguiente inventario Periodo iDemanda Di Costo preparación KiCosto almacenamiento hi(€) 1 2 3 4 5 6 10 15 7 20 13 25 20 17 10 18 5 50 1 1 1 3 1 1 Inicialmente hay 8 unidades y el costo unitario de producción es de 10 € para cada una de las unidades. Juan Eloy Ruiz Castro REFERENCIAS • Cao Abad, R. (2002) Introducción a la simulación y a la teoría de colas. A Coruña: Netbiblo. • Denardo, E. V. (2003) Dynamic Programming: Models and App: Models and Applications . Dover Books on Computer Science. • Kulkarni, V.G. (2011) Introduction to Modeling and Analysis of Stochastic Systems. Second Edition. Springer • Martín Martín, Q. (2003) Investigación Operativa. Pearson Prentice Hall. • Martín Martín, Q.; Santos Martín, M.T. y Paz Santana, Y.R. (2005) Investigación Operativa : problemas y ejercicios resueltos. Pearson Prentice Hall. • Ríos Insúa, S. (1993) Investigación Operativa: optimización. Centro de Estudios Ramón Areces. • Ríos Insúa, S.; Ríos Insúa, D.; Mateos Caballero, A.; Martín Jiménez, J. (2006) Problemas de Investigación Operativa. Ra-ma. • Sniedovich, M. (2010) Dynamic Programming: Foundations and Principles, Second Edition. CRC Press • Tijms, H.C. (2003) A First Course in Stochastic Models. John Wiley and Sons, Chichester.