Aula Teorica03

Prévia do material em texto

Pesquisa 
Operacional -
Simulação
Markov, filas e simulação de 
Monte Carlo
Prof. Henrique G. R. Chiavelli
• Unidade de Ensino: 03 – Markov, filas e simulação de Monte Carlo.
• Competência da Unidade: Compreender os conceitos de Cadeias de Markov, a 
Teoria das Filas e o método de simulação conhecido como Monte Carlo.. 
• Resumo: Cadeias de Markov – simulação; Teoria das filas – simulação; O método de 
Monte Carlo.
• Palavras-chave: Markov; Teoria das Filas; Simulação; Método; Monte Carlo.
• Título da Teleaula: Markov, filas e simulação de Monte Carlo.
• Teleaula nº: 03
Conteúdo – Aula 3
Unidade 3 - Markov, filas e simulação de Monte Carlo
Seção 3.1 - Cadeias de Markov – simulação
Seção 3.2 - Teoria das filas – simulação
Seção 3.3 - O método de Monte Carlo
Contextualização
Cadeias de Markov
Teoria das Filas
Método Monte 
Carlo
Cadeias de 
Markov -
Simulação
Cadeias de Markov
Cadeias de Markov são processos estocásticos com propriedade
markoviana em um espaço de estados discretos.
A previsão de demanda pode ser compreendida
como uma Cadeia de Markov, pois sua demanda
futura independe da demanda histórica, mas
somente ao estado atual.
Como propriedade markoviana entendemos os processos que não
dependem do que ocorreu tempos atrás para chegar ao estado
futuro, mas somente ao seu atual estado e o imediatamente anterior.
Cadeias de Markov
Cadeia de Markov com tempo discreto: Espaço de parâmetros:
discreto. Espaço de estados: discreto.
Processo de Markov com tempo discreto: Espaço de parâmetros:
discreto. Espaço de estados: contínuo.
Cadeia de Markov com tempo contínuo: Espaço de
parâmetros: contínuo. Espaço de estados: discreto.
Processo de Markov com tempo contínuo: Espaço de 
parâmetros: contínuo. Espaço de estados: contínuo.
Aplicações de cadeias de Markov
Através dos fundamentos da Cadeia de Markov é
possível simular a evolução das participações de
mercados de empresas concorrentes entre si,
desde que seja conhecida a participação inicial e a
matriz de probabilidade de transição de uma
marca para outra.
Cadeias de Markov também são utilizadas em
problemas envolvendo a simulação de estoques.
https://images.app.goo.gl/e5pQ9PabypcTbE7x7
Aplicações de cadeias de Markov
Ruína do apostador:
Considere um apostador apostando no resultado de uma 
sequência de lançamentos independentes de uma moeda 
justa. Se der cara, ele acrescenta um valor à sua carteira. 
Se a moeda der coroa, ele perde o mesmo valor. 
Se ele conseguir uma fortuna de um valor
predeterminado por ele, o apostador irá parar
de jogar. Se a carteira dele estiver vazia, ele
deve parar de apostar.
Aplicações de cadeias de Markov
Ruína do apostador:
A situação do apostador pode ser modelada, e 
simulada, e duas questões poderão ser respondidas:
Quanto tempo levará para o jogador chegar a 
uma das duas situações possíveis?
Quais são as probabilidades das duas 
possibilidades?
Fonte: https://goo.gl/images/nPuiKg
Situação-Problema
Por não possuir informações referente ao novo
produto, a diretoria entende que poderá utilizar
algumas informações de produtos muito similares
ao novo para começarem a compreender o
comportamento do mercado e prever a demanda
desse novo produto.
A diretoria de uma empresa do setor metal-mecânico deseja
saber qual a demanda mais provável de seu novo produto a ser
lançado nos próximos três meses.
Situação-Problema
O primeiro mês tem 35% de chance de ter uma
demanda de até 3000 unidades (considerado pela
diretoria como sendo de alta demanda) e 65% de ter
uma demanda de até 1000 unidades (baixa demanda).
O estudo também indicou que caso a demanda seja
alta, a imediatamente posterior tem probabilidade de
75% de ser alta e 25% de ser baixa, mas se a demanda
for baixa, a imediatamente posterior terá 50% de ser
alta e 50% de ser baixa.
Situação-Problema
O desafio no cenário descrito é de prever a
demanda do produto mais provável, e para isso
você deverá utilizar o modelo da Cadeia de
Markov para construir a matriz de probabilidade
de transição e simular a demanda mais provável
dos três primeiros meses.
Situação-Problema
Para solucionar o problema, inicialmente é preciso 
montar a matriz de probabilidade de transição:
Fonte: LD. Pg. 126
Situação-Problema
Para calcularmos a demanda, aplicaremos:
Para o primeiro mês:
Para o segundo mês:
Para o terceiro mês:
Fonte: LD. Pg. 127
Resolvendo a Situação-Problema
Para o primeiro mês:
Resolvendo a Situação-Problema
Para o segundo mês:
= =
X
=
=
Resolvendo a Situação-Problema
Para o terceiro mês
=
=
=
X =
Resolvendo a Situação-Problema
Calculando a multiplicação das matrizes temos:
Para o primeiro mês teremos 58,75% de termos alta
demanda e 41,25% de termos baixa demanda.
No segundo mês, serão 64,69% a chance de ter alta demanda
e 35,31% de termos baixa demanda.
E no terceiro mês, a probabilidade de termos
alta demanda é de 66,17% e de baixa demanda
é de 33,83%.
Teoria das Filas -
Simulação
Teoria das Filas
Em linhas de produção de empresas manufatureiras, a formação de filas,
ou congestionamentos, ocorre devido à falta de balanceamento no
sistema, ou seja, não está devidamente dimensionado (PRADO, 2014).
Fonte: Prado (2014).
Esses 
congestionamentos 
são conhecidos 
como gargalos
Principais características de uma fila
Os principais fatores que interferem a operação de
um sistema, afetando o seu desempenho, podem
ser classificados em quatro categorias:
Modo de chegada
Forma do atendimento
Disciplina da fila
Estrutura do sistema
Fonte: https://images.app.goo.gl/PsMsudbQq4rTSFAL9
Modo de chegada
Quantos “clientes” chegam por tempo ao meu sistema no tempo (0,T)?
A chegada é dada por uma média, representada por (λ);
Essas chegadas podem ser em grupos ou individuais.
Fonte: Prado (2014).
Modo de chegada
No processo de Poisson, as médias de chegadas são dadas por (λ);
A distribuição de Poisson nos permite calcular a probabilidade de ocorrer as 
chegadas P(x);
x= número de chegadas por unidade de tempo para (x = 0, 1, 2, 3, 4, 5, ...)
Fonte: Prado (2014).
= taxa de chegada (nº médio de 
chegadas em determinado tempo)
X! = fatorial de x
Forma do atendimento (λ)
Quando a população é finita, a taxa de chegada 
dependerá da população;
População Finita – taxa de chegada variável;
População Infinita – taxa de chegada constante;
Taxas das chegadas (λ): Número médio 
de clientes que chegam 
procurando o serviço 
por unidade de tempo. 
https://images.app.goo.gl/cccss15sDTEKn9wL6
A disciplina da fila
Primeiro a chegar é o primeiro a ser atendido (FCFS);
Último a chegar primeiro a ser atendido (LCFS);
Atendimentos aleatórios (SIRO).
Atendimentos prioritários (idosos, grávidas, etc.).
Menor Tempo de Processamento (MTP);
Data Devida (DD).
https://images.app.goo.gl/TNakKarWTdpFtNXn6
Estrutura do sistema:
É a quantidade de servidores (Unidade de atendimento + 
capacidade da fila de espera);
Taxa de serviço (µ): Número médio de clientes que podem ser 
atendidos por cada servidor por unidade de tempo. 1/µ é a 
duração média do serviço;
A capacidade máxima pode ser limitada;
Sistemas com filas de capacidade infinita, todos os 
clientes serão atendidos.
Estrutura do sistema
Sistema com uma fila e um posto de atendimento
Sistema com uma fila e três postos de atendimento
Estrutura do sistema
Sistema complexo de fila
Estrutura do sistema
O modelo de fila mais simples é representado como:
A / B / m
• A refere-se a distribuição de probabilidade do processo de chegada.
• B representa a distribuição do tempo de atendimento.
• m seria o número de postos de atendimentos.
Portanto, uma fila representada por M /M / 1 indica que 
a chegada dos clientes corresponde a uma distribuição 
exponencial, bem como o tempo de atendimento, com 
somente um posto de atendimento no sistema.
Conceitos fundamentais das filas M/M/1
Distribuição exponencial é consistente 
com chegadas aleatórias;
Processo de Poisson é um tipo especial de processode contagem de chegadas no qual algumas hipóteses 
devem ser satisfeitas (FERREIRA FILHO, 2013):
Incrementos independentes;
Independência do tempo;
Não ocorrem chegadas simultâneas.
Exemplo: cálculo de chegadas
Em um lava jato, em média chegam por hora três carros (λ= 3) . 
Após uma campanha publicitária, o proprietário quer saber a 
probabilidade de começar a chegar 5 carros por hora (x = 5).
Fonte: Prado (2014).Fonte: Prado (2014).
Capacidade do sistema
Se λ > μ, ou seja, se a taxa de chegada for maior
que a taxa de atendimento, nossa fila tenderá ao
∞ (infinito);
Se μ > λ: quanto menor esta relação, menor será
o tamanho da fila.
https://images.app.goo.gl/A9Cru7MFip2mHCM88
A Probabilidade de que o sistema esteja ocupado é dada 
pela taxa de ocupação do sistema (ρ), quando, no sistema, 
tem somente um canal de atendimento, temos:
Medidas de desempenho em simulação de teoria das filas
• O tempo em que o posto de atendimento permanece ocioso ou ocupado.
• O tempo médio que cada cliente gasta na fila de espera.
• O tempo médio gasto pelo cliente no sistema, ou seja, a média dos tempos 
computados desde o instante de entrada até o momento de saída.
• O número médio de clientes na fila, por unidade de tempo (tamanho médio da 
fila).
• O número médio de clientes no sistema em uma 
unidade de tempo.
• A probabilidade de existir um número n de clientes no 
sistema.
Teoria das Filas
Existe alguma forma de avaliar o desempenho do 
nosso sistema?
Tempo médio gasto pelo cliente na fila
Fonte: Prado (2014).
Tempo médio de permanência no sistema
Fonte: Prado (2014).
Teoria das Filas
Existe alguma forma de avaliar o desempenho do nosso sistema?
Tempo médio de espera no sistema?
Percentual de tempo que o sistema está ocupado



Fonte: Prado (2014).
Fonte: Prado (2014).
Exemplo: Teoria 
das Filas
Exemplo 1
Será montada uma linha exclusiva para a produção desse novo produto
e contará com uma máquina de cada tipo (torno, fresa e retífica).
Estima-se que as taxas médias de processamento são de 15 peças/dia,
12 peças/dia e 20 peças/dia, respectivamente para torno, fresa e
retífica.
Será necessário encaminhar ordens de produção
com taxa média 10 ordens/dia.
Haverá o surgimento de gargalos????
Exemplo 1
Inicialmente, vamos compreender as
informações que compõem o cenário:
As chegadas de ordens chegam a uma taxa
média de 10 ordens por dia, portanto, λ =10
ordens/dia.
A taxa de processamento do torneamento é
de 15 peças/dia, logo, µ =15 peças por dia.
Exemplo 1: Solução
A taxa de processamento do fresamento é de 12
peças/dia, logo, µ =12 peças por dia.
A taxa de processamento da retífica é de 20 
peças/dia, logo, µ =20 peças por dia. 
Trata-se de filas sequenciais no sistema de
produção segundo o modelo M/M/1, e o esquema
do processo de produção pode ser visto na figura:
Exemplo 1: Solução
Para verificar se existe a formação de gargalos, é 
preciso calcular o número de peças em fila em 
cada um dos processos.
Fonte: elaborada pelo autor.
Fonte:LD. Pg. 147
Retífica
Exemplo 1: Solução
Para o torneamento:
Para o fresamento:
Para a retífica:
Fonte:LD. Pg. 147
Exemplo 1: Solução
Podemos concluir que haverá peças aguardando
processamento no torneamento e no fresamento,
e a etapa mais crítica é o fresamento.
Portanto, haverá formação de gargalos no
torneamento e no fresamento (onde é mais
crítico).
Exemplo 2
Após o lançamento do novo produto, houve um
aumento na previsão de demanda por ele e a
empresa pensa em adquirir novas máquinas para
atender. Antes de qualquer decisão, foi pedida uma
simulação com o novo cenário.
A nova demanda é atendida com a seguinte taxa de
chegada de pedidos: 18 por dia.
Exemplo 2
Segundo os fabricantes das novas máquinas, as
taxas de processamentos são de:
• Torneamento = 20 peças/dia;
• Fresamento = 25 peças/dia;
• Retífica = 35 peças/dia.
Exemplo 2: Solução
Nova taxa de chegada é: λ =25
Para o Fresamento:
Para a retífica:
Para o torneamento:
Método de 
Monte Carlo
Simulação
A simulação é definida como a representação de um sistema real 
a partir de um modelo.
O processo da simulação, portanto, consiste em construir um modelo
que execute uma rotina sequencial de instruções, de uma maneira
repetitiva semelhante a um programa de computador.
Esse modelo deve imitar o comportamento do
problema que está sendo estudado, portanto, as
variáveis envolvidas devem assumir um caráter
aleatório.
Método de Monte Carlo
Em diversas situações, os modelos de simulação
são utilizados para analisar uma decisão sob risco,
em outras palavras, um modelo em que o
comportamento de um ou mais fatores não é
conhecido com certeza, portanto, é considerado
como uma variável aleatória.
O comportamento de uma variável aleatória é
descrito por uma distribuição de probabilidade.
Método Monte Carlo ou Simulação de Monte Carlo
O desempenho do sistema real é imitado usando-
se distribuições de probabilidades para gerar
aleatoriamente diversos eventos que ocorrem no
sistema.
Uma maneira de transformar um conjunto de 
números aleatórios em outro conjunto de números 
(variáveis aleatórias), com a mesma distribuição da 
variável considerada.
Exemplo: Método de Monte Carlo
Vamos imaginar uma experiência a partir da qual queremos
conhecer a soma obtida com maior frequência no
lançamento de dois dados não viciados e lançados ao
mesmo tempo.
Fonte: https://goo.gl/images/3mYjiL
Exemplo: Método de Monte Carlo
As somas possíveis são: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 e 12.
A soma cujo valor é igual a dois (2) é obtida somente quando em
ambos os dados saírem a face com o numero 1, ou seja, uma chance.
O valor 3 é possível quando sair o número 1 em um dos dados e 
o número 2 no outro, portanto, duas possibilidades.
O valor 4 é possível quando em ambos os dados
saírem o número 2 ou quando em um dos dados
sair o numero 1 e no outro o numero 3 totalizando
3 chances, e assim por diante.
Somas possíveis e
frequências no
lançamento de
dois dados:
Fonte: adaptado de Moreira (2010).
Resultados
possíveis
com faixa de
números
atribuídos:
Fonte: adaptado de Moreira (2010).
Aplicações do método de Monte Carlo
1. Projeto de instalações para descarregamento
de cargas, quando se deseja responder questões
como: quantas plataformas devem ser
construídas? Que tipo e em que quantidade é
necessária para movimentar o material? Quantos
colaboradores são necessários para as operações?
Aplicações do método de Monte Carlo
2. Na determinação de políticas de estoque, é
possível determinar, por meio da simulação, o
momento e a quantidade dos pedidos de
reposição, bem como os níveis de estoque, de
forma a atender as necessidades dos clientes.
Aplicações do método de Monte Carlo
3. Balanceamento de linhas – por meio da
simulação pelo método de Monte Carlo é possível
balancear as linhas permitindo uma produção de
forma contínua, sem sobressaltos durante o
processamento.
Questão
Simular significa representar. No contexto empresarial, simular um
sistema significa fazer com que esse sistema possa operar como um
sistema real, com objetivo de estudar suas propriedades. Uma
ferramenta bastante conhecida para a simulação é o método Monte
Carlo (NEUMANN, 2011).
No que consiste o método de Monte Carlo?
Questão
a) Estimativa para o comportamento entre as chegadas de clientes em uma 
fila.
b) Uma estimativa para a distribuição de probabilidade associada à chegada 
de clientes em uma fila.
c) Sequências de resultados nas quais as probabilidades dos resultados em um 
instante dependem do ocorrido no instante imediatamente anterior.
d) Geração de valores de variáveis, com auxílio de 
números ao acaso ou aleatórios.
e) Sub-rotinas determinísticas para geração de 
números.
Recapitulando
Recapitulando
Cadeias de Markov
Teoria das Filas
Método Monte 
Carlo
Aplicações da 
Cadeias de Markov
Características da 
Teoria das Filas
Aplicações do 
Método Monte Carlo