Um café pequeno tem um atendente e lugar para três clientes lá dentro, contando o que está sendo atendido. Os clientes chegam ao acaso, mais ou menos um a cada dois minutos, e um pedido leva um minuto em média. Quantas pessoas há lá dentro, em média? Quanto tempo um cliente passa lá? Com que frequência alguém é mandado embora na porta? O número de clientes lá dentro sobe e desce de um em um e, com as hipóteses certas, o futuro dele depende só do valor presente. Isso o torna uma cadeia de Markov, e toda pergunta vira uma pergunta sobre a distribuição estacionária dela.
Ao final você vai conseguir
- Usar o processo de Poisson para achar a chance de uma chegada num intervalo curto.
- Explicar por que o atendimento exponencial deixa o estado ser só o número de clientes.
- Montar a matriz de transição de uma fila em tempo discreto, incluindo os estados vazio e cheio.
- Resolver uma cadeia de nascimento e morte pelo balanço detalhado.
- Calcular L, Lq, W e Wq, usando a lei de Little com as chegadas que entram.
“As chegadas formam um processo de Poisson de taxa λ” quer dizer: os números de chegadas em trechos de tempo separados são independentes, e o número em qualquer trecho de comprimento t é Poisson com média λt. De forma equivalente, os intervalos entre chegadas são tempos exponenciais independentes com média 1/λ (o capítulo Distribuições comuns liga as duas coisas). Para transformar isso numa cadeia, cortamos o tempo em intervalos curtos de comprimento h e perguntamos o que acontece em cada um.
Os atendimentos são supostos exponenciais com taxa μ (média 1/μ). A exponencial não tem memória: um atendimento que já dura s minutos tem a mesma chance de terminar nos próximos h minutos que um que acabou de começar. É por isso que o estado pode ser só o número de clientes. Ninguém precisa lembrar há quanto tempo o atendimento atual está rodando. Com k atendentes ocupados ao mesmo tempo, o próximo término é o primeiro de k tempos exponenciais independentes:
Seja Xₖ o número de clientes no sistema (esperando ou sendo atendidos) depois de k intervalos, de 0 até a capacidade K. Em cada intervalo uma chegada acontece com chance a e um término com chance dₙ, de forma independente. Uma chegada e nenhum término: sobe um. Um término e nenhuma chegada: desce um. Os dois ou nenhum: o número fica.
O café: λ = 0,5, atendimento médio de 1 minuto, K = 3, h = 0,1
a = 1 − e^(−0,05) = 0,04877 e, com um atendente, d = 1 − e^(−0,1) = 0,09516 sempre que há alguém lá dentro. Arredondando para cinco casas:
| de ↓ para → | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | 0.95123 | 0.04877 | 0 | 0 |
| 1 | 0.09052 | 0.86535 | 0.04413 | 0 |
| 2 | 0 | 0.09052 | 0.86535 | 0.04413 |
| 3 | 0 | 0 | 0.09052 | 0.90948 |
Linha 0: uma chegada (0,04877) é o único jeito de sair. Linha 1: subir exige uma chegada e nenhum término, 0,04877 × 0,90484 = 0,04413; descer exige um término e nenhuma chegada, 0,95123 × 0,09516 = 0,09052. Linha 3: uma chegada sozinha é recusada, então a probabilidade de ficar recebe esses 0,04413 também.
Uma cadeia que só sobe ou desce um de cada vez é uma cadeia de nascimento e morte, e para ela vale o balanço detalhado: no longo prazo, o fluxo para cima pela aresta entre n e n + 1 é igual ao fluxo para baixo. Isso dá cada π(n + 1) a partir de π(n) com uma multiplicação, sem sistema para resolver, mesmo para K = 150.
Por que a lei de Little vale: observe o café por um tempo longo T e some o tempo de todo mundo lá dentro. Contando cliente por cliente, são cerca de λ_ef·T clientes × W minutos cada. Contando minuto por minuto, é o número de pessoas lá dentro em cada instante somado ao longo dos T minutos, cerca de L × T. As duas contagens são o mesmo total, então L·T = λ_ef·T·W e L = λ_ef W. Nada no argumento usou tempos exponenciais; a lei de Little vale para quase qualquer fila.
Quando h → 0, a ≈ λh e dₙ ≈ min(n, c)μh, então cada razão subir/descer tende a λ/(min(n + 1, c)μ): o h se cancela. Isso dá a distribuição exata da fila em tempo contínuo, escrita M/M/c/K (chegadas markovianas, atendimentos markovianos, c atendentes, capacidade K):
| L | Lq | W | Wq | π(3) | |
|---|---|---|---|---|---|
| cadeia, h = 0.1 | 0.7506 | 0.2689 | 1.6079 | 0.5759 | 0.0664 |
| exato (h → 0) | 0.7333 | 0.2667 | 1.5714 | 0.5714 | 0.0667 |
Barras: a distribuição estacionária da cadeia, π(n) = probabilidade de n clientes no sistema. Pontos: a resposta exata em tempo contínuo. W e Wq saem da lei de Little com as chegadas que entram, λ(1 − π(K)). Diminua h e as barras vão para cima dos pontos. A escolha embaixo dos controles é a única convenção que a discretização deixa em aberto: com o sistema cheio, se uma chegada e uma saída caem no mesmo intervalo, o recém-chegado ocupa o lugar liberado ou já tinha sido recusado? Isso importa cada vez menos à medida que h diminui. Aperte play para ver a cadeia rodar, um minuto simulado por segundo.
Com c atendentes, nada muda além de dₙ, que cresce com o número de ocupados até todos os c estarem trabalhando. Uma capacidade K grande também não é mais difícil: a fórmula do produto tem um fator por nível. Quando K é grande e λ < cμ (menos chegadas do que os atendentes dão conta), as probabilidades dos níveis mais altos são minúsculas, a perda π(K) é praticamente 0, e a fila se comporta como uma com lugar ilimitado. Se λ ≥ cμ, a fila cresce sem limite numa fila ilimitada, e numa limitada fica perto de cheia.
| Passo | O que fazer |
|---|---|
| 1 | Estados: o número no sistema, de 0 a K (K conta os que estão sendo atendidos). |
| 2 | Por intervalo: a = 1 − e^(−λh), e dₙ = 1 − e^(−min(n, c)μh) para cada n (d₀ = 0). |
| 3 | Linhas de P: subir a(1 − dₙ), descer (1 − a)dₙ, ficar o resto; em K a chegada sozinha é perdida (e escolha a convenção para chegada + saída). |
| 4 | π pelo balanço detalhado: π(n + 1) = π(n)·subir(n)/descer(n + 1), depois divida pelo total. |
| 5 | L = Σ nπ(n), Lq = Σ (n − c)π(n) para n > c. |
| 6 | λ_ef = λ(1 − π(K)), W = L/λ_ef, Wq = Lq/λ_ef. Confira: W − Wq ≈ 1/μ. |
| 7 | Compare com a resposta contínua M/M/c/K; uma diferença grande quer dizer h grande demais ou uma linha errada. |
Uma rodada de 10 perguntas
Acerte quantas conseguir. Os erros voltam no final, numa rodada de revisão.
Cada exercício é criado na hora, então uma rodada nova nunca é igual. O computador escolhe a resposta primeiro e monta a pergunta em volta dela, trabalhando com frações exatas, por isso o gabarito está sempre certo. As respostas são lidas de forma exata: 0,75, 3/4 e 6/8 contam como o mesmo número (quando a forma irredutível é pedida, 6/8 só recebe um lembrete). Uma resposta errada mostra a resolução linha por linha, na ordem em que a lição faz; o número novo de cada linha aparece colorido.
| Errado | Certo | Por quê |
|---|---|---|
| chance de término μh com 2 atendentes ocupados | 1 − e^(−2μh) | a primeira de duas exponenciais termina à taxa 2μ |
| um término a partir do estado 0 | d₀ = 0 | um sistema vazio não tem atendimento para terminar |
| uma chegada a partir de K vai para K + 1 | ela é recusada: o número fica em K | a capacidade inclui os clientes sendo atendidos |
| W = L/λ | W = L/(λ(1 − π(K))) | só as chegadas que entram passam tempo lá dentro |
| Lq = Σ n π(n) para n > c | Σ (n − c) π(n) | c dos n clientes estão sendo atendidos, não esperando |
| estado = número + tempo de atendimento até agora | só o número | atendimentos exponenciais não têm memória |
Ideias-chave
- Chegadas de Poisson: uma chegada num intervalo h com chance a = 1 − e^(−λh) ≈ λh; duas no mesmo intervalo têm chance ≈ (λh)²/2.
- Atendimentos exponenciais não têm memória, então o estado é só o número no sistema; k atendentes ocupados terminam à taxa kμ.
- Por intervalo: subir = a(1 − dₙ), descer = (1 − a)dₙ, ficar = o resto; d₀ = 0; em K uma chegada sozinha é perdida.
- Só movimentos de ±1: o balanço detalhado dá π(n + 1) = π(n)·P(n→n+1)/P(n+1→n).
- L = Σ nπ(n), Lq = Σ (n − c)π(n); W = L/λ_ef e Wq = Lq/λ_ef com λ_ef = λ(1 − π(K)).
- Quando h → 0 a cadeia tende à fila contínua M/M/c/K, π(n) ∝ Π λ/(min(k, c)μ).