• Author / Uploaded
• Francisco Chediak

Citation preview

Cadenas de Markov

Capítulo 6 Cadenas de Markov

p11

. . .

p1j

. . .

p1n

pi1 . . .

. . .

pij . . .

. . .

pin . . .

pmj . . .

pmn

. . .

P=

pm1 . . .

. . .

. . .

Andrei Andreivich Markov fué un matemático ruso (1856 - 1922) que postuló el principio de que existen ciertos procesos estocásticos cuyo futuro depende, únicamente, de su presente y es independiente de su pasado; estos, reciben el nombre de cadenas de Markov.

Introducción Existen algunos procesos que evolucionan en el tiempo de una manera probabilística. Estos procesos se llaman procesos estocásticos. Si el proceso tiene la propiedad particular de que las probabilidades que describen la forma en que el proceso evolucionará en el futuro, dependen sólo del estado actual en que se encuentra el proceso y, por lo tanto, son independientes de los eventos ocurridos en el pasado, se le llama cadena de Markov o proceso con la propiedad Markoviana. Dicho de otra manera, la propiedad Markoviana establece que la probabilidad condicional de cualquier evento futuro, dado cualquier evento pasado y el estado actual, es independiente del evento pasado y y sólo depende del estado actual del proceso. Descripción del problema Las cadenas de Markov se usan para describir un proceso físico o económico que tenga las siguientes propiedades: 1. El número de sucesos es finito. 2. La probabilidad del siguiente suceso depende solamente del suceso inmediatamente anterior. 3. Estas probabilidades permanecen constantes en el tiempo. Francisco Chediak

267

Cadenas de Markov Sea si = al i-ésimo estado de un total de m estados posibles, donde 2 ≤ m ≤ ∞; m = número de estados posibles. n = Número de pasos o incrementos; n = 0 , el suceso presente; n = 1, el suceso siguiente; n = 2, el suceso en una ocasión, después del siguiente. Ejemplo 6.1 Formulación de un proceso como una cadena de Markov. Los fabricantes de automóviles tienen los siguientes datos con respecto a las compras de los clientes:

Compra actual Suceso n = 0

Siguiente compra Suceso n = 1 % de compra Ford S1

% de compra Chevrolet S2

% de compra Mazda S3

S1: Ford

40

30

30

S2: Chevrolet

20

50

30

S3: Mazda

25

25

50

Aquí, los estados son: S1 = El cliente tiene un automóvil marca Ford S2 = El cliente tiene un automóvil marca Chevrolet S3 = El cliente tiene un automóvil marca Mazda Los sucesos son: n = 0 , La compra actual n = 1 , La siguiente compra El 40% de los clientes que actualmente tienen un Ford, en la siguiente compra adquieren un Ford (Son los clientes fieles a la marca Ford). El 30% de los clientes que ahora tienen un Ford, en la siguiente compra adquieren un Chevrolet. El 30% de los clientes que ahora tienen un Ford, en la siguiente compra adquieren un Mazda. 268

Flaminio Vera

Cadenas de Markov Fíjese que en la primera fila están el 100% de los clientes, que ahora tienen un Ford. Lo mismo ocurre para cada una de las dos siguientes filas. Con ésta información establecemos la matriz de transición P

P=

S1

S2

S3

S1

0,40

0,30

0,30

S2

0,20

0,50

0,30

S3

0,25

0,25

0,50

p13 = 0,30 = Probabilidad de que un cliente, que posee ahora un Ford (S1 , n = 0), pueda comprar un Mazda, en la siguiente ocasión (S3 , n = 1). p13 = 0,30 = Probabilidad de comprar un Mazda, siendo que en la anterior compra se adquirió un Ford. Fíjese que ésta última aseveración corresponde a la definición de la probabilidad condicional de dos eventos A y B. Por todo lo anterior, podemos concluir que una matriz de transición debe cumplir con las siguientes condiciones: 1. Cada elemento pij debe ser una probabilidad, o sea, que debe tener un valor entre 0 y 1: 0 < pij < 1 n

2. Cada fila debe sumar exactamente 1; Σ pij = 1 ; i = 1,2, . . . , m j=1

P=

S1

Sj

Sn

S1

p11

p1j

p1n

Si

pi1

pij

pin

Sm

pm1

pmj

pmn

Cada fila es un vector de probabilidad Vi y debe cumplir las mismas condiciones de la matriz de transición. Ejemplo: V2 = [0,20 0,50 0,30]. Luego: La matriz de transición P está compuesta por vectores de probabilidad Vi. Ahora, empleando los datos del ejemplo, se muestra una de las bondades de las cadenas de Markov, frente al uso normal de la estadística. Francisco Chediak

269

Cadenas de Markov La matriz de transición puede usarse para determinar la probabilidad de un estado, después de n sucesos. Si se quiere determinar la probabilidad de que un cliente que acaba de comprar un Ford, compre un Chevrolet en la ocasión después de la siguiente, podemos abordar el problema desde el enfoque estadístico, pero, también podemos hallar la solución mediante la cadena de Markov, con mejor rendimiento del proceso y además, obtendremos más información que empleando el enfoque estadístico. Análisis según las técnicas de la teoría clásica de la probabilidad. Compra presente n=0

0,40

Comprar Ford

0,30

0,30

Compra siguiente n=1

Comprar Ford

Compra en la ocasión después de la siguiente n=2 0,40 Ford 0,30 Chevrolet (0,4)(0,3) = 0,120 0,30 Mazda

0,20 Ford Comprar Chevrolet 0,50 Chevrolet (0,3)(0,5) = 0,150 0,30 Mazda

Comprar Mazda

0,25 Ford 0,25 Chevrolet (0,3)(0,25) = 0,075 0,50 Mazda 0,345

Respuesta: La probabilidad de que el propietario de un Ford ahora (S1 , n = 0) compre un Chevrolet después de la siguiente ocasión (S2 , n = 2) es de 0,345 Análisis facilitado por las cadenas de Markov: Significado del vector de probabilidad Vi: Para el estado S1 V1 = [0,4 0,3 0,3] Si el estado presente es S1, la probabilidad de que en el siguiente suceso esté en el estado S1, es p11 = 0,4 Si el estado presente es S1, la probabilidad de que en la siguiente compra esté en el estado S2, es p12 = 0,3 Si el estado presente es S1, la probabilidad de que en la siguiente compra esté en el estado S3, es p13 = 0,3 270

Flaminio Vera

Cadenas de Markov Vni = Vector de probabilidad que describe las probabilidades de los posibles estados en n pasos, si el estado presente es Si V21 = Este vector da la probabilidad de todas las posibles compras en 2 pasos, ya que el cliente posee ahora un Ford (n = 0 , S1) Fíjese que ésta información se obtiene a partir del producto: V11 P 0,4 V21 = V11 P = [0,4 0,3 0,3] 0,2 0,25

0,3 0,5 0,25

0,3 0,3 = [0,295 0,345 0,360] 0,5

n=2 Fíjese que: V21 = [0,295 0,345 0,360] Ford

Ford

Mazda Chevrolet

Interpretaciones: Si ahora tengo un Ford, la probabilidad de comprar un Ford, en la ocasión después de la siguiente es de 0,295 (fidelidad a la marca). Si ahora tengo un Ford, la probabilidad de comprar un Chevrolet, en la ocasión después de la siguiente es de 0,345. Si ahora tengo un Ford, la probabilidad de comprar un Mazda, en la ocasión después de la siguiente es de 0,360. Conclusión: Las cadenas de Markov facilitan una técnica para formular y analizar un caso especial de problema de probabilidad. Si el estado presente es poseer un Mazda (S3 , n = 0). ¿Cuál es la probabilidad de repetirlo, en cada una de las respectivas etapas: n = 1 y n = 2 ? V31 = [0,25 0,25 0,5] 0,40 0,30 0,30

V32 = V31 P = [0,25 0,25 0,50] 0,20 0,50 0,30

= [0,275 0,325 0,4]

0,25 0,25 0,50

Francisco Chediak

271

Cadenas de Markov Si ahora se tiene un Mazda (S3 , n = 0), la probabilidad de comprar un Mazda en la siguiente compra es 0.5 (S3 , n = 1), y en la segunda compra, es de 0,4 (S3 , n = 2). Según lo anterior V0i = (pi1 . . . pii . . . pim) y pii = 1 , lo que quiere decir que en el tiempo n = 0, se conoce, exáctamente, cual es el estado; dicho de otra forma, si ahora tengo un Mazda, la probabilidad de que ahora tenga un Mazda es uno (1 = La certeza). V0i = 1 V1i = V0i P = P V2i = V1i P = V0i P P = V0i P2 = P2 V3i = V2i P = V1i P P = V1i P2 = P3 V4i = V3i P = V2i P P = V1i P P P =V1i P3 = P4

Empleando la inducción matemática

. . . . . . Vni = V1i Pn-1 = Pn

Si el cliente es dueño ahora de un Chevrolet. ¿Cuáles son las probabilidades asociadas con su cuarta compra? V42 = V12 P3 0,40 0,30 0,30 0,20 0,50 0,30 0,25 0,25 0,50

P3 =

0,40 0,30 0,30 0,20 0,50 0,30 0,25 0,25 0,50

P3 =

0,295 0,345 0,360 0,255 0,385 0,360 0,275 0,325 0,400

P3 =

0,277 0,351 0,372 0,269 0,359 0,372 0,275 0,345 0,380

V42 = [0,2 0,5 0,3]

0,40 0,30 0,30 0,20 0,50 0,30 0,25 0,25 0,50

0,277 0,351 0,372 0,269 0,359 0,372 0,275 0,345 0,380

V42 = [0,2724 0,3532 272

0,40 0,30 0,30 0,20 0,50 0,30 0,25 0,25 0,50

0,3744] Flaminio Vera

Cadenas de Markov Solución: p21 = 0,2724 = Probabilidad de adquirir un Ford en la cuarta compra, siendo que ahora tiene un Chevrolet. p22 = 0,3532 = Probabilidad de adquirir un Chevrolet en la cuarta compra, siendo que ahora tiene un Chevrolet (fidelidad a la marca). p23 = 0,3744 = Probabilidad de adquirir un Mazda en la cuarta compra, siendo que ahora tiene un Chevrolet. Si se quiere una información más completa, entonces se calcula P4 ya que contendrá a V41 , V42 , V43

P4 = P3 P =

P = 4

0,277 0,351 0,372 0,269 0,359 0,372 0,275 0,345 0,380

0,2740 0,3516 0,3777 0,2724 0,3532 0,3744 0,2740 0,3500 0,3700

0,40 0,30 0,30 0,20 0,50 0,30 0,25 0,25 0,50

  

V41 V42 V43

Aquí, ya disponemos de todas las probabilidades relacionadas con la cuarta compra

Cadenas de Markov Ergódicas Es un proceso en el cual es posible avanzar desde un estado hasta cualquier otro estado. No es necesario que esto, sea posible en un sólo paso, pero, debe ser posible para que cualquier estado sea alcanzado, independientemente del estado presente, esto es, puede irse de un estado a otro, a través de otro estado. Ejemplo 6.2 Tufik conduce un automóvil por un sector cuyas calles están trazadas como se indica en la figura. Cada vez que Tufik llega a una esquina puede dar vuelta o seguir derecho con igual probabilidad. Francisco Chediak

273

Cadenas de Markov 7

8

9

Fíjese que Tufik puede ir con su automóvil, desde cualquier esquina hasta cualquier otra esquina, así sea, a través de una esquina intermedia.

4

5

6

Desde la esquina 1 puede ir a la esquina 3, a través de la esquina 2; o a través de las esquinas 4,5 y 6.

1

2

3

Ahora construimos la matriz de transición y observamos la propiedad llamada ergódica. Matriz de Transición

1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9

0 1/2 0 1/2 0 0 0 0 0 1/3 0 1/3 0 1/3 0 0 0 0 0 1/2 0 0 0 1/2 0 0 0 1/3 0 0 0 1/3 0 1/3 0 0 0 1/4 0 1/4 0 1/4 0 1/4 0 0 0 1/3 0 1/3 0 0 0 1/3 0 0 0 1/2 0 0 0 1/2 0 0 0 0 0 1/3 0 1/3 0 1/3 0 0 0 0 0 1/2 0 1/2 0

Tufik puede llegar a cualquier localización (estado), a partir de cualquier localización presente (estado); luego, es una cadena de Markov Ergódica. Cadena de Markov Regular Una cadena regular es una cadena que tiene una matriz de transición P, la cual, para alguna potencia de P, tiene, únicamente, elementos de probabilidad diferentes de cero. Para determinar si una cadena de Markov es regular, se debe elevar, sucesivamente, al cuadrado la matriz de transición hasta que todos los ceros sean eliminados o hasta que se desarrolle un patrón, que demuestre obviamente, que, por lo menos un cero, nunca podra ser eliminado. Ejemplo 6.3 Determine si la siguiente matriz de transición es o no regular.

P=

274

X X 0 X X 0 X X 0 X 0 0 0 X X X 0 X 0 X X X 0 0 0 Flaminio Vera

Cadenas de Markov

P2 =

P4 =

X X 0 X X 0 X X 0 X 0 0 0 X X X 0 X 0 X X X 0 0 0

X X 0 X X 0 X X 0 X 0 0 0 X X X 0 X 0 X X X 0 0 0

X X X X X X X X X X X X X 0 X X X 0 X X X X X X X

X X X X X X X X X X X X X 0 X X X 0 X X X X X X X

=

X X X X X X X X X X X X X 0 X X X 0 X X X X X X X

=

X X X X X X X X X X X X X X X X X X X X X X X X X

Queda demostrado que la matriz de transición dada, es regular.

Resumen:

n

Regular

Cadena de Markov

No Regular

n n

Ergódica Ergódica No Ergódica

Determinación de las condiciones de estado estable La existencia de condiciones de estado estable, en una cadena ergódica regular, puede demostrarse calculando Pn, para diversos valores de n; a medida que aumenta el valor de n, los valores pij tienden hacia un límite fijo y cada vector de probabilidad Vni tiende a hacerse igual para todos los valores de i. En el ejemplo 6.1, se tiene la matriz de transición ergódica y regular que al ser elevada a la potencia 8, da como resultado: 0,40 0,30 0,30 P = 0,20 0,50 0,30 0,25 0,25 0,50 Francisco Chediak

275

Cadenas de Markov P2 =

0,40 0,30 0,30 0,20 0,50 0,30 0,25 0,25 0,50

0,40 0,20 0,25

0,30 0,50 0,25

0,30 0,30 0,50

=

0,295 0,255 0,275

0,345 0,385 0,325

0,36 0,36 0,40

P3 =

0,40 0,30 0,30 0,20 0,50 0,30 0,25 0,25 0,50

0,295 0,255 0,275

0,345 0,385 0,325

0,36 0,36 0,40

=

0,277 0,269 0,275

0,351 0,359 0,345

0,372 0,372 0,380

P4 =

0,40 0,30 0,30 0,20 0,50 0,30 0,25 0,25 0,50

0,277 0,269 0,275

0,351 0,359 0,345

0,372 0,372 0,380

=

0,2740 0,2724 0,2740

0,3516 0,3532 0,3500

0,3744 0,3744 0,3760

P5 =

0,40 0,30 0,30 0,20 0,50 0,30 0,25 0,25 0,50

0,2740 0,2724 0,2740

0,3516 0,3532 0,3500

0,3744 0,3744 0,3760

=

0,27352 0,27320 0,27360

0,35160 0,35192 0,35120

0,37488 0,37488 0,37520

P6 =

0,40 0,30 0,30 0,20 0,50 0,30 0,25 0,25 0,50

0,27352 0,27320 0,27360

0,35160 0,35192 0,35120

0,37488 0,37488 0,37520

=

0,273448 0,273384 0,273480

0,351576 0,351640 0,351400

0,374976 0,374976 0,375040

P7 =

0,40 0,30 0,30 0,20 0,50 0,30 0,25 0,25 0,50

0,273448 0,273384 0,273480

0,351576 0,351640 0,351400

0,374976 0,374976 0,375040

=

0,2734384 0,3515664 0,3749952 0,2734256 0,3515792 0,3749952 0,2734480 0,3515440 0,3750080

P8 =

0,40 0,30 0,30 0,20 0,50 0,30 0,25 0,25 0,50

0,2734384 0,3515664 0,3749952 0,2734256 0,3515792 0,3749952 0,2734480 0,3515440 0,3750080

=

0,27343744 0,35156352 0,37499904 0,27343488 0,35156608 0,37499904 0,27344000 0,35155840 0,37500160

Fíjese que los Vni se van volviendo iguales, a medida que n crece V81 = 0,27343744 0,35156352 0,37499904 P8 = V82 = 0,27343488 0,35156608 0,37499904 V83 = 0,27344000 0,35155840 0,37500160 La probabilidad de que un cliente adquiera un Ford, a la larga, es de 0,2734 independiente de qué tipo de vehículo tenga ahora. El 35,15% de la demanda, a la larga, se espera que compre un Chevrolet. El 37,49% de los clientes, a la larga, comprará un Mazda. Esta información es valiosa para la planeación de la producción en las compañías productoras o ensambladoras de estas marcas de vehículos. Éstas probabilidades se denominan: Probabilidades de estado estable. Fíjese lo dispendioso que resulta conseguir las probabilidades del estado estable; por ello, se hace necesario un método más eficiente. Método analítico para obtener las probabilidades de estado estable Para un valor suficientemente grande de n, el vector de probabilidad Vni se hace igual para todas las i, y no cambia para valores grandes de n. 276

Flaminio Vera

Cadenas de Markov Luego en: Vni = Vn-1i P grandes de n

ó

Vn+1i = Vni P

entonces Vni = Vn+1i

para valores

Luego existe un vector V* tal que V* = V*P Ahora, sea vj el j-ésimo elemento del vector de probabilidad V*. Puesto que V* es un vector de probabilidad, debe cumplir que: m

Σv = 1

j=1

j

obteniendo un sistema con m+1 ecuaciones y m variables, de las que se puede eliminar una ecuación, menos la de: m

Σv = 1

j=1

j

que es de estricto cumplimiento. Para nuestro ejemplo de los vehículos, tenemos que: V* = V*P

0,40 0,30 0,30 [v1 v2 v3] 0,20 0,50 0,30 0,25 0,25 0,50

= [v1 v2 v3]

v1 + v2 + v3 = 1

0,4v1 + 0,2v2 + 0,25v3 = v1 0,3v1 + 0,5v2 + 0,25v3 = v2 0,3v1 + 0,3v2 + 0,50v3 = v3 v1 + v2 + v3 = 1

Si en estos resultados, descartamos la tercera ecuación y los ordenamos, obtenemos:

-0,6v1 + 0,2v2 + 0,25v3 = 0 0,3v1 - 0,5v2 + 0,25v3 = 0 v1 + v2 + v3 = 1

Eliminando v1 de las ecuaciones 1 y 2, tenemos: Francisco Chediak

277

Cadenas de Markov 4/5v2 + 17/205v3 = 3/5 - 4/5v2 - 1/20 v3 = -3/10 v1 + v2 + v 3 =

v2 =

3/5 -3/10

17/20 -1/20

4/5 -4/5

17/20 -1/20

=

1

-3/100 + 51/200 -1/25 + 17/25

=

9/40 16/25

= 45/128

v2 = 0,3515625

v3 =

4/5 3/5 -4/5 -3/10 4/5 -4/5

17/20 -1/20

=

-6/25 + 12/25 -1/25 + 17/25

=

6/25 16/25

= 3/8 = 0,375

v1 = 1 - 45/128 - 3/8 = 35/128 = 0,2734375 Interpretación: A la larga, el 27,34% de los clientes comprarán un Ford. A la larga, el 35,15% de los clientes comprarán un Chevrolet. A la larga, el 37,50% de los clientes comprarán un Mazda. Cadenas de Markov absorbentes Se usan para describir procesos o sistemas que cesan o por lo menos, vuelven a comenzar, después de alcanzar determinadas condiciones. Ejemplos 1. Después de hallar un número predeterminado de partes aceptables o defectuosas, se suspende una inspección secuencial. 2. Después de n horas de funcionamiento, se detiene una máquina para repararla o remplazarla. Un ESTADO ABSORBENTE es aquel que tiene una probabilidad igual a cero, de ser abandonado, es decir, que una vez alcanzado es imposible dejarlo, y el proceso, o se detiene completamente o se detiene para luego comenzar, a partir de algún otro estado. 278

Flaminio Vera

Cadenas de Markov UNA CADENA DE MARKOV es ABSORBENTE si tiene por lo menos un estado absorbente y es posible ir, desde cada estado no absorbente hasta por lo menos, un estado absorbente. No es necesario efectuar una transición en un paso, ni es necesario tener la posibilidad de alcanzar cada estado absorbente, a partir de cualquier estado no absorbente. Ejemplo 6.4 En una compañía se inspecciona el producto terminado de acuerdo a la siguiente política: Se selecciona e inspecciona artículo por artículo hasta hallar uno defectuoso, o hasta encontrar cinco artículos buenos. Se espera que el 90% de las partes sea aceptable. Si el primer artículo inspeccionado está defectuoso, se suspende la inspección y se rechaza el lote de producción; si el artículo está bueno, se procede a seleccionar el segundo artículo. Si el segundo artículo inspeccionado está defectuoso, se suspende la inspección y se rechaza el lote de producción; si el artículo está bueno, se procede a seleccionar el tercer artículo. Si el tercer artículo inspeccionado está defectuoso, se suspende la inspección y se rechaza el lote de producción; si el artículo está bueno, se procede a seleccionar el cuarto artículo. Si el cuarto artículo inspeccionado está defectuoso, se suspende la inspección y se rechaza el lote de producción; si el artículo está bueno, se procede a seleccionar el quinto artículo. Si el quinto artículo inspeccionado está defectuoso, se suspende la inspección y se rechaza el lote de producción; si el artículo está bueno, se acepta el lote de producción y el proceso de inspección termina o se empieza uno nuevo, para otro lote de producción. Los posibles estados son: S1(0,0) = Empieza el proceso de selección, no hay todavía una unidad de producto ni buena ni mala. S2(1,0) = El primer artículo inspeccionado es bueno. S3(2,0) = El segundo artículo inspeccionado es bueno. S4(3,0) = El tercer artículo inspeccionado es bueno. S5(4,0) = El cuarto artículo inspeccionado es bueno. S6(5,0) = El quinto artículo inspeccionado es bueno. Aquí, se termina el proceso de inspección. S7(0,1) = El primer artículo inspeccionado es defectuoso, el lote se rechaza y el proceso de inspección termina. Francisco Chediak

279

Cadenas de Markov S8(1,1) = El segundo artículo inspeccionado es defectuoso, siendo que el primero fué aceptado. El proceso de inspección se termina y el lote es rechazado. S9(2,1) = Los dos primeros artículos fueron inspeccionados y aceptados; el tercer artículo inspeccionado es rechazado. El proceso de inspección se detiene y el lote es rechazado. S10(3,1) = A probados los tres primeros artículos, el cuarto artículo es inspeccionado y rechazado; luego, el proceso de inspección termina y el lote es rechazado. S11(4,1) = Aprobados los cuatro primeros artículos inspeccionados, el quinto artículo es rechazado y el proceso de inspección termina y el lote es rechazado. Fíjese que los estados S6 a S11 son estados absorbentes, ya que una vez que se está en ellos, el proceso de inspección termina. La anterior información se presenta en la siguiente tabla: Descripción física Estados

Unidades buenas

Unidades malas

Observación

S1(0,0)

0

0

Al empezar

S2(1,0)

1

0

S3(2,0)

2

0

S4(3,0)

3

0

S5(4,0)

4

0

S6(5,0)

5

0

Absorbente

S7(0,1)

0

1

Absorbente

S8(1,1)

1

1

Absorbente

S9(2,1)

2

1

Absorbente

S10(3,1)

3

1

Absorbente

S11(4,1)

4

1

Absorbente

Ahora, construimos la matriz de transición. Fíjese que si está en S1 , sólo puede ir a los estados S2 y S7 en un paso. Inspecciona el primer artículo y saldrá bueno (S2) o malo (S7). Sabiendo que la probabilidad de que un artículo salga bueno es 0,9 y de que salga malo es 0,1, entonces ir de S1 a S2, tiene una probabilidad de 0,9; e ir de S1 a S7, tiene una probabilidad de 0,1 280

Flaminio Vera

Cadenas de Markov De forma similar, se procede para los demás estados. S1 S2 S3 S4 S5 S6 S7 S8 S9 S10 S11 (0,0) (1,0) (2,0) (3,0) (4,0) (5,0) (0,1) (1,1) (2,1) (3,1) (4,1) S1 (0,0) S2 (1,0) S3 (2,0) S4 (3,0) S5 (4,0) S6 (5,0) S7 (0,1) S8 (1,1) S9 (2,1) S10 (3,1) S11 (4,1)

0,9 0,1 0,9 0,1 0,9 0,1 0,9 0,1 0,9 0,1 1 1 1 1 1 1

Reordenamos los elementos de la matriz, colocando primero, los estados absorbentes, tanto en las filas como en las columnas y obtenemos submatrices con relaciones entre estados absorbentes y no absorbentes, bien interesantes. Matriz de transición revisada S6 S7 S8 S9 S10 S11 S1 S2 S3 S4 S5 (5,0) (0,1) (1,1) (2,1) (3,1) (4,1) (0,0) (1,0) (2,0) (3,0) (4,0)

I S6 (5,0) S7 (0,1) S8 (1,1) S9 (2,1) S10 (3,1) S11 (4,1) S1 (0,0) S2 (1,0) S3 (2,0) S4 (3,0) S5 (4,0)

O

1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0.1 0 0 0 0 0 0.9 0 0 0 0 0 0.1 0 0 0 0 0 0.9 0 0 0 0 0 0.1 0 0 0 0 0 0.9 0 0 0 0 0 0.1 0 0 0 0 0 0.9 0.9 0 0 0 0 0.1 0 0 0 0 0

A

N

La submatriz I es una matriz identidad y muestra la relación entre los estados absorbentes. Una vez se entra a un estado absorbente, la probabilidad de permanecer en él, es 1. Francisco Chediak

281

Cadenas de Markov La submatriz O es una matriz nula y muestra que no hay relación alguna entre los estados absorbentes y los estados no absorbentes. La probabilidad de salir de un estado absorbente hacia un estado no absorbente, es cero. La submatriz A muestra la relación entre los estados no absorbentes y los estados absorbentes. Indica, la probabilidad de ir de un estado no absorbente a un estado absorbente, en un solo paso. Muestra la probabilidad de terminar el proceso en un sólo paso, si ahora nos encontramos en un estado no absorbente. La submatriz N proporciona la probabilidad de ir a un estado no absorbente, desde un estado no absorbente, en un solo paso. Con la anterior información, podemos calcular: 1) El número de pasos esperados antes de que el proceso sea absorbido. 2) El número esperado de veces que el proceso está en cualquier estado dado no absorbente y 3) La probabilidad de absorción por cualquier estado absorbente dado. 1) El número de pasos esperados antes de que el proceso sea absorbido es: (I - N)-1 , siendo I la matriz identidad de N, luego debe tener su misma dimensión.

1 0 0 0 0 0 0,9 0 0 0 0 1 0 0 0 0 0 0,9 0 0 I - N = 0 0 1 0 0 - 0 0 0 0,9 0 0 0 0 1 0 0 0 0 0 0,9 0 0 0 0 1 0 0 0 0 0 1 -0,9 0 0 0 0 1 -0,9 0 0 I - N = 0 0 1 -0,9 0 0 0 0 1 -0,9 0 0 0 0 1 1 -0,9 0 0 0 1 0 0 0 0 0 1 -0,9 0 0 0 1 0 0 0 0 0 1 -0,9 0 0 0 1 0 0 0 0 0 1 -0,9 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 1 -0,9 0 0 0 1 0 0 0 0 0 1 -0,9 0 0 0 1 0 0 0 0 0 1 -0,9 0 0 0 1 0 0 0 0 0 1 -0,9 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1

282

Flaminio Vera

Cadenas de Markov 1 -0,9 0 0 0 1 0 0 0 0 0 1 -0,9 0 0 0 1 0 0 0 0 0 1 -0,9 0 0 0 1 0 0 0 0 0 1 -0,9 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1

1 0 -0,81 0 0 1 0,9 0 0 0 0 1 -0,9 0 0 0 1 0 0 0 0 0 1 -0,9 0 0 0 1 0 0 0 0 0 1 -0,9 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1

1 0 0 -0,729 0 1 0,9 0,81 0 0 0 1 0 -0,81 0 0 1 0,9 0 0 0 0 1 -0,9 0 0 0 1 0 0 0 0 0 1 -0,9 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1

1 0 0 0 -0,6561 1 0,9 0,81 0,729 0 0 1 0 0 -0,729 0 1 0,9 0,81 0 0 0 1 0 -0,81 0 0 1 0,9 0 0 0 0 1 -0,9 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0,9 0,81 0,729 0,6561 0 1 0 0 0 0 1 0,9 0,81 0,729 0 0 1 0 0 0 0 1 0,9 0,81 0 0 0 1 0 0 0 0 1 0,9 0 0 0 0 1 0 0 0 0 1

(I - N)-1 =

Estado inicial

1 0,9 0,81 0,729 0,6561 0 1 0,9 0,81 0,729 0 0 1 0,9 0,81 0 0 0 1 0,9 0 0 0 0 1

(0,9)

(0,81)(0,9)

(0,729)(0,81)(0,9)

(0,6561)(0,729) (0,81)(0,9)

Para Si = Σaij ; i = 1,2, . . , m

Número de pasos esperados antes de la absorción

S1

1 + 0,9 + 0,81 + 0,729 + 0,6561 = 4,0951

S2

0 + 1 + 0,9 + 0,81 + 0,729 = 3,439

S3

0 + 0 + 1 + 0,9 + 0,81 = 2,71

S4

0 + 0 + 0 + 1 + 0,9 = 1,9

S5

0+0+0+0+1=1

Francisco Chediak

283

Cadenas de Markov Interpretación Si ahora estamos en el estado S1, el número de pasos esperados para la absorción es 4,0951 Si ahora estamos en el estado S2, el número esperado de piezas a inspeccionar antes de acabar la inspección es 3,439 Si hemos sacado dos artículos y ambos están buenos, el número esperado de piezas a inspeccionar antes de terminar la inspección es 2,71 Si ahora estamos en S4 el número de pasos esperado antes de la absorción es 1,9 Si ahora tenemos cuatro piezas buenas inspeccionadas, el número esperado de artículos a inspeccionar, antes de aceptar o rechazar el lote, es de una pieza. Aquí es trivial el resultado, pues la quinta pieza saldrá buena o mala; en tal caso, se acepta o rechaza el lote. En ambos casos, se termina la inspección.

2) El número esperado de veces que el proceso está en cualquier estado dado no absorbente es: S1 S1 S2 [I - N]-1 = S3 S4 S5

S2

S3

S4

S5

1 0,9 0,81 0,729 0,6561 0 1 0,9 0,81 0,729 0 0 1 0,9 0,81 0 0 0 1 0,9 0 0 0 0 1

Interpretación Si el proceso está ahora en S1: El número de veces esperado en este estado es 1 El número de veces esperado en el estado S2 es 0,9 El número de veces esperado en el estado S3 es 0,81 El número de veces esperado en el estado S4 es 0,729 El número de veces esperado en el estado S5 es 0,6561 Si el proceso está ahora en S2: El número de veces esperado en el estado S1 es cero, por lo tanto, no se puede regresar del estado S2 al estado S1 El número de veces esperado en el estado S2 es 1 El número de veces esperado en el estado S3 es 0,9 El número de veces esperado en el estado S4 es 0,81 El número de veces esperado en el estado S5 es 0,729 284

Flaminio Vera

Cadenas de Markov De igual manera se interpreta para los estados S3 , S4 y S5

3) La probabilidad de absorción por cualquier estado absorbente es: Probabilidad = (I - N)-1 A 1 0,9 0,81 0,729 0,6561 0 0,1 0 0 0 0 0 1 0,9 0,81 0,729 0 0 0,1 0 0 0 0 0 1 0,9 0,81 0 0 0 0,1 0 0 0 0 0 1 0,9 0 0 0 0 0,1 0 0 0 0 0 1 0.9 0 0 0 0 0,1

S1 S2 S3 S4 S5

S6

S7

S8

S9

0,59049 0,6561 0,729 0,81 0,9

0,1 0 0 0 0

0,09 0,1 0 0 0

0,081 0,09 0,1 0 0

S10

S11

0,0729 0,06561 0,081 0,0729 0,09 0,081 0,1 0,09 0 0,1

Si ahora estamos en S1(0,0) , la probabilidad de ser absorbido por el estado S6(5,0) es 0,59049. La probabilidad de aceptar el lote es 0,59049 La probabilidad de que el lote sea rechazado es 1 - 0,59049 = 0,40951. También se puede calcular este valor sumando las probabilidades de ser absorbido por los estados de rechazo del lote (S7 , S8 , S9 , S10 y S11), siendo que ahora estamos empezando el proceso de inspección (S1): 0,1 + 0,09 + 0,081 + 0,0729 + 0,06561 = 0,40951 Si ahora estamos en el estado S5 (4,0), la probabilidad de ser absorbidos por el estado S6(5,0) es 0,9 que es la probabilidad de que una pieza sea aceptada. De igual manera se interpretan los demás elementos probabilísticos de la matriz (I - N)-1A

Ejemplo 6.5 Un taller de maquinaria que produce 100 piezas y cuyo diagrama de flujo de producción con sus probabilidades es: Francisco Chediak

285

Cadenas de Markov Entrada de la piesa en bruto S1

p18 = 0,10

Máquina A p21 = 0,05

p12 = 0,90

S2

p28= 0,05

Inspección A p23 = 0,90

S3

p38 = 0,03

Máquina B p43 = 0,04

p34 = 0,97

S4

S5

p58 = 0,02

Máquina C p65 = 0,03

p56 = 0,98

Desechos

p48 = 0,04

Inspección B p45 = 0,92

S8

S6

p68 = 0,03

Inspección C p67 = 0,94 Empaque y transporte

S7

Fíjese que cada sitio posible en donde podemos encontrar la pieza de producción, se define como un estado. También se registra la probabilidad de ir de un estado i-ésimo a un estado j-ésimo. Fíjese que todos los estados posibles son considerados; por ello, la suma de las probabilidades de las flechas que salen de un estado es 1. Ahora consideraremos algunas preguntas para observar la potencialidad y la información valiosa que se puede lograr con las cadenas de Markov. 286

Flaminio Vera

Cadenas de Markov Interpretación de la información Una unidad de producción que entra en la máquina A tiene una probabilidad de salir defectuosa de 0,1 y de salir buena de 0,9. Una unidad de producción que ingresa a la inspección A tiene una probabilidad de 0,05 de ser considerada inservible; de ser buena, del 0,9; y de ser apta para ser reprocesada del 0,05 1) ¿Qué fracción esperada de partes comenzadas son completadas? Descripción de los posibles estados: S1 = La unidad de producción se encuentra en la máquina A S2 = La unidad de producción se encuentra en la inspección A S3 = La unidad de producción se encuentra en la máquina B S4 = La unidad de producción se encuentra en la inspección B S5 = La unidad de producción se encuentra en la máquina C S6 = La unidad de producción se encuentra en la inspección C S7 = La unidad de producción se encuentra en la sección de empaque y transporte S8 = La unidad de producción se encuentra en la sección de desechos. S1

Matriz de transición

S1 S2 S3 S4 S5 S6 S7 S8

S2

S3

S4

S5

S6

S7

S8

0 0,9 0 0 0 0 0 0,1 0,05 0 0,9 0 0 0 0 0,05 0 0 0 0,97 0 0 0 0,03 0 0 0,04 0 0,92 0 0 0,04 0 0 0 0 0 0,98 0 0,02 0 0 0 0 0,03 0 0,94 0,03 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1

Fíjese que los estados S7 y S8 son absorbentes. Una vez la unidad de producción se encuentre en uno de ellos, su proceso de producción ha terminado. Observe que son excluyentes. S7

Matriz de transición transformada

S7 S8 S1 S2 S3 S4 S5 S6

Francisco Chediak

S8

S1

S2

S3

S4

I

O

A

N

S5

S6

1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0,1 0 0,90 0 0 0 0 0 0,05 0,05 0 0,90 0 0 0 0 0,03 0 0 0 0,97 0 0 0 0,04 0 0 0,04 0 0,92 0 0 0,02 0 0 0 0 0 0,98 0.94 0,03 0 0 0 0 0,03 0 287

Cadenas de Markov

I-N =

1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1

I-N =

0 0,9 0 0 0 0 0,05 0 0,9 0 0 0 0 0 0 0,97 0 0 0 0 0,04 0 0,92 0 0 0 0 0 0 0,98 0 0 0 0 0,03 0

1 -0,9 0 0 0 0 -0,05 1 -0,9 0 0 0 0 0 1 -0,97 0 0 0 0 -0,04 1 -0,92 0 0 0 0 0 1 -0,98 0 0 0 0 -0,03 1

Empleando el Excel y un formato de dos cifras decimales, calculamos la inversa: 1,05 0,94 0,88 0,86 0,81 0,80 0,05 1,05 0,98 0,95 0,90 0,88 0 0 1,04 1,01 0,96 0,94 0 0 0,04 1,04 0,99 0,97 0 0 0 0 1,03 1,01 0 0 0 0 0,03 1,03

(I - N)-1 =

S7 S8

(I - N)-1A =

(I - N)-1A =

288

S1 S2 S3 S4 S5 S6

S1 S2 S3 S4 S5 S6

1,05 0,94 0,88 0,86 0,81 0,80 0 0,05 1,05 0,98 0,95 0,90 0,88 0 0 0 1,04 1,01 0,96 0,94 0 0 0 0,04 1,04 0,99 0,97 0 0 0 0 0 1,03 1,01 0 0 0 0 0 0,03 1,03 0,94

S7

0,1 0,05 0,03 0,04 0,02 0,03

S8

0,75 0,25 0,83 0,17 0,88 0,12 0,91 0,09 0,95 0,05 0,97 0,03

Flaminio Vera

Cadenas de Markov De 100 unidades de producción que empiezan el proceso, 75 terminan en empaque y transporte. 2) ¿Cuántas unidades de producción deben ingresar al taller para que se empaquen y transporten 100 unidades?

100/0,75 = 133,33 = 134 unidades del producto deben empezar el proceso para asegurar que para empaque y transporte lleguen 100 unidades de producto terminado.

3) Dados los datos sobre tiempos estimados por operación, ¿Cuáles son los requerimientos esperados de horas hombre en cada sitio?

Operación

Tiempo estimado para cada operación (en horas - hombre)

Máquina A

3,00

Máquina B

2,50

Máquina C

1,50

Inspección (cada una)

0,25

Empaque y transporte

0,10

Como los datos de la primera fila de la matriz (I - N)-1 representan el número esperado de veces que se encuentra una unidad de producción en cada centro de trabajo, entonces, las horas-hombre totales, son el producto de las horashombre por cada operación por el número de veces que se espera que una pieza esté en cada lugar de trabajo. S1

(I - N)-1 =

Francisco Chediak

S1 S2 S3 S4 S5 S6

S2

S3

S4

S5

S6

1,05 0,94 0,88 0,86 0,81 0,80 0,05 1,05 0,98 0,95 0,90 0,88 0 0 1,04 1,01 0,96 0,94 0 0 0,04 1,04 0,99 0,97 0 0 0 0 1,03 1,01 0 0 0 0 0,03 1,03

289

Cadenas de Markov Operación Máquina A Inspección A Máquina B Inspección B Máquina C Inspección C

Horas-Hombre esperadas 3,00x 1,05 = 3,150 0,25x0,94 = 0,235 2,50x0,88 = 2,200 0,25x0,86 = 0,215 1,50x 0,8 1 = 1,215 0,25x0,80 = 0,200 7,215

Requerimientos estimados de Horas-Hombre por cada parte terminada Para obtener la información sobre la base de una parte terminada, se dividen todas las horas-hombre esperadas por la probabilidad de una elaboración satisfactoria. Operación Máquina A Inspección A Máquina B Inspección B Máquina C Inspección C Empaque y Transporte

Horas-Hombre por unidad de producción 3,150/0,75 = 4,200 0,235/0,75 = 0,313 2,200/0,75 = 2,930 0,215/0,75 = 0,286 1,215/0,75 = 1,620 0,200/0,75 = 0,266 = 0,100 9,715

4) Dados los datos sobre costos de mano de obra y de materiales, ¿Cuáles son los costos directos esperados? Operación Máquina A Máquina B Máquina C Inspección (cada una) Empaque y Transporte

Costo por Hora de operación ($) 10 10 12 10 8

El costo de los materiales es de $15 por pieza y el de los residuos, $2 por pieza. 290

Flaminio Vera

Cadenas de Markov Valor esperado del costo directo de una pieza terminada Valor esperado del costo directo = de una pieza terminada

de los Σ Costos de operación + Costo materiales

Valor de - las partes desechables

Costos de Operación

Operación

Costo por Hora ($)

Horas Hombre

Costo total de la operación ($)

10 10 10 10 12 10 8

4,200 0,313 2,930 0,286 1,620 0,266 0,100

42,00 3,13 29,30 2,86 19,44 2,66 0,80

Máquina A Inspección A Máquina B Inspección B Máquina C Inspección C Empaque y Transporte

Total

$100,19

Costo de los Materiales Recuerde que para producir una unidad hay que introducir al sistema 1,33 unidades de producción. $15(1,33) = $19,95 Valor de las partes desechables Si el porcentaje de unidad terminada es 0,75, entonces el porcentaje que va desechos es 1 - 0,75 = 0,25, por consiguiente: $2(1,33)(0,25) = $0,665 Valor esperado del costo directo de una parte terminada Francisco Chediak

=

$100,19 + $19,95 - $0,665 = $119,475

291

Cadenas de Markov Ejemplo 6.6 Una tienda de computadores portátiles tiene en el almacén un modelo especial que se puede ordenar cada semana (pedir al proveedor). La demanda es una variable aleatoria independiente que sigue una distribución Poisson con media 1 (µ = 1). La tienda usa la siguiente política para ordenar: Si el nivel del inventario, al final de la semana, es 0 ó 1 , se piden 2 computadores; de otra manera, no se ordena. Si los costos de mantener en inventario 3,2,1,0 computadores es de $10, $8, $5 y $0, respectivamente: a) Encuentre las probabilidades de estado estable para los estados de ésta cadena de Markov. b) Encuentre el costo de almacenamiento esperado, a la larga, por semana. Solución a) I0



Semana 1

I1



Semana 2

I2



Semana 3





D1 ≈ P(1)

D2 ≈ P(1)

I3



....



D3 ≈ P(1)

Di = Demanda de la semana i - ésima ; Ii = Inventario final de la semana i ésima Posibles estados del inventario al final de cada semana: S1 = No hay computadores portátiles en inventario. S2 = Hay 1 computador portátil en el inventario. S3 = Hay 2 computadores portátiles en el inventario. S4 = Hay 3 computadores portátiles en el inventario. Fíjese que como consecuencia de la política de ordenar, como máximo se encontrarán en el inventrio al finalizar de la semana, 3 computadores portátiles. La matriz de transición tiene la siguiente configuración general.

P=

292

P11 P21 P31 P41

P12 P22 P32 P42

P13 P23 P33 P43

P14 P24 P34 P44

en donde

p =

µne-µ n!

Flaminio Vera

Cadenas de Markov p14 = 0. Probabilidad de que ahora existan cero (0) computadores, en el inventario y a la semana siguiente, hayan tres (3). De acuerdo a la política de pedidos, esto es imposible, ya que si no se tienen computadores ahora, entonces se solicitan dos (2), y no hay ninguna demanda posible para que al final de la semana se termine con tres (3) computadores en el inventario, por eso, la probabilidad es cero (0). p13 = p(D=0) = 10e-1/0! = 0.368. Si ahora no hay computadores, de acuerdo a la política de pedidos, se ordenarán dos (2) computadores; luego, si la semana se termina con dos (2) computadores en el inventario, es porque la demanda fue cero (0). p12 = p(D=1) = 11e-1/1! = e-1 = 0,368. Si al final de la presente semana, no hay computadores en el inventario, de acuerdo a la política de la empresa, se piden dos (2). Para que al final de la siguiente semana, el inventario sea de un (1) computador, la demanda debió ser de un (1) computador (2 - 1 = 1). p11 = p(D>2) = 1 - p(D3) = 1 - p(D2) = 0,264 p41 = p(D>3) = 0,080 p32 = p(D=1) = 0,368 p42 = p(D=2) = 0,184 p33 = p(D=0) = 0,368 p43 = p(D=1) = 0,368 p23 = 0 p44 = p(D=0) = 0,368 Entonces, la matriz de transición es:

S1 S2 S3 S4

S1 0,264 0,368 S2 0,080 0,184 S3 0,264 0,368 S4 0,080 0,184

[v1 v2 v3 v4]

0,368 0 0,368 0,368 0,368 0 0,368 0,368

0,264 0,368 0,368 0 0,080 0,184 0,368 0,368 0,264 0,368 0,368 0 0,080 0,184 0,368 0,368

Francisco Chediak

V*P = V* entonces

= [v1 v2 v3 v4]

293

Cadenas de Markov 0,264v1 + 0,080v2 + 0,264v3 + 0,080v4 = v1 0,368v1 + 0,184v2 + 0,368v3 + 0,184v4 = v2 0,368v1 + 0,368v2 + 0,368v3 + 0,368v4 = v3 0,368v2 + 0,368v4 = v4 v1 + v2 + v3 + v4 = 1 0,368v1 - 0,816v2 + 0,368v3 + 0,184v4 = 0 0,368v1 + 0,368v2 - 0,632v3 + 0,368v4 = 0 0,368v2 - 0,632v4 = 0 v2 + v3 + v4 = 1 v1 + AV = b A-1AV = A-1b IV = A-1b V = A-1b

Eliminando la primera fila y ordenando, el sistema de ecuaciones queda, así: Resolviendo el sistema de ecuaciones de manera matricial, tenemos:

Premultiplicando por A-1, como A-1A = I y como IV = V, entonces:

0,368 -0,816 0,368 0,184 A = 0,368 0,368 -0,632 0,368 0 0,368 0 -0,632 1 1 1 1

Empleando el Excel para calcular la matriz inversa de A y con un formato de 3 cifras decimales, tenemos que:

1,225 1 1,225 0,181 0 0,225 0,,285 = -0,775 A 0 -1 0 0,368 -0,451 0 -1,451 0,166

Ahora, calculando V = A -1b, tenemos:

-1

v1 v2 v3 v4

1,225 = -0,775 0 -0,451

v1 = 0,18 1 v2 = 0,285 v3 = 0,368 v4 = 0,1 66 1,000

1 1,225 0,1 8 1 0 0,225 0,285 -1 0 0,368 0 -1,451 0,1 66

0 0 0 1

=

0,1 81 0,285 0,368 0,166

La probabilidad de terminar la siguiente semana inventario de cero computadores es de 0,181 La probabilidad de terminar la siguiente semana inventario de un computador es de 0,285 La probabilidad de terminar la siguiente semana inventario de dos computadores es de 0,368 La probabilidad de terminar la siguiente semana inventerio de tres computadores es de 0,166

con un con un con un con un

b) El costo de almacenamiento esperado por semana a largo plazo es: (0)(0,181) + (5)(0,285) + (8)(0,368) + (10)(0,166) = $6,029 294

Flaminio Vera

Cadenas de Markov PROBLEMAS PROPUESTOS 6.1

Determinar si la siguiente matriz de transición es ergódica

p=

6.2

X 0 0 X X

X X 0 0 X

X X 0

X 0 X

0 X X

X 0 X 0

0 X 0 X

X 0 X 0

0 X 0 X

Comprobar si la siguiente matriz de transición es una cadena a) Regular, b) Ergódica.

p=

6.5

X X X X 0

Comprobar si la siguiente matriz de transición es una cadena a) Regular, b) Ergódica.

p=

6.4

X 0 X 0 0

Comprobar si la siguiente matriz de transición es una cadena a) Regular, b) Ergódica.

p=

6.3

0 X 0 X 0

0 X X 0

X 0 0 X

X 0 0 X

0 X X 0

Hallar el número esperado de pasos hacia la absorción, para la siguiente matriz de transición: S1 S2 p= S3 S4

0,2 0 0,4 0,4

Francisco Chediak

0,3 1 0 0,2

0,3 0 0,3 0,2

0,2 0 0,3 0,2

Solución: Comenzando en el estado S1, el número de pasos esperados para la absorción es: 5,15306 295

Cadenas de Markov 6.6 Un taller de maquinaria que produce 100 partes y cuya secuencia de pasos de fabricación de cada parte con sus probabilidades respectivas es: Entrada S1

p = 0,1

Maquinado p = 0,05

S4

p = 0,9

Desechos

S2 Inspección p = 0,9

Los estados se definen así:

p = 0,05

S3

S1 = Maquinado S2 = Inspección S3 = Almacén S4 = Desechos

Almacén de producto terminado

a) ¿Qué fracción esperada de partes comenzadas es almacenada como producto terminado? ¿Cuántas partes deben ingresar al taller para que se almacenen 100 unidades como producto terminado? b) Dado los costos estimados por operación. ¿Cuáles son los requerimientos esperados de Horas-Hombre, en cada sitio? Tiempo estimado para cada operación en Horas - Hombre

Operación

6.7

Maquinado

3,00

Inspección

0,25

a) 0,8482 ; 117,896 b) Maquinado: 3,70 H-H Inspección: 0,27 H-H

Se lleva a cabo una encuesta de mercadeo de tres marcas de alimentos para el desayuno, X, Y y Z. Cada vez que el cliente compra un nuevo paquete, puede comprar de la misma marca o cambiar por otra. Se han obtenido los siguientes datos estimados que se expresan como fracciones decimales: Marca recién comprada Marca presente

296

Solución:

X Y Z

X

Y

Z

0,7 0,3 0,3

0,2 0,5 0,3

0,1 0,2 0,4 Flaminio Vera

Cadenas de Markov

Se estima que en este momento el 30% de los clientes compran la marca X; 20%, la marca Y y 50%, la marca Z, siendo éstas las condiciones iniciales: ¿Cuál será la distribución de clientes después de dos (2) periodos de tiempo? Solución: 46.8%, 32% y 21.2%, respectivamente

6.8 En un determinado proceso de producción, cada unidad pasa por dos etapas. Al final de cada etapa, los artículos se desechan (probabilidad de 0,2); se regresan para reprocesarlos (probabilidad de 0.3); o pasan a la etapa siguiente (probabilidad de 0,5). a) Describa el proceso como una cadena de Markov y establezca la matriz de transición. b) ¿Cuál es el número esperado de pasos hacia la absorción? c) Si en un lote se comienzan 100 partes, ¿Cuál es el número esperado de partes buenas que pueden completarse? d) ¿Cuántas horas-hombre esperadas se necesitan en cada sitio si el tiempo estimado para cada operación en Horas-Hombre son: Etapa 1: 3,0 y Etapa 2: 2,5 e) ¿Cuáles son los costos directos esperados por unidad, si los costos por hora de operación son: Etapa 1: $10; Etapa 2: $12; los costos por materia prima por unidad son: $15 y los costos de los residuos por unidad son: $2? Solución: b) 2,45 ; 1,43 c) 51 partes ; d) 8,4 ; 5 ; e) $171,48 6.9

Se está considerando la compra de dos copiadoras de oficina. Son similares en todos los aspectos, excepto, en el control de claro-oscuro que opera en forma automática. En la Maquina A existe una probabilidad de 0,95 de que el control permanezca ajustado todo el dia, si está ajustado en la mañana; pero, si no está ajustado, hay 0,1 de probabilidad de que permanezca así. Para la máquina B, las probabilidades equivalentes son de 0,9 y 0,05, respectivamente. Si el costo es el mismo, ¿Qué máquina se debe comprar? Solución: La máquina que se debe comprar es la A (0,9474)

6.10 Calcular las probabilidades de estado estable para la siguiente matriz de transición: S1 S2 S1 S2 Francisco Chediak

0,7 0,3 0,5 0,5

Solución: 3/8, 5/8 297

Cadenas de Markov 6.11 El departamento de comercialización de la marca X hizo una investigación y encontró que, si un cliente compra su marca, existe una probabilidad de 0,7 de que la compre de nuevo, la próxima vez. Por lo tanto, si la última compra fue de otra marca, entonces, se escoge la marca X sólo con una probabilidad del 0,2. ¿Cuál es el porcentaje de mercado que puede pronosticarse a la larga, para la marca X? Solución: 40% 6.12 Una computadora se inspecciona cada hora y se encuentra, que está trabajando o descompuesta. Si está trabajando, la probabilidad de que siga trabajando la siguiente hora es de 0,9. Si está descompuesta, se toman medidas para repararla, lo que puede llevar más de una hora. Siempre que la computadora está descompuesta independientemente de cuánto tiempo haya pasado, la probabilidad de que siga descompuesta es de 0,35 a) Demuestre que ésta, es una cadena de Markov y encuentre la matriz de transición. b) Encuentre las probabilidades de estado estable e interprételas. Solución: 0,86 ; 0,13 6.13 Un distribuidor de automóviles Volkswagen Golf efectúa el pedido de carros a la ensambladora todos los sábados a la hora del cierre de ventas, de tal suerte que el lunes, antes de empezar las ventas, ya puede disponer de los autos ordenados. La demanda es una variable aleatoria, independiente que tiene una distribución Poisson con media uno (1). El distribuidor tiene la siguiente política para ordenar los autos: Si no hay en el inventario el sábado, a la hora del cierre de ventas, efectúa una orden por tres carros. De lo contrario, si cuenta con vehículos en él, no efectúa el pedido. Si el inventario inicial es de tres carros, a) Diseñe éste proceso como una cadena de Markov y halle las probabilidades de estado estable. b) ¿Cuál es el costo promedio esperado de mantener el inventario por semana, si el distribuidor sabe que el costo de mantener 3 automóviles en inventario es de $18.000; el de mantener 2, es de $8.000; el de mantener 1 es de $2.000 y el de no mantener inventario, es de $0.? Solución: a) 0,286; 0,285; 0,263 y 0,166 b) $5.662,00

298

Flaminio Vera

Cadenas de Markov 6.14 Un proceso de producción incluye una máquina que se deteriora con rapidez por el trabajo pesado, tanto en la calidad como en la cantidad de producción, por lo que se inspecciona al final de cada día. Inmediatamente después de la inspección, se califica la condición de la máquina dentro de cuatro estados posibles:

Estado Condición



0 1 2 3



El proceso se puede modelar como una cadena de Markov con matriz de transición de un paso, como se observa a continuación:

Tan buena como nueva. Operable - Deterioro mínimo. Operable - Deterioro mayor. Inoperable y remplazable por una tan buena como nueva.

Estados 0 1 2 3 0 1 2 3

0 7/8 1/16 1/16 0 3/4 1/8 1/8 0 0 1/2 1/2 0 0 0 1

a) Encuentre la probabilidad de estado estable. b) Si los costos por encontrarse en los estados 0, 1, 2, 3 son: $0, $1.000, $3.000 y $6.000, respectivamente, ¿Cuál es el costo diario esperado con el tiempo? y c) Encuentre el tiempo de recurrencia esperado para el estado 0; esto es, el tiempo esperado de uso de la máquina, antes de tener que remplazarla. Solución: a) 0, 0, 0, 1 ; b) $6.000 ; c) Un (1) día 6.15 Una empresa de refrescos ha contratado a un experto en Investigación de Operaciones para analizar su posición en el mercado. Están preocupados, en especial, por su mayor competidor. El experto piensa que el cambio de marca se puede modelar como una cadena de Markov, definiendo tres estados: El estado A representa los clientes de la empresa de refrescos; el estado B, a los clientes de su mayor competidor y el estado C, a todas las demás marcas. Los datos se toman cada mes y el experto construye la siguiente matriz de transición:

P=

A

B

C

A

0,70

0,20

0,10

B

0,20

0,75

0,05

C

0,10

0,10

0,80

Francisco Chediak

¿Cuáles son los porcentajes de mercado en el estado estable para cada una de las fábricas de refresco? Solución: 34,62% ; 38,46% ; 26,92%

299

Cadenas de Markov 6.16 Los administradores de la empresa Cola-Cola consideran que la probabilidad de que un cliente compre su bebida, o el principal producto de la competencia, Pesi-Cola, se basa en la compra mas reciente del cliente. Suponga que son apropiadas las siguientes probabilidades de transición:

Cola-Cola

Pesi-Cola

Cola-Cola 0,9 0,1 Pesi-Cola 0,1 0,9 a)

Trace un diagrama de árbol de dos periodos para un cliente que compró la última vez Cola-Cola. ¿Cuál es la probabilidad de que éste cliente compre Cola-Cola en una segunda compra?

b)

¿Cuál es la participación en el mercado a largo plazo, para cada uno de estos dos productos?

c)

Se está planeando una campaña importante de publicidad para aumentar la probabilidad de atraer a los clientes de Pesi-Cola. Los administradores consideran que la nueva campaña aumentará la probablilidad de que un cliente cambie de Pesi-Cola a Cola-Cola. en 0,15. ¿Cuál es el efecto de la campaña de publicidad sobre las participaciones en el mercado?



Solución: a) 0,82 ; b) 50% ; 50% ; c) 60% ; 40%

6.17 Una cadena de Markov tiene las siguientes probabilidades de transición: S1 S2 S3 S4 S1 0,5 0,3 0,1 0,1 S2 0,3 0,4 0,1 0,2 S3 0,1 0,2 0,6 0,1 S4 0,1 0,3 0,1 0,5

Encuentre las probabilidades de estado estable.



Solución: 0,2704 ; 0,3111 ; 0,2 ; 0,2185

6.18

La siguiente matriz incluye dos estados absorbentes

S1 S2 S3 S4

a) Cuáles son los estados absorbentes?

S1 0,2 0,4 0,3 0,1 S2 0,1 0,6 0,2 0,1 S3 0 0 1 0 S4 0 0 0 1

b) Para cada estado no absorbente encuentre la probabilidad de terminar en un estado absorbente.

300

Flaminio Vera

Cadenas de Markov

Solución: 5/7 ; 2/7 ; 19/28 ; 9/28

6.19 El contralor de Coruniversitaria analizó las cuentas por cobrar y halló la siguiente matriz de transición: Al mes 2 A

B

Pagadas

Cuentas Morosas

A 0,4 0,1 0,5 0 B 0,1 0,2 0,6 0,1 Del mes 1 Pagadas 0 0 1 0 Cuentas morosas 0 0 0 1 Las cuentas A tienen de 0 a 30 días y actualmente suman un total de $60.000. Las cuentas B tienen de 31 a 90 días, para un total de $40.000, en el momento actual. ¿Qué asignación debe hacer el contralor a las cuentas morosas? Solución: $6.383,00

6.20 Encuentre e interprete las probabilidades de estado estable de la siguiente matriz de transición, empleando el método analítico:



A

B

C

A

0,6

0,2

0,2

B

0,1

0,5

0,4

C

0,2

0,1

0,7

Solución: 11/37 ; 8/37 ; 18/37

Francisco Chediak

301