PE_Lista5_Solucoes

Prévia do material em texto

Processos Estocásticos
Quinta Lista de Exercı́cios
1 Suponha que um organismo unicelular pode estar somente em dois estágios distintosA ouB. Um indivı́duo
no estágio A passa para o estágio B com uma taxa exponencial α. Um indivı́duo no estágio B se divide
em dois novos indivı́duos de tipo A com uma taxa exponencial β. Defina uma CTMC apropriada para a
população desses organismos e determine os parâmetros para esse modelo (tempo gasto em cada estado e
probabilidades de transição).
Seja NA(t) o número de organismos no estágio A no instante t e, de forma análoga, seja NB(t) o número de
organismos no estágio B. Assim, podemos tomar os pares ordenados 〈NA(t), NB(t)〉 para representar os estados
da CTMC. Isto é, o PE {〈NA(t), NB(t)〉, t ≥ 0} é uma CTMC com parâmetros
v〈n,m〉 = αn+ βm
P〈n,m〉;〈n−1,m+1〉 =
αn
αn+ βm
P〈n,m〉;〈n+2,m−1〉 =
βn
αn+ βm
.
2 Considere duas máquinas que são reparadas por um único técnico. A máquina i funciona por um tempo
exponencial com taxa λi antes de quebrar (com i = 1, 2). Os tempos de reparo (para quaisquer das duas
máquinas) são exponenciais com taxa µ. É possı́vel analisar esse sistema como um PNM? Se sim, quais são
os parâmetros? Se não, seria possı́vel analisá-lo?
Este não é um PNM porque somente a informação de quantas máquinas estão funcionando em um dado instante
não é suficiente para se analisar o sistema. Para tal é necessário saber também quais máquinas estão funcionando
em cada instante. Assim, podemos construir uma CTMC com os seguintes estados:
• 0: ambas as máquinas estão funcionando.
• 1: máquina 1 funcionando, 2 com defeito.
• 2: máquina 2 funcionando, 1 com defeito.
• 3: ambas máquinas com defeito, máquina 1 sendo consertada.
• 4: ambas máquinas com defeito, máquina 2 sendo consertada.
Essa CTMC pode ser representada pelo seguinte diagrama:
1
2
3
4
0
λ2
λ1
µ
µ
µ
µ
λ1
λ2
1
A CTMC acima possui os parâmetros tempo gasto em cada estado
v0 = λ1 + λ2 v1 = λ1 + µ v2 = λ2 + µ v3 = v4 = µ
e probabilidades de transição
P01 =
λ2
λ1 + λ2
P02 =
λ1
λ1 + λ2
P31 = P42 = 1
P10 =
µ
λ1 + µ
P14 =
λ1
λ1 + µ
P20 =
µ
λ2 + µ
P23 =
λ2
λ2 + µ
.
3 Considere um PNM com taxas de chegadas λi = (i+ 1)λ e taxas de saı́da µi = iµ, i ≥ 0.
a. Determine o tempo esperado para se sair do estado 0 e chegar no estado 4.
b. Determine o tempo esperado para se sair do estado 2 e chegar no estado 5.
Construindo a Cadeia de Markov que representa o PNM descrito no enunciado, temos
0 1 2 · · · i i+ 1 · · ·
λ0 = 1λ
µ1 = 1µ
λ1 = 2λ
µ2 = 2µ
λ2 = 3λ
µi = iµ
λi = (i+ 1)λ
µ(i+1) = (i+ 1)µ
Começando com E[T0] =
1
λ0
=
1
λ
, usamos a identidade E[Ti] =
1
λi
(
1 + µiE[Ti−1]
)
(veja slide 18 da aula 12)
para computar E[Ti] para i = 1, 2, 3, 4. Assim
E[T1] =
1
λ1
(
1 + µ1E[T0]
)
=
1
2λ
[
1 +
µ
λ
]
E[T2] =
1
λ2
(
1 + µ2E[T1]
)
=
1
3λ
[
1 +
µ
λ
+
(
µ
λ
)2]
E[T3] =
1
λ3
(
1 + µ3E[T2]
)
=
1
4λ
[
1 +
µ
λ
+
(
µ
λ
)2
+
(
µ
λ
)3]
E[T4] =
1
λ4
(
1 + µ4E[T3]
)
=
1
5λ
[
1 +
µ
λ
+
(
µ
λ
)2
+
(
µ
λ
)3
+
(
µ
λ
)4]
e, generalizando, vemos que
E[Ti] =
1
(i+ 1)λ
·
[
i∑
j=0
(
µ
λ
)i]
.
a. Como Ti é o tempo que o processo leva para transitar do estado i para o estado i + 1, o tempo esperado é
E[T0] + E[T1] + E[T2] + E[T3].
b. Mesma explicação do item anterior: E[T2] + E[T3] + E[T4].
4 Assume-se que cada indivı́duo de uma população procria com uma taxa exponencial λ e morre com uma taxa
exponencial µ. Além disso, há uma taxa exponencial θ de crescimento da população devido à imigração.
No entanto, a imigração não é permitida se o tamanho da população é maior ou igual a N . Modele essa
situação como um PNM.
2
Tomando cada estado X(t) como o tamanho da população no instante t, temos um PNM com
λn = nλ+ θ, n < N
λn = nλ, n ≥ N
µn = nµ .
5 Uma pequena barbearia, operada por um único barbeiro, pode acomodar no máximo dois clientes ao mesmo
tempo. Clientes em potencial chegam com uma taxa de Poisson de 3 por hora e os tempos de serviço são
VAs exponenciais independentes com média de 1/4 hora.
a. Qual é o número médio de clientes na barbearia?
b. Qual é a proporção de clientes em potencial que entram na loja?
Tomando o número de clientes na barbearia como o estado, temos um PNM com
λ0 = λ1 = 3, µ1 = µ2 = 4 .
Graficamente temos
0 1 2
λ0
µ1
λ1
µ2
e calculando as equações de fluxo para os estados 0 e 2, vem
λ0π0 = µ1π1 ⇒ π1 =
3
4
π0
µ2π2 = λ1π1 ⇒ π2 =
3
4
π1 =
(
3
4
)2
π0 .
Como π0 + π1 + π2 = 1, podemos resolver o sistema de equações para π0
π0 +
3
4
π0 +
(
3
4
)2
π0 = 1 ⇒ π0 =
16
37
.
a. O número médio de clientes na barbearia é
π1 + 2π2 =
[
3
4
+ 2
(
3
4
)2 ]
· π0 =
30
37
.
b. A proporção de clientes em potencial que entram na loja é
λ(1− π2)
λ
= 1− π2 = 1−
9
16
· 16
37
=
28
37
.
6 Um centro de atendimento é composto por dois servidores, cada um trabalhando com uma taxa exponencial
de dois serviços por hora. Clientes chegam com uma taxa de Poisson de três por hora. Assuma que a
capacidade do centro é de no máximo três clientes.
a. Que fração dos clientes em potencial entram no sistema?
b. Qual seria o valor do item anterior se houvesse somente um servidor no sistema com uma taxa duas
vezes mais rápida, isto é, µ = 4?
3
Tomando o número de clientes no centro como o estado, temos um PNM com
λ0 = λ1 = λ2 = 3, µ1 = 2, µ2 = µ3 = 4 .
Assim, as equações de fluxo se reduzem a
π1 =
3
2
π0
π2 =
3
4
π1 =
9
8
π0
π3 =
3
4
π2 =
27
32
π0
e portanto
π0 =
[
1 +
3
2
+
9
8
+
27
32
]−1
=
32
143
.
a. A fração de clientes em potencial que entram no sistema é
λ(1− π3)
λ
= 1− π3 = 1−
27
32
· 32
143
=
116
143
≈ 81.1% .
b. Com um único servidor trabalhando duas vezes mais rápido temos um PNM com
λ0 = λ1 = λ2 = 3, µ1 = µ2 = µ3 = 4 .
Agora, as equações de fluxo se reduzem a
π1 =
3
4
π0
π2 =
3
4
π1 =
(
3
4
)2
π0
π3 =
3
4
π2 =
(
3
4
)3
π0
e portanto
π0 =
[
1 +
3
4
+
(
3
4
)2
+
(
3
4
)3 ]−1
=
64
175
.
E finalmente, a nova fração de clientes que entram no sistema é
1− π3 = 1−
27
64
· 64
175
=
148
175
≈ 84.6% .
7 Considere um ponto de taxi onde taxis e clientes chegam de acordo com processos de Poisson com respec-
tivas taxas de um e dois por minuto. Um taxi fica sempre em espera, independente do número de taxis já
parados no ponto. Entretanto, um cliente que chega e não encontra um taxi disponı́vel vai embora, isto é,
não existe uma fila de espera de clientes.
a. Calcule o número médio de taxis esperando.
b. A proporção de clientes que chegam e conseguem um taxi.
Sejam os estados denotados pelo número de taxis esperando. Assim, temos um PNM com λn = 1 e µn = 2. Note
que essa CTMC corresponde a um modelo de fila M/M/1, cujas métricas já são conhecidas.
4
a. A média de taxis esperando é o tamanho médio da fila =
1
µ− λ
.
b. A proporção de clientes que chegam e conseguem um taxi é a proporção de clientes que chegam e encontram
ao menos um taxi esperando. A taxa de chegada desses clientes é 2(1− π0). A proporção dessas chegadas
é portanto
2(1− π0)
2
= 1− π0 = 1−
(
1− λ
µ
)
=
λ
µ
=
1
2
.
8 Para uma fila M/M/1, calcule
a. o número esperado de chegadas durante um perı́odo de serviço; e
b. a probabilidade de que nenhum cliente chegue durante um perı́odo de serviço.
a. Seja S uma VA indicando o tempo de serviço. Como a taxa de serviço é exponencial, sabemos que E[S] =
1/µ. O número esperado de chegadas buscado corresponde então a E[λS] = λE[S] = λ/µ. (O segundo
passo das equações é justificado pelo fato de λ ser uma constante com relação ao tempo de serviço, pois
chegadas e saı́das são eventos independentes.)
b. Novamente tomamos S como uma VA indicando o tempo de serviço. Buscamos a probabilidade condicional
de haver 0 chegadas dado que o perı́odo de serviço é S. Mas essa probabilidade é exatamente igual à
probabilidade o servidor terminar antes de uma novachegada (caso contrário o sistema muda de estado e o
tempo S é “resetado” – tente entender o motivo). Assim, a probabilidade pedida é
µ
λ+ µ
.
9 As máquinas de uma fábrica quebram com uma taxa exponencial de 6 por hora. A fábrica emprega apenas
um técnico que conserta as máquinas com uma taxa exponencial de 8 por hora. O custo causado pela
produção perdida quando há máquinas com defeito é de $10 por hora por máquina. Qual é o custo médio
causado por máquinas defeituosas?
Este problema pode ser modelado por uma fila M/M/1 com λ = 6 e µ = 8. O custo médio é dado por
$10 por hora por máquina × número médio de máquinas quebradas.
Mas o número médio de máquinas quebradas é exatamente L, cuja fórmula já é conhecida:
L =
λ
µ− λ
=
6
2
= 3 .
Portanto, o custo médio é de $30 por hora.
10 Considere um sistema M/M/1 onde clientes chegam com taxa λ e são servidos com taxa µ. No entanto,
assuma que em qualquer momento que o servidor estiver ocupado existe uma probabilidade dele quebrar,
levando o sistema a parar. A probabilidade de quebra é descrita por uma taxa exponencial α. Quando o
sistema para, todos os clientes que estavam no sistema partem e não são mais permitidas chegadas até que
o defeito for consertado. O tempo de reparo é exponencialmente distribuı́do com taxa β.
a. Defina os estados apropriadamente.
b. Descreva as equações de equilı́brio de fluxos.
5
a. O estados são n (n ≥ 0) e b. O estado n indica que há n clientes no sistema e o estado b que uma quebra
ocorreu. A CTMC que modela o sistema descrito é dada pelo diagrama abaixo.
0 1 2 n · · · n+ 1 · · ·
b
λ
µ
λ
µ
λ
µ
λ
µ
α α α
αβ
b. As equações de fluxo são
λπ0 = µπ1 + βπb
(λ+ µ+ α)πn = λπn−1 + µπn+1 n > 0
βπb = α(1− π0) .
6