Upload
buiphuc
View
235
Download
4
Embed Size (px)
Citation preview
1Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Conceitos básicos
Experimento aleatório:experimento com resul-tado incerto
Espaço Amostral: conjunto de todos os possíveisresultados em um experimento aleatório.
Espaço de Eventos: conjunto de todos os fatossobre os quais se quer uma medida de probabilidade.
Medida de Probabilidade: medida associada a cadaevento que representa sua frequência relativa numnúmero muito grande de experimentos.
2Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Espaço de Probabilidades: É o terno (Ω, E, P) onde:
Ω é um conjunto chamado espaço amostral;E é uma coleção de sub-conjuntos de Ω (cha-mados eventos), escolhida de modo a satisfazer:
1- Se A é um evento, então A é um evento;2- Se A1, A2, ... são eventos, sua união tam-bém é um evento;
P é uma função de E em R tal que:
1- P(A) ≥ 0 para todo A∈E;2- P(Ω) = 1;3- Se A1, A2, ... são eventos disjuntos (i.e. mú-tuamente exclusivos), então:
∑∞
=
∞
=
=
1ii
1ii )A(PAP U
3Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Consequências:
P(A)+P(A) = P(A∪A) = P(Ω) = 1
0 ≤ P(A) ≤ 1
Se A0 ⊂ A1⊂ A2 ⊂ ... ⊂ An ⊂ An+1 ⊂ ... então:
( )nnnnAlimP)A(Plim
∞→∞→=
Se P(A∩B) = P(AB) = P(A)P(B)diz-se que os eventos A e B são independentes
4Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Probabilidade Condicional:
Dado que um evento B aconteceu, qual a pro-babilidade de um evento A também ter acon-tecido?
Resp.: É a medida da interssecção A ∩ B emrelação à medida de B
Por definição:
)B(P)AB(P)B|A(P =
Se B1, B2, ... são mutuamente exclusivos eainda: Ω=U
iiB
então (regra da probabilidade total):
∑ ⋅=i
ii )B(P)B|A(P)A(P
Fómula de Bayes:
∑ ⋅⋅
=
iii
kkk )B(P)B|A(P
)B(P)B|A(P)A|B(P
5Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Quando o conjunto Ω for enumerável, é possível as-sociar a cada elemento de Ω uma probabilidade, demodo a satisfazer às condições anteriores.
Neste caso, todos os sub-conjuntos de Ω são eventose o valor de probabilidade associado a cada evento éa soma das probabilidades associadas a seus elementos.
Exemplo: Ω = Z, com: Ζ∈= n,21
31)n(P n
221:.obs
0nn =∑
∞
=
Se o conjunto não for enumerável, não é possívelfazer a mesma associação.
Exemplo: Ω = R. Para definir a função P(.), sejaa função f(x), x ∈R, tal que:
∫∞
∞−
≥= 0)x(h ,1dx)x(h
A seguinte definição especifica probabilidades paratodos os eventos de Ω:
∫∞−
=≤0x
0 dx)x(h)xx|x(P
6Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Variáveis Aleatórias:
Uma var. aleatória é uma função que as-socia a cada ω ∈ Ω um número (real)
X: Ω RPor razões de consistência, exige-se quepara todo x ∈R, o conjunto:
ω: ω ∈ Ω e X(ω) ≤ x = [X ≤ x]
pertença ao espaço de eventos E.
Função de distribuição cumulativa:
F(x) = P[X ≤ x]
F(x) é uma função monotonicamente não-decres-cente, contínua à direita e tal que 0 ≤ F(x) ≤ 1 eainda F(−∞) = 0 e F(∞) = 1
7Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Quando o conjunto Ω for enumerável, diz-seque a variável aleatória é discreta.
Neste caso, a função de distribuição cumulativaé uma "escada" (função descontínua à esquerda)
Quando o conjunto Ω não for enumerável, a variável aleatória pode ser contínua ou mista.
x
F(x)
1
x1 x2 x3 x4
x
F(x)
1
x1
8Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Pode-se definir vetores de v.a. e suas distribuiçõesconjuntas:
X = [X1 X2 ... Xn]
F(x1, x2, ..., xn) = P[X1 ≤ x1, X2 ≤ x2, ...,Xn ≤ xn ]
A distribuição marginal de Xi é dada por:
Fi(xi) = F(x1, x2, ..., xn) xj = ∞j ≠ i
As variáveis aleatórias X1, ...,Xn serão indepen-dentes se:
F(x1, x2, ..., xn) = F1(x1)F2(x2)...Fn(xn)
para todo x1, x2, ..., xn
9Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Função de densidade de probabilidade:
Dada uma função de distribuição cumulativa,F(x) define-se a função de densidade de pro-babilidade de uma v.a. como sendo:
dxdF)x(f =
x
f(x)
x1 x2 x3 x4
x
f(x)
x1
De modo geral:
∫=−=≤<b
a
dx)x(f)a(F)b(F]bXa[P
10Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Z = [X Y]
F(x,y) = P[X ≤ x, Y ≤ y]
Consideremos o vetor de v.a.'s bi-dimensional:
A densidade conjunta é dada por:
com a seguinte distribuição conjunta:
yxF)y,x(f
2
∂∂∂
=
De modo que:
∫ ∫∞− ∞−
βαβα=y x
dd),(f)y,x(F
As densidades marginais de X e Y são dadas por:
∫∞
∞−
==∂
∞∂= dy)y,x(f
dxdF
x),x(F)x(f x
x
∫∞
∞−
==∂∞∂
= dx)y,x(fdydF
y)y,(F)y(f Y
Y
11Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Dada uma distribuição conjunta, F(x,y), qual aprobabilidade P[X ≤ x | Y = y] ?
Obs.: a definição:)B(P)AB(P)B|A(P =
é indefinida, dado que P[Y=y] = 0
Define-se portanto a densidade condicional:
)y(f)y,x(f)y|x(f
Y
= (definida somente se fY(y)≠0)
A distribuição condicional é dada por:
∫∞−
αα==≤=x
d)y|(f]yY|xX[P)y|x(F
A regra da probabilidade total fica:
∫∞
∞−
⋅⋅=≤=≤ dy)y(f]yY|xX[P]xX[P Y
12Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Média, variância e desvio padrão
A esperança matemática, valor esperado ou médiade uma variável aleatória X é dada por:
∫∞
∞−
⋅⋅= dx)x(fx]X[E
De modo geral uma função de uma variável aleatóriatambém é uma variável aleatória.
Seja Y=g(X) uma v.a. obtida a partir da v.a. X. Tem-se:
∫∞
∞−
⋅⋅== dx)x(f)x(g)]X(g[E]Y[E
O momento de ordem n de uma v.a. X é obtidofazendo-se g(x)=xn
∫∞
∞−
⋅⋅== dx)x(fx]X[E]X[E nnn
13Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
A variância de uma v.a. X é definida por:
]])X[EX[(E]X[Var 2−=
22 ]X[E]X[E]X[Var −=
portanto:
O desvio padrão de X é dado por:
]X[VarX =σ
O coeficiente de variação de X é dado por:
]X[EC X
Xσ
=
14Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Uniforme)(xf
xa b
ab −1
12)ab(
2ab]X[E
bxa ,abax)x(F
bxa ,ab
1)x(f
22X
−=σ
+=
≤≤−−
=
≤≤−
=
Algumas densidades usuais:
15Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
)( xf
xµ
∞<<∞σ=σ
µ=
πσ= σµ−−
x-
]X[Efechada forma temnão )x(F
21)x(f
22X
2/)x(
2 e22
Normal
16Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
)(xf
x
µ
22X
x
x
/1/1]E[X
0 x,e1)x(F0,0x ,e)x(f
µ=σ
µ=>−=
>µ>µ=µ−
µ−
Exponencial
17Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
)( xf
x
18/)bcacabcba(3/)cba(]X[E
cxb )ac)(bc/()xc[(1bxa )ac)(ab/()ax(
)x(F
cxb )ac)(bc/()xc(2bxa )ac)(ab/()ax(2
)x(f
2222X
2
2
−−−++=σ
++=
≤≤−−−−≤≤−−−
=
≤≤−−−≤≤−−−
=
Triangular
ac −2
a b c
18Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Processos Estocásticos
Um processo estocástico X(t) = X(ω,t) é umacoleção de variáveis aleatórias indexadas por t.As variáveis aleatórias são definidas num espaçode probabilidades comum (Ω, E, P) com ω ∈ Ω.O domínio de t é algum sub-conjunto de R
•Para ω = ω0 fixo, a função X(ω0,t)=x(t) é umaamostra da trajetória do processo estocástico;
•Para t = t0 fixo, a função X(ω,t0) é uma v.a. igualao estado do processo estocástico no instante t0.
Exemplos:
X(ω,t) é um movimento browniano (processo regular,isto é, o futuro não pode ser determinado a partir dopassado, mas as estatísticas podem ser determinadasa partir de uma única amostra.)
X(ω,t) = R(ω)cos(αt+φ(ω)) (processo preditível ondeocorre o contrário)
19Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Distribuições e densidades
de 1a ordem:F x t P X t x( , ) [ ( ) ]= ≤
f x t F x tx
( , ) ( , )=
∂∂
de 2a ordem:F x x t t P X t x X t x( , , , ) [ ( ) , ( ) ]1 2 1 2 1 1 2 2= ≤ ≤
n21
n21n21n
n21n21
xxx)t,,t,t,x,,x,x(F
)t,,t,t,x,,x,x(f
∂∂∂∂
=
=
L
LL
LL
de ordem n:
]x)t(X,,x)t(X,x)t(X[P)t,,t,t,x,,x,x(F
nn2211
n21n21
≤≤≤==L
LL
21
21212
2121 xx)t,t,x,x(F)t,t,x,x(f
∂∂∂
=
20Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
média: η( ) [ ( )] ( , )t E X t x f x t dx= = ⋅ ⋅−∞
∞
∫
autocorrelação:
R t t E X t X t
x x f x x t t dx dx
( , ) [ ( ), ( )]
( , , , )
1 2 1 2
1 2 1 2 1 2 1 2
= =
=−∞
∞
−∞
∞
∫∫
autocovariância:
)t()t()t,t(R)t,t(C 212121 ηη−=
R(t,t) = E[X2(t)] é a potência do processoC(t,t) é a variância do processo.
obs.: se X(t) = h(t) (caso determinístico), então η(t) = h(t)
obs.: no caso determinístico R(t1,t2) = h(t1)h(t2)
obs.: no caso determinístico C(t1,t2) = 0
21Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Classificações
Processo Estocástico de Estado Contínuo:O espaço amostral Ω não é enumerável
Processo Estocástico de Estados Discretos ouCadeia: O espaço amostral Ω é enumerável
Processo Estocástico de Tempo Discreto ouSequência Estocástica: O domínio da variá-vel t é enumerável. Notação: Xk(ω) = Xk
Processo Estocástico de Tempo Contínuo: O domínio da variável t não é enumerável.
22Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Processos Estocásticos Estacionários
senso estrito:
senso largo:
X(t) e X(t+c) tem as mesmas distribuições e densi-dades, ou seja, para todo n:
)ct,,ct,ct,x,,x,x(F)t,,t,t,x,,x,x(F
n21n21
n21n21
+++==LL
LL
E[X(t)] = η(t) = constantee
)(g)tt(g)]t(X),t(X[E)t,t(R
21
2121
τ=−===
23Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Processos Estocásticos Independentes
Um processo estocástico de grande simplicidadeé uma sequência estocástica em que as v.a.'s X1(ω), X2(ω), ..., Xn(ω), ... são independentesumas das outras. Neste caso, para qualquer n:
)t,x(F)t,x(F)t,x(F)t,,t,t,x,,x,x(F
nnn222111
n21n21
⋅⋅⋅==
K
LL
)t,x(F)t,x(F)t,x(F)t,,t,t,x,,x,x(F
nn2211
n21n21
⋅⋅⋅==
K
LL
Se ainda todas as distribuições forem idênticas,diz-se que o processo (sequência) é independen-te e identicamente distribuído - iid
24Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Processos de Markov
Por definição, num Processo de Markov a pro-babilidade acima é igual a:
Consideremos uma sequência de instantes:
t0 ≤ t1 ≤ ... ≤ tk-1 ≤ tk
Suponhamos que no instante tk há observações dis-poníveis de um processo estocástico: x0, x1, ..., xk.Em geral a melhor informação sobre a v.a. X(tk+1)é obtida calculando-se a probabilidade condicional:
]x)t(X,,x)t(X,x)t(X|x)t(X[P 001k1kkk1k1k ===≤ −−++ L
]x)t(X|x)t(X[P kk1k1k =≤ ++
ou seja, o passado é sintetizado na informaçãotrazida pela última medida (propriedade de não-memória).
25Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
se o espaço amostral for discreto tem-se umacadeia de Markov
A propriedade de não-memória tem dois aspectos:
M1: Toda informação passada sobre o estadoé irrelevante.
M2: O tempo de permanência no estado cor-rente é irrelevante.
Se desde o instante t1 até o instante t2, o estadofor x2, tem-se:
P[X(t3) ≤ x3 | X(t2)=x2] = =P[X(t3) ≤ x3 | X(t)=x2, t1 ≤ t ≤ t2]
Num SDED o aspecto M2 interfere diretamenteno tempo inter-eventos, restringindo sua distri-buição a ser exponencial.
26Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Processo Semi-Markoviano
Um processo estocástico é dito Semi-Markovianose atender à restrição M1:
"Toda informação passada sobre o estadoé irrelevante."
em outras palavras, não é necessário haver me-mória dos estados passados, mas pode ser ne-cessário haver memória do tempo de permanên-cia no estado.
Este tipo de processo estocástico é mais flexí-vel para a modelagem de SDED's pois não res-tringe as distribuições dos tempos inter-eventosa serem exponenciais.
27Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Processo de Renovação ('Renewal')
Considere-se uma sequência de relógio estocásticacomo definida no cap. 2:
Vi,k = Vi,1, Vi,2, ..., i ∈ E, Vi,k ∈ R+, k=1,2,...
onde assumiu-se que as sequências de relógio são iid e independentes umas das outras. Portanto cada Vi,k é completamente caracterizada por uma função de distri-buição
Gi(t) = P[Vi ≤ t]
Considere-se agora o processo estocástico N(t)que conta o número de evento até o instante t,sendo que os instantes inter-eventos são dadospela sequência Vi,k
Por definição, o processo N(t) é chamdo deprocesso de renovação ('renewal')
28Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Processo de Poisson
Definição:
N(t) é um processo que conta o número de ocor-rências de eventos no intervalo (0, t]. O espaçode estados de N(t) é 0, 1, 2, ...
Consideremos um SDED com um único evento.
Obviamente N(0) ≤ N(t1) ≤ ... ≤ N(tk) se 0 ≤ t1 ≤ ... ≤ tk
A partir de alguma suposições simplificadoras,o objetivo é calcular P[N(t) = n] = Pn(t)
Se o processo de contagem satisfaz às hipótesespropostas a seguir, ele é chamado de processo decontagem de Poisson.
29Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Considere-se uma partição da reta real num númeroarbitrário de intervalos (tk−1, tk] , k = 1, 2, ...
Assume-se t0 = 0 e N(0) = 0;
Define-se: N(tk−1, tk) = N(tk) − N(tk−1)
Hipóteses
•H1: Dois eventos não podem ocorrer simultaneamente;
•H2: N(t1), N(t1, t2), ..., N(tk−1, tk), ... são variáveisaleatórias mutuamente independentes.
•H3: P[N(tk−1, tk) = n] pode depender do comprimentodo intervalo (tk − tk−1) mas não dos pontos tk e tk−1.
De H3:
P[N(α, α+t) = n] = P[N(t) = n]
30Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Passo 1: P[N(t) = 0] = P0(t) = e−λt
Passo 2: P[N(∆t) = 0] = 1 − λ∆t + o(t)
0t)t(olim:onde
0t=
∆→∆
Passo 3: P[N(∆t) = n] = o(t); n=2, 3, ...P[N(∆t) = 1] = λ∆t + o(t)
Passo 4:Pn(t+∆t) = (1 − λ∆t)Pn(t) + λ ∆t Pn−1(t) + o(t)
Passo 5: )t(P)t(Pdt
)t(dP1nn
n−λ+λ−=
Passo 6: ;0t ;e!n)t()t(P t
n
n ≥λ
= λ−
31Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
;0t ;e!n)t()t(P t
n
n ≥λ
= λ−
A expressão:
caracteriza completamente o processo N(t)e é chamada de distribuição de Poisson
obs.: Pn(t) = P[N(t) = n]; t é um parâmetro
Importância:
•Simplifica a análise de SDED;
•Aplicável em muitos problemas reais;
•Boa aproximação quando há superposiçãode múltiplos processos de natureza geral.
32Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Média da distribuição de Poisson:
t)t(Pn)]t(N[E0n
n ⋅λ=⋅= ∑∞
=
obs.: λ = E[N(t)]/t = taxa média de ocorrência
20 momento: t)t()]t(N[E 22 λ+λ=
Variância:
t)]t(N[E)]t(N[E)]t(N[Var 22 λ=−=
Propriedade:
Num processo de Poisson, os tempos inter-even-tos são distribuídos exponencialmente.
Vk = sequência dos tempos intereventos (é i.i.d.)
G(t) = P[Vk ≤ t] = 1 − e−λt ; tedtdG)t(g λ−⋅λ==
2
1]V[Var ; 1]V[Eλ
=λ
=
33Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Propriedade de não-memória
Considere-se um processo de Poisson onde:
z YV
tT T+z
ocorrência do último evento
instanteatual
próximoevento
V(ω): v.a. associada ao tempo intereventos
G(t) = P[V ≤ t] = 1 − e−λt ;
Y(ω): v.a. associada ao tempo residual
[V>z] é um evento dado; portanto [V ≤ z] não pode ocorrer
Pergunta-se: P[V ≤ z+t | V>z] = P[Y ≤ t | V>z]
34Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Tem-se:
t
z
z)tz(
e1)e1(1
)e1()e1(]zV[P1
]tzVz[P]zV[P
]zV e tzV[P]zV|tzV[P
λ−
λ−
λ−+λ−
−=
=−−
−−−=
≤−+≤<
=
=>
>+≤=>+≤
Portanto: P[V ≤ z+t | V>z] = P[Y ≤ t | V>z] = 1− e−λt
ou seja, a distribuição do tempo residual é indepen-dente de z e idêntica a G(t) !!
Esta é a propriedade de não-memória, indicando quenão é relevante o registro do tempo de permanência noatual estado.
35Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
A recíproca também é verdadeira:
Se P[V ≤ z+t | V>z] é independente de zentão P[V ≤ t] = 1 − e−λt para algum λ > 0
De modo geral tem-se:
Processos de Poisson
Intervalos intereventos exponenciais
Propriedade de não-memória
não demonstradoporém demonstrável
36Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Superposição de Processos de Poisson
Considere-se um SDED com m processos de Poissonsuperpostos e mutuamente independentes
m , 2, 1,i ;e1)t(G]tV[P tii
i K=−==≤ λ−
t
t
t
...
processo 1
processo 2
processo m
T
z1 Y1
z2 Y2
zm Ym
tprocesso j
Yj
...
Distribuição do tempo intereventos:
Y* = min Yii=1,2,...,m
P[Y* ≤ t] = 1 − e−Λt; Λ = λ1 + λ2 + ... + λm
37Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Paradoxo do Tempo Residual
Considere um ponto de ônibus com passagens poissonianas (média 1/λ). Um passageiro cheganum instante aleatório. Quanto, em média, o pas-sageiro espera pelo próximo ônibus?
R1: Em média o passageiro vai esperar metadedo intervalo entre dois ônibus: (1/2λ)
Contradição: e a propriedade de não-memória?
R2: Devido à propriedade de não-memória,o passageiro vai esperar, em média, 1/λ.
Contradição: Dado que o passageiro chega emqualquer ponto do intervalo entre dois eventos,então os ônibus passam em média a cada1/λ + 1/λ = 2/λ unidades de tempo.
38Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
A resposta R2 é a correta.
Solução do paradoxo:
•Há uma maior probabilidade de o passageiro che-gar num intervalo maior;
•A média dos intervalos nos quais chega um pas-sageiro é de fato 2/λ.
T1 T2 Tk−1 Tk
passageiro
Z~ Y~
V~
G(t) = P[V ≤ t]~ ~
g(t) é a densidade associada.~
Prova-se que E[V] = 2/λ~
39Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Teoria de Filas
Assunto Tradicional, voltado para uma classe deSDED's (problemas que envolvam compartilha-mento de recursos).
A teoria de filas não se confunde com o estudo de SDED's, pois:
•pode não ser o fenômeno predominante;
•não capta o comportamento dinâmico(ênfase nos aspectos estocásticos).
•Determinação do desempenho do sistema sobcertas condições;
•Desenvolvimento de ferramentas descritivas,no lugar de prescritivas
Objetivos:
40Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Especificação de um modelo:
a) Especificação dos modelos estocásticos paraos processos de chegada e de serviço.
b) Especificação dos parâmetros estruturais dosistema tais com capacidade de armazenaento,número de servidores
c) Especificação das políticas de operação("operating policies") tais como condi-ções de aceitação de clientes, priorizaçãoem relação a tipos de clientes, etc..
chegadaserviço
41Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Modelos Estocásticos
Yk = intervalo entre a (k−1)-ésima e a k-ésimachegada de clientes à fila; é a sequênciaestocástica associada à chegada de clientes.
É usual assumir que Yk é i.i.d. e portantoa distribuição:
A(t) = P[Y≤ t]descreve a chegada de clientes
É usual a notação: E[Y] = 1/λ, sendo λ a taxamédia de chegada de clientes.
Zk = tempo de serviço para o k-ésimo cliente
Assume-se também que Zk é i.i.d. e portantoB(t) = P[Z≤ t]
descreve o serviço.
É usual a notação: E[Z] = 1/µ, sendo µ a taxamédia de serviço.
42Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Parâmetros Estruturais
•Capacidade de armazenamento:É o número admissível de clientes na fila; usual-mente inclui o cliente em serviço (K = 1, 2, ... )
•Número de Servidores:Define o número de clientes sendo atendidosao mesmo tempo (m = 1, 2, ...)
Fila simples apresenta: m = 1K = ∞
43Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Políticas de Operação(operating policies)
•Número de classes de clientes que terão diferentesprioridades e tempos de serviço.
•Estratégias de escalonamento - definem que classedeve ser processada em primeiro lugar (ao terminarum serviço) ou sobre a oportunidade de realizar umapreempção.
•Disciplinas de fila - determinam a ordem de servi-ço, mesmo no caso de classe única, p. ex. FIFO, LIFO, aleatória, etc.
•Estratégias de admissão - independentemente dacapacidade de armazenamento, pode ser oportunonegar a admissão a alguns clientes, p. ex. clientescom baixa prioridade podem ser aceitos somentese a fila estiver vazia.
Ex. simples: •classe única;•todos os clientes são admitidos e servidos;
•FIFO.
44Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Notação A/B/m/K
A: distribuição dos tempos entre chegadas;B: distribuição dos tempos de serviço;m: número de servidores;K: capacidade de armazenamento (se omitida = ∞)
A distribuições A e B são usualmente designadaspela seguinte convenção:
G: distribuição geral, ou seja, não se sabe nadasobre os tempos de chegada/serviço;
GI: distribuição geral em que os tempos de che-gada/serviço são i.i.d.; (alguns autores utilizam G)
D: caso determinístico;
M: caso markoviano, isto é, os tempos são ex-ponencialmente distribuídos
Exemplos: M/M/1; GI/G/1; M/M/1/1; M/G/2; ...
45Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Sistemas Fechados
n clientes
N − n clientes
População finita de clientes → sistema fechado
Notação: A/B/m/K/N
número de clientes
obs.:•Se N = ∞ , N é omitido (sistema aberto);•Se N < ∞ e K = ∞ nota-se: A/B/m//N
46Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Desempenho de um Sistema de Filas
Variáveis de interesse (sequências estocásticas):
Yk: intervalo entre chegadas;Zk: tempo de serviço;Ak: instante de chegada do k-ésimo cliente;Dk: instante de partida do k-ésimo cliente;Wk: tempo de espera do k-ésimo cliente;Sk: tempo no sistema do k-ésimo cliente.
relacionadas da seguinte forma:
Sk = Dk − Ak
Sk = Wk + Zk
Dk = Ak + Wk + Zk
X(t) = comprimento da fila no instante t;U(t) = trabalho remanescente (workload) no instante t,
isto é, o tempo requerido para esvaziar o sistema.
Outras variáveis (processos estocásticos):
47Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
O tempo de espera Wk é uma importante medidado desempenho do sistema; em geral
P[Wk ≤ t] é dependente de k
mas quando k → ∝ pode existir uma distribuição es-tacionária, independente de k:
lim P[Wk ≤ t] = P[W ≤ t]k→∞
Se este limite existe, a v.a. W descreve o tempo deespera de um cliente típico em regime permanente
Considerações semelhantes podem ser feitas paraa sequência estocástica:
Sk → S
U(t) → U
ou para os processos estocásticos:
X(t) → X
48Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Medidas de Desempenho
Assume-se o alcance de regime permanente;são medidas de desempenho:
E[W], E[S], E[X]
Podendo-se definir ainda:
Utilização = fração de tempo em que o servidorestá ocupado;
Throughput = taxa em que os clientes deixam osistema após o serviço.
É fato que: utilização < 1throughput < µ
se há regime, então: taxa de entrada = taxa de saída
⇒ throughput = λ
49Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
define-se:
µλ
==
==ρ
serviço de média taxachegada de média taxa
tráfegodeeintensidad
)m
:servidores (mµ
λ=ρ
Algumas relações:
]nX[Pn ==π
utilização = 1 − π0throughput = µ(1 − π0) = λ
Portanto:01 π−=
µλ
ρ = intensidade de tráfego = utilização
relações válidas em regime, para m = 1 e K = ∞
Se π0 = 1 → permanentemente ocioso;Se π0 = 0 → permanentemente ocupado (fila instável)
0 ≤ ρ < 1
50Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Relações Dinâmicas
Tem-se: Wk = max0, Dk−1− Ak
Dk = Ak + Wk + ZkAk − Ak−1 = Yk
mas:portanto: Wk = max0, Wk−1 + Zk−1 − Yk
(expressão recursiva para os tempos de espera)
mas: Sk = Wk + Zk
portanto: Sk = max0, Sk−1 − Yk − Zk
(expressão recursiva para os tempos de sistema)
portanto: Dk = maxAk, Dk−1 + Zk
(expressão recursiva para os tempos de partida)
mas: Wk = Dk − Ak − Zk
Eqs. de caráter geral, independentes das distribui-ções das variáveis aleatórias.
51Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Lei de Little
n
t
nd(t)
na(t)u(t)
x(t)
12
...
AB
Área de A: tempo de sistema do 10 cliente;Área de B: tempo de sistema do 20 cliente;Área hachurada: tempo total de sistema até o instante t.
)t(n)t(u)t(s
a
=
t)t(u)t(x =
t)t(n)t( a=λ
tempo médio por cliente;
comprimento médio da fila;
taxa média de chegada de clientes.
52Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
)t(n)t(u)t(s
a
=t
)t(u)t(x =t
)t(n)t( a=λ
)t(s)t()t(x ⋅λ=
Hipóteses cruciais: λ=λ∞→
)t(limt
s)t(slimt
=∞→
Conclui-se: sx)t(xlimt
λ==∞→
Se os limites acima existirem para qualquertrajetória (ergodicidade):
lei de LittleE[X] = λE[S]
(não é uma demonstração)
53Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
E[X] = λE[S]
λE[X]
E[S]sistemade filas
•o raciocínio anterior não é uma demonstração;•contudo a lei de Little pode ser demonstrada;•não depende das distribuições das v.a.'s;•não depende das estratégias de operação;•em geral:
Para as fronteiras adequadas tem-se:
E[XQ] = λE[W]
E[XS] = λE[Z]
onde: XQ é o tamanho da fila excluído o servidor;XS é o número médio de clientes no servidor
54Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Duas observações:
A expressão:
sx λ=
)t(s)t()t(x ⋅λ=é verdadeira para qualquer t
A expressão:
só é verdadeira em regime, isto é, x significará a filamédia em regime se λ( t)e s(t) atingirem o regime
a)
b) λ é a taxa de clientes realmente entrando no sis-ma e isso deve ser levado em conta caso haja algum controle de admissão ou rejeição devidoa limites de armazenamento
55Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Análise da fila M/M/1
Se o tempo entre chegadas e o tempo de serviçotem distribuição exponencial então X(t) é umacadeia de Markov
Definimos, como anteriormente: πn(t) = P[X(t) = n]
Em geral, uma fila pode ser associada a um autô-mato estocástico em que o estado X(t) é o númerode clientes no sistema.
O processo estocástico X(t) é um GSMP
O cálculo destas probabilidades pode ser feito:
1. Por simulação, estimando o tempo de perma-nência no estado X(t) = n e dividindo-o pelo tem-po total de simulação;
2. Analiticamente
56Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Teorema:Para uma fila com processo de chegada de Poisson eindependentes do tempo de serviço, a probabilidadede que um cliente a chegar encontre n clientes na filaé igual à probabilidade de que o tamanho da fila seja n.
αn(t) = P[cliente ao chegar no instante t encontre X(t) = n]
αn(t) = πn(t)
Resultado da teoria de cadeias de Markov:
L 2, 1,j
);t()t()t()(dt
d1j1j1j1jjjj
j
=
πµ+πλ+πµ+λ−=π
++−−
)t()t(dt
d1100
0 πµ+πλ−=π
obs.: embora não demonstrado, este resultado éintuitivo.
57Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
L 2, 1,j
;0)( 1j1j1j1jjjj
=
=πµ+πλ+πµ+λ− ++−−
01100 =πµ+πλ−
Portanto, em regime:
Consequentemente:
0j21
1j10j π
µ⋅⋅µ⋅µ
λ⋅⋅λ⋅λ=π −
L
L
∑∞
=
−
µ⋅⋅µ⋅µλ⋅⋅λ⋅λ
+
=π
1j j21
1j100
1
1
L
L
58Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Para o caso M/M/1, tem-se, ∀n:
portanto:
∑∞
=
µλ
+
=π
1j
n0
1
1
µλ−µ
λ=
µλ
<µλ ∑
∞
= 1 se- tem1 se
n
1n
finalmente: ρ−=µλ
−=π 110
onde ρ = λ/µ é a intensidade de tráfego.
obs.: 0 ≤ ρ < 1
λn = λµn = µ
59Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Tem-se ainda:
nn
n )1()1( ρρ−=ρ−
µλ
=π
Esta é a distribuição estacionária para o compri-mento da fila M/M/1.
obs.: esta expressão não é válida para ρ ≥ 1 poisΣπn→∞
Utilização: = 1 − π0 = ρ = λ/µ
Throughput: = µ( 1 − π0) = λ
Se a fila M/M/1 é estável, o throughput é a taxade chegada (esperado, considerando o regime)
Se ρ ≥ 1, o throughput é µ, pois π0 = 0 e o ser-vidor estará operando constantemente.
60Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Comprimento médio da fila:
∑∑∞
=
∞
=
ρ⋅ρ−=π⋅=0n
n
0nn n)1(n]X[E
∑∑∑∞
=
∞
=
−∞
=
ρρ
=ρ=ρρ 0n
n
0n
1n
0n
n n1ndd
ρ−=ρ∑
∞
= 11
0n
n
∑∞
=
ρρ
=ρ− 0n
n2 n1
)1(1
∞=ρ−
ρ=
→ρ→ρ 1lim]X[Elim :.obs
11
Tem-se que:
portanto:
finalmente:ρ−
ρ=
1]X[E
ou seja, ao se tentar manter o servidor tão ocupado quanto possível, a qualidade do serviço decai através do aumento da fila e consequentemente do tempo de espera.
61Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Tempo médio de Sistema:
ρ−µ=
ρ−ρ
λ=
λ=
1
1
11]X[E1]S[E
Da lei de Little:
µ=
∞=
→ρ
→ρ
1]S[Elim
]S[Elim :.obs
0
1
que é o tempo médio de servviço
Tempo médio de Espera:
E[S] = E[W] + E[Z]
)1(1
1
1]W[E
ρ−µρ
=µ
−ρ−µ=
0]W[Elim
]W[Elim :.obs
0
1
=
∞=
→ρ
→ρ
62Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
grande var.
pequena var.
1 ρ
1/µ
E[S]
faixa de opera-ção recomendada
Do ponto de vista prático, recomenda-se que aoperação ocorra numa faixa de operação emque a utilização é baixa → atendimento rápido
Este resultado, embora deduzido para a filaM/M/1, é verificado em geral.
63Simulação de Sistemas Dinâmicos
3. Probabilidades, Estatística e Teoria de Filas
Transitórios
L 2, 1,j
);t()t()t()(dt
d1n1nn
n
=
µπ+λπ+πµ+λ−=π
+−
)t()t(dt
d1100
0 πµ+πλ−=π
Para o caso M/M/1, tem-se, ∀n: λn = λµn = µ
As equações diferenciais que relacionam as pro-babilidades P[N(t) = n] ficam portanto:
A solução não é trivial, mesmo para o caso simples:
∑++=
−
++
−−
−
−µ+λ−
ρρρ−+
+ρ+ρ=πK
2injj
2j
n
1in2
)1in(
in2
)in(t)(
n
)]at(J)1(
)at(J)at(J[e)t(
onde:
( )modif. Bessel de funções
!k)!kn(2
x)x(J
2a
inicial) (condição 1)0(
0k
k2n
n
21
i
∑∞
=
+
+=
µρ=
=π