1

Unidad No. 3 Análisis de Markov y Teorías de colas

Trabajo de investigación

Introducción

Dentro de esta investigación se planteó el objetivo de definir cada uno de los conceptos

que integran el análisis de Markov, comenzando desde los más básicos hasta los más

complejos, al igual el por qué es llamado así a dicho estudio, dándole este nombre por su

autor (Markov) en este documento se plasma acerca de su biografía, así como todos sus

logros que ejecutó.

Otro tema de suma importancia que hacemos mención, son las cadenas de Markov, que

hacen referencia a una herramienta para analizar el comportamiento y el gobierno de

determinados tipos de procesos estocásticos, esto es, procesos que evolucionan de forma

no determinística a lo largo del tiempo en torno a un conjunto de estados.

Una cadena de Márkov, por tanto, representa un sistema que varía un estado a lo largo

del tiempo, siendo cada cambio una transición del sistema.

Para tales cadenas, se hace el uso de diversos términos involucrados para un mejor

entendimiento, como son: Los estados son la caracterización de la situación en que se halla

el sistema en un instante dado, matriz de transición: Que es el arreglo numérico donde se

condensa las probabilidades de un estado a otro. La matriz regular: es una matriz cuadrada

que posee inversa. Estado recurrente: Un estado es recurrente si después de haber entrado a

este estado, el proceso definitivamente regresa a ese estado, Matriz ergódica: Si los estados

en una
cadena son recurrentes, aperiódicos y se comunican entre si. Estados absorbentes: Una

cadena de Márkov en la que uno o más estados es un estado absorbente, es una cadena de

Márkov absorbente.

Hay muchos modelos en la teor´ıa de colas. Los modelos son explicados como procesos

de nacimiento y muerte, donde el nacimiento es la entrada de un cliente al sistema y muerte

la salida del cliente. Para poder entender estos modelos previamente debemos de clasificar

el sistema de cola según su estructura: Fuente de entrada, disciplina de la cola y mecanismo

de servicio. Además las colas tienen unos parámetros que nos permite calcular el número

de clientes en el sistema, el tiempo de espera en el sistema, entre otros, que es el objetivo

de este estudio.
Índice

Introducción....................................................................................................................... 1
Índice.................................................................................................................................. 3
3.1 Conceptos principales................................................................................................4
3.2 Matriz de transición y sus aplicaciones en administración.....................................7
3.3 Condición de equilibrio.............................................................................................10
3.4 Estados absorbentes................................................................................................11
3.5 Modelos de líneas de espera....................................................................................12
3.6 Distribución de llegada de Poisson y Distribución de servicio exponencial con
un servidor, servicio PEPS, población y cola infinita...................................................17
3.7 Distribución de llegada de Poisson y Distribución de servicio exponencial con
varios servidores, servicio PEPS, población y cola infinita.........................................22
Conclusión....................................................................................................................... 24
Referencias bibliográficas..............................................................................................25
3.1 Conceptos principales

El análisis de Markov, llamado así por los estudios realizados por el ruso Andréi

Andréyevich Márkov entre 1906 y 1907, sobre la secuencia de los experimentos

conectados en cadena y la necesidad de descubrir matemáticamente los fenómenos físicos.

La teoría de Markov se desarrolló en las décadas de 1930 y 1940 por A.N.Kolmagoron,

W.Feller, W.Doeblin, P.Levy, J.L.Doob y otros.

El análisis de Markov es una forma de analizar el movimiento actual de alguna

variable, a fin de pronosticar el movimiento futuro de la misma. Este método ha

comenzado a usarse en los últimos años como instrumento de investigaciones de

mercadotecnia, para examinar y pronosticar el comportamiento de los clientes desde el

punto de vista de su lealtad a una marca y de sus formas de cambio a otras marcas, la

aplicación de esta técnica, ya no solo se limita a la mercadotecnia, sino que su campo de

acción se ha podido aplicar en diversos campos.

Las cadenas de Márkov son una herramienta para analizar el comportamiento y el

gobierno de determinados tipos de procesos estocásticos, esto es, procesos que evolucionan

de forma no determinística a lo largo del tiempo en torno a un conjunto de estados.

Una cadena de Márkov, por tanto, representa un sistema que varía un estado a lo largo

del tiempo, siendo cada cambio una transición del sistema. Dichos cambios no están

predeterminados, aunque sí lo está la probabilidad del próximo estado en función de los

estados anteriores, probabilidad que es constante a lo largo del tiempo (sistema homogéneo

en el tiempo). Eventualmente, es una

transición, el nuevo estado puede ser el mismo que el anterior y es posible que exista la

posibilidad de influir en las probabilidades de transición actuando adecuadamente sobre el

sistema (decisión).

Para el estudio de las cadenas de Márkov, deben tenerse en cuenta algunos conceptos

claves como los siguientes:

 Estados

El estado de un sistema en un instante t es una variable cuyos valores solo pueden

pertenecer al conjunto de estaos en el sistema. El sistema modelizado por la cadena, por lo

tanto, es una variable que cambia con el valor del tiempo, cambio al que llamamos

transición.

 Matriz de transición

Los elementos de matriz representan la probabilidad de que el estado próximo sea el

correspondiente a la columna si el estado actual es el correspondiente a la fila.

Posee 3 propiedades básicas:

a) La suma de las probabilidades de los estados debe ser igual a 1.

b) La matriz de transición debe ser cuadrada.

c) Las probabilidades de transición deben estar entre 0 y 1.

  Distribución actual (Vector Po)

Es la manera en la que se distribuyen las probabilidades de los estados en un periodo

inicial, (periodo 0). Esta información te permitirá averiguar cuál será la distribución en

periodos posteriores.

 Estado estable

Se puede decir que el estado estable es la distribución de probabilidades que en cierto

punto quedará fija para el vector P y no presentará cambios en periodos posteriores.

 Bloqueo

Estado de un sistema donde todos los servidores están ocupados.

 Canal de servicio

Sistema que sirve a las unidades o clientes.

 Cliente

Unidad que llega al sistema para realizar algún servicio.

 Cola

Número de clientes que esperan ser atendidos.

 Disciplina de generación

Estadística de los tiempos de llegada de las unidades de datos.

  Disciplina de servicio

Estadística del tiempo que se tarda en servir las unidades en un sistema de colas.

 Red de cola

Sistema formado por un conjunto de colas interconectadas.

 Red abierta

Red de colas con entrada y salida de unidades al sistema.

 Red cerrada

Red de colas sin entrada ni salida de unidades. El número de unidades se mantiene

constante.

 Tasa de llegada

Velocidad media de llegadas al sistema.

 Tasa de servicio

Velocidad media del servicio de las unidades en el sistema.

 Tasa de transición

Velocidad o probabilidad de transición de un estado a otro.

3.2 Matriz de transición y sus aplicaciones en administración

Muchos son los defensores de que en el proceso de toma de decisiones en la

administración se debe tener en cuenta tanto los factores objetivos como

subjetivos entorno a ella. Un gran número de administradores toman partida en utilizar

métodos objetivos, o llamados también cuantitativos, los que con un fuerte basamento

matemático formal, modelan la situación en la cual hay que decidir por una alternativa,

planificar, asignar, y realizar toda una serie de actividades que pueden comprometer en un

momento determinado la organización. Por otro lado, están quienes defienden los métodos

subjetivos, también llamados cualitativos, pues alegan que el entorno convulso que vive

una organización hace de la administración una actividad sujeta a las condiciones del medio

que le rodea y de los individuos implicados.

La administración moderna requiere el apoyo de herramientas de diferentes ramas de la

ciencia que ayuden al proceso de toma de decisiones, como por ejemplo la Matemática

Aplicada. En este contexto aparecen variables aleatorias que con el transcurso del tiempo

cambian, y que pueden ser representadas a través de modelos cuantitativos. Cuando en

estos modelos el estado presente de dichas variables resume toda la información anterior

para describir cómo se comportarán en el futuro, se dice que se está en presencia de una

cadena de Markov; una herramienta eficiente para el análisis de procesos de esta

naturaleza, como por ejemplo la ejecución de proyectos de investigación, el cual reviste

gran importancia en la gestión de ciencia e innovación tecnológica.

Dentro de los métodos cuantitativos para la toma de decisiones, el enfoque estocástico

propone el estudio de una variable aleatoria que evoluciona en el tiempo. Un proceso

estocástico es llamado específicamente una Cadena de Markov –que debe su nombre al

matemático ruso Andrei Andreevitch Markov–,

cuando en este modelo aparece una sucesión de variables aleatorias tal que el "siguiente"

estado del proceso es independiente de los estados anteriores, siempre que sea conocido el

estado presente. Estas variables aleatorias, que constituyen los denominados "estados de

transición", aparecen con bastante definición y regularidad en el área de la administración.

Tipos de matrices de transición

Tipo de matriz Descripción

Matriz estocástica derecha Matriz cuadrada donde cada una de cuyas

filas está formada por números reales no

negativos, sumando cada fila

1.

Matriz estocástica izquierda Matriz cuadrada cada una de cuyas

columnas se encuentra formada por

números reales no negativos, sumando

cada una 1.

Matriz doble estocástica Matriz cuadrada donde todos los

valores son no negativos y todas las

filas y columnas suman 1.

Aplicaciones de la matriz de transición

 Teoría de la probabilidad: rama de las matemáticas que estudia los

fenómenos aleatorios y estocásticos

  Fenómenos aleatorios: aquellos que se obtienen de experimentos

realizados, bajo las mismas condiciones determinadas, pero como

resultado posible poseen un conjunto de alternativas.

3.3 Condición de equilibrio

Algunas cadenas de Markov cumplen la llamada condición de equilibrio

minucioso.

La comprensión detallada de la condición de equilibrio es muy importante. la

ecuación de balance detallado de la condición, que establece que para

la probabilidad de transición de q y distribución estacionaria π, una Cadena de Markov

satisface balance detallado si:

esto tiene más sentido como:

Básicamente, la probabilidad de transición de estado x, estado y; debe ser

proporcional a la razón de las densidades de probabilidad.

A la ecuación se llama ecuación de balance detallado. La utilidad de las cadenas

reversibles está dada por el siguiente resultado.

Como condición de equilibrio, tenemos el balance detallado, sin embargo, también

tendremos otra noción de Equilibrio.

 El equilibrio termodinámico se caracteriza por tener un valor mínimo en sus potenciales

termodinámicos, es decir, variables de estado que tienen dimensiones de energía, tales como

la energía libre de Gibbs, son sistemas caracterizados por tener la presión y temperatura

constantes. Un estado de equilibrio en un sistema lattice finito es aquel que minimiza la

energía libre de Gibbs, lo cual se llama equilibrio termodinámico.

3.4 Estados absorbentes

Se dice que un estado es absorbente si es cero la probabilidad de hacer una transición

fuera de ese estado. Por tanto, una vez que el sistema hace transición hacia un estado

absorbente, pertenece en el siempre.

Un estado es absorbente si:

en la i-ésima fila de T.

La descripción de los procesos o sistemas que cesan (o por lo menos vuelven a

comenzar) después de alcanzar determinadas condiciones se utiliza un caso especial de

cadenas de Márkov. Por ejemplo, después de hallar un numero predeterminado de partes

aceptables o defectuosas, se suspende una inspección secuencial; después de x horas de

funcionamiento se detiene una máquina

para repararla o remplazarla, etc. Tales procesos pueden modelarse como una cadena

de Márkov absorbente.
 Una cadena de Márkov con espacio de estados finito se dice absorbente si se cumplen las

dos condiciones siguientes:

a) La cadena tiene al menos un estado absorbente.

b) 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,

I = una matriz de identidad que indica que uno siempre permanece en estado de

absorción una vez que se alcanza.

0 = Matriz cero que representa 0 probabilidad de Transición de los estados absorbentes a

la Estados no absorbentes.

A = Las probabilidades de transición de los estados no absorbentes a los estados

absorbentes.

N = Las probabilidades de transición entre los estados no absorbentes.

3.5 Modelos de líneas de espera

Se conoce como línea de espera a una hilera formada por uno o varios clientes que

aguardan para recibir un servicio. Los clientes pueden ser personas, objetos,
máquinas que requieren mantenimiento, contenedores con mercancías en espera de ser

embarcados o elementos de inventario a punto de ser utilizados. Las líneas de espera se

forman a causa de un desequilibrio temporal ente la demanda de un servicio y la capacidad

del sistema para suministrarlo.

Junto a los árboles de decisiones, con frecuencia los modelos de líneas de espera son

útiles para la planificación de la capacidad. Frente a ciertos centros de trabajo, como el

mostrador de pasajes de un aeropuerto, un centro de máquinas o un centro de cómputos

central, tienden a formarse líneas de espera. Es así porque los tiempos de llegada entre dos

trabajos o clientes sucesivos varían y el tiempo de procesamiento también varía de un

consumidor al siguiente.

Los modelos de líneas de espera usan distribuciones de probabilidad para ofrecer

estimaciones del tiempo de retraso promedio de los clientes, la longitud promedio de las

filas de espera y la utilización del centro de trabajo.

Los gerentes suelen usar esta información para elegir la capacidad más efectiva en

términos de costos, hallando un equilibrio entre el servicio al cliente y el costo de la

capacidad agregada.

En la mayoría de los problemas de líneas de espera que se presentan en la vida real, la

tasa de demanda varía; es decir, los clientes llegan a intervalos imprevisibles. Lo más

común es que también haya variaciones en el ritmo de producción del servicio,

dependiendo de las necesidades del cliente.

Los administradores de operaciones reconocen el trueque que se lleva a cabo entre el

costo de ofrecer un buen servicio y el costo del tiempo de espera del

cliente o la máquina. Los administradores desean que las filas de espera sean lo

suficientemente cortas, de tal forma que los clientes no se sientan descontentos y se vayan

sin comprar, o que compren pero nunca regresen. Sin embargo, los administradores están

dispuestos a permitir alguna espera, si ésta es proporcional a un ahorro significativo en los

costos del servicio. Cuando la empresa intenta elevar su nivel de servicio, se observa un

incremento en los costos.

La teoría de las líneas de espera es aplicable a empresas de servicios o manufactureras,

porque relaciona la llegada de los clientes y las características de procesamiento del

sistema de servicios con las características de salida de dicho sistema. El sistema de

servicio puede consistir en la operación de cortar el cabello en una peluquería, o bien, en el

departamento de partes, con una máquina determinada para atender un pedido de

producción. Otros ejemplos de clientes y servicios son las filas de los espectadores que

esperan frente a un estadio de fútbol para comprar entradas, los camiones que aguardan

para ser descargados en una planta de acopio de cereales, las máquinas en espera de ser

reparadas por una cuadrilla de mantenimiento y los pacientes que hacen antesala para ser

atendidos por un médico. Cualquiera que sea la situación, los problemas referentes a líneas

de espera tienen algunos elementos en común.

El análisis de los problemas de líneas de espera comienza con una descripción de los

elementos básicos de la situación. Cada situación específica tendrá características

diferentes, pero cuatro elementos son comunes a todas ellas:

a) Un insumo, o población de clientes, que genera clientes potenciales.

b) Una línea o fila de espera formada por los clientes.

 c) La instalación de servicio, constituida por una persona (o una cuadrilla), una

máquina (o grupo de máquinas) o ambas cosas si así se requiere para proveer el

servicio que el cliente solicita.

d) Una regla de prioridad para seleccionar al siguiente cliente que será

atendido por la instalación de servicio.

Imagen 01. Elementos básicos de los modelos de líneas de espera

El sistema de servicio suele describirse en términos del número de filas y

la disposición de las instalaciones.

Número de filas. Las filas de espera se diseñan en forma de una sola fila o filas

múltiples. En general, se utiliza una sola fila en mostradores de aerolíneas, cajas de los

bancos y algunos restaurantes de comida rápida, mientras que las filas múltiples son

comunes en los supermercados y espectáculos públicos como teatros o canchas de fútbol.

Cuando se dispone de servidores múltiples y cada uno de ellos puede manejar

transacciones de tipo general, la disposición de una sola fila mantiene a todos ellos

uniformemente ocupados y proyecta en los clientes una sensación de que la situación es

equitativa. Estos piensan que serán

atendidos de acuerdo con su orden de llegada, no por el grado en que hayan podido

adivinar los diferentes tiempos de espera al formarse en una fila en particular. El diseño de

filas múltiples es preferible cuando algunos de los servidores proveen un conjunto de

servicios limitado. En esta disposición, los clientes eligen los servicios que necesitan y

esperan en la fila donde se suministra dicho servicio, como sucede en los supermercados es

las que hay filas especiales para los clientes que pagan en efectivo o para los que compran

menos de 10 artículos.

Algunas veces, los elementos que esperan su turno no están organizados nítidamente en

filas. Las máquinas que necesitan ser reparadas en el taller de producción de una fábrica

pueden permanecer en sus respectivos sitios y el equipo de mantenimiento es el que tiene

que acudir a cada lugar. A pesar de todo, podemos considerar que esas máquinas forman

una sola fila o filas múltiples, según el número de cuadrillas de reparación y sus

respectivas especialidades.

Asimismo, los usuarios que llaman por teléfono para pedir un taxi también forman una fila,

aunque cada uno se encuentre en un lugar diferente.

Imagen 02. Diversas disposiciones de filas de espera

 Disposición de instalaciones de servicio. Las instalaciones de servicio consisten en el

personal y/o el equipo necesario para proporcionar dicho servicio al cliente. Los gerentes

deben elegir una disposición adecuada según el volumen de sus clientes y el carácter de los

servicios ofrecidos. Algunos servicios requieren un solo paso, también conocido como

fase, en tanto que otros requieren una secuencia de pasos.

Imagen 03. Ejemplos de disposiciones para instalaciones de servicio

3.6 Distribución de llegada de Poisson y Distribución de servicio

exponencial con un servidor, servicio PEPS, población y cola infinita

Los gerentes de operaciones suelen utilizar modelos de filas de espera para establecer el

equilibrio entre las ventajas que podrían obtener incrementando la eficiencia del sistema de

servicio y los costos que esto implica. Además, los gerentes deberían considerar los costos

por no hacer mejoras al sistema: las largas filas de espera o los prolongados tiempos de

espera resultantes de esto provocan que los clientes se arrepientan o deserten. Por lo tanto,

es preciso que
los gerentes estén interesados en las siguientes características de operación del sistema:

 Longitud de la fila. El número de clientes que forman una fila de espera refleja

alguna de estas dos condiciones: las hileras cortas significan que el servicio al

cliente es bueno o que la capacidad es excesiva, y las hileras largas indican una

baja eficiencia del servidor o la necesidad de aumentar la capacidad.

 Número de clientes en el sistema. El número de clientes que conforman la fila y

reciben servicio también se relaciona con la eficiencia y la capacidad de dicho

servicio. Un gran número de clientes en el sistema provoca congestionamientos y

puede dar lugar a la insatisfacción del cliente, a menos que el servicio incremente

su capacidad.

 Tiempo de espera en la fila. Las filas largas no siempre significan tiempos de

espera prolongados. Si la tasa de servicio es rápida, una fila larga puede ser

atendida eficientemente. Sin embargo, cuando el tiempo de espera parece largo, los

clientes tienen la impresión de que la calidad del servicio es deficiente. Los

gerentes tratan de cambiar la tasa de llegada de los clientes o de diseñar el sistema

para que los largos tiempos de espera parezcan más cortos de lo que realmente son.

 Tiempo total en el sistema. El tiempo total transcurrido desde la entrada al sistema

hasta la salida del mismo ofrece indicios sobre problemas con los clientes,

eficiencia del servidor o capacidad. Si algunos clientes pasan demasiado tiempo en

el sistema del servicio, tal vez sea necesario cambiar

 la disciplina en materia de prioridades, incrementar la productividad o ajustar de

algún modo la capacidad.

 Utilización de las instalaciones de servicio. La utilización colectiva de instalaciones

de servicio refleja el porcentaje de tiempo que éstas permanecen ocupadas. El

objetivo de la gerencia es mantener altos niveles de utilización y rentabilidad, sin

afectar adversamente las demás características de operación.

El mejor método para analizar un problema de filas de espera consiste en relacionar las

cinco características de operación y sus respectivas alternativas con su valor monetario. Sin

embargo, es difícil asignar un valor económico a ciertas características (como el tiempo de

espera de un cliente en un banco). En estos casos, es necesario que un analista compare el

costo necesario para aplicar la alternativa en cuestión, frente a una evaluación subjetiva del

costo que implicaría el hecho de no hacer dicho cambio.

Elementos de un problema de colas, caso de un servidor:

a) Arribos

 Los arribos ingresan al sistema aleatoriamente

 Los arribos vienen de una población infinita

 No se permiten arribos simultáneos

 Los arribos tienen una distribución de Poisson; La población de una llegada

en cualquier instante de tiempo es la misma que en cualquier otro momento.

 b) Cola

 El tamaño de la cola es infinita

 Los arribos no pueden cambiar lugares en la cola

c) Servidor

 El tiempo de servicio es aleatorio

 Puede haber interrupciones en el servicio

 Disciplina de servicio: Primero en arribar, primero en ser servido

 Tiene una distribución exponencial

d) Salida

 No se permite que las unidades que salen vuelvan a ingresar al

sistema.

Según la notación de Kendall:

Consideraciones que se deben conocer para el estudio de sistemas de colas.

¿La estación de servicio puede atender las demandas de los clientes? averiguamos

comparando las tasas de arribo y servicio:

3.7 Distribución de llegada de Poisson y Distribución de servicio

exponencial con varios servidores, servicio PEPS, población y cola infinita

Se puede deducir expresiones semejantes para un problema de cola multicanal siempre y

cuando se suponga una población infinita. Estas ecuaciones son más generales que los

anteriores ellos pueden reducirse al caso de canal simple haciendo K = 1.

Las características de operación de las líneas de espera de canales múltiples puede

aplicarse sólo a situaciones donde kµ > λ La tasa promedio de servicio del sistema con k

servidores es kµ, siendo λ/kg el factor de utilización del sistema.

Según la notación de Kendall:

Conclusión

Para concluir podemos decir que las cadenas de Markov son una herramienta para

analizar el comportamiento y el gobierno de determinados tipos de procesos estocásticos,

esto es, procesos que evolucionan de forma no determinística a lo largo del tiempo en torno a

un conjunto de estados.

Que para su elaboración requieren del conocimiento de diversos elementos como

son el estado y la matriz de transición.

Dichos elementos fueron descubiertos por su creador Markov, el cual realizó una

secuencia de experimentos conectados en cadena y la necesidad de descubrir

matemáticamente los fenómenos físicos

Este método es muy importante, ya que ha comenzado a usarse en los últimos años

como instrumento de investigaciones de mercadotecnia, para examinar y pronosticar el

comportamiento de los clientes desde el punto de vista de su lealtad a una marca y de sus

formas de cambio a otras marcas, la aplicación de esta técnica, ya no solo se limita a la

mercadotecnia sino que su campo de acción se ha podido aplicar en diversos campos.

Esperemos que este artículo sea de gran utilidad y que los conceptos

contenidos queden explicados de manera clara.

Referencias bibliográficas

Pérez, J. (2011, 3 de Junio). Andrei Markov. Recuperado de

http://investigacindeoperaciones.html

Morales, L. (2011, 2 de Junio). Cadenas de Markov. Recuperado de: http://io2-

ingindustrial.blogspot.com/2011/06/cadenas-de-markov.html