Investigacion Operativa

PROBLEMAS DE CADENAS DE MARKOV

M1. Estudiar los procesos estocásticos definidos por las matrices:

M2. Considerar un proceso markoviano con la siguiente matriz de probabilidades de transición:

a) ¿Cual es el tiempo medio de primer paso de 3 a 2?

b) ¿Cuales deberian ser las probabilidades iniciales de estado

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 dias y la B 1 dia. Los posibles estados del taller son pues:

1 = ninguna tarea, 2 = primer dia de la tarea A

3 = segundo dia de la tarea A 4 = tarea B

La probabilidad de una nueva demanda de tarea A al principio de cada dia es a; la de la tarea B es 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 dia 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:

b) Encontrar las probabilidades límite de estados para este proceso

c) 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 dias de desocupación de ambas políticas?

M4. El siguiente proceso de Markov empieza en el estado 1

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

c) 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 o

e) El proceso entre en el estado 2 exactamente una vez en las tres primeras transiciones

f) El proceso realice la transición 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.

M5. Supongamos que la probabilidad de que mañana llueva si hoy está lloviendo es 0.6, y que la probabilidad de que mañana haga buen tiempo si hoy hace buen tiempo es 0.4.

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.

M6. Determinar las clases de las siguientes cadenas de Markov y decir si son o no recurrentes

M7. Consideremos el siguiente juego: un jugador apuesta una unidad en cada partida. Tiene una probabilidad p de ganar y q=1-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.

= 0 < Xn < T

Xn+1 = Xn Xn = 0 ó T

es una cadena de Markov. Supongamos que las sucesivas partidas del juego son independientes y que la fortuna inicial del jugador es X0

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

c) Sean T = 3 y p = 0.3 Hallar 

d) Sean T = 3 y p = 0.7 Hallar 

¿Qué se puede deducir de c) y d)?

M8. Supongamos que una red de comunicaciones transmite dígitos binarios 0 o 1. Al recorrer la red, existe una probabilidad q de que el dígito binario se reciba de forma incorrecta en el siguiente paso. Si X0 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.

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 (Z0=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=1, se efectua un pedido de reposición de 2m (Qm en el caso general) unidades, donde m es el menor entero tal que Zn+2m>=1. (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 (X0=2). Resulta entonces:

Xn= Xn-1 - Dn+2m, Si Xn-1-Dn<1

(n=1,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

c) Suponer que el coste de efectuar un pedido de reposición es (3+3m).

El coste de mantenimiento del stock es Zn, si Zn>=0, y cero en caso contrario.

El coste de ruptura del stock es -4Zn, si Zn<0. 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+1,k+2,......,k+Q-1.

M10. El Servicio Hidrológico de la Comunidad Autónoma de X planea construir un embalse para regular la cuenca de uno de sus rios con el objetivo de satisfacer los requerimientos de agua para regadío. La capacidad máxima del embalse previsto será de 4.000.000 m3, o, de manera abreviada 4 unidades de agua (1 unidad de agua = 1.000.000 m3 ).

Antes de proceder a la construcción el Servicio desearia tener alguna idea sobre la efectividad del mismo a largo plazo. Para ello se ha llevado a cabo un estudio sobre los volúmenes semanales de agua aportados por el río, encontrándose con que ppueden aproximarse por medio de la siguiente distribución de probabilidad discreta:

Aportación semanal

en unidades de agua 2 3 4 5

-------------------------------------------------------------------

Probabilidad 0.3 0.4 0.2 0.1

El Servicio está considerando la posibilidad de contratos de regadío que requeriran el consumo de 2 unidades de agua por semana, pero adicionalmente, para mantener los estándares de calidad del agua para otros usos, deberá dejar salir al menos 1 unidad de agua por semana. Por lo tanto el objetivo semanal será dejar salir 3 unidades de agua. Si el estado del embalse (nivel del embalse) más la aportación de agua del rio es menor que esta cantidad se tendrá que dejar salir menos agua, afectando la carencia a los regadios. Si el embalse está lleno, cualquier exceso será vertido por los aliviaderos. El nivel mínimo admitido del embalse (estado mínimo) no podrá ser inferior a una unidad de agua.

a) Representar el diagrama de transiciones, encontrar la matriz de probabilidades de transición, y comprobar que se trata de un proceso markoviano.

b) ¿Cual será el número medio de semanas transcurrido desde que el embalse se encuentra en el estado con 2 unidades de agua hasta que esté totalmente lleno?

c) Supuesto el embalse en el estado mínimo con 1 unidad de agua, ¿Cuantas semanas tardará, en promedio, en volver a estar en la misma situación?

d) Suponiendo que la primera semana partimos de una situación en la que se embalsaban 3 unidades de agua ¿Cual es la probabilidad de que dos semanas después se encuentre al mínimo?.

M11. Una tienda de venta de ordenadores personales tiene un modelo particular cuyo stock puede reponerse semanalmente.

Representemos por D1, D2,....., la demanda de este modelo durante la primera semana, la segunda, etc.. Suponemos que las demandas Di son variables aleatorias independientes e identicamente

...