Lista_5_Cadeias_de_Markov

Prévia do material em texto

Universidade Federal Fluminense 
Profª. Lídia – Pesquisa Operacional II 1 
DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO 
PESQUISA OPERACIONAL II 
PROFª. LÍDIA 
Cadeias de Markov – Lista Nº 5 
 
1. Um carro de polícia está patrulhando uma região conhecida pelas atividades de gangues. 
Durante uma patrulha, há 60% de chance de a localidade que precisar de ajuda ser atendida 
a tempo, senão o carro continuará a sua patrulha normal. Ao receber uma chamada há 10% 
de chance de cancelamento (quando o carro volta a sua patrulha normal) e 30% de chance 
de o carro já estar atendendo a uma chamada anterior. 
Quando o carro de polícia chega à cena, há 10% de chance de os arruaceiros terem fugido 
(então o carro volta à patrulha) e 40% de chance de uma prisão imediata. Caso contrário, os 
policiais farão uma busca na área. Se ocorrer uma prisão, há 60% de chance de transportar 
os suspeitos até o distrito policial; caso contrário, serão liberados e o carro volta à patrulha. 
a. Expresse as atividades probabilísticas da patrulha policial sob uma forma de matriz de 
transição. 
b. Se no momento em questão o carro de polícia estiver em uma cena para onde foi 
chamado, determinar a probabilidade de ocorrer uma prisão em duas patrulhas. 
 
2. 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. 
 
 
3. 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. 
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. 
 
4. 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 ponto 0. A cada etapa ela tem probabilidade 0,5 
de se deslocar um ponto no sentido horário (0 segue 4) 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. 
 
5. 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% 
 Universidade Federal Fluminense 
Profª. Lídia – Pesquisa Operacional II 2 
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? 
c. 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? 
d. Determine o número médio de semanas transcorridas antes de um carro ser devolvido 
a sua localidade de origem. 
 
6. 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. 
 
7. 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 policiai antes de sua carteira 
de motorista ser cassada mais uma vez? 
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? 
 
8. 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.