mpa定量分析方法排队论.ppt

《mpa定量分析方法排队论.ppt》由会员分享，可在线阅读，更多相关《mpa定量分析方法排队论.ppt（80页珍藏版）》请在三一办公上搜索。

1、中国人民大学,MPA定量分析方法,排队论Queuing Theory,3,主讲人简介,杨健（英国兰卡斯特大学管理科学博士）中国人民大学公共管理学院MPA定量分析首席教授公共管理定量分析研究所所长电子政务博士生导师金融信息中心主任投资与证券主编英国运筹学JORS国际顾问国家高技术研究发展计划（863）评审专家国家自然科学基金管理科学评审专家企业年金投资管理机构评审专家,4,内容,一、概述二、等候系统的特征三、单线等候系统的数学模型四、单线等候系统案例五、等候时间的奥妙六、多线等候系统的稳态概率模型七、多线等候系统八、转化状态和截断九、最佳系统设计,5,一、概述,排队论，又称排队论、队论、等候理论

2、和随机服务系统理论，是研究系统拥挤现象和排队现象，旨在决定服务设施最佳设计。排队论的研究将有助在服务机构的设施和顾客的等待服务时间之间取得平衡。从而使高质量低成本的服务和管理得以实现。,6,排队是我们在日常生活中经常遇到的现象。有些排队是有形的，如车站上等待买票的旅客，有些排队是无形，如电话交换机接到的电话呼叫。不论是那一种排队，它们都有着一种共同的要求，就是要求接受某种服务，并且它们的到是随机的。,7,排队论发源于本世纪初。当时美国贝尔电话公司发明了自动电话，以适应日益繁忙的工商业电话通讯需要。这个新发明带来了一个新问题，即通话线路与电话用户呼叫的数量关系应如何妥善解决，这个问题久久未能解决

3、。1909年，丹麦的哥本哈根电话公司A.K.埃尔浪(Erlang)在热力学统计平衡概念的启发下予以解决了。,8,Alexander Graham Bell,Alexander Graham Bell是聋哑教师。他一直在研究一种将声波转换成可见形象的方法。于1876年2月14日获得了电话的专利。他的系统由麦克风和扬声器组成。,9,1876年的液体电话筒,1876年3月10日贝尔就是通过这个话筒实现了电话的第一次通话。其经典名句是贝尔喊出的“瓦特森先生，快来，我需要你帮助。”当时贝尔将话筒中的酸液溅到了。它的收藏者是在俄勒岗贝尔电话大楼的地下室发现的。,10,第二次世界大战期间，排队论逐渐推广到机

4、器维修管理、陆空交通管理等方面。直到1951年以后，才在理论上奠定基础，并在应用方面获利很大的发展。,11,12,服务系统由服务设施和服务对象(统称顾客)构成：,13,目前，排队论不仅应用于工业、工程(如水库)、军事、交通运输、服务性行业等的规划和管理，并促进了可靠性理论、库存论和电子计算机设计的发展。此外，排队论对于随机过程理论作出了很大的贡献，并向物理学提供了思路、概念和方法。排队论有其广泛发展的前景。,14,唐伯虎与排队论,有一次，唐伯虎代一商人写了一副对联：“生意如春意，财源似水源。”那人不满意，说对联要意思明显、容易理解的才好。唐伯虎就重新写了一副：“门前生意，好似夏日蚊虫，队进队出

5、；柜里铜钱，要像冬天虱子，越捉越多。”那商人十分高兴地告别而去。,15,十口心思，思君思国思社稷！八目共赏，赏花赏月赏秋香！,16,二、等候系统的特征,等候系统的形成是由于在某特定时间内，到达服务设施的顾客超过服务设施的服务能量，不能立即得到服务而需排队等候，于是出现了等候线。,17,18,服务系统概述,排队过程的一般表示如下图：,19,服务过程的一般模型，各个顾客由顾客源（总体）出发，到达服务机构前，等待接受服务，服务完了就离开了。,20,排队系统的组成与特征，一般的排队系统都有三个组成部分：（1）输入过程（2）排队规则（3）服务机构,21,（1）输入过程,对顾客的到来应了解其到来的方式，顾

6、客相继到来的时间间隔，可以是确定的，也可以是随机的，顾客的到达可以是相互独立的也可以是有关联的，这些我们称为输入过程。它是一个服务系统启动的依据。我们讨论的是顾客的到来是相互独立的、平稳的随机型的输入过程。这里所谓平稳的是指描述相继到达的间隔时间分布和所含参数（如期望值，方差等）都是与时间无关的。,22,（2）排队规则,排队规则是指排队所遵循的规则，如按顾客对等待的态度可区分为即时制或称损失制（若服务台忙，顾客可立即离去）和等待制。按顾客接受服务规则是接顾客接受服务的次序。例如,先到先服务、后到先服务、随机服务、优先照顾、强占先服务等等，五花八门，不胜枚举。,23,（3）服务机构,这是指服务台

7、的数目，服务台的排列（并列还是串列等见图）以及服务时间，它也可分为确定型和随机型的，和输入过程一样，讨论的是平稳的随机型情形。,24,若按上述排队系统的特征讨论问题，故虑不能太细。因而必须抓住对问题影响最大的三个因素，它们是：1.相继顾客到达的间隔时间分布；2服务时间分布；3.服务台个数。,25,记住定义！,顾客参与等候的那一时刻称为到达时间；从到达时间起到接受服务这一段时间称为等候时间；服务设施提供服务所需的时间称为服务时间；顾客于服务完成后即行离去。顾客从到达到离去的过程构成等候系统。,26,在种种可能形成等候线的情况中，都有某种输入(顾客)来到服务设施接受服务，其到达速率是不规则的随机变

8、量，而且服务时间的长短也是不规则的随机分配。悖论:服务设施服务的容量（capacity）是很难设计：太大了会造成服务设施的闲置和浪费，太小了会造成排队现象或顾客的不满。,27,排队论就是通过分析研究服务对象与服务设施之间的动态关系，获利可靠的数据，借以提供适量的服务设施来适应随机的到达速率，也就是谋求设施闲置的浪费与等候的费用之间的平衡，并控制这两种成本在最低的水平。,28,案例：普鲁士骑兵,29,十九世纪时，巴特开惠茨根据普鲁士骑兵队的统计报告，对十个骑兵连中的骑兵在二十年中被马践踢致死的记录作了分析。这样，他的观察数值有10*20=200个，他作了一个表，列示死亡人数的分布情况。,30,频

9、率分布,31,从这个表里可以看出，死亡事件共 0*109+1*65+2*22+3*3+4*1=122（人次）。平均每连队每年死亡人次为 Ex=122/200=0.61依据POISSON PROCESS 计算其频率：P(X=0)=e-0.61=0.544P(X=1)=0.61e-0.61=0.331P(X=2)=0.612e-0.61/2!=0.101P(X=3)0.613e-0.61/3!=0.021P(X=4)=0.614e-0.61/4!=0.003,32,“对准台湾的弹道导弹的命中率”,据香港媒体报道，大陆军方正通过一家南韩公司，从美国太空图象公司(Space Imaging Co.)驻

10、汉城的分公司，购买台湾地形卫星图片。据悉，“太空图象”在1999年发射的IKONOS卫星所拍摄的地表照片，分辨率在1公尺以内，外传台湾也曾购买过，而公司的发言人布兰德也说，他们在设法拓展亚洲市场，但会遵守美国的法律和规定。巡航导弹采取超低空飞行避开地方的防空火力网，这一能力完全依靠弹载电脑按照非常精确的地形数据操纵飞行高度、速度和方向，而高清晰度星照片正是精确地形数据的唯一来源。购买美国间谍卫星拍摄的高清晰度台湾地形照片，相信是要用来提高短程弹道导弹和巡航导弹的命中率。,33,案例：“太空图象”,34,三、单线等候系统的数学模型,现在，先建立一个最简单明了的、仅有一个服务设施的等候系统的数学模

11、型，要求能够预测：(1)任何时刻系统内顾客不同人数的概率；(2)顾客在系统内平均所花费的时间；(3)服务设施闲置概率，或闲置时间。,35,The Exponential Distribution,f（t）=exp（-t）,36,为了便于构模起见，现作如下的假定：到达来源是有限的，服务每次限于一人；排队纪律是先到先服务；一个顾客得到服务以后另一个顾客立即进入服务设施；顾客的到达每单位时间为平均人且服从指数分布，即 f（t）=exp（-t），其中t 代表时刻，服务设施每单位时间平均服务人(即单位时间内离开服务设施的人数)。,37,我们分析如下：代表单位时间内顾客到达的平均人数(即两次到达平均间隔时

12、间的倒数)代表单位时间内顾客离去的平均人数，在服务设施连续工作的情况下，单位时间内的服务能力=/代表服务因子若1(即单位时间内到达的人数超过离去的人数)，可以预期队伍逐渐形成并且越来越长。反之，如果1(即到达人数少于离去人数)，则排队情况必将逐步改善，甚至根本不必排队。,38,100人服务系统,现假定：有100人这样的服务系统在0时点同时开始服务，没有人排队。后来在每一个系统中，顾客有到达的也有离去的，队伍逐渐形成并且扩大。除个别例外外，没有两个系统有相同的到达一离去情况。,39,1000小时后的真实状况,40,从表中的数字可以看出，在一段相当长的时间以后，虽然某一个系统内的人数可能有较大的波

13、动，但100个系统的平均人数和设施闲置百分率却变化甚小。同时，任一个系统中有0、1、2、n、个顾客的概率也变化极小。过了一段相当长时间以后，这个概率趋于稳定。,41,令n代表某一系统中的顾客人数(称为该系统的状态)pn(t)代表给定时刻t系统内有n个顾客的概率(称为状态概率)，pn代表过了相当长时间以后，状态概率波动极小而趋于稳定时的概率(称为稳态概率)。pn(t)与pn之间的关系是 lim pn(t)=pn这里，pn(t)与时间相关，pn与时间不相关。,42,可以想象，在相当长时间以后，系统内有n个顾客的概率波动极微，即 lim pn(t)=0数学推导(从略)可得p0=1-(1)pn=n(1

14、-)n=0,1,2,(2)由此可见，稳态概率只和服务因子相关，而与和的绝对值不相关。,43,从式(1)和(2)还可导出(从略)：系统闲置的概率为1-(3)服务设施的利用率为(4)系统内顾客的平均人数为T=/(-)=/(1-)(5)等候线上的平均人数为Q=2/(1)(6)系统内顾客花费的平均时间为1/()(7)顾客在等候线上的平均时间为/()(8),44,四、单线等候系统案例,某医院急诊室每24小时内平均有96名病人就诊。每一病人需10分钟的紧张抢救。医院的设备一次仅能处理一个病人。,45,该医院的排队程度可描述如下：到达率：=96/24=4人/小时服务率：=1/1060=6人/小时服务因子：=

15、/=4/6=2/3平均稠密度(顾客平均人数)：T=/(1-)=2人正在抢救中的平均病人数：S=2/3人排队等候的平均病人数：Q=T-S=4/3人没有病人的时间比例：p0=1-=1/3,46,根据上述情况，平均有4/3个病人必须排队等候抢救。为了建设和谐社会，这种状况是不能令人满意的。但是，任何改善方案都涉及到经费开支。管理目标：现在希望平均等候人数能从4/3人减少到1/2人，问预算将受到何等的影响？,47,公众抗议：人不如狗！,48,如果你是院长，如何改善服务质量？经过调查得出下面的参数和提高效果的措施：假定按目前医疗水平，平均每10分钟抢救一例病人的情况，院方每起需支出100元；倘欲缩短时间

16、，每一例缩短1分钟需多支出10元。,49,新目标是使排队等候的平均病人数变成Q=2/(1)=1/2解方程，得服务因子=1/2我们将达到这个目的所需的服务因子=1/2 代入=/=4/（1/2）=8 人/小时故平均抢救时间=1/小时=7.5分钟，即比原来缩短2.5分钟。每一起需多支出25元，每天多出2596=2400元。,50,但是，没有病人的时间部分为p0=1=11/2=50%，换言之，除了增加开支之外，设备闲置率也提高了 1/21/3=1/6=16.7%。,51,五、等候时间的奥妙,在许多场合，服务系统的主要关键不仅在于顾客排队的人数，还在于顾客耗费于排队的时间。关于这个问题，有以下两个经营效

17、率的衡量尺度：(1)每一顾客的平均等候时间；(2)每一个必须等候的顾客平均等候时间。这两个尺度是不同的，因为有一部分顾客在到达的时刻，队伍是空的，不需要等候！,52,当一个顾客进入系统的时候，已经有些人在排队，后到的人必须在先到的人受理之后才能轮到。由于先到的顾客被服务的时间与队伍长度不相关，又由于 那个时刻对被受理的顾客的服务时间和系统中人数不相关(因服从泊哇松分布)，系统中的人数每人服务时间的平均=系统中平均人数平均服务时间。令 W 代表每一顾客的平均等候时间，则 W=T/,53,例如，上述急救室中每一病人的平均等候时间W=系统中2人(平均)/6人/小时(服务率)=20分钟这个平均等候时间

18、也包括那些不需等候的病人在内。假设W*代表必须等候的病人的平均等候时间，根据数学推导(从略)W*=W/则急诊室的案例中，必须等候的病人的平均等候时间为 W*=20/(2/3)=30分钟,54,“安全因素”,在许多场合，经营效率的“安全因素”措施很重要。,55,例如，上述的急诊室，院方为了把两个或两个以上病人同时在系统中(一个在抢救，其他在等候！)的机会控制在指定的水平(例如10%以下)，应如何确定服务因子？为了达到这个目标，可从下列公式求：,56,1(p0+p1)0.101(1)+(1)0.10求解得2=0.10 服务因子 0.316已知到达率为4人/小时=/12.6 人/小时即，平均抢救时间

19、约为4.7分/人。,57,多线等候?让我想一想！,58,单通道和多通道服务系统,59,六、多线等候系统的稳态概率模型,假设：k 代表服务线数 代表进入系统的的到达率 代表每一服务线的服务率=/代表每一服务线的服务因子*=/k代表整个系统的服务因子,60,根据数学推导(从略)，稳态概率的方程式是：,61,七、多线等候系统,“精兵简政”某政府机构/商店有官员/职员4名，经过统计分析每人平均6分钟可接待一位来访者,平均每3分钟有一个来访者到达。,62,则此排队模型的基本参数是：服务线数：k=4到达率：=20 人/小时服务率(每线)：=10 人/小时服务因子(每线)：/=2整个系统的服务因子：*=/k

20、=1/2,63,该店顾客的平均人数T可计算如下：T 0p0+1p1+2p2+3p3+00.13+10.26+20.26+30.18+1.92 人等候接待的顾客的平均人数Q 1p5+2p6+0.045+0.045+0.17 人,64,由此可见，正在被服务的顾客人数STQ1.75人每一顾客的平均等候时间W0（p0+p3）+（1/）p4+（1/）p5+0.10.09+0.20.045+0.037小时（2.22分钟）,65,必须等候的顾客平均等候时间为W*W/1-（p0+p1+p2+p3）2.22/0.17 13.1 分钟这一等候系统运算参数在这类应用中是很重要的。因为顾客会因不耐久候而到别家铺子去，

21、以致营业受到损失。,66,机构改革分析,在许多场合，作业分析（OR）是在商店/政府机关正式对外办公/开张和选择职员确定之前已要考虑。作为全局决策过程的一个侧面，在上述例子中，假定有三个可能的方案可供权衡：（1）保留原有四名职员；（2）换成能力加倍的两名职员；（3）换成能力减半的八名职员。你的意见如何？,67,则第二个排队模型的基本参数是服务线数：k2到达率：20人/小时服务率（每线）：20人/小时服务因子（每线）：/1整个系统服务因子：*/k1/2,68,那么，稳态概率可计算如下：p1=p0=10.33=0.33p2=(/2)p1=1/20.33=0.17p3=(/2)p2=(1/2)0.17

22、=0.08p4=(/2)p3=(1/2)0.08=0.04,69,商店里顾客的平均数可计算为T=00.33+10.33+20.17+=1.36 人等候接待的顾客的平均人数将是Q=1p2+2p3+3p4+=0.17+0.17+0.12+=0.67 人,70,虽然，总的拥挤情况好了一些，但顾客等候的平均人数却有所增加。每一顾客平均等候时间W=0(p0+p1)+(1/)p2+(2/)p3+=0.050.17+0.100.08+0.150.04+=0.043小时（2.6分钟）比“4线服务系统”增加了20%。,71,但是，必须等候的顾客平均等候时间是W*=W/1-(p0+p1)=2.0/0.33=6.0

23、分钟分析:这比“4线服务系统”大大缩短了。虽然，一个顾客在“2线服务系统”中有更多的等候机会，但是他的平均等候时间却可缩短一半以上（6.0分钟比13.1分钟！）。,72,以上两种方案可供选择，是以各个运算参数作为经济分析和经理部门决策性评价的依据。而这种决定在很大程度上取决于有经验的营业员的工资比没有经验的营业员的工资大多少，整个拥挤情况改善后的利弊，必须等候的顾客的等候时间，等等因素。,73,八、转化状态和截断,上述单线等候系统的限制条件是稳定状态，而且在任何时候顾客的平均人数是固定的。但是，在现实情况中，这些条件不是普遍存在的。例如，新设备的使用，新产品的推销等，则都是属于转化状态。有的系

24、统虽然经过很长的时间以后，也永远不能达到稳定状态。,74,另外，上述各例都是当服务设施忙碌时，顾客平均到达率小于设施的平均服务率(即时，时间长久以后，理论上系统内顾客人数似乎会变成无穷大，而实际上，等候线到了一定的长度不可能再扩大，因为顾客是不耐久候的，也就是说，系统会被截断。因此，即使，等候系统仍可以是稳定状态的。,75,九、最佳系统设计,大多数等候系统都比上述等候系统模型复杂得多。服务规则也可能不是先到达先服务。当等候线过长时，顾客可能另到别的服务设施去，等等。等候系统既然如此复杂，要试图用分析模型预测实际系统的行为几乎是不可能的。,76,服务对象种类繁多，到达的来源有有限和无穷之别，到达

25、时间的分布和间隔各不相同，服务线有多有少，服务的方法、内容和时间互不一致。,77,有了模拟法和电子计算机，就可以对实际等候系统中的很多程序加以模拟，研究任何复杂的等候系统的行为。,78,丘成桐的故事：Akamai Technologies公司是丘成桐的朋友F.Thomson Leighton开办的。Akamai公司目标业务是提供网络交通的解决方案。Akamai运用了排队论（Queuing Theory）和图论（Graph Theory）的原理，透过建立一个有效的数学模型，以寻求网络上的可行路径及最短路径。,79,由于网络用户对缓解网络交通需求殷切，该公司成立之日，IPO超额5倍，由26美元的招股价，在当天急升至145美元。该公司的市值曾一度是香港国际机场的总值的1.5倍之多。Akamai的成功证明了，数学家也有强劲的市场升值力。,80,联系方式,地址：北京市海淀区万柳东路11号万泉新新家园12-1-901（100089）电话：010-82551227/28；传真：010-82551226 邮件：,