PESQUISA OPERACIONAL II. Parte 2 (MARKOV)

Prévia do material em texto

Prof. Airton Carneiro Prof. Francisco Pinheiro 
PESQUISA OPERACIONAL II 
Denomina-se processos estocásticos àqueles processos que 
evoluem no tempo de forma probabilística, podendo ser 
classificados em relação ao Estado ou ao Tempo: 
 
Em relação ao Estado: 
 Estado Discreto (cadeia): X(t) é definido sobre um conjunto 
enumerável ou finito. 
 Estado Contínuo (sequência): X(t) caso contrário. 
 
Em relação ao Tempo (Parâmetro): 
 Tempo Discreto: “t” é finito ou enumerável. 
 Tempo Contínuo: “t” caso contrário. 
PROCESSOS ESTOCÁSTICOS 
Prof. Airton Carneiro Prof. Francisco Pinheiro 
PESQUISA OPERACIONAL II 
Exemplos: 
 Número de usuários em uma fila de banco em um determinado 
instante: Estado Discreto e Tempo Contínuo. 
 Índice pluviométrico diário: Estado Contínuo e Tempo Discreto. 
 Número de dias chuvosos: Estado Discreto e Tempo Discreto. 
 
Se o estado em que se encontra o processo estocástico depende só 
do estado anterior, mas não dos anteriores a esse, estaremos ante 
um processo de Markov. 
PROCESSOS ESTOCÁSTICOS 
Prof. Airton Carneiro Prof. Francisco Pinheiro 
Em matemática, a cadeia de Markov é um caso particular de 
processo estocástico com estados discretos (o parâmetro, em geral o 
tempo, pode ser discreto ou contínuo) e apresenta a propriedade 
Markoviana, chamada assim em homenagem ao matemático russo 
Andrei Andreyevich Markov. A definição desta propriedade, 
também chamada de memória markoviana, é que os estados 
anteriores são irrelevantes para a predição dos estados seguintes, 
desde que o estado atual seja conhecido. 
PESQUISA OPERACIONAL II 
CADEIAS DE MARKOV 
Prof. Airton Carneiro Prof. Francisco Pinheiro 
Um processo estocástico é um Processo de Markov se a ocorrência 
de um estado futuro depender de somente do estado imediatamente 
precedente. 
A matriz P (em notação matricial, qualquer letra maiúscula em 
negrito representa uma matriz) define a denominada cadeia de 
Markov. 
PESQUISA OPERACIONAL II 
CADEIAS DE MARKOV 
Prof. Airton Carneiro Prof. Francisco Pinheiro 
PESQUISA OPERACIONAL II 
Representação de uma Cadeia de Markov: 
 
As representações mais comuns de uma cadeia de Markov são a 
notação matricial e o diagrama de estado. Vejamos o exemplo: 
Suponhamos que o tempo em uma região geográfica é classificado 
como Sol, Nublado ou Chuva, em um determinado dia, assim a 
matriz P do problema é: 
Prof. Airton Carneiro Prof. Francisco Pinheiro 
De forma equivalente, o diagrama de estado seria: 
PESQUISA OPERACIONAL II 
0,1
0,2
0,4
0,2
0,5
0,5
0,4
Sol
Chu
va
Nub
lado
0,4
0,3
Prof. Airton Carneiro Prof. Francisco Pinheiro 
PESQUISA OPERACIONAL II 
Probabilidades de Transição em n-etapas e Absolutas 
Dadas as probabilidades iniciais a(0) = {aj
(0)} de iniciar no estado “j” 
e a matriz de transição P de uma cadeia de Markov, as 
probabilidades absolutas a(n) = {aj
(n)} de estar no estado “j” após 
“n” transições (n > 0) são calculadas da seguinte maneira: 
 
a(1) = a(0)P 
 a(2) = a(1)P = a(0)PP = a(0)P2 
 a(3) = a(2)P = a(0)P2P = a(0)P3 
 A matriz Pn é conhecida como matriz de transição em n etapas. 
Pelos cálculos anteriores, temos: 
 Pn = Pn - 1 P, ou de forma geral: 
Pn = Pn - m Pm, 0 < m < n 
 
 
 
Prof. Airton Carneiro Prof. Francisco Pinheiro 
PESQUISA OPERACIONAL II 
Exemplo – O problema do Jardineiro: 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 cai em um dos três 
estados: 1 – bom; 2 – razoável; 3 – ruim. Ao longo dos anos, o 
jardineiro observou que a condição do solo no ano anterior causava 
um impacto sobre a produtividade no ano corrente e que a situação 
podia ser descrita pela seguinte cadeia de Markov: 
Prof. Airton Carneiro Prof. Francisco Pinheiro 
Na matriz mostrada acima, se observa que as probabilidades de 
transição neste ano mostram que a condição do solo pode se 
deteriorar ou se manter, mas nunca melhorar. Se a condição do solo 
neste ano for boa (estado 1), há 20% de chances de não mudar no 
ano seguinte, 50% de chance de se tornar razoável (estado 2) e 
30% de chance de deteriorar até uma condição ruim (estado 3). Se 
a condição do solo neste ano for razoável (estado 2), a 
produtividade não tem chances de no próximo ano passar a ser boa, 
a produtividade no ano seguinte pode permanecer razoável com 
probabilidade 0,5 ou tornar-se ruim (estado 3), também com 
probabilidade 0,5. Por fim, uma condição ruim neste ano (estado 3) 
só pode resultar em igual condição no próximo ano (isso implica que 
a probabilidade de ser ruim seja 1). 
PESQUISA OPERACIONAL II 
Prof. Airton Carneiro Prof. Francisco Pinheiro 
PESQUISA OPERACIONAL II 
O jardineiro pode alterar as probabilidades de 
transição P (para o próximo ano) usando 
fertilizante para melhorar a condição do solo. 
Nesse caso, a matriz de transição se torna: 
Prof. Airton Carneiro Prof. Francisco Pinheiro 
PESQUISA OPERACIONAL II 
 
 
a) Se a condição do solo é boa, isto é, a(0) = (1, 0, 0), determine as 
probabilidades absolutas dos três estados do sistema após 1 ano 
usando fertilizantes. 
b) Se a condição do solo é boa, isto é, a(0) = (1, 0, 0), determine as 
probabilidades absolutas dos três estados do sistema após 4 anos 
usando fertilizantes. 
c) Se a condição do solo é boa, isto é, a(0) = (1, 0, 0), determine as 
probabilidades absolutas dos três estados do sistema após 1 ano 
sem usar fertilizantes. 
d) Se a condição do solo é boa, isto é, a(0) = (1, 0, 0), determine as 
probabilidades absolutas dos três estados do sistema após 4 anos 
sem usar fertilizantes. 
 
Prof. Airton Carneiro Prof. Francisco Pinheiro 
PESQUISA OPERACIONAL II 
Solução: 
a) Usando fertilizantes, as probabilidade absolutas após 1 ano 
serão: 
 
Portanto, após 1 ano teremos: a(1) = a(0)P 
Prof. Airton Carneiro Prof. Francisco Pinheiro 
PESQUISA OPERACIONAL II 
Solução: 
b) Usando fertilizantes, as probabilidades absolutas após 4 anos 
serão: 
Portanto, após 4 anos teremos: a(4) = a(0)P4 
Prof. Airton Carneiro Prof. Francisco Pinheiro 
PESQUISA OPERACIONAL II 
Exemplo: Um professor de engenharia compra um novo computador 
a cada dois anos e tem preferência por três modelos: M1, M2 e M3. 
Se o modelo atual for M1, o próximo computador pode ser M2 com 
probabilidade 0,2 ou M3 com probabilidade 0,15. Se o modelo 
atual for M2, as probabilidades de trocar para M1 e M3 são 0,6 e 
0,25, respectivamente, e, se o modelo atual for M3, então as 
probabilidades de trocar para M1 e M2 são 0,5 e 0,1, 
respectivamente. 
Represente a situação como uma cadeia de Markov. 
 
Prof. Airton Carneiro Prof. Francisco Pinheiro 
PESQUISA OPERACIONAL II 
Exemplo: 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á 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 contrario, 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. Expresse as atividades 
probabilísticas da patrulha policial sob a forma de uma matriz de 
transição. 
 
 
Prof. Airton Carneiro Prof. Francisco Pinheiro 
PESQUISA OPERACIONAL II 
Exemplo: Pacientes que sofrem de falência renal podem fazer um 
transplante ou hemodiá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 
rins de doadores vivos voltam à hemodiálise. As porcentagens de 
óbitos entre os dois grupos são 20% e 10%, respectivamente. Entre 
os que continuam com a hemodiálise, 10% morrem, e, entre os que 
sobrevivem mais de um ano após o transplante, 5% morrem e 5% 
voltam hemodiálise. Represente a situação como uma cadeia de 
Markov. 
 
 
Prof. Airton Carneiro Prof. Francisco Pinheiro 
PESQUISA OPERACIONAL II 
Problema1: Analisando o problema do professor ao comprar um 
computador, determine a probabilidade de o professor comprar o 
modelo corrente dentro de quatro anos. 
 
Problema2: Analisando o problema do carro de polícia. Se no 
momento em questão o carro de polícia estiver em uma cena para 
onde foi chamado, determine a probabilidade de ocorrer uma prisão 
em duas patrulhas. 
 
Problema 3: Analisando o problema do paciente em hemodiálise: 
(a) Para um paciente que está atualmente em dialise, qual é a 
probabilidade de receber um transplante em dois anos? 
(b) Para um paciente que atualmente sobrevive há mais de um ano, 
qual é a probabilidade de sobreviver mais quatro anos? 
 
 
 
Prof. Airton Carneiro Prof. Francisco Pinheiro 
CLASSIFICAÇÃO DOS ESTADOS EM UMA CADEIA DE MARKOV 
Os estados de uma cadeia de Markov podem ser classificado com 
base na probabilidade de transição de P. 
 
 1. Um estado j é dito accessível a partir do estado i, se para algum 
n  0. Lembre que é simplesmente a probabilidade condicional de se 
encontrar no estado j após n-etapas, partindo do estado i. 
 
 
 2. Os estados i e j se dizem comunicantes se a partir do estado i se 
alcança o estado j e se a partir do estado j se alcança o estado i. 
 
 
 3. Quando dois estados se comunicam, se diz que eles pertencem à 
mesma classe. 
 
 
PESQUISA OPERACIONAL II 
A B 
P > 0 
A B 
Prof. Airton Carneiro Prof. Francisco Pinheiro 
CLASSIFICAÇÃO DOS ESTADOS EM UMA CADEIA DE MARKOV 
 
 4. Se todos os estados são comunicantes, portanto todos pertencem a 
uma única classe, a cadeia de Markov é dita de irredutível. 
 
PESQUISA OPERACIONAL II 
0,1
0,2
0,4
0,2
0,5
0,5
0,4
Sol
Chu
va
Nub
lado
0,4
0,3
Prof. Airton Carneiro Prof. Francisco Pinheiro 
5. Um estado i é absorvente se retornar para ele mesmo, com 
certeza, em uma transição, isto é, = 1. 
 
 
 
 
 
6. Um estado é transiente se a partir de um estado i puder alcançar 
um estado j, mas a partir do estado j não puder voltar ao mesmo 
estado i em que estava. 
 
PESQUISA OPERACIONAL II 
A B 
C D 
Prof. Airton Carneiro Prof. Francisco Pinheiro 
 7. Um estado j é recorrente se a probabilidade de voltar ao estado 
j em que estava com base em outros estados for 1. Isso pode 
acontecer se, e somente se, o estado não for transiente. 
 
 
 
 
 
8. Um estado j é periódico com período t > 1 se um retorno só for 
possível em t, 2t, 3t, .... etapas. 
 
PESQUISA OPERACIONAL II 
A B 
C 
0,8 
0,3 
0,7 
1 
0,2 
Prof. Airton Carneiro Prof. Francisco Pinheiro 
Analisando a seguinte cadeia de markov temos: 
 
PESQUISA OPERACIONAL II 
1 2 
3 4 
1 
1 
0,3 
0,6 
0,4 
0,7 
Prof. Airton Carneiro Prof. Francisco Pinheiro 
PESQUISA OPERACIONAL II 
1 2 
3 4 
1 
1 
0,3 
0,6 
0,4 
0,7 
Os estados 1 e 2 são transientes porque não podem retornar. Os 
estado 3 e 4 que, de certo modo, desempenham o papel de um 
estado absorvente (mas não são estados absorventes), constituem um 
conjunto fechado. 
Prof. Airton Carneiro Prof. Francisco Pinheiro 
Ex: Considere a seguinte cadeia de Markov para os estados 1 e 2 
(caso do jardineiro): 
PESQUISA OPERACIONAL II 
Os estados 1 e 2 são transientes porque alcançam o estado 3 mas 
nunca podem voltar ao estado anterior. O estado 3 é absorvente 
porque p33 = 1. 
1 2 
3 
0,5 0,5 
1 
0,2 
0,3 
0,5 
Prof. Airton Carneiro Prof. Francisco Pinheiro 
PROBABILIDADES DE ESTADO NO EQUILÍBRIO E TEMPOS 
MÉDIOS DE RETORNO 
PESQUISA OPERACIONAL II 
P= 
P2= = 
P4= = 
Prof. Airton Carneiro Prof. Francisco Pinheiro 
PROBABILIDADES DE ESTADO NO EQUILÍBRIO E TEMPOS 
MÉDIOS DE RETORNO 
PESQUISA OPERACIONAL II 
P8= = = 
As probabilidades de estado no equilíbrio são definidas por: 
 = P 
1j
j

n......,,2,1j,
1
j
ji 


Tempo médio do primeiro retorno ou tempo médio de recorrência 
Prof. Airton Carneiro Prof. Francisco Pinheiro 
Exemplo: Em um domingo ensolarado de primavera, o MiniGolf 
pode obter R$ 2.000 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 
amanha 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 o número médio de dias em que o tempo não estará 
ensolarado. 
 
PESQUISA OPERACIONAL II 
Prof. Airton Carneiro Prof. Francisco Pinheiro 
Exemplo: Joe adora jantar em restaurantes de comida típica. Seus 
pratos favoritos são os mexicanos, italianos, chineses e tailandeses. 
Na média, ele paga R$ 10,00 por uma refeição mexicana, R$ 
15,00 por uma refeição italiana, R$ 9,00 por uma refeição chinesa 
e R$ 11,00 por uma refeição tailandesa. Os hábitos alimentares de 
Joe são previsíveis: há 70% de chance de a refeição de hoje ser 
uma repetição da de ontem e probabilidades iguais de trocar para 
uma das três restantes. 
(a) Expresse o problema como uma cadeia de Markov 
(b) Quanto Joe pagará em média por seu jantar diário? 
 
PESQUISA OPERACIONAL II 
Prof. Airton Carneiro Prof. Francisco Pinheiro 
Exemplo: Há três categorias de contribuintes do lmposto de Renda nos Estados 
Unidos: os que nunca sonegam impostos, os que sonegam as vezes e os que 
sempre sonegam. Um exame de auditorias de declarações de lmposto de Renda 
de um ano para o ano seguinte mostra que 95% dos que não sonegaram 
impostos no ano anterior continuam na mesma categoria no ano corrente, 4 % 
passam para a categoria “às vezes” e o restante passa para a categoria 
“sempre”. No caso dos que sonegam as vezes, 6% passam para “nunca”, 90°/o 
continuam na mesma categoria e 4% passam para “sempre”. Quanto aos que 
“sempre” sonegam, as porcentagens respectivas são 0%, 10% e 90%. 
(a) Expresse o problema como uma cadeia de Markov. 
(b) No longo prazo, quais seriam as porcentagens de sonegadores nas 
categorias “nunca”, “às vezes” e “sempre”? 
(c) Estatísticas mostram que o contribuinte da categoria “às vezes” sonega 
impostos de aproximadamente R$ 5.000 por declaração, e os da categoria 
“sempre”, de aproximadamente R$ 12.000. Considerando uma taxa de imposto 
sobre a renda de 12% e uma população de contribuintes de 70 milhões, 
determine a redução anual no recolhimento de impostosdevida a sonegação. 
PESQUISA OPERACIONAL II 
Prof. Airton Carneiro Prof. Francisco Pinheiro 
Solução: 
PESQUISA OPERACIONAL II 
a) 
b) 
Assim, no estado de equilibrio: nunca = 44,12%, 
as vezes 36,76%, sempre 19,12% 
Prof. Airton Carneiro Prof. Francisco Pinheiro 
Continuação: 
PESQUISA OPERACIONAL II 
c) A sonegação esperada de impostos/ano = 0,12 [ 
(0,4412)(70106)(0) + (0,3676)( 70106)(5.000) + (0,1912)( 
70106)(12.000) ] 
= 34.712.1641.097,07