Pesquisa Operacional Processos Estocasticos Aula 1

Prévia do material em texto

Pesquisa Operacional III 
 
Profª Lidia 
 
 Processos Estocásticos: Cadeias de 
Markov 
Processo Estocásticos 
 Descrevem um comportamento de um sistema ao 
longo do tempo, Xt 
 t: 0,1,2, ... ou 1,2,3, ... 
 Xt é uma Variável Aleatória pode ser descrita 
através de uma Função Distribuição de 
Probabilidade 
 Exemplos: 
 Xt: número de câmeras disponíveis no final da 
semana t 
 Xt a quantidade de pacotes trafegando em uma rede 
de computadores no instante t; Número de usuários 
na fila de um sistema em função do tempo 
2 
Processo Estocásticos 
 Estado atual do sistema ou categoria é chamada de 
estado, estados mutuamente exclusivos 
 Espaço de estados: 
 Finito 
 Infinito 
 Ex.1(Taha): condição de uma máquina para o mês 
t, 0, se a condição for ruim; 1 se a condição for 
razoável; 2, se a condição for boa 
 A variável aleatória é finita (só três estados) 
 Estado do sistema no instante t 
3 
Processo Estocásticos 
 Em geral: 
 Estados denotados: 0,1,...,M 
 Sistema observados em determinados pontos do 
tempo, t 
 Exemplo 1 é um processo estocástico finito 
 Ex.2 (Taha): serviços chegam a uma oficina 
mecânica à taxa de 5 por hora. O processo de 
chegada segue uma distribuição de Poisson, que 
permite que qualquer número de serviços entre 
zero e infinito chegam à oficina durante o 
intervalo de tempo (0,t) 
 Xt = 0,1,2,..., t>0 
 Exemplo 2 é um processo estocástico infinito 
4 
Processo Estocásticos 
 Exemplo 3 (Hillier & Lieberman). 
Seja Dt o nº de câmeras que são vendidas na semana t 
(caso o estoque não esteja esgotado). Suponha 
também que os Dt sejam variáveis aleatórias 
independentes e identicamente distribuídas com uma 
distribuição de Poisson com média igual a 1. Defina Xt o 
número de câmeras disponíveis no final de semana t. 
O dono da loja deseja saber como evolui o estoque de 
câmeras ao longo das semanas. 
Considere a seguinte política de encomendas: 
Se Xt = 0, encomendar três câmeras; se Xt >0, não 
encomendar nenhuma câmera. 
 Quais os possíveis estados das Xt? 
 As variáveis aleatórias Xt são independentes? 
 5 
Processo de Markov 
 Um processo estocástico é um processo de 
Markov se a ocorrência de um estado futuro 
depender somente do estado imediatamente 
precedente (o sistema não possui memória) 
 
 
 Nome em homenagem a A. A. Markov, que em 
1907 definiu e analisou esses processos 
 Processo de Markov de espaço de estados 
discreto e finito: Cadeia de Markov 
   
  
     
n 1 n 0 n 1 nt n 1 t n t 0 t n 1 t n
P X x | X x ,...,X x P X x | X x
6 
Cadeia de Markov 
 Probabilidades de transição (uma etapa) de passar do 
estado i em t ao estado j em t+1: 
 
 
 Por definição: 
 
 
 Notação matricial: 
 
 
 
 
 Se pij igual para t = 0,1,2,... então probabilidades de 
transição são estacionárias, não mudam ao longo do 
tempo e são independentes 
   ij t 1 tp P X j | X i
 ij
j
p 1, i=0,1,2,...,n
 
 
 
 
  
 
11 12 1n
21 22 2n
n1 n2 nn
p p ... p
p p ... p
P
... ... ... ...
p p ... p
7 
Cadeias de Markov 
 Exemplo 4: O tempo de uma cidade A pode mudar 
de maneira bastante rápida de um dia para o outro. 
Entretanto, as chances de termos tempo seco 
amanhã são ligeiramente maiores, caso esteja seco 
hoje do que se chover hoje. Particularmente, a 
probabilidade de termos tempo seco amanhã é de 
0,8, caso hoje esteja seco, porém é de apenas 0,6 
caso hoje chova. Essas probabilidades não mudam, 
caso as informações sobre o tempo antes de hoje 
também forem levadas em consideração. 
8 
Cadeias de Markov 
 Considerando 0: seco, 1: chuvoso 
 
 
 
 Podemos expressar também como um diagrama de 
transições (um grafo) que é a representação gráfica 
da matriz de transições 
 
 
9 
Cadeias de Markov 
 Exemplo 5. Todo ano, no início da estação de plantio 
de mudas (março a 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 pode ser boa, razoável e ruim. 
Se a condição neste ano for boa, há 50% de chance 
de se tornar razoável e 30% de se deteriorar. Se a 
condição do solo neste ano for razoável, a 
produtividade pode se manter ou se tornar ruim com 
as mesmas chances, no entanto existe 30% de 
chance da produtividade se tornar boa. Finalmente, 
para uma condição ruim neste ano existe um 30% de 
chances de se tornar razoável, mas não existe 
possibilidade dela ser tornar boa. 
10 
Cadeias de Markov 
 Exemplo 6 (H & L). Suponha que um jogador tenha 
1 u.m. e a cada rodada do jogo ganhe 1 u.m. com 
probabilidade de p>0 ou perca 1 u.m. com 
probabilidade de 1-p>0. O jogo termina quando o 
jogador acumular 3 u.m. ou então quando ele 
“quebrar”. Expresse como uma cadeia de Markov. 
 Exemplo 7. Expresse o exemplo 3 como uma cadeia 
de Markov. 
11 
Cadeias de Markov 
 Se precisarmos determinar probabilidades ao longo 
de um período, ou seja, o que acontece após várias 
transições? 
 Probabilidades de transição em n etapas: 
 
 
 Probabilidade condicional de que o sistema estará 
no estado j após exatamente n etapas (unidades de 
tempo), dado que ele inicia no estado i a qualquer 
instante t é: 
 
 
 
   
n
ij t n tp P X j | X i
 
M
(n) (n)
ij ij
j=1
p 0 e p 1, i=0,1,2,...,n
12 
Equações de Chapman-Kolmogorov 
 Método para calcular probabilidades de transição 
em n etapas: 
 
 
 Para n=2 temos 
 
 
 Matricialmente: P(n) = P .P(n-1) 
 = P(n-1).P 
 = P (2) .P(n-2) 
 ... = P (k) .P(n-k) 
 
 
 
 
  
M M
(n) (n 1) (n) (m) (n m)
ij ik kj ij ik kj
k 0 k 0
p p p ou p p p 


M
(2)
ij ik kj
k 0
p p p
13 
Equações de Chapman-Kolmogorov 
 Exemplo 8: no exemplo do clima 
 Encontre P(2) e responda: 
 se tempo estiver seco em um dado dia, qual a 
probabilidade de após dos dias se encontrar no mesmo 
estado? 
 se o tempo estiver no estado chuva em um dado dia, 
qual a probabilidade de após dos dias se encontrar no 
estado seco? 
 Se o tempo estiver seco em um dado dia, qual a 
probabilidade de após quatro dias se encontrar no 
mesmo estado? 
14 
Probabilidades absolutas 
 Dadas as probabilidades iniciais 
 e dada a matriz P, as probabilidades absolutas a(n) 
de estar no estado j após n transições (n>0): 
 
 
 Ex. 9 (exemplo do jardineiro). Suponha que este 
ano o jardineiro usou um fertilizante de forma que 
ele acredita que a produtividade do solo ficou da 
seguinte forma 50% de chance dela ser boa, 40% 
de ser razoável e 10% de ser ruim. Qual será a 
probabilidade da produtividade do solo ser boa 
após dois anos? 
(n) (0) na a P
 (0) (0)ja a
15 
Exemplo 10 
 Uma locadora de automóveis tem filiais em Phoenix, Denver, 
Chicago e Atlanta. A locadora permite aluguel de carros com 
devolução na mesma cidade ou em outra cidade, de modo 
que um carro alugado em uma localidade pode acabar em 
outra. As estatísticas mostram que, ao final de cada semana, 
70% de todos os carros são alugados e devolvidos na 
mesma cidade. No caso de aluguel com devolução em outras 
cidades, o quadro é: de Phoenix, 20% são devolvidos em 
Denver, 20% são devolvidos em Atlanta e 60% em Chicago; 
de Denver, 60% em Chicago e 40% em Atlanta; de Chicago, 
50% são devolvidos em Atlanta e o restante em Denver; e, 
de Atlanta, 80% são devolvidos em Chicago, 10% em 
Denver e 10% em Phoenix. 
a. Expresse a situação como uma cadeia de Markov. 
b. Se a locadora começar a semana com 100 carros em cada 
localidade,como será a distribuição em duas semanas? 
 
 
16 
Classificação dos Estados 
 Absorvente: se o estado j retornar para ele mesmo 
com certeza pjj=1 
 Transiente: se o estado j puder alcançar outro 
estado mas não pude voltar ao mesmo estado em 
que estava ( para todo i) 
 Recorrente: se a probabilidade de voltar ao estado 
em que estava com base em outros estados for 1 
(só acontece se o estado não for transiente) 
 Periódico: se um retorno só for possível em t, 2t, 
3t, .... etapas (com t>1), i.e. sempre que n 
não for divisível por t. 
 

(n)ij
n
lim p 0
(n)jjp 0
17 
Classificação dos Estados 
 Exemplo 11: suponha que uma determinada cadeia de 
Markov tem a seguinte matriz de transição: 
 
 
 
 
 
 Classifique os estados 
 
 
 
 
 
 
  
 0 1 2 3 4
0 1/ 4 3 / 4 0 0 0
1 1/ 2 1/ 2 0 0 0
P 2 0 0 1 0 0
3 0 0 1/ 3 2 / 3 0
4 1 0 0 0 0
18 
Periodicidade 
 Propriedades: se um retorno só for possível em t, 
2t, 3t, .... etapas (com t>1) 
 Forma de testar periodicidade de um estado é 
calculando Pn e observando os valores de 
 para n=1,2,.... 
 Exemplo 12: 
(n)
jjp
19 
Periodicidade 
 Em uma cadeia de Markov de estados finitos, os 
estados recorrentes que foram aperiódicos são 
denominados estados ergódicos 
 Cadeia de Markov ergódica: se todos os estados 
forem ergódicos 
 Probabilidade de estado estável (probabilidades 
estacionárias): probabilidade de encontrar o 
processo em certo estado (j), após um grande 
número de transições, j, independente do 
estado estável. 
20 
Probabilidades Estacionárias 
 Em uma cadeia de Markov ergódica, as 
probabilidades de estado estável são definidas 
por 
 
 Em que os j satisfazem única e exclusivamente as 
seguintes equações de estado estável 
 
(n)
j ij
n
lim p 0

  
M
j i ij
i 0
M
j
j 0
p , para j = 0,1,...M
1


  
 


21 
Probabilidades Estacionárias 
 Exemplo 13: no exemplo do clima. 
 Dois estados: seco e com chuva 
 Quais são as equações de estado estável? 
 Encontre as probabilidades a longo prazo. 
 
 
Outro resultado 
 Número esperado de transições antes de os 
sistemas retornarem a um estado j pela 
primeira vez: tempo médio do primeiro retorno 
ou tempo médio de recorrência jj=1/ j 
22 
Exemplo 14 
 Em um domingo ensolarado de primavera, o 
MiniGolf pode obter 2.000 u.m. de receita bruta. Se 
o dia estiver nublado, a receita cai 20%. Um dia 
chuvoso reduz a receita em 80%. Se o dia de hoje 
estiver ensolarado, há 80% de chance que amanhã 
o tempo também vai estar ensolarado, sem 
nenhuma chance de chuva. Se o dia estiver 
nublado, há 20% de chance de chover amanhã e 
30% de chance de fazer sol. A chuva continuará no 
dia seguinte com uma probabilidade de 0,8, mas há 
10% de chance de fazer sol. 
 Determine a receita diária esperada para o MiniGolf. 
 Determine a número médio de dias em que o tempo não 
estará ensolarado. 23 
Exemplo 15 
 No exemplo da locadora, considerando a matriz de 
transições no exemplo 7. 
a. Se cada localidade estiver prevista para manusear um 
máximo de 110 carros, no longo prazo haverá algum 
problema de espaço em qualquer uma das localidades? 
b. Determine o número médio de semanas transcorridas 
antes de um carro ser devolvido a sua localidade de 
origem. 
 
24 
Exemplo 16 
 Jim tem um vasto histórico de multas de trânsito. Infelizmente 
para ele, a moderna tecnologia permite o acesso às suas multas 
anteriores. Logo que ele acumular 4 multas, sua carteira de 
motorista será cassada até ele concluir um curso educativo para 
novos motoristas, quando recomeçará com uma ficha limpa. Jim 
fica mais afoito imediatamente após concluir o curso para novos 
motoristas e é invariavelmente detido pela polícia com 50% de 
chance de ser multado. Após cada nova multa, ele tenta ser mais 
cuidadoso, o que reduz em 0,1 a probabilidade de uma multa. 
 Expresse a situação como uma cadeia de Markov. 
 Qual o número médio de vezes que Jim será detido pela policiai 
antes de sua carteira de motorista ser cassada mais uma vez? 
 Qual é probabilidade de Jim perder sua carteira de motorista? 
 Se cada multa custa 100 u.m., quanto Jim paga em média entre 
sucessivas suspensões de sua carteira? 
 25 
Exemplo 17 
 Suponha que uma rede de comunicações transmita 
dígitos binários, 0 ou 1, em que cada dígito é 
transmitido quatro vezes em seguida. Durante cada 
transmissão, a probabilidade é 0,99 de que o dígito 
introduzido será transmitido de forma acurada. 
 Expresse a situação como uma Cadeia de Markov. 
 Determine a probabilidade de que um dígito 
entrando na rede será gravado de forma precisa 
após a última transmissão. 
 
26 
Exemplo 18 
 Uma livraria acompanha diariamente o nível de estoque 
de um livro popular para repor o estoque de 100 
exemplares no início de cada dia. Os dados para os 
últimos 30 dias fornecem a seguinte posição de estoque 
ao final do dia: 1, 2, 0, 3, 2, 1, 0, 0, 3, 0, 1, 1, 3, 2, 3, 
3, 2, 1, 0, 2, 0, 1, 3, 0, 0, 3, 2, 1, 2, 2. 
 Represente como o estoque diário como uma cadeia de 
Markov 
 Determine a probabilidade de estado em equilíbrio de a 
livraria ficar com falta de estoque de livros em qualquer 
dia. 
 Determine o estoque diário esperado. 
27 
Vamos pensar!!!! 
 Quais as probabilidades a longo prazo dos estados 
absorventes? 
 
 1,0 0,0 0,0 0,8 0,1 0,1 
P = 0,3 0,3 0,4 e Q = 0,3 0,3 0,4 
 0,1 0,9 0,0 0,0 0,0 1,0 
 
28 
Questão de prova 
 Pacientes que sofrem da falência renal podem fazer um 
transplante ou diálise periódica. Durante qualquer ano, 
30% conseguem transplantes de pessoas que morreram 
e 10% recebem rins de um doador vivo. No ano 
seguinte a um transplante, 30% dos transplantados 
com rins de pessoas mortas e 15% dos que receberam 
os rins de doadores vivos voltam à diálise. As 
porcentagens de óbitos entre os dois grupos são 20% e 
10%, respectivamente. Entre os que continuam com 
diálise, 10% morrem, e, entre os que sobrevivem mais 
de um ano após o transplante, 5% morrem e 5% 
voltam à diálise. 
 Represente como uma cadeia de Markov. 
 Para um paciente que está atualmente em diálise, qual é 
a probabilidade de receber um transplante em dois anos. 
 
29