第五讲 排队论模型【修理工录用问题】工厂平均每天有一台机器发生故障而需要修理，机器的故障数服从泊松分布。
修理一台机器平均花费20元。现有技术水平不同的修理工人A和B，A种修理工平均每天能修理1.2台机器，每天工资3元；B种修理工平均每天能修理1.5台机器，每天工资5元，两种修理工修理机器的时间为负指数分布。问工厂录用哪种工人较合算？
本讲主要内容
1. 排队论的基本概念
2. 单服务台的排队模型
3. 多服务台的排队模型
4. 排队系统的最优化问题
5. 数学建模实例：校园网的设计和调节收费问题5.1 排队论的基本概念5.1.1 什么是排队系统排队论也称随机服务系统理论，它是20世纪初由丹麦数学家Erlang应用数学方法在研究电话话务理论过程中而发展起来的一门学科，在实际中有广泛的应用。
它涉及的是建立一些数学模型，藉以对随机发生的需求提供服务的系统预测其行为。现实世界中排队的现象比比皆是，如到商店购货、轮船进港、病人就诊、机器等待修理等等。排队的内容虽然不同，但有如下共同特征：
（1）有请求服务的人或物，如候诊的病人、请求着陆的飞机等，我们将此称为“顾客”。
（2）有为顾客提供服务的人或物，如医生、飞机跑道等，我们称此为“服务员”。由顾客和服务员就组成服务系统。
（3）顾客随机地一个一个（或者一批一批）来到服务系统，每位顾客需要服务的时间不一定是确定的，服务过程的这种随机性造成某个阶段顾客排长队，而某些时候服务员又空闲无事。
为了叙述一个给定的排队系统，必须规定系统的下列组成部分：
1.输入过程 即顾客来到服务台的概率分布。排队问题首先要根据原始资料，由顾客到达的规律、作出经验分布，然后按照统计学的方法（如卡方检验法）确定服从哪种理论分布，并估计它的参数值。我们主要讨论顾客来到服务台的概率分布服从泊松分布，且顾客的达到是相互独立的、平稳的输入过程。所谓“平稳”是指分布的期望值和方差参数都不受时间的影响。
2.排队规则 即顾客排队和等待的规则。排队规则一般有即时制和等待制两种。所谓即时制就是服务台被占用时顾客便随即离去；等待制就是服务台被占用时，顾客便排队等候服务。等待制服务的次序规则有先到先服务、随机服务、有优先权的先服务等，我们主要讨论先到先服务的系统
3.服务机构 服务机构可以是没有服务员的，也可以是一个或多个服务员的；可以对单独顾客进行服务，也可以对成批顾客进行服务。和输入过程一样，多数的服务时间都是随机的，且我们总是假定服务时间的分布是平稳的。若以ξn表示服务员为第n个顾客提供服务所需的时间，则服务时间所构成的序列{ξn}，n=1，2，…所服从的概率分布表达了排队系统的服务机制，一般假定，相继的服务时间ξ1，ξ2，…是独立同分布的，并且任意两个顾客到来的时间间隔序列{Tn}也是独立的。
如果按服务系统的以上三个特征的各种可能情形来对服务系统进行分类，那么分类就太多了。因此，现在已被广泛采用的是按顾客相继到达时间间隔的分布、服务时间的分布和服务台的个数进行分类。
排队论主要是对服务系统建立数学模型，研究如下内容：
（1）排队系统的概率分布问题，主要是研究队长分布、等待时间分布和忙期分布等；
（2）最优化问题：分为静态最优化和动态最优化，即为系统的最优设计和系统的最优运行问题；
（3）排队系统的统计推断：判断一个给定的排队系统符合哪种模型，以便于根据排队理论进行分析研究。
5.1.2 排队模型的标准形式
排队模型的标准形式为X/Y/Z/A/B/C，其中：
X 表示顾客来到时间间隔的分布类型；
Y 表示服务时间的分布类型；
Z 表示服务员个数；
A 系统容量;
B 顾客源个数;
C 服务规则.
例如先来先服务的等待排队模型主要由三参数法即X/Y/Z，“M/M/1/k/∞/FCFS”表示顾客到达间隔时间和服务时间均服从负指数分布，一个服务台，系统至多容纳k个顾客潜在的顾客数不限，先来先服务的排队系统。
“M/M/c”即Poisson输入，负指数服务时间分布，c个服务台的等待制排队模型。 “M/G/1”即Poisson输入，一般服务时间分布，单个服务台的等待制排队模型。
5.1.3 排队系统的运行指标
研究排队问题的目的，是研究排队系统的运行效率，估计服务质量，确定系统参数的最优值，以决定系统的结构是否合理，设计改进措施等。所以，必须确定用来判断系统运行优劣的基本数量指标，这些数量指标通常是：
（1）队长 指排队系统中的顾客数，它的期望值记为Ls；排队长，指在排队系统中排队等待服务的顾客数，其期望值记为Lq。
系统中的顾客数 = 等待服务的顾客数 + 正被服务的顾客数
所以Lq（或Ls）越大，说明服务效率越低。
（2）逗留时间 指一个顾客在排队系统中的停留时间，即顾客从进入服务系统到服务完毕的整个时间。其期望值记为Ws。等待时间，指一个顾客在排队系统中等待服务的时间，其期望值记为Wq。
逗留时间 = 等待时间 + 服务时间
（3）忙期 指从顾客到达空闲服务机构起到服务机构再次为空闲这段时间长度，即服务机构连续工作的时间长度。它关系到服务员的工作长度，即服务机构连续工作的时间长度。
它关系到服务员的工作强度、忙期的长度和一个忙期中平均完成服务的顾客数，这些都是衡量服务效率的指标。要计算以上这些指标必须知道系统状态的概率，所谓系统状态即时刻t时排队系统中的顾客数。如果时刻t时排队系统中有n个顾客，就说系统的状态是n，其概率一般用Pn(t)表示。
求Pn(t)的方法，首先要建立含Pn(t)的关系式，因t为连续变量而n只取非负整数，所以建立的Pn(t)的关系式一般是微分差分方程，这时要求方程的解是不容易的，有时即使求出也很难利用。因此，往往只求稳态解Pn，求Pn并不一定求t→∞时的Pn(t)极限，而只需由Pn'(t)=0，用Pn代替Pn(t)即可。
5.2 单服务台的排队模型设系统的输入过程服从泊松分布，服务时间服从负指数分布，单服务台的排队系统有以下三种情形：（1）标准型：M/M/1(M/M/1/∞/∞);（2）系统容量有限制：M/M/1/N/∞;（3）顾客源为有限的：M/M/1/∞/m.5.2.1标准型：M/M/1M/M/1模型是指顾客源为无限，顾客到达相互独立，到达过程是平稳的，到达率数服从参数为λ 的泊松分布：单服务台、队长无限、先到先服务；各顾客的服务时间服从参数为μ的负指数分布，且相互独立。
首先求出排队系统在任意时刻t的、状态为n的概率Pn(t)，已知顾客到达率服从参数为λ的泊松分布，服务时间服从参数为μ的负指数分布，由此决定了[t，t +△t]时间间隔内：（1）有1个顾客到达的概率为λ△t+o(△t)，没有顾客到达的概率是1-λ△t+o(△t)。（2）当有顾客在接受服务时，1个顾客被服务完了的概率是μ /3△t+o(△t)，没有服务完的概率是1-μ△t+o(△t)。（3）多于一个顾客到达或服务完的概率为o(△t)，均可忽略。
注1：因为单位时间内顾客到达数X～P（λ），所以Δt时间间隔内顾客到达数Y～ P（λλΔΔt），因而在Δt时间间隔内有1个顾客到达的概率为：P{ Y=1 } =λΔt·e-t=λΔt + o(ΔλΔt)，没有顾客到达的概率为P{Y=0}= e-t=1-λΔt + o(Δt)。注2：由于服务时间T～E（μ），故在有顾客接受服务时，1个顾客被服务完的概率为μΔP{T≤Δt }=1 -e-t=μΔt + o(Δt)，没有被服务完的概率为1-μΔt + o(Δt)。
在t+△t时刻，系统中有n个顾客的状态由t时刻的以下状态转化而来：①t时刻系统中有n个顾客，没有顾客到达且没有顾客服务完毕，其概率为：[1-λ△t+o(△t)][ 1-μ△t+o(△t)]= (1-λ△t-μ△t)+o(△t)；②t时刻系统中有n+1个顾客，没有顾客到达且有1个顾客服务完毕，其概率为：[1-λ△t+o(△t)][μ△t+o(△t)]= μ△t+o(△t)；③ t时刻系统中有n-1个顾客，有1个顾客到达且没有顾客服务完毕，其概率为：[λ△t+o(△t)][1-μ△t+o(△t)]= λ△t+o(△t)；④其他状态的概率为o(△t)。
因此，在t+△t时刻，系统中有n个顾客的概率Pn(t+△t)满足：Pn(t+ t)=Pn(t)(1 λ t ? t)+Pn+1(t)? t+Pn 1(t)λ t+ο( t).移项整理，两边同除以△t，得Pn(t+ t) Pn(t)ο( t)=λPn 1(t)+?Pn+1(t) (λ+?)Pn(t)+. t t令△t→0，得dPn(t)=λPn 1(t)+?Pn+1(t) (λ+?)Pn(t)dt当n=0时，因为 n=1,2L.P0(t+ t)=P0(t)(1 λ t)+P1(t)(1 λ t)? t+ο( t)所以有dP0(t)= λP0(t)+?P1(t). dt对于稳态情形，与t无关，其导数为零。
因此，得到λPn 1+?Pn+1 (λ+?)Pn=0,n>1 λP0+?P1=0这是关于Pn的差分方程，也反映出了系统状态的转移关系，即每一状态都是平衡的，求解得P1=(λ/?)P0，递推可得Pn=(λ/?)P0(n≥1). n由概率的性质知∑Pn=0∞n=1，将上式代入λ / μ <1时可得到P0=1 λ/?Pn=(1 λ/?)(λ/?). n因为顾客到达规律服 从参数为λ的泊松分布，服务时间服从参数为μ的负指数分布，其 期望值就分别为λ，1/μ。
所以λ表示单位时间内平均到达的顾客数，μ表示单位时间内能服务完的顾客数。如果令ρ=λ/μ，这时ρ就表示相同时间内顾客到达的平均数与能被服务的平均数之比，它是刻画服务效率和服务机构利用程度的重要标志，称ρ为服务强度。上面在ρ<1的条件下得到了稳定状态下的概率Pn，n=0，1，2，…。
其实，如果ρ>1，可以证明排队长度将是无限增加的，即使ρ=1的情况下，P0(t)也是随时间而变化的，系统达不到稳定状态.因此，这里只讨论ρ<1时情况，从上面的推导知Pn=(1-ρ) ρn n=0,1,2,….下面计算出系统的运行指标.(1) 队长（平均顾客数）：由于系统的状态为n时即系统中有n个顾客，由期望的定义得Ls=∑npn=∑n(1 ρ)ρn=ρ/(1 ρ)=λ/(? λ).n=0n=1∞∞(2) 排队长：（等待的平均顾客数）
Lq=∑(n 1)pn=∑(n 1)ρn(1 ρ)n=1n=1∞∞=ρ2/(1 ρ)=ρλ/(? λ).
可以证明，顾客在系统中逗留时间服从参数为μ-λ的负指数分布。因此，有(3) 系统中顾客的平均逗留时间：Ws=1/(? λ).(4) 系统中顾客的平均等待时间：Wq=Ws 1=ρ/(? λ) ?由以上结论可以看出，各指标之间有如下关系：；Lq=λWq；； Ls=λWs；Ws=Wq+1/?,Ls=Lq+λ/?，这些关系式称为Little公式.在指标的计算过程中，一般只要计算其中一个，其它的指标便可随之导出。
5.2.2系统容量有限制：M/M/1/N/ ∞因为是单服务台，排队系统的容量为N，即是排队等待的顾客最多为N-1，在某时刻一顾客到达时，如系统中已有N个顾客，那么这个顾客就被拒绝进入系统。
假设顾客平均到达率为λ，平均服务率为μ，在研究系统中有n个顾客的概率Pn(t)时，和标准型M/M/1研究方法相同，当n=N时有'PN(t)=λPN 1(t) ?PN(t)在稳态情形下，令ρ=λ，得 ?P1=ρP0 Pn+1+ρPn 1=(1+ρ)Pn,n=1,2,L,N 1P=ρPN 1 N在条件∑P=1下解上式得到 ii=0N1 ρ P= 01 ρN+1,ρ≠1 P=1 ρρn1≤n≤N.nN+1 1 ρ注：
（1）如果ρ=1（即λ=μ），由P0=P1=L=PN=1，即到达率和服务率相等，在N+1稳态情况下系统不会出现排队等待现象；
（2）这里因为是有限项的和，所以不要求ρ<1，但当ρ>1（λ>μ）时，表示单位时间内到达率大于服务率，系统的损失率增加，即被拒绝排队的数量增大.
下面给出系统的各种指标的计算结果：
（1） 队长：
Ls=∑nP=∑N+1=nn=0
Nn=0NNNnN,ρ=1 2n(1 ρ)ρn
Ls=∑npn=∑N+1n=1n=01 ρ
=(N+1)ρρ 1 ρ1 ρN+1
= L s -(1-P0) N+1; ,ρ≠1（2）排队长：Lq=∑(n 1)P
n=1Nn
N N ,ρ=12+1N = ； N+1 ρρρN ,ρ≠1N+1 11ρρ
（3）逗留时间： Ws=Ls/[?(1 P0)]；
（4）等待时间：Wq=Ws 1. ?
应该指出，Ws，Wq的导出过程中不是采用平均达到率λ，而是采用有效到达率λ效。这主要是由于当系统已满时，顾客的实际到达率为零，因为正在被服务的顾客的平均数为1 P0=λ效/?，于是λ效=?(1 P0).
5.2.3顾客源为有限的：M/M/1/∞/m
对该模型的顾客总体虽只有m个顾客，但每个顾客的到来并接受服务后，仍然回到顾客总体，即可以再次到来，所以对系统的容量是没有限制的，实际上系统中的顾客数永远不会超过m，即与模型M/M/1/m/m的意义相同。
与前面情况类似，假设每个顾客的到达率相同为λ，在系统外的平均顾客数为m-Ls,故系统的有效到达率为λe=λ(m-Ls).考虑稳态的情况，可得系统状态概率的平衡方程为
?P1=mλP0, ?Pn+1+(m n+1)λPn 1=[(m n)λ+?]Pn,(1≤n≤m 1)
?P=λP.m 1 m
注意到∑Pn=0mn=1，由递推关系不难求得系统状态的概率为1 =,Pi 0mm! λ ∑ i=0(m i)! ?n !mλ P= P0,1≤n≤m.n (m n)! ?该系统的运行指标为Ls=∑npn=mn=1mN?11m(1 P0),Ws= ,Wq=Ws , λ?(1 P0)λ?(λ+?)(1 P0)= L s-(1-P0). λLq=∑(n 1)Pn=mn=1
【例5-1】病人候诊问题 某单位医院的一个科室有一位医生值班，经长期观察，每小时平均有4个病人，医生每小时平均可诊5个病人，病人的到来服从泊松分布，医生的诊病时间服从负指数分布。
试分析该科室的工作状况。如果满足99%以上的病人有座，此科室至少应设多少个座位？如果该单位每天24h上班，病人看病1h因耽误工作单位要损失30元，这样单位平均每天损失多少元？如果该科室提高看病速度，每小时平均可诊6个病人，单位每天可减少损失多多少？可减少多少个座位？解 由题意知λ=4，μ=5，ρ=4/5，ρ=4/5=0.8<1，从而排队系统的稳态概率为：Pn=0.2×0.8n，n=0，1，2…该科室平均有病人数为：Ls=ρ/(1 ρ)=0.8/(1 0.8)=4（人）该科室内排队候诊病人的平均数为：Ls=Lq λ/?=4 0.8=3.2（人）看一次病平均所需的时间为：Ws=Ls/λ=4/4=1h排队等候看病的平均时间为：Wq=Ws 1/?=1 1/5=0.8h为满足99%以上的病人有座，设科室应设m个座位，则m应满足：P{医务室病人数≤m}≥0.99∑ρn=0mn(1 ρ)=1 ρm+1≥0.99ρm+1≤0.01ln0.01m≥ 1=20lnρ所以该科室至少应设20个座位。
如果该单位24h上班，则每天平均有病人24×4=96人，病人看病所花去的总时间为96×1=96 h。
因看病平均每天损失30×96=2880元。如果医生每小时可诊6个病人，ρ=2/3，则Ls=2（人），Lq=4/3（人）Ws=0.5h，Wq=1/3h，这样单位每天的损失费为96×0.5×30=1440元，因而单位每天平均可减少损失2880-1440=1440元，这时为保证99%以上的病人有座，应设座位数m≥ln0.01/ln(2/3)-1=11个，比原来减少了9个。
【例5-2】单人理发馆有6个椅子，当6个椅子都坐满时，后来到的顾客不进店就离开。顾客平均到达率为3人/h，理发平均需15min，试分析该服务系统。解 由题意知N=7，λ=3人/h，μ=4人/h，
因此，某顾客一到达就能理发的概率为：P0=(1 3/4)(1 (3/4)8)=0.27783/48(3/4)8平均需要等待的顾客数量为：Ls= =2.11人 81 (3/4)1 (3/4)Lq=Ls (1 P0)=2.11 (1 0.2778)=1.39人有效到达率为：λ效=?(1 P0)=4(1 0.2778)=2.89人/h.顾客在理发馆平均逗留时间为：Ws=Ls/λ效=2.11=0.73h=43.8min. 1.895.3多服务台的排队模型这里研究单队列、并列的C个服务台的情形，同单服务台类似，讨论如下三种模型：
（1）标准型：M/M/C(M/M/C/∞/∞);（2）系统容量有限制：M/M/C/N/∞;（3）顾客源为有限的：M/M/C/∞/m.5.3.1标准型：M/M/C（M/M/C/∞/∞）前提假设同M/M/1/∞/∞，顾客流为泊松流，平均到达率为λ，各服务台的服务时间满足负指数分布，而各而各服务台的工作是相互独立的（不搞协作），单个服务台的平均服务率为μ，则整个服务机构的平均服务率为Cμ(当n≥C),或nμ(当n1时，系统就会出现排队现象。类似地，可以得到系统状态概率的平衡方程?P1=λP0, (n+1)?Pn+1+λPn 1=(λ+n?)Pn,(1≤n≤C)C?P+λP=(λ+C?)P,(n>C).n+1n 1n
其中∑P
n=0∞n=1，且ρ=λ≤1，由递推关系可得系统状态概率 C?
C 1k1λ11λC 1P0=[∑()+()] C!1 ρ?k=0k!?
1λnn≤Cn!(?P0, Pn=
1(λnP,n>C0n C ? C!C
系统的运行指标为
∞∞λ(Cρ)CρLs=Lq+，Lq=∑(n C)Pn=∑kPk+C=P, 20?!(1)C ρn=C+1k=1
Wq=Lq/λ，Ws=Wq+1/?=Ls/λ.
5.3.2系统容量有限制：M/M/C/N/∞
假设系统中有C个服务台，系统的最大容量为N(N≥C),其它假设同前面一样。当系统客满（即系统中有N个顾客）时，有C个接受服务，N-C个在排队，再有顾客到来将被拒绝而离去，系统将有损失率。
当系统的状态为n时，每个服务台的服务率为μ,则系统的的总服务率：当0 类似地，可以得到系统的状态概率平衡方程 ?P1=λP0, (n+1)?P+λP=(λ+n?)P,(1≤n≤C) n+1n 1n C?P+λP=(λ+C?)P,(C≤n 其中∑P n=0Nn=1，且ρ=λ≤1，由递推关系可得系统状态概率 C? 1CCN C 11 Cρ(ρ ρ)k ∑(Cρ)+,ρ≠1, 1 ρk!C! P0= k=0 CC 1C 1k(C)+(N C+1),ρ=1, ∑k!!C k=0 1n(C)P0,0≤n≤Cρ n!Pn= C C(ρ)nP,C 系统的运行指标为 Ls=Lq+Cρ(1 PN)， (Cρ)CρN CN C[1()(1), Lq=∑(n C)Pn=P ρ N C ρρ02C!(1 ρ)n=C+1N Wq=Lq λ(1 PN),Ws=Wq+1/?.. CCN系统满员的损失率为P损=PN=ρP0. C! 特别地，当N=C时，即M/M/C/C/∞,此时系统为即时制服务，不允许顾客在系统内排队，亦即系统的状态概率为 1λ 1(Cρ)n P0=[∑()],Pn=P0, k!?C!k=0C 1k 相应地运行指标为 C1Lq=Wq=0,Ws=,Ls=∑nPn=Cρ(1 PC). ?n=1 5.3.3顾客源为有限的：M/M/C/∞/m 假设同前面的模型相同，系统的状态概率的平衡方程为 ?P1=mλP0, (n+1)?P+(m n+1)λP=[(m n)λ+n?]P,(1≤n≤C) n+1n 1n C?P+(m C+1)λP=[(m C)λ+C?]P,(C≤n 由递推关系可得状态概率 1C1CρCC P0=[∑()+m!k=0k!(m k)!mC!k1ρk 1mλ],ρ=, ∑C?k=0(m k)!mC m!λn ( (m n)!n!?)P0,0≤n≤C Pn= m!λn (P0,C 系统的运行指标为 Ls=∑nPn,，Lq=n=1mn=C+1∑(n C)Pn,Ws=mLqLs. Wq=λeλe有效到达率为λe=λ(m Ls)，且Ls=Lq+λeλ=Lq+(m Ls). ??类似的还有M/M/C/N/m，M/M/C/m/m，M/M/C/C/m等情况，可作相应的讨论.【例5-3】某火车站售票处有三个窗口，顾客的到达服从泊松分布，平均每分钟有0.9人到达，服务时间服从负指数分布，平均每分钟可服务0.4人。现假设排成一队，依次向空闲的窗口购票，试分析该排队系统。解 据题意知m=3，λ=0.9，μ=0.4,则ρ=P0=[1+λ0.9==0.75 ?3×0.40.910.9210.931+(+( 1=0.0743 0.42!0.43!0.41 0.75即整个售票处空闲的概率为0.0743。 (0.9/0.4)3×3/4平均队长 Lq=×0.0743=1.7/113!(1/4)2平均等待时间 Wq=1.7/0.9=1.89min平均逗留时间 Ws=1.89+1/0.4=4.39min5.4排队系统的最优化问题5.4.1 一般排队系统的最优化问题排队系统的最优化问题可分为系统设计最优化和系统控制最优化，系统设计最优化又称静态最优化，是指在服务系统设置以前根据一定的质量指标，找出参数的最优值，从而使系统设计最经济.例如：服务机构的规模大小、服务台的个数、系统容量大小等.系统控制最优化又称动态最优化，是指对已有的排队系统寻求使其某一目标函数达到最优的运行指标。