ModelagemdeSistemasDiscretosTP01_II

Prévia do material em texto

Modelagem de Sistemas Discretos
Universidade Veiga de Almeida – UVA
Curso de Engenharia de Produção
Profª Izabel Saldanha Matsuzaki, MSc. 
1) Cadeias de Markov
1.1) Processos estocásticos
“É uma coleção de variáveis aleatórias indexadas (𝑋 ), onde t é
um índice definido no conjunto T”. Dessa forma, entende‐se
que um processo estocástico é a descrição de um fenômeno
aleatório que varia com o tempo.
(HILLIER e LIEBERMAN, 2006)
Disciplina: Modelagem de Sistemas Discretos.
Prof. Izabel Saldanha Matsuzaki
Ponto de interesse: descrevem o comportamento de um sistema 
operando ao longo de um período.
1) Cadeias de Markov
1.1) Processos estocásticos
Disciplina: Modelagem de Sistemas Discretos.
Prof. Izabel Saldanha Matsuzaki
1) Cadeias de Markov
1.2) Distribuição de probabilidade
Seja (𝑡 , 𝑡 , … , 𝑡 ), com 𝑡 𝑡 ⋯ 𝑡 um conjunto discreto
de pontos de T, a distribuição conjunta do processo 𝑋 𝑡 nesses
pontos pode ser definida como:
𝑃 𝑋 𝑥 ,𝑋 𝑥 , … ,𝑋 𝑥
A probabilidade do processo estocástico estar no tempo t no
estado 𝑎 é chamada probabilidade de estado (𝑃 ). Essa
probabilidade é definida por:
𝑃 𝑃 𝑋 𝑎
Disciplina: Modelagem de Sistemas Discretos.
Prof. Izabel Saldanha Matsuzaki
1) Cadeias de Markov
1.2) Distribuição de probabilidade
O vetor p 𝑝 𝑝 … 𝑝 … é chamado vetor de
probabilidade de estado.
A probabilidade do processo estocástico (com tempo e estados
discretos) estar no estado j, dado que estava no estado i, é
chamada probabilidade de transição (𝑃 ), onde:
𝑃 𝑃 𝑋 𝑗|𝑋 𝑖
Disciplina: Modelagem de Sistemas Discretos.
Prof. Izabel Saldanha Matsuzaki
1) Cadeias de Markov
1.2) Distribuição de probabilidade
Uma hipótese que leva à tratabilidade analítica é a de que, o
processo estocástico é uma Cadeia de Markov, quando possui a
seguinte propriedade fundamental:
𝑃 𝑋 𝑗|𝑋 𝑘 ,𝑋 𝑘 , … ,𝑋 𝑘 𝑋 𝑖
𝑃 𝑋 𝑗|𝑋 𝑖 , ∀ 𝑡 0, 1, … . e toda sequência
𝑖, 𝑗,𝑘 ,𝑘 , … ,𝑘 .
Disciplina: Modelagem de Sistemas Discretos.
Prof. Izabel Saldanha Matsuzaki
Essa propriedade markoviana diz que a probabilidade condicional de 
qualquer “evento” futuro, dado quaisquer “eventos” passados e o estado 
presente 𝑿𝒕 𝒊, é independente dos eventos passados e depende apenas
do estado atual.
1) Cadeias de Markov
1.2) Distribuição de probabilidade
Contudo, se ocorrer a situação em que as probabilidades de
transição não mudam ao longo do tempo, então estas
probabilidades de transição são ditas estacionárias.
Simplificando a notação com probabilidades de transição
estacionárias, façamos:
𝑝 𝑃 𝑋 𝑗|𝑋 𝑖
A existência de probabilidade de transição (em uma etapa)
estacionária também implica o mesmo, para cada i, j e n (n = 0,
1, 2, ....). Considerando a notação anterior, temos:
Disciplina: Modelagem de Sistemas Discretos.
Prof. Izabel Saldanha Matsuzaki
1) Cadeias de Markov
1.2) Distribuição de probabilidade
𝑝 𝑃 𝑋 𝑗|𝑋 𝑖
Para todo t = 0, 1,.... essas probabilidades condicionais são
denominadas probabilidades de transição em n etapas.
Disciplina: Modelagem de Sistemas Discretos.
Prof. Izabel Saldanha Matsuzaki
ATENÇÃO:
Como as 𝑝 são probabilidades condicionais, elas tem 
que ser não‐negativas. Já que o processo deve realizar a 
transição para algum estado, elas devem satisfazer as 
seguintes propriedades:
𝑝 0; ∀ 𝑖 𝑒 𝑗;𝑛 0, 1, 2, …
∑ 𝑝 1 ; ∀ 𝑖 ;𝑛 0, 1, 2, …
1) Cadeias de Markov
1.3) Matriz de transição
Uma maneira conveniente de apresentar todas as
probabilidades de transição em n etapas é o formato de matriz:
Disciplina: Modelagem de Sistemas Discretos.
Prof. Izabel Saldanha Matsuzaki
1) Cadeias de Markov
1.3) Matriz de transição
Ou de modo equivalente:
Disciplina: Modelagem de Sistemas Discretos.
Prof. Izabel Saldanha Matsuzaki
1) Cadeias de Markov
1.4) Diagrama de Transição de Estados
Definição: é o grafo representativo do processo estocástico, onde o conjunto
de vértices está associado ao conjunto de estados (representado por
círculos). O conjunto de arcos/arestas, por sua vez, está associado as
possíveis transições e é valorado pelas probabilidades de transição.
Disciplina: Modelagem de Sistemas Discretos.
Prof. Izabel Saldanha Matsuzaki
1) Cadeias de Markov
1.5) Exemplos
1) O tempo na cidade de Niterói pode mudar de maneira
bastante rápida de um dia para o outro. Entretanto, as chances
de termos tempo seco (sem chuvas) amanhã são ligeiramente
maiores, caso esteja seco hoje do que se chover.
Particularmente, a probabilidade de termos tempo seco
amanhã é de 0,8, caso hoje esteja seco, porém é de apenas 0,6,
caso hoje chova. Essas probabilidades não mudam, se as
informações sobre o tempo antes de hoje também forem
levadas em consideração.
Disciplina: Modelagem de Sistemas Discretos.
Prof. Izabel Saldanha Matsuzaki
1) Cadeias de Markov
1.5) Exemplos
Continuação...) Começando em um dado dia inicial (chamado aqui de dia 0),
o tempo é observado em cada dia t = 0, 1, 2, ..... O estado do sistema no dia t
pode ser:
Disciplina: Modelagem de Sistemas Discretos.
Prof. Izabel Saldanha Matsuzaki
Estado 0 = Dia t é seco
ou
Estado 1 = Dia t é com chuva.
𝑋 0 𝑠𝑒 𝑜 𝑑𝑖𝑎 𝑡 𝑒𝑠𝑡𝑖𝑣𝑒𝑟 𝑠𝑒𝑐𝑜1 𝑠𝑒 𝑛𝑜 𝑑𝑖𝑎 𝑡 𝑒𝑠𝑡𝑖𝑣𝑒𝑟 𝑐ℎ𝑜𝑣𝑒𝑛𝑑𝑜
Dessa forma, para t = 0, 1, 2, .... A variável aleatória 𝑋 assume os seguintes 
valores: 
1) Cadeias de Markov
1.5) Exemplos
Continuação ex:1..)
A partir das informações apresentadas, responda:
Quais são as probabilidades de transição? Monte a matriz de
transição.
Disciplina: Modelagem de Sistemas Discretos.
Prof. Izabel Saldanha Matsuzaki
𝑝 𝑃 𝑋 0 𝑋 0 0,8
𝑝 𝑃 𝑋 0 𝑋 1 0,6
∀ 𝑡 0, 1, 2, … .
Além disso:
𝑝 𝑝 1
𝑝 𝑝 1
logo: 𝑝 1 0,8 0,2
𝑝 1 0,6 0,4
1) Cadeias de Markov
1.5) Exemplos
Continuação ex:1..)
Portanto a matriz de transição será igual a :
Disciplina: Modelagem de Sistemas Discretos.
Prof. Izabel Saldanha Matsuzaki
0 1
𝑝 0,8
𝑝 0,4
𝑝 0,2
𝑝 0,6
1) Cadeias de Markov
1.5) Exemplos
2) Suponha a existência de três possíveis classificações sociais para
um indivíduo de uma população: classes A, B e C. A probabilidade de
um indivíduo sair da classe C e ir para a classe B pode ser
determinada por estudos estatísticos que observem a taxa de
indivíduos que, ao longo de um determinado período, migram entre
essas classes. Sabe‐se que não é possível a migração de um indivíduo
da classe C para a A, contudo 10% da população consegue melhorar
sua posição social e migrar para a classe B. Além disso, os relatórios
apresentaram os mesmos percentuais quando ocorre o downgrade
das classes A e B, ou seja, iguais a 50%. Algo semelhante ocorre
quando estes indivíduos conseguem permanecer em suas classes,
sem sofrer este downgrade, isto é, algo em torno de 30%. A partir
dessas informações, apresente a matriz e o diagrama de transição
com os respectivos valores das probabilidades de transição.
Disciplina: Modelagem de Sistemas Discretos.
Prof. Izabel Saldanha Matsuzaki
1) Cadeias de Markov
1.5) Exemplos
2) Suponha a existência de três possíveis classificações sociais para
um indivíduo de uma população: classes A, B e C. A probabilidade de
um indivíduo sair da classe C e ir para a classe B pode ser
determinada por estudos estatísticos que observem a taxa de
indivíduos que, ao longo de um determinado período, migram entre
essas classes. Sabe‐se que não é possível a migração de um indivíduo
da classe C para a A, contudo, 10% da população consegue melhorar
sua posição social e migrar para a classe B. Além disso, os relatórios
apresentaram os mesmos percentuais quando ocorre o downgrade
das classes A e B, ou seja, iguais a 50%. Algo semelhante ocorre
quando estes indivíduos conseguem permanecer em suas classes,
sem sofrer este downgrade, isto é, algo em torno de 30%. A partir
dessas informações, apresente a matriz e o diagrama de transição
com os respectivos valores das probabilidades de transição.
Disciplina: Modelagem de Sistemas Discretos.
Prof. Izabel Saldanha Matsuzaki
1) Cadeias de Markov
1.5) Exemplos
2) Resolução:
Disciplina: Modelagemde Sistemas Discretos.
Prof. Izabel Saldanha Matsuzaki
𝑋
0, 𝑠𝑒 𝑜 𝑖𝑛𝑑í𝑣𝑖𝑑𝑢𝑜 𝑒𝑠𝑡𝑖𝑣𝑒𝑟 𝑛𝑎 𝑐𝑙𝑎𝑠𝑠𝑒 𝐴
1, 𝑠𝑒 𝑜 𝑖𝑛𝑑𝑖𝑣í𝑑𝑢𝑜 𝑒𝑠𝑡𝑖𝑣𝑒𝑟 𝑛𝑎 𝑐𝑙𝑎𝑠𝑠𝑒 𝐵
2, 𝑠𝑒 𝑜 𝑖𝑛𝑑𝑖𝑣í𝑑𝑢𝑜 𝑒𝑠𝑡𝑖𝑣𝑒𝑟 𝑛𝑎 𝑐𝑙𝑎𝑠𝑠𝑒 𝐶
𝑝 𝑃 𝑋 0 𝑋 2 0
𝑝 𝑃 𝑋 1 𝑋 2 0,1
𝑝 𝑃 𝑋 1 𝑋 1 0,5
𝑝 𝑃 𝑋 2 𝑋 1 0,5
𝑝 𝑃 𝑋 0 𝑋 0 0,3
𝑝 𝑃 𝑋 1 𝑋 1 0,3
𝑃
0
1
2
0,3 0,5
0,3 0,5
0 0,1
0 1 2
𝑃
0
1
2
0,3 0,5 0,2
0,2 0,3 0,5
0 0,1 0,9
0 1 2
1) Cadeias de Markov
1.5) Exemplos
2)
Disciplina: Modelagem de Sistemas Discretos.
Prof. Izabel Saldanha Matsuzaki
0,2
0,3
1) Cadeias de Markov
1.5) Exemplos
3)
Disciplina: Modelagem de Sistemas Discretos.
Prof. Izabel Saldanha Matsuzaki
1) Cadeias de Markov
1.5) Exemplos
3) Resposta:
a) Desde que a probabilidade do tempo de amanhã seja
dependente apenas do tempo de hoje, a propriedade
Markoviana é válida para a evolução do tempo.
b) Seja 𝑋 0 𝑠𝑒 𝑜 𝑑𝑖𝑎 𝑡 𝑒𝑠𝑡𝑖𝑣𝑒𝑟 𝑐ℎ𝑢𝑣𝑜𝑠𝑜1 𝑠𝑒 𝑛𝑜 𝑑𝑖𝑎 𝑡 𝑒𝑠𝑡𝑖𝑣𝑒𝑟 𝑠𝑒𝑐𝑜 𝑜𝑢 𝑐𝑙𝑎𝑟𝑜
Então 𝑃 0,5 0,50,1 0,9
Disciplina: Modelagem de Sistemas Discretos.
Prof. Izabel Saldanha Matsuzaki
1) Cadeias de Markov
1.5) Exemplos
4) (Questão da avaliação A1/2018) O centro de computação da
Universidade de Harvard tem experimentado o tempo de
inatividade do computador. Suponhamos que as tentativas de
um processo de Markov associado sejam definidas como
períodos de uma hora e que a probabilidade de o sistema estar
em um estado em execução ou em estado inativo seja baseada
no estado do sistema no período anterior. Dados históricos
mostram as seguintes probabilidades de transição:
Disciplina: Modelagem de Sistemas Discretos.
Prof. Izabel Saldanha Matsuzaki
a) Se o sistema estiver executando inicialmente, qual é a probabilidade de o
sistema estar inativo na próxima hora de operação?
1) Cadeias de Markov
1.5) Exemplos/exercício
5) Suponha que temos um modelo de mercado de ações de
modo que o fato de a ação subir amanhã depende se ela
aumentou hoje e ontem. Particularmente, se a ação tiver
subido nos últimos dois dias, ela subirá amanhã com
probabilidade 0,9. Se a ação subiu hoje, mas caiu ontem, então
ela subirá amanhã com probabilidade 0,6. Se a ação caiu hoje,
porém subiu ontem, então ela subirá amanhã com
probabilidade 0,5. Finalmente, se a ação caiu nos últimos dois
dias, então ela subirá amanhã com probabilidade 0,3. A partir
dessas informações apresente a matriz de transição e as
respectivas probabilidades de transição.
Disciplina: Modelagem de Sistemas Discretos.
Prof. Izabel Saldanha Matsuzaki
1) Cadeias de Markov
1.5) Exemplos/exercício
5)
Disciplina: Modelagem de Sistemas Discretos.
Prof. Izabel Saldanha Matsuzaki
Referências
• HILLIER, F.S.; LIEBERMAN, G.J. Introdução à pesquisa
operacional. 9. ed. São Paulo: MCGRAW‐HILL Brasil, 2013.
https://integrada.minhabiblioteca.com.br/#/books/9788580
551198/cfi/714!/4/4@0.00:4.87
• TAHA, Hamdy A. Pesquisa operacional. São Paulo: Pearson
Prentice Hall, 2008.
Disciplina: Modelagem de Sistemas Discretos.
Prof. Izabel Saldanha Matsuzaki