• Author / Uploaded
• Victor Manuel Cruz Martinez

Citation preview

Instituto Tecnológico Superior de Coatzacoalcos. División de Ingeniería Industrial.

AGOSTO – DICIEMBRE 2019. Nombre del Alumno:

Cruz

Martínez

Apellido Paterno

Apellido Materno

Víctor Manuel Nombre(s)

ASIGNATURA: INVESTIGACIÓN DE OPERACIONES II UNIDAD 4 “CADENAS DE MARKOV”

Carrera:

Ing. Industrial

No Control:

Semestre:

5°

Grupo:

``B``

17081151.

Nombre del Docente:

Jiménez

Apellido Paterno

Ventura

Bricio.

Apellido Materno

Nombre(s)

Fecha: 21/10/2019

ÍNDICE. Introducción.

3

Desarrollo. 4.1. Introducción a las cadenas de Markov.

4

4.2. Probabilidad de transiciones estacionarias de n pasos.

9

4.3. Estado estable.

12

4.4. Casos especiales (cadenas absorbentes, cadenas cíclicas).

14

4.5. Uso de software

18

Conclusión.

22

Referencias bibliográficas.

23

2

INTRODUCCIÓN. La explicación de estas cadenas fue desarrollada por el matemático de origen ruso Andréi Márkov en el año 1907 y a través de su estudio a lo largo del siglo XX se han podido emplear en numerosos casos prácticos de la vida cotidiana y la investigación. También se conoce como cadena simple biestable de Markov. Según señaló Markov, en sistemas o procesos estocásticos (es decir, aleatorios) que presentan un estado presente o actual es posible conocer sus antecedentes o desarrollo histórico y, por lo tanto, establecer una descripción de la probabilidad futura de los mismos. En las cadenas de Markov considera ciertos puntos discretos en el tiempo para toma valores de la variable aleatoria que caracteriza al sistema. Entonces las cadenas de Markov se usan para estudiar ciertos comportamientos de largo y cortos plazos de sistemas. Los estados en el tiempo representan situaciones exhaustivas y mutuamente excluyentes del sistema en un tiempo específico. Además, el número de estado puede ser finito o infinito. Por lo general una cadena de Markov describe el comportamiento de transición de un sistema en intervalos de tiempo igualmente espaciados. Sin embargo, existen situaciones donde los espaciamientos temporales dependen de las características del sistema y por ello, pueden no ser iguales entre sí. Las cadenas de Markov se pueden aplicar en áreas como la educación, comercialización, servicios de salud, finanzas, contabilidad y producción.

3

UNIDAD 4 “CADENAS DE MARKOV” 4.1. Introducción a las cadenas de Markov. Una cadena de Markov es una serie de eventos, en la cual la probabilidad de que ocurra un evento depende del evento inmediato anterior. En efecto, las cadenas de este tipo tienen memoria. " Recuerdan" el último evento y esto condiciona las posibilidades de los eventos futuros. Esta dependencia del evento anterior distingue a las cadenas de Markov de las series de eventos independientes, como tirar una moneda al aire o un dado. 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 Ej , 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 Mj al estado Ek. Para describir completamente una cadena de Markov es necesario saber el estado actual y todas las probabilidades de transición.

4

Probabilidades de transición. Una forma de describir una cadena de Markov es con un diagrama de estados, como el que se muestra en la figura 4.1.2. En ésta se ilustra un sistema de Markov con cuatro estados posibles : M1, M2 , M3 y M4 . La probabilidad condicional o de transición de moverse de un estado a otro se indica en el diagrama

Otro método para exhibir las probabilidades de transición es

usar

una

matriz

de

transición. . La matriz de transición para el ejemplo del diagrama de estados se muestra en la tabla 4.1.1 .

Otro método para exhibir las probabilidades de transición es usar una matriz de transición. . Para n = 0, 1, 2, .... El superíndice n no se escribe cuando n = 1. Procesos estocásticos. Un proceso estocástico se define sencillamente como una colección indexada de variables aleatorias { Xt }, donde el subíndice t toma valores de un conjunto T dado. Con frecuencia T se toma como el conjunto de enteros no negativos, y X representa una característica de interés medible en el tiempo t. Por ejemplo, el proceso estocástico, X1 , X2 , X3, .., puede representar la colección de niveles de inventario 5

semanales (o mensuales) de un producto dado, o puede representar la colección de demandas semanales (o mensuales) de este producto. Un estudio del comportamiento de un sistema de operación durante algún periodo suele llevar al análisis de un proceso estocástico con la siguiente estructura. En puntos específicos del tiempo t , el sistema se encuentra exactamente en una de un número finito de estados mutuamente excluyentes y exhaustivos, etiquetados 0, 1, . . , s. Los periodos en el tiempo pueden encontrarse a intervalos iguales o su esparcimiento puede depender del comportamiento general del sistema en el que se encuentra sumergido el proceso estocástico. Aunque los estados pueden constituir una caracterización tanto cualitativa como cuantitativa del sistema, no hay pérdida de generalidad con las etiquetas numéricas 0, 1, . . , M , que se usarán en adelante para denotar los estados posibles del sistema. De esta forma, la representación matemática del sistema físico es la de un proceso estocástico {Xi}, en donde las variables aleatorias se observan en t = 0, 1, 2,. . ., y en donde cada variable aleatoria puede tomar el valor de cualquiera de los M + 1 enteros 0, 1, .. , M . Estos enteros son una caracterización de los M + 1 estados del proceso.

Propiedad Markoviana de primer orden.

Se dice que un proceso estocástico tiene la propiedad markoviana si

P { Xt+1 = j | X0 = K0 , X1 = K1 , . ., Xt-1 = Kt-1 , = Kt-1, Xt = 1} = P { X t+1 | X1 = i }, para toda t = 0, 1, . . y toda sucesión i, j , K0 , K1 , . . , Ki-1 .

Se puede demostrar que esta propiedad markoviana es equivalente a establecer una probabilidad condicional de cualquier "evento" futuro dados cualquier "evento " pasado y el estado actual Xi = i , es independiente del evento pasado y sólo depende del estado actual del proceso. Las probabilidades condicionales P{ Xt+1 = j | Xt = i } se llaman probabilidades de transición. Si para cada i y j, P{ Xt+1 = j | 6

| Xt = i } = p{ X1 = j | X0 = i }, para toda t = 0, 1, ....

Entonces se dice que las probabilidades de transición (de un paso) son estacionarias y por lo general se denotan por pij . Así, tener probabilidades de transición estacionarias implican que las probabilidades de transición no cambian con el tiempo. La existencia de probabilidades de transición (de un paso) estacionarias también implica que, para cada i, j y n (n = 0, 1, 2,...),

P{ Xt+n = j | | Xt = i } = p{Xn = j | X0 = i }, Para toda t = 0, 1, . . .

Estas probabilidades condicionales casi siempre se denotan por llaman probabilidades de transición de n pasos. De esta manera,

y

se es

simplemente la probabilidad condicional de que la variable aleatoria X, comenzando en el estado i, se encuentre en el estado j después de n pasos ( unidades de tiempo ). Como las

son probabilidades condicionales, deben satisfacer las propiedades:

7

4.2. Probabilidad de transiciones estacionarias de n pasos. Las ecuaciones de Chapman-Kolmogorov proporcionan un método para calcular estas probabilidades de transición de n pasos:

Estas ecuaciones simplemente señalan que al ir de un estado i al estado j en n pasos, el proceso estará en algún estado k después de exactamente m (menor que n) pasos. Así, Es solo la probabilidad condicional de que, si se comienza en el estado i, el proceso vaya al estado k despues de m pasos y después al estado j en n- m pasos.

Los casos especiales de m=1 y m=n-1 conducen a las expresiones Para toda i, j, y n de lo cual resulta que las probabilidades de transición de n pasos se pueden obtener a partir de las probabilidades de transición de un paso de manera recursiva. Para n=2, estas expresiones se vuelven:

Note que las

son los elementos de la matriz P(2) , pero también debe de

observarse que estos elementos,

se obtienen multiplicando la matriz de

transición de un paso por sí misma; esto es , P(2) = P * P = P2 .

En términos más generales, se concluye que la matriz de probabilidades de transición de n pasos se puede obtener de la expresión : P(n) = P * P .... P = Pn = PPn-1 = Pn-1 P. Entonces, la matriz de probabilidades de transición de n pasos se puede obtener calculando la n-ésima potencia de la matriz de transición de un paso. Para valores no muy grandes de n, la matriz de transición de n pasos se puede calcular en la forma que se acaba de describir, pero cuando n es grande, tales cálculos resultan tediosos y, más aún, los errores de redondeo pueden causar inexactitudes. Ejemplo: Una tienda de cámaras tiene en almacén un modelo especial de cámara que se puede ordenar cada semana. Sean D1, D2, ... las demandas de esta cámara durante la primera, segunda, ... , semana, respectivamente. Se supone que las D i son variables aleatorias independientes e idénticamente distribuidas que tienen una distribución de probabilidad conocida. Sea X0 el número de cámaras que se tiene en el momento de iniciar el proceso, X1 el número de cámaras que se tienen al final de la semana uno, X2 el número de cámaras al final de la semana dos, etc. Suponga que X0 = 3 . El sábado en la noche la tienda hace un pedido que le entregan el lunes en el momento de abrir la tienda. La tienda hace un pedido que le entregan el lunes en el momento de abrir la tienda. La tienda usa la siguiente política ( s, S) 1 para ordenar : si el número de cámaras en inventario al final de la semana es menor que s =1 (no hay cámaras en la tienda), ordenar (hasta) S=3. De otra manera, no coloca la orden (si se cuenta con una o más cámaras en el almacén, no se hace el pedido). Se supone que las ventas se pierden cuando la demanda excede el inventario. Entonces, {X1} para t = 0, 1, .. es un proceso estocástico de la forma que se acaba de describir. Los estados posibles del proceso son los enteros 0, 1, 2, 3 que representan el número posible de cámaras en inventario al final de la semana.

9

Así, dado que tiene una cámara al final de una semana, la probabilidad de que no haya cámaras en inventario dos semanas después es 0.283; es decir, De igual manera, dado que se tienen dos cámaras al final de una semana, la probabilidad de que haya tres cámaras en el almacén dos semanas después es 0.097; esto es, La matriz de transición de cuatro pasos también se puede obtener de la siguiente manera: P(4) = P4 = P(2) * P(2) Así, dado que queda una cámara al final de una semana, 0.282 es la probabilidad de que no haya cámaras en inventario 4 semanas más tarde; es decir, De igual manera, dado que quedan dos cámaras en el almacén final de una semana, se tiene una probabilidad de 0.171 de que haya tres cámaras en el almacén 4 semanas después; esto es,

4.3. Estado estable. El termino probabilidad de estado estable significa que la probabilidad de encontrar el proceso es cierto estado despues de un numero grande de transiciones es independiente de la distribucion de probabilidad inicial definida para los estados. Es

10

importante observar que la probabilidad de estado estable no significa que el proceso se establezca en un estado. Parece que existe una probabilidad limite de que el sistema se encuentre en el estado “j” despues de un numero grande de transicion, y que esta probabilidad es independiente

del

estado

inicial.

En

realidad,

estas

propiedades

del

comportamiento a largo plazo de un proceso de Markov de estado finito se cumplen en condiciones relativamente generales. El termino probabilistico de estado estable significa que la probabilidad de econtrar el proceso en cierto estado despues de un numero grande de transiciones es independiente de la districubucion de probabilidad inicial definida para los estados. Es importamte observar que la probabilidad de estado estable no significa que el proceso se establezca en un estado. Por el contrario, el proceso continua haciendo transiciones de un estado a otro y en cualquier paso “n” la probabilidad de transicion del estado “i” al estado “j” es todavia Pij. Para n grande, tiende a una matriz con renglones idénticos. Esto significa que después de un largo tiempo, la cadena de markov se estabiliza, e (independientemente del estado inicial i) hay una probabilidad de que se está en el estado. El vector se llama distribución de estado estable o distribución de equilibrio, para la cadena de markov. Para una cadena determinada con matriz de transición P, ¿cómo se puede hallar la distribución de probabilidad de estado estable? A partir del teorema 1, se observa que para n grande y toda i, Teorema Sea P la matriz de transición de una cadena de M estados. Existe entonces un vector

tal que

11

Se establece que para cualquier estado inicial i , El vector

.

a menudo se llama distribución de estado estable, o

también distribución de equilibrio para la cadena de Markov. Para encontrar la distribución de probabilidades de estacionario para una cadena dada cuya matriz de transición es P, según el teorema, para n grande y para toda i ,

(1)

Como Pij (n + 1) = ( renglón i de Pn )(columna j de P), podemos escribir

(2)

Ejemplo: Suponga que toda la industria de refrescos produce dos colas. Cuando una persona ha comprado la cola 1, hay una probabilidad de 90 % de que su siguiente compra se de cola 1. Si una persona compró cola 2, hay un 80 % de probabilidades que su próxima compra sea de cola 2.

Entonces:

12

Al reemplazar la segunda ecuación por la condición

,

obtenemos el sistema

Al despejar resulta que

Por lo tanto, después de largo tiempo, hay

probabilidad 2/3 de que una persona dada compre cola 1 y 1/3 de probabilidad de que una persona compre cola 2.

4.4. Casos especiales (cadenas absorbentes, cadenas cíclicas). Cadenas absorbentes. Una 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: 13

Inge cosmos vende partes de camiones, cuando una empresa compra a Inge cosmos, le dan tres meses para pagar si la cuenta no se salda en ese periodo, Inge cosmos cancela la cuenta y la remite a una cuenta de cobranza, y da por terminada, por tanto ingecosmo clasifica las cuentas nuevas, con un mes de retraso, con dos meses de retraso, tres meses de retraso, pagadas o incobrables, ingecosmos estudio sus antiguos registros y descubrió que. a) El 70% de las cuentas nuevas se pagan en un mes, el 60% de las cuentas con un mes de retraso se pagan al final de mes. b) el 50% de las cuentas con dos meses de retraso se pagan al final del ultimo mes c) el 60% de las cuentas con tres meses de retraso se remiten a una cuenta de cobranzas

1) 2)

Forme Cual

es

la

probabilidad

la de

matriz que

una

nueva

de transición cuenta

se

liquide

3) Cual es la probabilidad de que una cuenta de un mes de retraso se vuelva incobrable 4) Si las ventas de Inge cosmos son en promedio $ 125 000 al mes, cuánto dinero se asentara como deuda incobrable

1) Matriz de transición, los estados son, cuentas nuevas, con 1 me, 2 meses y 3 meses de retraso, cuentas pagadas e incobrables.

2) Para calcular la probabilidad que una nueva cuenta se liquide, debemos seguir los siguientes pasos:

14

1 Encontrar la matriz fundamental X

La matriz I

La matriz (I-N)

Ahora la matriz fundamental es

2do paso es multiplicar la matriz fundamental por la matriz A absorbente

15

Rta// la probabilidad que una nueva cuenta se liquide es de 0,964 3) la probabilidad de que una cuenta de un mes de retraso se vuelva incobrable, también es posible identificarla en la ultima tabla de potabilidades y es de 0,12

4) Debido a que la probabilidad de que una cuenta nueva se vuelva incobrable es de 0,036 . Entonces si multiplicamos $ 125 000 * 0,036 = $ 4 500, tenemos la cantidad que se asentara como incobrable mensualmente , para calcular la cantidad al año multiplicamos $ 4500 * 12 = $ 54 000 y aquí tenemos la cantidad que se asentara como incobrable en el año.

Cadenas cíclicas. La cadena C4, cuya matriz de probabilidades de transición se muestra a continuación, después de un número elevado de transiciones presenta un comportamiento diferente del de las cadenas anteriores. Al ir obteniendo matrices de transición, se observa que estas no convergen a un valor concreto, sino que muestran un comportamiento cíclico. En este caso, las transiciones impares tienden a un valor y las pares a otro. Este tipo de cadenas son cadenas son cadenas cíclicas. En este caso particular, nos encontramos ante una cadena de periodo p=2. La columna es siempre cero, por lo que el estado I no aparecerá en las probabilidades a largo plazo; quiere ello decir que la cadena considerada no es ergódica, aunque es claro que pueden existir cadenas cíclicas ergódicas.

16

También debemos preguntarnos qué ocurre con las probabilidades estacionarias en las cadenas cíclicas, ya que si las sucesivas potencias de P no tienden hacia unos valores determinados. Más adelante, cuando estudiamos el cálculo sistemático de P*.

4.5. Uso de software A.-) PROGRAMAS DE COMPUTACIÓN (Microsoft Adicional al programa SOLVER, incluido

en

EXCEL-2000

de

MIcrosoft

(cuya

explicación

didáctica

del

funcionamiento del programa Solver (445 kb), se incluye en este documento que puede ser bajado por Usted), se incorporan otros programas que operan bajo sistema WIndows 98/ME/2000/XP, debiendo disponer de una computadora actualizada con procesador Pentium II y superiores, memoria mínima de 256 kb y capacidad de disco de 50 MB y los cuales pueden ser bajados a Chang y es aplicable a todos los problemas de Investigación de Operaciones. Para conocer sus usos y aplicaciones, se incorpora el MANUAL DE USO del WINQSB. A.) El programa PrgLin, cuya propiedad es de la Universidad de Lisboa (Portugal), el cual se aplica A.3) El programa Lingo, propiedad de Lindo Systems Inc (USA), que dado su gran tamaño (18.9 Mb),

para soluciones gráficas de problemas de dos dimensiones. A.) El programa InvOp (361 kb), desarrollado por la Universidad del Cuyo en Argentina, se aplica para la solución de problemas relacionados con transporte y redes. Continuación:. A.1) El programa WinQSB (3.9 Mb), cuya propiedad intelectual es del Dr. Yih-Long

B.-) USO DEL PROGRAMA SOLVER DE EXCEL) Para conocer la aplicación del método SOLVER de EXCEL (Microsoft), se utilizará un ejemplo práctico:

17

Max Z=10 X1 + 8 X2 Sujeto

a:

30X1 +20X2