cadenas de markov.ppt

1

INSTITUTO TECNOLÓGICO DE SAN JUAN DEL RÍO

INVESTIGACIÓN DE OPERACIONES II

CASO La Move – U Rental se especializa en el arrendamiento de camiones a personas que desean realizar sus propias mudanzas. El gerente de distribución de la compañía, esta considerando aplicar un ‘cargo por traslado’ para cubrir el costo de enviar camiones desde las áreas en las que hay sobrantes a otros lugares en los que se necesitan. Antes de decidir si debe aplicar el cargo por traslado al costo del arrendamiento de los camiones que se dirigen a áreas en las que hay sobrantes, desea determinar la proporción del número total de camiones que a largo plazo, acabaran en cada una de las áreas de renta. Si las proporciones son aproximadamente las mismas, el cargo por traslado será innecesario. Si no es así, el cargo dependerá de la proporción del total que termine en cada región.

4

El gerente ha dividido la parte de los estados unidos que atiende la compañía en tres regiones : norte, central y sur, de registro previos se ha determinado que de los camiones que se rentan cada mes en el norte, 20% van a una ciudad del norte, 30% terminan en la región central y 50% se devuelven a la compañía en la región del sur. De manera similar, la compañía ha determinado que , cada mes, 40% de los camiones que se rentan en al región central se devuelven en la misma, 30% se devuelven en el norte y el 30% restante se devuelven en el sur. Por ultimo, de los camiones que se rentan cada mes en la región sur, 20% se devuelven en el norte y 40% se devuelven en la región central. En este momento 40% de los camiones se encuentran en el norte, 30% en la parte central y 30% están en la región sur .

5

Dado el patrón del movimiento de los camiones, la Move – U Company esta interesada en saber lo siguiente. 1.- ¿Qué proporción de los camiones se encontrara en cada región después de un mes? ¿después de dos meses? 2.- ¿Qué proporción de los camiones estará en cada región después de un periodo largo? Análisis del caso Se elabora una tabla como la siguiente para resumir la información referente a la proporción de camiones que tienen una región de origen y llegan a otro destino.

Tabla 1. proporción de camiones que se regresan a cada región

Región Donde se Devuelve

Región donde se renta

Norte Central Sur

Norte 0.2 0.3 0.5

Central 0.3 0.4 0.3

Sur 0.2 0.4 0.4

6

Análisis del caso

En esta tabla la región donde se renta el camión se lista en el extremo izquierdo y la región en donde se devuelve el camión aparece en la parte superior. Por ejemplo, observando el primer renglón de la tabla y la primera columna, puede verse que 20% de los camiones que se rentan en el norte se devuelven en el mismo norte. Otra forma de plantear esta relación , es que existe una probabilidad de 0.2 de que un camión rentado en el norte sea regresado en la misma región.

7

Observar que para cualquier renglón la suma de las probabilidades es uno. Esto significa que un camión rentado debe ir a algún lado. Notar también que la región en la que se regresa un camión depende solo de la región en la que se rento, en otras palabras, el estado final del camión depende de su estado más reciente . Si un camión fue rentado alguna vez en la región central, no afecta el lugar en que se le regrese si ahora se renta en el norte. El hecho de que haya una probabilidad asociada con el lugar en el que se devolverán los camiones y que esta región en la que se devuelven dependa solo de la región en la que se rente significa que esta situación satisface las consideraciones básicas de los procesos de Markov.

8

Una consideración adicional para los problemas de este tipo es que habrá ocurrencias repetidas del evento bajo estudio.

Las principales consideraciones de los procesos de Markov aplicadas al ejemplo es: 1.- Hay incertidumbre con respecto a la región en la que se devolverán los camiones y es posible medir está incertidumbre a través de probabilidades. 2.- La región en la que se devuelven un camión depende solo de la región en la que fue rentado. 3.- Habrá ocurrencias repetidas, o ensayos, es decir, se rentan camiones bajo las mismas circunstancias.

9

Presentación de cadenas de Markov a través de un árbol

En la siguiente se muestra el diagrama de árbol para un camión que se renta en la región norte en el mes 0. los nodos en el árbol son las ubicaciones en los meses 0, 1 y 2 y en las ramas del árbol aparecen las probabilidades de cada transición.

10

Ubicación en el mes 0



Probabilidad de cada ubicación en el mes 2

Norte

Central

Sur

Norte

Central

Sur

Norte

Central

Sur

Norte

Central

Sur

Norte

0.2

0.3

0.5

0.4

0.4

0.2

0.3

0.3

0.4

0.2

0.3

0.5

0.06 ¤

0.04 •

0.10 +

0.09 •

0.12 ¤

0.09 +

0.10 •

0.20 ¤

0.20 +11




Probabilidad de cada ubicación en el mes 2

Norte

Central

Sur

Norte

Central

Sur

Norte

Central

Sur

Norte

Central

Sur

Norte

0.3

0.5

0.2

0.3

0.2

0.4

0.4

0.3

0.4

0.5

0.2

0.3

0.25 ¤

0.15 •

0.10 +

0.08 •

0.06 ¤

0.06 +

0.12 •

0.06 ¤

0.12 +11a

2do ejemplo cambio de probabilidades

Las probabilidades de encontrarse en cada uno de los estados en el mes 2 se calculan multiplicando las probabilidades individuales de transición. Ejemplo,

la probabilidad de estar en el norte en cada uno de los tres meses esta dado por (0.2)(0.2) = 0.04

Para determinar la probabilidad de que un camión se encuentre en el norte después de dos meses, se suman las tres probabilidades de encontrarlo en el norte: Ρ (de estar en el norte en el mes 2 dado que se encontraba en el norte en el mes 0) = 0.04 + 0.09 + 0.10 = 0.23, de manera similar (•)P (de estar en la región central en el mes 2 dado que estaba en el norte en el mes 0) = 0.06 + 0.12 + 0.20 = 0.38, (¤) y P(de estar en el sur en el mes 2 dado que estaba en el norte en el mes 0) = 0.10 + 0.09 + 0.20 = 0.39; (+) 0.23 + 0.38 + 0.39 = 1.0

12

Nota valores del primer ejemplo

Las probabilidades de encontrarse en cada uno de los estados en el mes 2 se calculan multiplicando las probabilidades individuales de transición. Ejemplo,

la probabilidad de estar en el norte en cada uno de los tres meses esta dado por (0.2)(0.2) = 0.04

Para determinar la probabilidad de que un camión se encuentre en el norte después de dos meses, se suman las tres probabilidades de encontrarlo en el norte: Ρ (de estar en el norte en el mes 2 dado que se encontraba en el norte en el mes 0) = 0.15 + 0.08 + 0.12 = 0.35, de manera similar (•)P (de estar en la región central en el mes 2 dado que estaba en el norte en el mes 0) = 0.25 + 0.06 + 0.060 = 0.37, (¤) y P(de estar en el sur en el mes 2 dado que estaba en el norte en el mes 0) = 0.10 + 0.06 + 0.12 = 0.28; (+) 0.35 + 0.37 + 0.28 = 1.0

Valores del segundo ejemplo 12a

Si se utiliza notación de matrices, los cálculos para el mes 1 aparecen de la siguiente manera: N C S N C S 0.2 0.3 0.5 N C S [ 1 0 0 ] 0.3 0.4 0.3 = [ 0.2 0.3 0.5 ] 0.2 0.4 0.4

Para el segundo mes, se repiten los cálculos:

N C S N C S 0.2 0.3 0.5 N C S [ 0.2 0.3 0.5 ] 0.3 0.4 0.3 = [ 0.23 0.38 0.39 ] 0.2 0.4 0.4

Vector de probabilidad para comenzar en el

norte

Matriz de transición de

un mes

Vector de probabilidad

después de un mes

Vector de probabilidad después

de un mes

Matriz de transición de un

mes


después de dos meses

13Valores del primer ejemplo

Si se utiliza notación de matrices, los cálculos para el mes 1 aparecen de la siguiente manera: N C S N C S 0.3 0.5 0.2 N C S [ 1 0 0 ] 0.4 0.3 0.3 = [ 0.3 0.5 0.2 ] 0.4 0.2 0.4

Para el segundo mes, se repiten los cálculos:

N C S N C S 0.3 0.5 0.2 N C S [ 0.3 0.5 0.2 ] 0.4 0.3 0.3 = [ 0.37 0.34 0.29 ] 0.4 0.2 0.4

Vector de probabilidad para comenzar en el

norte

Matriz de transición de

un mes


después de un mes

Vector de probabilidad después

de un mes

Matriz de transición de un

mes



13bValores del segundo ejemplo

Observar que estas series de cálculos pueden combinarse en uno solo de la siguiente manera:

N C S N C S N C S 0.2 0.3 0.5 0.2 0.3 0.5 N C S [ 1 0 0 ] 0.3 0.4 0.3 0.3 0.4 0.3 = [ 0.23 0.38 0.39 ] . 0.2 0.4 0.4 0.2 0.4 0.4


para comenzar en el norte

Matriz de transición de un mes




14Valores del primer ejemplo

El calculo del vector de probabilidad después de dos meses depende del vector de probabilidad en el mes 0 y de la matriz de transición de un mes. En los cálculos anteriores, se utilizo un vector de probabilidad inicial que representaba un camión que había comenzado en el norte. Para calcular la proporción de camiones que se encontraban en cada región después de dos meses, simplemente se sustituye la proporción original de camiones que se encuentran en cada región (40% de los camiones se encuentran en el norte, 30% en la parte central y 30% están en la región sur) y se considera como el vector inicial de probabilidad, es decir [ 0.4 0.3 0.3 ].

15

Los cálculos se convierten en :

N C S N C S N C S 0.3 0.5 0.2 0.3 0.5 0.2 N C S [ 0.4 0.3 0.3 ] 0.4 0.3 0.3 0.4 0.3 0.3 = 0.364 0.3430 0.293 0.4 0.2 0.4 0.4 0.2 0.4

Proporción de

camiones en el mes 0



Proporción de

camiones en el mes 2

16

En estos cálculos, se observa que después de dos meses que 23.6% de todos los camiones se encontraban en el norte, 37.7% estaban en la región central y 38.7% en el sur.

Desarrollo matemático

Puede resumirse el análisis anterior utilizando la notación siguiente:

P i j = probabilidad de cambiar del estado i al estado j en un paso P = matriz formada por los valores Pi j (matriz de transición) S i (t ) = probabilidad de encontrarse en el estado i en el estado j en el periodo t S (t) = vector de probabilidades de estado en el periodo t

17

Por ejemplo :

P11 = 0.2, P23 = 0.3, S1 (0) = 0.4, S (0) = [ 0.4 0.3 0.3 ] Utilizando esta notación, es posible plantear varios resultados clave . En primer lugar, se tiene que la suma de las probabilidades de estado debe ser igual a 1:

S1 (t) + S2 (t) + S3(t) + . . . . Sn (t) = 1 - - - - - - - - Para un caso con n estados De manera similar, para cada renglón de la matriz de transición, P, se tiene la suma:

Pi 1 + Pi2 + Pi3 + . . . . Pin = 1 - - - - - - - 2 para i = 1, 2, 3,. . . . . . . N. recordar que esto implica que debe hacerse alguna transición hacia un estado en cada paso. La transición de un periodo al siguiente se encuentra incluida en la siguiente ecuación:

1

2

18

S ( t + 1) = S (t) P - - - - - - - -

Para el primer periodo, esto se convierte en S (1) = S (0) P - - - - - - -

Y para el segundo periodo se tiene

S (2) = S (1) P = S (0) P² - - - - - - En general, este resultado se convierte en

S (t) = S (0) P⁺ - - - - - - - - Ahora, para la condición de estado estacionario, se tiene

S = S ( t + 1) = S (t) - - - - - - Donde S = vector de probabilidad de estado estacionario, que es el mismo sin importar el periodo. Esto implica que:

S = S P - - - - - - - - - - - -

3

4

5

6

7

8

19

Es decir, el vector de estado estacionario sigue siendo igual después de una transición de una etapa, para el ejemplo expuesto, esto da como resultado:

0.2 0.3 0.5 S = [S1 S2 S3] = [S1 S2 S3] 0.3 0.4 0.3 0.2 0.4 0.4

Terminando los cálculos, se lleva a un sistema de ecuaciones:

S1 = 0.2S1 + 0.3S2 + 0.2S3 - - - - - - - - - -

S2 = 0.3S1 + 0.4S2 + 0.4S3 - - - - - - - - - - -

S3 = 0.5S1 + 0.3S2 + 0.4S3 - - - - - - - - - - -

Se sabe también que la suma de estas probabilidades es igual a 1, por lo que se tiene 1 = S1 + S2 + S3 - - - - - - - - - - -

9 10

11

12

20

Si se resuelven los valores de S1, S2, y S3 utilizando las ecuaciones del 9 al 12 se llega a las probabilidades del estado estacionario:

S1 = 0.238, S2 = 0.376 S3 = 0.386

Dado que se tienen cuatro ecuaciones con tres incógnitas, es posible utilizar dos cualesquiera de las tres primeras ecuaciones, junto con la ultima, para encontrar el valor de las tres incógnitas .

Un detalle que resulta importante tomar en cuenta con respecto a esta condición de estado estacionario es que no depende del estado inicial. Si se comenzara con un vector de proporciones de [ 0.5 0.25 0.25 ] ó uno de [ 0.33 0.33 0.34 ], a largo plazo siempre se terminara con el mismo vector de proporciones de estado estacionario [0.238 0.376 0.386 ].

21

Resumiendo , el desarrollo de las cadenas de Markov, si existe una matriz de transición de una etapa P = [ Pi j ] y un vector de estado para el periodo t1 S (t), entonces se tiene que n

S = SP y ∑ Si = 1 i = 1

Para determinar los valores apropiados de Si que forma S, el vector de equilibrio.

22

Aplicaciones de los procesos de Markov

El Helderberg Junior College es una escuela financiada por el estado que ofrece grados intermedios en un curso de dos años. Los administradores del HJC están interesados en saber cuantos estudiantes se graduarán cada año, cuantos continuaran en la escuela y cuantos renunciaran a ella. Esta información es útil para planear las necesidades futuras de profesores y para obtener fondos del estado. Dado que HJC es una escuela con duración de dos años, los estudiantes que terminan su primer año pueden continuar en la escuela ó pasar a otra (a un estudiante que renuncia se le considera como transferencia).

23

Si los estudiantes continúan en la escuela, pueden asistir a cursos del segundo año ó repetir cursos del primero, los estudiantes que terminan el segundo año escolar se gradúan con un grado intermedio, continúan en la escuela para terminar los requisitos del grado ó bien se transfieren a otra escuela sin terminar los cursos necesarios para obtener el grado intermedio. en cualquier caso, la condición de un estudiante en el siguiente año escolar (el HJC no tiene clases en verano y no acepta transferencias) depende por completo de la condición que tiene este año.

24

Con base en datos anteriores, el jefe de la oficina de inscripciones del HJC ha determinado la proporción de estudiantes que cae en cada categoría, dependiendo de la condición en la que se encontraban el año anterior, esta información se muestra en la siguiente matriz de transición.

Esta matriz de transición es diferente al del problema introductorio del arrendamiento de camiones. Por las siguientes condiciones. En primer lugar, no es posible pasar a todos los demás estados a partir de uno especifico, por ejemplo, un estudiante que alcanza el estado de graduado ó el de transferido no puede a ningún otro estado.

1er año 2do año Graduados Transferencia

1er año 0.1 0.7 0 0.2

2do año 0 0.2 0.6 0.2

Graduados 0 0 1 0

Transferencia 0 0 0 1

25

Por esta razón , estos estados (graduado y transferido) se conocen como estados absorbentes por que una vez que se alcanzan no pueden abandonarse . En una cadena de Markov con estados absorbentes, la pregunta ya no es que proporción del total alcanzará un estado determinado, puesto que del total todos se encontraran en algún momento en uno de dos estados absorbentes. En otras palabras , la condición de estado estacionario contendrá todo en un estado absorbente . Dado esté resultado, la pregunta se convierte entonces en: ¿Qué proporción de los estados originales no absorbentes terminaran en cada uno de los estados absorbentes ? En el ejemplo del HJC la pregunta se convierte en:

26

¿Qué proporción de estudiantes de primer o segundo año se graduarán, y que proporción se transferirán a otra escuela ó la abandonaran? para calcular estas proporciones, es necesario definir primero una matriz especial que se denomina matriz fundamental Q. esta matriz se encuentra por medio del siguiente procedimiento. En el ejemplo del HJC la pregunta se convierte en: ¿Qué proporción de estudiantes de primer o segundo año se graduarán, y que proporción se transferirán a otra escuela ó la abandonaran? para calcular estas proporciones, es necesario definir primero una matriz especial que se denomina matriz fundamental Q. esta matriz se encuentra por medio del siguiente procedimiento.

27

1.- Eliminar los renglones correspondientes a los estados absorbentes originales2.- Dividir la matriz restante en estados absorbentes y no absorbentes. Denominar, G a la parte de la matriz bajo absorbentes, y a la parte bajo estados no absorbentes, H .

3.- Calcular Q = (I – H)‾ ¹ , en donde I = matriz identidad (unos en la diagonal principal, y ceros en las demás posiciones) y el exponente -1 se refiere al inverso de una matriz.

Paso 1.- eliminar los renglones absorbentes

Paso 2.- Dividir los renglones restantes en estados absorbentes y no absorbentes

0 0.2 0.1 0.7 G = H = 0.6 0.2 0 0.2

1er año 2do año Graduados transferencia

1er año 0.1 0.7 0.0 0.2

2do año 0 0.2 0.6 0.2

28

Paso 3.- Calcular Q = (I – H) ⁻ ¹

(1 – 0.1) (0 - 0.7) ⁻ ¹ 0.9 - 0.7 ‾ ¹ 1.111 0.972 Q = = = Q (0 - 0) (1 - 0.2) 0 0.8 0 1.250

Utilizando Q . Puede calcularse la proporción de estudiantes que alcanzarán cada uno de los estados absorbentes, si esta matriz de proporciones se

denota R, en donde r i j = proporción de estudiantes en un estado i que algún momento pasan a un estado j. por tanto

R = QG En nuestro ejemplo

1.111 0.972 0 0.2 Q = y G = 0 1.250 0.6 0.2

29

1.111 0.972 0 0.2 0.583 0.417 R = = 0 1.250 0.6 0.2 0.750 0.250

Los valores que aparecen en la matriz R pueden interpretarse como sigue: r₁₁ = 0.583 = proporción de estudiantes que se encuentran en el primer año y que en algún momento se graduaran r₁₂ = 0.417 = proporción de estudiantes que en su primer año y que se transferirán a alguna otra escuela r₂₁ = 0.750 = proporción de estudiantes que se encuentran en su segundo año y que se graduaran r₂₂ = 0.250 = proporción de estudiantes que se encuentran en un segundo año y que se transferirán

30

Si ahora existen 1000 estudiantes de primer año en el Helderber Junior College y 800 estudiantes de segundo año, es de esperarse que (0.583) (1000) = 583 estudiantes de primer año que en algún momento se graduaran (0.417) (1000) = 417 estudiantes de primer año que se transferirán (0.750) (1000) = 750 estudiantes de segundo año que se graduaran (0.250) (1000) = 250 estudiantes de segundo año que se transferirán Si los administradores del Helderberg Junior College desean que se gradúen en promedio 700 estudiantes, entonces será necesario aumentar el número de alumnos de primer año a (700 ÷ 0.583) = 1201 estudiantes (suponiendo que los nuevos estudiantes que se admiten provengan de la misma población que los estudiantes admitidos antes).

31

Puede interpretarse aun más la matriz fundamental Q utilizando el siguiente resultado: las entradas de la matriz fundamental Q proporcionan el número promedio de periodos que el sistema estará en cada uno de los no absorbentes.

En el caso del Helderberg Junior College esto significa que el estudiante promedio de primer año pasara 1.111 años en el primer año, antes de abandonar la escuela ó pasar al segundo año. De la misma manera, el estudiante promedio de primer año pasara 0.972 de año en el segundo año. También, el estudiante promedio de segundo año no invertirá tiempo en el primer año (tal como era de esperarse), pero invertirá 1.250 años en el segundo año

32

Otro resultado que puede obtenerse Q es que la suma de los renglones da el número promedio de periodos hasta que ocurra la observación en uno de los estados absorbentes . En el caso del Helderberg, esto significa que si un estudiante se encuentra en el primer año, necesitara en promedio 2.083 años para graduarse ó abandonar la escuela (transferirse). Si un estudiante se encuentra en el segundo año, el tiempo promedio para graduarse ó abandonar la escuela es de 1.250 años

33

Tiempos de la primera transición

En el problema anterior (caso de la escuela Helderberg Junior College) se hablo de (cadenas de Markov con y sin estados absorbentes). Otro calculo que con frecuencia resulta interesante es el tiempo promedio que transcurre antes de cambiar de un estado a otro por primera vez. Este tiempo se conoce como tiempo de la primera transición. Por ejemplo, en el caso de la Move – U Truck Rental Company, podría estar interesado en el tiempo promedio que se requeriría para que un camión rentado en el norte llegue a la región central.

34

El camión puede ir a otras regiones y volver al norte antes de pasar a la región central, pero todo lo que interesa de momento es el número promedio de periodos que se requieren en al actualidad para que un camión que se encuentra en la región del norte pase a la región central. para calcular el tiempo promedio de la primera transición del estado i al estado j, en primer lugar se determinara f ij que es el primer tiempo de transición de i a j. entonces se calculara este valor utilizando la formula.

ƒ i j = 1+ ∑ p i k ƒ k j k ≠ j

35

En donde P i j = probabilidad de pasar de i a j

Recordar que la matriz de transición para el caso de la Move – U es

0.2 0.3 0.5 0.3 0.4 0.3 0.2 0.4 0.4

Para hacer el calculo de la primera transición del norte a la región central (i= 1 a j = 2), se tiene la ecuación que sigue:

Ƒ₁₂ = 1 + P₁₂ + P₁₃ ƒ₃₂ ó ƒ₃₂ = 1 + 0.2ƒ₁₂ + 0.4ƒ₃₂

36

Si se resuelven estas dos ecuaciones simultaneas para determinar los valores de ƒ₁₂ y ƒ₃₂ . Se obtiene que en promedio el primer tiempo de transición de la región del norte (estado 1) a la región central (estado 2) es 1.896 meses. También se determina que el primer tiempo de transición de la región del sur (estado 3) a la región central es de 1.034 meses. Con base en esta información, el gerente de distribución de la Move – U Rental Company , puede esperar que un camión que sale de la región del norte requiera en promedio casi dos meses (1.896 meses) para ser entregado en al región central.

37

cadenas de markov.ppt

Documents