Investigació operatica estocàstica. Problemes

EST IOE p R o B L E M E s 000 000 000 , DIPLOMATURA D'ESTADISTICA INVESTIGACIO OPERATIVA ESTOCASTICA Javier Heredia UPC FACULTAT DE MATEMÁTIQUES I ESTADÍSTICA UNIVEASITAT POI.IT�CNICA DE CATALUNYA Biblioteca IIIHllll�IIHllll1 llrn lll�l�IHI 1400844784 UNIVERSITAT POLITÉCNICA DE CATALUNYA BIBLIOTECA EX -LIBRIS Investigació Operativa Estocastica COL.LECCIO DE PROBLEMES Departament d'Estadística i lnvestigació Operativa Secció d 'Informa.ti ca Curs 94-95 Fecultat {i ':' L:'.' .. '. . . . '. ·.Y)S 1 Estadistica - D:b;i;.:.tci:a M 1. Estudiar los procesos estocásticos definidos por las matrices: 0.4 P1 =0.2 0.3 3 4 5 o 1/4 o 0.4 o 0.4 0.5 0.4 0.1 o-.s 0.2 1/4 1/4 1/2 0.6 0.8 0.2 1 1/4 1/2 0.1 0.5 0.2 0.1 0.1 0.2 o 0.4 o 1/2 o Dept. d'EIO/Curs 93-94/Problemes IOE o o 0.5 o 1/2 1/2 0.5 0.2 o 0.3 0.4 0.2 0.2 0.1 3/4 1/4 1/2 o 0.3 0.4 0.1 0.1 0.5 0.2 0.3 1 M2. Considerar un proceso markoviano con la siguiente matriz de probabilidades de transición: P= 1/8 1/2 3/4 1/8 1/4 o 3/4 1/4 1/4 a) ¿Cual es el tiempo medio de primer paso de 3 a 2? b) ¿ Cuales deberian ser las probabilidades iniciales de estado 7t ( O } = [ 7t 1 ( O }, 1t 2 ( O }, 1t3 (O)] para que el proceso entrase en estado estacionario despues de una transicion? M3. Un taller de reparaciones puede efectuar el trabajo A o el trabajo B pero no los dos simultaneamente; la tarea A requiere 2 días y la B 1 día. Los posibles estados del taller son pues: 1 = ninguna tarea, 3 = segundo día de la tarea A 2 = primer día de la tarea A 4= tareaB La probabilidad de una nueva demanda de tarea A al principio de cada día es a; la de la tarea Bes b. No hay colas, si el taller está a mitad de ejecución de una tarea A, la llegada de una nueva demanda se pierde. La única ambigüedad se plantea cuando el taller termina un trabajo al final de un día y tiene la posibilidad de empezar al dia siguiente con una tarea A o una B. Las dos políticas son posibles: 1) Empezar siempre con una tarea A con preferencia a una B 2) Empezar siempre con una tarea B con preferencia a una A a) Demostrar que para la política 1 la matriz de probabilidades de transicion es: (1-a) (1-b) a ob (1a) P= o o 1 o (1-a) (1b) a ob (1-a) (1-a) (1-b) a ob ( 1-a) b) Encontrar las probabilidades límite de estados para este proceso e) Encontrar la matriz de probabilidades de transición para la política 2 d) ¿ Cual es la relación entre los porcentajes límite de días de desocupación de ambas políticas? Dept. d'EIO/Curs 93-94/Problemes IOE 2 M 4. El siguiente proceso de Markov empieza en el estado 1 o 0.4 o 0.5 o 0.2 0.5 0.6 0.8 Encontrar las probabilidades de que: a) El proceso esté en el estado 3 despues de tres transiciones b) El proceso llegue al estado 3 por primera vez después de n transiciones e) El proceso no haya llegado aún al estado 2 después de n transiciones d) Después de la tercera transición desde el estado 3 hasta el 2 las dos transiciones siguientes sean ( 2➔1➔3) o { 2➔3➔3) e) El proceso entre en el estado 2 exactamente una vez en las tres primeras transiciones f)El proceso realice la transición 1 ➔ 2 exactamente una vez en las tres primeras transiciones g) El número esperado de veces que el proceso entrará en el estado 2 durante las tres primeras transiciones. MS. Supongamos que la probabilidad de que mañana llueva si hoy está lloviendo es 0.6, y que la probabilidad de que hoy haga buen tiempo si hoy hace buen tiempo es 0.4. M6. a) Determinar la matriz de probabilidades de transición de la cadena de Markov correspondiente. b) Hallar la distribución de probabilidad del estado estacionario. Determinar las clases de las siguientes cadenas de Markov y decir si son o no recurrentes o o 1/3 2/3 1 o o o a) 1 o o o b) o1/2 1/2 o o 1 o o o 1/2 1/2 o o 1 o o 1/2 o o 1/2 Dept. d'EIO/Curs 93-94/Problemes IOE 3 M7. Consideremos el siguiente juego: un jugador apuesta una unidad en cada partida. Tiene una probabilidad p de ganar y q=l-p de perder. seguirá jugando hasta que se arruina o alcanza una fortuna de T unidades. Sea Xn la fortuna del jugador en la n-ésima partida. Xn+l = (.Xn+ 1 Xn - 1 con probabilidad p} O< Xn < T con probabilidad q = 1 -p Xn+l = Xn Xn = O ó T {Xn} es una cadena de Markov. Supongamos que las sucesivas partidas del juego son independientes y que la fortuna inicial del jugador es Xo a) Determinar la matriz de probabilidades de transición de 1 paso de la cadena de Markov b)Hallar las clases de la cadena de Markov e) Sean T = 3 y p = 0.3 Hallar f 10, f lT• f 20, Í2T d) Sean T = 3 y p = 0.7 Hallar f 10, f n, f20, Í2T ¿Qué se puede deducir de c) y d)? MS. Supongamos que una red de comunicaciones transmite dígitos binarios O o l. Al recorrer la red, existe una probabilidad q de que el dígito binario se reciba de forma incorrecta en el siguiente paso. Si Xo denota un dígito binario que entra en el sistema, X1 el dígito recibido después de la primera transición, X2 el dígito recibido después de la segunda transición, ... Xn , entonces es una cadena de Markov. Hallar la matriz de probabilidades de transición y la distribución de probabilidad del estado estacionario. Dept. d'EIO/Curs 93-94/Problemes IOE 4 M9. Considerar la siguiente política (k,Q) de gestión de inventarios. Sean D1,D2, ... las demandas de un producto en los períodos 1,2, .... , respectivamente.Si la demanda durante un periodo excede el número de items disponibles, la demanda insatisfecha es retenida, de manera que se satisface cuando llega el siguiente pedido de reposición del inventario. Denotemos por Zn (n=0,1,2, ... ) la cantidad de inventario disponible menos el número de unidades retenidas antes de efectuar un pedido de reposición de inventario al final del periodo n (ZO=0). Si Zn es cero o positivo, no se retienen órdenes. Si Zn es negativo, entonces -Zn representa el número de unidades de demanda retrasada y no queda inventario disponible. Si al principio del periodo n, Zn<k=l, se efectua un pedido de reposición de 2m (Qm en el caso general) unidades, donde mes el menor entero tal que Zn+2m>=l. (La cantidad pedida es el menor múltiplo entero de 2, que lleva el nivel de inventario hasta al menos una unidad). Sean Dn variables aleatorias independientes e identicamente distribuidas que toman cada uno de los valores 0,1,2,3,4 con probabilidad 1/5. Denotemos por Xn el valor del stock disponible después de efectuar el pedido al final del periodo n (Xo=2). Resulta entonces: Xn=Xn-1-Dn+2m, Si Xn-1-Dn<l (n=l,2,3, .... ) Xn= Xn-1 - Dn, Si Xn-1-Dn >=1 y Xn es una cadena de Markov con solo dos estados: 1,2. a) Encontrar la Matriz de Transiciones b) Encontrar las probabilidades del estado estacionario e) Suponer que el coste de efectuar un pedido de reposición es (3+3m). El coste de mantenimiento del stock es Zn, si Zn>=O, y cero en caso contrario. El coste de ruptura del stock es -4Zn, si Zn<O. Encontrar el coste medio esperado por unidad de tiempo. d) Comprobar que, en general, para una politica (k,Q) los estados posibles son k,k+l,k+2, ...... ,k+Q-1. Dept. d'EIO/Curs 93-94/Problemes IOE 5 Q 5. Un técnico en reparaciones se ocupa del mantenimiento de 3 máquinas. Para cada máquina, la distribución de probabilidades del tiempo antes de que se estropee es exponencial de media 9 horas. El tiempo de reparación también es exponencial de edia 2 horas. a) Calcular la distribución de probabilidades en el estado estacionario del nº de máquinas que no funcionan b) Haciendo una aproximación muy burda, supongamos que la población de llegada es infinita de forma que el proceso de llegada sigue una distribución de Poisson de tasa media de 3 cada 9 horas. Comparar el resultado obtenido en a) con el que se obtiene al hacer esta aproximación: 1) Utilizando el modelo de cola infinita 2) Utilizando el modelo de cola finita e) Supongamos ahora que podemos disponer de un 2º técnico para reparar las máquinas siempre que haya más de una máquina estropeada. Calcular en este caso, lo mismo que en el apartado a). Q6. Actualmente se está realizando la planificación para una nueva fábrica. Un departamento va a recibir una gran cantidad de ciertas máquinas automáticas y deseamos determinar cuantas máquinas deberían asignarse a cada operador para sus servicio (carga, descarga, ajuste, arranque, etc.) Para realizar este análisis se proporciona la siguiente información: El tiempo de espera (tiempo desde que se completa un servicio hasta que la máquina requiere un nuevo servicio) de cada máquina, es exponencial de media 150 minutos. El tiempo de servicio tiene una distribución exponencial de media 15 minutos. Cada operador atiende únicamente tres máquinas y no ayuda ni recibe ayuda de los otros operadores. Para que el departamento alcance la tasa de producción necesaria, las máquinas deben funcionar por lo menos el 89 % del tiempo en media. a) ¿Cual es el máximo nº de máquinas que puede asignarse a cada operador manteniendo la tasa de producción? b) Cuando a cada operador se le asigna el máximo nº obtenido en a), ¿Cual es la fracción de tiempo esperada en la que los operadores estarán ocupados atendiendo las máquinas? Dept. d'EIO/Curs 93-94/Problemes IOE 12 Q7. Consideremos un sistema de colas con llegadas de Poisson, en el que el sirviente debe realiz.ar dos tareas diferenciadas de forma secuencial para cada cliente, de forma que el tiempo total de servicio es la suma de los tiempos de las 2 tareas (estadísticamente independientes). a) Supongamos que el tiempo de la 1 ª tarea es exponencial de media 3 minutos y que el tiempo de la 2ª tarea tiene una distribución de Erlang de media 9 minutos y K = 3. ¿Qué modelo debe utiliz.arse para representar este sistema? b) supongamos que a) se modifica de forma que el tiempo de la 1 ª tarea tambien sigue una distribución de Erlang con K = 3 (la media se mantiene en 3 minutos). ¿ Qué modelo debería utiliz.arse para representar este sistema? QS. Una base de mantenimiento de aviones dispone de recursos para revisar únicamente un motor de avión a la vez. Por tanto, para devolver los aviones lo antes posible, la política que se sigue consiste en aplazar la revisión de los 4 motores de cada avión. En otras palabras, solamente se revisa un motor del avión cada vez que un avión llega a la base. con esta política, los aviones llegan según una distribución de Poisson de tasa media uno al día. El tiempo requerido para revisar un motor (una vez que se empieza el trabajo) tiene una distribución exponencial de media 1/2 al dia. Se ha hecho una propuesta para cambiar la política de revisión de manera que los 4 motores se revisen de forma consecutiva cada vez que un avión llegue a la base. a pesar de que ello supondría cuadruplicar el tiempo esperado de servicio, cada avión necesitaría ser revisado únicamente con una frecuencia 4 veces menor. Utilizar la Teoría de colas para comparar las 2 alternativas. Dept. d'EIO/Curs 93-94/Problemes IOE 13 Q9. El servicio de información telefónica de un instituto meteorológico consta de una centralita con 4 lineas atendida por una única persona que es la que proporciona la información. Cuando llega una llamada, ésta se rechaza si en ese momento todas las líneas están ocupadas; en caso contrario, se aceptará la llamada y ésta ocupará alguna linea desocupada. la telefonista atiende las llamadas según una disciplina FIFO, tardando en cada una de ellas una media de 60 segundos. La tasa de llegada de las llamadas es de 3 por minuto. Suponiendo que el número de llamadas que se reciben sigue una distribución de Poisson y que el tiempo que se tarda en atenderlas sigue una distribución exponencial, responder a las siguientes cuestiones; a) ¿Qué modelo permite estudiar el comportamiento de la centralita?. Dibujar el diagrama de tasas b) ¿Cual es el tiempo medio de espera hasta que se atiende una llamada? e) ¿Con qué probabilidad se rechaza una llamada? d) Actualmente se está considerando la posibilidad de ampliar el servicio de la centralita para reducir la probabilidad de rechazar una llamada. Las posibilidades que se están estudiando son: 1) Conectar a la centralita otras 4 lineas nuevas, manteniendo una única telefonista 2) Mantener las 4 lineas actuales pero contratar una nueva telefonista que trabajaría conjuntamente con la que ya está y a un ritmo de trabajo similar. ¿Cual de las 2 alternativas te parece más conveniente? Dept. d'EIO/Curs 93-94/Problemes IOE 14 QlO. Consideremos los siguientes diagramas de tasas, correspondientes a diferentes modelos de colas para procesos de nacimiento y muerte. 1) i.. i.. i.. 0000 '-.J'-.J'-.J eµ Donde c es una constante, O < c < 1 2) ... i.. i.. i.. i.. i., ,---.....,---..... ,---.....,---......,..z-x 0 G 0 0 (¿) 0•■- '-.J'-.J'-.J'-.J '-.J µ 2µ 2µ 3µ 3µ 3) µ µ µ Responder a las siguientes cuestiones: 3µ 3µ 'J.Jn ')Jn + 1 ,---.....,---..... e 0 e ... '----...1 '---...I µ µ a) Para todos los modelos anteriores (1,2 y 3) describir brevemente con qué tipo de situaciones se corresponden. Nota: b) Para los modelos 2 y 3 dar una expresión (lo más compacta posible) de Poc) Para el modelo 3 obtener el tiempo medio de espera en el sistema. ¿Cual será la longitud media del sistema cuando A = µ ? - L an=-1 -,si a<l. 1 - a n=O Dept. d'EIO/Curs 93-94/Problemes IOE 15 Q 11. Una gestoría dispone de tres personas que atienden al público; cada una de ellas tarda una media de 10 minutos en atender a un cliente. a) Supongamos que los clientes llegan con una tasa de 15 por hora. a.1) ¿Con qué probabilidad un cliente tiene que esperar para ser atendido? a.2) ¿Cual es el número medio de clientes en la cola? a.3) ¿Cual es el tiempo medio de espera en el sistema? b) Supongamos que se estructura la gestoría en tres servicios: uno dedicado a las gestiones de compra/venta, el segundo para documentación (DNI, pasaportes, carnets de conducir, ... ) y el tercero para las restantes gestiones. ahora, la tasa de llegada de los clientes a cada uno de los servicios es de 5 por hora. Además, cada uno de los tres empleados está asignado a un único servicio. b.1) ¿Con qué probabilidad un cliente tiene que esperar para ser atendido? b.2) ¿Cual es el número medio de clientes en la cola? b.3) ¿Cual es el tiempo medio de espera en el sistema? e) ¿Cual de las 2 alternativas anteriores te parece más conveniente? Razónalo. Q 12. Una estación de servicio tiene una única bomba de gasolina. Los coches que requieren servicio llegan según un proceso de Poisson con una tasa media de 20 . vehículos por hora. Si la bomba ya está sirviendo a un cliente los clientes potenciales pueden marcharse para ser atendidos en otra estación de servicio próxima. En particular si hay n coches en la estación de servicio, la probabilidad de que un cliente potencial se marche es de n / 4 para n = 1,2,3,4. El tiempo requerido para servir un coche es exponencial de media 3 minutos. a) Hallar la distribución de probabilidad del estado estacionario b) Encontrar el tiempo medio de permanencia en el sistema Dept. d'EIO/Curs 93-94/Problemes IOE 16 Ql3. Un vendedor de helados ha instalado un puesto de venta en un area de descanso de una autopista de manera que puede atender a los clientes sin que tengan que apearse. El concesionario de la autopista le ha alquilado un espacio con capacidad para cuatro vehículos contando el que esta siendo atendido. La tasa media de llegadas de los clientes es de 40 coches por hora y el puesto puede servir hasta 50 coches por hora. El beneficio neto por los helados vendidos a cada coche es de 50 pesetas. Teniendo en cuenta que el puesto de venta de helados está abierto durante 14 horas diarias, y que el concesionario de autopistas está dispuesto a alquilarle espacio adicional a 500 pesetas/día por plaza de coche, ¿Qué debe hacer? ¿Ha de alquilar plazas extra?. En caso afirmativo, ¿cuantas?. Q14. En cierto centro oficial existe un aparcamiento público gratuito con cuatro plazas. Los coches con intención de aparcar llegan a un ritmo de 6 por hora en promedio. Si encuentran plaza aparcan, si no deben buscar otro lugar, por ejemplo un aparcamiento subterráneo, de pago cerca de allí. En promedio cada coche permanece aparcado 30 minutos. Se pregunta: a) Probabilidad de que un coche que llegue al aparcamiento público gratuito pueda aparcar. b) Suponiendo que el aparcamiento público gratuito esté completo ¿Cuánto deberá aguardar, en promedio, un coche situafdo en doble fila, hasta que quede plaza libre? e) ¿Cuántas plazas de aparcamiento público gratuito deberían exixti.r para que el 85% de los coches que se dirigen al centro oficial puedan aparcar en él? Dept. d'EIO/Curs 93-94/Problemes IOE 17 Q 15. Un taller cuenta con tres máquinas idénticas que se averían según un proceso poissoniano de parámetro A . El coste de tener una máquina parada durante un día es de Apts. El taller cuenta, asimismo, con dos equipos para la detección y reparación de averías. Para cada uno de ellos el tiempo necesario para una reparación se distribuye según una ley exponencial. Uno de los equipos, el más antiguo, tiene un coste de funcionamiento de R pts/día y puede realizar hasta µ reparaciones/día, el doble de la tasa de averías de cada máquina. El otro equipo. más moderno, tiene un rendimiento triple que el del primero y un coste de funcionamiento también triple. El jefe de taller tiene que decidir entre dos políticas, para lo cual desea estimar los costes medios: a) Utilizar el equipo antiguo cuando sólo hay una máquina averiada b) Utilizar el equipo moderno cuando sólo hay una máquina averiada (Evidentemente, cuando hay dos máquinas averiadas, o las tres. trabajan los dos equipos de reparación) e) ¿Cual es la política óptima en función de la relación de costes A/R) Q16. En un taller hay cuatro máquinas que se averían, en promedio, cada 200 horas. Las averías son reparadas por un único equipo que tarda un promedio de 8 horas por avería. Cada máquina parada produce una pérdida de 8.000 pts/hora. a) ¿Qué fracción de tiempo hay por lo menos dos máquinas trabajando? b) ¿Resultaría rentable la instalación de una máquina que funcionase cuando alguna de las otras se avería sustituyendola, si la instalación supone una inversión de 10.000.000 pts a amortizar en cuatro años, considerando que hay 2000 horas de trabajo al año? Q 1 7. Una estación de servicio tiene una bomba de gasolina. Los coches que requieren servicio llegan según un proceso de Poisson con una tasa media de 20 vehículos por hora. Si la bomba está ocupada los clientes potenciales pueden marcharse para ser atendidos en otra estación. En particular, si hay n coches en la estación, la probabilidad de que un cliente potencial se marche es de n / 5 para n = 1,2,3,4,5. El tiempo requerido para servir un coche es de 3 minutos, en promedio, exponencialmente distribuidos. a) Identificar el modelo de colas y calcular b) Calcular el tiempo medio de permanencia en el sistema e) ¿Cual sería la ventaja si hubiesen 2 bombas de gasolina? Dept. d'EIO/Curs 93-94/Problemes IOE 18 Ql8. En una pequeña ciudad operan dos empresas de taxis. Cada una de ellas tiene dos taxis, y ambas se reparten el mercado en condiciones de igualdad. Esto resulta evidente por el hecho de que las llamadas telefónicas que llegan al servicio de atención al público de cada una de las empresas, siguen una distribución de Poisson de tasa media A=lO llamadas por hora en ambos casos. La duración media de una carrera de taxi es de 11.5 minutos, y sigue una distribución de probabilidad exponencial. Uno de los hombres de negocios de la ciudad ha comprado recientemente las dos empresas, y su primera preocupación es fusionar los dos servicios de atención al público en uno sólo, con el objetivo de ofrecer un servicio más rápido a los clientes, es decir, que tengan que esperar menos a que los recoja el taxi solicitado. ¿Es esto cierto, qué un único servicio de recepción de llamadas que fusione los dos existentes será más eficiente que los dos trabajando independientemente?. A pesar de todo, operando con un servicio único de atención al cliente, el propietario de la empresa fusionada piensa que el tiempo de espera hasta que el cliente recibe el servicio es excesivo, y como no dispone de capital para incrementar el número de taxis decide que la oficina que atiende las llamadas de los clientes para pedir servicio les comunique que no puede atender su petición cuando la lista de clientes a la espera de ser atendidos sea de 16. ¿Qué efectos tendrá esta decisión en los tiempos de espera?. ¿Cúal será el porcentaje de clientes perdidos?. Dept. d'EIO/Curs 93-94/Problemes IOE 19 Q 19. Los encargados de un servicio de lavado de coches instalado en un centro comercial desean efectuar un estudio sobre su rendimiento. Para ello registran la pauta de llegadas de vehículos por hora con los resultados siguientes: No. de llegadas O 1 2 3 4 56 7 8 9 10 11 12 13 14 15 16 Frecuencia 1 3 5 14 20 41 68 73 77 65 52 29 20 18 6 5 3 a) Comprobar si la pauta de llegadas es poissoniana El dispositivo de lavado puede atender solamente un coche a la vez, pero debido a los distintos tipos de servivio que puede ofrecer (lavado simple, lavado más bajos, lavado y encerado, etc.), el estudio de la duración de los procesos de servicio revela que siguen una distribución de probabilidad de tipo normal, con una media de 6 minutos, y una desviación estandard de 2 minutos. b) Tiempo medio diario que el servicio de lavado está desocupado en una jornada de 10 horas/día. e) Número medio de coches a la espera de ser lavados. d) Tiempo medio de espera total de todos los clientes que llegan en las 10 horas de apertura diaria Dept. d'EIO/Curs 93-94/Problemes IOE 20 Diplomatura d'Estadística UPC IOE SOLUCIÓ PROBLEMES CADENES DE MARKOV a) µ32 = 52/3; b) 1r(O)' = ( 9/20 3/40 19/40) b)_(1-a)(l-b). __ a. -(1-a)b 11"1 -l+a , 11"2 -11"3 -1+a' 1r4 -l+a ' ((1-a)(l-b) a(l-b) O b) e)p _ O O 1 O -(1-a)(l-b) a(l-b) O b (1-a)(l-b) a(l-b) O b d} Probabilitats de estat estacionari per a la segona política : _ (1-a�(l-b). _ _ a(l-b) . _ b 7rt -l+a 1-b) 1 11"2 -11"3 -t+a(l-b) 1 11"4 - l+a(l-b)' Rl ., lítº 1)º2)· (1-a)(l-b)/(l+a) -l ab l e ac10 11"1 po 1ques I . (l-a)(l-b)/(t+a(t-6)) --Ha < un percentatje de dies desocupats menor =} més favorable. a) pg> = O. 72; b)p = { (P12P21) :�: P12P23 (P12P21) ,-Pt3 n parell n senar ) P n-1 e = P13P33 i =} amb la política 2) s'obté d) CM =} les transicions abans de Xt = 2 no afecten a les transicions posteriors : p = (p21p13) + (p23p33) = 0.68 e)P = P12(P21P13 + P23p33) + p13p32 + P13p33p32 = 0.52 f) P= P12P21P13 + P12P23p33 + P12P23p32 = 0.4 g) E= 1 X 0.52 + 2 X 0.16 + 3 X 0. = 0.84 a) P= ( �:: �:!). b) 1r' = ( 0.6 0.4 ). a) Tots els estats recurrents i comuniquen : cadena irreduible. Estats periodics amb periode 3. b) Tres clases : C1 = {1},C2 = {4},C3 = {2, 3}. Estat 1 absorbent, estat 4 transitori, estats 2 i 3 recurrents aperiodics. 1