Baixe o app para aproveitar ainda mais
Prévia do material em texto
MAB-515 2010-1 1 Terceiro Teste MAB-515 2010-2 (2/12/2010) (50 pontos) Nome: GABARITO 1ª Questão: (25 pontos) (CMTD) Para seleção de uma vaga olímpica, dois atletas competem entre si, por várias disputas. As disputas têm sempre um vencedor e não há empate. Quando um dos atletas acumula um saldo de três vitórias sobre o outro, ele se classifica para a vaga. Um atleta está melhor preparado e tem uma probabilidade p de vencer uma disputa, enquanto o outro, menos treinado, tem probabilidade q (=1-p) de vencer uma disputa. Queremos calcular a probabilidade de cada atleta obter a vaga olímpica em função de p e q, e também o número médio de disputas até a definição. Resolva o problema utilizando Cadeia de Markov a) (5) Desenhe uma cadeia de Markov que permita obter as probabilidades solicitadas. Dica: Não existe estado absorvente nesta cadeia! b) (5) Indique em função das probabilidades de equilíbrio: P{ganho da vaga pelo atleta mais preparado} e P{ganho da vaga pelo atleta menos preparado}. Atenção: estas duas probabilidades tem que somar a 1, pois um deles é que ganha a vaga olímpica. c) (5) Obtenha as probabilidades de equilíbrio em função de p e q. Use q e não 1-p. Escreva o sistema de equações, enumere as equações que serão utilizadas, e resolva o sistema indicando claramente qual equação está sendo utilizada a cada passo. d) (5) Calcule as probabilidades de ganho da vaga com p = 2/3 e q = 1/3. Cheque se elas somam a 1. e) (5) Quantas disputas em média ocorrerão até a definição da vaga? Dê a resposta literal e a resposta numérica. Solução: a) (5) b) (5) P{vaga ganha pelo atleta menos preparado} = 2* 2* 2* 2 1 1 3 3 1 2 3 3 F pi pi pipi pi = + P{vaga ganha pelo atleta mais preparado} = 2 2 2* 2 2 2 3 3 1 2 3 3 F pi pi pipi pi = + 2* 1* 1 2/3 2/3 2/3 0 2 1 2/3 F 1/3 1/3 1/3 1/3 2/3 1/3 MAB-515 2010-1 2 A disputa termina quando se alcança o estado F (Final). Este estado é alcançado a partir de E2 e de E2*, pois 2* 2 1 2 3 3F pi pi pi= + . Em um número n de transições, o estado F é visitado chegando por E2 um número médio de vezes dado por 2 2 3 tpi e o estado F é visitado em média Ftpi vezes. Logo, a probabilidade do mais capacitado vencer é dada pela relação entre estes dois valores e raciocínio idêntico pode ser aplicado para obter a probabilidade do menos capacitado ganhar a vaga. c) (10) Circundando cada estado para obter cinco equações linearmente independentes: 0 1 1* 1 0 2 1* 2* 0 2 1 2* 1* { 0} (1) { 1} (2) { 1*} (3) { 2} (4) { 2*} (5) FE q p E p q E p q E p E q pi pi pi pi pi pi pi pi pi pi pi pi pi pi = + + = + = + = = Substituindo (4) em (2): 0 1 0 1 1 (6)1 p p pq pq pi pi pi pi pi= + ∴ = − Substituindo (5) em (3): 0 1* 1* 0 1* (7)1 q pq q pq pi pi pi pi pi= + ∴ = − Substituindo (6) e (7) em (1): 0 0 0 0 (1 3 ) (8) 1 1 1F F pq pq pq pq pq pq pi pi pi pi pi pi − = + + ∴ = − − − Substituindo (6) e (7) em (4) e (5) nos permite escrever 2 2 0 0 2 2*(9) , (10)1 1 p q pq pq pi pi pi pi= = − − A sexta equação a ser usada é a conservação de probabilidade 0 1 2 1* 2* 1Fpi pi pi pi pi pi+ + + + + = . Usando (6 a10), temos 2 2 0 0 0 0 0 0 0 2 2 (1 3 ) 1 1 1 1 1 1 1 1 (11) 4 62 4 p q p q pq pq pq pq pq pq pq pq pqpq p q p q pi pi pi pi pi pi pi − + + + + + = − − − − − − − ∴ = = −− + + + + Substituindo os valores de p=2/3 e q = 1/3 obtemos: MAB-515 2010-1 3 1 1* 0 0 2 1 02* 1* 1 2 1* 2* 2{ 0} (1) 3 3 2{ 1} (2) 3 3 2{ 1*} (3) 3 3 2{ 2} (4) 3 { 2*} (5) 3 FE E E E E pi pi pi pi pi pi pi pipi pi pi pi pi pi = + + = + = + = = Substituindo (4) em (2): 0 0 01 1 1 1 2 2 62 7 (6) 3 9 9 3 7 pi pi pipi pi pi pi= + ∴ = ∴ = Substituindo (5) em (3): 0 0 01* 1* 1* 1* 32 7 (7) 9 3 9 3 7 pi pi pipi pi pi pi= + ∴ = ∴ = Substituindo (6) e (7) em (1): 0 0 0 0 2 2 3 (8) 7 7 7F F pi pi pi pi pi pi= + + ∴ = Substituindo (6) e (7) em (4) e (5) nos permite escrever 0 0 2 2* 4 (9) , (10) 7 7 pi pi pi pi= = A sexta equação a ser usada é a conservação de probabilidade 0 1 2 1* 2* 1Fpi pi pi pi pi pi+ + + + + = . Usando (6 a10), temos 0 0 0 0 0 0 0 6 4 3 3 71 (11) 7 7 7 7 7 24 pi pi pi pi pi pi pi+ + + + + = ∴ = Foi solicitada apenas a dedução literal e substituição final pelos valores numéricos. A dedução completa e repetida é para facilitar correções. d) (5) Com os valores numéricos temos 0 1 2 1* 2* 7 6 4 3 1 3 , , , , , 24 24 24 24 24 24F pi pi pi pi pi pi= = = = = = . Então, P{vaga ganha pelo atleta menos preparado} = 2* 1 3 9F pi pi = = , e P{vaga ganha pelo atleta mais preparado} = 22 8 3 9F pi pi = = . e) (5) E[número de disputas]= 1 211 7 3Fpi − = = . Explicação: após atingir o estado F retornamos a E0 com probabilidade 1. Logo, saindo de E0, o número médio de transições ou disputas até alcançar F será dado pelo tempo médio entre retornos ao estado F menos 1. MAB-515 2010-1 4 2ª Questão: (25 pontos) (CMTC) Uma fila de atendimento num posto possui dois fiscais de plantão que atendem à fila simultaneamente. O tempo de atendimento de cada pessoa é exponencial com média 1 / µ . Os fregueses chegam à fila segundo um processo Poisson com taxa λ , mas desistem de esperar com probabilidade ( )1 kp− , onde k é o número de fregueses na fila da espera, e vão embora. Atenção, pois k = 0 quando há menos de 3 pessoas no posto. a) (5) Desenhe a cadeia de Markov cujo estado é o número de pessoas no posto. Se você não tiver certeza do seu desenho peça para confirmar e pague 2 pontos. Se estiver errado e solicitar mais uma confirmação, mais 2 pontos. Solução imediata são 5 pontos. Você não pode errar a solução deste item para não comprometer o restante da questão. b) (5) A fila é estável quando ela fica ociosa com probabilidade maior que zero. Qual a condição para a cadeia ter estados recorrentes positivos? Justifique. c) (5) Escreva o conjunto de equações para obtenção das probabilidades em equilíbrio. d) (5) Indique em função de 0 , 2λpi ρ µ= ,k e p a expressão fechada para , 2i ipi ≥ . Cuidado ao generalizar expressões. e) (5) Para as pessoas que decidem ficar e esperar por atendimento, calcule o tempo médio desde o instante de chegada até o instante de partida do posto em função de ipi . Solução: a) (5) b) (5) Existirá sempre um determinado i tal que 1, , 2 ipλ λ µ µ < ∀ ∀ finitos. Logo, , teremos 1, 2 Jp j iλ µ < ∀ > e então o sistema será sempre recorrente positivo, pois a tendência será da cadeia de Markov visitar os estados à esquerda em longo prazo, não importando a situação inicial das taxas para os estados com número de pessoas menor do que i O sistema será então sempre estável. Esta conclusão é intuitiva, pois à medida que a fila de espera aumenta, diminui a taxa de chegada de pessoas à fila de espera. O que acontece em um congestionamento de trânsito é semelhante. Quando há indicação de que o trânsito está congestionado, os motoristas tentam outras vias ou desistem e retornam para casa. Para qualquer estado j > i, o incremento médio de pessoas à fila é negativo, indicando que retornaremos a este estado com certeza no futuro. Logo, ele será recorrente. Havendo a solução por Foster podemos garantirque será recorrente positivo. Calcular as probabilidades será passo adiante, mas a solução do estado E0, embora exista, não é uma fórmula fechada. 0 1 3 2 5 4 λ λ λ pλ 2pλ µ 2µ 2µ 2µ 2µ (1) (2) (3) (4) (5) MAB-515 2010-1 5 c) (5) As equações podem ser obtidas pela igualdade de fluxos entre os estados em equilíbrio e usando a conservação de probabilidade. Usaremos 2 λρ µ = . 0 1 1 0 2 1 2 2 0 3 2 3 3 0 4 3 4 4 0 2 3 5 4 5 5 0 3 6 6 5 6 6 0 5 10 7 6 7 7 0 0 (1) 2 (2) 2 2 (3) 2 2 (4) 2 2 (5) 2 2 (6) 2 2 (7) 2 2 1i i p p p p p p p p λ pi µpi pi ρpi λ pi µpi pi ρ pi λ pi µpi pi ρ pi λ pi µpi pi ρ pi λ pi µpi pi ρ pi λ pi µpi pi ρ pi λ pi µpi pi ρ pi pi ∞ = = ∴ = = ∴ = = ∴ = = ∴ = = ∴ = = ∴ = = ∴ = =∑ � d) (5) Se representarmos a expressão para 02ka kk ppi ρ pi= , em função de ka , expoente do parâmetro p, então podemos ver que 1 3, 3.k ka a k k−= + − ≥ Então, ( 3)( 3 1) ( 3)( 2)1 2 3 4 ( 3) , 3 2 2k k k k k a k k− − + − −= + + + + + − = = ≥� . Podemos ver que 2 0a = , e a expressão fornece o valor corretamente. Então, ( 3)( 2) 2 02 , 2 k k k p kpi ρpi − − = ≥ e) (5) Devemos usar Little, [ ] [ ]E N E Tβ= , onde E[N] é o número médio de pessoas na fila e β é a taxa média de chegada de pessoas que não desistem. 2 3 0 1 2 3 4 5 1 2 3 4 1 0 1 0 1 0 1 0 1 2 2 2 2 (1 ) 2 2 [ ] [ ] 2 2 i i i i p p p E N i i E T β λpi λpi λpi λ pi λ pi λ pi µpi µpi µpi µpi µpi µ pi pi µ µpi µpi pi pi µ µpi µpi ∞ = ∞ = = + + + + + + = + + + + = + − − = − − = ∴ = − − ∑ ∑ � �
Compartilhar