Simulação a Eventos Discretos - ufjf.br · PDF fileExemplo: sistemas que podem ser modelados como filas de espera. ... Simulação é limitada para 5 chegadas, chegada do cliente

Fernando Nogueira Simulação 1

Simulação a Eventos Simulação a Eventos

DiscretosDiscretos


Introdução

�Simulação não é uma técnica de otimização: estima-se medidas de performance deum sistema modelado.

�Modelos Contínuos X Modelos Discretos

Modelos Contínuos: estado do sistema muda continuamente em função do tempo.Utiliza-se geralmente equações diferenciais para descrever iterações entre diferenteselementos do sistema. Exemplo: crescimento de populações, circuitos eletrônicos,reações químicas, modelos econométricos,...

Modelos Discretos: estado do sistema muda somente no instante que ocorre um evento,para todos os demais instantes de tempo, nada muda no sistema. Para isto, utiliza-se osconceitos de Filas. Exemplo: sistemas que podem ser modelados como filas de espera.Obs: este tipo de simulação é conhecido como Simulação a Eventos Discretos.

Definição Genérica de Eventos

Toda Simulação a Eventos Discretos descreve, diretamente ou indiretamente, situaçõesde fila, em que clientes chegam, aguardam em fila se necessário e então recebematendimento antes de deixar o sistema. Com isso, existem apenas dois eventos quecontrolam a simulação: chegadas e atendimentos.


Exemplo: dois produtos são processados em duas máquinas em série, as quais possuemampla área de buffer. Os eventos são:

A11: o produto 1 chega na máquina 1. D11: o produto 1 deixa a máquina 1.




Nota-se que só existe 2 eventos: chegada (A) de um produto em uma máquina e saída(D) de um produto de uma máquina. Os números 1 e 2 são atributos que caracterizamos eventos. obs: admitindo que um produto ao ser processado na máquina 1 vai diretopara a máquina 2, os eventos D11 e A12 são idênticos, assim como D21 e A22.

Amostragem a partir de Distribuições de Probabilidade

Quando o intervalo t entre sucessivos eventos é probabilístico, faz-se necessário geraramostra aleatórias a partir de uma distribuição de probabilidade f(t).

Método Inverso ⇒ seja F(x) = P{y ≤ x} a Função de Distribuição de Probabilidade davariável aleatória x com Função Densidade de Probabilidade f(x) (contínua ou discreta),e R uma amostra aleatória a partir da Distribuição Uniforme (0,1), x = F-1(R).


F ( x )

1

0 x x 1

R 1

c o n t í n u a

F ( x )

1

d i s c r e t a

0 x x 1

R 1

Exemplo: Distribuição Exponencial

( )

( ) ∫λ−λ−

λ−

−=λ=

λ=t

0

tx

t

e1dxetF

etf ( )

( ) ( )Rln1

touR1ln1

t

tFR

λ−=−

λ−=

=

1000 2000 3000 4000 5000 6000 7000 8000 9000 10000

1

2

3

4

5

6

7

Amostras de t a partir de Exponencial (lambda = 1.5)

Amostra

t

0 1 2 3 4 5 6 7 80

500

1000

1500

2000

2500Histograma

t

Fre

quencia


Geração de Números Aleatórios com Distribuição Uniforme

Como utilizar o computador digital, a mais precisa e determinística máquina concebidapelo homem, para produzir números aleatórios ? Uma vez que qualquer programa vaiproduzir uma saída inteiramente previsível, a geração de números aleatórios em umcomputador representa uma impossibilidade conceitual.

A única maneira prática consiste em utilizar operações aritméticas. Tais números nãosão verdadeiramente aleatórios e por isso são denominados Números Pseudo-Aleatórios. O método mais comum para gerar Números Pseudo-Aleatórios é:

Método Congruente Multiplicativo

Dado os parâmetros u0 (semente), b, c e m, um número pseudo-aleatório Rn pode sergerado por:

( )

( )( ) 0ypara,xy,xmod

0ypara),y/x(floor*yxy,xmod

:onde

,...2,1n,m

uR

,...2,1n,m),cbu(modu

nn

1nn

==

≠−=

==

=+= −

( )

( )

4167.012

5R

512),589(modu

6667.012

8R

812),5119(modu

12m,11u,5c,9b

:Exemplo

2

2

1

1

0

==

=+×=

==

=+×=

====


Simulação Monte Carlo

Estimar a área de uma circunferência com equação (x-1)2 + (y-2)2 = 25

Raio = 5, área do quadrado = 100, área exata da circunferência = 78.5398

-4 -2 0 2 4 6-3

-2

-1

0

1

2

3

4

5

6

7

-4 -2 0 2 4 6-3

-2

-1

0

1

2

3

4

5

6

7

-4 -2 0 2 4 6-3

-2

-1

0

1

2

3

4

5

6

7

n=10

área = 80% da área do quadrado = 80

n=100

área = 78% da área do quadrado = 78

n=1000

área = 78.4% da área do quadrado = 78.4


Mecanismo da Simulação a Eventos Discretos

Evento Chegada

1. Gerar e armazenar cronologicamente o tempo de chegada do próximo cliente(=tempo corrente + tempo entre chegadas).

2. Se a instalação de atendimento está ociosa

a) Começar o atendimento e declarar a instalação de atendimento ocupada.Atualizar as estatísticas de utilização da instalação de atendimento.

b) Gerar e armazenar cronologicamente o tempo de saída (término do atendimento)do cliente (=tempo corrente + tempo de atendimento).

3. Se a instalação de atendimento está ocupada, colocar o cliente na fila e atualizar asestatísticas da fila.

Evento Saída (Atendimento)

1. Se a fila está vazia, declarar a instalação de atendimento ociosa. Atualize asestatísticas da instalação de atendimento.

2. Se a fila não está vazia

a) Selecionar um cliente a partir da fila e coloca-lo na instalação de atendimento.Atualizar a fila e as estatísticas da instalação de atendimento.

b) Gerar e armazenar cronologicamente o tempo de saída dos cliente. (=tempocorrente + tempo de atendimento).


Exemplo:

O intervalo de tempo entre chegadas em uma barbearia é exponencial com média de 15minutos e existe um único barbeiro que gasta entre 10 e 15 minutos uniformementedistribuídos para fazer uma barba. A disciplina da fila é FIFO e deseja-se 1)estimar autilização média da barbearia, 2) o número médio de clientes no sistema e 3) o tempomédio que um cliente aguarda na fila.

Seja p e q amostras aleatórias dos tempos entre chegadas e de atendimento,respectivamente, então:

( )1R0.minemR510q

1R0.minemRln15p

≤≤+=

≤≤−=

Chegada do Cliente 1 em T = 0

Gerar chegada do cliente 2 em T = 0 + p1 = 0 + [-15ln(.0589)] = 42.48 min.

Instalação de atendimento está ociosa em T = 0, cliente 1 começa a ser atendido. Otempo de saída é T = 0 + q1 = 0 + (10 + 5 x .6733) = 13.37 min.

A lista cronológica é:T Evento

13.37 saída do cliente 1

42.48 chegada do cliente 2


Saída do Cliente 1 em T = 13.37

Porque fila está vazia, instalação é declarada ociosa. Declarar que a instalação deatendimento esteve ocupada entre T = 0 e T = 13.37 min. Atualizar a lista cronológica:

T Evento


Chegada do Cliente 2 em T = 42.48

Gerar chegada do cliente 3 em T = 42.48 + p2 = 42.48 + [-15ln(.4799)] = 53.49 min.

Instalação de atendimento está ociosa em T = 42.48, cliente 2 começa a ser atendido einstalação é declara ocupada. O tempo de saída é T = 42.48 + q2 = 42.48 + (10 + 5 x.9486) = 57.22 min. Atualizar a lista cronológica:

T Evento




Gerar chegada do cliente 4 em T = 53.49 + p3 = 53.49 + [-15ln(.6139)] = 60.81 min.

Instalação de atendimento está ocupada (até T = 57.22), cliente 3 é colocado na fila emT = 53.49 Atualizar a lista cronológica:

T Evento





Cliente 3 é retirado da fila para começar atendimento. O tempo aguardado é W3 = 57.22– 53.49 = 3.73 min. O tempo de saída é T = 57.22 + (10 + 5 x .5933) = 70.19 min.Atualizar a lista cronológica:

T Evento




Gerar chegada do cliente 5 em T = 60.81 + p4 = 60.81 + [-15ln(. 9341)] = 61.83 min.

Instalação de atendimento está ocupada (até T = 70.19), cliente 4 é colocado na fila.Atualizar a lista cronológica:

T Evento




Simulação é limitada para 5 chegadas, chegada do cliente 6 não é gerada. A instalaçãode atendimento está ocupada e então cliente é colocado na fila em T = 61.83. Atualizara lista cronológica:

T Evento





T Evento




T Evento



Não há mais clientes no sistema (fila e instalação de atendimento) e a simulaçãotermina.


10 20 30 40 50 60 70 80 90 T

1

2

W3

W4

W5

A1=3.73 A2=28.63

Lq

10 20 30 40 50 60 70 80 90 T

1

q1

A3=13.37 A4=50.34

Utilização

instalação

q2 q3 q4 q5

clientes349.82.92

36.32

82.92

AAL 21

q

==

+=

barbeiros686.082.92

71.63

82.92

AA

instalação

Utilização43

==

+=

min47.65

36.32

5

25.1938.973.300

5

WWWWWW 54321

q ==++++

=++++

=


( )( )( )

( )( )( )

≤≤∀−−

−

≤≤∀−−

−

=

.c.c,0

bxc,cbab

xb2

cxa,acab

ax2

)c,b,ax(f

( )( )( )

( )( )( )

≤≤∀−−

−−

≤≤∀−−

−

=

.c.c,0

bxc,cbab

xb1

cxa,acab

ax

)c,b,ax(F

2

2

Distribuição Triangular

14

Estatística

Em Probabilidade os modelos matemáticos de

processos e sistemas são “afetados por chances”.

Em Estatística estes modelos são “checados

contra a realidade”.

15

Distribuições Empíricas

Como dados amostrados são “convertidos” para

funções de probabilidade? Os passos a se seguir

são:

1)Armazenar os dados na forma de um

histograma de freqüência e determinar a função

de probabilidade empírica associada.

2)Utilizar um teste estatístico a fim de verificar

se a função de probabilidade empírica é

amostrada a partir de alguma função de

probabilidade teórica.

16

Histograma de Freqüências

Um histograma de freqüência é construído como o número de amostras

que estão dentro de um determinado intervalo de uma série de intervalos

não superpostos de valores possíveis (ou no mínimo coerentes) que as

amostras podem assumir.

17

Exemplo

Suponha que um comerciante de laranjas pese todas as 100 caixas de

laranjas que comprou de um produtor.

18

58.6482 60.7688 57.9416 58.8650 60.5505 61.5079 58.4430 59.1439 59.7513 61.7646

59.1022 59.2938 61.8068 59.9236 60.1800 58.6753 60.9961 59.1470 61.2076 61.0790

61.0359 60.7524 59.0461 61.1086 59.8184 61.2934 61.4001 61.2937 57.3782 61.2049

59.7765 60.8209 61.2855 60.8319 59.7009 60.2464 60.4145 60.6598 58.7840 60.1347

59.0217 60.4803 61.0445 59.5986 60.3876 58.8829 60.0900 58.7793 59.5580 59.3169

58.7369 59.1403 58.7313 59.2234 59.4756 58.3702 59.6124 57.7219 60.3160 59.2787

59.5117 59.6192 60.1209 59.5806 58.7161 60.3290 59.2428 60.6603 59.2318 59.8816

60.7025 59.7575 60.6408 58.7476 59.0084 61.8732 60.0859 60.2366 59.0289 59.2829

60.0155 59.1466 58.4206 60.2357 59.9757 60.2416 60.0236 58.1723 59.7747 60.5153

59.7560 60.7227 58.9124 60.7652 57.3110 60.6493 60.1931 59.9564 61.2574 61.2378

19

Os valores mínimo e máximo nesta tabela são 57.3110

e 61.8732, respectivamente.

Isto significa que todas as amostras podem ser

classificadas no intervalo [57,62], escolhido

arbitrariamente.

Arbitrariamente escolhem-se o número de intervalos

para dividir o intervalo [57,62]. Escolhendo-se 5

intervalos, pode-se montar a seguinte tabela:

20

I Intervalo Freqüência

Observada Oi

Freqüência

Relativa fi

Freqüência Relativa

Acumulada Fi

1 [57,58] 4 0.04 0.04

2 [58,59] 15 0.15 0.19

3 [59,60] 34 0.34 0.53

4 [60,61] 31 0.31 0.84

5 [61,62] 16 0.16 1

total 100 1

2158 59 60 61 62

0

5

10

15

20

25

30

35Histograma de Freqüência Observada

pesos (kg)

Fre

qüência

2258 59 60 61 62

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1Histograma de Freqüência Relativa e Acumulada

pesos (kg)

Fre

qüência

Rela

tiva

23

∑=

=N

1i

iifpp ( )∑

=

−=N

1i

i

2

i

2

p fpps

kg9.595.6116.05.6031.05.5934.05.5815.05.5704.0p =×+×+×+×+×=

( ) ( ) ( )

( ) ( ) 222

2222

p

kg1.19.595.6116.09.595.6031.0

9.595.5934.09.595.5815.09.595.5704.0s

=−×+−×

+−×+−×+−×=

24

Teste da Qualidade do Ajustamento

Este teste é utilizado para avaliar se as amostras

utilizadas na determinação da distribuição empírica

são oriundas de uma distribuição teórica especifica.

Com os valores estimados de média e variância no

exemplo anterior é possível comparar a distribuição

empírica com uma Distribuição Normal, por exemplo,

com parâmetrosp=µ 2

ps=σ

2558 59 60 61 62

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1Distribuição Relativa e Acumulada Empírica e Teórica

pesos (kg)

Fre

qüência

Rela

tiva o

u p

robabili

dade

26

Teste de Qui-Quadrado

( ) ( ) ( )( )∫−

−−==i

1i

I

I

1iii IFIFndxxfnn

( )∑

=

−=χ

N

1i i

2

ii2

n

nO

27

28

( ) ( ) ( ) ( ) ( )2534.1

464.12

464.1216

331.31

331.3131

494.34

494.3434

974.15

974.1515

236.3

236.3422222

2 =−

+−

+−

+−

+−

=χ

Teste de Hipótese

H0: amostras são oriundas da distribuição teórica

H1: amostras não são oriundas da distribuição teórica

A hipótese básica (H0) é aceita, ao nível de

significância α, se:

2

1,

2

α−νχ<χ

1kN −−=ν = 5 – 2 – 1 = 2

29

Para um nível de significância de 5%, por exemplo, o

valor tabelado é 99.52

05.01,2

2

1, =χ=χ −α−ν

Como ,pode-se dizer que a hipótese nula H0

é aceita, ou seja, para um nível de confiança de 95%,

as amostras são oriundas de uma população com

Distribuição Normal.

2534.12 =χ


Tabela A2 - Percentis da Distribuição de Qui-Quadrado

P 0,005 0,01 0,025 0,05 0,1 0,25 0,75 0,9 0,95 0,975 0,99 0,995

νννν

1 0,00 0,00 0,00 0,00 0,02 0,10 1,32 2,71 3,84 5,02 6,63 7,88

2 0,01 0,02 0,05 0,10 0,21 0,58 2,77 4,61 5,99 7,38 9,21 10,60

3 0,07 0,11 0,22 0,35 0,58 1,21 4,11 6,25 7,81 9,35 11,34 12,84

4 0,21 0,30 0,48 0,71 1,06 1,92 5,39 7,78 9,49 11,14 13,28 14,86

5 0,41 0,55 0,83 1,15 1,61 2,67 6,63 9,24 11,07 12,83 15,09 16,75

6 0,68 0,87 1,24 1,64 2,20 3,45 7,84 10,64 12,59 14,45 16,81 18,55

7 0,99 1,24 1,69 2,17 2,83 4,25 9,04 12,02 14,07 16,01 18,48 20,28

8 1,34 1,65 2,18 2,73 3,49 5,07 10,22 13,36 15,51 17,53 20,09 21,95

9 1,73 2,09 2,70 3,33 4,17 5,90 11,39 14,68 16,92 19,02 21,67 23,59

10 2,16 2,56 3,25 3,94 4,87 6,74 12,55 15,99 18,31 20,48 23,21 25,19

11 2,60 3,05 3,82 4,57 5,58 7,58 13,70 17,28 19,68 21,92 24,73 26,76

12 3,07 3,57 4,40 5,23 6,30 8,44 14,85 18,55 21,03 23,34 26,22 28,30

13 3,57 4,11 5,01 5,89 7,04 9,30 15,98 19,81 22,36 24,74 27,69 29,82

14 4,07 4,66 5,63 6,57 7,79 10,17 17,12 21,06 23,68 26,12 29,14 31,32

15 4,60 5,23 6,26 7,26 8,55 11,04 18,25 22,31 25,00 27,49 30,58 32,80

16 5,14 5,81 6,91 7,96 9,31 11,91 19,37 23,54 26,30 28,85 32,00 34,27

17 5,70 6,41 7,56 8,67 10,09 12,79 20,49 24,77 27,59 30,19 33,41 35,72

18 6,26 7,01 8,23 9,39 10,86 13,68 21,60 25,99 28,87 31,53 34,81 37,16

19 6,84 7,63 8,91 10,12 11,65 14,56 22,72 27,20 30,14 32,85 36,19 38,58

20 7,43 8,26 9,59 10,85 12,44 15,45 23,83 28,41 31,41 34,17 37,57 40,00

21 8,03 8,90 10,28 11,59 13,24 16,34 24,93 29,62 32,67 35,48 38,93 41,40

22 8,64 9,54 10,98 12,34 14,04 17,24 26,04 30,81 33,92 36,78 40,29 42,80

23 9,26 10,20 11,69 13,09 14,85 18,14 27,14 32,01 35,17 38,08 41,64 44,18

24 9,89 10,86 12,40 13,85 15,66 19,04 28,24 33,20 36,42 39,36 42,98 45,56

25 10,52 11,52 13,12 14,61 16,47 19,94 29,34 34,38 37,65 40,65 44,31 46,93

26 11,16 12,20 13,84 15,38 17,29 20,84 30,43 35,56 38,89 41,92 45,64 48,29

27 11,81 12,88 14,57 16,15 18,11 21,75 31,53 36,74 40,11 43,19 46,96 49,65

28 12,46 13,56 15,31 16,93 18,94 22,66 32,62 37,92 41,34 44,46 48,28 50,99

29 13,12 14,26 16,05 17,71 19,77 23,57 33,71 39,09 42,56 45,72 49,59 52,34

30 13,79 14,95 16,79 18,49 20,60 24,48 34,80 40,26 43,77 46,98 50,89 53,67

35 17,19 18,51 20,57 22,47 24,80 29,05 40,22 46,06 49,80 53,20 57,34 60,27

40 20,71 22,16 24,43 26,51 29,05 33,66 45,62 51,81 55,76 59,34 63,69 66,77

45 24,31 25,90 28,37 30,61 33,35 38,29 50,98 57,51 61,66 65,41 69,96 73,17

50 27,99 29,71 32,36 34,76 37,69 42,94 56,33 63,17 67,50 71,42 76,15 79,49

55 31,73 33,57 36,40 38,96 42,06 47,61 61,67 68,80 73,31 77,38 82,29 85,75

60 35,53 37,48 40,48 43,19 46,46 52,29 66,98 74,40 79,08 83,30 88,38 91,95

65 39,38 41,44 44,60 47,45 50,88 56,99 72,28 79,97 84,82 89,18 94,42 98,10

70 43,28 45,44 48,76 51,74 55,33 61,70 77,58 85,53 90,53 95,02 100,43 104,21

75 47,21 49,48 52,94 56,05 59,79 66,42 82,86 91,06 96,22 100,84 106,39 110,29

80 51,17 53,54 57,15 60,39 64,28 71,14 88,13 96,58 101,88 106,63 112,33 116,32

85 55,17 57,63 61,39 64,75 68,78 75,88 93,39 102,08 107,52 112,39 118,24 122,32

90 59,20 61,75 65,65 69,13 73,29 80,62 98,65 107,57 113,15 118,14 124,12 128,30

95 63,25 65,90 69,92 73,52 77,82 85,38 103,90 113,04 118,75 123,86 129,97 134,25

100 67,33 70,06 74,22 77,93 82,36 90,13 109,14 118,50 124,34 129,56 135,81 140,17

110 75,55 78,46 82,87 86,79 91,47 99,67 119,61 129,39 135,48 140,92 147,41 151,95

120 83,85 86,92 91,57 95,70 100,62 109,22 130,05 140,23 146,57 152,21 158,95 163,65

130 92,22 95,45 100,33 104,66 109,81 118,79 140,48 151,05 157,61 163,45 170,42 175,28

140 100,65 104,03 109,14 113,66 119,03 128,38 150,89 161,83 168,61 174,65 181,84 186,85

150 109,14 112,67 117,98 122,69 128,28 137,98 161,29 172,58 179,58 185,80 193,21 198,36

160 117,68 121,35 126,87 131,76 137,55 147,60 171,68 183,31 190,52 196,92 204,53 209,82

170 126,26 130,06 135,79 140,85 146,84 157,23 182,05 194,02 201,42 208,00 215,81 221,24

180 134,88 138,82 144,74 149,97 156,15 166,87 192,41 204,70 212,30 219,04 227,06 232,62

190 143,55 147,61 153,72 159,11 165,49 176,51 202,76 215,37 223,16 230,06 238,27 243,96

200 152,24 156,43 162,73 168,28 174,84 186,17 213,10 226,02 233,99 241,06 249,45 255,26

300 240,66 245,97 253,91 260,88 269,07 283,14 316,14 331,79 341,40 349,87 359,91 366,84

400 330,90 337,16 346,48 354,64 364,21 380,58 418,70 436,65 447,63 457,31 468,72 476,61

500 422,30 429,39 439,94 449,15 459,93 478,32 520,95 540,93 553,13 563,85 576,49 585,21

600 514,53 522,37 534,02 544,18 556,06 576,29 622,99 644,80 658,09 669,77 683,52 692,98

700 607,38 615,91 628,58 639,61 652,50 674,41 724,86 748,36 762,66 775,21 789,97 800,13

800 700,73 709,90 723,51 735,36 749,19 772,67 826,60 851,67 866,91 880,28 895,98 906,79

900 794,48 804,25 818,76 831,37 846,07 871,03 928,24 954,78 970,90 985,03 1001,63 1013,04

21, α−νχ

Documents

Simulação a Eventos Discretos - ufjf.br · PDF fileExemplo: sistemas que podem ser modelados como filas de espera. ... Simulação é limitada para 5 chegadas, chegada do cliente