04 CADEIAS DE MARKOV

Prévia do material em texto

Profº Túlio de Almeida 
Pesquisa Operacional II 
 
4. CADEIAS DE MARKOV 
Alocação de um estado sob dados discretos de tempo. Comportamento em cadeia descrito pelo matemático 
russo Andrei Markov. 
 
Um diagrama de estado para um exemplo simples é 
mostrado na figura à esquerda, usando para imaginar as 
transições de estado de um grafo dirigido. Os estados 
representam se um mercado de ações hipotético está 
exibindo um mercado em alta, mercado em baixa, ou 
tendência do mercado estagnado durante uma 
determinada semana. De acordo com a figura, uma 
semana de alta é seguido por uma outra semana de alta 
90% do tempo, de uma semana de baixa 7,5% do tempo, e 
uma semana estagnada outro 2,5% do tempo. 
 Próximo Período 
Mercado em Alta Mercado Estagnado Mercado em Baixa 
P
e
rí
o
d
o
 
A
tu
a
l 
Mercado em Alta 
 
0,90 0,025 0,075 
Mercado Estagnado 
 
0,25 0,50 0,25 
Mercado em Baixa 
 
0,15 0,05 0,80 
 
 
 
4.1. PROCESSOS ESTOCÁSTICOS 
 
4.1.1. O Que É um Processo Estocástico? 
 
 
Um processo estocástico é definido como uma 
coleção de variáveis randômicas Xt indexadas por um 
parâmetro t pertencente a um conjunto T. 
Frequentemente T é tomado para ser conjunto dos 
inteiros não-negativos (porém outros conjuntos são 
perfeitamente possíveis) e X(t) representa uma 
característica mensurável de interesse no tempo t. 
Exemplificando, X(t) pode representar o nível de 
estoque de um produto no fim da semana t. 
Processos estocástico são de interesse para 
descrever o procedimento de um sistema operando 
sobre algum período de tempo, com isso, em termos 
formais, a variável randômica X(t) representa o estado 
do sistema no parâmetro (geralmente tempo) t. 
 
Conclusão: Pode-se afirmar que X(t) é definido em um 
espaço denominado Espaço de Estados. 
 
4.1.2. Tipos de Processos Estocásticos 
Os processos estocásticos podem ser classificados 
como: 
 
Em Relação ao Estado 
 
 Estado Discreto (Cadeia): a variável X(t) é 
definida sobre um conjunto enumerável ou finito. 
 Estado Contínuo (Sequência): X(t) caso 
contrário. 
 
Em Relação ao Tempo 
 
 Tempo Discreto: t é enumerável ou finito. 
Estocástico 
vem de 
estoque? 
 
Profº Túlio de Almeida 
Pesquisa Operacional II 
 
 Tempo Contínuo: t caso contrário. 
 
Exemplos 
 
1. Número de usuários em uma fila de banco em 
um determinado instante. Estado discreto, 
tempo contínuo. 
2. Índice pluviométrico diário. Estado contínuo, 
tempo discreto. 
3. Número de dias chuvosos. Estado e tempo 
discretos. 
 
4.2. CONCEITOS SOBRE CADEIAS DE 
MARKOV 
 
4.2.1. Definição de uma Cadeia de Markov 
Seja Xt, uma variável aleatória que caracteriza o 
estado do sistema em pontos discretos no tempo t = 
1,2, ..., n. A família de variáveis aleatórias {Xt} forma 
um processo estocástico. O número de estados de um 
processo estocástico pode ser finito ou infinito, como 
pode ser observado nos exemplos a seguir: 
Exemplos 
 
A condição de uma máquina na ocasião de uma 
manutenção preventiva mensal é caracterizada como 
ruim, razoável ou boa. Para o mês t, o processo 
estocástico para esta situação pode ser representado 
como: 
 
,...2,1t,
boafor condição a se 2,
razoávelfor condição a se 1,
ruimfor condição a se ,0
X t 











 
 
A variável aleatória Xt é finita porque representa três 
estados: ruim (0), razoável (1) e bom (2). 
 
Serviços chegam a uma oficina mecânica à taxa de 5 
por hora. O processo de chagada segue uma 
distribuição de Poisson que, teoricamente, permite 
que qualquer número de serviços entre zero e infinito 
cheguem à oficina durante o intervalo de tempo (0,t). 
O processo de estado no limite que descreve o 
número de serviços que chegam é 
 
Xt = 0, 1, 2, ..., t > 0 
 
4.2.2. Processos de Markov 
Um processo estocástico é um processo de Markov se 
a ocorrência de estado futuro depender somente do 
estado precedente. Isso significa que, dados os 
tempos cronológicos t0, t1, t2, ... , tn, diz-se que a 
família de variáveis aleatórias {Xtn} = {x1, x2, ..., xn} é 
um processo de Markov se possuir a seguinte 
propriedade: 
 
 
}xX|xX{P}xX,...,xX|xX{P 1ntnt0t1ntnt 1nn01nn   
 
 
Em um processo markoviano com n estados 
(resultados) exaustivos e mutuamente exclusivos, as 
probabilidades em um ponto no tempo t = 0, 1, 2, ... 
são habitualmente expressas por: 
 
 
T ..., 2, 1, 0, tn; ..., 3, 2, 1, j)i,(};iX|jX{Pp 1ttij  
 
 
 
Isso é conhecido como probabilidade de transição em 
uma etapa do estado i em t-1 para estado j em t. Por 
definição: 
 
 
j
ij n ..., 3, 2, 1,i ;1p
 
n ..., 3, 2, 1,j),i(;0pij 
 
 
4.2.3. Probabilidades de Transição 
Um modo conveniente de resumir as probabilidades 
de transição em uma etapa é a notação matricial. 















nn3n2n1n
n2232221
n1131211
p...ppp
p...ppp
p...ppp
P

 
A matriz P define a denominada Cadeia de Markov. 
Uma propriedade desta matriz é que todas as 
probabilidades de transição pij são fixas 
(estacionárias) e independentes ao longo do tempo. 
Exemplo 
 
Todo ano no início da estação de plantio de mudas 
(março e setembro), um jardineiro usa um teste 
químico para verificar a condição do solo. 
Dependendo do resultado do teste, a produtividade 
para a nova estação cai em um de três estados: 
1. Bom 
2. Razoável 
3. Ruim 
Profº Túlio de Almeida 
Pesquisa Operacional II 
 
Ao longo dos anos, o jardineiro observou que a 
condição do solo no ano anterior causava um impacto 
sobre a produtividade do ano corrente e que a 
situação podia ser descrita pela seguinte cadeia de 
Markov: 
 
321
 
P = 










100
5,05,00
3,05,02,0
3
2
1
 
 
As probabilidades de transição mostram que a 
condição do solo pode se deteriorar ou se manter, 
mas nunca melhorar. Se a condição do solo neste ano 
for boa (estado 1) , há 20% de chance de não mudar 
no ano seguinte, 50% de chance de se tornar razoável 
(estado 2) e 30% de chance de deteriorar até uma 
condição ruim (estado 3). 
Se a condição do solo neste ano for razoável (estado 
2), a produtividade no ano seguinte pode permanecer 
razoável com probabilidade de 0,50 ou tornar-se ruim 
(estado 3), também com probabilidade de 0,50. Por 
fim, uma condição ruim neste ano (estado 3) só pode 
resultar em igual condição no próximo ano 
(probabilidade igual a 1). 
O jardineiro pode alterar as probabilidades de 
transição P utilizando fertilizante para melhorar a 
condição do solo. Nesse caso, a matriz de transição 
se torna: 
 
321
 
P = 










55,040,005,0
30,060,010,0
10,060,030,0
3
2
1
 
Agora a utilização do fertilizante permite melhorias nas 
condições de deterioração. Há 10% de chance de a 
condição do solo mudar de razoável para boa (estado 
2 para estado 1), 5% de chance de mudar de ruim 
para boa (estado 3 para estado1) e 40% de chance de 
mudar de ruim para razoável (estado 3 para estado 2). 
4.2.4. Probabilidades de Transição em n Etapas e 
Absolutas 
Dadas as probabilidades iniciais a
0
 = {aj
(0)
} de iniciar 
no estado j e a matriz de transição P de uma cadeia 
de Markov, as propriedades absolutas a
n
 = {aj
(n)
} de 
estar no estado j após n transições (n>0) são 
calculadas da seguinte maneira: 
a
(1)
 = a
(0)
P 
a
(2)
 =a
(1)
P = a
(0)
PP = a
(0)
P² 
a
(3)
 = a
(2)
P = a
(0)
P²P = a
(0)
P³ 
 Continuando sob a mesma ótica, tem-se que: 
n)0()n( Paa 
 
onde a matriz P é conhecida como matriz de transição 
em n etapas. Por esses cálculos pode-se observar 
que: 
PPP 1nn 
 
ou 
 
mmnn PPP 
 para 0 < m < n 
 
Observação: Tais equações são conhecidas como 
equações de Chapman-Kologomorov. 
 
Exemplo 
 
Voltando ao exemplo do jardineiro. Após a aplicação 
do fertilizante, obtem-se a seguinte matriz de 
transição: 
 
321
 
P = 










55,040,005,0
30,060,010,0
10,060,030,0
3
2
1
 
Sendo a condição atual do solo boa (estado 1), ou 
seja, a
(0)
 = (1, 0, 0), determine as probabilidades 
absolutas dos três estados do sistema após 1, 8 e 16 
estações de plantio. 
P² = 










4275,04900,00825,0
3550,05400,01050,0
2650,05800,01550,0
 
P
4
 = 










37857,052193,009950,0
37129,052645,010226,0
36026,053295,010679,0
 
ano atual 
ano seguinte 
Profº Túlio de Almeida 
Pesquisa Operacional II 
 
P
8
 = 










372863,0525384,0101669,0
372863,0525435,0101702,0
372733,0525514,0101753,0
 
P
16
 = 










372881,0524540,0101659,0
372881,0524540,0101659,0
372881,0524540,0101659,0
 
Desta forma, tem-se que: 
 10,060,030,0a
55,040,005,0
30,060,010,0
10,060,030,0
)001(a
)1(
)1(












 
 372733,0525514,0101753,0a
372863,0525384,0101669,0
372863,0525435,0101702,0
372733,0525514,0101753,0
)001(a
)8(
)8(












 372881,0524540,0101659,0a
372881,0524540,0101659,0
372881,0524540,0101659,0
372881,0524540,0101659,0
)001(a
)16(
)16(












 
Ou também, pode-se fazer da seguinte maneira: 
 10,060,030,0a
55,040,005,0
30,060,010,0
10,060,030,0
)001(a
)1(
)1(












 
 265,0580,0155,0a
55,040,005,0
30,060,010,0
10,060,030,0
)10,060,030,0(a
)2(
)2(












 
 33525,054700,011775,0a
55,040,005,0
30,060,010,0
10,060,030,0
)265,0580,0155,0(a
)3(
)3(












 
Observação: Repare que para períodos distantes do 
atual, como por exemplo a
(16)
, é mais eficaz calcular o 
produto das matrizes, enquanto para períodos mais 
próximos do período atual é mais viável utilizar a 
segunda propriedade. 
 
4.3. CLASSIFICAÇÃO DOS ESTADOS EM UMA 
CADEIA DE MARKOV 
 
4.3.1. Estados Absorventes 
 
Um estado j é absorvente se retornar para ele mesmo, 
com certeza, em uma transição, isto é, pij = 1. 
 
4.3.2. Estados Transientes 
 
Um estado j é transiente se puder alcançar outro 
estado mas não puder voltar ao mesmo estado em 
que estava com base em outro estado. 
Matematicamente, isso acontecerá se: 
 
0plim )n(ij
n


 para todo i. 
 
Exemplo 
 
Considerando a Cadeia de Markov do jardineiro sem o 
fertilizante. 
 
321
 










100
5,05,00
3,05,02,0
3
2
1
 
Os estados 1 e 2 são transientes porque alcançam o 
estado 3 mas nunca podem voltar ao estado anterior. 
O estado 3 é absorvente porque p33 = 1. Essas 
classificações também podem ser vistas quando 
0plim )n(ij
n


 é calculado. 
Por exemplo, 
 











100
100
100
P )100(
 
 
o que mostra que no longo prazo, a probabilidade de 
alguma vez voltar ao estado transiente 1 ou 2 é zero, 
ao passo que a probabilidade de ser capturado no 
estado absorvente 3 é certa. 
 
4.3.3. Estados Recorrentes 
 
Profº Túlio de Almeida 
Pesquisa Operacional II 
 
Um estado j é recorrente se a probabilidade de voltar 
ao estado em que estava com base em outros estados 
for 1. Isso pode acontecer se, e somente se, o estado 
não for transiente. 
 
4.3.4. Estados Periódicos 
Um estado j é periódico com período t > 1 se o retorno 
só for possível em t, 2t, 3t, ... etapas. Isso significa que 
pij
(n)
 = 0 sempre que n não for divisível por t. 
 
Exemplo 
 
Pode-se testar a periodicidade de um estado 
calculando P
n
 e observando os valores de pij
(n)
 para n 
= 1, 2, 3, ... . Esses valores serão positivos somente 
no período correspondente do estado. Por exemplo na 
cadeia: 
 











04,06,0
010
4,06,00
P
 
tem-se que 






















0856,0144,0
010
096,0904,00
P.
024,076,00
010
076,024,0
P 32
 






















09654,00346,0
010
2304,09770,00
P.
0576,09424,00
010
09424,00576,0
P 54
 
 
4.4. BIBLIOGRAFIA E REFERÊNCIAS 
[1] TAHA, Hamdy. Pesquisa Operacional. 8ª Edição. 
São Paulo: Pearson Prentice Hall, 2008. 
[2] HILLIER, Frederick S. & LIEBERMAN, Gerald J. 
Introduction to Operations Research. 7th Edition. 
McGraw Hill. 2001. 
[3] NOGUEIRA, Fernando. Cadeias de Markov. 
Disciplina: Modelagem e Simulação. Notas de Aula.