1、1 第一节 第二节 第三节2大纲要求：掌握排队论的基本概念、常见的到达时间间隔分布和服务时间分布特性，生灭过程及稳态概率。单服务台负指数分布排队模型；多服务台负指数排队模型；排队系统设计的最优化重点：掌握M/M/1模型及其应用难点：到达流的稳态概率和系统状态转移概率及其优化服务设计自学：M/G/1模型3 排队论（排队论（Queueing Theory)，也称随机服务系统，也称随机服务系统理论，是运筹学的一个重要分支之一。理论，是运筹学的一个重要分支之一。1909年，丹麦哥本哈根电子公司电话工程师年，丹麦哥本哈根电子公司电话工程师A.K.Erlang的开创性论文的开创性论文“概率论和电话通讯理论
2、概率论和电话通讯理论”标志标志此理论的诞生。排队论的发展最早是与电话，通信此理论的诞生。排队论的发展最早是与电话，通信中的问题相联系的，这些问题到现在仍是排队论传中的问题相联系的，这些问题到现在仍是排队论传统的应用领域。统的应用领域。近年来在计算机通讯、网络系统近年来在计算机通讯、网络系统、交通运输、医、交通运输、医疗卫生系统、库存管理、作战指挥等各领域中均得疗卫生系统、库存管理、作战指挥等各领域中均得到了广泛的应用。到了广泛的应用。各种排队问题：各种排队问题：4到达的顾客要求的服务服务机构 机械坏了 修理 修理工人 修理工人 领取配件 管理员 病人 就诊 医生 打电话 通话 交换台 文件 打
3、印 打印机 飞机降落 降落 跑道指挥机构 顾客 就餐 服务员 汽车 路口 红绿灯5 首先看一下一般排队系统的组成示意图，不难首先看一下一般排队系统的组成示意图，不难发现排队系统一般有三个基本组成部分：发现排队系统一般有三个基本组成部分：1.1.输入过输入过程；程；2.2.排队规则；排队规则；3.3.服务机构。现分别说明：服务机构。现分别说明：排队结构服务机构顾客源顾客到达排队规则服务规则离去图1 排 队系统示意图6 输入即为顾客的到达，可有下列情况：输入即为顾客的到达，可有下列情况：1）顾客源可能是有限的，也可能是无限的。顾客源可能是有限的，也可能是无限的。2）顾客是成批到达或是单个到达。顾客
4、是成批到达或是单个到达。3）顾客到达的间隔时间可能是随机的或确定的。顾客到达的间隔时间可能是随机的或确定的。4）顾客到达可能是相互独立的或关联的。所谓顾客到达可能是相互独立的或关联的。所谓独立就是以前顾客的到达对以后顾客的到达无影响。独立就是以前顾客的到达对以后顾客的到达无影响。5）输入过程可以是输入过程可以是平稳的平稳的（stationarystationary），也），也可以是可以是非平稳的非平稳的。输入过程是平稳的是指顾客相继。输入过程是平稳的是指顾客相继到达的间隔时间分布和参数（均值、方差）与时间到达的间隔时间分布和参数（均值、方差）与时间无关；非平稳的则是与时间相关，非平稳的处理比无
5、关；非平稳的则是与时间相关，非平稳的处理比较困难。较困难。7 1）顾客到达后接受服务，服务分为顾客到达后接受服务，服务分为即时制即时制（损失制）和（损失制）和等待制等待制。即时制不允许排队，不形。即时制不允许排队，不形成队列；而对于等待制将会形成队列，顾客可以成队列；而对于等待制将会形成队列，顾客可以按下规则接收服务：按下规则接收服务：(1)(1)先到先服务先到先服务 FCFS;(2)FCFS;(2)后到先服务后到先服务 LCFS LCFS(3)(3)随机服务随机服务RAND;RAND;（4 4）有优先权服务）有优先权服务 PSPS。2）从队列的空间可分为有容量限制和无容量从队列的空间可分为有
6、容量限制和无容量限制。也可分为有形的和抽象的。限制。也可分为有形的和抽象的。3 3）从队列数可分为单列和多列。（多列时包）从队列数可分为单列和多列。（多列时包括各列间可以相互转移、括各列间可以相互转移、不能相互转移不能相互转移；中途可；中途可退出、退出、中途不能退出中途不能退出等。）等。）8 1 1）服务机构分为单服务台和多服务台。不同）服务机构分为单服务台和多服务台。不同的输入形式与排队规则和服务机构联合后形成不的输入形式与排队规则和服务机构联合后形成不同的排队服务机构，如：同的排队服务机构，如：112n.12n。单队单服务台多队多服务台（并列)单队多服务台（并列）12n.12312单队多服
7、务台（串列）混合形式9 2)2)服务方式分为单个顾客服务和成批顾客服务。服务方式分为单个顾客服务和成批顾客服务。3)3)服务时间分为确定型服务时间分为确定型(定常时间）和随机型。定常时间）和随机型。4)4)服务时间的分布在这里我们假定是平稳的。服务时间的分布在这里我们假定是平稳的。我们研究的问题是：输入是服从某种分布，我们研究的问题是：输入是服从某种分布，顾客的到达是相互独立到达的平稳过程；各列顾客的到达是相互独立到达的平稳过程；各列间不能相互转移、中途不能退出；单个单个地间不能相互转移、中途不能退出；单个单个地服务方式，服务服从某种分布，服务方式，服务服从某种分布，FCFSFCFS。10最主
8、要的、影响最大的是：最主要的、影响最大的是：顾客相继到达的间隔时间分布顾客相继到达的间隔时间分布服务时间的分布服务时间的分布服务台数服务台数D.G.KendallD.G.Kendall，19531953提出了分类法，称为提出了分类法，称为KendallKendall记记号号(适用于并列服务台适用于并列服务台),1971),1971又扩展成为：又扩展成为：X/Y/Z/A/B/CX/Y/Z/A/B/C11 式中：式中：X 或或Y 表示顾客相继到达时间间隔分布和服表示顾客相继到达时间间隔分布和服务时间分布的各种分布符号：务时间分布的各种分布符号：M负指数分布（负指数分布具有无记忆性，即Markov性
9、）；D确定型（Deterministic）分布；EkK阶爱尔朗分布Erlang；G I 一 般 相 互 独 立 随 机 分 布(G e n e r a l Independent)；G 一般随机分布。12Z填写并列的服务台数填写并列的服务台数A排队系统的最大容量排队系统的最大容量NB顾客源数量顾客源数量m C排队规则（排队规则（FCFS、LCFS等。本章仅研究等。本章仅研究FCFS的排队规则）的排队规则）如如 即为顾客到达时间间隔即为顾客到达时间间隔为负指数分布，服务时间为负指数分布，单台，为负指数分布，服务时间为负指数分布，单台，无限容量，无限源，先到先服务的排队系统模型。无限容量，无限源，
10、先到先服务的排队系统模型。13 1.1.排队系统的统计推断排队系统的统计推断:即通过对排队系统主即通过对排队系统主要参数的统计推断和对排队系统的结构分析，判要参数的统计推断和对排队系统的结构分析，判断一个给定的排队系统符合于哪种模型，以便根断一个给定的排队系统符合于哪种模型，以便根据排队理论进行研究。据排队理论进行研究。2.2.系统性态问题系统性态问题:即研究各种排队系统的概率即研究各种排队系统的概率规律性，主要研究队长分布、等待时间分布和忙规律性，主要研究队长分布、等待时间分布和忙期分布等统计指标期分布等统计指标,包括了瞬态和稳态两种情形。包括了瞬态和稳态两种情形。3.3.最优化问题：即包括
11、最优设计最优化问题：即包括最优设计(静态优化静态优化)，最优运营（动态优化）。最优运营（动态优化）。14 统计推断 最优设计 性态问题 排队系统研究问题阶段示意图排队系统研究问题阶段示意图15 求解一般排队系统问题的目的主要是通过研究排求解一般排队系统问题的目的主要是通过研究排队系统运行的队系统运行的效率指标，估计服务质量，确定系统效率指标，估计服务质量，确定系统的合理结构和系统参数的合理值的合理结构和系统参数的合理值，以便实现对现有，以便实现对现有系统合理改进和对新建系统的最优设计等。系统合理改进和对新建系统的最优设计等。认识系统：系统分析；改造系统：设计系统。认识系统：系统分析；改造系统：
12、设计系统。排队问题的求解：排队问题的求解：1 1、确定或拟合排队系统顾客到达时间间隔的时间、确定或拟合排队系统顾客到达时间间隔的时间分布和服务时间分布分布和服务时间分布(可实测可实测)。16 2 2、根据排队系统对应的理论模型求出用以、根据排队系统对应的理论模型求出用以判断系统运行优劣的基本数量指标的概率分布或判断系统运行优劣的基本数量指标的概率分布或特征数。特征数。数量指标主要包括数量指标主要包括:(1)(1)队长：队长：系统中的顾客数，它的数学期望记为系统中的顾客数，它的数学期望记为L Ls s 。队列长：队列长：系统中排队等待服务的顾客数，它系统中排队等待服务的顾客数，它的数学期望记为的
13、数学期望记为L Lq q 。系统中顾客数系统中顾客数L Ls s=系统中排队等待服务的顾系统中排队等待服务的顾客数客数L Lq q+正被服务的顾客数正被服务的顾客数(2)(2)逗留时间：逗留时间：指一个顾客在系统中的停留时间，指一个顾客在系统中的停留时间，它的数学期望记为它的数学期望记为WsWs。17 等待时间：等待时间：指一个顾客在系统中排队等待的指一个顾客在系统中排队等待的时间，它的数学期望记为时间，它的数学期望记为Wq Wq。逗留时间逗留时间=等待时间等待时间+服务时间服务时间(3)(3)忙期：忙期：指从顾客到达空闲服务机构起到服务指从顾客到达空闲服务机构起到服务机构再次为空闲这段时间长
14、度。（忙期和一个忙机构再次为空闲这段时间长度。（忙期和一个忙期中平均完成服务顾客数都是衡量服务机构效率期中平均完成服务顾客数都是衡量服务机构效率的指标，忙期关系到工作强度）的指标，忙期关系到工作强度）为了计算上述的数量指标，必须首先计算系为了计算上述的数量指标，必须首先计算系统状态的概率统状态的概率 系统状态系统状态：系统状态是指系统中顾客数。：系统状态是指系统中顾客数。18 状态概率状态概率：用：用P Pn n(t)(t)表示表示,即在即在t t时刻系统中有时刻系统中有n n个个顾客的概率，也称瞬态概率。它是表述系统的各种顾客的概率，也称瞬态概率。它是表述系统的各种性能指标的基础。性能指标的
15、基础。状态的可能值：状态的可能值：队长没有限制时：队长没有限制时：n=0，1，2，队长有限制时：队长有限制时：n=0，1，2，3，N 即时制：服务台个数是即时制：服务台个数是c时，时，n=0，1，c 求解状态概率求解状态概率P Pn n(t)(t)方法：是建立含方法：是建立含P Pn n(t)(t)的微的微分差分方程，通过求解微分差分方程得到系统瞬分差分方程，通过求解微分差分方程得到系统瞬态解，由于瞬态解一般求出确定值比较困难，即态解，由于瞬态解一般求出确定值比较困难，即便求得一般也很难使用。因此我们常常使用它的便求得一般也很难使用。因此我们常常使用它的极限极限(如果存在的话如果存在的话)：1
16、9nttnp)(plim 稳态的物理意义见右图，稳态的物理意义见右图，系统的稳态一般很快都系统的稳态一般很快都能达到，但实际中达不能达到，但实际中达不到稳态的现象也存在。到稳态的现象也存在。值得注意的是求稳态概值得注意的是求稳态概率率P Pn n并不一定求并不一定求t的的极限极限,而只需求而只需求P Pn n(t)=0(t)=0 即可。即可。过渡状态 稳定状态 pn t 图3 排队系统状态变化示意图 称为稳态称为稳态(steady state)(steady state)解，或称统计平衡状态解，或称统计平衡状态 (Statistical Equilibrium State)(Statistic
17、al Equilibrium State)的解。的解。20 排队系统的组成与特征排队系统的组成与特征 排队系统的模型分类排队系统的模型分类 顾客到达间隔时间和服务时间的经验分布与顾客到达间隔时间和服务时间的经验分布与理论分布理论分布 稳态概率稳态概率P Pn n的计算的计算 标准的标准的M/M/1M/M/1模型模型(M/M/1/FCFS)/FCFS)系统容量有限制的系统容量有限制的模型模型M/M/1/N/FCFS/FCFS 顾客源有限模型顾客源有限模型M/M/1/M/M/FCFSFCFS 标准的标准的M/M/CM/M/C模型模型M/M/C/FCFS/FCFS21 M/M/C型系统和型系统和C个
18、个M/M/1型系统型系统 系统容量有限制的多服务台模型系统容量有限制的多服务台模型(M/M/C/N/)顾客源为有限的顾客源为有限的多服务台模型多服务台模型(M/M/C/M)(M/M/C/M)一般服务时间的（一般服务时间的（M/G/1M/G/1）模型）模型 Pollaczek-Khintchine(P-K)公式公式定长服务时间定长服务时间 M/D/1M/D/1模型模型 爱尔朗服务时间爱尔朗服务时间M/Ek/1模型模型 排队系统优化排队系统优化 M/M/1 模型中的最优服务率模型中的最优服务率 标准的标准的M/M/1 Model 系统容量为系统容量为N的情形的情形 M/M/C模型中最优服务台数模型
19、中最优服务台数C22 要解决排队问题，首先要确定排队系统要解决排队问题，首先要确定排队系统的到达间隔时间分布与服务时间分布。的到达间隔时间分布与服务时间分布。要研究到达间隔时间分布与服务时间分要研究到达间隔时间分布与服务时间分布需要首先根据现有系统原始资料统计布需要首先根据现有系统原始资料统计出它们的经验分布（见出它们的经验分布（见P315P315319319），然），然后与理论分布拟合，若能对应，我们就后与理论分布拟合，若能对应，我们就可以得出上述的分布情况。可以得出上述的分布情况。23 经验分布是对排队系统的某些时间参数根据经验分布是对排队系统的某些时间参数根据经验数据进行的统计分析，并依
20、据统计分析结果经验数据进行的统计分析，并依据统计分析结果假设其统计样本的总体分布，选择合适的检验方假设其统计样本的总体分布，选择合适的检验方法进行检验，当通过检验时，我们认为时间参数法进行检验，当通过检验时，我们认为时间参数的经验数据服从该假设分布。的经验数据服从该假设分布。分布的拟合检验一般采用分布的拟合检验一般采用2检验。具体参见有检验。具体参见有关的概率统计教材内容。关的概率统计教材内容。24随机变量：数随机变量：数 随着实验的结果的不同而变化随着实验的结果的不同而变化 离散型：离散型：的所有可能只有限或至多可列个的所有可能只有限或至多可列个 连续型：连续型：（）取值于某个区间（）取值于
21、某个区间（a a，b b）分布函数（连续）分布函数（连续）:xpxF aFbFbap 的概率分布的概率分布(离散):iixpxp i=1,2,311iixp25 数学期望数学期望:(离散)E()=1iiipxdxxxf (连续)E()=方差方差:2EED EE22=BApBpABp 条件概率条件概率:密度函数密度函数:(连续)dttfxFx 0 xf 1dttf,26式中式中为常数为常数(0)0)，称，称X X服从参数为服从参数为的泊松分布。的泊松分布。若在上式中引入时间参数若在上式中引入时间参数t t，即令，即令tt代替代替，则有：，则有：在概率论中，我们曾学过泊松分布，设随机变在概率论中，
22、我们曾学过泊松分布，设随机变量为量为X，则有：，则有：!nenxPn n=0,1,2,（1）tnnenttP!)(t0，n=0,1,2,（2）27 (2)(2)式所表示的是与时间有关的随机变量的概率，式所表示的是与时间有关的随机变量的概率，这已不是简单的概率论的知识了，而是一个随机过这已不是简单的概率论的知识了，而是一个随机过程，即泊松过程。程，即泊松过程。下面我们在一定的假设条件下，推出顾客的到达下面我们在一定的假设条件下，推出顾客的到达过程就是一个泊松过程。过程就是一个泊松过程。若设若设N(t)N(t)表示在时间区间表示在时间区间0,t)0,t)内到达的顾客数内到达的顾客数(t0)(t0)
23、，P Pn n(t(t1 1,t,t2 2)表示在时间区间表示在时间区间tt1 1,t,t2 2)(t)(t2 2tt1 1)内内有有n(0)n(0)个顾客到达的概率。即：个顾客到达的概率。即：)()(,1221ntNtNPttPn（t2t1，n0）28 无后效性（独立性）：无后效性（独立性）：各区间内的顾客到达数相各区间内的顾客到达数相互独立，即互独立，即MarkovMarkov性。性。.t0 t1 t2 tn-1 tn 平稳性：平稳性：即对于足够小的即对于足够小的tt，在时间区间，在时间区间tt，t+t+t)t)内内有有1 1个顾客到达的概率为个顾客到达的概率为)()(1tttttP，当当
24、P Pn n(t(t1 1,t,t2 2)符合于下述三个条件时，我们说顾客到符合于下述三个条件时，我们说顾客到达过程就是泊松过程或者说顾客到达形成普阿松流。达过程就是泊松过程或者说顾客到达形成普阿松流。普阿松流的三个特性：普阿松流的三个特性：设表示单位时间内有 一个顾客到达的概率29 普通性：普通性：对充分小的对充分小的t,t,在时间区间在时间区间 t,t+tt）内有内有2 2个或个或2 2个以上顾客到达的概率是个以上顾客到达的概率是tt一高阶无穷一高阶无穷小小.)(1),(0tottttP 令令t1 1=0,t=0,t2 2=t,=t,则则P Pn n(t(t1 1,t,t2 2)=P)=P
25、n n(0,t)=P(0,t)=Pn n(t)(t)也就是在也就是在t,t+tt,t+t内有一个顾客到达的概率与内有一个顾客到达的概率与t t无关无关,而与而与tt成正比。成正比。0 0 是常数，是常数，称为概率强度称为概率强度2)(),(nntotttP 即即 由此知，在由此知，在(t，t+t)t)区间内没有顾客到达的概率为区间内没有顾客到达的概率为:ttttttptttpii)(1),(1),(10 区间长度为t时有 n个顾客的概率30 为了求为了求Pn(t)，即，即Pn(0,t)，需要研究它在时刻，需要研究它在时刻t到到t+tt时刻的改变量，也就是要建立时刻的改变量，也就是要建立P Pn
26、 n(t)(t)的微分方程。的微分方程。对于区间对于区间00，t+t)+t)可以分成可以分成00，t)t)和和tt，t+t)t+t)，其到达总数是，其到达总数是n n，不外有下列三种情况：所，不外有下列三种情况：所以有：以有：310，t)t,t+t0,t+t 区间情形个数概率个数概率概率A n pn(t)0 1-t+pn(t)(1-t+(t)(t)B n-1 pn-1(t)1t pn-1(t)t(t)(t)n-2 Pn-2(t)2 C n-3 Pn-3(t)3 0 P0(t)n32 令令t0t0取极限（并注意初始条件）得：取极限（并注意初始条件）得：当当n=0时，没有时，没有B，C两种情况，则
27、：两种情况，则：1)0(0P)()(00tPdttdP(4)(4)()()1)()(1tttPttPttPnnn)()()()()(1tttPttPtPttPnnnntttPtPttPttPnnnn)()()()()(1)()()(1tPtPdttdPnnn n0 (3)(3)(0)0nP33 代初始条件代初始条件(t=0)(t=0)有：有：CCt01n C=0 C=0ttP)(n0（3 3）式两端乘）式两端乘 e et t 并移项得：并移项得：tetP)(0 (5)（没有顾客到达的概率）dttPtdP)()(00 由上式得：由上式得：CttP)(n0 两边积分得：两边积分得：一阶台劳展一阶台
28、劳展开为开为1-1-tt34tntnetPetPdtd)()(1 将将n=1,2,3代入（代入（6）得：）得：积分得：积分得：11101)()(dtetPetPtnttn(6)(6)110011)()(dtetPetPttt(注意利用注意利用(5)式式)tdteettt1011tntntnetPetPedttdP)()()(1tntnntetPetPdttdPe)()()(135 如此继续递推下去得：如此继续递推下去得：tettP!2)()(22 （2 2个顾客到达的概率）个顾客到达的概率）（n n个顾客到达的概率）个顾客到达的概率）tnnenttP!)()(即随机变量即随机变量N(t)=n服
29、从泊松分布。它的数学期望服从泊松分布。它的数学期望和方差为：和方差为：tettP)(1 （1 1个顾客到达的概率）个顾客到达的概率）11011102111)()(dteetdtetPetPtttttt2221t361)0(,)(nxfexf则有 由高等数学知，若设由高等数学知，若设.!.!212nxxxenx 即：即：tkkekt!)(0!)()()(11ntnetnPtNEnntnn)!1()(11nttennt 令令k=n-1，则：，则：!)()(0kttetNEkkt tetetNEtt)(372121)()!1()()!2()(tntntttennnttttttettett22)()1
30、()()1(ttNVar)(即：即：21221)(!)()()(tntnnettPnnntnn22)()()(tNEtNEtNVar 同理方差为：同理方差为：211121)()!1()()!1()()1()()!1()(tntntntetntnennntnnt38 其概率密度函数为：其概率密度函数为：tTTedtdFtf)(t0t0tTetPtF1)(1)(0 t0t0tetP)(0 没有顾客到达的概率为：没有顾客到达的概率为：(由（由（5）式而来）式而来)当输入过程是当输入过程是泊泊松流时，我们研究两顾客相继松流时，我们研究两顾客相继到达的时间间隔的概率分布。到达的时间间隔的概率分布。设设T
31、 T为时间间隔，分布函数为为时间间隔，分布函数为F FT T（t t），即：），即：F FT T（t t）=PTt=PTt 此概率等价于在此概率等价于在00，t t）区间内至少有）区间内至少有1 1个顾客个顾客到达的概率到达的概率.39 由前知，由前知，表示单位时间内顾客平均到达数表示单位时间内顾客平均到达数，这，这里里1/表示顾客到达的平均间隔时间表示顾客到达的平均间隔时间，两者是吻合的。，两者是吻合的。可以证明，间隔时间可以证明，间隔时间T T独立且服从负指数分布与顾独立且服从负指数分布与顾客到达形成泊松流是等价的。客到达形成泊松流是等价的。下面我们再谈一下服务时间的分布：下面我们再谈一下
32、服务时间的分布：对顾客的服务时间对顾客的服务时间，实际是系统处于忙期时两，实际是系统处于忙期时两顾客相继离开系统的时间间隔，一般地也服从负指顾客相继离开系统的时间间隔，一般地也服从负指数分布，即：数分布，即：即即T服从负指数分布，由概率论知它的期望及方差为：服从负指数分布，由概率论知它的期望及方差为：1TE21TVar dxxxfTE)(40其中：其中：表示单位时间内能被服务完成的顾客数表示单位时间内能被服务完成的顾客数，即，即平均服务率。平均服务率。1/1/表示一个顾客的平均服务时间表示一个顾客的平均服务时间。设设v v1 1,v,v2 2，,v,vk k是是k k个独立的随机变量，服从相同
33、个独立的随机变量，服从相同参数参数k k 的负指数分布，那么：的负指数分布，那么：tetF1)(tetf)(，则，则令令 ，则，则称为称为服务强度服务强度。41 串列的串列的k k个服务台，每台服务时间相互独立，服个服务台，每台服务时间相互独立，服从相同的负指数分布（参数从相同的负指数分布（参数k k），那么一顾客走完），那么一顾客走完k k个服务台总共所需要服务时间就服从上述的个服务台总共所需要服务时间就服从上述的k k阶阶ErlangErlang分布。分布。0)!1()()(1tekktktftkkk 则称则称T服从服从k阶阶爱尔朗分布，其特征值为爱尔朗分布，其特征值为:1TE21kTVa
34、r,kT 21的概率密度是的概率密度是(可以证明可以证明)当当k=1k=1时，时，ErlangErlang分布即为负指数分布；分布即为负指数分布；当当k k增加时，增加时，ErlangErlang分布逐渐变为对称的；分布逐渐变为对称的；当当k k 3030时，时，ErlangErlang分布近似于正态分布；分布近似于正态分布；每一个服从每一个服从k k，因此，因此E(TE(Ti i)=1/)=1/k k，且，且T Ti i之间相互独立之间相互独立 b bk k(t)(t)t t k=1k=1 k=2k=2 1/1/ErlangErlang分布曲线分布曲线 k=3k=342 例例:有易碎物品有易
35、碎物品500500件件,由甲地运往乙地由甲地运往乙地,根据以根据以往统计资料往统计资料,在运输过程中易碎物品按普阿松流发在运输过程中易碎物品按普阿松流发生破碎生破碎,其概率为其概率为0.002,0.002,现求现求:1.:1.破碎破碎3 3件物品的概件物品的概率率;2.;2.破碎少于破碎少于3 3件的概率和多于件的概率和多于3 3件的概率件的概率;3.;3.至至少有一件破损的概率少有一件破损的概率.解解:1.:1.求破碎求破碎3 3件物品的概率件物品的概率:=0.002500=1 则则 P(k=3)=(P(k=3)=(3 3/3/3！)e)e-=(1=(13 3/3/3！)e)e-1-1=0.
36、0613=0.0613 即物品破碎即物品破碎3 3件的概率为件的概率为6.136.13 2.2.破碎物品少于破碎物品少于3 3件的概率件的概率:43 破碎物品少于破碎物品少于3 3件的概率为件的概率为91.9791.97 破碎物品多于破碎物品多于3 3件的概率为件的概率为:02.098.01!1430kkekp 3.3.至少有一件破碎的概率为至少有一件破碎的概率为 PkPk 1=1-(11=1-(1k k/k!)e/k!)e-=1-(1=1-(10 0/0!)e/0!)e-1-1=0.632=0.6329197.02111!2120eekkknp44 研究对象为单队、单服务台（服务台数为研究对
37、象为单队、单服务台（服务台数为1 1），），包括：包括：（1 1）标准）标准M/M/1M/M/1模型（模型（M/M/1/M/M/1/）；）；（2 2）系统容量有限制（）系统容量有限制（M/M/1/N/M/M/1/N/）（3 3）有限顾客源（）有限顾客源（M/M/1/mM/M/1/m）45 以后各节将介绍几个常见的排队模型。对排队模以后各节将介绍几个常见的排队模型。对排队模型，在给定输入和服务条件下，主要研究系统的下型，在给定输入和服务条件下，主要研究系统的下述运行指标：述运行指标：(1)(1)系统的平均队长系统的平均队长Ls(Ls(期望值期望值)和平均队列长和平均队列长LqLq期望值；期望值；
38、(2)(2)系统中顾客平均逗留时间系统中顾客平均逗留时间WsWs与队列中平均等与队列中平均等待时间待时间WqWq；本节只研究本节只研究M/M/1M/M/1模型，下面分三种情况讨论：模型，下面分三种情况讨论：46 为分析模型，首先要确定在任意时刻为分析模型，首先要确定在任意时刻t t，状态，状态为为n n（系统中有（系统中有n n个顾客个顾客）的概率的概率P Pn n(t)(t)(瞬态概率瞬态概率)，它决定了系统的运行特征。它决定了系统的运行特征。已知顾客到达服从参数为已知顾客到达服从参数为的普阿松过程，服的普阿松过程，服务时间服从参数为务时间服从参数为的负指数分布。现仍然通过研的负指数分布。现
39、仍然通过研究区间究区间 t，t+tt）的变化来求解。在间刻）的变化来求解。在间刻t+tt，系统中有系统中有n n个顾客不外乎有下列四种情况（到达或个顾客不外乎有下列四种情况（到达或离去离去2 2个以上的没列入，是高阶无穷小）。个以上的没列入，是高阶无穷小）。1、输入过程：顾客源无限，顾客单个到达，相互独立，服从普阿松分布，平稳；2、排队规则：单队，队长无限制，FCFS。3、服务机构：单服务台，各顾客服务时间相互独立，服从负指数分布。此外：假设到达时间间隔和服务时间是相互独立的。标准的标准的M/M/1M/M/1模型即为模型即为M/M/1/FCFS/FCFS模型模型47区间(t,t+t)情况时刻t
40、 的顾客 到达 离去时刻t+t的顾客(t,t+t)的概率0,t+t的概率(略去(t)Ann1-t+(t)1-t+(t)Pn(t)(1-t)(1-t)Bn+1n1-t+(t)t+(t)Pn+1(t)(1-t)(t)Cn-1nt+(t)1-t+(t)Pn-1(t)(t)(1-t)Dnnt+(t)t+(t)Pn(t)(t)(t)48 由于这四种情况是互不相容的，所以由于这四种情况是互不相容的，所以Pn(t+t)t)应应是这四项之和，将所有的高阶无穷小合并，则有：是这四项之和，将所有的高阶无穷小合并，则有：tttPtttPtttPttPnnnn)1)()()1)(1)()(1)()1()(1ttttP
41、n)()()()()()(1)(11ttPttPtPtttttPnnnn)()()()(11tttPttPnn49)()()()1)(11tttPttPtttPnnntttPtPtPttPttPnnnnn)()()()()()()(11 令令t0t0，得关于，得关于P Pn n(t)(t)的微分差分方程：的微分差分方程：)()()()()(11tPtPtPdttdPnnnn(1)当当n=0时，只有表中的（时，只有表中的（A）、（）、（B）两种情况，）两种情况，因为在较小的因为在较小的tt内不可能发生（内不可能发生（D D）（到达后即离）（到达后即离去），若发生可将去），若发生可将tt取小即可。
42、取小即可。50)()1)()1)()(100tttPttPttP)()()(100tPtPdttdP (2)对于方程(1)、(2)求解很麻烦，即便求得解也是瞬态解，无法应用。为此,我们只要求得稳态解即可。稳态时，Pn(t)与时间无关，可以写成Pn，它对时间的导数为0，所以由(1)、(2)两式得：在时刻t系统处于无顾客状态，而在t+t时刻内又没有顾客来到系统（必然没有离去事件）在时刻t系统有一个顾客接受服务，在t+t时刻内服务完毕离去，且在t+t时刻内又没有顾客来到系统0)(11nnnPPP010PP(3)(3)(4)(4)51 上式即为关于上式即为关于Pn的差分方程。由此可得该排队的差分方程。
43、由此可得该排队系统的状态转移图：系统的状态转移图：012n-1nn+1.状态转换图 由（由（4）得：）得：001PPP 其中其中服务强度服务强度 将其代入（将其代入（3）式并令）式并令n=1,2,(也可从状态转移也可从状态转移图中看出状态平衡方程图中看出状态平衡方程)得：得：这种系统状态(n)随时间变化的过程就是生灭过程（Birth and Death Process），它可以描述细菌的生灭过程。520)(120PPP n=10)(020PPP 020202)()(1PPPP n=20)(231PPP0)(0230PPP 030302223)()(1PPPP53 以此类推以此类推，当，当n=n
44、时，时，00)(PPPnnn(5)(5)1 (否则排队无限远，无法服务完否则排队无限远，无法服务完)10nnP 以及概率性质知：以及概率性质知：111000PPnn(数列的极限为 )1110PnnP)1(6)(6)当=1时，似乎好象来一个顾客服务一个顾客，但这是在均衡条件下和所有的顾客的服务时间都相等时，才会出现不存在排队现象的这种理想的现象。在随机的情况下，这是不可能的。54 上式就是系统稳态概率，以它为基础可以上式就是系统稳态概率，以它为基础可以 算出系算出系统的运行指标。统的运行指标。(1)系统中的平均顾客数（队长期望值系统中的平均顾客数（队长期望值Ls）nnnnsnPnL001.)1(
45、.)1(3)1(2)1(32nn.3322143322nnnn1.32n(01)155Ls 即:(7)(7)nnnnqnPnL111)1()1(nnnnn111)1(12sL(8)(8)(3)顾客在系统中的平均逗留时间顾客在系统中的平均逗留时间Ws 顾客在系统中的逗留时间是随机变量，可以证顾客在系统中的逗留时间是随机变量，可以证明，它服从参数为明，它服从参数为-的负指数分布，分布函数的负指数分布，分布函数(2)队列中等待的平均顾客数队列中等待的平均顾客数Lq（队列长期望值）（队列长期望值）56 和密度函数为：和密度函数为：wewF)(1)(wewf)()()(（w00）1wEWs)(WsLs
46、(4)(4)顾客在队列中的等待时间的期望值顾客在队列中的等待时间的期望值W Wq q 顾客在队列中的等待时间应为顾客在队列中的等待时间应为W Ws s减去平均服务减去平均服务时间。时间。111WsWq)(WqLq57 四个指标的关系为四个指标的关系为(Little Little 公式公式)：系统处于空闲状态的概率：系统处于空闲状态的概率：10P 系统处于繁忙状态的概率：系统处于繁忙状态的概率：01)0(PNPLsLq1swqwWsLsWqLq1qswwqsLL 下标s表示系统 下标q表示队列583.2 系统容量有限制的系统容量有限制的模型模型 M/M/1/N/FCFS/FCFS 当系统容量最大
47、为当系统容量最大为N N时，排队系统中多于时，排队系统中多于N N个的顾个的顾客将被拒绝。当客将被拒绝。当N=1N=1时，即为瞬时制；时，即为瞬时制；NN时，即时，即为容量无限制的情况。为容量无限制的情况。排队系统 服务台顾客 N 4 3 2 1被拒绝59 现在研究系统中有现在研究系统中有n n个顾客的概率个顾客的概率P Pn n(t).(t).对于对于P P0 0(t)(t)，前面的（，前面的（2 2）式仍然成立）式仍然成立)()()(100tPtPdttdP(2)(2)对于对于(1)(1)式，当式，当n=1,2,n=1,2,N-1N-1时，也仍能成立。时，也仍能成立。)()()()()(1
48、tPtPtPdttdPnnnn(1)(1)(n=1,2,(n=1,2,N-1)N-1)但当但当n=Nn=N时，有下面两种情况：时，有下面两种情况：60情 况时 刻t的 顾 客区 间 t,t+t时 刻t+t的 顾 客 数概 率AN无 离 去（肯 定 不 到 达）NPN(t)(1-t)BN-1一 人 到 达（无 离 去）NPN-1(t)tttPttPttPNNN)()1()()(1)()()(1tPtPdttdPNNN(8)(8)其状态转移图为其状态转移图为:012n-1nn+1.状态转换图.N-1N61 在稳态情况下有：在稳态情况下有：010PP0)(11nnnPPP01NNPP(9)(9)解（
49、解（9）式得：）式得：01PP022PP0PPNN NnnNnnNnnPPP000001 而等比数列而等比数列10111NnNn621011NPnNnP111(1,nN)(1,nN)(10)(10)注：当注：当=1=1时，试讨论其概率时，试讨论其概率P Pn n下面计算其运行指标：下面计算其运行指标：(1)平均队长平均队长Ls：nPnLnNnNNnns01011nNnNn0111111)1(1NNN(1)试证=1时,Ls=N/263（2 2）队列长（期望值）队列长（期望值）NnsnqPLPnL10)1()1(有效到达率有效到达率e的引入：的引入：Little公式可应用的条件是：其平均到达率公式
50、可应用的条件是：其平均到达率是在系统是在系统有空时有空时的平均到达率。当系统满员时，就的平均到达率。当系统满员时，就不能再应用了。要用就应该应用有效到达率。不能再应用了。要用就应该应用有效到达率。因为系统容量有限，当满员时，顾客将被拒绝，因为系统容量有限，当满员时，顾客将被拒绝，因此实际的顾客到达率为因此实际的顾客到达率为0，与，与不一样，为了求不一样，为了求其他指标，需要求得有效到达率为其他指标，需要求得有效到达率为e：)1(NeP)1(0Pe可以验证：可以验证：64esesqLLLesSLWeqqLW 此种情况此种情况的公式与的公式与前类似，前类似，只有只有Ls不不同，同，e与与 不同。不
