Administracion

INSTITUTO TECNOLOGICO DE CIUDAD VICTORIA

DEPARTAMENTO DE INGENIERIA INDUSTRIAL

INVESTIGACION DE OPERACIONES II

UNIDAD 4
CADENAS DE MARKOV

M. C. Flora Alicia González Jiménez
Octubre 2009

Cuando se introduce el tiempo en los problemas de optimización, se pasa de un enfoque estático a uno dinámico, lo cual combinado con la aleatoriedad de las variables de decisión, produce laentrada a los procesos estocásticos. La combinación de los aspectos estocásticos y dinámicos en los problemas de optimización, se revisa a través de los llamados procesos markovianos de decisión.

Andrei Andreivich Markov fue 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 supasado; éstos reciben el nombre de Cadenas de Markov. El proceso de optimización se presenta en un sistema cualquiera, cuando en cada periodo de tiempo se dispone de una serie de alternativas de decisión, cada una con un costo asociado y cuya instrumentación coloca al sistema en otro estado con una determinada distribución de probabilidad. El proceso markoviano de decisión genera las accionesóptimas que minimizan el costo total esperado, en todo el horizonte de tiempo considerado.

Los procesos markovianos de decisión son métodos que se han aplicado para resolver problemas de inventarios, líneas de espera, mantenimiento y reemplazo, entre otros.

Conceptos básicos

Proceso estocástico: es una colección subindizada de variables aleatorias denotadas por Xt, donde el subíndice t pertenecea otro conjunto dado. Se puede visualizar como un salto aleatorio de un estado a otro en periodos consecutivos de tiempo. Para poder estudiar los procesos estocásticos, debe suponerse que poseen la propiedad de Markov, es decir, que el futuro depende únicamente del valor del estado del presente y es independiente del pasado. Matemáticamente, lo anterior se expresa de la siguiente manera:

P{Xt+1 = j | Xo = Ko, X1 = K1, …, X t-1= K t-1, Xt = i} = P {X t+1=j|Xt = i}

Esta expresión establece que la probabilidad condicional de encontrarse en el periodo t+1, en el estado j, depende únicamente del valor del estado en el periodo t y es independiente del pasado (periodos 0, 1, 2, t-2, t-1). La probabilidad condicional calculada a partir de la propiedad de Markov (expresión anterior), seconoce como probabilidad de transición.

Probabilidad p ij: es la probabilidad de que ocurra un cambio del estado i al j; se considera estacionaria porque no cambia con el tiempo. De relajarse esta condición, se tendrían probabilidades de transición dependientes del parámetro tiempo, lo que complicaría el análisis. El cálculo de esta probabilidad se hace mediante la siguiente expresión: p ij = P {Xt+1 = j|X t = i} para toda i, j

Cadena de Markov: se llama así a todo proceso que satisface la propiedad de Markov.

Probabilidad de transición en n periodos: son las probabilidades condicionales asociadas con los cambios de un estado a otro en cierto número de periodos; se identifican con el término p ij (n) y se define como: p ij (n) = P { X t+n = j| X t = i}

Como p ij (n) sonprobabilidades condicionales deben satisfacer: p ij (n) ≥ 0 para toda i, j y n = 0, 1, 2, … y
M
∑p ij (n) = 1 para toda i y n = 0,1,2, …
j=0

donde:

M es el número finito asociado a los diferentes estados por donde puede pasar el proceso.

Puede usarse una matriz para presentar las probabilidades de transición en n periodos; una matriz de transición se denomina doblementeestocástica cuando la sumatoria de todos los valores de probabilidad de i con respecto a un valor de j es igual a 1,
M
∑p ij (n) = 1 para toda j
i=0

Realización del proceso: es cualquier secuencia de valores asociados al proceso estocástico.

Espacio de estados: es el conjunto de todos los posibles valores asociados a un proceso estocástico. Si el espacio de estado contiene valores...