Trabajo de investigacion de Cadenas Markov PDF

Preview

Summary

Tarea...

Description

Tecnológico nacional de México Instituto tecnológico de Mérida Ingeniería industrial Investigación de operaciones II

Alumno: Montero Antonio Claudia Vanesa.

Facilitador: Ing. Cantillo Palma Joaquín Gaspar.

Grupo: 5i2

Enero-Junio 2020

Tema 4

Cadenas de Markov.

2

Tabla de contenido

Introducción. ............................................................................................................ 4 Aspectos fundamentales de la cadenada de Markov en la vida real. ...................... 5 Definición de cadenada de Markov ......................................................................... 5 Estados de la naturaleza y de los sistemas en la vida real. .................................... 6 Aplicación del modelo de Cadenas de Markov...................................................... 10 Resultados y discusión Descripción del proceso de producción................. 11 Ventajas y desventajas de su aplicación. .............................................................. 16 Ventajas. ..................................................................................................... 16 Desventajas ................................................................................................ 16 Características básicas de las cadenas de Markov ............................................... 17 Irreducibilidad.............................................................................................. 17 Absorsorbencia ........................................................................................... 17 Regularidad ................................................................................................ 17 Formulación de los problemas de aplicación de las cadenas de Markov .............. 18 Aplicación de las cadenas de Markov en la vida real. ........................................... 21 Ejemplo 1: ................................................................................................... 21 Ejemplo 2: ................................................................................................... 22 Ejemplo 3 .................................................................................................... 23 Conclusión............................................................................................................. 24 Referencias. .......................................................................................................... 25

3

Introducción. En esta 4ta unidad se habla sobre la importancia en la cual se debe implementar las cadenas de Markov. Las cadenas de Markov constituyen una clase de procesos estocásticos que ha tomado gran importancia por sus múltiples aplicaciones, así como sus aspectos teóricos. Quizá esto se deba a que gran parte de la teoría se puede interpretar de una manera intuitiva. Más aun cuando los objetos que intervienen para su descripción se pueden analizar de manera discreta, como es el caso del presente trabajo. Las cadenas de markov son modelos probabilísticos que se usan para predecirla evolución y el comportamiento a corto y a largo plazo de determinados sistemas En este documento presentaremos los aspectos generales de la teoría de cadenas de Markov con espacio de estados discreto. Introduciremos las definiciones y resultados más importantes que serán usados en el resto del trabajo.

4

Aspectos fundamentales de la cadenada de Markov en la vida real.

Las cadenas de Markov han experimentado una importante aplicación real en el ámbito de los negocios y las finanzas, al permitir como se ha señalado analizar y estimar futuros patrones de conducta de los individuos atendiendo a la experiencia y los resultados anteriores. Esto puede reflejarse en diferentes campos como la prevención de la morosidad, el estudio de las conductas de consumidores de un sector o la necesidad estacional de personal y mano de obra.

Pese a que el sistema elaborado por Markov es bastante sencillo y cuenta como hemos dicho con una aplicación práctica bastante fácil, son muchas las voces críticas que han señalado esta ventaja como una desventaja al mismo tiempo, debido a que un modelo tan simplificado no puede ser totalmente efectivo en procesos complejos. 1. Serie mensual de ventas de un producto 2. Estado de una máquina al final de cada semana (funciona/averiada) 3. Nº de clientes esperando en una cola cada 30 segundos 4. Marca de detergente que compra un consumidor cada vez que hace la compra. Se supone que existen 7 marcas diferentes 5. Nº de unidades en almacén al finalizar la semana

Definición de cadenada de Markov Una cadena de Markov es una sucesión de ensayos similares u observaciones en la cual cada ensayo tiene el mismo número finito de resultados posibles en donde también la probabilidad de cada resultado para un ensayo dado depende solo de resultados del ensayo inmediatamente precedente no de cualquier resultado previo.

5

Estados de la naturaleza y de los sistemas en la vida real. Sean i y j dos

estados

de

una

cadena

de

Markov,

diremos

que j es accesible desde i si

De otra forma el estado j es accesible desde i si existe una probabilidad positiva de que en un número finito de transiciones el estado j puede ser alcanzado desde el estado i.

Diremos

que

los

estados i y j son comunicativos si

ambos

son

mutuamente accesibles. Entonces dos estados i y j son no comunicativos si ocurre una o ambas situaciones:

La relación comunicativos es una relación de equivalencia entre los estados, luego esta relación define una partición en el espacio de estados agrupados en clases de equivalencia. Veamos un ejemplo, sea la matriz de transición

el grafo asociado a esta cadena de Markov es

6

Las clases de equivalencia son {0,1}, {2,3,4}. Si el estado inicial pertenece a la clase del {0,1} entonces, cualquiera sea el tiempo, permanecerá en esa clase, y para cualquier estudio del desarrollo dinámico de este sistema la matriz relevante será

De manera análoga, si el proceso se inicia en los estados {2,3,4}, entonces para cualquier tiempo posterior el proceso seguirá en dicha clase, y la matriz relevante será

El ejemplo anterior indica que al haber dos clases existe una "reducción" de la matriz de transición que dependerá de cuál es el estado inicial del proceso. Esto nos induce a entregar la siguiente definición. Diremos que una cadena de Markov es irreducible si la relación de equivalencia "comunicativos" genera una única clase. Esto es, el proceso es irreducible si todos los estados son comunicativos.

Periodicidad de una cadena de Markov: Se define el período de un estado i, y se denota por d(i), como el máximo común divisor de los enteros

para los

cuales 7

Ahora si

se define d(i) = 0.

Existen tres propiedades básicas del período de un estado que se puede verificar con lápiz y papel para diversas cadenas de Markov 

si i y j son comunicativos entonces d(i) = d(j)



Si i tiene período d(i) entonces existe un entero N tal que para todo n>N se

cumple que Esta propiedad asegura que el retorno a i puede ocurrir para todo múltiplo de d(i) suficientemente grande.



Si

para todo n suficientemente grande. Una cadena de Markov en la que cada estado tiene período 1 es llamada aperiódica. Una gran parte de las cadenas de Markov caen dentro de esta clasificación. Recurrencia. Vamos a definir el "regreso a casa en n pasos por primera vez". Para el estado i y el tiempo n definimos la probabilidad

Esto es,

es la probabilidad de que, partiendo desde el estado i, el primer

regreso al estado i ocurra en la n-ésima transición.

8

Es

claro

que

.

Ahora

la

probabilidad

se

puede

calcular

recursivamente de acuerdo a

donde se define

.

De manera similar podemos definir la probabilidad

; esto es, como la

probabilidad de la primera llegada desde el estado i al estado j en la n-ésima

transición. Se define, además,

. También es fácil verificar que

En base a la definición de las probabilidades

vamos a decir que un

estado i es recurrente si partiendo de i llegará, con probabilidad 1 en un tiempo finito, nuevamente al estado i. De otra forma i es recurrente si y solo

si

dirá transitorio si

.

Por

el

contrario,

el

estado i se

. Esta última definición nos dice que, si un

proceso abandona un estado transitorio, existe una probabilidad positiva de que nunca regrese.

9

Aplicación del modelo de Cadenas de Markov

Se aplicó el modelo de Cadenas de Markov para determinar el número de explantes iniciales que se requiere establecer para obtener un número definido de lote de producción (3,000 plantas finales mediante tres ciclos de multiplicación in vitro), según la estandarización de la empresa. Se estableció un registro histórico del número de plantas que fueron desechadas, reprocesadas y aquellas que continuaron su ciclo de reproducción. Se calculó la matriz de transición de Markov tomando en cuenta un 95% de éxito en la etapa de enraizamiento y la transición al empaque final, según registros de la empresa. A partir de la matriz obtenida, se estimaron las probabilidades de los estados adsorbentes (empaque y desecho) de cada etapa, mediante las operaciones matriciales: • Resta de Matriz Identidad con Matriz Transitoria: (I-N) • Matriz Inversa de 1-N: M inversa (I-N) • Multiplicación de la Matriz Inversa por la Matriz Absorbente: M inversa(I-N)*M(A). Con el cálculo de las probabilidades anteriores, se planteó una fórmula para obtener el número de plantas requeridas para cumplir con el lote de producción final, de acuerdo con la etapa en la que se encuentre el material vegetal. En esta fórmula, se presentó una relación entre el número de plantas deseadas, el coeficiente de multiplicación, el

número de ciclos de multiplicación y la probabilidad

correspondiente según la matriz de Markov.

Plantas iniciales = Nd CMN ciclos*Pij donde: Nd = Número de plantas deseadas CM = Coeficiente de Multiplicación N ciclos = Número de ciclos de multiplicación Pij = Probabilidad de acuerdo a Markov (Factor Markov) dependiendo de donde se inicie el proceso. El coeficiente de multiplicación utilizado fue de 3,74 y representa la relación de plantas finales entre plantas iniciales. Se obtuvo mediante el promedio de tres ciclos de multiplicación históricos de la empresa.

10

Resultados y discusión Descripción del proceso de producción.

El proceso productivo consiste en utilizar brotes axilares con capacidad regenerativa, obtenidos de campo o invernadero, que son desinfectados superficialmente e introducidos en medios nutritivos estériles bajo condiciones físicas controladas (temperatura, luz, humedad y foto periodo). Esta etapa es el establecimiento in vitro, durante el cual los brotes se activan en las condiciones artificiales de laboratorio y se seleccionan para la siguiente etapa aquellos que no presenten contaminación ni anormalidades. Estos brotes activados regeneran plantas completas durante un tiempo variable de incubación controlada y se utilizan para la etapa de multiplicación del material cuando alcanzan la altura y el desarrollo adecuados; estas plantas también pueden colocarse bajo condiciones de conservación (temperatura, nutrientes y luz reducidos) para tomarlas en el momento que se requieran para multiplicarlas. Luego del establecimiento se inicia la etapa de multiplicación in vitro, en la que los operarios toman las plantas que los brotes generaron y las seccionan en explantes tipo microestacas y nuevamente se cultivan en medios nutritivos frescos a razón de cuatro microestacas por frasco, lo que se conoce como subcultivo. Entre cada ciclo de subcultivo se define un período de incubación (aproximadamente 30 días) en cuartos controlados, durante los cuales el producto se transforma debido a procesos biológicos inducidos. Durante la labor de subcultivo, los operarios, además de seccionar el material y cultivarlo, lo inspeccionan y reprocesan aquellas plantas del lote de producción que no lograron el desarrollo adecuado, regresándolas a una etapa anterior. El período de incubación, aunque no implica manipulación de las plantas, se considera una operación debido a que ocurre transformación (biológica) del producto; también hay desecho (básicamente por contaminación) y reproceso (caída de plantas, presencia de oxidación, por ejemplo), lo que obliga a un recultivo en esta etapa. De esta forma, la etapa de multiplicación implica ciclos de crecimiento exponencial del material, los cuales finalizan de forma inducida, cuando se llega al 11

número final de explantes que potencialmente generaran las plantas requeridas para un lote. En este momento se transfieren a un medio de cultivo diferente que les permite desarrollarse en plantas y generar raíces, de manera que están listas para ser empacadas y transferidas a condiciones de invernadero. En todo el proceso de producción se tienen dos estados absorbentes, correspondientes al descarte y al producto terminado empacado al final. El cuadro 1 muestra información de cada una de las etapas involucradas en el proceso de producción.

12

13

De acuerdo con el cuadro anterior, para la columna de empaque se observa que las probabilidades de que una planta llegue hasta producto terminado aumentan conforme se avanza en las etapas del proceso de producción. Así, por ejemplo, la probabilidad de que una planta que se tome del stock y se convierta en producto terminado es menor (0,707) en comparación con una planta que se tome del ciclo de multiplicación III (0,821). Esta probabilidad involucra el reproceso que sufren las plantas en las respectivas etapas de inspección y ciclos de multiplicación. Desde el punto de vista biológico, el comportamiento ascendente de los valores de probabilidad a lo largo del proceso para que las plantas se conviertan en producto terminado, es un reflejo de la adaptación de los individuos a las condiciones de producción, conforme se avanza en el procedimiento. Con respecto a las probabilidades de desecho, se evidencia un comportamiento descendiente, en que se pierden menos plantas conforme se avanza en el proceso. Aunque la contaminación es un factor muy variable, otras fuentes de pérdida, como la muerte de las plantas, puede estar incidiendo en esta tendencia; es decir, es probable que la cantidad de plantas que se pierden por mortalidad disminuya 14

conforme se avanza en el sistema, debido a una mejor adaptación a las condiciones de crecimiento (Berthouly & Etienne, 2005). Con la ecuación; plantas iniciales = Nd CMN /ciclos*Pij , se estimó el número de plantas iniciales requeridas para la producción de un lote final de 3,000 vitro plantas para aclimatación. Para el coeficiente de multiplicación de la etapa de enraizamiento se utilizó un valor de 1, porque en esta fase únicamente se hace un cambio de medio de las plantas generadas por el ciclo de multiplicación III sin segmentarlas (cuadro 3).

15

Ventajas y desventajas de su aplicación. Ventajas. 

Simple de aplicar y entender



Los cálculos de sensibilidad se hacen fácilmente



Nos da con el tiempo una visión de los cambios en el sistema

Desventajas: Es un modo simplificado de un proceso de toma de decisiones complejo. Otras ventajas y desventajas: 

Teoría de Markov es simple de aplicar y entender.



Cálculos de sensibilidad (contestar las preguntas "qué-si") se llevan a cabo fácilmente.



La teoría de Markov nos da con el tiempo una visión de los cambios en el sistema.



P puede ser dependiente del estado actual del sistema. Si P es dependiente tanto del tiempo y del estado actual del sistema i.e., P es una función de t y st, entonces la ecuación de Markov básica se vuelve st=st-1P(t-1,st-1).



La teoría de Markov es un modelo simplificado de un proceso de toma de decisión complejo

16

Características básicas de las cadenas de Markov Irreducibilidad 

En una cadena de Markov un estado e j se dice que es accesible desde otro estado e i si la probabilidad de ir desde el estado e i al ej en algún momento futuro es distinta de cero.



Un estado e i está comunicado con otro e j si ej es accesible desde ei y ei lo es desde ej.



Una cadena de Markov se dice que es irreducible si todos los estados están comunicados entre sí.

Absorsorbencia 

Un estado e j se dice absorbente si es imposible abandonar dicho estado, es decir P(Xk= ej½Xk-1= ej) = 1.



Una cadena de Markov es absorbente si tiene algún estado absorbente.



Si una cadena de Markov es irreducible y absorbente entonces la probabilidad de caer en alguno de los estados absorbentes tiende a uno cuando el número de etapas tiende a infinito.

Regularidad 

Una cadena de Markov se dice que es regular si alguna potencia de la matriz de transición tiene todos sus elementos positivos (no hay ceros)



Si una cadena es regular entonces es irreducible y no absorbente.

17

Formulación de los problemas de aplicación de las cadenas de Markov

En la figura 4.1.1 se muestra el proceso para formular una cadena de Markov. El generador de Markov produce uno de n eventos posibles, E j., donde j = 1, 2, . . ., n, a intervalos discretos de tiempo (que no tiene que ser iguales). Las probabilidades de ocurrencia para cada uno de estos eventos dependen del estado del generador. Este estado se describe por el último evento generado. En la figura 4.1.1, el último evento generado fue E j, de manera que el generador se encuentra en el estado Mj.

La probabilidad de que Ek sea el siguiente evento generado es una probabilidad condicional: P ( Ek / Mj ). Esto se llama probabilidad de transición del estado M j al estado Ek. Para describir completamente una cadena de Markov es necesario saber el estado actual y todas las probabilidades de transición.

18

Ejercicio Una empresa está considerando utilizar Cadenas de Markov para analizar los cambios en las preferencias de los usuarios por tres marcas distintas de un determinado producto. El estudio ha arrojado la siguiente estimación de la matriz de probabilidades de cambiarse de una marca a otra cada mes:

Si en la actualidad la participación de mercado es de 45%, 25% y 30%, respectivamente. ¿Cuáles serán las participaciones de mercado de cada marca en dos meses más? En primer lugar definimos la variable aleatoria

que representa la marca que

adquiere un cliente cualquiera en el mes n. Dicha variable aleatoria puede adoptar los valores 1,2,3 en el mes n=0,1,2,3,.. Adicionalmente conocemos cuál es la distribución inicial y la matriz de probabilidades de transición en una etapa tal como se observa a continuación:

Luego para conocer la distribución de las participaciones de mercado al cabo de 2 meses (2 etapas) podemos utilizar la fórmula

: 19

Se concluye que las cuotas de mercado (participaciones de mercado) en dos meses a cambiado de un 4...