第六章排队论模型 排队论起源于1909年丹麦电话工程师A.K.爱尔朗的工作,他对电话通话拥挤问 题进行了研究。1917年,爱尔朗发表了他的著名的文章一“自动电话交换中的概率理 论的几个问题的解决”。排队论已广泛应用于解决军事、运输、维修、生产、服务、库 存、医疗卫生、教育、水利灌溉之类的排队系统的问题,显示了强大的生命力。 排队是在日常生活中经常遇到的现象,如顾客到商店购买物品、病人到医院看病常 常要排队。此时要求服务的数量超过服务机构(服务台、服务员等)的容量。也就是说, 到达的顾客不能立即得到服务,因而出现了排队现象。这种现象不仅在个人日常生活中 出现,电话局的占线问题,车站、码头等交通枢纽的车船堵塞和疏导,故障机器的停机 待修,水库的存贮调节等都是有形或无形的排队现象。由于顾客到达和服务时间的随机 性。可以说排队现象几乎是不可避免的。 排队论( Queuing Theory)也称随机服务系统理论,就是为解决上述问题而发展 的一门学科。它研究的内容有下列三部分 i)性态问题,即研究各种排队系统的概率规律性,主要是研究队长分布、等待 时间分布和忙期分布等,包括了瞬态和稳态两种情形 ⅱ讠)最优化问題,又分静态最优和动态最优,前者指最优设计。后者指现有排队 系统的最优运营 (i)排队系统的统计推断,即判断一个给定的排队系统符合于哪种模型,以便 根据排队理论进行分析研究。 这里将介绍排队论的一些基本知识,分析几个常见的排队模型。 §1基本概念 1.1排队过程的一般表示 下图是排队论的一般模型。 顾客随机1 股务机构 服务时间随机) 图1排队模型 图中虚线所包含的部分为排队系统。各个顾客从顾客源出发,随机地来到服务机构,按 定的排队规则等待服务,直到按一定的服务规则接受完服务后离开排队系统 凡要求服务的对象统称为顾客,为顾客服务的人或物称为服务员,由顾客和服务员 组成服务系统。对于一个服务系统来说,如果服务机构过小,以致不能满足要求服务的 众多顾客的需要,那么就会产生拥挤现象而使服务质量降低。因此,顾客总希望服务 机构越大越好,但是,如果服务机构过大,人力和物力方面的开支也就相应增加,从而 会造成浪费,因此研究排队模型的目的就是要在顾客需要和服务机构的规模之间进行权 衡决策,使其达到合理的平衡。 1.2排队系统的组成和特征 一般的排队过程都由输入过程、排队规则、服务过程三部分组成,现分述如下 1.2.1输入过程 输入过程是指顾客到来时间的规律性,可能有下列不同情况 (i)顾客的组成可能是有限的,也可能是无限的
-118- 第六章 排队论模型 排队论起源于 1909 年丹麦电话工程师 A. K．爱尔朗的工作，他对电话通话拥挤问 题进行了研究。1917 年，爱尔朗发表了他的著名的文章—“自动电话交换中的概率理 论的几个问题的解决”。排队论已广泛应用于解决军事、运输、维修、生产、服务、库 存、医疗卫生、教育、水利灌溉之类的排队系统的问题，显示了强大的生命力。 排队是在日常生活中经常遇到的现象，如顾客到商店购买物品、病人到医院看病常 常要排队。此时要求服务的数量超过服务机构（服务台、服务员等）的容量。也就是说， 到达的顾客不能立即得到服务，因而出现了排队现象。这种现象不仅在个人日常生活中 出现，电话局的占线问题，车站、码头等交通枢纽的车船堵塞和疏导，故障机器的停机 待修，水库的存贮调节等都是有形或无形的排队现象。由于顾客到达和服务时间的随机 性。可以说排队现象几乎是不可避免的。 排队论（Queuing Theory）也称随机服务系统理论，就是为解决上述问题而发展 的一门学科。它研究的内容有下列三部分： （i）性态问题，即研究各种排队系统的概率规律性，主要是研究队长分布、等待 时间分布和忙期分布等，包括了瞬态和稳态两种情形。 （ii）最优化问题，又分静态最优和动态最优，前者指最优设计。后者指现有排队 系统的最优运营。 （iii）排队系统的统计推断，即判断一个给定的排队系统符合于哪种模型，以便 根据排队理论进行分析研究。 这里将介绍排队论的一些基本知识，分析几个常见的排队模型。 §1 基本概念 1.1 排队过程的一般表示 下图是排队论的一般模型。 图 1 排队模型 图中虚线所包含的部分为排队系统。各个顾客从顾客源出发，随机地来到服务机构，按 一定的排队规则等待服务，直到按一定的服务规则接受完服务后离开排队系统。 凡要求服务的对象统称为顾客，为顾客服务的人或物称为服务员，由顾客和服务员 组成服务系统。对于一个服务系统来说，如果服务机构过小，以致不能满足要求服务的 众多顾客的需要，那么就会产生拥挤现象而使服务质量降低。 因此，顾客总希望服务 机构越大越好，但是，如果服务机构过大，人力和物力方面的开支也就相应增加，从而 会造成浪费，因此研究排队模型的目的就是要在顾客需要和服务机构的规模之间进行权 衡决策，使其达到合理的平衡。 1.2 排队系统的组成和特征 一般的排队过程都由输入过程、排队规则、服务过程三部分组成，现分述如下： 1.2.1 输入过程 输入过程是指顾客到来时间的规律性，可能有下列不同情况： （i）顾客的组成可能是有限的，也可能是无限的
(i)顾客到达的方式可能是一个一个的,也可能是成批的 ii)顾客到达可以是相互独立的,即以前的到达情况对以后的到达没有影响 否则是相关的 (iv)输入过程可以是平稳的,即相继到达的间隔时间分布及其数学期望、方差等 数字特征都与时间无关,否则是非平稳的。 1.2.2排队规则 排队规则指到达排队系统的顾客按怎样的规则排队等待,可分为损失制,等待制和 混合制三种 (i)损失制(消失制)。当顾客到达时,所有的服务台均被占用,顾客随即离去。 (i)等待制。当顾客到达时,所有的服务台均被占用,顾客就排队等待,直到接 受完服务才离去。例如出故障的机器排队等待维修就是这种情况。 (i)混合制。介于损失制和等待制之间的是混合制,即既有等待又有损失。有 队列长度有限和排队等待时间有限两种情况,在限度以内就排队等待,超过一定限度就 离去。 排队方式还分为单列、多列和循环队列。 1.2.3服务过程 (i)服务机构。主要有以下几种类型:单服务台;多服务台并联(每个服务台同 时为不同顾客服务):多服务台串联(多服务台依次为同一顾客服务);混合型。 (i)服务规则。按为顾客服务的次序采用以下几种规则 ①先到先服务,这是通常的情形。 ②后到先服务,如情报系统中,最后到的情报信息往往最有价值,因而常被优先处 ③随机服务,服务台从等待的顾客中随机地取其一进行服务,而不管到达的先后 ④优先服务,如医疗系统对病情严重的病人给予优先治疗 1.3排队模型的符号表示 排队模型用六个符号表示,在符号之间用斜线隔开,即X/Y/Z/A/B/C。第一 个符号X表示顾客到达流或顾客到达间隔时间的分布;第二个符号Y表示服务时间的 分布;第三个符号Z表示服务台数目;第四个符号A是系统容量限制;第五个符号B是 顾客源数目;第六个符号C是服务规则,如先到先服务FCFS,后到先服务LCFS等。并 约定,如略去后三项,即指X/Y/Z/∞/∞/FCFS的情形。我们只讨论先到先服务FCFS 的情形,所以略去第六项 表示顾客到达间隔时间和服务时间的分布的约定符号为 M一指数分布(M是 Markov的字头,因为指数分布具有无记忆性,即 Markov 性); D一确定型( Deterministic EA一k阶爱尔朗( Erlang)分布; G一一般( general)服务时间的分布 GI一一般相互独立( General Independent)的时间间隔的分布。 例如,M/M/1表示相继到达间隔时间为指数分布、服务时间为指数分布、单服 务台、等待制系统。D/M/c表示确定的到达时间、服务时间为指数分布、C个平行 服务台(但顾客是一队)的模型。 1.4排队系统的运行指标 为了研究排队系统运行的效率,估计其服务质量,确定系统的最优参数,评价系统 的结构是否合理并研究其改进的措施,必须确定用以判断系统运行优劣的基本数量指 119
-119- （ii）顾客到达的方式可能是一个—个的，也可能是成批的。 （iii）顾客到达可以是相互独立的，即以前的到达情况对以后的到达没有影响； 否则是相关的。 （iv）输入过程可以是平稳的，即相继到达的间隔时间分布及其数学期望、方差等 数字特征都与时间无关，否则是非平稳的。 1.2.2 排队规则 排队规则指到达排队系统的顾客按怎样的规则排队等待，可分为损失制，等待制和 混合制三种。 （i）损失制（消失制）。当顾客到达时，所有的服务台均被占用，顾客随即离去。 （ii）等待制。当顾客到达时，所有的服务台均被占用，顾客就排队等待，直到接 受完服务才离去。例如出故障的机器排队等待维修就是这种情况。 （iii）混合制。介于损失制和等待制之间的是混合制，即既有等待又有损失。有 队列长度有限和排队等待时间有限两种情况，在限度以内就排队等待，超过一定限度就 离去。 排队方式还分为单列、多列和循环队列。 1.2.3 服务过程 （i）服务机构。主要有以下几种类型：单服务台；多服务台并联（每个服务台同 时为不同顾客服务）；多服务台串联（多服务台依次为同一顾客服务）；混合型。 （ii）服务规则。按为顾客服务的次序采用以下几种规则： ①先到先服务，这是通常的情形。 ②后到先服务，如情报系统中，最后到的情报信息往往最有价值，因而常被优先处 理。 ③随机服务，服务台从等待的顾客中随机地取其一进行服务，而不管到达的先后。 ④优先服务，如医疗系统对病情严重的病人给予优先治疗。 1.3 排队模型的符号表示 排队模型用六个符号表示，在符号之间用斜线隔开，即 X /Y / Z / A/ B /C 。第一 个符号 X 表示顾客到达流或顾客到达间隔时间的分布；第二个符号Y 表示服务时间的 分布；第三个符号 Z 表示服务台数目；第四个符号 A 是系统容量限制；第五个符号 B 是 顾客源数目；第六个符号C 是服务规则，如先到先服务 FCFS，后到先服务 LCFS 等。并 约定，如略去后三项，即指 X /Y / Z / ∞ / ∞ / FCFS的情形。我们只讨论先到先服务 FCFS 的情形，所以略去第六项。 表示顾客到达间隔时间和服务时间的分布的约定符号为： M —指数分布（ M 是 Markov 的字头，因为指数分布具有无记忆性，即 Markov 性）； D —确定型（Deterministic）； Ek —k 阶爱尔朗(Erlang)分布； G —一般（general）服务时间的分布； GI —一般相互独立（General Independent）的时间间隔的分布。 例如， M / M /1表示相继到达间隔时间为指数分布、服务时间为指数分布、单服 务台、等待制系统。 D / M / c 表示确定的到达时间、服务时间为指数分布、 c 个平行 服务台（但顾客是一队）的模型。 1.4 排队系统的运行指标 为了研究排队系统运行的效率，估计其服务质量，确定系统的最优参数，评价系统 的结构是否合理并研究其改进的措施，必须确定用以判断系统运行优劣的基本数量指
标,这些数量指标通常是: (i)平均队长:指系统内顾客数(包括正被服务的顾客与排队等待服务的顾客)的 数学期望,记作L,。 (ii)平均排队长:指系统内等待服务的顾客数的数学期望,记作L。 (ii)平均逗留时间:顾客在系统内逗留时间(包括排队等待的时间和接受服务的 时间)的数学期望,记作W (iv)平均等待时间:指一个顾客在排队系统中排队等待时间的数学期望,记作 (v)平均忙期:指服务机构连续繁忙时间(顾客到达空闲服务机构起,到服务机 构再次空闲止的时间)长度的数学期望,记为T。 还有由于顾客被拒绝而使企业受到损失的损失率以及以后经常遇到的服务强度等 这些都是很重要的指标。 计算这些指标的基础是表达系统状态的概率。所谓系统的状态即指系统中顾客数 如果系统中有n个顾客就说系统的状态是n,它的可能值是 (i)队长没有限制时,n=0,1,2,…, (i)队长有限制,最大数为N时,n=0,1,…,N (i)损失制,服务台个数是c时,n=0,…,c 这些状态的概率一般是随时刻t而变化,所以在时刻t、系统状态为n的概率用 P(1)表示。稳态时系统状态为n的概率用P表示。 §2输入过程与服务时间的分布 排队系统中的事件流包括顾客到达流和服务时间流。由于顾客到达的间隔时间和服 务时间不可能是负值,因此,它的分布是非负随机变量的分布。最常用的分布有泊松分 布、确定型分布,指数分布和爱尔朗分布。 2.1泊松流与指数分布 设N(m)表示在时间区间[0,1)内到达的顾客数(t>0),令P(1,t2)表示在时间区 间[41,l2)(2>1)内有n(≥0)个顾客到达的概率,即 P(112)=P{N(2)-N(1)=n}(2>1,n≥0) 当P(112)合于下列三个条件时,我们说顾客的到达形成泊松流。这三个条件是 1°在不相重叠的时间区间内顾客到达数是相互独立的,我们称这性质为无后效 2°对充分小的△t,在时间区间[,+△n)内有一个顾客到达的概率与t无关,而 约与区间长Mt成正比,即 P(L,t+△)=A△+o(△) (1) 其中O(△t),当Mt→0时,是关于△的高阶无穷小。λ>0是常数,它表示单位时间 有一个顾客到达的概率,称为概率强度。 3°对于充分小的△,在时间区间[t,t+△)内有两个或两个以上顾客到达的概率 极小,以致可以忽略,即 ∑Pn(.t+△M)=0o(△)
-120- 标，这些数量指标通常是： (i)平均队长：指系统内顾客数（包括正被服务的顾客与排队等待服务的顾客）的 数学期望，记作 Ls 。 (ii)平均排队长:指系统内等待服务的顾客数的数学期望，记作 Lq 。 (iii)平均逗留时间：顾客在系统内逗留时间（包括排队等待的时间和接受服务的 时间）的数学期望，记作Ws 。 （iv）平均等待时间：指一个顾客在排队系统中排队等待时间的数学期望，记作 Wq 。 （v）平均忙期：指服务机构连续繁忙时间（顾客到达空闲服务机构起，到服务机 构再次空闲止的时间）长度的数学期望，记为Tb 。 还有由于顾客被拒绝而使企业受到损失的损失率以及以后经常遇到的服务强度等， 这些都是很重要的指标。 计算这些指标的基础是表达系统状态的概率。所谓系统的状态即指系统中顾客数， 如果系统中有n 个顾客就说系统的状态是n ，它的可能值是 （i）队长没有限制时，n = 0,1,2,L， （ii）队长有限制，最大数为 N 时， n = 0,1,L,N ， （iii）损失制，服务台个数是c 时，n = 0,1,L,c 。 这些状态的概率一般是随时刻 t 而变化，所以在时刻 t 、系统状态为 n 的概率用 P (t) n 表示。稳态时系统状态为n 的概率用 Pn 表示。 §2 输入过程与服务时间的分布 排队系统中的事件流包括顾客到达流和服务时间流。由于顾客到达的间隔时间和服 务时间不可能是负值，因此，它的分布是非负随机变量的分布。最常用的分布有泊松分 布、确定型分布，指数分布和爱尔朗分布。 2.1 泊松流与指数分布 设 N(t) 表示在时间区间[0,t) 内到达的顾客数（t > 0），令 ( , ) 1 2 P t t n 表示在时间区 间[ , )( ) 1 2 2 1 t t t > t 内有n(≥ 0) 个顾客到达的概率，即 ( , ) { ( ) ( ) } ( , 0) Pn t1 t2 = P N t2 − N t1 = n t2 > t1 n ≥ 当 ( , ) 1 2 P t t n 合于下列三个条件时，我们说顾客的到达形成泊松流。这三个条件是： 1 o 在不相重叠的时间区间内顾客到达数是相互独立的，我们称这性质为无后效 性。 2 o 对充分小的 Δt ，在时间区间[t,t + Δt)内有一个顾客到达的概率与t 无关，而 约与区间长 Δt 成正比，即 ( , ) ( ) 1P t t + Δt = λΔt + o Δt （1） 其中o(Δt) ，当 Δt → 0 时，是关于 Δt 的高阶无穷小。λ > 0 是常数，它表示单位时间 有一个顾客到达的概率，称为概率强度。 3 o 对于充分小的 Δt ，在时间区间[t,t + Δt)内有两个或两个以上顾客到达的概率 极小，以致可以忽略，即 ∑ ∞ = + Δ = Δ 2 ( , ) ( ) n n P t t t o t （2）
在上述条件下,我们研究顾客到达数n的概率分布。 由条件2°,我们总可以取时间由0算起,并简记P(0,D)=Pn() 由条件1°和2°,有 f(t+△)=P(D)(△ P(t+△)=∑P-(1)P(△),n 由条件2和3°得 P(△)=1-AAt+o(△) 因而有 (t+A)-f() 0(△) P(t+△)-P(D AP(0)+1Pn-(0) O(△) At 在以上两式中,取M趋于零的极限,当假设所涉及的函数可导时,得到以下微分方程 dP(n APo(t) dt An(1)+APBn1(1),n=1,2 取初值P(0)=1,P(0)=0(n=12,…),容易解出P(1)=e;再令 P()=Un()e,可以得到U(t)及其它Un()所满足的微分方程组,即 dU (0) aUn-(0), ()=1,Un(1)=0 由此容易解得 Pn() (lr) n= 正如在概率论中所学过的,我们说随机变量{N()=N(s+1)-N(s)}服从泊松分 布。它的数学期望和方差分别是 EIN(J= At: Var[N(J=at 当输入过程是泊松流时,那么顾客相继到达的时间间隔T必服从指数分布。这是 由于 P{T>l}=P{[0,1)内呼叫次数为零}=P(1)=e 那么,以F(1)表示T的分布函数,则有 t≥0 P{T≤l}=F(t) 而分布密度函数为 t>
-121- 在上述条件下，我们研究顾客到达数n 的概率分布。 由条件 2o ，我们总可以取时间由 0 算起，并简记 P (0,t) P (t) n = n 。 由条件 1o 和 2o ，有 ( ) ( ) ( ) 0 0 0 P t + Δt = P t P Δt ∑= + Δ = − Δ = n k Pn t t Pn k t Pk t n 0 ( ) ( ) ( ), 1,2,L 由条件 2o 和 3o 得 ( ) 1 ( ) 0 P Δt = − λΔt + o Δt 因而有 t o t P t t P t t P t Δ Δ = − + Δ + Δ − ( ) ( ) ( ) ( ) 0 0 0 λ ， t o t P t P t t P t t P t n n n n Δ Δ = − + + Δ + Δ − − ( ) ( ) ( ) ( ) ( ) λ λ 1 . 在以上两式中，取 Δt 趋于零的极限，当假设所涉及的函数可导时，得到以下微分方程 组： ( ) ( ) 0 0 P t dt dP t = −λ ， ( ) ( ), 1,2,L ( ) = − P t + P −1 t n = dt dP t n n n λ λ . 取初值 P0 (0) = 1 ， P (0) = 0(n = 1,2,L) n ，容易解出 t P t e−λ 0 ( ) = ；再令 t n n P t U t e−λ ( ) = ( ) ，可以得到 ( ) 0 U t 及其它U (t) n 所满足的微分方程组，即 ( ), 1,2, , ( ) = U −1 t n = L dt dU t n n λ U0 (t) =1，Un (t) = 0 . 由此容易解得 , 1,2,L ! ( ) ( ) = = − e n n t P t t n n λ λ . 正如在概率论中所学过的，我们说随机变量{N(t) = N(s + t) − N(s)}服从泊松分 布。它的数学期望和方差分别是 E[N(t)] = λt ； Var[N(t)] = λt 。 当输入过程是泊松流时，那么顾客相继到达的时间间隔T 必服从指数分布。这是 由于 P{T > t} = P{[0,t) 内呼叫次数为零 t P t e−λ } = 0 ( ) = 那么，以 F(t) 表示T 的分布函数，则有 ⎩ ⎨ ⎧ 0 − f t e t λt λ
对于泊松流,λ表示单位时间平均到达的顾客数,所以一就表示相继顾客到达平均 间隔时间,而这正和ET的意义相符。 对一顾客的服务时间也就是在忙期相继离开系统的两顾客的间隔时间,有时也服从 指数分布。这时设它的分布函数和密度函数分别是 G(t)=1-e",g()=e 我们得到 lim P(T≤t+△|T>=lm P{tl} 这表明,在任何小的时间间隔[t,t+△)内一个顾客被服务完了(离去)的概率是 △t+o(△)。表示单位时间能被服务完成的顾客数,称为平均服务率,而一表示 个顾客的平均服务时间 2.2常用的几种概率分布及其产生 2.2.1常用的连续型概率分布 我们只给出这些分布的参数、记号和通常的应用范围,更详细的内容参看专门的概 率论书籍 (i)均匀分布 区间(an,b)内的均匀分布记作U(a,b)。服从U(0,1)分布的随机变量又称为随机 数,它是产生其它随机变量的基础。如若X为U(0,1)分布,则Y=a+(b-a)X服从 (i)正态分布 以H为期望,a2为方差的正态分布记作N(,2)。正态分布的应用十分广泛 正态分布还可以作为二项分布一定条件下的近似。 iii)指数分布 指数分布是单参数A的非对称分布,记作EXp(A),概率密度函数为 (0)≈Jeb ≥0 0,tt+S|X>1)=P(X>s),在排队论、可靠性分析中有广泛应用。 (iv) Gamma分布 Gamma分布是双参数a,B的非对称分布,记作G(a,B),期望是aB。a=1时蜕 化为指数分布。n个相互独立、同分布(参数λ)的指数分布之和是 Gamma分布 (α=n,β=A)。 Gamma分布可用于服务时间,零件寿命等。 Gamma分布又称爱尔朗分布。 (v) Weibull分布 Weibull分布是双参数a,B的非对称分布,记作W(a,B)。a=1时蜕化为指数分 布。作为设备、零件的寿命分布在可靠性分析中有着非常广泛的应用 (vi)Beta分布
-122- 对于泊松流, λ 表示单位时间平均到达的顾客数,所以 λ 1 就表示相继顾客到达平均 间隔时间，而这正和 ET 的意义相符。 对一顾客的服务时间也就是在忙期相继离开系统的两顾客的间隔时间，有时也服从 指数分布。这时设它的分布函数和密度函数分别是 t G t e−μ ( ) = 1− ， t g t e μ μ − ( ) = 我们得到 = μ Δ > Δ → Δ → { } { } lim { | } lim 0 0 tP T t P t T t t t P T t t T t t t 这表明，在任何小的时间间隔 [t,t + Δt) 内一个顾客被服务完了（离去）的概率是 μΔt + o(Δt) 。 μ 表示单位时间能被服务完成的顾客数，称为平均服务率，而 μ 1 表示 一个顾客的平均服务时间。 2.2 常用的几种概率分布及其产生 2.2.1 常用的连续型概率分布 我们只给出这些分布的参数、记号和通常的应用范围，更详细的内容参看专门的概 率论书籍。 （i）均匀分布 区间 (a,b) 内的均匀分布记作U(a,b) 。服从U(0,1) 分布的随机变量又称为随机 数，它是产生其它随机变量的基础。如若 X 为U(0,1) 分布，则Y = a + (b − a)X 服从 U(a,b) 。 （ii）正态分布 以 μ 为期望， 2 σ 为方差的正态分布记作 ( , ) 2 N μ σ 。正态分布的应用十分广泛。 正态分布还可以作为二项分布一定条件下的近似。 （iii）指数分布 指数分布是单参数λ 的非对称分布，记作 Exp(λ)，概率密度函数为： ⎩ ⎨ ⎧ t + s | X > t) = P(X > s) ，在排队论、可靠性分析中有广泛应用。 （iv）Gamma 分布 Gamma 分布是双参数α,β 的非对称分布，记作G(α,β ) ，期望是αβ 。α = 1时蜕 化为指数分布。 n 个相互独立、同分布（参数 λ ）的指数分布之和是 Gamma 分布 （α = n, β = λ) 。Gamma 分布可用于服务时间，零件寿命等。 Gamma 分布又称爱尔朗分布。 （v）Weibull 分布 Weibull 分布是双参数α,β 的非对称分布，记作W(α, β ) 。α = 1时蜕化为指数分 布。作为设备、零件的寿命分布在可靠性分析中有着非常广泛的应用。 （vi）Beta 分布
Beta分布是区间(0,1)内的双参数、非均匀分布,记作B(a,B)。 2.2.2常用的离散型概率分布 (i)离散均匀分布 (ii) Bernoulli分布(两点分布) Bernoulli分布是x=10处取值的概率分别是p和1-p的两点分布,记作 Bern(p)。用于基本的离散模型 (ii)泊松( Poisson)分布 泊松分布与指数分布有密切的关系。当顾客平均到达率为常数A的到达间隔服从 指数分布时,单位时间内到达的顾客数K服从泊松分布,即单位时间内到达k位顾客 的概率为 e P k=0,1,2 k 记作 Poisson(λ)。泊松分布在排队服务、产品检验、生物与医学统计、天文、物理等 领域都有广泛应用。 (iv)二项分布 在独立进行的每次试验中,某事件发生的概率为P,则n次试验中该事件发生的 次数K服从二项分布,即发生k次的概率为 P (1-p),k=0,1 记作B(n,P)。二项分布是n个独立的 Bernoulli分布之和。它在产品检验、保险、生 物和医学统计等领域有着广泛的应用 当n,k很大时,B(n,p)近似于正态分布N(p,np(1-p);当n很大、P很小, 且Pp约为常数λ时,B(n,p)近似于 Poisson()。 §3生灭过程 一类非常重要且广泛存在的排队系统是生灭过程排队系统。生灭过程是一类特殊的 随机过程,在生物学、物理学、运筹学中有广泛的应用。在排队论中,如果N(1)表示 时刻t系统中的顾客数,则{N(1),t≥0}就构成了一个随机过程。如果用“生”表示顾 客的到达,“灭”表示顾客的离去,则对许多排队过程来说,{N(1),t≥0}就是一类特 殊的随机过程一生灭过程。下面结合排队论的术语给出生灭过程的定义 定义1设{N(1),t≥0}为一个随机过程。若N()的概率分布具有以下性质 (1)假设N(1)=n,则从时刻t起到下一个顾客到达时刻止的时间服从参数为n 的负指数分布,n=0,1,2,…。 (2)假设N(t)=n,则从时刻t起到下一个顾客离去时刻止的时间服从参数为n 的负指数分别,n=0,1,2,……。 (3)同一时刻只有一个顾客到达或离去。 则称{N(),t≥0}为一个生灭过程 一般来说,得到N()的分布Pn()=P{N(1)=n}(n=0,1,2,…)是比较困难的, 因此通常是求当系统到达平衡后的状态分布,记为pn,n=0.1,2, 为求平稳分布,考虑系统可能处的任一状态n。假设记录了一段时间内系统进入状 态n和离开状态n的次数,则因为“进入”和“离开”是交替发生的,所以这两个数要
-123- Beta 分布是区间(0,1) 内的双参数、非均匀分布，记作 B(α, β ) 。 2.2.2 常用的离散型概率分布 （i）离散均匀分布 （ii）Bernoulli 分布（两点分布） Bernoulli 分布是 x = 1,0 处取值的概率分别是 p 和1− p 的两点分布，记作 Bern( p) 。用于基本的离散模型。 （iii）泊松（Poisson）分布 泊松分布与指数分布有密切的关系。当顾客平均到达率为常数 λ 的到达间隔服从 指数分布时，单位时间内到达的顾客数 K 服从泊松分布，即单位时间内到达 k 位顾客 的概率为 , 0,1,2,L ! = = − k k e P k k λ λ 记作 Poisson(λ) 。泊松分布在排队服务、产品检验、生物与医学统计、天文、物理等 领域都有广泛应用。 （iv）二项分布 在独立进行的每次试验中，某事件发生的概率为 p ，则 n 次试验中该事件发生的 次数 K 服从二项分布，即发生k 次的概率为 P C p p k n k k n k k n = (1− ) , = 0,1,L, − . 记作 B(n, p) 。二项分布是n 个独立的 Bernoulli 分布之和。它在产品检验、保险、生 物和医学统计等领域有着广泛的应用。 当n,k 很大时， B(n, p) 近似于正态分布 N(np,np(1− p)) ；当n 很大、 p 很小， 且np 约为常数λ 时， B(n, p) 近似于 Poisson(λ)。 §3 生灭过程 一类非常重要且广泛存在的排队系统是生灭过程排队系统。生灭过程是一类特殊的 随机过程，在生物学、物理学、运筹学中有广泛的应用。在排队论中，如果 N(t) 表示 时刻t 系统中的顾客数，则{N(t),t ≥ 0}就构成了一个随机过程。如果用“生”表示顾 客的到达，“灭”表示顾客的离去，则对许多排队过程来说，{N(t),t ≥ 0}就是一类特 殊的随机过程－生灭过程。下面结合排队论的术语给出生灭过程的定义。 定义 1 设{N(t),t ≥ 0}为一个随机过程。若 N(t) 的概率分布具有以下性质： （1）假设 N(t) = n，则从时刻t 起到下一个顾客到达时刻止的时间服从参数为λn 的负指数分布，n = 0,1,2,L。 （2）假设 N(t) = n，则从时刻t 起到下一个顾客离去时刻止的时间服从参数为 μn 的负指数分别，n = 0,1,2,L。 （3）同一时刻只有一个顾客到达或离去。 则称{N(t),t ≥ 0}为一个生灭过程。 一般来说，得到 N(t) 的分布 p (t) P{N(t) n} n = = （ n = 0,1,2,L）是比较困难的， 因此通常是求当系统到达平衡后的状态分布，记为 pn , n = 0,1,2,L。 为求平稳分布，考虑系统可能处的任一状态 n 。假设记录了一段时间内系统进入状 态n 和离开状态 n 的次数，则因为“进入”和“离开”是交替发生的，所以这两个数要
么相等,要么相差为1。但就这两种事件的平均发生率来说,可以认为是相等的。即当 系统运行相当时间而到达平衡状态后,对任一状态n来说,单位时间内进入该状态的平 均次数和单位时间内离开该状态的平均次数应该相等,这就是系统在统计平衡下的“流 入=流出”原理。根据这一原理,可得到任一状态下的平衡方程如下: up,=Aopo 10P0+12P2=(41+1)P P1+H3P3=(2+2)P2 (3) An-P_+umpn1=(n,+uu)p 由上述平衡方程,可求得 P1==P0 p3 (A1P1-100)=一P1 122 12121 P3=n2+(2P2-小 12x120 p2 Po 133421 P u,P p-d) Pn Po Ans ,n=1,2, (4) Hn4n-1…1 则平稳状态的分布为 P=CaPo, n=1, 2 (5) 由概率分布的要求 Pn 有 1+∑Cn|P=1 于是 Po (6) 注意:(6)只有当级数∑C收敛时才有意义,即当∑Cn<∞时,才能由上
-124- 么相等，要么相差为 1。但就这两种事件的平均发生率来说，可以认为是相等的。即当 系统运行相当时间而到达平衡状态后，对任一状态 n 来说，单位时间内进入该状态的平 均次数和单位时间内离开该状态的平均次数应该相等，这就是系统在统计平衡下的“流 入＝流出”原理。根据这一原理，可得到任一状态下的平衡方程如下： M M M M n pn n pn n n pn p p p p p p p p n ( ) ( ) ( ) 2 1 0 1 1 1 1 1 1 3 3 2 2 2 0 0 2 2 1 1 1 1 1 0 0 λ μ λ μ λ μ λ μ λ μ λ μ μ λ + = + + = + + = + = − − + + （3） 由上述平衡方程，可求得 0： 0 1 0 1 p p μ λ= 1： 0 2 1 1 0 1 2 1 1 1 0 0 2 1 2 1 2 ( ) 1 p p p p p p μ μ λ λ μ λ μ λ μ μ λ = + − = = 2： 0 3 2 1 2 1 0 2 3 2 2 2 1 1 3 2 3 2 3 ( ) 1 p p p p p p μ μ μ λ λ λ μ λ μ λ μ μ λ= + − = = M M n ： 0 1 1 1 0 1 1 1 1 1 1 ( ) 1 p p p p p p n n n n n n n n n n n n n n n n μ μ μ λ λ λ μ λ μ λ μ μ λ L L + − + − − + + + = + − = = M M 记 1 1 1 2 0 μ μ μ λ λ λ L L − − − = n n n n Cn ， n =1,2,L （4） 则平稳状态的分布为 pn = Cn p0 ， n = 1,2,L （5） 由概率分布的要求 1 0 ∑ = ∞ n= pn 有 1 0 1 1 = ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ +∑ ∞ = C p n n 于是 ∑ ∞ = + = 1 0 1 1 n Cn p （6） 注意：（6）只有当级数∑∞ n=1 Cn 收敛时才有意义，即当∑ < ∞ ∞ n=1 Cn 时，才能由上
述公式得到平稳状态的概率分布。 §4M/M/s等待制排队模型 4.1单服务台模型 单服务台等待制模型M/M//∞是指:顾客的相继到达时间服从参数为A的负指 数分布,服务台个数为1,服务时间V服从参数为的负指数分布,系统空间无限, 允许无限排队,这是一类最简单的排队系统。 4.1.1队长的分布 记Pn=P{N=n}(n=01,2…)为系统达到平衡状态后队长N的概率分布,则 由式(4)~(6),并注意到An=A,n=0,2,…和n=1,n=0,1,2,…。记 并设p<1(否则队列将排至无限远),则 P,=p"po, n=1,2 其中 Po P (7) 因此 Pn=(1-p)p”,n=1,2 公式(7)和(8)给出了在平衡条件下系统中顾客数为n的概率。由式(7)不难看出, P是系统中至少有一个顾客的概率,也就是服务台处于忙的状态的概率,因而也称P为 服务强度,它反映了系统繁忙的程度。此外,(8)式只有在p=-<1的条件下才能得 到,即要求顾客的平均到达率小于系统的平均服务率,才能使系统达到统计平衡 4.1.2几个主要数量指标 对单服务台等待制排队系统,由已得到的平稳状态下队长的分布,可以得到平均队 长 n(1-p) =(p+2p2+3p3+…)-(p2+2p3+3p4+…) (9) =p+p+p+……= 平均排队长L为
-125- 述公式得到平稳状态的概率分布。 §4 M / M /s 等待制排队模型 4.1 单服务台模型 单服务台等待制模型 M / M /1/ ∞ 是指：顾客的相继到达时间服从参数为λ 的负指 数分布，服务台个数为 1，服务时间V 服从参数为 μ 的负指数分布，系统空间无限， 允许无限排队，这是一类最简单的排队系统。 4.1.1 队长的分布 记 p P{N n} n = = （ n = 0,1,2,L）为系统达到平衡状态后队长 N 的概率分布，则 由式（4）～（6），并注意到λn = λ, n = 0,1,2,L和 μn = μ, n = 0,1,2,L。记 μ λ ρ = 并设 ρ < 1（否则队列将排至无限远），则 n Cn ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ = μ λ ， n =1,2,L 故 p p0 n n = ρ ， n = 1,2,L 其中 ρ ρ ρ ρ = − ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ − ⎟ = ⎠ ⎞ ⎜ ⎝ ⎛ = + = − − ∞ = ∞ = ∑ ∑ 1 1 1 1 1 1 1 0 1 0 n n n n p （7） 因此 n pn = (1− ρ)ρ ， n =1,2,L （8） 公式（7）和（8）给出了在平衡条件下系统中顾客数为 n 的概率。由式（7）不难看出， ρ 是系统中至少有一个顾客的概率，也就是服务台处于忙的状态的概率，因而也称 ρ 为 服务强度，它反映了系统繁忙的程度。此外，（8）式只有在 = < 1 μ λ ρ 的条件下才能得 到，即要求顾客的平均到达率小于系统的平均服务率，才能使系统达到统计平衡。 4.1.2 几个主要数量指标 对单服务台等待制排队系统，由已得到的平稳状态下队长的分布，可以得到平均队 长 μ λ λ ρ ρ ρ ρ ρ ρ ρ ρ ρ ρ ρ ρ ρ − = − = + + + = = + + + − + + + = ∑ = ∑ − ∞ = ∞ = 1 ( 2 3 ) ( 2 3 ) (1 ) 2 3 2 3 2 3 4 0 1 L L L n n n s n L np n （9） 平均排队长 Lq 为
L=∑(m-1)pn=L-(1-P)=L 1( 关于顾客在系统中的逗留时间T,可说明它服从参数为-的复指数分布,即 P{T>l}=e-,t≥0 因此,平均逗留时间 因为,顾客在系统中的逗留时间为等待时间T和接受服务时间V之和,即 7+1 故由 W,=E(7)=E(T)+E(1)=W+ (12) 可得平均等待时间W为 Wa=ws 4(-1) 从式(9)和式(11),可发现平均队长L,与平均逗留时间W,具有关系 L=aw (14) 同样,从式(10)和式(13),可发现平均排队长L与平均等待时间W具有关系 L =an (15) 式(14)和式(15)通常称为 Little公式,是排队论中一个非常重要的公式 4.1.3忙期和闲期 在平衡状态下,忙期B和闲期Ⅰ一般均为随机变量,求它们的分布是比较麻烦的。 因此,我们来求一下平均忙期B和平均闲期I。由于忙期和闲期出现的概率分别为P和 1-p,所以在一段时间内可以认为忙期和闲期的总长度之比为p:(1-p)。又因为忙 期和闲期是交替出现的,所以在充分长的时间里,它们出现的平均次数应是相同的。于 是,忙期的平均长度B和闲期的平均长度I之比也应是p:(1-p),即 B (16) 又因为在到达为 Poisson流时,根据负指数分布的无记忆性和到达与服务相互独立的假 设,容易证明从系统空闲时刻起到下一个顾客到达时刻止(即闲期)的时间间隔仍服从 参数为A的负指数分布,且与到达时间间隔相互独立。因此,平均闲期应为一,这样, 便求得平均忙期为 B (17) 1-p2-2 与式(11)比较,发现平均逗留时间(W,)=平均忙期(B)。这一结果直观看上去 是显然的,顾客在系统中逗留的时间越长,服务员连续繁忙的时间也就越长。因此
-126- ( ) ( 1) (1 ) 2 0 1 μ μ λ λ ρ − = ∑ − = − − = − = ∞ = L n p L p L n q n （10） 关于顾客在系统中的逗留时间T ，可说明它服从参数为 μ − λ 的复指数分布，即 t P T t e ( ) { } − μ−λ > = ，t ≥ 0 因此，平均逗留时间 μ − λ = 1 Ws （11） 因为，顾客在系统中的逗留时间为等待时间Tq 和接受服务时间V 之和，即 T = Tq +V 故由 μ 1 Ws = E(T) = E(Tq ) + E(V ) = Wq + （12） 可得平均等待时间Wq 为 ( ) 1 μ μ λ λ μ − Wq =Ws − = （13） 从式（9）和式（11），可发现平均队长 Ls 与平均逗留时间Ws 具有关系 Ls = λWs （14） 同样，从式（10）和式（13），可发现平均排队长 Lq 与平均等待时间Wq 具有关系 Lq = λWq （15） 式（14）和式（15）通常称为 Little 公式，是排队论中一个非常重要的公式。 4.1.3 忙期和闲期 在平衡状态下，忙期 B 和闲期 I 一般均为随机变量，求它们的分布是比较麻烦的。 因此，我们来求一下平均忙期 B 和平均闲期 I 。由于忙期和闲期出现的概率分别为 ρ 和 1− ρ ，所以在一段时间内可以认为忙期和闲期的总长度之比为 ρ :(1− ρ) 。又因为忙 期和闲期是交替出现的，所以在充分长的时间里，它们出现的平均次数应是相同的。于 是，忙期的平均长度 B 和闲期的平均长度 I 之比也应是 ρ :(1− ρ)，即 ρ ρ − = I 1 B （16） 又因为在到达为 Poisson 流时，根据负指数分布的无记忆性和到达与服务相互独立的假 设，容易证明从系统空闲时刻起到下一个顾客到达时刻止（即闲期）的时间间隔仍服从 参数为λ 的负指数分布，且与到达时间间隔相互独立。因此，平均闲期应为 λ 1 ，这样， 便求得平均忙期为 ρ λ μ λ ρ − ⋅ = − = 1 1 1 B （17） 与式（11）比较，发现平均逗留时间（Ws ）＝平均忙期（ B ）。这一结果直观看上去 是显然的，顾客在系统中逗留的时间越长，服务员连续繁忙的时间也就越长。因此，一
个顾客在系统内的平均逗留时间应等于服务员平均连续忙的时间 4.2与排队论模型有关的 LINGO函数 (1)@peb(load, S) 该函数的返回值是当到达负荷为1oad,服务系统中有S个服务台且允许排队时系 统繁忙的概率,也就是顾客等待的概率。 (2)Opel(load, S) 该函数的返回值是当到达负荷为load,服务系统中有S个服务台且不允许排队时 系统损失概率,也就是顾客得不到服务离开的概率 (3)Opfs(load, S, K) 该函数的返回值是当到达负荷为load,顾客数为K,平行服务台数量为S时,有限 源的 Poisson服务系统等待或返修顾客数的期望值 例1某修理店只有一个修理工,来修理的顾客到达过程为 Poisson流,平均4人 /h;修理时间服从负指数分布,平均需要6min。试求:(1)修理店空闲的概率;(2) 店内恰有3个顾客的概率;(3)店内至少有1个顾客的概率;(4)在店内的平均顾客数 (5)每位顾客在店内的平均逗留时间;(6)等待服务的平均顾客数;(7)每位顾客平 均等待服务时间;(8)顾客在店内等待时间超过10min的概率。 解本例可看成一个M/M/1/∞排队问题,其中 (1)修理店空闲的概率 P (2)店内恰有3个顾客的概率 P3=p3(1-p)=04×(1-04)=0.38 (3)店内至少有1个顾客的概率 P{N≥l=1-p0=p=04 (4)在店内的平均顾客数 L 0.67(人) (5)每位顾客在店内的平均逗留时间 W L,0.67 (h)=10( (6)等待服务的平均顾客数 L=L-o- p 0.4 0.267(人) 1-p1-0.4 (7)每位顾客平均等待服务时间 L0.267 求-(b)=4min) (8)顾客在店内逗留时间超过10min的概率 P{T>10}=e6is'=e-=03679 编写 LINGO程序如下: model
-127- 个顾客在系统内的平均逗留时间应等于服务员平均连续忙的时间。 4.2 与排队论模型有关的 LINGO 函数 （1）@peb(load,S) 该函数的返回值是当到达负荷为 load，服务系统中有 S 个服务台且允许排队时系 统繁忙的概率，也就是顾客等待的概率。 （2）@pel（load,S） 该函数的返回值是当到达负荷为 load，服务系统中有 S 个服务台且不允许排队时 系统损失概率，也就是顾客得不到服务离开的概率。 （3）@pfs(load,S,K) 该函数的返回值是当到达负荷为 load，顾客数为 K，平行服务台数量为 S 时，有限 源的 Poisson 服务系统等待或返修顾客数的期望值。 例 1 某修理店只有一个修理工，来修理的顾客到达过程为 Poisson 流，平均 4 人 /h；修理时间服从负指数分布，平均需要 6min。试求：（1）修理店空闲的概率；（2） 店内恰有 3 个顾客的概率；（3）店内至少有 1 个顾客的概率；（4）在店内的平均顾客数； （5）每位顾客在店内的平均逗留时间；（6）等待服务的平均顾客数；（7）每位顾客平 均等待服务时间；（8）顾客在店内等待时间超过 10min 的概率。 解 本例可看成一个 M / M /1/ ∞ 排队问题，其中 λ = 4， 10 0.1 1 μ = = ， = = 0.4 μ λ ρ （1）修理店空闲的概率 p0 = 1− ρ = 1− 0.4 = 0.6 （2）店内恰有 3 个顾客的概率 (1 ) 0.4 (1 0.4) 0.38 3 3 p3 = ρ − ρ = × − = （3）店内至少有 1 个顾客的概率 P{N ≥1} = 1− p0 = ρ = 0.4 （4）在店内的平均顾客数 0.67 1 = − = ρ ρ Ls （人） （5）每位顾客在店内的平均逗留时间 (h) 10(min) 4 0.67 = = = λ s s L W （6）等待服务的平均顾客数 0.267 1 0.4 0.4 1 2 2 = − = − = − = ρ ρ Lq Ls ρ （人） （7）每位顾客平均等待服务时间 (h) 4(min) 4 0.267 = = = λ q q L W （8）顾客在店内逗留时间超过 10min 的概率 { 10} 0.3679 1 ) 15 1 6 1 10( > = = = − − − P T e e 编写 LINGO 程序如下： model: