数学建模算法全收录—排队论

无顾客
无顾客
n
无顾客 1 个顾客
n
1 个顾客 无顾客
n
1 个顾客 1 个顾客
n
9
上述四种情况发生概率分别为：
情况
时刻 t 顾客数
区间[ t，t + △t ) 到达顾客 离开顾客
概率
A
n
无顾客 无顾客 pn (t )(1 t )(1 t )
B
n+1
无顾客 1 个顾客 pn1(t )(1 t )t
时刻 t 顾客数
0 1 0
区间[ t，t + △t )
时刻 t + △t
到达顾客 离开顾客 顾客数
无顾客
无顾客
0
无顾客 1 个顾客
0
1 个顾客 1 个顾客
0
16
上述三种情况发生概率分别为：
情况
时刻 t 顾客数
区间[ t，t + △t ) 到达顾客 离开顾客
A
0
无顾客
无顾客
B
1
无顾客 1 个顾客
D
0
12
dpn (t ) dt
pn1(t )
pn1(t )
(
)
pn (t )
解上述方程的解是很困难的。这里只研究系统达到平
稳状态的情况，即系统运行了无限长时间之后，状态
概率分布不再随时间变化，显然此时 dpn (t ) 0
dt
13
由此可得，当 n≥1 时：
pn1 pn1 ( ) pn 0，n 1
第四节 单服务台负指数分 布排队系统
讨论单服务台的排队系统，并设定： 顾客到达过程服从泊松分布。 顾客服务时间服从负指数分布。
2

排队论课件
15
讨论系统处于平衡状态下的性质：
记 pn (t ) 为时刻t时系统处于状态n概率，即系统的瞬时分布 根据前面的约定，我们将主要分析系统的平衡分布，即当系统到 达统计平衡时时所处状态 n 概率，记为
pn , 又记：
N 系统处于平衡状态时队长，其均值为L，称为平均队长
N q 系统处于平衡状态时排队长，其均值为
P
n 0

n
1
有：
1 Cn P0 1 n1
于是：
P0
1 1 Cn
n 0
排队论课件
20
六、M/M/S等待制排队模型
1、单服务台模型 ①队长的分布
M / M /1/
记 pn PN n(n 1,2,) 为系统到达平衡状态后队长 N的概率分布， 注意到 n , n 0,1,2,,
排队论课件
L W
Lq Wq
25
2、多服务台模型
M /M /s/
记 pn PN n(n 1,2,) 为系统到达平衡状态后队长 N的概率分布， 注意到对个数s个服务台系统，有：
n n s
记 s s s
并设 s 1, 则：
n 1,2, s ns

M/D/1


D/M/1


M/E k/1

排队论课件Biblioteka 29结束语
排队论是专门研究带有随机因素，产生 拥挤现象的优化理论。也称为随机服务 系统。 排队论应用十分广泛。
排队论课件
30
n , n 0,1,2,,

n Cn n! s s!

常见仿真软件介绍与比较
功能方面
各软件均有独特的功能优势 ，如MATLAB/Simulink在数
学计算和可视化方面表现突 出，Arena则擅长离散事件仿
真。
易用性方面
MATLAB/Simulink和Arena 均提供友好的图形界面和丰 富的教程资源，便于用户快
速上手。
开放性方面
OMNeT作为开源软件，具有 较高的开放性和定制性，但 可能需要一定的编程基础。
完善。
建议和展望
在未来的学习和研究中，我将继续关注排队论领域的最新动态和研究成果，不断拓宽自 己的知识面和视野。同时，我也希望能够在实践中不断运用所学知识解决实际问题，提
高自己的实践能力和创新能力。
THANKS
感谢观看
成本效益
相较于实际系统搭建，仿真技术通常成本更低、周期更 短。
常见仿真软件介绍与比较
MATLAB/Simulink
提供强大的数学计算和可视化工具，适用于复杂系统建模与仿真。
Arena
专注于离散事件仿真，适用于制造、物流等领域的优化问题。
常见仿真软件介绍与比较
• OMNeT开源的网络仿真框架，适用于通 信网络性能评估。
06
总结与展望
本次课程重点内容回顾
排队论基本概念
介绍了排队论的定义、应用领域以及基 本术语和符号。
排队系统性能指标
介绍了评价排队系统性能的主要指标， 如平均队长、平均等待时间、服务强
度等。
排队系统组成与分类
详细阐述了排队系统的输入过程、服 务机构以及排队规则，并对排队系统 进行了分类。
经典排队模型及其求解
定义系统状态和变量
明确系统的状态和关键变量 ，如队列长度、等待时间等 。

约与区间长 Δt 成正比，即
∑ P (t, t + Δt ) = o( Δt )
n n=2
∞
（2）
-120-
在上述条件下，我们研究顾客到达数 n 的概率分布。 o 由条件 2 ，我们总可以取时间由 0 算起，并简记 Pn (0, t ) = Pn (t ) 。 由条件 1 和 2 ，有
o o
P0 (t + Δt ) = P0 (t ) P0 ( Δt )
P1 (t , t + Δt ) = λΔt + o( Δt ) （1） 其中 o( Δt ) ，当 Δt → 0 时，是关于 Δt 的高阶无穷小。 λ > 0 是常数，它表示单位时间
有一个顾客到达的概率，称为概率强度。 o 3 对于充分小的 Δt ，在时间区间 [t , t + Δt ) 内有两个或两个以上顾客到达的概率 极小，以致可以忽略，即
Pn (t + Δt ) = ∑ Pn − k (t ) Pk ( Δt ), n = 1,2,L
k =0 n
由条件 2 和 3 得
o
o
P0 ( Δt ) = 1 − λΔt + o( Δt )
因而有
P0 (t + Δt ) − P0 (t ) o( Δt ) = −λP0 (t ) + ， Δt Δt Pn (t + Δt ) − Pn (t ) o ( Δt ) . = − λPn (t ) + λPn −1 (t ) + Δt Δt 在以上两式中，取 Δt 趋于零的极限，当假设所涉及的函数可导时，得到以下微分方程
服务台（但顾客是一队）的模型。 1.4 排队系统的运行指标 为了研究排队系统运行的效率，估计其服务质量，确定系统的最优参数，评价系统 的结构是否合理并研究其改进的措施，必须确定用以判断系统运行优劣的基本数量指

机器发生故障需要维修
顾客
工人 病人 敌机 机器
服务台
公共汽车 医生 高炮 修理工
排队系统队列除了有形的还有无形的。
在上述顾客-服务台组成的排队系统中，顾客到来 的时刻与服务台进行服务的时间一般来说是随不同 的时机与条件而变化的，往往预先无法确定。因此， 系统的状态是随机的，故而排队论也称随机服务系 统。
最简单流应 x(t) :t 具 0有以下特征称
(1)流具有平衡性
对任何 a 和0 0 t1 t,2 tn x(a ti ) x(a)
的分布只取决于 t1,t2,而,t与n 无关a。
(2)流具有无后效性
(1 i n)
对互不交接的时间区间序列 ai ,bi (1 i， n)
x(bi ) 是x(a一i ) 组相互独立的随机变量。
N
pn
， 1
n0
1
p0
N 1
(1
)
1 N1
1 1
N
n p0 1
n0
1
pn
N 1
(1
)
n
1 N1
1 1
系统的各项指标
N
L
N
npn
n0
2
(N 1) N1
1
1 N1
1 1
Lq
N
(n
n0
1) pn
N 2
N N 1
N N1
1 1 N1
1 1
N 1
排队论模型
排队论模型
一、排队论的基本概念 二、单通道等待制排队问题
（M／M／1排队系统） 三、多通道等待制排队问题
（M／M／c排队系统）
一、排队论的基本概念
（一）排队过程 1.排队系统

P1
(m 1)
(m n 1) (m n)
P2
Pn 1
Pn
Pn 1
2



由状态转移图，可以建立系统概率平衡方程如下： P 1 mP 0, Pn 1 (m n 1)Pn 1 [(m n) ]Pn , 1 n m 1 Pm Pm 1 ,
E (T ) 1
n!
e

1.5 排队系统的常用分布
同样，对顾客服务时间常用的概率分布也是负指数分布， 概率密度为： t
f (t ) e
(t 0)
其中 表示单位时间内完成服务的顾客数，也称平均服务率． 3）爱尔朗分布：
(k ) k t k 1 kt 分布密度函数： f k (t ) (k 1)! e (t 0, k , 0)
N k k
模型的各数量指标参数如下： 1）系统里没有顾客的概率 1 1 N 1 P
0
1 1
1 1 N
2.2 系统容量有限的 M / M / 1/N / 模型
n P P0，n N 2）系统里有n个顾客的概率 n
3）在系统里的平均顾客数
3）服务时间的分布——在多数情况下，对每一个顾客的服务 时间是一随机变量，其概率分布有定长分布、负指数分布、 爱尔朗分布等.
1.3 排队系统的符号表示（Kendall符号）
根据不同的输入过程、排队规则和服务台数量，可以形成 不同的排队模型，为方便对模型的描述，通常采用如下的符 号形式：
X /Y / Z / A/ B /C
式中 表示平均到达率与平均服务率 之比，称为服务强度.
2.1 标准的 M / M / 1 模型

• 系统损失概率P损，即效劳系统满员的概率，或 者说，效劳员都忙着，排队位置满座的概率。
排队系统的运行指标
– 队长L系，即系统内顾客数的数学期望。 – 排队长L队，系统内排队顾客数的数学期望。 – 逗留时间W系，顾客在系统内逗留时间的数学期望。 – 排队时间W队，系统内顾客排队等待效劳时间的数学期望。这里
• 排队论的应用： • 广泛用于解决 局的通信线路的占线问题； • 车站、码头、机场等交通的枢纽的堵塞和疏导； • 故障机器的停机待修； • 水库的储存调节等有形无形的排队现象的问题。 • 本章内容 • 排队论的根本知识； • 常见的排队模型； • 讨论排队论系统的经济分析与最优化问题。
排队论的根本概念
数模排队理论
排队论的根本概念
• 在现实世界中，经常会发生为了获得某种效劳而 排队的现象
• 顾客到商店去买东西 • 病人到医院去看病 • 汽车去加油站加油 • 旅客到车站购票 • 当要求效劳的对象的数量超过效劳机构的容量就
会出现排队现象。 • 出现排队现象的原因：顾客到达人数和效劳时间
队模型算法
• 多通道损失制系统
• 模型：设系统内有n个效劳员，顾客来到效劳系统 时如果效劳员正在忙，顾客不能立即得到效劳， 那么顾客离去，另求效劳。
• 多通道损失制系统的各项效率指标：
• 损失概率P损，其中ρ＝λ/μ, λ为单位时间来的顾客
数即顾客流强度，μ为单位时间内一个效劳台效劳
的顾客数即效劳台能力．
• 问题的解决： • 增加效劳设施能减少排队现象，但这样势
必增加投资且可能出现因供大于求而使得 设施经常闲置、导致浪费，这通常不是一 个最经济的解决问题的方法。 • 作为管理人员来说，研究排队问题就是把 排对的时间控制在一定的限度内，在效劳 质量的提高和本钱的降低之间取得平衡， 找到最适当的解。

第五讲 排队论模型
【修理工录用问题】工厂平均每天有一台机器发生故障而需要修理，机器的故障数 服从泊松分布。 修理一台机器平均花费 20 元。 现有技术水平不同的修理工人 A 和 B， A 种修理工平均每天能修理 1.2 台机器， 每天工资 3 元； B 种修理工平均每天能修理 1.5 台机器，每天工资 5 元，两种修理工修理机器的时间为负指数分布。问工厂录用 哪种工人较合算？
Ls = ∑ np n = ∑ n(1 − ρ )ρ n = ρ /(1 − ρ ) = λ /( µ Nhomakorabea− λ ).
n =0 n =1
∞
∞
(2) 排队长： （等待的平均顾客数）
4
PDF 文件使用 "pdfFactory Pro" 试用版本创建
Lq = ∑ (n − 1) p n = ∑ (n − 1) ρ n (1 − ρ )
本讲主要内容
1. 2. 3. 4. 5. 排队论的基本概念 单服务台的排队模型 多服务台的排队模型 排队系统的最优化问题 数学建模实例：校园网的设计和调节收费问题
5.1 排队论的基本概念
5.1.1 什么是排队系统
排队论也称随机服务系统理论，它是 20 世纪初由丹麦数学家 Erlang 应用数学方法在研 究电话话务理论过程中而发展起来的一门学科， 在实际中有广泛的应用。 它涉及的是建立一 些数学模型， 藉以对随机发生的需求提供服务的系统预测其行为。 现实世界中排队的现象比 比皆是，如到商店购货、轮船进港、病人就诊、机器等待修理等等。排队的内容虽然不同， 但有如下共同特征： （1）有请求服务的人或物，如候诊的病人、请求着陆的飞机等，我们将此称为 “顾客” 。 （2）有为顾客提供服务的人或物，如医生、飞机跑道等，我们称此为“服务员” 。由顾 客和服务员就组成服务系统。 （3）顾客随机地一个一个（或者一批一批）来到服务系统，每位顾客需要服务的时间 不一定是确定的， 服务过程的这种随机性造成某个阶段顾客排长队， 而某些时候服务员又空 闲无事。 为了叙述一个给定的排队系统，必须规定系统的下列组成部分： 1.输入过程 即顾客来到服务台的概率分布。排队问题首先要根据原始资料，由顾客到 达的规律、 作出经验分布， 然后按照统计学的方法 （如卡方检验法） 确定服从哪种理论分布， 并估计它的参数值。 我们主要讨论顾客来到服务台的概率分布服从泊松分布， 且顾客的达到 是相互独立的、平稳的输入过程。所谓“平稳”是指分布的期望值和方差参数都不受时间的 影响。 2.排队规则 即顾客排队和等待的规则。排队规则一般有即时制和等待制两种。所谓即 时制就是服务台被占用时顾客便随即离去； 等待制就是服务台被占用时， 顾客便排队等候服 务。等待制服务的次序规则有先到先服务、随机服务、有优先权的先服务等，我们主要讨论 先到先服务的系统。 3.服务机构 服务机构可以是没有服务员的，也可以是一个或多个服务员的；可以对单

17
令 T0 = 0 Tn ：第 n 个顾客到达时刻， Xn：第 n 个顾客与第 n-1 个顾客到达的时间间隔。 则有
T0 T1 Tn
X n Tn Tn1 , n 1,2,
18
一般假定 { Xn }是独立同分布的，并记其分布函数 为 A( t )。关于{ Xn }的分布，排队论中经常用到的 有以下两种： ➢定长分布（D）：顾客相继到达时间间隔为确定 的常数。
Wq(t)：时刻 t 到达系统的顾客在系统中的等待时间。
pn(t)：时刻 t ，系统中有 n 个顾客的概率。
44
pn(t)
过渡状态
平稳状态
t
45
上述指标一般都是和系统运行的时间有关的随机变量 ，求这些随机变量的瞬时分布一般都是很困难的。 相当一部分排队系统，在运行了一定时间后，都会趋 于一个平稳状态（或称平衡状态），平稳状态下这些 指标和系统所处的时刻无关。
19
➢Poisson流（M）：顾客相继到达时间间隔的密度 函数为：
e t
a(
2. 排队
损失制排队系统
有限排队
队长有限排队系统
排队
混合制排队系统 等待时间有限排队系统
逗留时间有限排队系统 无限排队（等待制排队系统）
21
（1）有限排队
有限排队：排队系统中的顾客数是有限的，即系统 的空间是有限的，当系统被占满时，后面再来的顾 客将不能进入排队系统。
顾客相继到达时间 单个服务台
间隔为负指数分布
顾客源无限
M / M / 1 / ∞ / ∞ / FCFS
服务时间为负指数
分布
系统容量为无限
先到先服务
39
X/Y/Z/A/B/C
省略后三位

①模型特点
顾客总体为m个，每个顾客到达并经过服 务台后，任然回到原来总体，所以任然可 以到来。
②系统的稳态概率 Pn ；
1
P0 m m! ( )i
i0 (m i)!
Pn
m! (m n)!
(
)n
P0
,1
n
m
③系统运行指标 a、 系统中平均顾客数（队长期望值）
Ls m (1 P0)
排队论
（Queueing Theory）
生活中处处可见的排队现象
商店、超市等收款处排队付款 车站、民航、港口等售票处依次购买车船票 各种生产系统、存储系统、运输系统等一系
列现象 大型网游登陆前的排队等等
基本概念
研究随机的排队服务模型的主要工具是 排队论，排队论又称为随机服务系统理 论，是研究由顾客、服务机构及其排队 现象所构成的一种排队系统理论。
PnP10
P1 0 Pn1 (
) Pn
0
n 1
(3)
这是关于 Pn 的差分方程，表明了各状态间的转移 关系，可以用下图表示：
0
1
n-1
n
n+1
由上式可得 Pn ( / )n P0 令 / 1（否则队列将
排至无限远），由概率性质知
Pn 1
n0
将
Pn
的关系带入，
P0
n
n0
1
P0 1
求 limPn(t) Pn，此时系统的状态概率分布不再随时间变化 n
（4）利用 Pn 求系统运行指标
①队长：系统中的顾客数，期望记为 Ls ②排队长：系统中排队等待覅物的顾客数，期望记为 Lq ③逗留时间：一个顾客在系统中的停留时间，期望记为 Ws ④等待时间：一个顾客在系统中排队等待的时间，期望记