Skip to content

排队论:M/M/1 与 M/M/c 服务窗口 ​

方法速览 ​

  • 主要用途 在随机到达、随机服务的场景下,估计排队长度、平均等待时间与资源(窗口/收银台/服务器)利用率,为「开几个窗口才够」提供定量依据。
  • 必要输入 到达率 λ(单位时间到达人数)、服务率 μ(单位时间每窗口服务人数)、窗口数 c(M/M/c)、排队规则(默认先到先服务 FIFO)。
  • 适用条件 泊松到达(到达间隔独立、服从指数分布)、指数分布服务时间、到达与服务相互独立、稳态(利用率 ρ=λ/(cμ)<1)。
  • 典型不适用情况 到达或服务有明显时段性/成批性、服务时间不是指数分布(如恒定服务时间)、顾客到达后可能中途放弃(不耐烦)、ρ≥1 系统必然无限增长。
  • 最低限度的验证方式 用解析公式核对指标(Little 公式 L=λW 必须自洽),再用固定 seed 的离散事件仿真交叉验证平均值,并检查 ρ<1 的稳定性前提。

快速回答 ​

排队论把一个服务系统抽象为「顾客按 λ 的速率随机到达,c 个窗口各自按 μ 的速率随机服务」。最核心的稳定性条件是利用率 ρ=λ/(cμ) 必须小于 1:当 ρ<1 时队列长度围绕一个有限均值波动;当 ρ≥1 时到达速度不低于服务能力,系统没有可归一化的稳态分布,Erlang-C 公式失效。

在稳态下,平均队列长度 Lq、平均等待时间 Wq 等指标有闭式解(M/M/1 与 M/M/c 的 Erlang-C 公式),且由 Little 公式 L=λW 把「人数」和「时间」两类指标串起来。若前提(泊松到达 + 指数服务)不成立,就用离散事件仿真直接模拟,公式只能作为近似。

从零理解 ​

想象中午的食堂打饭窗口。每分钟平均来 2 个人(λ=2),每个打饭师傅平均每分钟服务 3 个人(μ=3)。如果只有 1 个窗口,ρ=2/3<1,队长虽然会波动,但有有限的稳态均值。到达率升至每分钟 3 人时,ρ=1,到达与服务在平均速率上刚好相抵,队长仍会随机起伏,已经没有可归一化的稳态分布。

「窗口数」的作用是分摊服务能力:c 个窗口的总服务能力是 cμ,所以利用率要除以 c,即 ρ=λ/(cμ)。同样 λ=6,μ=3,开 2 个窗口 ρ=1 刚好饱和(危险),开 3 个窗口 ρ=2/3 才稳定。多窗口的价值不是让每个窗口更快,而是让总服务能力超过到达压力。

四个量的直觉:到达率 λ 决定「多久来一个人」;服务率 μ 决定「一个人服务多久」;利用率 ρ 决定「系统多忙」(越接近 1 越拥挤);窗口数 c 决定「有多少人在同时服务」。ρ 越接近 1,队伍长度和等待时间不是线性增长,而是非线性飙升(公式里出现 1−ρ 的分母)。

数学原理 ​

符号表 ​

符号含义单位
λ到达率(泊松过程强度)人/单位时间
μ每窗口服务率(指数服务强度)人/单位时间
c服务窗口数(c=1 退化为 M/M/1)个
ρ=λ/(cμ)每窗口利用率(流量强度)无量纲
a=λ/μ到达相对服务的「供给量」无量纲
Lq平均排队人数(不含正在服务者)人
L平均系统内人数(排队 + 服务中)人
Wq平均排队等待时间时间
W平均系统停留时间(等待 + 服务)时间
P0系统空闲(无人)的稳态概率概率

Little 公式:L = λW ​

Little 公式是排队论最通用的守恒关系,不依赖到达/服务的具体分布,只要系统处于稳态:

L=λW,Lq=λWq.

直觉:系统内平均人数 L,等于「到达速率 λ × 每人在系统内平均停留时间 W」。如果每分钟来 2 个人、每人平均待 1 分钟,那么任意时刻系统内平均就有 2×1=2 个人。由此还可推出 W=Wq+1/μ(停留时间 = 排队时间 + 平均服务时间 1/μ)与 L=Lq+a(人数 = 排队人数 + 正在服务人数,稳态下正在服务者平均为 a=λ/μ)。

M/M/1 稳态推导(生灭过程要点) ​

M/M/1 的「M」分别指泊松到达(Markov)与指数服务(Markov),因此系统内人数 N(t) 构成一个生灭过程:状态从 n 只能转移到 n+1(到达,速率 λ)或 n−1(服务完成,速率 μ,n≥1)。

稳态下,每个状态的「流入 = 流出」给出平衡方程(这里只列要点,省略完整概率论证明):

λP0=μP1,(λ+μ)Pn=λPn−1+μPn+1 (n≥1).

由递推可得稳态分布 Pn=(1−ρ)ρn(几何分布),其中 ρ=λ/μ<1 保证 ∑nPn=1 收敛。于是:

P0=1−ρ,L=∑n=0∞nPn=ρ1−ρ,Lq=L−ρ=ρ21−ρ.

再用 Little 公式得 W=L/λ、Wq=Lq/λ。注意 Lq=L−ρ 的直觉:平均排队人数 = 平均系统人数 − 平均正在服务人数(ρ)。

M/M/c 与 Erlang-C 公式 ​

c 个窗口时,服务总速率取决于状态:当系统内有 n<c 人时只有 n 个窗口在服务,服务速率为 nμ;当 n≥c 时 c 个窗口全忙,服务速率恒为 cμ。解这个生灭过程的平衡方程,得到 Erlang-C 公式:

P0=[∑k=0c−1akk!+acc!(1−ρ)]−1,Lq=P0⋅acρc!(1−ρ)2,

其中 a=λ/μ、ρ=a/c。其余指标仍由 Little 公式导出:Wq=Lq/λ、W=Wq+1/μ、L=Lq+a。c=1 时代入即回到 M/M/1 的公式(Lq=ρ2/(1−ρ))。

稳定性条件 ρ < 1 ​

稳态公式只在 ρ=λ/(cμ)<1 时成立。ρ≥1 时到达速率不小于总服务能力,当 ho>1 时系统平均吞吐能力低于到达率,积压长期增加。当 ho=1 时,随机队列处于临界状态,也没有有限的稳态平均等待时间。这也是「开几个窗口」的硬约束:窗口数 c 至少要满足 c>λ/μ(严格大于,取等号仍会不稳定)。

排队规则 ​

默认假设先到先服务(FIFO):顾客按到达顺序进入空闲窗口。本文的公式与仿真均基于 FIFO;换用优先级(如急诊优先)或后到先服务会改变等待时间分布,需重新建模。

前提不成立为何需要仿真 ​

稳态公式要求「泊松到达 + 指数服务」。现实中:

  • 服务时间恒定(如自助机、流水线)对应 M/D/c,等待时间通常比 M/M/c 更短(变异性越小排队越短);
  • 到达成批或有时段性(下课、午休)破坏泊松的「独立、平稳」假设;
  • 顾客会放弃(队伍太长就走)需要引入耐心/拒绝模型。

这些场景没有简单闭式解,就用离散事件仿真:按到达/服务分布生成随机事件,按时间顺序推进,直接统计平均等待与队列长度。仿真的代价是需要固定 seed 保证可复现,并用解析值(当公式适用时)交叉验证。

动态实验 ​

M/M/2 排队系统:到达 → 排队 → 服务窗口
到达λ=2空闲窗口1空闲窗口2

ρ = λ/(cμ) ≈ 0.33

λ 2μ 3c 2队列长度 0服务中 0/2累计服务 0平均等待(仿真) 0.000

理论 Wq(稳态公式) 0.042

系统稳定(ρ < 1)

t=0.0:队列长度 0,服务中 0/2 台,累计服务 0 人,平均等待 0.000。初始空系统,2 个窗口空闲。

1 / 204
演示 48 个时间单位内的离散事件(每帧 = 一次到达或一次服务完成)。左图:到达箭头 → 排队方块 → 2 个服务窗口(绿色圆 = 正在服务,方块 = 排队等待;队列过长时只显示前 12 个并标注「…+N」)。 右列:实时读数与理论对照。仿真为教学近似;稳态公式(理论 Wq)仅在泊松到达、指数服务且 ρ<1 时成立, 参数变化会自动重算并回到第 0 帧。

参数说明:

  • 到达率 λ:2–8(单位时间到达人数),越大队伍越长。
  • 服务率 μ:3–6(每窗口单位时间服务人数)。
  • 窗口数 c:1–5,总服务能力为 cμ。
  • seed:42 / 7 / 1 / 99,固定种子保证逐次可复现;改任何参数都会重算并回到第 0 帧。

动画每一帧对应一次离散事件(一次到达或一次服务完成),帧内队列长度、服务中窗口数、累计服务人数与累计平均等待都来自固定 seed 的 M/M/c 仿真(指数服务,mulberry32 确定性 RNG)。右列「理论 Wq」为稳态公式值:当 ρ<1 时显示 Erlang-C 的 Wq;当 ρ≥1 时不显示稳态值,只标出「系统不稳定」。下表为稳态公式的理论值(与 Python 算例、单元测试一致):

系统λμcρ=λ/(cμ)LqWqLW
M/M/12312/34/3 ≈ 1.3332/3 ≈ 0.66721
M/M/22321/31/12 ≈ 0.08331/24 ≈ 0.041673/43/8
M/M/36332/38/9 ≈ 0.8894/27 ≈ 0.14826/9 ≈ 2.88913/27 ≈ 0.481

仿真对照(λ=2、μ=3、c=2、seed=42,离散事件仿真)——理论 Wq=0.04167:

指标理论值仿真值(duration=10000)
平均等待 Wq0.041670.04266
平均队列长度 Lq0.083330.08591
利用率 ρ0.333330.33976

声明:仿真为教学近似;稳态公式仅适用于泊松到达、指数服务且 ρ<1 的稳态。动画从空队列起步,又只统计已经完成服务的顾客。有限时长下会同时看到抽样波动和起步偏差,临近满载时尤其明显。

从等待目标反推服务窗口 ​

假设每分钟到达 2 人,每个窗口平均每分钟服务 3 人,希望平均排队不超过 5 秒。一个窗口虽满足稳定条件,理论等待为 2/3 分钟(40 秒)。两个窗口的理论等待为 1/24 分钟(2.5 秒),满足这个平均值目标。若约束是「95% 的顾客等候不超过 5 秒」,应计算等待时间的尾概率或用重复仿真估计分位数。

代码实践 ​

完整代码 ​

下面直接展示仓库中的 examples/queueing.py,可用 python examples/queueing.py 直接运行。脚本实现 M/M/1 与 M/M/c 稳态公式(用解析分数断言核对),并用 heapq 事件队列做 M/M/c 离散事件仿真,打印仿真平均等待与理论 Wq 的相对误差,最后画出等待时间直方图与队列长度曲线。

py
# -*- coding: utf-8 -*-
"""排队论 M/M/1 与 M/M/c —— MathModel FAQ 可运行算例。

实现 M/M/1 与 M/M/c(Erlang-C)稳态公式,并用离散事件仿真(heapq 事件队列,
M/M/c,duration=20000,seed=42)估计平均等待时间,与理论 Wq 对比相对误差。

确定性 RNG:本文件 mulberry32 与前端 TS 引擎
(docs/.vitepress/theme/math/queueing.ts)逐位一致,同 seed 同序列;
不使用系统随机,保证跨语言可复现。

稳态公式(仅当泊松到达 + 指数服务、且 ρ<1 时成立):
  M/M/1:ρ=λ/μ;Lq=ρ²/(1−ρ);Wq=Lq/λ;L=Lq+ρ;W=Wq+1/μ;P0=1−ρ。
  M/M/c:a=λ/μ,ρ=a/c;P0=[Σ_{k=0}^{c−1} aᵏ/k! + aᶜ/(c!(1−ρ))]⁻¹;
         Lq=P0·aᶜ·ρ/(c!(1−ρ)²);Wq=Lq/λ;W=Wq+1/μ;L=Lq+a。

运行方式(本机实测:Python 3.14.8 + numpy 2.5.3 + matplotlib 3.11.2):
  python examples/queueing.py

输出:控制台数值表 + docs/public/examples/queueing-demo.png
     (左:等待时间分布直方图;右:队列长度随时间曲线)。
"""
import sys
import math
# heapq 按完成时间找最早释放的窗口;deque 按先到先服务保存排队者。
import heapq
from collections import deque
from pathlib import Path

import matplotlib
matplotlib.use('Agg')
import matplotlib.pyplot as plt
import numpy as np

plt.rcParams['font.sans-serif'] = ['Microsoft YaHei', 'SimHei']
plt.rcParams['axes.unicode_minus'] = False

ROOT = Path(__file__).resolve().parent.parent
OUT_DIR = ROOT / 'docs' / 'public' / 'examples'

MASK32 = 0xFFFFFFFF


def _to_i32(u: int) -> int:
    """把 [0, 2^32) 的位型转成有符号 32 位整数。"""
    return u - 0x100000000 if u >= 0x80000000 else u


def mulberry32(seed: int):
    """确定性 RNG,与前端 TS 引擎逐位一致。返回闭包,每次调用输出 [0,1)。"""
    a = seed & MASK32

    def next_() -> float:
        nonlocal a
        a = (a + 0x6D2B79F5) & MASK32
        t = a
        s1 = t ^ (t >> 15)
        s2 = t | 1
        t2 = (_to_i32(s1) * _to_i32(s2)) & MASK32
        s3 = t2 ^ (t2 >> 7)
        s4 = t2 | 61
        m2 = (_to_i32(s3) * _to_i32(s4)) & MASK32
        t3 = t2 ^ ((_to_i32(t2) + _to_i32(m2)) & MASK32)
        r = (t3 ^ (t3 >> 14)) & MASK32
        return r / 4294967296.0

    return next_


def _factorial(n: int) -> int:
    return math.factorial(n)


def mm1(lam: float, mu: float) -> dict:
    """M/M/1 稳态指标;ρ≥1 抛 ValueError。"""
    if lam <= 0 or mu <= 0:
        raise ValueError('到达率与服务率应为正数')
    rho = lam / mu
    if rho >= 1:
        raise ValueError('到达率不小于服务率,系统不稳定')
    # p0 为空系统概率;已知平均排队人数后,再用 Little 关系换算平均等待。
    p0 = 1.0 - rho
    lq = rho * rho / (1.0 - rho)
    wq = lq / lam
    l = lq + rho
    w = wq + 1.0 / mu
    return {'rho': rho, 'L': l, 'Lq': lq, 'W': w, 'Wq': wq, 'P0': p0}


def mmc(lam: float, mu: float, c: int) -> dict:
    """M/M/c(Erlang-C)稳态指标;ρ=a/c≥1 抛 ValueError。"""
    if lam <= 0 or mu <= 0:
        raise ValueError('到达率与服务率应为正数')
    if not isinstance(c, int) or c <= 0:
        raise ValueError('窗口数应为正整数')
    a = lam / mu
    rho = a / c
    if rho >= 1:
        raise ValueError('到达率不小于服务率,系统不稳定')
    # k<c 时还有空闲窗口,逐项加状态权重;满员之后用几何级数合并为 last。
    s = sum(a ** k / _factorial(k) for k in range(c))
    last = a ** c / (_factorial(c) * (1.0 - rho))
    p0 = 1.0 / (s + last)
    # Lq 是队中人数,L 是系统总人数;其差 a 是平均在服务的人数。
    lq = p0 * a ** c * rho / (_factorial(c) * (1.0 - rho) ** 2)
    wq = lq / lam
    w = wq + 1.0 / mu
    l = lq + a
    return {'a': a, 'rho': rho, 'L': l, 'Lq': lq, 'W': w, 'Wq': wq, 'P0': p0}


def simulate_mmc(lam: float, mu: float, c: int, duration: float, seed: int,
                 service_dist: str = 'exp') -> dict:
    """M/M/c 离散事件仿真(heapq 事件队列),返回聚合指标与逐事件记录。"""
    rng = mulberry32(seed)

    def sample_exp(rate: float) -> float:
        # 指数分布逆变换:X=−ln(U)/rate;U=1−rng()∈(0,1] 避免 U=0 时 log(0)。
        return -math.log(1.0 - rng()) / rate

    def sample_service() -> float:
        # 两种服务分布的均值均为 1/mu,便于观察服务时长波动的影响。
        return sample_exp(mu) if service_dist == 'exp' else 1.0 / mu

    now = 0.0
    next_arrival = sample_exp(lam)
    departures = []  # 忙碌服务台完成时刻的最小堆
    queue = deque()  # 排队顾客到达时刻(FIFO)
    wait_samples = []
    total_wait = 0.0
    max_wait = 0.0
    integral_queue = 0.0
    integral_busy = 0.0
    queue_over_time = []

    while True:
        # 跳到下一个到达或完成事件。事件之间忙窗数和队长保持不变。
        next_dep = departures[0] if departures else float('inf')
        event_time = min(next_arrival, next_dep)
        if event_time > duration:
            break
        # 按持续时间累加面积,除以观察时长才是时间平均队长。
        integral_queue += (event_time - now) * len(queue)
        integral_busy += (event_time - now) * len(departures)
        now = event_time

        if next_arrival <= next_dep:
            if len(departures) < c:
                # 有空窗立即开服,等待为零,同时安排服务完成事件。
                wait_samples.append(0.0)
                heapq.heappush(departures, now + sample_service())
            else:
                queue.append(now)
            next_arrival = now + sample_exp(lam)
        else:
            heapq.heappop(departures)
            if queue:
                # 完成服务时释放窗口,最早到达的排队者进入并记录等待。
                arrival = queue.popleft()
                wait = now - arrival
                wait_samples.append(wait)
                total_wait += wait
                if wait > max_wait:
                    max_wait = wait
                heapq.heappush(departures, now + sample_service())
        queue_over_time.append((now, len(queue)))

    integral_queue += (duration - now) * len(queue)
    integral_busy += (duration - now) * len(departures)
    # served 统计观察窗内开始服务并取得等待时长的人数,包含未完成服务者。
    served = len(wait_samples)
    return {
        'avg_wait': total_wait / served if served else 0.0,
        'avg_queue_length': integral_queue / duration,
        'utilization': integral_busy / (c * duration),
        'served': served,
        'max_wait': max_wait,
        'wait_samples': wait_samples,
        'queue_over_time': queue_over_time,
    }


def run_formula_checks():
    print('== M/M/1 与 M/M/c 稳态公式(与解析值逐位对照)==')

    r1 = mm1(2.0, 3.0)
    assert math.isclose(r1['rho'], 2 / 3, rel_tol=0, abs_tol=1e-12), r1
    assert math.isclose(r1['Lq'], 4 / 3, rel_tol=0, abs_tol=1e-12), r1
    assert math.isclose(r1['Wq'], 2 / 3, rel_tol=0, abs_tol=1e-12), r1
    assert math.isclose(r1['L'], 2.0, rel_tol=0, abs_tol=1e-12), r1
    assert math.isclose(r1['W'], 1.0, rel_tol=0, abs_tol=1e-12), r1
    assert math.isclose(r1['P0'], 1 / 3, rel_tol=0, abs_tol=1e-12), r1
    print(f'  M/M/1 λ=2, μ=3:ρ={r1["rho"]:.6f}, Lq={r1["Lq"]:.6f}, '
          f'Wq={r1["Wq"]:.6f}, L={r1["L"]:.6f}, W={r1["W"]:.6f}, P0={r1["P0"]:.6f}')

    r3 = mmc(6.0, 3.0, 3)
    assert math.isclose(r3['rho'], 2 / 3, rel_tol=0, abs_tol=1e-12), r3
    assert math.isclose(r3['Lq'], 8 / 9, rel_tol=0, abs_tol=1e-12), r3
    assert math.isclose(r3['Wq'], 4 / 27, rel_tol=0, abs_tol=1e-12), r3
    assert math.isclose(r3['L'], 26 / 9, rel_tol=0, abs_tol=1e-12), r3
    assert math.isclose(r3['W'], 13 / 27, rel_tol=0, abs_tol=1e-12), r3
    assert math.isclose(r3['P0'], 1 / 9, rel_tol=0, abs_tol=1e-12), r3
    print(f'  M/M/3 λ=6, μ=3:ρ={r3["rho"]:.6f}, Lq={r3["Lq"]:.6f}, '
          f'Wq={r3["Wq"]:.6f}, L={r3["L"]:.6f}, W={r3["W"]:.6f}, P0={r3["P0"]:.6f}')

    # c=1 与 M/M/1 结果一致(独立交叉验证)
    r1c = mmc(2.0, 3.0, 1)
    assert math.isclose(r1c['Lq'], r1['Lq'], rel_tol=0, abs_tol=1e-9), (r1c, r1)
    assert math.isclose(r1c['Wq'], r1['Wq'], rel_tol=0, abs_tol=1e-9), (r1c, r1)
    print('  M/M/c c=1 与 M/M/1 结果一致(容差 1e-9)')

    # 不稳定时应抛错
    for bad in [(mm1, (3.0, 3.0)), (mmc, (6.0, 3.0, 2))]:
        try:
            bad[0](*bad[1])
            raise AssertionError('应抛出不稳定的错误')
        except ValueError as exc:
            assert '不稳定' in str(exc), exc
    print('  ρ≥1 时正确抛出「系统不稳定」')
    return r1, r3


def run_simulation():
    print('== M/M/c 离散事件仿真(λ=2, μ=3, c=2, duration=20000, seed=42)==')
    lam, mu, c, duration, seed = 2.0, 3.0, 2, 20000, 42
    sim = simulate_mmc(lam, mu, c, duration, seed)
    theory = mmc(lam, mu, c)
    rel_err = (sim['avg_wait'] - theory['Wq']) / theory['Wq']
    print(f'  理论 Wq = {theory["Wq"]:.6f}(Lq={theory["Lq"]:.6f},ρ={theory["rho"]:.6f})')
    print(f'  仿真平均等待 = {sim["avg_wait"]:.6f}(相对误差 {rel_err * 100:+.2f}%)')
    print(f'  仿真平均队列长度 = {sim["avg_queue_length"]:.6f}(理论 Lq={theory["Lq"]:.6f})')
    print(f'  仿真利用率 = {sim["utilization"]:.6f}(理论 ρ={theory["rho"]:.6f})')
    print(f'  服务人数 = {sim["served"]},最大等待 = {sim["max_wait"]:.6f}')
    # 仿真均值与理论值应在合理范围(教学近似,非精确断言)
    assert abs(sim['avg_wait'] - theory['Wq']) < 0.02, (sim['avg_wait'], theory['Wq'])
    assert abs(sim['avg_queue_length'] - theory['Lq']) < 0.02, (sim['avg_queue_length'], theory['Lq'])
    assert abs(sim['utilization'] - theory['rho']) < 0.02, (sim['utilization'], theory['rho'])
    return sim, theory


def make_figure(sim, theory):
    OUT_DIR.mkdir(parents=True, exist_ok=True)

    fig, (ax_hist, ax_queue) = plt.subplots(1, 2, figsize=(11.0, 4.2), dpi=110)

    # 左图包含立即服务的零等待。两条竖线对照理论期望和有限时长的样本平均。
    waits = np.asarray(sim['wait_samples'], dtype=float)
    ax_hist.hist(waits, bins=50, color='#5d42bc', alpha=0.85)
    ax_hist.axvline(theory['Wq'], color='#1f8a4c', lw=1.6, ls='--',
                    label=f"理论 Wq={theory['Wq']:.4f}")
    ax_hist.axvline(sim['avg_wait'], color='#c0392b', lw=1.6, ls=':',
                    label=f"仿真均值={sim['avg_wait']:.4f}")
    ax_hist.set_xlabel('等待时间')
    ax_hist.set_ylabel('人数')
    ax_hist.set_title(f'等待时间分布(n={sim["served"]})')
    ax_hist.legend(frameon=False, fontsize=8)
    ax_hist.grid(alpha=0.2)

    # post 阶梯在事件后保持新队长直到下个事件,水平线为稳态期望 Lq。
    times, lengths = zip(*sim['queue_over_time']) if sim['queue_over_time'] else ([0.0], [0])
    ax_queue.step(times, lengths, where='post', color='#5d42bc', lw=1.2)
    ax_queue.axhline(theory['Lq'], color='#1f8a4c', lw=1.2, ls='--',
                     label=f"理论 Lq={theory['Lq']:.4f}")
    ax_queue.set_xlabel('时间')
    ax_queue.set_ylabel('队列长度')
    ax_queue.set_title('队列长度随时间(seed=42)')
    ax_queue.legend(frameon=False, fontsize=8)
    ax_queue.grid(alpha=0.2)

    fig.tight_layout()
    out = OUT_DIR / 'queueing-demo.png'
    fig.savefig(out)
    plt.close(fig)
    print(f'== 绘图已保存到 {out} ==')


def main() -> None:
    print('== 环境 ==')
    print(f'  Python {sys.version.split()[0]}')
    import numpy as _np, matplotlib as _mpl
    print(f'  numpy {_np.__version__}, matplotlib {_mpl.__version__}')
    run_formula_checks()
    sim, theory = run_simulation()
    make_figure(sim, theory)
    print('== 全部断言通过 ==')


if __name__ == '__main__':
    main()

运行方式 ​

bash
cd mathmodel-faq
pip install numpy matplotlib      # 本算例仅需 numpy + matplotlib
python examples/queueing.py

本机实测环境:Python 3.14.8、numpy 2.5.3、matplotlib 3.11.2。脚本不联网、不使用系统随机;所有断言失败时脚本以非零退出码退出。

输出结果(本机实际运行) ​

text
== 环境 ==
  Python 3.14.8
  numpy 2.5.3, matplotlib 3.11.2
== M/M/1 与 M/M/c 稳态公式(与解析值逐位对照)==
  M/M/1 λ=2, μ=3:ρ=0.666667, Lq=1.333333, Wq=0.666667, L=2.000000, W=1.000000, P0=0.333333
  M/M/3 λ=6, μ=3:ρ=0.666667, Lq=0.888889, Wq=0.148148, L=2.888889, W=0.481481, P0=0.111111
  M/M/c c=1 与 M/M/1 结果一致(容差 1e-9)
  ρ≥1 时正确抛出「系统不稳定」
== M/M/c 离散事件仿真(λ=2, μ=3, c=2, duration=20000, seed=42)==
  理论 Wq = 0.041667(Lq=0.083333,ρ=0.333333)
  仿真平均等待 = 0.043466(相对误差 +4.32%)
  仿真平均队列长度 = 0.087211(理论 Lq=0.083333)
  仿真利用率 = 0.336933(理论 ρ=0.333333)
  服务人数 = 40128,最大等待 = 2.030408
== 绘图已保存到 …docs\public\examples\queueing-demo.png ==
== 全部断言通过 ==

结果图 ​

排队论:等待时间分布与队列长度随时间曲线

关键参数 ​

参数含义本算例取值与效果
λ到达率2(仿真)/ 6(M/M/3 公式例),λ 越大队伍越长
μ每窗口服务率3,服务越快队伍越短
c窗口数1 / 2 / 3,c 增大分摊服务能力、降低等待
ρ=λ/(cμ)每窗口利用率必须 <1;越接近 1 等待越剧烈上升
duration仿真时长20000(Python)/ 10000(TS 测试),越长平均值越接近理论
seed随机种子42(默认),固定 seed 结果可复现

常见错误 ​

  • ρ≥1 仍用公式:ρ=λ/(cμ)≥1 时系统不稳定、稳态公式发散,却仍代入 Erlang-C 得到「负的 P0」或负等待。诊断信号是 1−ρ≤0;必须先增加窗口数 c 或提高 μ 使 ρ<1,否则只能用仿真观察队列随时间增长。
  • 忽略服务时间分布:公式默认指数服务。若实际是恒定服务(M/D/c),用 M/M/c 会高估等待时间(指数服务的变异性更大)。应先检验服务时间的直方图/变异系数,再决定用公式还是仿真。
  • 用单窗口公式算多窗口:把 M/M/1 的 ρ=λ/μ 直接套到 c 个窗口上,漏掉「除以 c」。正确利用率是 λ/(cμ);c 个窗口的总服务能力是 cμ 而不是 μ。
  • 仿真单次当结论:一次仿真是随机过程的一个样本,单次平均等待与理论值有抽样误差。应固定 seed 保证可复现、加长 duration 收敛,并与解析值(当公式适用时)或多次仿真的分布区间对照,而不是把某一次的数值当成精确答案。

专业速查 ​

项目内容
假设泊松到达(指数到达间隔)、指数服务时间、到达与服务独立、稳态 ρ<1、FIFO
参数λ(到达率)、μ(每窗口服务率)、c(窗口数)、排队规则
复杂度公式 O(c)(Erlang-C 求和 c 项);离散事件仿真 O(事件数·log c)(heapq)
优点闭式解直观、由 Little 公式自洽、直接回答「开几个窗口」;仿真可扩展任意分布
缺点只适用稳态与指数假设;ρ 接近 1 时等待对参数极敏感;现实放弃/成批/时段性需仿真
评价指标利用率 ρ、平均队列长度 Lq、平均等待 Wq、系统停留 W、空闲概率 P0
相关 FAQ代码能够运行,但结果无法复现怎么办?、如何判断一个模型是否可靠?

双语言实验 ​

到达率再高一点,需要多开一个窗口吗 ​

设服务大厅只有一队,顾客按泊松过程到达,两个窗口独立服务,单窗服务速率均为每分钟 3 人。将固定时段的到达率从每分钟 4 人提高到 5.7 和 5.94 人。这些是假设参数,用来展示稳态逼近容量时的变化。实际排班时要验证时段长度、服务分布以及顾客是否会离队。

令 a=λ/μ、Tj=aj/j!。在所有窗口都忙以后,稳态概率每多一人就再乘一个 ρ,因此 Erlang C 的分子是 Tc/(1−ρ),分母还需加上 ∑j=0c−1Tj。代码用递推复算以避开大阶乘。若 Bj=Tj/∑k=0jTk,将分子分母同时除以 Tj−1 可得

B0=1,Bj=aBj−1j+aBj−1,P(wait)=Bc1−ρ+ρBc.

按 Wq=P(wait)/(cμ−λ),当到达率接近容量,等待概率逼近 1,剩余服务能力又逼近 0,所以平均等待会陡增。图用对数纵轴同时显示两窗和三窗的等待曲线,竖虚线标出两个窗口的容量。Wq 计排队时间,如需在系统内停留时间,还要加平均服务时间 1/μ。 MIT M/M/c 平衡概率与 Erlang C

独立运行 ​

Python 在终端安装依赖 python -m pip install numpy matplotlib,下载文件后运行 python mmf_queueing.py。MATLAB 将 mmf_queueing.m 放入当前文件夹,在命令窗口运行 result = mmf_queueing(),基础实验无需额外工具箱。两种脚本均输出数值并绘制图形。

下载 Python 源码 · 下载 MATLAB 源码

用 M/M/1 稳态公式检查每小时到达 3 人、服务 5 人时,利用率 0.6、平均等候 0.3 小时、平均排队 0.9 人。到达率不低于服务率时没有该稳态。

最简版依赖 Python:无第三方依赖。MATLAB:基础功能,无需额外工具箱。

在源码所在目录运行 python mmf_min_queueing.py

py
import json
arrival, service = 3, 5  # 单位都是人/小时。
if not 0 < arrival < service:
    raise ValueError("该算例要求 0 < 到达率 < 服务率")
utilization = arrival / service

# M/M/1:系统停留 W=1/(μ-λ),减去平均服务时长 1/μ 得纯等候。
system_time = 1 / (service - arrival)
wait = system_time - 1 / service
queue = arrival * wait  # Little 定律 Lq=λWq。
assert abs(wait - .3) < 1e-12 and abs(queue - .9) < 1e-12
result = {"utilization": utilization, "wait_hours": wait, "queue_length": queue}
print("LAB_RESULT " + json.dumps(result, ensure_ascii=False))
下载当前源码

Python 用函数依次计算三个到达率,并以 math.factorial 复核小窗口数的直接公式。MATLAB 用行向量一次算出三个场景,a.^counts 通过隐式扩展获得一张“人数状态 × 场景”表。两种实现也检查 Lq=λWq 以及单窗口时 Wq=ρ/(μ−λ)。

到达率(人/分钟)两窗利用率到达顾客须等待的概率两窗平均排队(分钟)
4.000.66670.53330.2667
5.700.95000.92563.0855
5.940.99000.985016.4171

最后一个场景加到三个窗口后,wq_extra_server 约为 0.14219 分钟,也就是 8.53 秒。这个差距是稳态假设下的容量比较。若实际到达率持续变化,需以适用的时间窗口或离散事件仿真评价平均等待和超时比例。

参数练习与参考结论

把最后一个到达率改成每分钟 6 人。两个窗口此时 ρ=1,脚本停止,因为没有可归一化的稳态分布。单独将同一个到达率代入三个窗口,更充裕的服务能力使 ρ=2/3,此时 P(wait)=4/9、Wq=4/27 分钟,约 8.89 秒。

关联文章 ​

MathModel FAQ · 数学建模知识库