Universidad de La SerenaFacultad de IngenieraDepartamento de ingeniera Civil Industrial

APLICACIN DE CADENAS DE MARVOV EN LNEAS DE ESPERA

Nombres: Mauro Faras Corts Carlos Gonzlez Vergara Jos Melndez Artigas Sebastin Valenzuela Portilla

Curso: Teora IIAsignatura: Investigacin de Operaciones IIDocente: Paulina Gonzlez MartnezFecha: 04 de Julio del 2014

NDICE

NDICE2INTRODUCCIN3DESARROLLO4Aplicacin de cadenas de markov a sistemas de antencin4 Un ejemplo numrico.7CADENAS DE MARKOV CON ESTADOS FUZZY12Probabilidad de eventos fuzzy12Un ejemplo numrico14CONCLUSIONES18REFERENCIAS19ANEXO20

INTRODUCCIN

La bsqueda de la optimizacin es una constante necesidad de las empresas, por ejemplo en la minera es algo trascendental porque se busca reducir costos en procesos de produccin y con esto tener una mayor competitividad en comparacin a otras empresas del rubro es por esto que para un ingeniero en minas es esencial conocer a profundidad cmo funcionan los procesos de decisin Markoviano.El desarrollo de este informe presenta como objetivo analizar la relacin entre la teora de colas y proceso de decisin markoviano, como este puede optimizar y generar mayor beneficio o menor costo , as con esto tener un mayor conocimiento como funciona y poder aplicarlo a distintas situaciones de la minera en especial. Un proceso de decisin Markoviano se puede utilizar para detallar un sistema dinmico el cual evoluciona en el tiempo de acuerdo a los efectos simultneos de las leyes probabilsticas de movimiento y la secuencia de decisiones tomadas. El sistema se observa en los instantes de tiempo t = 0,1,2,.. , y es clasificado en uno de los M estados del sistema. Luego de cada observacin se toma una de las K posibles decisiones. Ello implica que cuando el sistema se encuentra en un estado particular y se toma una decisin, el sistema se mueve a un nuevo estado con una probabilidad de transicin conocida y se genera un costo o un beneficio, y esto para cualquier combinacin de estados y decisiones. Una poltica es un conjunto de decisiones tomadas para cada uno de los estados del sistema. En general hay K polticas. El problema es encontrar la mejor poltica de manera que el coste promedio por unidad de tiempo sea mnimo, o que el beneficio sea mximo . Los procesos de decisin Markovianos representan una til herramienta para modelar y encontrar la poltica ptima en una amplia clase de sistemas. Estos son aplicables en reas tales como teora de colas, inventarios, mantenimiento, programacin dinmica probabilstica. La composicin de este informe se genera a travs de datos obtenidos desde internet de distintos papers los cuales analizamos y estudiamos detalladamente para tener una comprensin de la relacin de los procesos antes mencionados , de acuerdo con esto analizamos dos modelos de Cadenas de markov aplicados a lneas de espera para seleccionar el mayor beneficio o el menor costo dependiendo del caso al cual nos estemos refiriendo , desarrollamos dos diseos de sistemas de colas de capacidad limitada los cuales nos muestran cmo actan los procesos de decisin markoviano y con esto poder tomar las mejores decisiones en nuestro trabajo siempre pensando en optimizar el beneficio o reducir el costo como objetivo principal.

DESARROLLO

Para poder desarrollar nuestro estudio hemos indagado en bibliografa acerca de estos procesos de investigacin de operaciones que podran ser aplicados por las distintas empresas con el fin de mejorar sus utilidades entre otras cosas, en nuestro caso el rubro de la minera la informacin acerca de inventarios o determinadas actividades se encuentran restringidas a derecho privados lo que hace ms difcil su obtencin pero no cabe duda de que estos ejemplos si pueden ser aplicados a la industria minera, vale recordar el trabajo de lneas de espera aplicadas entre pala y camiones que realiz nuestro grupo este semestre.

APLICACIN DE CADENAS DE MARKOV A SISTEMAS DE ATENCIN

Definicin del problemaDado un sistema de atencin o prestacin de un servicio cualquiera a clientes de cualquier naturaleza, se quiere estudiar las caractersticas del proceso de atencin y de eventual espera en cola de los clientes (problema de anlisis) o determinar la configuracin de los canales de atencin para satisfacer un objetivo definido (problema de diseo o sntesis). Las principales caractersticas de estos procesos son las siguientes: Arribos de unidades a intervalos de tiempo regular o irregular a un sistema integrado por un centro de atencin o servicio (canales) y un centro de espera (cola) El centro de servicio puede estar constituido por una o varias estaciones o canales y cada unidad debe pasar por una (o eventualmente varias) estacin con el fin de recibir un servicio de duracin aleatoria. La duracin del servicio y el rgimen de arribos definen que las unidades puedan tener que esperar que una estacin se encuentre disponible, formando colas o lneas de espera.

Como ejemplo de estos procesos pueden mencionarse los siguientes:

La estructura de estos sistemas con sus elementos bsicos puede representarsede la siguiente manera:

Segn que la naturaleza del estudio sea de anlisis o de diseo, los interrogantes que surgen en el problema pueden estar dados por:

Adems el objetivo del problema puede ser:*Z=Costo mnimo = Costo operativo de 1 canal ($/hora.canal) * M (n de canales) + costo por demora de los clientes ($/hora.cliente) * L (n medio de clientes en el sistema) Mnimo

Adems el objetivo del problema puede ser:*Z=Costo mximo = Beneficio por atencin de clientes ($/cliente) * (velocidad de ingreso de clientes: clientes/hora) costo operativo de cada canal ($/hora.canal) * M (n de canales) Mximo

Para el clculo del nmero medio de clientes en el sistema es preciso definir una variable aleatoria de estado i=n que represente al nmero de clientes en el sistema. En funcin de la misma ser:

Para lo cual es necesario calcular las probabilidades del estado p, lo cual puede efectuarse mediante el mtodo de cadenas de Markov.

A continuacin se efecta la modelizacin del proceso mediante una cadena de Markov particular llamada de nacimiento y muerte para luego aplicar dicho modelo en distintos casos de sistemas de atencin.

Modelo de dos canales en paralelo de distinta velocidad y cola finita de una sola posicin

La estructura general del sistema es la siguiente:

Y el grfico de tasas de transicin, la matriz A y el vector p son:

Resolviendo el sistema de ecuaciones se obtienen las cinco probabilidades.

UN EJEMPLO NUMRICO

En una empresa bancaria denominada Banco R presenta el siguiente problema de Teora de Colas y Cadenas de Markov , Llegan 4 clientes cada hora a esta empresa , y esta dispone de dos cajas solamente, una caja A la cual atender a 3 clientes por hora y una caja B la cual atender a 2 clientes por hora.

Estados del Sistema:I Sistema VacoII Cliente en BIII Cliente en AIV Un cliente A y uno en BV Un cliente en A uno en B y uno en la colaVI Un cliente en A uno en B y dos en la cola

Matriz de tasas de transicin

Nmero Promedio de clientes en el sistemaL=0PI+ 1(PII + PIII) + 2PIV +3PV +4PVI

Nmero Promedio de clientes en la colaLC=0(PI+ PII + PIII + 2PIV) +1PV +2PVI

Nmero Promedio de clientes en cada canal de atencinHA=PIII+ PIV+ PV+ PVIHB=PII+ PIV+ PV+ PVI

Nmero Promedio de clientes que ingresan al sistema por horaQING= (PI+ PII+ PIII+ PIV+ PV)= (1- PVI)

Nmero Promedio de clientes que salen del sistema por hora: QSAL A+ QSAL BDonde QSAL A=A (PIII+ PIV+ PV+ PVI) y QSAL B=B (PII+ PIV+ PV+ PVI)

Tiempo promedio que un cliente permanece en el sistemaW= Tiempo promedio que un cliente permanece en la colaWc= Tiempo promedio que un cliente permanece en cada canal de atencinWcanal A= : Wcanal B=

Probabilidad de que un cliente sea atendido de inmediatoPI+ PII+ PIII Probabilidad de que un cliente no pueda ingresar por falta de espacioPVI Porcentaje del tiempo que el sistema est vaco 100*PI100*PI Porcentaje del tiempo que el sistema est totalmente ocupado100*PIV Porcentaje de tiempo que hay personas en cola100*(PV+ PIV) Porcentaje del tiempo que cada canal de atencin est en actividadA) 100*(PII+ PIV+ PV+ PVI)B) 100*(PIII+ PIV+ PV+ PVI)

Porcentaje del tiempo que cada canal de atencin no est ocupadoA) 100*[1-(PII+ PIV+ PV+ PVI)]B) 100*[1-(PIII+ PIV+ PV+ PVI)]

Definicin de estados1. Sistema vaco2. Un cliente en B3. Un cliente en A4. Un cliente en A y uno en B5. Un cliente en A, uno en B y uno en la cola6. Un cliente en A, uno en B y dos en la cola

Por otra parte, ac se presenta un sistema de colas con capacidad limitada M /M /1/ N (Winston [5]) a travs de la determinacin de la mejor poltica a seguir en las decisiones sobre propaganda, las cuales son tomadas teniendo en cuenta al nmero de clientes en cola en el instante de la toma de decisiones. As, si por ejemplo la longitud de cola es larga la decisin podr ser efectuar o no propaganda para aumentar la tasa de llegadas, tal decisin depender de los costes que conlleve la realizacin de publicidad.

Para llevar a cabo el proceso de optimizacin y encontrar la mejor poltica a seguir en cada estado de la Cadena de Markov que determina el sistema de colas vamos a utilizar la solucin por programacin lineal del proceso de decisin markoviano (Taha [4]). Esta solucin conlleva la formulacin de un programa lineal. Para un sistema con M estados y K alternativas de decisin, la formulacin del programa lineal asociado debe incluir M +1 restricciones y MK variables, el cual tender a ser muy extenso para valores de M y K grandes. Por ejemplo, si el sistema cuenta con una capacidad limitada a 15 unidades, el nmero de estados es M = N +1 = 16 , y suponiendo que existan dos alternativas de decisin, efectuar propaganda o no, entonces K = 2 , luego el sistema de programacin lineal que permite resolver para cada estado de la Cadena de Markov la decisin ms adecuada consta de 32 variables y 17 restricciones. Para reducir este nivel de clculo hemos desarrollado las Cadenas de Markov con estados fuzzy, de manera que en el problema en estudio se pueden considerar, por ejemplo, los estados fuzzy longitud corta de cola, longitud media de cola y longitud larga de cola y para resolver la optimizacin del sistema de colas a cada estado fuzzy se le asocia una alternativa de decisin (efectuar publicidad o no) de forma que el sistema de programacin lineal, dado que el modelo cuenta ahora con 3 estados (M = 3 ) y las alternativas de decisin son tambin 2 ( K = 2 ) consta de 6 variables y 4 restricciones, una cantidad de variables y restricciones sensiblemente inferior a las obtenidas sin la aplicacin de estados fuzzy sobre la Cadena de Markov.

CADENAS DE MARKOV CON ESTADOS FUZZY

Probabilidad de eventos fuzzy

Sea (,, P) el espacio probabilstico, donde denota el espacio muestral, una -lgebra sobre y P una medida de probabilidad. Un conjunto fuzzy A en define un evento fuzzy. Sea A () la funcin de pertenencia del evento fuzzy A. Entonces la probabilidad del evento fuzzy A y la probabilidad condicional del evento fuzzy A, dado un evento fuzzy B son definidas por Zadeh [7] como:

El producto de dos eventos fuzzy A y B se define como (Zimmermann [8]):A*B A*B=A*B

PROBABILIDADES DE LAS CADENAS DE MARKOV CON ESTADOS FUZZY

Sobre los estados del sistema definimos una particin fuzzy (Dubois y Prade [1]), es decir, un conjunto de estados fuzzy {1, 2, , n }, de manera que cada subconjunto fuzzy i , i {1,2,..., n } representa un estado o evento fuzzy de la cadena de Markov inicial.

Definicin 1: Se define la probabilidad de estado inicial fuzzy, P(i)=P(XO=i) a travs la probabilidad crisp de un evento fuzzy calculada mediante la integral de Lebesgue-Stieltjes (Zadeh [7]): ver anexo

SOLUCIN DEL PROBLEMA DE DECISIN MARKOVIANOEn esta seccin describimos brevemente la solucin por programacin lineal del proceso de decisin markoviano (Taha [4]). Para ello definimos las siguientes notaciones: pij(k): probabilidad de transicin del sistema del estado i al estado j cuando se toma la decisin k. C ik : coste esperado en el que se incurre durante la prxima transicin si el sistema est en el estado i y se toma la decisin k. y ik : probabilidad condicional de elegir la alternativa k dado que el sistema est en el estado i. C : coste esperado por transicin siguiendo una poltica R.

Una poltica R es un vector de decisiones di(R) cuando el sistema est en el estado i. As, R queda caracterizado por el vector d(R) = (d1(R),, dm (R)). Alternativamente, R tambin puede ser caracterizado asignando valores Dik = 0 1 en la matriz, en la cual cada columna debe contener un nico 1 y todos los dems elementos iguales a 0:

El conjunto de decisiones Dik y las variables yik estn relacionados por la ecuacin:

Con todo, el problema de decisin markoviano queda formulado mediante el siguiente programa lineal:

Con la solucin de este programa lineal se obtienen los valores de yik , y con (21) son obtenidos los resultados de las decisiones a tomar dependiendo el estado i, Dik.

Est demostrado que yik es estrictamente positivo para un nico k para cada i =1,..., M . Esto significa que la solucin ptima automticamente garantiza que Dik =1 para un nico k para cada i. Hay que tener en cuenta que para un problema con M estados y K alternativas de decisin, la formulacin del programa lineal asociado debe incluir M +1 restricciones y MK variables, el cual tender a ser muy extenso para valores de M y K grandes. Y es en esta situacin en donde las Cadenas de Markov con estados fuzzy pueden reducir considerablemente la complejidad computacional, proporcionando resultados ms acordes con las circunstancias reales.

UN EJEMPLO NUMRICOEl problema est relacionado con las decisiones de publicidad a tomar en un sistema de colas, y consiste en decidir si efectuar o no publicidad teniendo en cuenta la longitud de cola en el sistema. El sistema de colas en estudio es del modelo M/M /1/N y cuenta con un proceso de entrada de Poisson y tiempos de servicio acordes a una distribucin exponencial, la capacidad del sistema es de 10 unidades. El estudio del comportamiento del sistema evidencia que la tasa de llegadas es = 0.4 cuando no se toma la decisin de efectuar publicidad y = 0.6 cuando hay publicidad. La tasa de servicios depende de la longitud de la cola de manera que si la longitud de unidades en cola es inferior a 5 unidades entonces la tasa de servicio es de = 0.3, y si la longitud de unidades en cola es 5 ms, en ese momento el servicio se refuerza aumentando la tasa de servicio a = 0.5. Dada la capacidad del sistema, los estados de la cadena de Markov asociada son X = {0,1,...,10}. Hay dos alternativas de decisin, (1) no publicidad (k =1) y (2) publicidad (k = 2). Si denotamos por P la matriz de probabilidad de transicin asociada con X, entonces dados los valores de y , es:

Y si denotamos por Pk la matriz de probabilidad de transicin asociada con X para la decisin k, entonces las matrices Pk para k = 1, 2 son:

Para encontrar la solucin por programacin lineal del proceso de decisin planteado el programa lineal debe contener 12 restricciones y 22 variables. Este mtodo de clculo puede ser sensiblemente reducido si los estados del sistema son fuzzy. As, en el sistema las decisiones sern asociadas con tres estados fuzzy denotados 1, 2 y 3 que corresponden a longitud corta de cola, longitud media de cola y longitud larga de cola, respectivamente. Y sobre los 11 estados del sistema se establece la siguiente particin fuzzy que relaciona los estados iniciales del sistema con los estados fuzzy, definidos mediante la matriz Q:

Hay que resear que los estados del sistema, X son conocidos en los problemas especficos de modelos de decisin de colas. Sin embargo hay que decidir los estados fuzzy correspondientes y sus funciones de pertenencia, para poder desarrollar la metodologa propuesta. Esto puede hacerse a travs del mtodo formulado por Yager [6] o el mtodo de Dubois et al. [2] para la construccin de funciones de pertenencia a partir de datos obtenidos de diversas fuentes o de expertos. Se han calculado los costes esperados para las dos decisiones y los tres estados fuzzy y se muestran en la tabla 1.

Supondremos que las probabilidades de estado inicial pi son todas iguales, luego pi =1/11. Con este dato se obtiene que las probabilidades de estado inicial fuzzy son:P (1)=3.2/11 P (2)=4.6/11 P (3)=3.2/11Y la matriz S:

Las matrices de probabilidad transicin correspondientes a los estados fuzzy 1, 2 y 3 para la decisin k, = [Pk (j / i)] se obtiene usando (18): k= SPkQ:

Con todo, el programa lineal a plantear para encontrar la solucin al problema de si efectuar o no publicidad teniendo en cuenta la longitud de cola en el sistema, consta de 4 restricciones y 6 variables, y es:

Minimizar C=10y11 + 3y12 +7y21 +5y22 +4y31 +7y32 sujeto a y11 + y12 +y21 +y22 +y31 +y32 =1y11 + y12 (0.8335y11 +0.07978y12 +0.0941y21 +0.0755y22)=0y21 + y22 (0.1665y11 +0.2022y12 +0.8103y21 +0.8071y22 +0.1687y31 +0.1375y32)=0y31 + y32 (0.0956y21 +0.1174y22 +0.8313y31 +0.8625y32)=0yik 0, i=1,2,3; k=1,2La solucin ptima es y11=y21=y32=0 y y12=0.1804, y22=0.4834 y y31=0.3362. Luego utilizando (21) es:

As, la poltica ptima selecciona la alternativa 2 ( k = 2 ), es decir efectuar propaganda cuando el sistema se encuentra en los estados fuzzy 1 y 2 (longitud corta y media de cola) y la alternativa 1 ( k =1 ), es decir no efectuar propaganda cuando el sistema se encuentra en el estado fuzzy 3 (longitud larga de cola), siendo el valor ptimo de C igual a 3.697.

Conclusiones

Los sistemas de colas son muy comunes en la sociedad, por ejemplo personas esperando para realizar transacciones un banco, estudiantes esperando en las fotocopiadoras, vehculos esperando para pagar una estacin de peajes, mquinas daadas esperando mantencin, etc.La adecuacin de estos sistemas puede tener un efecto importante sobre la calidad de vida y la productividad.Para estudiar estos sistemas, la teora de colas formula modelos matemticos que representan su operacin y despus usa estos modelos para obtener medidas de desempeo. Este anlisis proporciona informacin vital para disear de manera efectiva sistemas de colas que logren un balance apropiado entre el costo de proporcionar el servicio y el costo asociado con la espera por ese servicio.Por otro lado las cadenas de Markov, se pueden considerar como una de las grandes aportaciones de las matemticas. No necesariamente tienes que ser un experto en la materia para poder entender en qu consisten y el uso que le puedes dar en las diferentes situaciones de la vida diaria.

Se ha demostrado que las cadenas de Markov tienen un gran valor en la economa, ya que mientras nos predice lo que podra ocurrir en un segundo periodo de tiempo, los mercados lo utilizan para mejorar sus propios intereses.

El concepto de probabilidad de eventos fuzzy asociados a los procesos de decisin Markovianos permite dar solucin a situaciones en las cuales los estados no puedan ser medidos con precisin, debido a que los estados son perfectamente medibles y observables pero el nmero de estados es tan amplio que las decisiones no pueden ser asociadas con los estados exactos el sistema.

Si el sistema a evaluar cuenta con un amplio nmero de estados la solucin tendr por tanto un gran nmero de variables y restricciones. Mediante el uso de las Cadenas de Markov con estados fuzzy, el sistema a resolver es reducido considerablemente lo que conlleva una disminucin de la complejidad computacional as como de la toma de decisiones ya que sta queda limitada a slo tres estados (longitud corta, media o larga de cola).

Si bien en este trabajo hemos visto la aplicacin de las Cadenas de Markov con o sin estados fuzzy en la Teora de Colas, stas pueden ser utilizadas tanto en problemas de inventarios (neumticos,E.P.P) como en mantenimiento de sistemas, mayor eficiencia para el Carguo y transporte, entre otros.

La sinergia de estas dos materias suena complejo, pero no lo es como parece, y sus aplicaciones pueden solucionar grandes problemas ya sea de empresas o personas particulares.

Referencias

[1] D. Dubois, H. Prade. Fuzzy Sets and Systems: Theory and Applications. Academic Press, Boston, 1980.

[2] D. Dubois, H. Prade, R.R. Yager. Merging fuzzy information. En: J. Bezdek, D. Dubois, H. Prade (Eds.), Fuzzy Sets in Approximate Reasoning and Information Systems. Kluwer, Boston 1999, pg. 335-401.

[3] D. de la Fuente, M.J. Pardo. Calculation of the degree of customer satisfaction for the optimization and design of a flow line system with finite capacity and fuzzy data. XIV Congress of International Association for Fuzzy Set Management and Economy, SIGEF07. Poiana Braov, Romania, pg. 540-558, 2007.

[4] H.A. Taha. Operations Research: An Introduction (seventh ed.). Prentice-Hall, New Jersey, 2003.

[5] W.L. Winston. Operations Research: Applications and Algorithms (fourth ed.). Duxbury Press, Boston, 2003.

[6] R.R. Yager. Level sets for membership evaluation of fuzzy subsets. En R.R. Yager (Ed.), Fuzzy Sets and Possibility Theory: Recent Developments. Pergamon Press, Oxford, 1982, pg. 90-97. [7] L.A. Zadeh. Probability measures of fuzzy events. Journal of Mathematical Analysis and Applications 23, pg. 421-427, 1968.

[8] H.J. Zimmermann. Fuzzy Set Theory and its applications (fourth ed.). Kluwer, Boston, 2001.

Anexo