Simulação de uma rede PERT
Processos de nascimento e morte
Noções estudadas
Simulação de uma rede PERT
Processos de nascimento e morte
Noções estudadas
Nesta aula. . .
Simulação de uma rede PERT
Considere a seguinte rede de actividades, em que se admite que a duração
de cada uma das actividades não é conhecida com precisão:
1
Simulação de uma rede PERT
2
Processos de nascimento e morte
1
@2
/ 4
@
/ 3
/ 5
João Pedro PEDROSO
6
/ 7
@
/ 8
João Pedro PEDROSO
Métodos de Apoio à Decisão
Simulação de uma rede PERT
Processos de nascimento e morte
Noções estudadas
/ 10
>
?9
> 12
/ 11
/ 13
/ 14
>
Métodos de Apoio à Decisão
Simulação de uma rede PERT
Processos de nascimento e morte
Noções estudadas
Duração das atividades
Recorrendo à simulação, resolva as seguintes questões.
As estimativas para a duração mínima, máxima, e mais provável para cada
uma das actividades dada na tabela seguinte (em dias).
Actividade
(1,2)
(1,3)
(2,4)
(3,4)
(3,5)
(3,6)
(4,7)
(5,7)
(6,8)
(7,9)
a
4
2
1
6
5
7
5
1
2
10
b
8
8
7
12
15
18
12
3
6
20
m
6
4
3
9
10
12
9
2
3
15
João Pedro PEDROSO
Actividade
(7,10)
(8,9)
(8,11)
(9,10)
(10,14)
(11,12)
(11,13)
(12,13)
(12,14)
(13,14)
a
5
6
7
2
10
5
4
1
8
7
b
28
11
18
2
40
20
18
3
12
22
m
18
9
10
2
25
10
12
2
10
10
1
Determine a duração média do projecto, e compare-a com a solução da
aproximação analítica utilizada nesta disciplina.
2
Determine a probabilidade de o projecto ser concluído em menos de 50
dias.
3
Determine a probabilidade de a tarefa (1,3) ser crítica.
4
Determine as durações médias do projecto nas seguintes
circunstâncias:
1
2
Actividades (5,7) e (6,8) têm de começar ao mesmo tempo;
Actividades (5,7) só precisa de ser realizada se (3,5) terminar depois de
(3,4).
Compare-as com o valor anterior.
Métodos de Apoio à Decisão
João Pedro PEDROSO
Simulação de uma rede PERT
Processos de nascimento e morte
Noções estudadas
Métodos de Apoio à Decisão
Simulação de uma rede PERT
Processos de nascimento e morte
Noções estudadas
Simulador: código em Python
Processos de nascimento e morte
def simulate(N, V, A, P, S, a, b, m):
t = 0
p = {}
for (i,j) in A:
p[i,j] = 0
for k in range(N):
D = {} # activity durations
for (i,j) in A:
D[i,j] = betarnd(a[i,j],m[i,j],b[i,j])
tmin, critical = cpm(V, A, P, S, D)
t += tmin
for (i,j) in critical:
p[i,j] += 1
print "%12g\t%s" % (tmin, critical)
t = float(t)/N
for (i,j) in A:
p[i,j] = float(p[i,j])/N
return t, p
Exemplo:
Uma companhia telefónica recebe em média 140 chamadas/h.
O intervalo entre chamadas segue uma distribuição exponencial.
Uma telefonista pode atender em média 30 chamadas/h, tendo o tempo
de atendimento uma distribuição exponencial.
A companhia tem 7 telefonistas, e pode colocar 3 chamadas em espera;
as chamadas acima destas serão recusadas.
Pretende-se determinar:
1
Que fracção de tempo estão as telefonistas todas ocupadas?
2
Qual é a fracção de chamadas perdidas?
(código completo em http://www.dcc.fc.up.pt/~jpp/mad/pert.py):
João Pedro PEDROSO
Métodos de Apoio à Decisão
João Pedro PEDROSO
Simulação de uma rede PERT
Processos de nascimento e morte
Noções estudadas
Métodos de Apoio à Decisão
Simulação de uma rede PERT
Processos de nascimento e morte
Noções estudadas
Propriedades da distribuição exponencial
Processos de nascimento e morte
3
lambda exp(-lambda t)
A distribuição exponencial com
parâmetro λ tem densidade
a(t) = λe−λt ;
Processos estocásticos com tempo contínuo, em que o estado do
sistema em qualquer instante é descrito por um inteiro não negativo.
2.5
2
lambda
Leis de alteração nestes processos:
1.5
A média é E(A) = 1/λ;
1
0.5
A variância é varA = 1/λ2 ;
1
com probabilidade λj ∆t + O(∆t) ocorre um nascimento entre t e t + ∆t
2
com probabilidade µj ∆t + O(∆t) ocorre uma morte entre t e t + ∆t
um nascimento incrementa em uma unidade o estado do sistema (j → j + 1); uma
morte decrementa-o.
λj – taxa de nascimento
µj – taxa de morte
0
0
0.5
1
1.5
2
2.5
3
Lemma
Se uma variável aleatória A tem distribuição exponencial, então para t e ∆t
não negativos:
P(A > t + h|A ≥ t) = P(A > h)
Para um processo de chegada, se
o sistema esteve t horas no estado actual, ou se
o sistema esteve → 0 horas no estado actual
3
nascimentos e mortes são independentes entre si, e limt→0 O(∆t)/∆t = 0.
Com estas leis pode-se mostrar que a probabilidade de ocorrência de
mais do que um evento entre t e t + ∆t é O(∆t).
Estes processos ficam completamente especificados pelo conhecimento
de λj e de µj (sendo µ0 = 0).
a probabilidade de haver uma chegada nas próximas h horas é a
mesma (ausência de memória).
João Pedro PEDROSO
Métodos de Apoio à Decisão
João Pedro PEDROSO
Métodos de Apoio à Decisão
Simulação de uma rede PERT
Processos de nascimento e morte
Noções estudadas
Simulação de uma rede PERT
Processos de nascimento e morte
Noções estudadas
Sistemas com um servidor
Sistemas com mais do que um servidor
Ausência de memória: para um sistema no estado j, no instante t:
Exemplo:
as probabilidades de nascimento entre t e t + ∆t são independentes do
tempo que o sistema esteve no estado j
pode-se determinar como se uma chegada tivesse ocorrido no instante t
probabilidade de ocorrer um nascimento em [t, t + ∆t]:
R ∆t
−λt dt = 1 − e−λ∆t = λ∆t + O(∆t)
0 λe
1
2
3
3 servidores
taxa de nascimento: λ = 4
taxa de morte: µ = 5
A mesma coisa para a probabilidade de morte em [t, t + ∆t]:
R ∆t −µt
µe dt = 1 − e−µ∆t = µ∆t + O(∆t)
0
λ
0
λ
1
µ
λ
µ
λ
...
2
µ
µ
João Pedro PEDROSO
λ
j −1
λ
j
µ
4
0
µ
...
µ
4
4
3
2
5
λ
j +1
4
1
10
4
...
4
15
15
15
NOTA: se as chegadas ou os tempos de serviço não são exponenciais:
processos de nascimento/morte em geral não são apropriados.
Métodos de Apoio à Decisão
João Pedro PEDROSO
Simulação de uma rede PERT
Processos de nascimento e morte
Noções estudadas
Métodos de Apoio à Decisão
Simulação de uma rede PERT
Processos de nascimento e morte
Noções estudadas
Probabilidades dos estados em processos de nascimento/morte
Define-se Pij (t) como a probabilidade de estar no estado j no instante t,
se para t = 0 estava no estado i. (Tal como nos processos de Markov,
aproxima-se de um valor πj , independente do estado inicial.)
Relacionar, para ∆t pequeno, Pij (t + ∆t) com Pij (t)
Formas de se entrar no estado j em t + ∆t:
Estado Estado em
em t
t + ∆t
Probabilidade
j −1
j
Pi,j−1 (t)(λj−1 ∆t + O(∆t))
j +1
j
Pi,j+1 (t)(µj+1 ∆t + O(∆t))
j
j
Pij (t)(1 − µj+1 ∆t − λj−1 ∆t − 2O(∆t))
outro
j
O(∆t))
(I)
(II)
(III)
(IV)
Probabilidades estacionárias para processos de nascimento/morte
No estado estacionário, estuda-se o comportamento quando t → ∞
Fazendo πj = limt→∞ Pij (t), para t → ∞ temos πj ≈ Pij (t) (a derivada no
estado estacionário é zero)
Substituindo no sistema de equações anterior:
µ1 π1 = π0 λ0
(j = 0)
λj−1 πj−1 + µj + 1πj+1 = πj (λj + µj ) (j = 1, 2, . . .)
O sistema fica então:
π1 µ1 = π0 λ0
(j = 0)
(λ1 + µ1 )π1 = λ0 π0 + µ2 π2
(j = 1)
(λ2 + µ2 )π2 = λ1 π1 + µ3 π3
(j = 2)
...
(λj + µj )πj = λj−1 πj−1 + µj+1 πj+1
(j)
Resolução: exprimir todos os πj em termos de π0 , obtendo-se:
Assim, temos: Pij (t + ∆t) = (I) + (II) + (III) + (IV ) = . . .
πj = π0 cj , com cj =
Sistema infinito de equações diferenciais, em geral de resolução muito
difícil.
π0 =
−→ estudar o estado estacionário é mais fácil. . .
1+
λ0 λ1 . . . λj−1
µ1 µ2 . . . µj
1
P∞
j=1
cj
Se o somatório não for finito, não existe estado estacionário.
João Pedro PEDROSO
Métodos de Apoio à Decisão
João Pedro PEDROSO
Simulação de uma rede PERT
Processos de nascimento e morte
Noções estudadas
Métodos de Apoio à Decisão
Simulação de uma rede PERT
Processos de nascimento e morte
Noções estudadas
Exemplo
Uma companhia telefónica recebe em média 140 chamadas/h.
O intervalo entre chamadas segue uma distribuição exponencial.
Uma telefonista pode atender em média 30 chamadas/h, tendo o tempo
de atendimento uma distribuição exponencial.
A companhia tem 7 telefonistas, e pode colocar 3 chamadas em espera;
as chamadas acima destas serão recusadas.
Pretende-se determinar:
1
Que fracção de tempo estão as telefonistas todas ocupadas?
2
Qual é a fracção de chamadas perdidas?
São as que chegam ao sistema no estado 10: 2.6%.
π7 + π8 + π9 + π10 = 21.11%
João Pedro PEDROSO
Estado
0
1
2
3
4
5
6
7
8
9
10
λ
140
140
140
140
140
140
140
140
140
140
0
Métodos de Apoio à Decisão
µ
0
30
60
90
120
150
180
210
210
210
210
cj
1
4.66667
10.8889
16.9383
19.7613
18.4439
14.3453
9.56350
6.37567
4.25045
2.83363
πj
0.00917
0.04279
0.09984
0.15530
0.18118
0.16911
0.13153
0.08768
0.05846
0.03897
0.02598
109.068
1
João Pedro PEDROSO
Simulação de uma rede PERT
Processos de nascimento e morte
Noções estudadas
0.21109 →
Métodos de Apoio à Decisão
Simulação de uma rede PERT
Processos de nascimento e morte
Noções estudadas
Noções estudadas
Em média, quantas telefonistas estarão ocupadas?
Estado
0
1
2
3
4
5
6
7
8
9
10
λ
140
140
140
140
140
140
140
140
140
140
0
µ
0
30
60
90
120
150
180
210
210
210
210
cj
1
4.66667
10.8889
16.9383
19.7613
18.4439
14.3453
9.56350
6.37567
4.25045
2.83363
πj
0.00917
0.04279
0.09984
0.15530
0.18118
0.16911
0.13153
0.08768
0.05846
0.03897
0.02598
109.068
1
João Pedro PEDROSO
n
0
1
2
3
4
5
6
7
7
7
7
Métodos de Apoio à Decisão
n × πj
0
0.04279
0.19967
0.46590
0.72474
0.84553
0.78916
0.61379
0.40919
0.27280
0.18186
Processos de nascimento e morte.
Distribuição exponencial.
4.54542
João Pedro PEDROSO
Métodos de Apoio à Decisão
P10
j=7
πj
Simulação de uma rede PERT
Processos de nascimento e morte
Noções estudadas
Próxima aula
Processos de nascimento e de morte.
Cadeias de Markov.
João Pedro PEDROSO
Métodos de Apoio à Decisão