• Author / Uploaded
• jucacepi

Citation preview

PROCESOS DE DECISIÓN MARKOVIANOS Ing. Diana G. Ramírez, MSc. Investigación de Operaciones II Abril de 2013

PROCESOS ESTOCÁSTICOS • Un proceso estocástico (Xt)tT es una familia de variables aleatorias Xt, en donde dichas variables toman valores en un espacio medible, llamado ESPACIO DE ESTADOS, S, para el cual los elementos pertenecientes a S son llamados ESTADOS. El conjunto T se llama ESPACIO DE PARÁMETROS del proceso. • Se dice que X es real si las variables aleatorias Xt son de valor real para cada tT. • Si TN0, entonces X se llama PROCESO CON PARÁMETRO DE TIEMPO DISCRETO. • Si T es un intervalo de la recta real, entonces el proceso X se llama PROCESO CON PARAMETRO DE TIEMPO CONTINUO. • Si TRn con n>1, entonces el proceso X se llama CAMPO ALEATORIO

CADENAS DE MARKOV • Las procesos de Markov son una clase de procesos estocásticos (Xt)tT que cumplen con la propiedad markoviana, es decir, para cada variable aleatoria Xt, se cumple que, PX t 1  j X 0  K 0 , X 1  K1 ,..., X t 1  K t 1 , X t  i  PX t 1  j X t  i • Las cadenas de markov son procesos markovianos con elementos de estado discretos. Esto es lo que estudiaremos en este curso.

PROBLEMA DEL JARDINERO • Cada año, al comenzar la estación para trabajar los jardines (marzoseptiembre) un jardinero usa una prueba química para determinar el estado del suelo. Dependiendo de los resultados de las pruebas, la productividad para la nueva estación cae en uno de los tres estados: – 1) Bueno – 2) Regular – 3) Malo

• A través de los años, el jardinero observó que las condiciones meteorológicas prevalecientes durante el invierno (octubre-febrero) juegan un papel importante en la determinación de la condición del suelo, dejándolo igual o empeorándolo, nunca mejorándolo. • En este respecto, el estado del suelo del año anterior es un factor importante para la productividad del presente año.

PROBLEMA DEL JARDINERO • Las probabilidades de transición durante un periodo de un año, de un estado de productividad a otro, se representa con la siguiente cadena de markov:

• El jardinero puede mejorar esta matriz de transición si, por ejemplo, aplicara fertilizante para mejorar el estado del suelo. La matriz resultante sería:

PROBLEMA DEL JARDINERO • El jardinero asocia una función de ingresos con la transición de un estado a otro. Dependiendo de cada decisión (si usar fertilizante o no) varían así mismo los ingresos, representados por las matrices R1 y R2.

PROBLEMA DEL JARDINERO ¿Qué decisión se debe tomar?... Depende del tipo de problema

• Variante No. 1: Etapas Finitas Supongamos que el jardinero desea jubilarse en N años. El problema del jardinero se expresa como un modelo de programación dinámica de etapas finitas como sigue: m= # de estados en cada etapa (m=3) fn(i)= Ingreso óptimo esperado de las etapas n, n+1,…,N, cuando i es el estado del sistema. La ecuación que relaciona fn con fn+1 es:

En donde, Y el valor esperado por etapa sería:

PROBLEMA DEL JARDINERO La equación recursiva de programación dinámica se escribe de la siguiente forma:

• Ejemplo del Jardinero Supongamos que el jardinero desea jubilarse en 3 años. Valor esperado en un año para k=1 (no usar fertilizante):

Valor esperado en un año para k=2 (usar fertilizante):

PROBLEMA DEL JARDINERO • Ejemplo del Jardinero Para poder resolver la anterior ecuación, dado que es recursiva debemos empezar por el final hasta llegar al principio. Etapa 3:

PROBLEMA DEL JARDINERO • Ejemplo del Jardinero Etapa 2:

PROBLEMA DEL JARDINERO • Ejemplo del Jardinero Etapa 1:

Solución Óptima: Para los años 1 y 2, el jardinero debe aplicar fertilizante (k*=2) y para el año 3 sólo debe aplicarse fertilizante si la tierra está en regulares o peores condiciones (estado 2 y 3, respectivamente.

EJEMPLO DE INVENTARIOS* • Un almacén tiene en bodega un tipo especial de neveras que se pueden ordenar semanalmente. Sea t la demanda respectiva de esta nevera durante la t-ésima semana. Se asume que las t están idénticamente distribuidas con función de distribución independiente del periodo de tiempo, definida por P(t  k )  ak ; k  0,1,2,... • Siendo



ak  0 y  ak  1 k 0

• Una política de inventario consiste entonces en identificar dos valores críticos no negativos c y C. La implementación de la política es como sigue: Si la cantidad de neveras no es mas grande que c, entonces inmediatamente se hace el pedido de neveras hasta completar la cantidad C. Sin embargo, si la cantidad de neveras excede a c, entonces no se hace ningún pedido. Sea Xt la variable aleatoria que representa el número de neveras que se tienen al final de la semana t.

*Tomado de: Llinás, Humberto. Procesos Estocásticos. p.6

SEGUIMOS EL EJEMPLO DE INVENTARIOS… • Entonces (Xt)tT es un proceso estocástico con espacio de estados S= {0,1,…,C-1,C} y con parámetro de tiempo discreto. De acuerdo a las reglas de la política de inventarios, las cantidades de neveras en dos periodos consecutivos están relacionadas por medio de la expresión  max{ 0, C  t 1}, X t  c X t 1   max{ 0, X t  t 1}, c  X t  C

• Para t= 1,2,3,…

SEGUIMOS EL EJEMPLO DE INVENTARIOS… • Tomando el ejemplo de inventarios, el punto de reorden es de 2 y el nivel de reorden es de 5. • Grafique el diagrama de transición • Calcule las probabilidades de transición si suponemos que la demanda sigue una distribución uniforme entre 2 y 6 neveras • Calcule las probabilidades de transición si suponemos que la demanda sigue una distribución de poisson con =3 neveras • ¿Cual es la probabilidad condicional de que al empezar la semana 4 se tengan 3 neveras dado que en la semana anterior se tuvieron 0?

DIAGRAMA DE ESTADOS 1

2

… 0

C

C-1

MATRIZ DE TRANSICIÓN • DISTRIBUCIÓN UNIFORME 0 1 2 3 4 5

0 0,4 0,4 0,4 0,8 0,6 0,4

1 0,2 0,2 0,2 0,2 0,2 0,2

2 0,2 0,2 0,2 0 0,2 0,2

3 0,2 0,2 0,2 0 0 0,2

4

5 0 0 0 0 0 0

0 0 0 0 0 0

MATRIZ DE TRANSICIÓN • DISTRIBUCIÓN POISSON 0 1 2 3 4 5

0 0,185 0,185 0,185 0,577 0,353 0,185

1 0,168 0,168 0,168 0,224 0,224 0,168

2 0,224 0,224 0,224 0,149 0,224 0,224

3 0,224 0,224 0,224 0,050 0,149 0,224

4 0,149 0,149 0,149 0,000 0,050 0,149

5 0,050 0,050 0,050 0,000 0,000 0,050

=+POISSON.DIST(x;3;VERDADERO) : promedio de 3 neveras Valor de la demanda acumulada

Dem(3)=+POISSON.DIST(3;3;VERDADERO)-POISSON.DIST(2;3;VERDADERO)

EJEMPLO DE LAS MÁQUINAS • Un proceso de producción contiene una máquina que se deteriora rápidamente tanto en la calidad como en la cantidad de producción si la carga de trabajo es grande, de manera que se lleva a cabo una inspección periódica, por ejemplo, al final de cada día. En cuanto se inspecciona, se anota la condición de la máquina y se clasifica en uno de los cuatro estados posibles: ESTADO 0 1 2 3

CONDICIÓN Tan buena como nueva Operable: -deterioro menor Operable: -deterioro mayor Inoperable: -productos de calidad inaceptable

• Sea Xt el estado observado de la máquina después de la inspección al final del día t. • Se supone que {Xt} es un proceso de Markov, con una matriz de transferencia j i 0 1 2 3

0

1

0 0 0 0

7/8 3/4 0 0

2

3

1/16 1/16 1/8 1/8 1/2 1/2 0 1

MATRICES DE ORDEN SUPERIOR • Es posible estudiar matrices de orden superior (k>1), a partir de la transformación de las matrices de orden 1. • Dada una cadena de orden k con n estados se puede definir una cadena equivalente de orden 1 de la siguiente forma: • En el que los estados de la cadena de orden 1 se definen como los diferentes conjuntos (ordenados) en los que puede estar la cadena en las k ultimas transacciones. • De esta forma la cadena tiene X=nk estados.

MATRICES DE ORDEN SUPERIOR • Por ejemplo, si hay 3 estados por transición, en la 2da transición visualizamos 32=9 estados Et-1

1 2

1

3 1

2

2 3 1

3

2 3

Et

MATRICES DE ORDEN SUPERIOR • Y no todos las transacciones serán posibles, sólo aquellas que son que para la cadena superior sea coherente con la definición anterior. • Es decir,

POR EJEMPLO…

Esta es una Cadena de Markov de n=3 estados: A, B y C y de orden k=2

POR EJEMPLO… • Cadena de Markov de n=3 estados: A, B y C y de orden k=2 E E E t-2

t

t-1

P{Et=A/Et-1=A} P{Et-1=A/Et-2=A}

A P{Et=B/Et-1=A}

A

B P{Et-1=B/Et-2=A}

B

B P{Et=C/Et-1=A}

P{Et-1=C/Et-2=A}

C C

C

A

POR EJEMPLO… Con base en este árbol de decisión, presentamos la siguiente matriz de transición con orígenes (Et-1, Et-2) y los destinos (Et,Et-1)

En esta tabla se indica el estado Et y la probabilidad correspondiente.

TEOREMA DE CHAPMANKOLMOGOROV • Dado un problema de transición de k pasos, se define la probabilidad de que el proceso se encuentre en el estado j si k etapas antes se encontraba en el estado i, como: • Pero, ¿cómo llegamos a esto? Si al cabo de m matriz con todas las filas iguales • Si no es ergótica: P*=> matriz mas difícil de calcular

• Para todas las cadenas que no tienen clases finales cíclicas, se escribe la siguiente identidad:

CALCULO DE PROBABILIDADES ESTACIONARIAS • Sabiendo que P* cumple la ecuación: • Tenemos,

• Para el ejemplo de C1:

VOLVAMOS AL EJEMPLO: PRONOSTICOS DEL CLIMA

• Calcula P5 y P10. ¿Cuál es el comportamiento de P5 cuando n tiende a infinito? Como se comporta p(n) cuando n • tiende a infinito? Depende el limite de p(0)?

VOLVAMOS AL EJEMPLO DE LAS MÁQUINAS • Estos son todos los estados posibles de la máquina al finalizar el día: ESTADO 0 1 2 3

CONDICIÓN Tan buena como nueva Operable: -deterioro menor Operable: -deterioro mayor Inoperable: -productos de calidad inaceptable

j i 0 1 2 3

0

1

0 0 0 0

7/8 3/4 0 0

2

3

1/16 1/16 1/8 1/8 1/2 1/2 0 1

• ¿En cuántos días se espera que la máquina dure? – ¿qué tipo de Cadena de Markov? – ¿Cuáles son las probabilidades estacionarias? – ¿En cuantos pasos se logra un estado estable? – ¿cuál es el estado estable? – ¿es importante saber desde que día se comienza a contar?