Investigación de Operaciones II UNIDAD 4. Cadenas de Markov

Investigación de Operaciones II

UNIDAD 4. Cadenas de Markov

4.4.1. Estados absorbentes

Cadenas absorbentesUna cadena de Markov con espacio de

estados finito se dice absorbente si se cumplen las dos condiciones siguientes:

1. La cadena tiene al menos un estado absorbente.

2. De cualquier estado no absorbente se accede a algún estado absorbente.


Si denotamos como A al conjunto de todos los estados absorbentes y a su complemento como D, tenemos los siguientes resultados:

Su matriz de transición siempre se puede llevar a una de la forma


donde la submatriz Q corresponde a los estados del conjunto D, I es la matriz identidad, 0 es la matriz nula y R alguna submatriz.

, esto es, no importa en donde se encuentre la cadena, eventualmente terminará en un estado absorbente.


Ejemplo.

Modelo de enfermedad. Este modelo se puede representar por 4 estados: ◦E1 donde las personas no tienen enfermedad, ◦E2 donde las personas tienen la enfermedad, ◦E3 estado muerte como consecuencia de la

enfermedad y ◦E4 estado muerte por otras causas.


El correspondiente diagrama de transición es:


Supongamos la siguiente matriz de transición:


Se tienen dos estados absorbentes E3 y E4, y la interpretación que de las probabilidades individuales son las siguientes: p11 = 1/2 significa que una persona dado que no está enferma en un periodo tiene una probabilidad de 1/2 de no estarlo en el siguiente periodo, p24

= 1/8 significa que una persona dado que no está enferma en un periodo tiene una probabilidad de 1/8 de morir en el siguiente periodo por otras causas y así sucesivamente.


En este ejemplo la matriz de transición tiene la siguiente forma típica:

donde, en este caso,


Entonces, un estado es absorbente cuando una vez que se entra en él no se puede salir del mismo.

Un estado Ei es absorbente sipii = 1pij = 0 (i 6= j, j = 1, . . . , m)

en la i-ésima fila de T.

4.5.1. Uso de software

PROCESO DE MARKOV

La opción Nuevo Problema (New Problem) genera una plantilla llamada Especificaciones del problema PMK (MKP Problem Specification) en la cual, se introducirán las características de nuestro problema:



Para comenzar a armar un problema de este tipo es necesario ingresar los campos:

Título del problema (Problem Title) Número de estados (Number of

States)


Un poco de teoría

Un sistema existe en estados diferentes (o condiciones). A través del tiempo, el sistema se moverá de un estado a otro estado. El proceso de Markov normalmente se usa para caracterizar estos movimientos o transiciones.


Para describir y analizar un proceso de Markov, definimos las terminologías siguientes:

Estado: una condición particular del sistema, i = 1, 2,..., n.

Probabilidad de estados s(i): la probabilidad de que el sistema se encuentre en el estado i

Probabilidad de transición p(i,j): la probabilidad de que el sistema se mueva del estado i al estado j

S(t): conjunto de todos s(i) en momento t, Ʃs(i) = 1P: matriz de transición p(i,j), dónde i=1,2,…,m yj =

1, 2,... ,n


Dado el sistema en el momento t con las probabilidades de estado S(t), entonces en el momento t+1, el sistema se expresará por S(T+1) = S(T) P

Y en el t+2 , el sistema se expresará por S(T+2) = S(T) P P = S(T) P²

Y en t+3, el sistema se expresará por S(T+2) = S(T) P P P = S(T) P³


Y así sucesivamente.

Si las probabilidades de estado no cambian de periodo a periodo, el sistema se encuentra en estado estable. No todo sistema tiene un estado estable.


Si el sistema alcanza el estado estable, las probabilidades de estado estable, digamos S, tendrán las propiedades siguientes:

S = S P (1)La ecuación (1) representa un conjunto de

n ecuaciones simultáneas con n variables de probabilidad de estado.


Para obtener las probabilidades de estado estable, reemplace cualquiera de las ecuaciones en (1) con Ʃs(i)= 1 y resuelva las n nuevas ecuaciones simultáneas.


Analizando un ejemplo

Ingresemos un sistema representado por 4 estados:


La plantilla vacía representa una matriz con las relaciones entre los estados (State), sus probabilidades iniciales (Initial Prob.) y el costo de cada uno de ellos (State Cost).


En el menú Resolver y analizar (Solve and Analyze) tenemos las opciones de Resolver los estados completos (Solve Steady State) o mostrar el Proceso de Markov por pasos (Markov Process Step)


La primera opción da como resultado la siguiente tabla:


Resolviendo el ejercicio paso a pasoRegresando a la matriz inicial y tomando

la segunda opción del menú Resolver y analizar (Solve and Analyze) tenemos una ventana que nos permite controlar las iteraciones del proceso:



Podemos observar el Número de periodos procesados (The Number of Time Periods from Initial).

Pulsemos en el botón NEXT PERIOD y luego en el botón OK:


Para el periodo dos (recuerde pulsar en NEXT PERIOD seguido del botón OK):


En la columna Probabilidad del estado resultante (Resulted State Probability) se muestran las probabilidades para los periodos. Pulsando es el botón STEADY STATE alcanzamos la matriz estable:


Documents

Investigación de Operaciones II UNIDAD 4. Cadenas de Markov