EAD 350 1 sem 2017 1ª aula de Cadeias de Markov

Prévia do material em texto

Cadeias de Markov – Introdução
EAD 350 Pesquisa Operacional 
Segmento Modelos de Redes
Prof. Nicolau Reinhard
1º Semestre de 2017
Referências básicas:
Taha, H., Pesquisa Operacional 8ª edição, Pearson, Prentice Hall, 2008 – cap 17
Site com tutorial, exercícios e ferramenta de simulação:
Waner, S e Constenoble, S., Finite mathematics: everything, chapter 7, 
disponível em http://www.zweigmedia.com/RealWorld/tcfinitep.html
EAD 350 Cadeias de MarkovExemplo 1 
Uma cidade tem apenas 2 jornais: Diário (D) e Gazeta (G)
Em t=0 D tem 400 assinantes e G tem 100 assinantes
Premissas do processo de renovação anual de assinaturas: 
1. O sistema é fechado: não há novos assinantes e assinantes antigos não saem
2. Os assinantes decidem no inicio de cada ano que jornal assinarão naquele ano, 
considerando apenas o seu estado no ano anterior, sem levar em conta o 
histórico de decisões dos outros anos (sistema sem memória).
Na passagem do ano 0 para o ano 1 ocorreu que: 
50 assinantes de D passaram a assinar G (12,5% dos assinantes de D) 
e
10 assinantes de G passaram a assinar D (10% dos assinantes de G)
Se este comportamento se mantiver nos anos seguintes (em termos de % dos 
assinantes que mudam em relação ao total de assinantes daquele jornal no ano 
anterior), no longo prazo qual será o número de assinantes de cada jornal?
(Fonte: Moreira, D., Pesquisa Operacional, Thomson, 2007, pag. 337, adaptado)
A
B
C
D
E
F.
Probabilidades de transição em uma cadeia de Markov em n etapas:
a°: Vetor de estado no instante 0
a¹ = a° . P, onde P é a matriz de transição.
Donde:
an=a°.Pn
e
Pn=Pn-m.Pm 
(equações de Chapman-Kolmogorov)
O estado “a” que satisfaz à equação:
a = a.P
Se existir, é denominado “estado de equilíbrio”
Probabilidades de transição
A
B
C
D
E
F.
Definição de estados em uma 
Cadeia de Markov
1. Um Estado j é alcançável a partir do Estado i se P(ij)n>0 para algum n>0 { (B,A); (E,C), etc}
2. Um Estado i é comunicante com um Estado j se i é alcançável a partir de j e vice-versa 
{(A,B); (D,E)}
3. Um Estado é transiente (temporário) se, após sair o sistema jamais pode voltar a este 
Estado (C)
4. Um Estado não transiente é chamado recorrente (o sistema certamente voltará a ele) 
5. Um Estado é absorvente se o sistema não pode deixá-lo após nele entrar {(F), (D E)}
6. Um Estado é periódico com período p se o sistema voltar a ele após cada p transições 
Uma Cadeia de Markov será denominada ergódica se todos os seus estados forem
recorrentes 
e 
aperiódicos
Para uma cadeia ergódica o “tempo médio do primeiro retorno a um estado”, 
também chamado de tempo médio de recorrência é dado por:
TRj = 1/Soma de Pij
n para todo i
A
B
C
D
E
F.
Cadeia ergódica
Exemplo 2 Fonte: Taha, H, Pesquisa Operacional, Pearson, 2008, adaptado
Um motorista pode cometer infrações de trânsito e receber pontos na carteira. 
Com 4 pontos ele é obrigado a se submeter a novo exame no mês seguinte 
(com isto ele zera sua contagem de pontos)
Em cada mês as probabilidades de ele receber um ponto a mais dependem 
apenas do número que ele já acumulou deste o último exame. 
(hipótese simplificadora: Ele jamais receberá mais de um ponto num mesmo mês.)
Número de pontos Probabilidade de receber 
no início do mês mais um ponto no mês
0 50%
1 40% 
2 30%
3 20%
4 0%
Tarefa: Construir a cadeia de Markov que representa este processo e calcular o 
estado de equilíbrio.
Pergunta: Qual o número médio de períodos entre dois exames consecutivos do 
motorista? (use o conceito de tempo médio de recorrência)
Note que o motorista 
fica mais cauteloso à 
medida que aumenta o 
seu número de pontos 
acumulados na carteira.
Cadeias de Markov Exercício 1
Prazo de entrega: 19/06/2017 até as 19 horas através do Moodle
Uma locadora de automóveis tem 1.000 veículos e opera em 4 cidades, com as seguintes 
probabilidades de local de devolução dos veículos locados em cada cidade
70% dos automóveis são devolvidos após uma semana na própria cidade onde foram 
locados. Para os demais 30%, depois de uma semana:
1. Dos veículos que foram alugados em Sorocaba: 20% são devolvidos em Santos, 60% em 
São Paulo e 20% em Campinas
2. Dos veículos que foram alugados em Santos: 40% são devolvidos em Campinas e 60% em 
São Paulo
3. Dos veículos que foram alugados em São Paulo: 50% são devolvidos em Campinas e 50% 
em Santos
4. Dos veículos que foram alugados em Campinas: 80% são devolvidos em São Paulo, 10% em 
Santos e 10% em Sorocaba
Perguntas
1. Qual o tamanho médio de pátio necessário (em número de veículos) em cada cidade?
2. Qual o número médio de semanas para um veículo ser devolvido à sua localidade de origem? 
(use o conceito de tempo médio de recorrência)
Observação: justifique as suas respostas a partir da análise da cadeia de Markov do negócio 
Fonte: Taha, H, Pesquisa Operacional, 8ª ed, Pearson, Pag. 293, adaptado