lista de exercIcios 4 Cadeia de Markov

Prévia do material em texto

Profº Túlio de Almeida 
Pesquisa Operacional II 
 
LISTA DE EXERCÍCIOS 4 – CADEIAS DE MARKOV 
 
QUESTÕES PARA DISCUSSÃO 
 
 
Q1 O que são processos estocásticos? 
 
Q2 O que é um processo de Markov? Conceitue e cite 
exemplos. 
 
Q3 Qual a principal diferença entre um Processo de 
Markov e uma Cadeia de Markov? 
 
Q4 Conceitue “Probabilidade de Transição”. 
 
Q5 Quais são os 4 possíveis estados em uma Cadeia 
de Markov? O que difere um do outro? 
 
Q6 Quais são as equações de Chapman-
Kologomorov? Como estas podem ser aplicadas em 
cálculos de cadeias de Markov com n períodos? 
 
Q7 Defina cadeia ergódica. 
 
Q8 O que são as probabilidades de estado estável? 
Como estas podem ser obtidas? 
 
Q9 Qual a relação das probabilidades de estado 
estável com os conceitos de autovalores e 
autovetores? 
 
 
 
 
EXERCÍCIOS DE FIXAÇÃO 
 
E1 Faça as operações matriciais que são pedidas: 
Dadas as matrizes 













00,011,062,077,0
12,015,020,055,0
43,050,025,022,0
00,124,075,088,0
A 















5
7
4
2
B 
a. A
3
 
b. A.B 
c.B².A
8
 
 
E2 Dado o diagrama de transição de estado, obtenha 
a matriz de probabilidades de transição.
 
E3 Classifique os estados das Cadeias de Markov 
conforme as informações apresentadas: 
a. 
Profº Túlio de Almeida 
Pesquisa Operacional II 
 
 
b. 










001
100
010
 
c. 














1000
3
1
3
10
3
1
0100
0
4
1
4
1
2
1
 
d. 










1,07,02,0
03,07,0
9,001,0
 
e. 
f. 
 
 
E4 Seja uma cadeia de Markov homogênea com 
o espaço de transição e a seguinte 
matriz de transição: 
 
 
Calcule: 
 
a. 
b. 
 
E5 Dadas as seguintes matrizes de transição (em 
uma etapa) de uma cadeia de Markov, determine 
as classes da cadeia de Markov e se elas são ou não 
recorrentes. 
a. 0 1 2 3 
P = 
0
1
2
3 [
 
 
 0 0
1
3⁄
2
3⁄
1 0 0 0
0 1 0 0
0 1 0 0 ]
 
 
 
 
 
b. 0 1 2 3 
P = 
0
1
2
3
[
 
 
 
 
1 0 0 0
0 1 2⁄
1
2⁄ 0
0 1 2⁄
1
2⁄ 0
1
2⁄ 1 0
1
2⁄ ]
 
 
 
 
 
 
 
 
 
PROBLEMAS E APLICAÇÕES 
 
P1 O estado no ano de 2013 do uso da terra em uma 
cidade com 50 quilômetros quadrados é dado por: 
I. uso residencial = 30% 
II. uso comercial = 20% 
III. uso industrial = 50% 
Assumindo que a matriz de probabilidades de 
transição para um período de 5 anos é dada por: 
 
IIIIII
 
P = 










90,010,000,0
20,070,010,0
10,010,080,0
III
II
I
 
Profº Túlio de Almeida 
Pesquisa Operacional II 
 
Calcule o estado de uso da terra para os anos de 
2018 e 2023. 
 
P2 Um fabricante possui uma máquina muito 
importante no núcleo de um dos seus processos de 
produção. Devido ao uso intenso, a máquina 
deteriora-se rapidamente em no que se refere a 
qualidade e produtividade. Portanto, no final de cada 
semana, é realizada uma inspeção minuciosa que 
resulta em classificar a condição da máquina em um 
dos quatro estados possíveis: 
Estado Condição 
0 Excelente (como se fosse nova) 
1 Operável, com baixa deterioração 
2 Operável, com grande deterioração 
3 Inoperável 
 
Após a organização dos dados históricos sobre esses 
resultados de inspeção, uma análise estatística é feita 
sobre como o estado da máquina evolui de um mês 
para o outro. A seguinte matriz mostra a frequência 
relativa (probabilidade) de cada possível transição do 
estado em um mês (uma linha da matriz) para o 
estado no mês seguinte (uma coluna da matriz). 
 0 1 2 3 
0 0 7/8 1/16 1/16 
1 0 3/4 1/8 1/8 
2 0 0 1/2 1/2 
3 0 0 0 1 
 
Os gastos com manutenção por mês de acordo com o 
estado da máquina são: 
 estado 0 = $0 
 estado 1 = $1.000 
 estado 2 = $3.000 
 estado 3 = $6.000 
Acerca do problema abordado, considerando que a 
máquina está nova. 
a. Qual será o estado da máquina após 6 meses? 
b. Faça um gráfico de custos acumulado durante um 
ano de uso da máquina. Considere o ciclo de vida da 
máquina. 
c. Quais são as probabilidades de estado estável? 
d. Qual o custo médio permanente esperado para o 
problema apresentado? 
 
P3 Um professor de engenharia compra um novo 
computador (e ele está precisando muito por sinal) a 
cada 2 anos e tem preferência por 3 modelos: M1, M2 
e M3. Se o modelo atual for M1, o próximo pode ser 
M2 com probabilidade 0,20 ou M3 com probabilidade 
de 0,15. Se o modelo atual for M2, as probabilidades 
de trocar por M1 e M3 são respectivamente 0,60 e 
0,25, e se o modelo atual for o M3, então as 
probabilidades de trocar pelos modelos M1 e M2 são 
de 0,50 e 0,10. 
a. Represente a situação por meio de cadeia de 
Markov (diagrama) 
b. Obtenha a matriz de probabilidades de transição 
c. Calcule as probabilidades de troca de modelo 
computador daqui a 4 anos considerando que o 
modelo atual do computador do professor é o modelo 
M2. 
 
P4 Um carro de polícia está patrulhando uma região 
conhecida pela atividade de gangues. Durante uma 
patrulha há a probabilidade de 60% de a localidade 
que precisar de reforço ser atendida a tempo, senão a 
patrulha continuará sua patrulha normalmente. Ao 
receber uma chamada, há 10% de chance de 
cancelamento (quando a patrulha volta a sua patrulha 
normal) e 30% de chance de o carro estar atendendo 
uma chamada anterior. 
Quando o carro chega a cena, há 10% de os 
arruaceiros já terem fugido (então o carro volta a 
patrulha) e 40% de chance de uma prisão imediata. 
Caso contrário, os policiais farão uma busca na área. 
Se ocorrer prisão, há 60% de chance de transportar os 
suspeitos até o distrito policial; caso contrário, serão 
liberados e o carro volta a patrulha. 
a. Expresse as atividades da patrulha policial sob a 
forma de matriz de transição. 
b. Se no momento atual o carro de polícia estiver 
atendendo a um chamado, determine a probabilidade 
de ocorrer uma prisão em duas patrulhas. 
 
P5 No final de um determinado dia, o valor é 
registrado. Se o estoque subiu, a probabilidade de que 
ele suba amanhã é de 0,7. Se o estoque tiver 
diminuído, a probabilidade de que ele suba amanhã é 
de apenas 0,5. Esta é uma cadeia de Markov, onde o 
estado 0 representa o estoque subindo e o estado 1 
representa a queda do estoque. 
a. a matriz de transição é dada por 
b. quais são os estados após a decorrência de uma 
semana (7 dias), sabendo que o estoque subiu ontem 
e hoje. 
 
P6 Suponha que o modelo do mercado de ações seja 
alterado de tal forma que para o estoque aumentar 
amanhã, dependa se aumentou hoje e ontem. Em 
particular, se o estoque aumentou nos últimos dois 
dias, ele aumentará amanhã com probabilidade de 
0.9. Se o estoque aumentou hoje, mas diminuiu 
ontem, então aumentará amanhã com probabilidade 
de 0,6. Se o estoque diminuiu hoje, mas aumentou 
ontem, então ele aumentará amanhã com 
probabilidade de 0,5. Finalmente, se o estoque 
Profº Túlio de Almeida 
Pesquisa Operacional II 
 
diminuiu nos últimos dois dias, então aumentará 
amanhã com probabilidade de 0,3. Se definimos o 
estado como representando se o estoque vai para 
cima ou para baixo hoje, o sistema não é mais uma 
cadeia de Markov. No entanto, podemos transformar o 
sistema em uma cadeia de Markov, definindo os 
estadosda seguinte maneira: 
Estado 0: o estoque aumentou hoje e ontem. 
Estado 1: o estoque aumentou hoje e diminuiu ontem. 
Estado 2: o estoque diminuiu hoje e aumentou ontem. 
Estado 3: o estoque diminuiu hoje e ontem. 
Isso leva a uma cadeia de Markov de quatro estados 
com a seguinte matriz de transição: 













0,00,03,00,0
5,00,05,00,0
0,04,00,06,0
0,01,00,09,0
P 
Qual é panorama após 16 dias, sabendo que o 
estoque aumentou hoje e ontem? 
 
P7 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 chuvacontinuará no dia 
seguinte com uma probabilidade de 0,8, mas há 10% 
de chance de fazer sol. 
a. Determine a receita diária esperada para o 
MiniGolf. 
b. Determine a número médio de dias em que o 
tempo não estará ensolarado. 
 
P8 Uma partícula se move em um círculo através de 
pontos que foram marcados como 0, 1, 2, 3, 
4 (no sentido horário). A partícula começa no ponto0. 
A cada etapa ela tem probabilidade 0,5 de se deslocar 
um ponto no sentido horário (0 segue4) e 0,5 de se 
movimentar um ponto no sentido anti-horário. 
a. Expresse a situação como uma cadeia de Markov. 
b. Encontre as probabilidades de estado estável. 
c. Verifique o que acontece com essas probabilidades 
de estado estável, caso, a cada etapa, a probabilidade 
de se deslocar um ponto no sentido horário muda para 
0,9 e a probabilidade de se movimentar um ponto no 
sentido anti-horário muda para 0,1. 
 
P9 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? 
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? 
 
P10 O governo federal tenta auxiliar as atividades 
de pequenas empresas concedendo financiamentos 
anuais para projetos. Todas as propostas são 
competitivas, mas a chance de receber financiamento 
é mais alta se o proprietário não recebeu nenhuma 
nos últimos três anos, e mais baixa se recebeu 
financiamentos em cada um dos últimos três 
anos. 
Especificamente, a probabilidade de obter um 
financiamento se não conseguiu nenhuma nos últimos 
três anos é 0,9; 0,8 se obteve um financiamento; 0,7 
se obteve dois financiamentos; e apenas 0,5 se 
recebeu 3. 
a. Expresse a situação como uma cadeia de Markov. 
b. Determine o número esperado de financiamentos 
por proprietário por ano. 
 
P11 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. 
a. Expresse a situação como uma cadeia de Markov. 
b. Qual o número médio de vezes que Jim será detido 
pela policia antes de sua carteira de motorista ser 
cassada mais uma vez? 
Profº Túlio de Almeida 
Pesquisa Operacional II 
 
c. Qual é probabilidade de Jim perder definitivamente 
sua carteira de motorista? 
d. Se cada multa custa 100 u.m., quanto Jim 
paga em média entre sucessivas suspensões de sua 
carteira? 
 
P12 Um labirinto para camundongos consiste nos 
caminhos mostrado na figura a seguir. A 
interseção 1 é a entrada do labirinto e a interseção 5 é 
a saída. Em qualquer interseção, o camundongo tem 
probabilidades iguais de selecionar qualquer um dos 
caminhos disponíveis. 
Quando chega na interseção 5, o camundongo poderá 
voltar a circular no labirinto. 
a. Expresse a situação como uma cadeia de Markov. 
b. Determine a probabilidade de o camundongo 
chegará saída após três tentativas se começar na 
interseção 1. 
c. Determine a probabilidade de longo prazo de o 
camundongo localizar a interseção de saída. 
 
 
DESAFIOS 
 
D1 Os traços físicos são determinados pelos genes que um descendente recebe de seus dois ascendentes. No caso 
mais simples, um traço no descendente é determinado por um par de genes, um de cada um dos dois ascendentes. 
Em geral, cada gene num par pode tomar uma de duas formas, denotadas por 
A e a, que são os alelos. Isso leva a três pareamentos possíveis, a saber, 
 
AA, Aa, aa 
 
denominados genótipos(os pares Aa e aA determinam o mesmo traço e são, portanto, indistinguíveis). Mostra-se, no 
estudo da hereditariedade, que se um dos ascendentes tiver genótipo conhecido e o outro ascendente for de 
genótipo aleatório, então o descendente terá a probabilidade de genótipo dada na próxima tabela, que pode ser vista 
como uma matriz de transição de um processo de Markov. 
 
 Genótipo de 
Ascendente 
AA Aa aa 
Genótipo de 
Descendente 
AA 0,50 0,25 0 
Aa 0,50 0,50 0,50 
aa 0 0,25 0,50 
 
Assim, por exemplo, o descendente de um ascendente de genótipo AA e de outro escolhido aleatoriamente e de 
genótipo desconhecido tem uma chance de 50% de ser AA, 50% de ser Aa e nenhuma chance de ser aa. 
a. Mostre que a matriz de transição é regular. 
b. Encontre o vetor estacionário e discuta sua interpretação física. 
c. Sabendo que o gene do descendente é Aa, calcule o a probabilidade deste possuir um descendente aa 25 
gerações depois.