Biblioteca 1189645

Prévia do material em texto

CCE 0516 - Simulação da Produção e Teoria das Filas 
 
 
 
 
 
 
Professor: Carlos Roberto Silva Santos 
Pós graduado, bacharel em Engenharia Civil e em 
Ciências Contábeis pela UFES & Auditor. 
 2018/1 
 
0 
 
 
 
 
CCE 0516 - Simulação da Produção e Teoria das Filas 
 
 
 
 
 
Norteadores 
 
I. Frequência; 
II. Provas(AV1- Carlos; AV2-Estácio; AV3- Estácio) ; 
III. Exercício/Trabalho . 
1 
CCE 0516 - Simulação da Produção e Teoria das Filas 
Contextualização: 
 
• Oportunidade de introduzir o aluno ao mundo de aplicação da 
simulação como meio auxiliar a tomada de decisão. 
 
Objetivo geral: 
 
• Visão geral das técnicas e métodos associados à simulação. 
 
 
2 
CCE 0516- Simulação da Produção e Teoria das Filas 
Ementa 
3 
CCE 0516- Simulação da Produção e Teoria das Filas 
Ementa 
4 
Unidade 1 
Processos Estocásticos 
O que é? 
 
 Modelos de probabilidade para processos que 
evoluem no tempo de maneira probabilística. 
 
 Um Processo Estocástico é definido como uma 
coleção de variáveis randômicas X(t) indexadas por 
um parâmetro t pertencente a um conjunto T. 
 
 
5 
Unidade 1 
Processos Estocásticos 
O que é? 
 
 
 Um Processo Estocástico é uma família/sequência de 
variáveis aleatórias X(t) que descreve a evolução de 
alguma característica X do processo sob análise ao 
longo do tempo, t. 
 
 
6 
Unidade 1 
Processos Estocásticos 
 Os processos com filas com tempos entre chegadas 
sucessivas (λ) e/ou de atendimento (µ) 
representados por variáveis aleatórias são processos 
denominados estocásticos (probabilísticos). 
 
 Assim, neste capítulo são introduzidos alguns 
conceitos e características básicas de processos 
estocásticos (com ênfase nos processos 
markovianos*) necessários para o estudo da Teoria 
de Filas. 
*matemático russo Andrei Markov 
Fonte: Cap 3 do Livro Teoria de Filas, Fogliatti & Mattos 
 
 
7 
Unidade 1 
Processos Estocásticos 
 
 
• Existem vários "tipos" de Processos Estocásticos, 
porém, nestas notas de aula será apenas abordado 
um tipo de Processo Estocástico denominado 
Processo Markoviano*. 
 
 
* a distribuição de probabilidade do próximo estado depende apenas do estado atual 
e não da sequência de eventos que precederam. 
 
 8 
Unidade 1 
Processos Estocásticos 
Traduzindo... 
 
 Processos Estocásticos são de interesse para descrever o 
procedimento de um sistema operando sobre algum período 
de tempo, com isso, em termos formais, a variável randômica 
X(t) representa o estado do sistema no parâmetro t 
(geralmente tempo). 
 
 Fenômeno que varia em algum grau, de forma imprevisível, à 
medida que o tempo passa, segundo Clarke e Disney. 
 
 I) Para um maior aprofundamento no estudo dos processos estocásticos, são recomendados 
entre outros os livros de Clarke e Disney(1979), Ross(1996) e Trivedi (2002). 
 
 
 
9 
Unidade 1 
Processos Estocásticos 
 
 
 
 A imprevisibilidade, nesse caso, significa que se observou 
uma seqüência inteira do processo em várias ocasiões 
diferentes, sob condições presumivelmente idênticas; as 
seqüências em observação, resultantes, seriam, em geral, 
diferentes. 
 
 
 
 
 
 
10 
Teoria das Filas 
Variáveis Randômicas Fundamentais 
11 
Unidade 1 
Processos Estocásticos 
 
Então.... 
 
 O resultado da experiência aleatória é uma seqüência ou 
série de valores, uma função, e não apenas um único número. 
 
 Por exemplo, a probabilidade de haver infratores, no sistema 
de rodízio implantado na cidade de São Paulo, nos diversos 
dias da semana, ou diversos períodos do dia, são diferentes. 
 
 
 
 
 
 
 
 
12 
Unidade 1 
Processos Estocásticos 
Exemplificando: 
 
 Nível de estoque de um produto no fim da semana; 
 
 Variação minuto a minuto do índice IBOVESPA; 
 
 Variação do tráfego em um cruzamento; 
 
 Variação diária no tamanho do estoque de uma empresa. 
 
 
 
13 
Unidade 1 
Processos Estocásticos 
 Parâmetro do Processo 
 Para analisar o processo estocástico é preciso especificar o 
período de tempo T envolvido: quando ele será observado. 
• Se T é contínuo (sequência), T={ t: 0 ≤ t <∞): 
 Trata-se de um Processo Estocástico de Parâmetros Contínuos 
 “ Se a variável aleatória X for contínua, a probabilidade para um 
dado valor Xi tenderá a zero.” A probabilidade para um dado 
valor da variável aleatória será igual ao número de vezes que 
ocorre esse dado valor, dividido pelo número total de valores da 
variável. Ora, o número total de valores da variável tende a 
infinito, e a divisão pelo seu valor tenderá a zero. 
 Ex: A= P(Xi ≤ X ≤ Xj) ou pela área “A” do gráfico. 
 
 
14 
Unidade 1 
Processos Estocásticos 
 Parâmetro do Processo 
 Para analisar o processo estocástico é preciso especificar o 
período de tempo T envolvido: quando ele será observado. 
 
• Se T é discreto, T={0,1,2,...,} (caso contrário, “finito/contável”): 
 Trata-se de um Processo Estocástico de Parâmetros Discretos : 
 “ Se uma dada variável aleatória X for discreta, ela assumirá 
apenas um número finito de valores Xi; a cada um desses 
valores podemos associar uma dada probabilidade de 
ocorrência P(Xi).” 
 Ex: Séries Temporais em geral. (Xi)  P(Xi) 
 
15 
Unidade 1 
Processos Estocásticos 
Classificação: 
 
 Os Processos Estocásticos podem ser classificados como: 
 
 a) Em relação ao Estado 
 
 Estado Discreto (contagem): X(t) é definido sobre um 
conjunto enumerável (infinito de inteiros) ou finito. 
 
 Estado Contínuo (uma medida): X(t) caso contrário. (aparelho) 
 
 
16 
Unidade 1 
Processos Estocásticos 
Classificação: 
 
 b) Em relação ao Tempo (Parâmetro) 
 
 Tempo Discreto: t é finito ou enumerável. 
 
 Tempo Contínuo: t caso contrário. 
 
17 
Unidade 1 
Processos Estocásticos 
Classificação: (Exemplos) 
• 1. Número de usuários em uma fila de banco em um 
determinado instante 
 R:Estado Discreto e Tempo Contínuo. 
• 2. Índice pluviométrico diário 
R:Estado Contínuo e Tempo Discreto. 
• 3. Número de dias chuvosos: 
R: Estado Discreto e Tempo Discreto. 
18 
Unidade 1 
Processos Estocásticos 
Revisão dos Conceitos de Álgebra Matricial 
• Definição; 
• Matriz quadrada; 
• Vetores; 
• Matriz Diagonal; 
• Matriz Identidade e Nula; 
• Operações com Matrizes; 
• Algumas Propriedades 
 
 19 
Unidade 1 
Processos Estocásticos 
Revisão dos Conceitos de Álgebra Matricial Relevante 
 
• Multiplicação de Matrizes 
 
 A² = A . A , A³= A² . A , A⁴= A³ . A , .... , Aⁿ = Aⁿ⁻¹ . A 
 
 
 
• Vetor de Probabilidade 
 
 Um vetor u = ( u1, u2, u3, .... , un ) é chamado vetor de 
probabilidade, se seus componentes são não negativos e 
somam 1. 
π = [ 0.30, 0.20, 0.50 ] 
A = [ 0.30, 0 , 0.70 ] 
 
 
20 
Unidade 1 
Processos Estocásticos 
Revisão dos Conceitos de Álgebra Matricial Relevante 
 
• Multiplicação de Matrizes 
• m= ad +bg + cj; 
• n= ae+bh+ ck; 
• o= af+bi+ cl. 
 
 
 
21 
d e f 
g h i 
j k l 
a b c m n o 
Unidade 1 
Processos Estocásticos m=0,575 e n=0,425 
Revisão dos Conceitos de Álgebra Matricial Relevante 
 
• Vamos treinar? Multiplicação de Matrizes 
 
 
 
22 
0,9 0,1 
0,0875 0,9125 
0,6 0,4 m n 
Unidade 1 
Processos Estocásticos 
 
• Matrizes Estocásticas 
 
 Umamatriz quadrada P = pij é chamada matriz 
estocástica, se cada uma de suas linhas é um vetor de 
probabilidade, isto se cada entrada de p é não negativa, 
e a soma das entradas em cada linha é igual a 1. 
 
 
• Teorema: Se A e B são matrizes estocásticas, então o produto de AB é uma 
matriz estocástica. Conseqüentemente, todas as potências de Aⁿ são 
matrizes estocásticas. 
 
23 
Unidade 1 
Processos Estocásticos 
 
• Matrizes Estocásticas Regulares 
 
 
 Para que P seja matriz estocástica regular, é necessário que 
o vetor fixo de probabilidade tenha todos os elementos 
positivos, a soma igual a 1 e nenhuma componentes igual à 
zero 
 
 Assim como, uma matriz estocástica P é considerada regular 
se todas as entradas de alguma potência de Pⁿ são positivas 
(≠ 0). 
 
 
 
 
 
24 
Unidade 1 
Processos Estocásticos 
 
• Exemplo de Matriz Estocástica Regular 
 
 
 Se t = (1/4; 0; 1/4; 0; 1/4; 1/4) é um vetor fixo da matriz 
estocástica P, então, P é regular? 
 
 
 
• Não. Para que P seja matriz estocástica regular, é necessário que o vetor 
fixo de probabilidade tenha todos os elementos positivos, a soma igual a 1 
e nenhuma componentes igual à zero. Apesar de todos os elementos 
serem positivos e a soma igual a 1, temos componente zero no vetor, 
logo, P não é matriz estocástica regular. 
25 
Unidade 1 
 
Processos Markovianos 
 
Um processo estocástico é denominado processo 
markoviano se dada uma sequência de tempos 
to<t1<t2<...<tn<t, a distribuição de probabilidade 
condicional de X(t) para dados valores de X(to), 
X(t1) ... X(tn) depende unicamente de X(tn), ou 
seja: P[X(t) <=x/X(tn) = xn,X(tn-1)= xn-1,..., X(to)= 
xo] = P[X(t)<= x/ X(tn)= Xn] 
 
 
 
26 
Unidade 1 
Processos Estocásticos 
Processos Markovianos 
 
• A expressão pode ser "traduzida" por a probabilidade 
condicional de qualquer evento futuro, dado qualquer 
evento passado e o estado presente X(tk) = xk, é 
independente do evento passado e depende somente do 
estado presente. 
 
• Em termos mais resumidos: um Processo Estocástico é 
dito ser um Processo Markoviano se o estado futuro 
depende apenas do estado presente e não dos estados 
passados. 
 
 
27 
Unidade 1 
 
Processos Markovianos 
 
 Em outras palavras, dada a informação do presente, 
toda informação passada é irrelevante para a 
previsão da posição do processo no futuro. 
 
• Essa propriedade é denominada “ausência de 
memória” (Memoryless). 
 
• Este tipo de Processo Estocástico é também denominado de 
memoryless process (processo sem memória), uma vez que o 
passado é "esquecido" (desprezado). 
 
 
28 
Unidade 1 
Processos Estocásticos 
Exemplo : 
 
O estado no ano de 1993 do uso da terra em uma 
cidade de 50 quilômetros quadrados de área é: 
 
• Tabela 1 - Estado do uso da terra em 1993. 
I uso residencial 30% 
II uso comercial 20% 
III uso industrial 50% 
29 
Unidade 1 
Processos Estocásticos 
Exemplo : Memoryless 
 
 Em análises anteriores indicam que a chegada de 
clientes em uma dada agência bancária segue uma 
distribuição exponencial com média de 20 chegadas 
por hora. Você, estagiário, está fazendo um 
levantamento nessa agência e na presente hora, já 
decorrido 15 minutos, já chegaram 10 clientes. 
Quantos clientes você espera que ainda cheguem na 
presente hora? 
30 
Unidade 1 
Cadeias de Markov 
 
 
 Chama-se cadeias de Markov um processo 
markoviano que possui o espaço de estados discreto 
e com as seguintes propriedades: 
 
• I ) Cada resultado pertence a um conjunto finito de 
resultados ( a1, a2 , a3 , ...., an ), chamado espaço dos 
estados do sistema; se o resultado da n-ésima tentativa é 
ai , dizemos que o sistema se encontra no estado ai no 
 instante n. 
 
 
 
31 
Unidade 1 
Processos Estocásticos 
Cadeias de Markov 
 
Chama-se cadeias de Markov um processo 
estocástico com as seguintes propriedades: 
 
• II ) O resultado de qualquer ensaio depende, no máximo, 
do resultado do ensaio imediatamente anterior e não de 
qualquer dos precedentes; a cada par de estados (ai, aj ) 
está associada à probabilidade Pij de que ocorra aj 
imediatamente após ter ocorrido ai. 
 
 
 
32 
Unidade 1 
Processos Estocásticos 
Cadeias ou Processos de Markov 
 
 
 São sequências de resultados em que a 
probabilidade de cada resultado depende do que 
aconteceu no momento imediatamente passado*. 
 
* pág. 335 do Livro Pesquisa Operacional ,curso introdutório ,de Daniel 
Augusto Moreira. 
 
 
33 
Unidade 1 
Processos Estocásticos 
Cadeias de Markov 
 
 
Os valores atribuídos a pij correspondem às 
probabilidades de transição de um para outro 
estado, isto pode ser visto através da chamada 
matriz de transição P. 
 
 
34 
Unidade 1 
Processos Estocásticos 
Cadeias de Markov 
 
 Assim, a cada estado ai corresponde a iésima linha 
(pi1, pi2, ... , pij ) da matriz de transição P; se o 
sistema está no estado ai, então esse vetor linha 
representa as probabilidades de todos os possíveis 
resultados do próximo ensaio; por isso é um vetor de 
probabilidade. 
 
 
 
35 
Unidade 1 
Processos Estocásticos 
Cadeias de Markov 
 
 Teorema : A matriz de transição de uma Cadeia de 
Markov é uma matriz estocástica. 
 
 
 
36 
Unidade 1 
Processos Estocásticos 
Cadeias de Markov 
Exemplo : 
 
 Três crianças arremessam a bola uma para a outra. A 
sempre arremessa para B; B sempre arremessa para 
C; e C arremessa a bola para A ou para B, com a 
mesma probabilidade. 
 
 
37 
Unidade 1 
Processos Estocásticos 
Cadeias de Markov 
 
 Esta é uma Cadeia de Markov, pois a pessoa que 
arremessa a bola num determinado instante não é 
influenciada por aquelas que arremessaram 
anteriormente. O espaço de estado do sistema é { A , 
B, C } e a matriz de transição é apresentada a seguir: 
 
38 
Unidade 1 
Cadeias de Markov 
 matriz de transição 
 
39 
Unidade 1 
Processos Estocásticos 
Cadeias de Markov 
 
 A primeira linha da matriz corresponde ao vetor que 
indica que A sempre passa a bola para B; a segunda 
linha corresponde ao fato de que B sempre passa a 
bola para C; a última linha corresponde ao fato de 
que C arremessa a bola para A ou B com idênticas 
probabilidades, não ficando com a bola. 
40 
Unidade 1 
Processos Estocásticos 
Distribuição Estacionária de uma Cadeia de Markov 
 
• Pelo Teorema 3, verificamos que a sequência das 
matrizes de transição em n etapas converge para a 
matriz T, cujas linhas são iguais ao único vetor fixo de 
probabilidade t de P; portanto, a probabilidade de 
evolução do estado ai para o estado aj ( para um n 
suficientemente grande ) independe do estado inicial 
de ai. 
 
41 
Unidade 1 
Cadeias de Markov 
 
 
• Exemplo clássico de aplicação das cadeias de Markov 
está no problema da mudança de marcas por parte 
do consumidor, ou seja, a lealdade à marca. 
 
42 
Unidade 1 
Cadeias de Markov 
 
• Com o conceito de cadeias de Markov, é possível 
calcular paulatinamente as fatias de mercado de 
diversos produtos concorrentes, desde que sejam 
conhecidas as fatias originais e as probabilidades de 
transição de uma marca a outra. Também é possível 
prever o efeito de estratégias adotadas para a 
proteção da marca. Assim, para tais cálculos, é muito 
útil o conceito de matriz. 
 
• Fonte dos slides 41 ao 48 : Cap. 10 doLivro Pesquisa Operacional curso 
introdutório do Daniel A. Moreira. 
 
43 
Unidade 1 
Cadeias de Markov 
 
• Particularizando para o caso de diferentes marcas 
que disputam um dado mercado, a matriz de 
probabilidades de estado (fatias de mercado) é um 
arranjo numérico de uma linha e tantas colunas 
quantas sejam as marcas concorrentes. Assim, por 
exemplo, em um mercado no qual concorram três 
marcas A, B e C, de um certo produto , o arranjo para 
um dado instante (t) seria: 
 
 
 
 
44 
0,45 0,23 0,32 
Unidade 1 
Cadeias de Markov 
 
 
• Por sua vez, a matriz de probabilidade de transição 
indica as probabilidades de os clientes passarem de 
uma marca pra outra, no momento seguinte. 
Levando em conta as três diferentes marcas A, B e C, 
poderíamos ter a seguinte matriz de transição: 
 
 
 
 
45 
Unidade 1 
Matriz de Probabilidades de Transição da Escolha 
 
 
 
 
 
 
 
• Assim, por exemplo, aqueles que compram a marca A têm 
uma probabilidade de 0,75 de voltar a comprá-la no próximo 
período. Os clientes mais fiéis são os de probabilidade 0,90. 
46 
DE (t) PARA (t+1) 
Marca A Marca B Marca C 
Da Marca A 0,75 0,15 0,10 
Da Marca B 0,08 0,90 0,02 
Da Marca C 0,25 0,15 0,60 
Unidade 1 
Matriz de Probabilidades de Transição 
 
• Ou, simplesmente 
 
 
 
 
47 
0,75 0,15 0,10 
0,08 0,90 0,02 
0,25 0,15 0,60 
Unidade 1 
Matriz de Probabilidades de Transição 
 
 
 
 
• Fatias de Mercado(t) Matriz Prob. de Transição 
48 
0,75 0,15 0,10 
0,08 0,90 0,02 
0,25 0,15 0,60 
0,45 0,23 0,32 
Unidade 1 
Matriz de Probabilidades de Transição 
 
• Dadas a matriz de probabilidades de estado para um 
dado momento t e a matriz de probabilidades de 
transição, é possível calcular a nova probabilidade de 
estado para outro momento (t+1), simplesmente 
multiplicando essas matrizes. 
 
 
49 
Unidade 1 
Distribuição de Poisson 
 
 A distribuição de Poisson é uma distribuição discreta 
empregada em situações probabilísticas onde a área de 
oportunidade de ocorrência de um evento é grande, mas 
a oportunidade de ocorrência em um intervalo 
particular (ou em um ponto) é muito pequena. 
 Exemplo: 
• Número de defeitos ao longo de um fio de uma linha de 
transmissão de energia. 
• Erros de datilografia em um livro. 
• Acidentes industriais. 
• Chegadas em modelos de fila de espera. 
50 
Unidade 1 
Distribuição de Poisson 
 
51