Distribución Estacionaria de una Cadena de Markov en Tiempo Continuo

En la Teoría de Probabilidades, una Cadena de Markov en Tiempo Continuo (CTMCContinuous Time Markov Chain) corresponde a un modelo matemático donde una variable aleatoria toma valores en un espacio finito y donde el tiempo en que la variable se encuentra en un determinado estado adopta valores reales no negativos que siguen una Distribución Exponencial. Dicha característica denominada Propiedad de No Memoria determina que el comportamiento a futuro del proceso estocástico depende sólo del estado actual y no del comportamiento histórico de dicha variable.

En este contexto a continuación presentamos un ejemplo del cálculo de una Distribución Estacionaria o de Largo Plazo para una Cadena de Markov en Tiempo Continuo. Nuestro objeto de análisis en términos intuitivos es similar al caso de la Distribución Limite de una Cadena de Markov en Tiempo Discreto, es decir, estimar en el largo plazo (e independiente de la distribución inicial) cuál es la probabilidad que el proceso estocástico se encuentre en uno de los N estados posibles.

Distribución Estacionaria Cadena de Markov en Tiempo Continuo

Aves arriban a uno de los 4 alimentadores (comederos) ubicados en el patio de una casa de acuerdo a un Proceso de Poisson con tasa promedio de un ave por minuto. Si todos los alimentadores (4 en total) están ocupados, el ave se va sin esperar que un alimentador se desocupe y en caso contrario el ave come de un alimentador por un tiempo determinado que sigue una Distribución Exponencial con media de un minuto. Se desea modelar la cantidad de alimentadores o comederos ocupados X(t) a través de una Cadena de Markov en Tiempo Continuo.

Sea X(t) la variable aleatoria que representa el número de alimentadores ocupados. En este contexto X(t) representa el número de entidades presentes en los alimentadores en el instante t, cuyo tamaño aumenta con la llegada (nacimiento) de entidades (aves) o disminuye con la salida (muerte) de entidades (aves).

Al existir 4 alimentadores, la cantidad de éstos que se pueden encontrar ocupados en un instante del tiempo son 0, 1, 2, 3 o 4, (X(t)\in\begin{Bmatrix}0,1,2,3,4\end{Bmatrix}t\geq 0) según se representa en el diagrama de transición a continuación:

proceso nacimiento y muerte ctmc

Los valores en las flechas que unen los estados 0 con el 1, 1 con el 2, 2 con el 3 y 3 con el 4, corresponden a la tasa de llegada λ (tasas de nacimiento) que en este caso corresponde a \lambda_{i}=1[\frac{ave}{minuto}] para todo i.

Por otro lado las tasas de servicio (salida o muerte) µ corresponderán a \mu_{i}=i\mu, de modo que de esta forma se obtienen las tasas indicadas en la parte inferior del diagrama en aquella transiciones que consisten en disminuir el número de alimentadores ocupados. Notar que en este caso \mu=1[\frac{ave}{minuto}] .

La cadena propuesta es claramente irreducible (es decir, todos los estados se comunican entre sí y existe por tanto una única clase de estados), de modo que podemos estimar una distribución estacionaria o de largo plazo. En este sentido la ecuación correspondiente es:

ecuaciones largo plazo ctmc

Donde por cierto \sum\pi _{i}=1. La Matriz General G, que tiene como característica que la sumatoria de los valores en sus respectivas filas corresponde a cero, a su vez queda definida por:

matriz g ctmc

De este modo se obtiene el siguiente sistema de ecuaciones:

sistema ecuaciones largo plazo ctmc

La solución del sistema corresponde a:

soluciones ecuaciones ctmc

Que representa para cada estado la proporción del tiempo (en el largo plazo) que cada uno de ellos se encontrará ocupado, por ejemplo, se espera que en el 36,92% del tiempo no se encuentren alimentadores (comederos) ocupados.

Los resultados anteriores han sido corroborados haciendo uso de una planilla de Simulación de Sistemas de Espera disponible en el Libro Investigación de Operaciones de H. Taha. Notar que se ha establecido un límite de 4 entidades (en este caso aves) para el sistema:

simulación ctmc

El número de alimentadores ocupados en el largo plazo son:

alimentadores ocupados largo plazo

Se concluye que en el largo plazo se encuentren ocupados 0,9845 comederos. Cabe destacar que según el resultado de la simulación anterior L_{s}=0,98462 y por cierto la diferencia respecto a nuestro resultado obedece exclusivamente a la cantidad de decimales utilizados para la estimación.

Comparación de un Servicio General y Específico para la Atención de Clientes (Teoría de Colas)

En los sistemas de atención de público se suelen encontrar distintos esquemas o configuraciones en las que se organiza la espera de los clientes antes de ser atendidos. Se pueden observar casos donde los clientes se ordenan en una fila para ser atendidos por un servidor, otros donde los clientes se ordenan en una fila común y luego son atendidos por un servidor en la medida que este disponible (esquema frecuente en las cajas rápidas en los supermercados). En este contexto el siguiente artículo evaluaremos un sistema de atención general y uno específico, comparando desde un punto de vista cuantitativo el desempeño de cada caso a través de la simulación del comportamiento de la Línea de Espera.

Un banco pequeño en un centro comercial tiene dos cajeros. Uno maneja al público general y uno maneja a los clientes regulares. Cada tipo de clientes llega con una media de 20 por hora (para una proporción de la llegada total de 40 clientes por hora). El tiempo de servicio para ambos cajeros promedia 2 minutos (sigue una distribución exponencial, es decir, se verifica el cumplimiento de la Propiedad de Falta de Memoria o Amnesia de la Distribución Exponencial). El gerente del banco está considerando cambiar el orden de atención para permitir que cada cajero pueda manejar ambos tipos de clientes. Debido a que los cajeros tendrían que manejar ambos tipos de trabajos, sus eficiencias disminuirían a un tiempo de servicio de 2,2 minutos por cliente. ¿Se debe cambiar al nuevo esquema de atención?.

Servicio General y Específico para la Atención de Clientes

El servicio específico implica que cada cajero atiende de forma exclusiva un tipo de clientes sin existir colaboración entre los mismos. Una representación esquemática de dicho escenario se muestra a continuación:

servicio-especifico-teoria-

En el artículo Simulación de una Línea de Espera M/M/1 (Teoría de Colas) en Excel se detalla el procedimiento para obtener los indicadores de desempeño de una línea de espera con un servidor, donde el tiempo entre llegadas de los clientes se distribuye exponencial, al igual que los tiempos de servicios. En el ejemplo la atención para cada tipo de clientes muestra los siguientes resultados:

servicio-general-mm1

El número esperado de clientes en el sistema Ls es de 2 clientes (en este caso la fila y atención para cada tipo de cliente constituye un sistema), el número esperado de clientes en la fila Lq es de 1,333, el tiempo promedio que un cliente esta en el sistema Ws es 0,1 horas, es decir, 6 minutos. Finalmente el tiempo que un cliente esta en la fila Wq es de 0,06667 horas (4 minutos).

En el caso de un servicio general, en donde existe colaboración entre los servidores, la capacidad de cada uno de ellos baja a µ=60/2,2[clientes/hora].

servidor-general-teoria-de-

Los indicadores de desempeño son: Ls=3,17307 (considerando los 2 tipos de clientes, es decir, en promedio se espera tener menos clientes en el sistema que el caso del servicio específico donde en total se esperan, en promedio, 4 clientes en el sistema); el tiempo promedio que un cliente esta en el sistema Ws es 0,07933 horas (aprox 4,76 minutos); el número esperado de clientes en la fila Lq es de 1,7064 y el tiempo que en promedio un cliente esta en la fila Wq es de 0,04266 horas (2,56 minutos).

mm1-servicio-general

Se concluye que si bien en nuestro ejemplo la capacidad de cada uno de los servidores baja al atender los 2 tipos de clientes, esto se ve compensado por el efecto de colaboración que se genera entre los mismos, lo que permite bajar el tiempo que en promedio un cliente esta en el sistema y en la fila. Estos aspectos claramente son valorados desde la perspectiva de los clientes y deberían ser tomados en cuenta al momento de decidir si se cambia el esquema original de atención de clientes.

¿Quieres tener el archivo Excel con la planilla de Simulación de una Línea de Espera utilizada en este ejemplo?

[sociallocker]

MUCHAS GRACIAS!. DESCARGA AQUÍ EL ARCHIVO

[/sociallocker]

Simulación de una Línea de Espera M/M/1 (Teoría de Colas) en Excel

Un sistema de espera M/M/1 es aquel que considera un servidor, con tiempos exponenciales de servicio y entre llegadas de clientes. La implicancia que los tiempos de servicio se distribuyan exponencial es que existe una preponderancia de tiempos de servicio menores al promedio combinados con algunos pocos tiempos extensos. Un ejemplo de ello es lo que sucede en las cajas de los bancos donde la mayoría de las transacciones requieren poco tiempo de proceso por parte del cajero, no obstante algunas transacciones más complejas consumen bastante tiempo. Por otra parte afirmar que los tiempos entre llegadas se distribuyen exponencial implica una preponderancia de tiempos entre llegadas menores que el promedio en combinación con algunos tiempos más extensos. Lo anterior tiene relación con la aleatoriedad del proceso de llegada de clientes que permite establecer la Propiedad de Falta de Memoria o Amnesia de la Distribución Exponencial y con los conceptos presentados en el artículo Qué son las Líneas de Espera (Teoría de Colas), donde queda en evidencia que la formación de las colas o filas esta asociada a la variabilidad del sistema.

En este contexto consideremos la siguiente notación, donde valores usuales para A y B son M (distribución exponencial) y G (distribución general).

notacion-de-kendall

El siguiente ejemplo disponible en el artículo Qué es la Ley de Little y su aplicación en el análisis de Líneas de Espera, nos permitirá ilustrar la simulación en Excel del comportamiento de un sistema de espera M/M/1.

Simulación de una Línea de Espera M/M/1

Ejemplo: Un pequeño banco está considerando abrir un servicio para que los clientes paguen desde su automóvil. Se estima que los clientes llegarán a una tasa promedio de 15 por hora (λ=15). El cajero que trabajará en la ventanilla puede atender a los clientes a un ritmo promedio de uno cada tres minutos (es decir, la capacidad promedio del servidor es de µ=20). Suponga que el patrón de llegadas es Poisson y el patrón de servicios es Exponencial.

Al hacer uso de la Planilla de Fórmulas de Sistema de Espera, se alcanzan los resultados que se resumen en la imagen a continuación.

salida-planilla-linea-de-es

Con esto la utilización promedio del servidor es de un 75%, el número esperado de clientes en el sistema Ls es 3, el número esperado de clientes en la fila Lq son 2,5, el tiempo promedio que un cliente permanece en el sistema Ws (espera más atención) son 0,2 horas (0 12 minutos) y el tiempo promedio que un cliente permanece en la fila Wq (esperando su atención) es de 0,15 horas (o 9 minutos).

Otra alternativa es simular el comportamiento de la línea de espera con configuración M/M/1 haciendo uso de Excel. Para ello ingresamos en la planilla Queueing_Simulator el número de servidores (1), la distribución para el tiempo entre llegadas (exponencial con media de 4 minutos, esto es, si llegan en promedio 15 clientes por hora, entonces en promedio llega un cliente cada 1/15 de hora o equivalentemente cada 4 minutos) y una distribución para el tiempo de servicio también exponencial con media de 3 minutos. Finalmente ingresamos el número de llegadas que se desea simular (arbitrariamente se ha seleccionado 100.000 llegadas para evaluar un comportamiento del sistema en el largo plazo) y luego Run Simulation.

simulacion-mm1-excel

Se puede apreciar que los resultados obtenidos en la columna F son (aproximadamente) similares a los obtenidos utilizando los resultados que establece la Ley de Little. Por ejemplo, el número esperado de clientes en el sistema L es 3,0157; el número esperado de clientes en la fila Lq es 2,2665; el tiempo esperado que un cliente permanece en el sistema W son 12,0612 minutos y así sucesivamente.

Importante: Los resultados mostrados anteriormente corresponden a aquellos obtenidos con una simulación tipo. Si una vez alcanzados los resultados presionamos nuevamente Run Simulation obtendremos cambios en los resultados los cuales de todos modos deberían aproximar los resultados de la Ley de Little bajo el supuesto de considerar un número significativo de llegadas a simular.

¿Quieres tener el archivo Excel con la Simulación de una Línea de Espera M/M/1 utilizada en este ejemplo?

[sociallocker]

MUCHAS GRACIAS!. DESCARGA AQUÍ EL ARCHIVO

[/sociallocker]

Qué son las Líneas de Espera (Teoría de Colas)

En el artículo Qué es la Ley de Little y su aplicación en el análisis de Líneas de Espera describimos algunos elementos básicos asociados al estudio de líneas de espera como la población de referencia (finita o infinita), distribución de los tiempos entre llegadas (usualmente se distribuyen de forma exponencial, satisfaciendo la Propiedad de Falta de Memoria o Amnesia de la Distribución Exponencial), disciplina del servicio (FIFO, Prioridad, etc), entre otros elementos. A continuación buscaremos ahondar en dichos fundamentos buscando responder ¿Qué son las Líneas de Espera?.

En dicho contexto considere la siguiente pregunta: Un pequeño almacén tiene un solo vendedor que atiende en promedio a 12 clientes por hora (es decir su capacidad es µ=12[/c/h]), atendiendo de un cliente a la vez. La llegada de los clientes al almacén es a una tasa promedio de 10 clientes por hora (λ=10[/c/h]). ¿Hay filas en el almacen? (clientes esperando por su atención). Probablemente muchas personas respondan que no, pero la respuesta correcta es: depende.

linea-de-espera-llegada

Un ejemplo que permite evidenciar lo anterior es el siguiente. Un proceso como el que se describió en la pregunta anterior (almacén) que recibe 12 clientes por hora (λ). La columna Arrival Time detalla el minuto en el cual el cliente llega al almacén (asumamos que estamos evaluando desde las 07:00 a las 08:00, es decir, el primer cliente llega a las 07:00, el segundo a las 07:07 y así sucesivamente). Finalmente la columna Service Time detalla el tiempo que el vendedor se demora en atender al cliente (al calcular el promedio de los valores de dicha columna se observa que es 4,083 minutos, es decir, µ=14,69[/c/h] aproximadamente). Luego la utilización promedio del servidor (vendedor) es ρ=λ/µ=0,8167< 1. Los detalles de este procedimiento se puede consultar en el artículo Cómo calcular la Utilización de un servidor, Tiempo de Espera y Tiempo de Flujo de una Línea de Espera.

llegada-de-clientes

No obstante si analizamos en detalle del proceso de espera anterior podemos observar lo siguiente:

grafico-clientes-en-el-sist

Los clientes 3, 4, 5, 6, 7, 8 y 9 debieron esperar antes de ser atendidos por el vendedor aun cuando la utilización (promedio) del mismo es menor a 1. En el gráfico de barras adicionalmente se observa la cantidad de clientes en el sistema para un instante del tiempo dado (esto considerando tanto el cliente que eventualmente pueda estar siendo atendido más los que eventualmente están esperando por su atención). Por ejemplo a las 07:31 se esta atendiendo al cliente 5 y están esperando en fila los clientes 6, 7 y 8 (es decir, hay 4 clientes en el sistema). Luego la conclusión que podemos generalizar en este caso es:

Si existe variabilidad en las llegadas de los clientes al sistema y/o en las atenciones (tiempos de servicio), entonces hay colas o filas (aunque de largo finito). Esto a pesar de que λ<µ, o sea, de que ρ< 1. Si λ>µ el sistema es inestable (se generan colas infinitas).Dicho de otra modo la existencia de colas o filas en un sistema se deben a la variabilidad y no al hecho de que λ>µ (ρ> 1).

Cálculo de la Probabilidad de un Número de Llegadas en un Tiempo Determinado utilizando la Distribución de Poisson

Cuando los clientes llegan a un servicio de forma totalmente aleatoria (es decir, no hay forma de pronosticar cuándo va a llegar alguien) la función de densidad de probabilidad para describir la cantidad de llegadas durante un tiempo determinado se representa por la Distribución de Poisson y automáticamente la distribución del tiempo entre llegadas sigue una Distribución Exponencial según lo expuesto en el artículo Propiedad de Falta de Memoria o Amnesia de la Distribución Exponencial.

En este contexto la fórmula que permite calcular la probabilidad exacta de n llegadas dentro de un período T es la siguiente:

probabilidad-poisson

Consideremos por ejemplo un taller que se dedica a labores de reparación y que la llegada de éstos diariamente se comporta de forma aleatoria con una tasa de 10 trabajos diarios. ¿Cuál es la probabilidad de que no lleguen trabajos durante una hora cualquiera bajo el supuesto que el taller opera 8 horas al día?.

probabilida-cero-llegadas-p

Notar que \lambda =\frac{10}{8}=1,25[\frac{trabajos}{hora}]. Es decir, la probabilidad de no recibir trabajos durante una hora cualquiera es aproximadamente a un 28,65%.

Asumamos ahora una nueva situación. Un proceso que tiene una tasa promedio de llegada de 6 clientes por hora (\lambda =6[clientes/hora]) y se desea evaluar cuál es la probabilidad de que lleguen exactamente 0, 1, 2,…,n clientes en un intervalo de tiempo de 0,5 horas (30 minutos). El siguiente vídeo proporciona una simulación de dicho escenario:

En el gráfico, el área amarilla, por ejemplo, significa exactamente la probabilidad que 3 personas lleguen en las 0,5 horas. El área amarilla más el área roja, por ejemplo, significa la probabilidad de que lleguen 2 o 3 personas en los 30 minutos.

Adicionalmente haciendo uso del software Geogebra y su herramienta cálculos de probabilidad, se puede representar la Distribución de Poisson para los parámetros descritos anteriormente de forma de obtener rápidamente los resultados para distintos números de llegadas (notar que la Distribución de Poisson es discreta).

distribucion-poisson-geogeb