给16萌萌哒的小学妹弟研一上运筹学

1、1OPERATIONS RESEARCH运筹学把握住随机 郑江波2排队论(Queuing Theory) 排队论（queuing),也称随机服务系统理论，是运筹学的一个主要分支。 1909年，丹麦哥本哈根电子公司电话工程师A. K. Erlang的开创性论文“概率论和电话通讯理论”标志此理论的诞生。排队论的发展最早是与电话，通信中的问题相联系的，直到现在这还是排队论的传统的应用领域。近年来在计算机通讯网络系统、交通运输、医疗卫生系统、库存管理、作战指挥等各领域中均得到应用。31.1 排队系统的组成与特征 排队系统一般有三个基本组成部分：1.输入过程；2.排队规则；3.服务机构。1 排队论的基本

2、概念4输入即为顾客的到达，可有下列3种情况：1）顾客来源。顾客总体(称为顾客源)的组成可能是有限的，也可能是无限的。如，上游河水流入水库可以认为总体是无限的，工厂内停机待修的机器显然是有限的总体。2）顾客到达方式。顾客到来的方式可能是一个一个的，也可能是成批的。如，到餐厅就餐就有单个到来的顾客和受邀请来参加宴会的成批顾客。 1. 输入过程53）顾客流的概率分布。顾客随机一个(批)个(批)来到排队系统，顾客流的概率分布用来描述相继到达的顾客之间的间隔时间分布是确定的还是随机的，分布参数是什么，到达的间隔时间是否独立，分布是随时间变化的还是平稳的。62. 排队规则 1）损失制。顾客到达时，如果所有

3、的服务台都被占用，且服务机构又不允许顾客等待，顾客只能离去，这种服务规则就是损失制。2）等待制。当顾客到达时，如果所有服务台都被顾客占用而无空闲，这时该顾客自动加入队列排队等待服务，服务完才离开。 （1）先到先服务 FCFS （2）后到先服务 LCFS（3）随机服务RAND （4）有优先权服务 PR 73. 服务机构 1）服务机构可以是单服务员和多服务员服务，这种服务形式与队列规则联合后形成了多种不同队列，不同形式的排队服务机构，如：8 2)服务方式分为单个顾客服务和成批顾客服务。 3)服务时间分为确定型和随机型。 4)服务时间的分布在这里我们假定是平稳的。9上述特征中最主要的、影响最大的是：

4、顾客相继到达的间隔时间分布服务时间的分布服务台数 D.G.Kendall，1953提出了分类法，称为Kendall记号(适用于并列服务台)即：X/Y/Z:A/B/C1.2 排队系统的模型分类10式中：X顾客相继到达间隔时间分布。M负指数分布Markov，D确定型分布（Deterministic）EkK阶爱尔朗分布Erlang， G 一般随机分布GI 一般相互独立随机分布(General Independent) Y填写服务时间分布（与上同）Z填写并列的服务台数A排队系统的最大容量B顾客源数量 C排队规则 如 M/M/1:/FCFS即为顾客到达为泊松过程，服务时间为负指数分布，单台，无限容量，无

5、限源，先到先服务的排队系统模型。11系统指标队长，指在系统中的顾客数，它的期望值记Ls；(2) 排队长，指在系统中排队等待服务的顾客数，它的期望值记作Lq 系统中顾客 数在队列中等待服务的顾客数正被服务的顾客数+=一般情形，Ls(或Lq)越大，说明服务效率越低。12(3) 逗留时间，指一个顾客在系统中的停留时间，它的期望值记作Ws；(4) 等待时间，指一个顾客在系统中排队等待的时间，它的期望值记作Wq；等待时间服务时间+逗留时间=131.3 排队论研究的基本问题 （1）排队系统的统计推断:即通过对排队系统主要参数的统计推断和对排队系统的结构分析，判断一个给定的排队系统符合于哪种模型，以便根据排

6、队理论进行研究。 （2）系统性态问题:即研究各种排队系统的概率规律性，主要研究队长分布、等待时间分布和服务期分布等统计指标,包括了瞬态和稳态两种情形。 （3）最优化问题：即包括最优设计(静态优化)，最优运营（动态优化）。 141.4 排队问题求解(主要指性态问题) 排队问题的一般步骤： 1. 确定或拟合排队系统顾客到达的时间间隔分布和服务时间分布(可实测)。 2. 研究系统状态的概率。系统状态是指系统中顾客数。状态概率用Pn(t)表示,即在t时刻系统中有n个顾客的概率，也称瞬态概率。15 求解状态概率Pn(t)方法是建立含Pn(t)的微分差分方程，通过求解微分差分方程得到系统瞬态解，由于瞬态解

7、一般求出确定值比较困难，即便求得一般也很难使用。因此我们常常使用它的极限(如果存在的话)： 稳态的物理意义见右图，系统的稳态一般很快都能达到，但实际中达不到稳态的现象也存在。值得注意的是求稳态概率Pn并不一定求t的极限,而只需求Pn(t)=0 即可。过渡状态稳定状态pnt图3 排队系统状态变化示意图 称为稳态(steady state)解，或称统计平衡状态 (Statistical Equilibrium State)的解。162 到达间隔时间分布和服务时间的分布 一个排队系统的最主要特征参数是顾客的到达间隔时间分布与服务时间分布。要研究到达间隔时间分布与服务时间分布需要首先根据现存系统原始资

8、料统计出它们的经验分布，然后与理论分布拟合，若能对应，我们就可以得出上述的分布情况。172.1 经验分布 经验分布是对排队系统的某些时间参数根据经验数据进行统计分析，并依据统计分析结果假设其统计样本的总体分布，选择合适的检验方法进行检验，当通过检验时，我们认为时间参数的经验数据服从该假设分布。 分布的拟合检验一般采用2检验。由数理统计的知识我们知：若样本量n充分大(n50)，则当假设H0为真时，统计量总是近似地服从自由度为k-r-1的 2分布，其中k为分组数，r为检验分布中被估计的参数个数。182.2 理论分布 式中为常数(0)，称X服从参数为的泊松分布，若在上式中引入时间参数t，即令t代替，

9、则有： 1.泊松分布 在概率论中，我们曾学过泊松分布，设随机变量为X，则有：n=0,1,2, （1） 与时间有关的随机变量的概率，是一个随机过程，即泊松过程。 t0，n=0,1,2, （2）19（t2t1，n0） 若设N(t)表示在时间区间0,t)内到达的顾客数(t0),Pn(t1,t2)表示在时间区间t1,t2)(t2t1)内有n(0)个顾客到达的概率。即： 在一定的假设条件下 顾客的到达过程就是一个泊松过程。 当Pn(t1,t2)符合下述三个条件时，顾客到达过程就是泊松过程(顾客到达形成泊松流)。20 无后效性：各区间的到达相互独立,即Markov性。 也就是说过程在tn所处的状态与 以前

10、所处的状态无关(t+t的状态与t之前的状态无关） 。平稳性：即对于足够小的t，有：泊松流具有如下特性： 在t,t+t内有一个顾客到达的概率与t无关,而与t成正比。21 普通性：对充分小的t,在时间区间（t,t+t）内有2个或2个以上顾客到达的概率是一高阶无穷小.由此知，在(t，t+t)区间内没有顾客到达的概率为： 令t1=0,t2=t,则P(t1,t2)=Pn(0,t)=Pn(t) 0 是常数，它表示单位时间到达的顾客数，称为概率强度。即P0+P1+P2=1在上述假设下，t时刻系统中有n个顾客的概率pn(t)： 22 A n pn(t) 01-t+ (t) pn(t)(1-t+ (t)B n-

11、1 pn-1(t) 1t pn-1(t)t(t) (t)n-2 Pn-2(t) 2C n-3 Pn-3(t) 30 P0(t) n23(1)(2)当n=0时，则(3)（没有顾客到达的概率）将（3）代入（1）式，运用数学归纳法求出（4）瞬态方程求解（2）的微分方程，可得：24级数令k=n-1，则：同理方差为：顾客到达过程是一个泊松过程(泊松流)。期望252.负指数分布 可以证明当输入过程是泊松流时，两顾客相继到达的时间间隔T独立且服从负指数分布。（等价） 因为到达为泊松流，所以，t时段内没有来顾客的概率为所以， t时段内有顾客到来（即间隔T t ）的概率为而这正是负指数分布的分布函数，说明T 服

12、从负指数分布，且参数同为 。26 表示单位时间内顾客平均到达数,1/表示顾客到达的平均间隔时间。对顾客的服务时间：系统处于忙期时两顾客相继离开系统的时间间隔，一般地也服从负指数分布，服务时间的分布：，则其中：表示单位时间内能被服务的顾客数，即平均服务率。 1/表示一个顾客的平均服务时间。令 ，则称为服务强度。可以证明：27 3.爱尔朗(Erlang)分布 设v1, v2，, vk是k个独立的随机变量，服从相同参数 k 的负指数分布，那么：其概率密度是28 串联的k个服务台，每台服务时间相互独立，服从相同的负指数分布（参数k），那么一顾客走完k个服务台总共所需要服务时间就服从上述的k阶Erlan

13、g分布。则称T服从k阶爱尔朗分布。其特征值为：,1/ k表示一个顾客的一个服务台的平均服务时间。29 例:有易碎物品500件,由甲地运往乙地,根据以往统计资料,在运输过程中易碎物品按泊松分布发生破碎,其破损率为0.002,现求:1.破碎3件物品的概率;2.破碎少于3件的概率和多于3件的概率;3.至少有一件破损的概率. 解: =0.002500=1 1破碎3件物品的概率为: P(k=3)=(3/3！)e-=(13/3！)e-1=0.0613 即物品破碎3件的概率为6.13 2.破碎物品少于3件的概率:30 破碎物品少于3件的概率为91.97破碎物品多于3件的概率为:3.至少有一件破碎的概率为 P

14、k1=1-(1k/k!)e-=1-(10/0!)e-1=0.63231 对排队模型，在给定输入和服务条件下，主要研究系统的下述运行指标： (1)系统的平均队长Ls(期望值)和平均队列长Lq(期望值)； (2)系统中顾客平均逗留时间Ws与队列中平均等待时间Wq； 本节只研究M/M/1模型，下面分三种情况讨论：3.M/M/1模型323.1 标准的M/M/1模型 M/M/1:/FCFS模型 1.稳态概率Pn的计算 在任意时刻t，状态为n的概率Pn(t)（瞬态概率），它决定了系统的运行特征。 已知顾客到达服从参数为的泊松过程，服务时间服从参数为的负指数分布。现仍然通过研究区间t，t+t）的变化来求解。

15、在时刻t+t，系统中有n个顾客不外乎有下列四种情况（ t，t+t）内到达或离开2个以上没列入）。？ 33 由于这四种情况是互不相容的，所以Pn(t+t)应是这四项之和，则有：所有的高阶无穷小合并34令t0，得关于Pn(t)的微分差分方程：(1) 当n=0时，只有表中的（A）、（B）两种情况，因为在较小的t内不可能发生（D）（到达后即离去），若发生可将t取小即可。(2)生灭过程瞬态解35由此可得该排队系统的状态转移图：由（4）得：其中服务强度 将其代入（3）式并令n=1,2,(也可从状态转移图中看出状态平衡方程)得：关于Pn的差分方程n-1nn+1201稳态时， 它对时间的导数为0，所以由(1)

16、、(2)两式得：Pn(t)与时间无关,可以写成Pn,(3)(4)36n=1n=237以此类推，当n=n时，(5)以及概率性质知：(数列的极限为 )(6)否则排队无限远系统稳态概率系统的运行指标382. 系统的运行指标计算 (1) 系统中的队长Ls（平均队长）(00)=Lq43例1 某修理店只有一个修理工人，来修理的顾客到达服从泊松流，平均每小时4人；修理时间服从负指数分布，平均需6分钟。求：（1）修理店空闲的概率；（2）店内有3个顾客的概率；（3）店内至少有1个顾客的概率；（4）店内顾客的平均数；（5）顾客在店内的平均逗留时间；（6）等待服务的顾客平均数；（7）平均等待修理时间；（8）必须在店内消耗15分钟以上的概率。4445例2： 某医院手术室根据病人来诊和完成手术的时间记录，任意抽查100个工作小时，每小时来就诊的病人数n的出现次数如表1。又任意抽查了100个完成手术的病历，所用时间v(小时)出现的次数如表2。计算手术室的各项指标。46到达的病人数n出现次数fn010128229316410566以上1合计100为病人完成手术时间v(小时)出现次数fv0.00.2380.20.4250.40.6170.60.890.81.061.01.251.2以