数学建模与排队论与泊松过程

Poisson过程与排队论模型三峡大学理学院于林排队是日常生活中经常遇到的现象，如顾客到商店购物，病人到医院看病等等，常要遇到排队。排队的目的是要求另外的人或事物为其服务，而一旦不能立即被服务就必然形成排队。这种现象不仅在个人日常生活中出现，电信局的占线问题，车站、码头等交通枢纽的车船堵塞和疏导，故障机器待修等都是有形无形的排队现象。研究这些排队现象的规律的学科就是排队论，也叫随机服务系统。主要内容1排队论的几个基本概念2Poisson过程3几个常见的排队论模型一、排队论的几个基本概念我们把要求服务的人或事物称为顾客，把为顾客服务的人或事物叫做服务机构（服务员或服务台），顾客排队要求服务的过程或现象称为排队系统或服务系统。由于顾客到达的时刻与进行服务的时间一般来说都是随机的，所以服务系统又称随机服务系统。各种随机服务系统都有3个共同的组成部分（1）输入系统:即各种类型的顾客按照怎样的规律到达服务系统要求服务；（2）排队规则:指到达系统的顾客按什么次序接受服务；（3）服务机构:指同一时刻有多少服务设备可以接纳顾客，每个顾客须服务多少时间。判别一个服务系统优劣的主要指标有sL【队长】指在系统中的顾客数，它的期望值记作sL。【排队长】指在系统中排对等待服务的顾客数，它的期望值记作qL。一般说来，sL或qL越大，说明服务质量越低，排队成龙，顾客最讨厌。【逗留时间】指一个顾客在系统中的停留时间，它的期望值记作sW。【等待时间】指一个顾客在系统中排队等待的时间，它的期望值记作qW。[逗留时间]=[等待时间]+[服务时间]【忙期】指从一个顾客到达空闲服务机构起，到服务机构再次空闲时止这段时间的长度，即服务机构连续工作的时间长度。它关系到服务员的工作强度和服务质量。分析和研究服务系统的服务状况需要以上一些指标，而计算这些指标的基础是表达系统状态的概率。我们用)(tPn表示在时刻t，系统的状态为n（即系统中的顾客数为n）的概率。计算)(tPn的方法可以通过输入过程，排队规则，和服务机构的具体情况建立关于)(tPn的微分差分方程。因此研究排队问题的关键在于如何建立关于)(tPn的微分差分方程。怎样由)(tPn的微分差分方程求解)(tPn关系到排队问题能否最终解决。一般来说，方程的瞬态解（即通常解）是不容易求得的，即使求得也很难利用。为了使问题简化，可以令0)(/tPn的办法求解。这样一来就把微分差分方程变成差分方程，而不再含微分了。因为这样做意味着把)(tPn当作与t无关，因此称为稳态解。尽管不稳态的情况确实存在，但对大多数的应用问题系统会趋于稳态的。二．Poisson过程一种常用的输入过程Poisson过程的得出，本身就是一个数学建模的过程。用)(tN表示在时间区间],0(t内到达的顾客数)0(t，用),(21ttPn表示在时间区间),[21tt)(12tt内有n个顾客到达的概率。即),(21ttPn})()({12ntNtNP我们来探求)(tPn的概率分布。【基本假设】（1）无后效性（或独立增量性）：在不相重叠的时间区间内，到达系统的顾客数是相互独立的；（2）平稳性：对充分小的t，在时间区间),[ttt内，有一个顾客到达的概率与t无关，而约与t成正比，即),(1tttP)(tot其中0为常数，它表示单位时间内平均到达的顾客数；（3）普通性：对充分小的t，在时间区间),[ttt内，有两个和两个以上顾客到达的概率很小，以至于可以忽略不计。即)(),(2totttPnn。【模型求解】由条件（1），我们总可以取时间由0算起，并记),0()(tPtPnn。在由条件（2）（3）易知，在时间区间),[ttt内没有顾客达到的概率为)(1),(0tottttP注意到),0[tt可以分为),0[t和),[ttt两部分，利用全概率公式得)(ttPn)1)((ttPn)()(1tottPn)1(n两边同除以t，并令0t，便得到0)0(,1),()()(1nnnnPntPtPdttdP（1）其中0)0(nP为当然的初始条件。当0n时，可以得到1)0()()(000PtPdttdP（2）其中1)0(0P表示在0t时没有人到达的概率是1。初值问题（2）很容易求解，用分离变量法先求出)(0tP，然后在通过递推法，便可得到tnnenttP!)()(，,0t,3,2,1,0n因此这种计数过程)(tN被成为强度为的Poisson过程。【时间间隔的分布】当输入过程是Poisson过程是，我们考察两个顾客相继到达的时间间隔T（显然也是随机变量）的概率分布。设T的分布函数为)(tFT，则}{)(tTPtFT}{1tTP)(10tPte1，)0(t从而其密度函数为tTTetFdtdtf)()(，)0(t所以T为具有数学期望1的指数分布。这在直观上也容易理解：若平均到达率为，那么平均到达时间间隔必为1。【服务时间的分布】对一个顾客的服务时间v（随机变量），就是忙期两个顾客相继离开系统的时间间隔，一般也服从指数分布。这可以通过和前面类似的办法说明，只需把前面的输入流换成同样分布的输出流即可。设v的分布函数和密度函数分别是tvetF1)(，tvetf)(，)0(t其中表示单位时间能被服务完的顾客数（期望值），称为平均服务率。比值有明确的含义，它表示在相同时间区间内，顾客到达的平均数与被服务的平均数之比；或者是对相同顾客数，服务时间之和的期望值与到达时间间隔之和的期望值的比。这个比值是刻画服务效率和服务机构利用程度的重要标志，我们称为服务强度。显然，越小，服务质量越好；当1时，队列将无限长，服务质量太差。三、几个常见的排队论模型模型一.顾客源无限，系统容量不限的M/M/1模型这一模型的具体条件是：在输入过程中，顾客有无限多个，而且彼此相互独立地单独到来，到达过程是平稳的，到达的顾客流服从Poisson分布。服务规则要求单队，且队长没有限制，先到先服务。服务机构为单服务台，对各个顾客的服务时间是相互独立的，且服从相同的指数分布。设顾客的到达规律服从参数为的Poisson分布，而服务时间服从参数为的指数分布。这样，在时间区间),[ttt内，有一个顾客到达的概率为)(tot，没有顾客到达的概率为)(1tot；当顾客接受服务时，1个顾客被服务完了（离去）的概率为)(tot，而没有服务完（没离去）的概率为)(1tot。多于1个顾客的到达或离去的概率为)(to。于是，运用全概率公式，有)(ttPn))(1)((tottPn))(1(tot))()((tottPn))((tot))(1)((1tottPn))((tot))()((1tottPn))(1(tot)(to整理得)(ttPn)1)((tttPnttPn)(1ttPn)(1)(to)(ttPn)(tPnttPn))((ttPn)(1ttPn)(1)(to两边同除以t，并令0t，便得到关于)(tPn的微分差分方程)()()()()(11tPtPtPtPdtdnnnn（1）（1）式是在1n时得到的，当0n时类似地可得到)()()(100tPtPtPdtd（2）现在我们要求（1）和（2）的稳态解，即令0)(tPdtdn，,3,2,1,0n得到关于)(tPn的差分方程为：0)()()1(,0)()()()(1011tPtPntPtPtPnnn（3）由此便可求得00PPPnnn（4）这里我们假设1（否则队列将排至无限），在注意10nnP，于是111000PPnn由此得)1(,)1()1(,10nPPnn（5）这就是系统状态为n的概率。下面我们以此为基础计算系统的几个主要指标。1．系统中的平均顾客数（即队长的期望值sL）0nnsnPLnnn0)1(12．队列中的平均顾客数（即队列长的期望值qL）0)1(nnqPnLsL12)(23．一个顾客在系统中逗留时间的期望值sW在排队论中有结论：当输入流是参数为的Poisson流，服务时间服从参数为的指数分布时，1个顾客在系统中的逗留时间W服从参数为的指数分布。从而1)(WEWs4．一个顾客在系统中等待时间的期望值qW1sqWW)(【案例分析之一】到共用电话间打电话的人可以认为是以Poisson流到达，且两个人到达的平均时间间隔为10分钟，打一次电话的平均时间为3分钟，试问：（1）这一电话的平均排队人数；（2）每一个人的平均等待时间；（3）1个人到达后必须等待的概率；（4）若这一电话间每天只连续开放8小时，那么可能有多少时间它是空闲的；（5）若电话局确信1个人到电话间至少须等待3分钟时，就会在此电话间在安装另一部电话，那么在平均到达率增加到多少时，须安装另一部电话？【解】平均到达率10.0101（人/分钟）平均服务率33.031（人/分钟）（1）qL)(213.0)10.033.0(33.0)10.0(2（人）（2）)(qW32.1)10.033.0(33.010.0（分钟）（3）3.033.010.010PP（4）由于7.010P（单位时间内闲置的概率），所以这部电话在开放的8小时内闲置时间大约有6.57.08（小时）（5）设平均到达率由原来的10.0增加到/时，1个人到电话间后至少必须等待3分钟，即这时须加装另一部电话，那末)33.0(33.03//解此方程得到/16.0。模型二.系统容量有限（Ｎ）的M/M/1模型现在的问题与第一个问题比较，只是把容量不限换成容量为N，所以模型一的差分方程当Nn时，在这里也是对的。现在我们只需考虑Nn的情况，仍然运用全概率公式得：)(ttPN))(1)((tottPN1))()((1tottPN))(1(tot)(to经过类似的处理，可以得到)()()(1tPtPtPdtdNNN从而得模型二的稳态情形的差分方程为：11101)1,,2,1(,)1(NNnnnPPNnPPPPP注意这时有10NnnP，解此差分方程便得)(11)1(11110NnPPnNnN这里我们没有考虑1的情况，也没有限制1。若令N，则模型二就变成模型一。借助上式的结果，可以求得模型二的几个主要指标：1．系统中的平均顾客数（即队长的期望值sL）NnnsnPL0121)1(1NNN)1(2．队列中的平均顾客数（即队列长的期望值qL）0)1(nnqPnL)1(0PLs3．一个顾客在系统中逗留时间的期望值sW这时要注意，平均到达率是在系统有空时的平均到达率。当系统已满)(Nn时，则到达率为0，因此需要求出有效到达率e。因为正在被服务的顾客平均数为：eP01由此得10111)1(NeP)1(111NNNP再注意，当系统容量无限时有sL，1sW所以ssLW当系统容量为N时，上述公式也成立。实际上这个公式可以单独证明，这就是著