PO2 Cap 1 Processos Makovianos VS

Prévia do material em texto

Pesquisa Operacional 
Modelos Probabilísticos
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ário fazer 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 envolvendoincerteza.
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 1Cadeias 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,00000,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
Classificação de Estados de uma Cadeia de Markov
• Um importante conjunto de definições está relacionado
ao tipo de estado que estamos observando numa Cadeia
de Markov, pois utiliza-se essas definições para analisar
determinados fatos sobre as mesmas.
• Estado Acessível: Um estado j é dito acessível, a partir
de um estado i, se existir n ≥ 1 tal que pij
(n) > 0.
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 78
Classificação de Estados de uma Cadeia de Markov
– Exemplos 1 – Modelo do Clima. Neste modelo temos:
– Note que o estado “0” é acessível a partir do estado “1”, pois
p10 > 0
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 79







4,06,0
2,08,0
1
0
P
0 1
Classificação de Estados de uma Cadeia de Markov
– Exemplos 4 – Modelo do Jogo. Neste modelo temos:
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 80













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
Classificação de Estados de uma Cadeia de Markov
– Neste caso temos que o estado “0” não é acessível a partir do
estado “2” em uma etapa, mas é acessível em duas etapas (vide
matriz abaixo). Logo existe n tal que p20
(2) > 0. Assim conclui-se
que o estado “0” é acessível a partir do estado “2”.
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 81













000,1000,0000,0000,0
744,0000,0096,0160,0
360,0144,0000,0496,0
000,0000,0000,0000,1
3
2
1
0
2
P
0 1 2 3
Classificação de Estados de uma Cadeia de Markov
• Estados Comunicantes. Dizemos que dois estados i e j
se comunicam, se i é acessível a partir de j e vice-versa.
– Exemplo 1 – Modelo do Clima. Nesse modelo os estado “0”
e “1” são comunicantes, pois “0” é acessível a partir de “1”
(p10 = 0,6 > 0) e “1” acessível a partir de “0” (p01 = 0,2 > 0);
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 82
Classificação deEstados de uma Cadeia de Markov
– Exemplo 4 – Modelo do Jogo. Nesse modelo temos estados
não comunicantes. Vimos que o estado “0” é acessível a
partir do estado “2” (p20
(2) = 0,16 > 0). Mas nesse modelo o
estado “2” nunca é acessível a partir do estado “0”, pois
termos p20
(n) = 0 n. (Você pode verificar que a primeira
linha das matrizes de transição P, P(2) ..., será sempre
(1,0,0,0)).
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 83
Classificação de Estados de uma Cadeia de Markov
• OBS: Em geral qualquer estado se comunica consigo
mesmo, pois:
• OBS: Se um estado i se comunica com um estado j então o
estado j se comunica com o estado i (comutatividade)
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 84
    1|0  iXiXPp ttii
Classificação de Estados de uma Cadeia de Markov
• Se um estado i se comunica com um estado k e o estado k se
comunica com o estado j, então o estado i se comunica com
o estado j. (transitividade)
• Como consequência das afirmações anteriores, os estados
podem ser divididos em classes distintas, tais que aqueles
estados que se comunicam entre si encontram-se na mesma
classe.
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 85
Classificação de Estados de uma Cadeia de Markov
• Exemplo: Modelo do Clima. Nesse modelo “0” se
comunica com “1” e como a relação é comutativa,
temos que “1” se comunica com “0”. Assim os estados
“0” e “1” formam uma única classe;
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 86
Classificação de Estados de uma Cadeia de Markov
• Exemplo: Modelo do Jogo. Nesse modelo note:
– O estado “0” é acessível a partir de “1” e “2” (por exemplo:
p10 = 0,6 e p20
(n) = 0,16 ), mas a partir de “0” nenhum estado
é acessível (exceto o próprio, conforme afirmação acima);
– O mesmo pode se dizer do estado “3” (verifique!!!)
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 87
Classificação de Estados de uma Cadeia de Markov
– Já os estados “1” e “2” são comunicantes entre si (por
exemplo: p12 = 0,6 e p21 = 0,4 );
• Assim nesse modelo temos a formação de três classes:
uma formada só pelo estado “0”; uma só pelo estado
“3” e outra pelos estados “1” e “2”.
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 88
Classificação de Estados de uma Cadeia de Markov
• Uma cadeia que possui apenas uma classe que contém
todos os seus estados é dita irredutível.
• No caso do modelo do clima temos uma cadeia
irredutível. Mas no caso do modelo do jogo isso não
acontece
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 89
Classificação de Estados de uma Cadeia de Markov
• Um estado é dito transiente se a probabilidade de a
cadeia nunca voltar a esse estado, depois de passar pelo
mesmo, é positiva. Assim um estado i é dito transiente
se, e somente se, existir um estado j (j  i) que não se
comuniquem, ou seja: j é acessível a partir de i mas i
não é acessível a partir de j.
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 90
Classificação de Estados de uma Cadeia de Markov
• Um estado que não é transiente é dito recorrente.
• Um tipo especial de estado recorrente é o estado dito
absorvente. Um estado i é dito absorvente se pii
(n) = 1,
ou seja, uma vez que o processo assume esse estado não
mais sairá dele.
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 91
Classificação de Estados de uma Cadeia de Markov
• Exemplo 5: Considere a Cadeia de Markov com estados
E = { 0,1,2,3,4 } e matriz de probabilidade de transição
dada por:
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 92

















00001
03/23/100
00100
0002/12/1
0004/34/1
4
3
2
1
0
P
0 1 2 3 4
Classificação de Estados de uma Cadeia de Markov
• Pelas nossas definições:
– “2” – é um estado absorvente, pois uma vez que o processo
assume “2” o mesmo permanece valendo “2” indefinidamente;
– “3” – é um estado transiente pois há uma probabilidade de 1/3 da
cadeia sair e “3” e chegar em “2” e então nunca mais voltar a
“3”;
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 93
Classificação de Estados de uma Cadeia de Markov
– “4” - é um estado transiente particular. Ele só pode ser acessível
pelo sistema no instante inicial do processo. Caso isso ocorra, já
na etapa seguinte o processo deixará “4” indo para “0”, não mais
retornando;
– “0” e “1” – São recorrentes, pois uma vez que o sistema caia em
um desses estados sempre terá probabilidade positiva de retorno
(nesse caso após entrar nessa classe a cadeia permanecerá nela
indefinidamente).
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 94
Classificação de Estados de uma Cadeia de Markov
• Pelas nossas definições:
– “4” - é um estado transiente particular. Ele só pode ser
acessível pelo sistema no instante inicial do processo. Caso
isso ocorra, já na etapa seguinte o processo deixará “4” indo
para “0”, não mais retornando;
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 95
Classificação de Estados de uma Cadeia de Markov
• OBS: A recorrência é uma propriedade de classe, isto é,
dada uma classe todos os seus estados são recorrentes
ou transientes;
• Em uma Cadeia de Markov finita, nem todos os estados
podem ser transientes. Assim todos os estados de uma
cadeia de Markov finita e irredutível são recorrentes.
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 96
Classificação de Estados de uma Cadeia de Markov
• Periodicidade. Um estado i tem período t, se t é o maior
inteiro: pii
(n) = 0 para todo n diferente de t, 2t, 3t, ...(t e
seus múltiplos).
• Exemplo: Modelo do Jogo: para esse modelo temos os
seguintes fatos:
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 97
Classificação de Estados de uma Cadeia de Markov
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 98













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
 













00,100,000,000,0
60,024,000,016,0
36,000,024,040,0
00,000,000,000,1
3
2
1
0
2
P
0 1 2 3
 













000,1000,0000,0000,0
744,0000,0096,0160,0
360,0144,0000,0496,0
000,0000,0000,0000,1
3
2
1
0
3
P
0 1 2 3
Classificação de Estados de uma Cadeia de Markov
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 99
 













0000,10000,00000,00000,0
7440,00576,00000,01984,0
4464,00000,00576,0496,0
0000,00000,00000,00000,1
3
2
1
0
4
P
0 1 2 3
 













00000,100000,000000,000000,0
77856,000000,002304,019840,0
44640,003456,000000,051904,0
00000,000000,000000,000000,1
3
2
1
0
5
P
0 1 2 3
Classificação de Estados de uma Cadeia de Markov
• Assim note:
• OBS: Se um estado i é tal que pii
(s) > 0 e pii
(s+1) > 0 então
esse estado tem período 1 e é dito aperiódico.
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 100
        000576,0024,00 511
4
11
3
11
2
1111  ppppp
        000576,0024,00 522
4
22
3
22
2
2222  ppppp
Classificação de Estados de uma Cadeia de Markov
• 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 101
Comportamentode 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 102
             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 103







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 104
t
1t
0
0
0
1
1
1
 0
0
00p
 0
1
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 105
           
   
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 106
   
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 107
Comportamento de Longo Prazo das Cadeias de Markov
• Pela expressão geral, sabemos:
mas:
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 108
   
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 109
       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 110







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 111
              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 112
 
 
  ,,,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 113



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 114
Comportamento de Longo Prazo das Cadeias de Markov
• Portanto: se
• então, no longo prazo, teremos:
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 115
  






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 116
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 117
   
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 118
  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 119
   


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 120
Custo Médio Esperado por Unidade
• Exemplo: Modelo de Estoque. Para esse modelo já
vimos que:
– T = { 0,1,2,3,... } – Indica o tempo emsemanas;
– 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 121
Custo Médio Esperado por Unidade
– Matriz de Transição:
Pesquisa Operacional 1 - Prof. Luciano Barboza da Silva 122













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 Silva 123
   














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 124











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 125
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 126
   
       
662,5$
166,018263,08285,02286,00
0




M
j
tj jXCCE 