第六章排队论ppt课件.ppt

《第六章排队论ppt课件.ppt》由会员分享，可在线阅读，更多相关《第六章排队论ppt课件.ppt（64页珍藏版）》请在三一办公上搜索。

1、数学建模简明教程,国家精品课程,第六章 排队论,一、问题引入与分析,二、排队论的基本概念,三、几类排队论模型,四、模型的建立与求解,1. 2001年全国数学竞赛的B题“公交车调度”,某条公交线路上行方向共14站，下行方向共,13站.公交公司配给该线路同一型号的大客车，每,辆标准载客100人，据统计客车在该线路上运行的,平均速度为20公里/小时.运营调度要求，乘客候车,时间一般不要超过10分钟，早高峰一般不要超过,是这样的：,一、问题引入与分析,5分钟，车辆满载率不应超过120%，一般也不要,低于50%.,试根据这些材料和要求，为该线路设计一个,便于操作的全天（工作日）的公交车调度方案,包括两个

2、起点站的发车时刻表；一共需要多少,辆车；这个方案以怎样的程度照顾到了乘客和,公交公司双方的利益；等等.,2.问题分析：,对于第一个问题，关于公交车的调度方案，,可以利用各种的不同的方法，比如多目标规划，,去求得在一定原则下的最优方案，得到一个满足,实际情况的分配方案，但要建立具体的明确、完,整的数学模型，以及求解模型的方法，如何采集,运营数据是关键的.在实际中，公交车具有随机,性，特别是顾客的到来是随机的，是无法精确预,测的，这就决定了公交车的数量并不是完全确定,的固定不变的，而是随着不同时段顾客的多少而,变化.因此顾客和公交车之间存在随机因素.,很明显，顾客和公交车是一个服务和被服务,的关系

3、.如果公交车数量过多，也就是已有的资,源大于需求，虽然公交车的数量能够满足顾客,需求，减少了顾客排队等待的时间，公交车提供,的服务使顾客的满意度很高，却会造成公交车公,司的浪费，比如某一时段某一线路所发公交车上没,有顾客或很少的顾客，个别时段个别线路如此，公,交车公司也许可以接受，但长时间的空跑或入不敷,出，最终会使公交车公司不堪重负，甚至倒闭；另,一方面，如果公交车数量较少，很多顾客得不到服,务，或者很多顾客花了很长的时间去排队等候，造,成顾客的不满意度提高，这样公交车公司会失去顾客.,如何考虑随机因素，设计合理方案，建立数学模,型，一方面提供服务的服务机构即公交公司的线,路设计合理，能够赢

4、得顾客，获得利益；另一方,面被服务的顾客能够在被服务的过程中，排队等,候的时间最短，这都是上述问题要解决的，也是,排队论的主要研究内容.,二、排队论的基本知识,2. 排队系统描述,3. 基本组成部分,4. 数量指标,5. 排队模型的记号,1. 背景介绍,1.背景介绍,排队论是研究排队现象的理论和应用的学科，是,专门研究由于随机因素影响而产生的拥挤现象的科学.,20世纪初丹麦数学家、电气工程师爱尔朗把概率论应,用于电话通话问题，从而开创了这门应用数学科学.,20世纪30年代中期，费勒引进了生灭过程，排队论,才被数学界承认为一门重要的学科.20世纪40年代排,对论在运筹学这个新领域中成了一个重要的

5、部分.20,世纪50年代初肯德尔对排对论作了系统的研究，他用,马尔科夫链方法研究排队论，使排队论得到进一步发,展.20世纪60年代起排队论研究的课题日趋复杂，很,多问题很难求得精确解，因此开始了近似方法的研究.,排队论应用范围很广，它适用于一切服务系统.尤,其在通信系统、交通系统、计算机存储系统和生产管理,系统等方面应用的最多.,排队是日常生活和工作中常见的现象.例如等公共,汽车排队，到商店购物排队，交款排队，到医院看病,等待排队，买火车票排队，托运行李排队，取货排队，,这是人的排队.还有另一种排队，例如文件等待打印或,发送，报告等首长批示，路口红红灯下的汽车、自行车,等待通过路口，这是物或设

6、备排队.,总之，凡是具有公共服务性质的事业和工作，凡,是出现拥挤现象的领域，都是排队论的用武之地.,2.排队系统描述,排队系统又称为随机服务系统，是研究服务,请求服务的人或者物顾客；,排队系统的共同特征：,顾客到达系统的时刻是随机的，为每一位顾客,有为顾客服务的人或者物，即服务员或服务台；,过程和拥挤现象的随机模型.,提供服务的时间是随机的，因而整个排队系统,的状态也是随机的.,排队系统的几种形式：,基本排队过程：,从图66可知，每个顾客由顾客源按一定方式,到达服务系统，首先加入队列排队等待接受服务，,然后服务台按一定规则从队列中选择顾客进行服,务，获得服务的顾客立即离开.,排队论所要研究解决

7、的问题：,面对拥挤现象，人们通常的做法是增加服务设施,但是增加的数量越多，人力、物力的支出就越大，甚,至会出现空闲浪费，如果服务设施太少，顾客排队等,待的时间就会很长，这样对顾客会带来不良影响.如,何做到既保证一定的服务质量指标，又使服务设施费,用经济合理，恰当地解决顾客排队时间与服务设施费,用大小这对矛盾，就是随机服务系统理论排队论,所要研究解决的问题。,3.排队系统的基本组成部分,排队系统是由输入过程、排对规则和服务机构组成.,(1).输入过程 指要求服务的顾客是按怎样的规律,(i) 顾客总体数. 又称顾客源、输入源.这是指顾客,(ii) 顾客到达方式. 这是描述顾客是怎样来到系统,到达排

8、队系统的过程，有时也把它称为顾客流.一,般可以从3个方面来描述个输入过程.,的来源.顾客源可以是有限的，也可以是无限的.,的，是单个到达，还是成批到达.,(iii) 顾客流的概率分布.或称相继顾客到达的时间,(2).排对规则 指服务台从队列中选取顾客进行,(i)损失制 指如果顾客到达排队系统时，所有,间隔的分布.这是求解排队系统有关运行指标问题,时，首先需要确定的指标.顾客流的概率分布一般,有定长分布、二项分布、泊松流(最简单流)、爱尔,朗分布等若干种.,服务的顺序.一般可以分为损失制、等待制和混,合制等3大类.,服务台都被先到的顾客占用，那么他们就自动,离开系统永不再来.,(ii)等待制 指

9、当顾客来到系统时，所有服务台,a.先到先服务 按顾客到达的先后顺序对顾客,b.先到后服务,c.随机服务 即当服务台空闲时，不按照排队,d.优先权服务,都不空，顾客加入排队行列等待服务.等待制中，,服务台在选择顾客进行服务时常有如下四种规则：,进行服务.,序列而随意指定某个顾客接受服务.,(iii)混合制 这是等待制与损失制相结合的一种服,a.队长有限.当排队等待服务的顾客人数超,b.等待时间有限.即顾客在系统中的等待时,c.逗留时间(等待时间与服务时间之和)有限.,务规则，一般是指允许排队，但又不允许队列无限,长下去.具体说来，大致有三种：,过规定数量时，后来的顾客就自动离去，另,求服务，即系

10、统的等待空间是有限的.,间不超过某一给定的长度T，当等待时间超,过T时，顾客将自动离去，并不再回来.,(3). 服务机构,(i)服务台数量及构成形式. 从数量上说，服务台有单,(ii)服务方式. 这是指在某一时刻接受服务的顾客数，,(iii)服务时间的分布.在多数情况下，对每一个顾客的,服务台和多服务台之分. 从构成形式上看，服务台有：,单队一-单服务台式；单队一-多服务台并联,式；多队一-多服务台并联式；单队一-多服,务台串联式；单队一-多服务台并串联混合式，,以及多队多服务台并串联混合式等等.,它有单个服务和成批服务两种.,服务时间是一随机变量.,4. 排队系统的主要数量指标,排队论主要研

11、究系统的性态，即与排队有关,(1).排队系统主要数量指标,等待时间、 忙期、 队长.,的数量指标的概率规律性；系统的优化问题；统,计推断，根据资料合理建立模型.目的是正确设,计和有效运行各个服务系统，使之发挥最佳效益.,所以必须确定判断系统运行优劣的基本数量指标.,(i).等待时间 从顾客到达时刻起到他开始接受服务止这,(ii).忙期 忙期是指从顾客到达空闲着的服务机构起，到,(iii).队长 队长是指系统中的顾客数(排队等待的顾客数与,段时间称为等待时间.等待时间是个随机变量.从顾客,到达时刻起到他接受服务完成止这段时间称为逗留时,间，也是随机变量.,服务机构再次成为空闲止的这段时间，即服务

12、机构连续忙,的时间.这是个随机变量，是服务员最为关心的指标，因,为它关系到服务员的服务强度.与忙期相对的是闲期,即,服务机构连续保持空闲的时间.在排队系统中，忙期和闲,期总是交替出现的.,正在接受服务的顾客数之和)；排队长是指系统中正在排队,等待服务的顾客数.队长和排队长一般都是随机变量.,(2).数量指标的常用记号,(i).主要数量指标,W平均逗留时间，即(在任意时刻)进入,所有顾客数的期望值；,等待服务的顾客数的期望值；,稳态系统的顾客逗留时间的期望值；,稳态系统的顾客等待时间的期望值.,L-平均队长， 即稳态系统任一时刻的,平均等待时间，即(在任意时刻)进入,平均等待队长，即稳态系统任一

13、时刻,(ii).其它常用数量指标,s 系统中并联服务台的数目；,N 稳态系统任一时刻的状态（即系统中,U 任一顾客在稳态系统中的逗留时间；,Q 任一顾客在稳态系统中的等待时间；,所有顾客数）；,平均到达率；,平均到达间隔；,平均服务率；,平均服务时间；,有服务台全部空闲的概率；,繁忙程度的重要尺度.,服务强度，即每个服务台单位时间内的平,均服务时间，一般有 ，这是衡量排队系统,:稳态系统任意时刻状态为n的概率；,5. 排队系统的描述符号,描述符号：X/Y/Z/A/B/C,X顾客相继到达的间隔时间的分布 ；常用下,M表示到达的过程为泊松过程或负指数分布；,D表示定长输入；,G表示一般相互独立的随

14、机分布.,Y服务时间的分布；所用符号与表示顾客,列符号：,到达间隔时间分布相同.,表示K阶爱尔朗分布；,Z服务台个数 ； “1”表示单个服务台，“s” (s1),A系统容量限制(默认为)；如系统有K个等待位子，则,B顾客源数目（默认为）；分有限与无限两种，表,C服务规则；,常用下列符号：,FCFS：表示先到先服务的排队规则；,LCFS：表示后到先服务的排队规则；,PR： 表示优先权服务的排队规则。,表示多个服务台.,0K，当K=0时，说明系统不允许等待，即为损失制.,K=时为等待制系统，此时一般省略不写.K为有限整数,时，表示为混合制系统.,示顾客源无限，一般也可省略不写.,例如：某排队问题为

15、MMS/FCFS，则,某些情况下，排队问题仅用上述表达形式,如不特别说明则均理解为系统等待空间容量,表示顾客到达间隔时间为负指数分布(泊松流)；,服务时间为负指数分布；有s (s1)个服务台；系,统等待空间容量无限(等待制)；顾客源无限，采,用先到先服务规则.,中的前3个符号.例如，某排队问题为MMS.,无限；顾客源无限，先到先服务，单个服务的等,待制系统.,三、几类排队论模型,1. M/M/S 模型,2. GI/M/n 模型,1. M/M/s排队模型,M/M/s排队模型是指s个服务员的排队系统，,顾客到来间隔时间是独立同分布的；,服务时间也是独立同分布的；,并且独立于输入过程；,排队规则是等

16、待制；,含假定：,顾客到来间隔时间服从参数为 的指数分布，,服务时间服从参数为 的负指数分布，且有隐,按排队论的基本构成特征，来求解该排队模型,(1).基本构成,(i) 顾客到达规律,的主要数量指标：,平均到达率.,表示在 时间到达的顾客数，称为排队系统的输入过程.,其平均值为 ，即单位时间内到达的顾客数为 ，并称为,它服从参数为 的泊松分布，即：,(ii) 服务时间,服务率 .,表示顾客到达间隔时间序列，其,中 表示第n个顾客的到来时刻.,可以证明： 服从参数 为的泊松分布的充,负指数分布.,要条件是到达间隔时间序列 独立同分布且服从,记Z为服务时间，Z服从参数为 的负指数分布：,则 ，即为

17、每个顾客平均服务时间为 ，从,而单位时间内被服务的顾客的平均数为 ，称为平均,(iii) 排队规则,按顾客的到达的先后顺序服务，即先到先服务.,满足以上三个条件的模型在排队论中记为模型,(2).数量特征(只讨论s=1情形),(i) 平均队长,稳态下系统内等待服务的顾客数，其数学期,望称为平均等待队长，即,M/M/s模型，其中s为服务员的个数.,(ii)平均逗留时间和平均等待时间,平均逗留时间为,平均等待时间为,则公式,称为Little公式.,(3). M/M/s 排队模型,(i) 当s=2时 服务强度,平均队长,平均等待时间,(ii) 当s是任意的,服务强度,平均队长,平均等待时间,例1.某医

18、院急诊室同时只能诊治一个病人，诊治时间,服从指数分布，每个病人平均需要15分钟。病人按泊,松分布到达，平均每小时到达3人。试对此排队系统,进行分析.,解,对此排队系统分析如下：, 先确定参数值：这是单服务系统有，,= 3人/h,= 60/15 人/h=4人/h,故服务强度为：, 计算稳态概率：,这就是急诊室空闲的概率，也是病人不必等待立,即就能就诊的概率.,而病人需要等待的概率则为,这也是急诊室繁忙的概率., 计算系统主要工作指标,急诊室内外的病人平均数：,急诊室外排队等待的病人平均数：,病人在急诊室内外平均逗留时间：,病人平均等候时间：, 为使病人平均逗留时间不超过半小时，那么平均,15-1

19、2=3min,即平均服务时间至少应减少3min.,服务时间应减少多少？,由于,平均服务时间为：, 若医院希望候诊的病人90% 以上都能有座位,则,候诊室至少应安置多少座位?,设应该安置个座位,加上急诊室的一个座位,共有+1个。要使90% 以上的候诊病人有座位，,相当于使“来诊的病人数不多于+1个”的概率,不少于90%，即,上式两边取对数,即候诊室至少应安置6个座位.,所以,例2 承接例1，假设医院增强急诊室的服务能力，使,其同时能诊治两个病人，且平均服务率相同，试分析,该系统工作情况，并且，例1、例2的结果进行比较。,解 这相当于增加了一个服务台，故有:,病人必须等候的概率,即系统状态N2的概

20、率：,表6-1 两个系统的比较,2. GI/M/n排队模型,满足下述三个条件的随机服务系统称为GI/M/n排队模型,(1).GI/M/s系统的构成,b. 服务系统由n个并联的服务台所组成.,c.各顾客的服务时间之间是相互独立同分布的，服,是相互独立同分布的随机变量.,务时间与到达间隔时间相互独立,且服务时间的分,a. 顾客到达时刻的间隔,布服从参数为 的负指数分布 .,(2).数量特征,存在且与初始条件无关，其表达式为：,(i) 队长,定理6.1 设 为第m个乘客到达时系统的队长，当,时，队长的分布极限,a. 该系统的平稳分布下的平均队长为,b. 系统的平均队长为,c. 系统服务台平均占有数,

21、其中,(ii) 等待时间,存在且与初始条件无关，其表达式为,令第m个顾客的等待时间为 ，其分布为,定理6.2 对GI/M/n系统，当 时，队长的分布极限,其中 都与定理(6.1)中的一致.,定理6.3 在GI/M/n系统中，设各顾客服务的时间相互独,在平衡状态下，顾客到达是不需要等待的概率为,平均等待时间为,等待的时间内，每台服务设施的输出过程（即服务完成,离开服务机构的顾客）是一个以 为强度的泊松过程.,立且具有公共的以 为参数的负指数分布，则在该顾客,四、模型建立与求解,1. 问题分析,2. 基本假设,3. 模型的建立与求解,1. 问题分析,将公交车的运行看作是提供服务，即服务机构；,将乘

22、客看作顾客，乘客乘坐公交车看作是接受公交,的服务. 公交车运行中乘客的数目描述了系统的状,态，随着时间的变化，一些乘客得到服务后离去，,又有一些新的顾客到来，在人数较多时就要排队等,服务系统，这里拟用排队论来解决该问题.按排队,论的要求，将公交车看作服务机构，乘客看作顾客.,候，而且，顾客到来的时间具有随机性，对顾客的,服务时间也有随机性，所以公交车运行系统是一个,随时间变化的随机动态系统，可以看作一个随机,2. 基本假设,(i). 某站旅客到达为泊松过程,(ii).公交车对每批乘客服务时间为相互独立的负,指数分布，每批服务时间是指公交车从起始站出,乘客到达时间间隔服从参数为 的k阶爱尔兰分布

23、：,发再返回起始站所需的时间为 .,服从参数 为的负指数分布 .,其中 表示运行一个程序的平均时间.,3. 模型的建立与求解,k阶爱尔朗分布的概率密度为：,到达间隔的期望值,公交车服务系统的服务强度为：,以平均等待队长衡量乘客的满意度，系统,以乘客的等待时间在非高峰期不超过10分,服务台的平均占有数衡量公交车公司的利益作,为规划模型的目标 ；,钟，高峰期不超过5分钟，以及车容量在区间,(50,120)作为约束条件，建立随机规划模型 :,约束条件为：,对上述模型求解即可得到公交车调度的一个,完整方案. 至此，利用排队论来建立调度问题的,一个明确、完整的随机规划数学模型，可以利用,一般规划模型的求

24、解方法进行求解 .,再见,三片蛇叶从前有个穷人，穷得连自己的儿子都养不活。儿子便对他说：“好爸爸，我们现在的日子过得太糟了，而我又是你的一个负担。我现在想离开家，看能不能挣到饭吃。”父亲祝福了他，然后悲痛欲绝地送他出了家门。这时候，一个强大帝国的国王正和人打仗，于是他便参加了国王的部队，上前线去打仗。他到达前线时正好赶上激烈的战斗，而且情况非常危急，他的战友们纷纷倒在敌人的弹雨中。当指挥官也牺牲时，剩下的人打算逃跑，可是这位年轻人站出来大着胆子对他们叫道：“我们决不能让自己的祖国灭亡！”于是其他人跟在他的后面，在他的带领下打败了敌人。当国王得知这场胜利全靠他一个人时，就把他提升到最高的位置，给

25、了他许多财富，使他一下子成了全国最显赫的人物。国王有一个女儿，虽长得非常美丽，脾气却非常古怪，她只答应嫁给一个保证在她死后愿意被活埋在她身边的人。“如果这个人真心实意地爱我，”她说，“我死了之后他活着还有什么用？”反过来，她也是一样。如果她丈夫先死，她愿意和他一起被埋进坟墓。她这古怪的誓言吓得人一直不敢向她求婚，可是这位年轻人被公主的美貌迷住了，不顾一切地请求国王把女儿嫁给他。“你知道你要作出什么样的承诺吗？”国王问。“要是我活得比她长，就得为她做陪葬，”他回答，“可是我非常爱她，根本不在乎这种危险。”国王于是便答应了，他们举行了盛大的婚礼。这对年轻人幸福美满地生活了一段时间，妻子便突然得了重

26、病，医生们没有一个能治好她。她死了之后，年轻的丈夫想起了自己的诺言，知道自己得活生生地被关在坟墓里，不由得惊恐万状，可也没有什么别的办法。国王在王宫的各个大门口都派了岗哨，所以他根本不可能逃避这厄运。安葬尸体的那一天，他也被带进了王室的陵墓，然后墓门就被关上了，而且还上了插销。棺材旁有张桌子，上面放着四支蜡烛、四条面包和四瓶酒。等这些东西消耗完后，他就会饿死。他万分痛苦、万分伤心地坐在那里，每天只吃一丁点面包，只喝一口酒，可死神还是一天天地在向他逼近。正当他出神地坐在那里时，他看到一条蛇从墓穴的角落里钻了出来，向死尸爬去。他以为蛇是去咬她的肉，便拔出宝剑说：“只要我还活着，你就休想碰她一下。”

27、说完就把蛇砍成了三段。过了一会儿，又一条蛇从洞里爬了出来。当它看到第一条蛇被砍成了三段，已经死了，它便爬了回去。可不一会儿它又爬了出来，嘴里衔着三片绿色的叶子。然后，它把死蛇的三段拼在一起，在每一处伤口上盖上一片叶子。顷刻之间，那条断蛇的的几个部分又长在了一起。蛇动了几下便活了过来，然后和第二条蛇一起逃走了，而那三片叶子却留在了地上。这位目睹了这一切的不幸青年突然产生了一个想法：不知道这些把死蛇重新救活的叶子的魔力能不能把人也救活。于是，他捡起叶子，在他亡妻的嘴上放了一片，又把另外两片放在她的眼睛上。他刚把叶子放好，血液便开始在她的血管里流动，慢慢涌上了她苍白的脸颊，使它重新变得绯红。接着，她

28、吸了口气，睁开眼睛，说：“啊，上帝，我这是在哪里呀？”“你和我在一起，亲爱的妻子，”他回答，然后把所发生的一切，以及他救活她的经过告诉了她。他给她喝了点酒，又给她吃了点面包。等她重新恢复精力后，他扶她站起来走到墓门口，又是敲门又是叫喊。卫兵们听到后便去报告国王。国王亲自来打开墓门，发现他俩健康而富有活力，不禁为悲伤的事情终于结束而欣喜万分。年轻人把那三片蛇叶带了出来，把它们交给一个侍从，说：“给我小心保管好，要时刻带在身边。天知道我们还会遇到什么麻烦呢？说不定我们还用得着它们呢！”可他的妻子发生了变化，她死而复生之后好像完全失去了对丈夫的爱。过了一段时间，年轻人想过海去看看他的老父亲。他们上船

29、之后，她就忘记了她丈夫对她所表现出的深深的爱和忠诚，也忘记了他对她的救命之恩，可恶地迷上了船长。一天，当年轻人睡着时，她叫来船长，自己抱住丈夫的头，船长抓住他的脚，两个人一起把他扔进了大海。干完了这可耻的勾当之后，她说：“我们现在回去，就说他死在路上了。我会在我父亲的面前大大地夸奖你，赞扬你，使他同意把我嫁给你，并且让你做王位的继承人。”可是那位忠心耿耿的侍从在暗中目睹了一切。他从大船上解下一只小船，坐上去寻找他的主人，不再管那两个坏家伙驶向哪里。他从水里捞起年轻人的尸体，把身上带着的三片蛇叶分别放在他的眼睛和嘴巴上，幸运地救活了他。他俩日夜奋力地划船，小船行驶如飞，结果他们比其他人先回到老国

30、王的王宫。老国王看到他俩独自回来自然感到很惊讶，便问发生了什么事。他听说自己女儿的可恶行径后说：“我不相信她会干出这样卑鄙的事情，但是很快就会真相大白的。”他命令他俩躲进一间密室，不要让任何人看见。不久，大船驶了回来，那个不知羞耻的女人满脸愁容地来见父亲。老国王问：“你怎么独自回来了？你丈夫呢？”“唉，亲爱的父亲，”她回答，“我的心都要碎了。我丈夫在途中突然得病死了，要不是这位好心的船长帮助我，我就惨喽！我丈夫死的时候他也在场，他可以把一切告诉你。”国王说：“我要让死去的人复活！”说着就打开了密室，叫那主仆二人出来。那女人一看见自己的丈夫，就像被雷打了一样跪了下去，请求饶恕。国王说：“绝不能饶恕！他愿意和你一起去死，而且把你救活，可你却趁他睡着时害死他，你是罪有应得。”接着，她和她的帮凶被放在一条凿了洞的船上。船被推到海上，很快就在汹涌的浪涛中沉没了。,