TOS Cap 1 Processos Makovianos

Prévia do material em texto

Técnicas de Simulação e Otimização 
 
1 – Processos Markovianos 
Professor Luciano Barboza da Silva 
Processos Estocásticos 
• Um processo estocástico é definido como uma 
sequência de Variáveis Aleatórias (VA){Xt}, em que o 
índice t pertence um dado conjunto T. 
• OBS: Lembre-se que uma VA é uma função X : Ω →  
que associa cada elemento do espaço amostral Ω a um 
valor real; 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 2 
Processos Estocásticos 
• Ex: Lançamento de 3 moedas. Se X o número de caras. 
Temos: 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 3 
Ω 
ccc 
cck 
kcc 
ckc 
ckk 
kkc 
kck 
kkk 
3)( cccX
      2 cckXckcXkccX
      1 ckkXkckXkkcX
  0kkkX
c – cara 
k - coroa 
Processos Estocásticos 
• Dizemos que um processo {Xt} está associado a dois 
conjuntos: 
 T - Conjunto de Índices: Esse índice estabelece uma simples 
enumeração das variáveis. Pode representar tempo, 
distância,etc. 
 E – Conjunto de Estados: Determina os valores que a VA Xt 
poderá assumir em cada unidade t  T. 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 4 
Processos Estocásticos 
• Assim podemos dizer que um Processo Estocástico é 
uma sequência: X0, X1, X2,...,onde cada Xt assume 
valores em um conjunto de estados E para cada t  T. 
• Exemplo 1: O clima em uma dada cidade pode mudar 
rapidamente de um dia para outro. Vamos representar o 
clima por uma VA Xt com as seguintes características: 
Pesquisa Operacional 2 - Prof. Luciano Barboza da Silva 5 
Processos Estocásticos 
 t indica o dia em que o tempo foi avaliado, contados a partir 
de um dia referencial chamado “0”; 
 Xt uma VA definida como 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 6 




t
t
X t
 dia no momento nenhum em chovido tenhanão caso ,0
 dia no momento algum em chovido tenha,1
Processos Estocásticos 
• Vamos modelar a situação acima como um processo 
estocástico: 
– Conjunto de Índices (T): Representa os dias contados a partir 
do referencial. Assim temos: 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 7 
 ,...3,2,1,0T
Processos Estocásticos 
– Conjunto de Estados (E): Como só é possível (pela nossa 
definição) que tenhamos tempo seco (absolutamente sem 
chuva no dia observado, denotaremos por “0”) ou chuvoso 
(caso haja incidência de chuva em algum momento, 
denotaremos por “1”) podemos definir E como: 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 8 
 1,0E
Processos Estocásticos 
– Assim, por exemplo: 
• [X0 = 1] – Significa que houve chuva no dia referencial; 
• [X1 = 0] – Não houve chuva no primeiro dia de interesse 
observacional; 
– Em geral: 
• [Xt = k] – No dia de observação t ocorreu o estado k. 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 9 
Processos Estocásticos 
– Graficamente poderíamos pensar numa realização do 
processo como uma sequência: {1,0,0,1...}, que graficamente 
seria: 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 10 
0 0 11
T
0X 1
X
2X 3X


Processos Estocásticos 
• Exemplo 2: Uma loja estoca determinado modelo de 
câmera que pode ser encomendada semanalmente. 
Sejam D1, D2, D3 ... VA´s que representam a demanda 
semanal por essa câmera. Suponhamos que as VA´s Dt 
sejam independentes e identicamente distribuídas (IID). 
Seja X0 o números de câmeras disponível no estoque da 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 11 
Processos Estocásticos 
 loja (digamos numa segunda pela manhã), X1, o número de 
câmeras em estoque no final da primeira semana (digamos 
sábado à noite), X2 o número de câmeras em estoque no 
final da segunda semana e assim sucessivamente. 
Suponhamos adicionalmente que X0 = 3, de modo que a 
primeira semana comece com 3 câmeras em estoque e que 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 12 
Processos Estocásticos 
 se estabeleça como estratégia de reposição: 
– Caso no final de uma certa semana, digamos t, o estoque 
esteja zerado, sou seja, se Xt = 0, solicita-se 3 unidades ao 
fornecedor do produto que repõe 3 unidades imediatamente; 
– Caso no final de uma certa semana, digamos t, o estoque 
esteja positivo, ou seja, Xt > 0, nada é solicitado. 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 13 
Processos Estocásticos 
 Vamos modelar esse processo com os elementos que 
definimos: 
– Processo: O processo a ser modelado é a evolução do estoque, 
aqui representado por Xt; 
– T : O conjunto de índices representa a semana observada, de 
modo que Xt representa o número de câmeras no final da semana 
t. Assim T = {0,1,2,3,...}; 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 14 
Processos Estocásticos 
 OBS: Note que o estoque no final da semana t é 
exatamente igual ao estoque inicial da semana t +1 (no 
caso de reposição podemos considerar que o estoque é 
reposto ainda na semana t). Nesse caso faz sentido 
afirmarmos que X0 corresponde ao estoque inicial da 
semana 1. 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 15 
Processos Estocásticos 
– Conjunto de Estados (E): Vamos agora determinar E: 
• Em primeiro lugar note que os elementos de E são números 
inteiros não-negativos ( E  N ). Como Xt assume valores em E, 
sabemos que Xt é uma VA discreta; 
• Assim o valor mínimo que podemos ter em E é “0”, que identifica 
um estoque vazio; 
 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 16 
Processos Estocásticos 
• A dinâmica do modelo pode ser representada da seguinte forma: 
 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 17 
tX
1tX
1tD
Semana t 
Processos Estocásticos 
– Xt é o estoque no início da semana t+1. 
• Se Xt > 0, então teremos Xt+1 = Xt – Dt+1; 
• Se Xt = 0, então pela estratégia de reposição solicita-se 3 unidades 
do produto ao fornecedor, que entrega imediatamente de modo que 
passamos a ter Xt = 3. Logo Xt+1 = 3 – Dt+1; 
• Além disso lembramos que Xt é quantidade e portanto não pode ser 
negativa. 
 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 18 
Processos Estocásticos 
– Dessa forma definimos nosso processo como: 
 
 
 OBS: Vale lembrar que a regra de reposição vale a qualquer 
instante. Assim se Xt+1 = 0 aplica-se a estratégia de modo que no 
início da semana t + 2 tenhamos Xt+1 = 3. Assim nosso processo 
assumirá valor máximo de 3. 
 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 19 









0 se ]0;max[
0 se ]0;3max[
1
1
1
ttt
tt
t
XDX
XD
X
Processos Estocásticos 
– Assim temos todos os elementos do modelo que estudamos 
até agora: 
 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 20 
 
 3,2,1,0 :(discreto) Estados de Cojunto 
;3,2,1,0 :semanas) (em Tempo de Índice 
..2,1,0 semana da final no estoque em câmeras de Nº 



EE
TT
tX t

Processos Estocásticos 
 OBS: O conjunto de índices T pode ser discreto ou contínuo. No 
primeiro caso chamamos o processo de Processo em Tempo 
Discreto. No outro caso de Processo em Tempo Contínuo (nesse 
curso estudaremos apenas o primeiro); 
 OBS: Os estados também podem assumir valores discretos, ou 
contínuos. Se discretos podem ser estados finitos ou infinitos. 
(nesse curso estudaremos apenas o caso discreto finito) 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 21 
Cadeias de Markov 
• Para estudar analiticamente processos estocásticos, é 
necessáriofazer suposições sobre seus elementos. Um 
tipo bastante útil de processo são as Cadeias de Markov. 
• Modelos baseados nas ideias das cadeias de markov são 
bastante comuns na análise de processos envolvendo 
incerteza. 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 22 
Cadeias de Markov 
• Suposições do Modelo 
– Conjunto de Índices (T) discreto, vamos inclusive supor T  
N (o fato de termos T discreto justifica chamarmos esse 
modelo de Cadeia, conforme vimos anteriormente); 
– Conjunto de Estados (E) discreto, em geral E  Z; 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 23 
Cadeias de Markov 
– Propriedade Markoviana. 
• Esta é uma propriedade técnica. Afirma que a probabilidade de um 
processo assumir determinado estado (digamos j  E), em 
determinado momento (digamos t  T) depende apenas do estado 
que o mesmo assumiu no tempo t – 1  T, e não da trajetória 
seguida pelo processo até t – 1. Simbolicamente: 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 24 
    EjiiiiXjXPiXiXiXjXP tttot   ,,,,|,,,| 1011110 
Cadeias de Markov 
 OBS: Chamamos as probabilidades condicionais P(Xt = j | Xt-1 = i) 
de Probabilidades de Transição. Elas medem a probabilidade 
de a cadeia sair do estado i e chegar ao estado j e uma única etapa 
(unidade de tempo) ; 
 OBS: Vamos supor no nosso modelo que as probabilidades de 
transição independem do instante em que o processo se encontra, 
ou ainda: 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 25 
     iXjXPiXjXPiXjXP tttt   01211 ||| 
Cadeias de Markov 
 Note que neste caso, as probabilidades dependem apenas dos 
estados i e j. Dizemos que esse tipo de Cadeia de Estacionária. 
 OBS: Podemos, adicionalmente, medir transições em mais de 
uma etapa, por exemplo: P(X2 = j | X0 = i). 
 Em geral P(Xt+n = j | Xt = i) = P(Xn = j | X0 = i), é chamada 
Probabilidade de Transição em n etapas. 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 26 
Cadeias de Markov 
 OBS: Vamos utilizar a seguinte notação: 
 
 
 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 27 
 
   iXjXPp
iXjXPp
tt
n
ij
ttij




1
1
|
|
Cadeias de Markov 
 OBS: Suponhamos agora uma Cadeia com conjunto de 
estados E = {0,1,2...,M}. Em todos os momentos a cadeia 
estará em algum estado de i  E e migrará para algum estado 
j  E ( j podendo ser igual a i , ou seja, a cadeia permanece 
no estado em que estava no instante anterior) . Assim: 
 
 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 28 
   


M
k
n
ij
n
ij pp
0
10
Cadeias de Markov 
 OBS: Uma notação que nos ajudará muito é a Matriz de Probabilidades 
de Transição (ou simplesmente Matriz de Transição). Nessa matriz 
resumimos todas as probabilidades relevantes para compreendermos as 
transições do modelo. Para um modelo com E = {0,1,2,...,M} temos: 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 29 













MMMM
M
M
ppp
ppp
ppp
M 




10
11110
00100
1
0
P
0 1

M
Cadeias de Markov 
 Exemplo: Retornando ao exemplo 1 (Modelo do Clima). Como 
vimos o índice de tempo para esse modelo, T, identifica os dias e o 
conjunto de estados , E, identifica a classificação do dia: chuvoso (0) 
ou seco (1) (E = { 0,1 }). Suponha agora que tenhamos as seguintes 
informações adicionais: 
– A probabilidade de termos tempo seco amanhã são ligeiramente maiores, se o 
tempo hoje for seco do que se o tempo hoje for chuvoso; 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 30 
Cadeias de Markov 
– Particularmente: a probabilidade de termos tempo seco amanhã, caso 
hoje seja um dia seco, é de 0,8; 
– A probabilidade de termos tempo seco amanhã, caso hoje seja um dia 
chuvoso é de 0,6. 
• Modelo: 
– Processo: Xt – Indica a classificação do dia quanto a manifestação do 
clima no dia t; 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 31 
Cadeias de Markov 
– Índice de Tempo T = { 0,1,2,3... }: Indica um dia de observação 
(por simplicidade vamos supor que o dia de observação inicie as 
00:00h e encerre as 23:59h). Vamos imaginar adicionalmente que 
o processo é observado as 23:59h de cada dia ; 
– Estados E = { 0,1 }: Descreve o tipo, ou a classificação, do dia 
quanto ao seu clima: “0” para tempo seco e “1” para tempo 
chuvoso; 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 32 
Cadeias de Markov 
– Probabilidade de Transição: Pelo problema sabemos que: 
• A probabilidade de termos tempo seco amanhã (digamos em t + 1) caso 
hoje (digamos t) seja um dia seco é de 0,8. Simbolicamente: 
 
• Conseqüentemente a probabilidade de que amanhã tenhamos tempo 
chuvoso, dado que hoje tivemos tempo seco é 0,2. Simbolicamente 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 33 
  8,00|0100   tt XXPp
  2,00|1101   tt XXPp
Cadeias de Markov 
• A probabilidade de termos tempo seco amanhã (digamos em t + 1) caso 
hoje (digamos t) seja um dia chuvoso é de 0,6. Simbolicamente: 
 
 
• Conseqüentemente a probabilidade de que amanhã tenhamos tempo 
chuvoso, dado que hoje tivemos tempo chuvoso é 0,4. Simbolicamente 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 34 
  6,01|0110   tt XXPp
  4,01|1111   tt XXPp
Cadeias de Markov 
– Assim temos a seguinte matriz de transição: 
 
 
 
 OBS: A matriz P(n) de uma única etapa é denotada por P; 
 OBS: Como o processo é homogêneo as probabilidades de transição 
independem dos tempos em que as transições ocorrem. Dependem apenas dos 
estados envolvidos: 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 35 







4,06,0
2,08,0
1
0
P
0 1
   iXjXPiXjXPp ttij   011 ||
Cadeias de Markov 
 OBS: Note as propriedades das probabilidades de transição: as 
probabilidades são não negativas e as linhas somam 1. Simbolicamente: 
 
 
 OBS: As probabilidades da diagonal principal da matriz de transição (no 
nosso exemplo p00 e p11 ) são chamadas de probabilidade de 
permanência pois medem a probabilidade da cadeia não modificar o seu 
estado de um instante para o seguinte. 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 36 
  
1
0 100
1,0110
j iiij
M
j ijij
ippppp
Cadeias de Markov 
 OBS: Em modelos pequenos como esse, uma representação gráfica, 
chamada Diagrama de Transição pode ser bastante útil : 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 37 
0 1
2,001 p
6,010 p
4,011 p8,000 p
OBS: O sentido das setas indicam 
o sentido da transição. 
Cadeias de Markov 
 Exemplo 3: Ao final de cada dia o preço de uma ação é 
registrado. Se hoje o preço subiu a probabilidade de que 
subirá amanhã é de 0,7. Se, por outro lado o preço caiu 
hoje, amanhã subirá com apenas 0,5 de probabilidade. 
Para fins de simplificação, classificaremos a situação do 
preço da ação permanecer constante como queda. 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 38 
Cadeias de Markov 
• Modelo: 
– Processo: Xt indica se o preço da ação fechou em queda ou 
em alta; 
– T = { 0,1,2,3,...}: O índice de tempo representa um dia 
completo de evolução do preço da ação; 
 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 39 
Cadeias de Markov 
– E = {0,1}: O conjunto de estados, contém as classificações 
possíveis do processo, segundo as definições do problema:“0” indica um dia de queda nos preços, “1” indica um dia 
alta nos preços. 
– Assim nosso processo será: 
 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 40 




t
t
X t
 tempono suba ação a caso ,1
 tempono caia ação a caso ,0
Cadeias de Markov 
– Matriz de Transição: 
 
 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 41 







5,05,0
3,07,0
1
0
P
0 1
Cadeias de Markov 
– Diagrama de Transição: 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 42 
0 1
3,001 p
5,010 p
5,011 p7,000 p
Cadeias de Markov 
 Exemplo 4: Suponha que um jogador tenha $1,00 e aposte 
em um jogo em que ganha $1,00 com probabilidade 0,6 e 
perca $1,00 com probabilidade 0,4. O jogo termina sob 
duas condições: 
– Vitória: o jogador acumula $3,00 ()entrou com $1,00 e ganhou 
$2,00); 
– Derrota: o jogado perde tudo (fica com $0,00). 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 43 
Cadeias de Markov 
• Modelo: 
– Processo: Xt mede a quantidade de dinheiro que o jogador 
tem depois da jogada t; 
– T = { 0,1,2,3,...}: Mede a quantidade de “rodadas”. Em cada 
rodada o jogador perde ou ganha com as probabilidades 
definidas no problema; 
 Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 44 
Cadeias de Markov 
– OBS: Aqui o tempo “0” significa o período anterior ao jogo, 
ou seja, anterior à primeira rodada. 
– E = {0,1,2,3}: Identifica a categoria em que se encaixa o 
jogador, ou seja a quantidade de dinheiro acumulada depois 
da rodada t. Pela dinâmica descrita para o jogo o menor valor 
possível de dinheiro acumulada é “0” e a maior “3”, podendo 
acontecer todos os inteiros intermediários; 
 Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 45 
Cadeias de Markov 
– OBS: Nesse modelo X0 = 1. Isso traduz matematicamente a 
afirmação de que o jogador inicia a partida com $1,00. Note 
que por algum motivo que ignoramos (em geral podemos 
dizer que a “natureza” escolheu), o jogar tem uma certa 
quantidade de dinheiro que independe da dinâmica interna do 
jogo. 
 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 46 
Cadeias de Markov 
– P - Matriz de Transição : Seguimos o seguinte raciocínio: 
• Considere Xt = 1. Nesse caso temos duas ocorrências possíveis: ou 
Xt+1 = 2, com probabilidade 0,6, ou Xt+1 = 0, com probabilidade 0,4. 
Assim, p12 = 0,6 e p10 = 0,4. Note que não há possibilidade de 
termo Xt+1 = 1, pois ou o jogador ganha $1,00 ou perde $1,00, bem 
como não há possibilidade de Xt+1 = 3, uma vez que em cada rodada 
as perdas e os ganhos são unitários. Assim: p11 = p13 = 0. 
 
 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 47 
Cadeias de Markov 
• Considere Xt = 2. Nesse caso temos duas ocorrências possíveis: ou 
Xt+1 = 3, com probabilidade 0,6, ou Xt+1 = 1, com probabilidade 0,4. 
Assim, p23 = 0,6 e p21 = 0,4. Note que não há possibilidade de 
termo Xt+1 = 2, pois ou o jogador ganha $1,00 ou perde $1,00, bem 
como não há possibilidade de Xt+1 = 0, uma vez que em cada rodada 
as perdas e os ganhos são unitários. Assim: p20 = p22 = 0. 
 
 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 48 
Cadeias de Markov 
• Considere Xt = 0. Nesse caso o jogador perdeu o jogo (vide regras), ou 
seja, pelo fato de não ter mais dinheiro em jogo nesta partida(isso não 
significa que o apostador não possa começar outra partida). Assim Xt+1 = 
0, e conseqüentemente: p00 =1 e p01 = p02 = p03 = 0. 
• Considere Xt = 3. Nesse caso o jogador ganhou o jogo (vide regras), ou 
seja, ganhou o máximo de dinheiro possível na partida em curso (isso não 
significa que o apostador não possa começar outra partida). Assim Xt+1 = 
3, e conseqüentemente: p33 =1 e p30 = p31 = p32 = 0. 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 49 
Cadeias de Markov 
– Dessa forma, temos a seguinte Matriz de Transições para o 
modelo: 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 50 













0,10,00,00,0
6,00,04,00,0
0,06,00,04,0
0,00,00,00,1
3
2
1
0
P
0 1 2 3
Cadeias de Markov 
• Exemplo: Problema do Estoque. Vamos retomar agora o 
exemplo do estoque, acrescentando algumas informações: 
– Suponhamos que a demanda semanal Dt, obedece a uma 
distribuição de Poisson com média  = 1 unidade/semana. Dessa 
forma, como as Dt são independentes e identicamente distribuídas 
temos: 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 51 
    Tt
d
e
d
e
dDP
d
t 

!!
1 11
Cadeias de Markov 
• Modelo: 
– Processo (Xt): Volume de mercadorias em estoque no final da 
semana t; 
– Índice de Tempo (T): Conta as semanas. T = {0,1,2,...}; 
– Estados do Processo (E): Determinam os volumes possíveis 
de estoque das câmeras. E = {0,1,2,3}; 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 52 
Cadeias de Markov 
• Matriz de Transição (P). Para esse modelo temos a 
seguinte matriz: 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 53 













33323130
23222120
13121110
03020100
3
2
1
0
pppp
pppp
pppp
pppp
P
0 1 2 3
Cadeias de Markov 
– Considere Xt = 0. Neste caso, como visto nas estratégias de 
reposição, fazemos uma solicitação de 3 unidades ao 
fornecedor (no sábado a noite, momento de observação do 
estoque) e esse pedido é imediatamente atendido de modo 
que ficamos Xt = 3 unidades. Assim para calcularmos p00 
temos a seguinte identidade: 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 54 
   3|00|0 1100   tttt XXPXXPp
Cadeias de Markov 
 Assim, como a semana t + 1 inicia com 3 unidades, para que 
tenhamos no final desta semana 0 unidades (ou seja Xt+1 = 0) 
temos que ter Dt+1 ≥ 3. Assim temos: 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 55 
   
       21013
3|00|0
1111
1100




tttt
tttt
DPDPDPDP
XXPXXPp
Cadeias de Markov 
 OBS: Note que se tivermos demanda superior a 3 unidades, o 
que é possível, entregamos todo o nosso estoque durante a 
semana, ficando sem atender a alguma solicitação, por isso 
temos interesse no evento [Dt+1 ≥ 3]. 
 Temos: 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 56 
   
  1839,0
2!2
2
3679,0
!1
13679,0
!0
0
11
1
1
1
1
1
1
1










ee
DP
e
e
DPe
e
DP
t
tt
Cadeias de Markov 
 Assim: 
 
 
 Para calcular p01 segue-se o mesmo raciocínio, lembrando 
apenas que se temos 3 unidades no meço da semana, para 
chegarmos ao final com 1 unidade, temos que ter [Dt = 2]. 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 57 
       
0803,01839,03679,03679,01
2101300

 tttt DPDPDPDPp
Cadeias de Markov 
 Já temos essa probabilidade calculada. Assim 
 
 
 De modo similar temos: 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 58 
   
  1839,02
3|10|1 1101

 
t
tttt
DP
XXPXXPp
    3679,003679,01 0302  tt DPpDPp
Cadeias de Markov 
– Considere Xt = 1. Neste caso, como visto nas estratégias de 
reposição, não há reposição do estoque, e portanto iniciamos 
a semana t + 1 com um apenas unidade em estoque. Dessa 
forma temos: 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 59 
     
  6321,03679,0101
1111|0
1
11110



t
tttt
DP
DPDPXXPp
Cadeias de Markov 
– Temos ainda: 
 
– Notemos adicionalmente que pela dinâmica do modelo o 
estoque jamais cresce no meio da semana, logo: 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 60 
    3679,001|1 1111   ttt DPXXPp
01312  pp
Cadeias de Markov 
– Seguindo esta mesma lógica para os casos em que [Xt = 2] e 
[Xt = 3] (note que o caso [Xt = 3] é idêntico ao caso [Xt = 0]) 
podemos completar a matriz de transição para o modelo. 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 61 













3679,03679,01839,00803,0
0000,03679,03679,02642,0
0000,00000,03679,06321,0
3679,03679,01839,00803,0
3
2
1
0
P
0 1 2 3
Equações de Chapman-Kolmogorov 
• As equações de Chapman-Kolmogorov representam um 
processo iterativo que permite construir probabilidades 
de transição em “n” etapas conhecendo as 
probabilidades de transição em uma etapa; 
 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 62 
Equações de Chapman-Kolmogorov 
• Ideia básica: Suponha que queiramos saber a 
probabilidade de que em n etapas saiamos de um estado 
i (no tempo t) para um estado j (no tempo t + n). Essa 
probabilidade é denotada por pij 
(n). 
• Uma forma é a seguinte: Imagine uma cadeia com 
Conjuntos de Estados E = { 0, 1, 2 ,..., M }. 
 Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 63 
Equações de Chapman-Kolmogorov 
• Então, ir em n etapas do estado i para o estado j pode 
ser escrito como um trajeto de uma etapa de i a um 
estado k e um segundo trajeto de n - 1 etapas do estado 
k ao estado j. 
 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 64 
Equações de Chapman-Kolmogorov 
• Graficamente: 
 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 65 
i
0
1
2
M
j
1 etapa n-1 etapas 
Estado k 
Equações de Chapman-Kolmogorov 
• Assim a probabilidade da cadeia sair de i, ir a um k 
qualquer em uma etapa e depois em n-1 etapas chegar a 
j é dada por: 
 
 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 66 
    NkppkXjXPiXkXP nkjiktnttt  
)(
11 ||
Equações de Chapman-Kolmogorov 
• Como esse mesmo procedimento vale para qualquer k  
N temos que a equação final é dada por: 
 
• Em particular se n = 2, temos: 
 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 67 
   


M
k
n
kjik
n
ij ppp
0
1
  


M
k
kjikij ppp
0
2
Equações de Chapman-Kolmogorov 
• Uma forma muito útil de mostrar essas equações é o seu 
formato matricial: 
• OBS: Note, para n = 2 que: 
 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 68 
   1 nn PPP
 
   
    































22
0
2
0
2
00
0
000
0
000
2
MMM
M
MMM
M
MMM
M
pp
pp
pp
pp
pp
pp









PPP
Equações de Chapman-Kolmogorov 
• Exemplo 1 – Voltemos a considerar o exemplo do clima. 
Sabemos que: 
 
 Suponhamos a seguinte questão: Dado que tivemos um dia 
seco no tempo t, qual a probabilidade de que tenhamos um 
dia também seco no dia t + 2? 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 69 







4,06,0
2,08,0
1
0
P
0 1
Equações de Chapman-Kolmogorov 
• Podemos calcular essa probabilidade utilizando nosso 
velho conhecido diagrama de árvore: 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 70 
t
1t
2t
0
0
0
0
1
1
1
8,0
8,0
2,0
2,0 6,0 4,0
  64,08,08,0    12,06,02,0  76,012,064,0 
Equações de Chapman-Kolmogorov 
• Utilizando a equação de Chapman-Kolmogorov, em sua 
forma matricial temos: 
 
• Logo 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 71 
 
   
    
























28,072,0
24,076,0
4,06,0
2,08,0
4,06,0
2,08,0
2
11
2
10
2
01
2
002
pp
pp
P
  76,0200 p
Equações de Chapman-Kolmogorov 
• OBS: Interpretamos a matriz de transição em n etapas 
de modo similar “a matriz de uma única etapa. Assim: 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 72 
   iXjXPp tnt
n
ij   |
A probabilidade de a cadeia estar no estado j no temo t + n dado que estava 
em i no tempo t. 
Equações de Chapman-Kolmogorov 
• OBS: Podemos aplicar esse princípio arbitrariamente, 
de modo que: 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 73 
 
   
   
 


























256,0744,0
248,0752,0
4,06,0
2,08,0
28,072,0
24,076,0
2
3
11
3
10
3
01
3
003 PPP
pp
pp
Equações de Estado 
• Define-se a Probabilidade de Estado j
(t), como a 
probabilidade de a Cadeia estar no estado j, na etapa t. 
Simbolicamente: 
 
• Note-se que esta probabilidade não é condicionada. 
Independe de onde a Cadeia partiu. 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 74 
    EjjXP t
t
j 
Equações de Estado 
• Define-se o vetor de probabilidades de estado (t), na 
etapa t, como sendo o vetor M dimensional contendo 
todas as probabilidades de estado para cada estado 
individual, ou seja: 
 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 75 
          tMtttt  210π
Equações de Estado 
• OBS: Vamos verificar mais adiante que este vetor de 
probabilidades pode ser atualizado utilizando-se a 
matriz de transição. 
• OBS: Note que este vetor contem apenas probabilidades 
não condicionais. 
 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 76 
Equações de Estado 
• Exemplo 1. Voltando ao exemplo do clima. Afirmar que (0) 
= [1,0] significa que o estado “0” (tempo seco) ocorre com 
certeza (0
(0) = 1) no tempo 0. Já (0) = [0,2;0,8] significa 
que a probabilidade de no segundo dia termos um chuva é 
de 0,8. 
• OBS: Note que no casos do segundo dia não nos referimos 
ao que ocorreu no dia 1. 
 Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 77 
Cadeias Finitas Ergódicas 
• Em uma Cadeia de Markov de estados finitos, os 
estados recorrentes que forem aperiódicos são 
denominados ergódicos. 
• Uma Cadeia de Markov é dita ergódica se todos os seus 
estados são ergódicos. 
 
 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 78 
Comportamento de Longo Prazo das Cadeias de Markov 
• Imaginemos agora uma cadeia de dois estados, de modo 
que: 
– As probabilidades de estado no tempo t = 0 e t = 1 são dadas, 
respectivamente, por: 
 
 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 79 
             1110101000 ;;   ππ
Comportamento de Longo Prazo das Cadeias de Markov 
• Suponhamos adicionalmente que tenhamos a seguinte 
matriz de probabilidade de transição: 
 
 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 80 







1110
0100
1
0
pp
pp
P
0 1
Comportamento de Longo Prazo das Cadeias de 
Markov 
• Utilizando o modelo de árvore vamos verificar a 
evolução da cadeia: 
 
 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 81 
t
1t
0
0
0
1
1
1
 0
0
00p
 01
01p 10p 11p
 
00
0
0 p
 
01
0
0 p
 
10
0
1 p
 
11
0
1 p
               110101001001000011101 ;; pppp  π
Comportamento de Longo Prazo das Cadeias de 
Markov 
• Podemos escrever esse resultado de outra forma: 
 
 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 82 
           
   
Pππ
π
01
1110
01000
1
0
0
1
1
1
0
1 ;;








pp
pp

Comportamento de Longo Prazo das Cadeias de 
Markov 
• Em palavras: para obtermos as probabilidades de estado 
no tempo t = 1, tomamos as probabilidades de estado no 
tempo t = 0 e pós-multiplicamos pela matriz de 
transição P; 
• De modo geral, em um processo estacionário teremos: 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 83 
   
Pππ tt 1
Comportamento de Longo Prazo das Cadeias de Markov 
• Exemplo: Modelo do Clima. Imaginemos que saibamos que 
no dia anterior ao primeiro dia de observação, ou seja, no 
tempo t = 0, tenha chovido. Assim temos (0) = [ 0, 1 ] 
(0
(0) = 0 significa que com certeza não teremos clima seco 
no tempo t = 0; e 1
(0) = 1 significa que com certeza termos 
chuva em t = 0). Qual a probabilidade que chova no tempo t 
+ 2? 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 84 
Comportamento de Longo Prazo das Cadeias de Markov 
• Pela expressão geral, sabemos: 
 
 mas: 
 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 85 
   
Pππ 12 
   
Pππ 01 
       4,0;6,0
4,06,0
2,08,0
1,001 





 Pππ
Comportamento de Longo Prazo das Cadeias de Markov 
• Assim: 
 
• OBS:Esse procedimento pode ser executado qualquer 
que seja o tamanho do conjunto de estados. 
 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 86 
       28,0;72,0
4,06,0
2,08,0
4,0;6,012 





 Pππ
Comportamento de Longo Prazo das Cadeias de Markov 
• Um fato importante. Ainda sobre o modelo do clima. 
Temos 
 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 87 







4,06,0
2,08,0
P
 







28,072,0
24,076,0
2
P
 







256,0744,0
248,0752,0
3
P
 







251,0749,0
250,0750,0
4
P
 







25,075,0
25,075,0
5
P
 







25,075,0
25,075,0
6
P
Comportamento de Longo Prazo das Cadeias de Markov 
• Note que para n ≥ 5 P(n) fica constante. Dizemos, 
matematicamente, que a matriz convergiu. 
• Note ainda: 
 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 88 
              25,0;75,0
25,075,0
25,075,0
1;0602456 





 PπPπPππ 
Comportamento de Longo Prazo das Cadeias de Markov 
• Portanto (n) também converge. Em geral vale o 
resultado: 
 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 89 
 
 
  ,,,1
:estável estado de equações seguintes às teclusivamen
-ex e única satizfazem os que em 0lim
o disso, Além . de teindependen é e existe lim o
 l,irredutíve e ergódica Markov de Cadeiaqualquer Para
0
10





M
j
Mj
jj
n
ijn
n
ijn
p
ip


ππPπ
Comportamento de Longo Prazo das Cadeias de Markov 
• Isso significa que sob as condições de ergodicidade e 
irredutibilidade, o vetor de probabilidades de estado 
converge. 
• OBS:  =  P é um sistema de equações lineares com M + 1 
equações, sendo uma delas linearmente dependente. Para 
conseguirmos a solução única acrescentamos a equação 
restante: . 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 90 



M
j
j
0
1
Comportamento de Longo Prazo das Cadeias de Markov 
• Exemplo: Modelo do Tempo. Suponhamos agora que 
nossa questão seja: sob as condições de problema qual a 
probabilidade de que chova num período distante da 
data inicial (chamaremos isso de longo prazo)? 
• Como para esse modelo nossa cadeia é ergódica e 
irredutível, sabemos que o processo estabilizará. 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 91 
Comportamento de Longo Prazo das Cadeias de Markov 
• Portanto: se 
• então, no longo prazo, teremos: 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 92 
  






4,06,0
2,08,0
; 10 Pπ
     
25,0
75,0
1
6,08,0
1)3(
4,02,0)2(
6,08,0)1(
4,02,0;6,08,0
4,06,0
2,08,0
;;
1
0
10
100
10
101
100
10101010
































πPπ
Comportamento de Longo Prazo das Cadeias de Markov 
• Pelo fato de as duas equações do sistema original (primeira 
e segunda equações) serem linearmente dependentes, 
acrescentamos uma terceira equação para garantirmos a 
unicidade da solução; 
• Reduzimos o sistema de três equações a duas (primeira e 
terceira). Uma solução igual seria encontrada se 
utilizássemos a segunda e a terceira. 
 Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 93 
Comportamento de Longo Prazo das Cadeias de Markov 
• OBS: Sob as condições definidas temos relações de 
curo e longo prazo: 
– Curto prazo: 
– Longo prazo: 
– Em qualquer caso: 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 94 
   
Pππ tt 1
πPπ 



M
j
j
0
1
Custo Médio Esperado por Unidade 
• Consideremos uma cadeia de markov finita e irredutível. O 
limite abaixo sempre existe: 
 
• Seja agora o vetor  = [0, 1, ..., M ] o vetor de estados 
cujas componentes são definidas como o limite acima. 
Valem as relações de estabilidade: 
 Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 95 
  Mjip
n
j
n
k
n
ij
n
,,2,1,0 e 
1
lim
0










1
0
 

M
j
jπPπ
Custo Médio Esperado por Unidade 
• Suponha agora que exista uma função C(Xt) (custo, por 
exemplo) associada ao processo, no tempo t = 0, 1, 2, ... 
Note que C(Xt) é uma VA. Nessas condições pode-se 
mostrar que o Custo Médio por Unidade é dado por: 
 
 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 96 
   


M
j
tj jXCCE
0

Custo Médio Esperado por Unidade 
• OBS: Note que j captura o percentual de tempo que a 
cadeia passa no estado j. Assim o custo médio 
corresponde a uma média ponderada, com os pesos 
dados pelas probabilidades de estado de longo prazo. 
 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 97 
Custo Médio Esperado por Unidade 
• Exemplo: Modelo de Estoque. Para esse modelo já 
vimos que: 
– T = { 0,1,2,3,... } – Indica o tempo em semanas; 
– E = { 0, 1, 2, 3} – Indica os estados que a cadeia pode 
assumir. No nosso problema o volume de mercadorias em 
estoque; 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 98 
Custo Médio Esperado por Unidade 
– Matriz de Transição: 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 99 













3679,03679,01839,00803,0
0000,03679,03679,02642,0
0000,00000,03679,06321,0
3679,03679,01839,00803,0
3
2
1
0
P
0 1 2 3
Custo Médio Esperado por Unidade 
– Calculando as probabilidades de estado no longo prazo 
temos: 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva100 
   














3679,03679,01839,00803,0
0000,03679,03679,02642,0
0000,00000,03679,06321,0
3679,03679,01839,00803,0
,,,,,, 32103210 
πPπ
Custo Médio Esperado por Unidade 
– O que nos leva ao seguinte sistema 
 
 
 
– e, adicionalmente 
 
 
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 101 











32103
32102
32101
32100
368,0000,0000,0368,0
080,0264,0000,0368,0
184,0368,0368,0184,0
080,0264,0632,0080,0




13210  
Custo Médio Esperado por Unidade 
– Utilizando-se três das equações do sistema e a equação 
adicional chegamos a: 
 
– O Consideremos agora a seguinte função de custo simples: 
 
 
 Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 102 
166,0263,0285,0286,0 3210  
 












3se18$
2se8$
1se2$
0se0$
j
j
j
j
jXC t
Custo Médio Esperado por Unidade 
– Sob essas condições chegamos a 
 
 
 
 
 Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 103 
   
       
662,5$
166,018263,08285,02286,00
0




M
j
tj jXCCE 