PESQUISA OPERACIONAL II. Parte 2

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. Isso significa que 𝑝 = 0𝑖𝑗
(𝑛)
 
sempre que n não for divisível por t. 
 
 
PESQUISA OPERACIONAL II 
A B 
C 
0,8 
0,3 
0,7 
1 
0,2 
Prof. Airton Carneiro Prof. Francisco Pinheiro 
Com base nas definições dadas, uma cadeia de Markov 
finita não pode consistir em estados que sejam todos 
transientes porque, por definição, a propriedade transiente 
requer entrar em outros estados “capturadores” e, 
portanto, nunca poder voltar ao estado transiente. O 
estado “capturador” não precisa ser um único estado 
absorvente. Por exemplo, na cadeia: 
 
PESQUISA OPERACIONAL II 
Prof. Airton Carneiro Prof. Francisco Pinheiro 
Com base nas definições dadas, uma cadeia de Markov finita não 
pode consistir em estados que sejam todos transientes porque, por 
definição, a propriedade transiente requer entrar em outros estados 
“capturadores” e, portanto, nunca poder voltar ao estado transiente. 
O estado “capturador” não precisa ser um único estado absorvente. 
Por exemplo, na cadeia: 
 
PESQUISA OPERACIONAL II 
Prof. Airton Carneiro Prof. Francisco Pinheiro 
os estados 1 e 2 são transientes porque não podem ser entrados 
novamente uma vez que o sistema esteja “capturado” nos estados 3 e 
4. 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. Por definição, todos os estados de um conjunto 
fechado devem se comunicar, o que significa que é possível ir de 
qualquer estado a qualquer outro estado do conjunto em uma ou mais 
transições, ou seja, para todo i  j e n  1. Observe que os dois 
estados, 3 e 4, poderiam ser estados absorventes se p33 = p44 = 1. 
Nesse caso, cada estado forma um conjunto fechado. 
PESQUISA OPERACIONAL II 
Prof. Airton Carneiro Prof. Francisco Pinheiro 
Diz-se que uma cadeia de Markov fechada é ergódica se todos os 
seus estados forem recorrentes e aperiódicos (não periódicos). Nesse 
caso, as probabilidades absolutas após n transições, a(n) = a(0)Pn, 
sempre convergem exclusivamente para uma distribuição-limite 
(estado de equilíbrio) à medida que n  , que é independente das 
probabilidades iniciais a(0), como será demonstrado mais na frente. 
PESQUISA OPERACIONAL II 
Prof. Airton Carneiro Prof. Francisco Pinheiro 
Um exemplo de uma cadeia periódica e uma não periódica 
mostra-se no gráfico abaixo: 
PESQUISA OPERACIONAL II 
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. Essas classificações também podem ser vistas 
quando : lim
𝑛→∞ 
 𝑝 = 0𝑖𝑗
(𝑛)
 é calculado. Como 
Prof. Airton Carneiro Prof. Francisco Pinheiro 
consequentemente, isso mostra que, no longo prazo, a 
probabilidade de alguma vez voltar ao estado transiente 1 ou 2 é 
zero, ao passo que a probabilidade de ser “capturado” no estado 
absorvente 3 é certa. 
 
PESQUISA OPERACIONAL II 
Prof. Airton Carneiro Prof. Francisco Pinheiro 
Exemplo: Pode-se testar a periodicidade de um estado calculando 
Pn e observando os valores de para n = 2, 3, 4, .... Esses valores 
serão positivos somente no período correspondente ao estado. 
Considerando a cadeia: 
 
PESQUISA OPERACIONAL II 
Prof. Airton Carneiro Prof. Francisco Pinheiro 
Continuando com n = 6, 7, …. , Pn mostra que p11 e p33 são 
positivos com valores pares de n, e valor zero, caso contrário. Isso 
significa que o período para os estados 1 e 3 é 2. 
 
 
Problema: Classifique os estados das seguintes cadeias de 
Markov. Se um estado for periódico, determine seu período. 
 
 
PESQUISA OPERACIONAL II 
Prof. Airton Carneiro Prof. Francisco Pinheiro 
Problema: Dadas as seguintes matrizes, determine as classificações 
da cadeia e se são recorrentes. 
PESQUISA OPERACIONAL II 
Problema: Dadas as seguintes matrizes, determine seu período.