Investigación de Operaciones II

Cadenas de Markov

1. Proceso Estocástico distribución de Poisson con media de 1. La empresa tiene la

siguiente politica de inventario:
Es un modelo de probabilidad acerca de un proceso que evoluciona
en el tiempo de manera probabilística. Un proceso estocástico se  Si Xt=0, ordena 3 cámaras.
define como la colección indexada de variables aleatorias X t, donde  Si Xt>0, no ordena cámaras.
el índice t toma valores de un conjunto T dado. Con frecuencia T se
Donde Xt es una variable aleatoria que representa el número de
considera el conjunto de enteros no negativos mientras que X t
cámaras disponibles al final de la semana t.
representa una característica de interés cuantificable en el tiempo t.
Modelar la siguiente situación como una cadena de Markov y
Estos procesos modelan el comportamiento del sistema durante
realizar el diagrama de transición de estados y la matriz de
algunos periodos de tiempo.
transición.
Ejercicio 01: El clima en Barranquilla cambia con cierta rapidez de un
2.1.Clasificación de estados en una cadena de Markov
día a otro. En particular, la probabilidad que mañana este seco si
hoy está seco es de 0.8, pero es de solo 0.6 si hoy llueve.
 Estado accesible: un estado al que se puede acceder desde
Modelar como un proceso estocástico. otro estado.
 Estado recurrente: un estado tiene este nombre si, después
2. Cadena de Markov
de haber entrado a este estado, el proceso definitivamente
Es un proceso estocástico donde se cumple la propiedad regresará a ese estado, por tanto un estado es recurrente
markoviana. Se dice que un proceso estocástico X t tiene la sino es transitorio. Si una cadena de Markov solo tiene
propiedad markoviana si P ( x t+1 / x t + x t −1 ) =P ( x t +1 / x t ) estados recurrentes, a esta se le denomina “Cadena de
Markov Ergódica”.
Una cadena de Markov tiene las siguientes propiedades:  Estado transitorio: un estado tiene este nombre, si después
de haber entrado a este estado, el proceso nunca regresa a
 Un número finito de estados.
él.
 Probabilidades de transición estacionarias, por ejemplo:
 Estado absorbente: un estado tiene este nombre si, después
p p01 de haber entrado ahí, el proceso nunca saldrá de él.
[
P= 00
p 10 p22 ] Si una cadena de Markov tiene estados transitorios y absorbentes, a
Ejercicio 02: Una empresa que distribuye maquinaria pesada tiene esta se le denomina “Cadenas de Markov con estados
una demanda aleatoria que se puede modelar mediante una absorbentes”.

1
Investigación de Operaciones II
Cadenas de Markov

mañana, si hoy el clima es seco. Esto está dado por:

P ( x t+1 =¿/ x t=S ).
2.2.Cadenas de Markov Ergódicas
Pero en una cadena de Markov, es importante no solamente
Para definir una cadena de Markov Ergódica es importante definir: establecer la matriz de transición en un solo paso, sino calcular la
 La matriz de transición P. Esta es una matriz cuadrada que matriz de transición en dos pasos, tres pasos, cuatro pasos y así
tiene tantas posiciones como estados tenga la cadena de sucesivamente hasta determinar la matriz en n pasos.
Markov. Para realizar este cálculo se hace uso de la multiplicación matricial,
 La posición o el paso inicial de la cadena. Este está de la siguiente manera.
determinado por el vector fila a 0 que tiene tantas posiciones
como estados tenga la cadena de Markov. P(2 )=P2=P . P
P(3 )=P3=P . P (2)
Para mayor claridad, en el ejemplo 01 se tienen dos estados, clima
P( 4)=P 4=P . P (3)
seco y lluvioso, si el caso mencionara, “Si hoy el clima es seco, cual
.
es la probabilidad que en 3 días sea lluvioso el clima”.
.
Si el vector que define la posición de la cadena está definido de la P(n )=Pn=P . P(n−1)
siguiente manera, a 0=¿, el vector inicial para este caso sería: Al realizar esta operación n veces se obtienen las probabilidades de
estado estable de la siguiente manera:
a 0=( 1,0 )
lim P(n)
ij =π j
Si el ejemplo mencionara, “Si hoy la probabilidad de que el clima sea n →∝

seco es del 80%, cual es la probabilidad que en 3 días sea lluvioso el 2.2.2. Calculo del vector n de la Cadena de Markov
clima”, el vector inicial sería:
Un paso posterior al inicial de la Cadena de Markov está definido
a 0=( 0.8 , 0.2 ) por a n. Para realizar el cálculo de esta, se utiliza la siguiente
2.2.1. Matriz de transición de n pasos formulación:
( 1) (0)
La matriz de transición de una cadena de Markov determina la a =a P
( 2) (1) (0) (2)
probabilidad de pasar de un estado a otro estado en un solo paso. a =a P=a P
( 3) (2) (0) (3 )
Por ejemplo, la probabilidad que el clima sea lluvioso el día de a =a P=a P

2
Investigación de Operaciones II
Cadenas de Markov

. El análisis de estados absorbentes es diferente al análisis que se

. realiza con estados recurrentes. Para realizar este análisis es
a (n)=a(0 ) P(n) necesario construir la matriz de transición de la siguiente manera:

P= N A
2.2.3. Calculo del tiempo medio de recurrencia 0 ( 1 )
Donde:
Algo muy importante en el estudio de Cadenas de Markov Ergodicas
N= Matriz de estados transitorios a estados transitorios
es la determinación del número esperado de transiciones antes de
A= Matriz de estados transitorios a estados absorbentes
que el sistema regrese a un estado j por primera vez, se calcula de la 1= Matriz identidad
siguiente manera:

1 Con esta matriz se pueden realizar los siguientes cálculos:

μ jj = , j=1, 2,3,…, n
πj −1
( I −N j ) = Tiempo esperado para llegar al estado j iniciando en el
2.2.4. Calculo del tiempo del primer paso estado i.
−1
Es el tiempo medio de transiciones para llegar por primera vez al ( I −N j ) .1= Tiempo esperado para la absorción.
−1
estado j desde el estado i. Para realizar el cálculo se realiza de la ( I −N j ) . A = Probabilidad para la absorción.
siguiente manera:
3. Problemas propuestos.
−1
μi j =( I −N j ) 1 , j ≠i
Ejercicio 03: Las familias de cierto país se clasifican según residan en
Donde áreas rurales, urbanas o suburbanas. Los estudios de movilidad
I = matriz identidad (m-1) demográfica estiman que, en promedio, en el curso de un año, el
N j= Matriz de transiciones P sin su fila j-esima y columna j-esima del 15% de las familias urbanas cambia de residencia y se traslada a un
estado del destino j área suburbana, y el 5% a un área rural; mientras que el 6% de las
1= Vector columna (m-1) con todos los elementos iguales a 1. familias residentes en áreas suburbanas se traslada a áreas urbanas,
y el 4% a áreas rurales, y finalmente el 4% de las familias rurales
2.3.Cadenas de Markov con estados absorbentes migra a las áreas urbanas y el 6% a las suburbanas.

 ¿Cuál es la probabilidad de que una familia que vive

ahora en un área urbana siga viviendo en un área

3
Investigación de Operaciones II
Cadenas de Markov

urbana dentro de dos años? ¿Y en una suburbana?. ¿Y  Formular esta situación como una Cadena de Markov,
en una rural? describir los estados y las suposiciones y desarrollar
 Supongamos que en el presente el 40% de las familias una matriz de transición.
del país viven en áreas urbanas, el 35% en suburbanas y  Es posible contratar un ayudante adicional, con un
el 25% en rurales. ¿Qué porcentaje de familias vivirá en costo de $10, con el objeto de que la falla siempre sea
áreas urbanas dentro de dos años? reparada dentro del mismo periodo. ¿Es conveniente
 ¿Qué distribución de población es de prever en el futuro hacer esto? Si no lo es, ¿Cuánto estaría dispuesto a
si las tendencias no cambian? pagar por esto?

Ejercicio 04: Suponiendo que cada año el 50% de los alumnos Ejercicio 06: Un proceso de producción consta de tres etapas
de primero pasa a segundo, el 30% permanece en primero y el secuenciales E1, E2, E3. En la etapa 1 se genera un 7% de no
20% abandona; de los alumnos de segundo el 50% pasa a conformes que no son recuperables. El 10% de la producción
tercero, el 40% permanece en segundo y el 10% abandona, y de que llega a la etapa dos, son artículos no conformes. El 90% de
los alumnos de tercer curso el 60% terminan o abandonan y el los artículos no conformes que llegan a la etapa dos, se
40% repiten tercero, se pide: recuperan por reproceso en la misma etapa para lograr
artículos conformes, el 5% de ellos no se logran recuperar.
 Escribir la matriz de transición describiendo Los restantes se reprocesan en la etapa1. En la etapa 3 se
previamente los estados del proceso. pierde un 5% de la producción, el 6% se reprocesa en la
 Si entran 600 alumnos un año en primer curso, calcular etapa2. A continuación, en la sección de empaque, debido al
cuántos habrá en cada curso (de esos 600) al principio mal manejo,
del tercer año. un 3% se clasifica como producto terminado de segunda, El
 De los 600, ¿Cuántos niños abandonan? resto va a despacho. Cada una de estos artículos se vende en
120um. El costo directo respectivo en cada etapa es: 200um,
150um, 130um, 60um por artículo. Los artículos reprocesados
Ejercicio 05: Una máquina funciona durante un determinado provocan un costo adicional de 6um cada uno.
periodo de tiempo con una probabilidad de falla de 0.3. El 60 %
de las veces la falla puede repararse exactamente en un  Calcule el número de unidades que se deben programar
período, y en los demás casos se requieren exactamente dos en la etapa uno para obtener Q = 180000 unidades
periodos para la reparación. Se puede suponer que las fallas se conformes
presentan al final de un periodo. El costo por tiempo perdido es  Calcule el costo total del número promedio de unidades
de $50 por periodo. fabricadas para Q=180000 unidades conformes.

4
Investigación de Operaciones II
Cadenas de Markov

 Calcule el costo promedio por unidad conforme

producida.  Si hoy el viajante está en C, ¿cuál es la probabilidad de
 que también tenga que trabajar en C al cabo de cuatro
Ejercicio 07: El ascensor de un edificio con bajo y dos pisos días?
realiza viajes de uno a otro piso. El piso en el que finaliza el  ¿Cuáles son los porcentajes de días en los que el agente
viaje n-ésimo del ascensor sigue una cadena de Markov. Se comercial está en cada una de las tres ciudades?
sabe que la mitad de los viajes que parten del bajo se dirigen a
cada uno de los otros dos pisos, mientras que si un viaje Ejercicio 09: Suponga que toda la industria de refresco produce
comienza en el primer piso, sólo el 25% de las veces finaliza en dos colas: Coca Cola y Pepsi Cola. Cuando una persona ha
el segundo. Por último, si un trayecto comienza en el segundo comprado Coca Cola hay una probabilidad de 90% de que siga
piso, siempre finaliza en el bajo. Se pide: comprándola la vez siguiente. Si una persona compró Pepsi, hay
80% de que repita la vez siguiente. Se pide:
 Calcular la matriz de probabilidades de transición de la
cadena  Si una persona actualmente es comprador de Pepsi.
 Dibujar el grafo asociado ¿Cuál es la probabilidad de que compre Coca Cola
 ¿Cuál es la probabilidad de que, a largo plazo, el pasadas dos compras a partir de hoy?
ascensor se encuentre en cada uno de los tres pisos.  Si en la actualidad una persona es comprador de Coca
Cola. ¿Cuál es la probabilidad de que compre Coca Cola
Ejercicio 08: Un agente comercial realiza su trabajo en tres pasadas tres compras a partir de ahora?
ciudades A, B y C. Para evitar desplazamientos innecesarios está  Supongamos que el 60% de toda la gente toma hoy
todo el día en la misma ciudad y allí pernocta, desplazándose a Coca Cola y el 40% Pepsi. A tres compras a partir de
otra ciudad al día siguiente, si no tiene suficiente trabajo. ahora, ¿Qué fracción de los compradores estará
Después de estar trabajando un día en C, la probabilidad de tomando Coca Cola.
tener que seguir trabajando en ella al día siguiente es 0,4, la de  Determinar el estado estable.
tener que viajar a B es 0,4 y la de tener que ir a A es 0,2. Si el
viajante duerme un día en B, con probabilidad de un 20%
tendrá que seguir trabajando en la misma ciudad al día
siguiente, en el 60% de los casos viajará a C, mientras que irá a
A con probabilidad 0,2. Por último si el agente comercial trabaja
todo un día en A, permanecerá en esa misma ciudad, al día
siguiente, con una probabilidad 0,1, irá a B con una
probabilidad de 0,3 y a C con una probabilidad de 0,6.

5
Investigación de Operaciones II
Cadenas de Markov