海师大金鹏食堂优化设计研究

1、.PAGE . WORD格式可编辑 专业知识分享 本 科 生 毕 业 论 文 题目：运筹学在现代物流中的应用探究姓 名： 牛亚南 学 号： 201005010278 专 业： 应用数学 年 级： 2010级 学 院：数学与统计学院 完成日期：14年4月10日 指导教师： 王凯华副院长 .本科生毕业论文独创性声明本人声明所呈交的毕业论文是本人在导师指导下进行的研究工作及取得的研究成果,除了文中特别加以标注和致谢的地方外,本论文中没有抄袭他人研究成果和伪造数据等行为 。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。论文作者签名： 日期： 本科生毕业论文使用授权声明X

2、X师范大学有权保留并向国家有关部门或机构送交毕业论文的复印件和磁盘,允许毕业论文被查阅和借阅。本人授权XX师范大学可以将本毕业论文的全部或部分内容编入有关数据库进行检索,可以采用影印、缩印或其他复印手段保存、汇编毕业论文。论文作者签名： 日期： 指导教师签名： 日期： 目录 TOC o 1-3 h z u HYPERLINK l _Toc325448905 1 引言 PAGEREF _Toc325448905 h 1HYPERLINK l _Toc325448906 2 排队论简介 PAGEREF _Toc325448906 h 2HYPERLINK l _Toc325448907 3 模型的

3、建立与分析 PAGEREF _Toc325448907 h 2HYPERLINK l _Toc325448908 3.1 调查数据 PAGEREF _Toc325448908 h 3HYPERLINK l _Toc325448909 3.2 模型假设 PAGEREF _Toc325448909 h 3HYPERLINK l _Toc325448910 3.3 模型建立 PAGEREF _Toc325448910 h 4HYPERLINK l _Toc325448911 3.4 模型求解 PAGEREF _Toc325448911 h 4HYPERLINK l _Toc325448912 3.5

4、 模型分析 PAGEREF _Toc325448912 h 5HYPERLINK l _Toc325448913 3.6窗口数的优化设计 PAGEREF _Toc325448913 h 8HYPERLINK l _Toc325448914 4 结束语 PAGEREF _Toc325448914 h 9HYPERLINK l _Toc325448915 英文摘要 PAGEREF _Toc325448915 h 10HYPERLINK l _Toc325448916 致谢 PAGEREF _Toc325448916 h 10HYPERLINK l _Toc325448917 附录 PAGEREF

5、_Toc325448917 h 11.XX师范大学金鹏食堂排队优化牛亚南摘要：首先,分析调查到的数据,发现学生流符合泊松分布,服务时间符合指数分布,由此模型就变成了排队论中典型的 MMn 模型,根据 MMn 模型中的各效率指标的公式,可得到欣苑食堂拥挤情况的各方面数据。根据模型求解得到的数据,对模型进行了更精确的量化分析。由此发现解决本模型的关键就在于分析顾客平均排队时间,然后对其与窗口数之间的关系进行了拟合,并就两者之间关系进行了灵敏度分析。针对窗口数与顾客平均排队时间之间的关系,再从经济学的角度进行了分析,即比较增加窗口后成本的增加量与减少排队等待时间所带来的收益之间的大小关系,最后得出金

6、鹏食堂设置7个窗口最为合理。关键词：排队论,M/M/s 模型,灵敏度,等待损失1 引言在学校里,常常可以看到这样的情景：下课后,许多同学争先恐后跑向食堂去买饭,小小的卖饭窗口前没过几分钟便排成了长长的队伍,本来空荡荡的食堂也立即变得拥挤不堪。XX农业大学由于近年来学校学生人数的增加,这种现象变得尤为严重。增加窗口数量,减少排队等待时间,是学生十分关心的问题。然而就食堂的角度来说,虽说增加窗口数量可以减少排队等待时间,提高学生对该食堂的满意度,从而赢得更多的学生到该食堂就餐,但是同时也会增加食堂的运营成本,因此如何在这两者之间进行权衡,找到最佳的窗口数量,对学生和食堂双方来说都是很重要的。排队论

7、是通过研究各种服务系统的排队现象,解决服务系统最优设计和最优化控制的一门科学。本论文将根据食堂排队状况建立数学模型,运用排队论的观点进行分析,通过比较各方面因素的关系,为其拥挤状况找到一个较合理的解决方案。2 排队论概述2.1 排队论简介排队queuing是日常生活中经常遇到的现象。如顾客去商店买东西、病人到医院看病等,当售货员、医生等的数量满足不了顾客或病人及时服务的需要时,就出现了排队的现象。出现这样排队的现象,使人感到厌烦,但由于顾客到达人数即顾客到达率和服务时间的随机性,可以说排队现象又是不可避免的。当然增加服务设施如售货员、医生等可以减少排队现象,但这势必会增加投资且因供大于求使设施

8、常常空闲进而导致浪费,所以这通常不是一个最经济的解决办法。作为管理人员来说,就要研究排队问题,把排队时间控制在一定的限度内, 在服务质量的提高和成本的降低之间取得平衡,找到最适当的解。排队论queuing theory,又称随机服务系统理论是通过研究各种服务系统在排队等待现象中的概率特性从而解决服务系统最优设计与最优控制的一门学科,它被广泛的应用于解决诸如电话局占线问题、车站码头机场等交通枢纽的堵塞与 疏导、故障机器的停机待修、水库的存储调节等有形无形的排队问题。2.2 排队论发展概况随机服务系统理论起源于电话系统的研究,从1909年开始,丹麦的电话工程师爱尔朗用概率论方法研究电话通话问题,从

9、而开创了这门应用数学学科,并为这门学科建立许多基本原则,取得了随机服务系统理论最早的成果。他在热力学统计平衡理论的启发下,成功地建立了电话统计平衡模型,并由此得到一组递推状态方程,从而导出著名的Erlang电话损失率公式。1930年以后,当W.Feller引进了生灭过程时,排队论才被数学界承认为一门重要的学科,开始更为一般情形的研究,得到了早期的一些重要结果,1940年前后,开始了对机器管理、陆空交通等方面的应用。在第二次世界大战期间及以后,排队论在运筹学这个新领域中变成了一个重要的内容。1951年以后,理论工作有了新的进展,逐渐奠定了现代随机服务系统理论的基础与此同时,应用的范围也木断扩大；

10、开拓了很多新的应用领域,如存储问题、定货间题、可靠性问题、计数器、计算机性能分析与设计等等。2.3 排队论未来主要研究方向随机服务系统的主要研究方可分三方面：1. 系统的性态问题队长、等待时间和忙期是随机服务系统的三个主要数量指标,对各种系统研究各项数量指标的变化规律,这就是性态研究这是随机服务系统理论最主要的研究方向,绝大部分文献都是属于这一类的。早期的研究集中于系统的平稳性态,五十年代中期以后开始注意到瞬时性态的研究,并遥渐成为研究的焦点。2. 系统的最优化问题最优化问题的研究可以追溯到Erlang的年代,他早已考虑过电话最优线路数的确定,但在六十年代以后才受到了普遍的重视,系统的最优化可

11、以分为设计的最优化和控制的最优化两类。3. 系统的统计问题从历史上看,统计问题的研究是先于性态研究的,但是在随机服务系统理论的发展过程中,统计问题的进展是缓慢的。2.4 排队论的展望1随机服务系统理论中还有很多重要的问题悬而未决或解决得很不彻底,M/G/n等系统的瞬时性态的明显表达式；如各种经典系统的便于计算的渐近公式或近似算法；如复杂的随机服务网络的分析；如用各种简单系统逼近复杂系统的问题；如由输出过程与服务分布来识别输人过程等各种所谓逆问题,等等,这些问题的研究需要耗费人们艰苦的劳动,它们的解决将会大大推动随机服务系统理论的进展。另外,也还有很多问题的研究刚刚开始,如各种最优化问题、统计问

12、题,一这些都是概率统计和运筹学工作者可以充分发挥才能的用武之地。2. 随机服务系统理论与存储论、定货论、可靠性理论之间存在极为密切的关系,相互渗透,相互促进。因此,应该深人研究它们之间在问题提法和处理方法上的共性和特性,探索建立它们的统一理论。3.应该重视随机服务系统理论与计算机科学的数学理论之间的密切联系。计算机有着极其广阔的发展前途,它的严格的数学理论的建立势在必行,目前国际上已普遍予以重视,我们也必须不失时机,大力从事计算机设计与性能分析中的随机服务系统理论与组合数学等研究,为计算机设计的数学理论的奠基工作做出贡献。2.5 多服务台排队系统的数学模型2.5.1 排队论及M/M/s 模型排

13、队论是研究排队系统又称为随机服务系统的数学理论和方法,是运筹学的一个重要分支。在日常生活中,人们会遇到各种各样的排队问题。排队问题的表现形式往往是拥挤现象。排队系统的符号一般形式为：X/Y/Z/A/B/C。其中：X 表示顾客相继到达时问间隔的分布；Y 表示服务时间的分布；Z 表示服务台的个数；A 表示系统的容量,即可容纳的最多顾客数；B 表示顾客源的数目；C 表示服务规则。排队论的基本问题是研究一些数量指标在瞬时或平稳状态下的概率分布及其数字特征,了解系统运行的基本特征；系统数量指标的统计推断和系统的优化问题等。当系统运行一定时间达到平稳状态后,对任一个状态n 来说,单位时间内进入该状态的平均

14、次数和单位时间内离开该状态的平均次数应相等,即系统在统计平衡下流入=流出。据此可得任一状态下的平衡方程如下：0：1：2：n：由上述平衡方程,可求得：平衡状态的分布为：,n=1,21其中：,n=1,22由概率分布的要求：,有：,于是：3注意： 3 式只有当级数收敛时才有意义,即当为系统达到平稳状态后队长N的概率分布,注意到对个数为S的多服务台系统,有：,n= 0,1,2,和,记,则当时,由123式,有其中：公式4和公式5给出了在平衡条件下系统中顾客数为n的概率,当ns时,即系统中顾客数大于或等于服务台个数,这时再来的顾客必须等待,因此记：C=式6称为Erlang等待公式,它给出了顾客到达系统时需

15、要等待的概率。对多服务台等待制排队系统,由已得到的平稳分布可得平均排队长为：记系统中正在接受服务的顾客的平均数为,显然也是正在忙的服务台的平均数,故：式7说明,平均在忙的服务台个数不依赖于服务台个数s,这是一个有趣的结果。由7式,可得到平均队长L 为：L = 平均排队长+正在接受服务的顾客的平均数=对多服务台系统,Little 公式依然成立,即有平均逗留时间W=；平均等待时间 。3 模型的建立与分析由于周六周日学校没课,故学生去食堂的时间较为分散,很少发生排长队的现象,在此就不做分析了。仅就周一至周五的食堂拥挤情况进行分析。经观察发现,一般打到饭的同学都能找到座位吃饭,故可认为,食堂里的座位数

16、是足够的,无需添加新的桌椅。所以解决食堂拥挤状况,主要是解决排长队的问题,此问题建立进行分析。3.1 调查数据统计了从4月19日到4月23日周一到周五11：50至12：55高峰期金鹏食堂的学生流分布情况：共统计了3060人次的数据,见下表：不同时间段学生就餐人流量表11：50至11：55到达人数11：50至11：55到达人数11：50至11：55到达人数11：50至11：55到达人数11：50至11：55到达人数11：50至11：55到达人数周一50951801857428周二451001751806330周三52831951866635周四38931631997039周五7271181206

17、7729总计257442894956350161 表一由概率论的知识可知,若分布满足,则该分布为泊松分布。其中为泊松分布的密度,为泊松分布的参数由上表可得=3.39。经检验,该分布近似于泊松分布。虽然仅仅调查了一周的数据,但考虑到学生到食堂就餐具有较大的稳定性,所以认为调查的数据还是较为可靠的。另外在非高峰时段很少发生排队现象,故在此也不做分析。3.2 模型假设1、由于学校学生多,而食堂少,在中午时段,学生又大都集中在11：50至12：10这一时间段赶去食堂吃饭,故可认为在该时间段中学生源是无限的,且学生单独到来且相互独立。 2、学生对菜色没有特别偏好,每个窗口对学生来说都是一样的。 3、食堂

18、实行先来先服务原则,且学生可自由在队列间进行转移,并总向较短的队进行转移,没有学生会因为队列过长而离去,故可认为排队方式是单一队列等待制。 4、食堂共有6个常用窗口,经观察可发现,每个窗口服务员的工作效率是随机的,很难对其进行精确的分析。所以由一般统计规律,认为其满足指数分布,平均每个学生的服务时间是15秒,且服务员之间无差异。 5、以10秒为一个时间单位。3.3 模型建立基于以上的假设,此次建立的模型符合排队论中的多通道等待模型M/M/n。该模型的特点是：服务系统中有n个服务员,顾客按泊松流来到服务系统,到达强度为；服务员的能力都是,服务时间服从指数分布。当顾客到达时,如果所有服务员都忙着,

19、顾客便参加排队,等待服务,一直等到有服务员为他服务为止。这个系统的效率指标有：顾客到达强度：每个顾客的平均服务时间 ：t服务员能力:系统服务强度,即平均每单位时间中系统可以为顾客服务的时间比例:空闲概率:系统中排队顾客的平均数:L=顾客平均排队时间:W=顾客平均逗留时间：W=W+t系统中顾客的平均数：L=L+3.4 模型求解由调查的数据可知=3.39,t=1.5,n=6,带入以上各式可得：服务员能力,系统服务强度,因为空闲概率：系统中排队顾客的平均数:L=27顾客平均排队时间:W=7.96顾客平均逗留时间：=9.46系统中顾客的平均数：=32.09由此可见,当学生中午在11：40至12：10这

20、个时间段去欣苑食堂吃饭时,一进门就会发现里面已经人满为患,几乎不可能找到空闲的窗口。而且,已经有32个同学正在排队买饭。27个人正在排队等待,平均一个窗口5人。当学生们开始排队时,要过80秒钟才能开始打饭,要过95秒钟才能吃上可口的饭菜。为了检验该数据与事实相符,我特地体验了几次,下表是我的统计数据：统计数据表时间3月19日12：003月20日12：003月21日12：003月22日12：00排队等待人数4546排队等待时间80857075忽略那些随机因素,实验得到的那些结论和实际数据还是较为符合的,可见该模型还是很成功的。3.5 模型分析对学生来说,中午的时间是很有限的11点40下课,14点

21、30上课,能尽快吃上饭对学生来说是很重要的。同时,学生在食堂排队的平均逗留时间W0很大程度上可以决定学生对食堂的选择,所以食堂工作人员也希望能尽可能的满足学生的需求。研究学生平均逗留时间W0,将是解决本模型的关键所在。平均逗留时间W0是由平均排队时间W和平均服务时间t组成。经研究认为15秒的平均服务时间t对于服务员来说已经是极限了,如果再加快速度反而可能手忙脚乱,增大出错的可能性,到时反而会降低效率,故认为平均服务时间t不可改变,是个常数。至于平均排队时间W,由公式可知它是由顾客到达强度,每个顾客的平均服务时间t和窗口数n来决定的,由于学生对于食堂的选择都有一定的偏好,即一般都会去同一个食堂吃

22、饭,所以可以认为学生流是稳定的,即为常数,由上面的分析又可知t也是常数,因此能对平均排队时间构成影响的就只有窗口数n了,下面就n的取值对W的影响进行分析：由matlab可以得到它们两者之间的散点图：注：在上图中把W的单位改成了秒。从图中可看出各点之间的变化规律较为平稳,所以有可能用多次多项式将其拟合,然后又用matlab对其进行了三次多项式的拟合,从而得到了它们的拟合图：拟合图：它们之间的二次多项式关系式是：y=-4.3+112.8x-918.6+2836.6从图中可以看出,随着窗口数的增加,平均排队等待时间急剧减少,当窗口数达到5以后时,变化趋于平缓。从拟合图中,能看出窗口数与平均排队等待时

23、间的大致关系,为了得到更精确的分析,再用灵敏度的观点进行讨论。由于窗口数n只能是整数,所以得到如下表的对应关系：窗口数与排队时间对应关系表单位：秒窗口数n678910平均排队时间W275.231.640.580.21下面分析平均排队时间对窗口数的灵敏度：灵敏度S=由此可得不同的窗口数n下的灵敏度：窗口数对应的的灵敏度表窗口数n678910灵敏度029.1317.5116.4517.62由此可见,平均排队时间W对窗口数十分敏感,均达到了16以上,其中以窗口数从6变成7时尤为明显,其平均排队时间由27秒变为5.23秒。而其他几种情况虽也很敏感,但是平均排队时间变化的绝对值很小,大小不超过4秒钟。3

24、.6 窗口数的优化设计从以上的灵敏度分析可知,当窗口数超过7时,即使增加再多的窗口,其平均排队时间变化的绝对值大小也只在5秒左右,而这么小的时间间隔我们认为对学生是不会造成什么影响的。但是增加窗口会给食堂带来巨大的成本压力,他们自然也不可能增加。至于小于6个窗口时,从图中可看出,平均排队时间会大大增加,这会引起学生的极大不满,造成学生的大量流失,当然也是不合理的。至此可看出,最佳的窗口设置是6个或7个。对于学生方面来说,当然是排队等待时间越短越好,即7个窗口比6个好。对于食堂方面来说,窗口数的增加一方面会导致成本的增加,另一方面会缩短排队时间,即意味着它能为更多学生服务,所以它是否会增加窗口数

25、就取决于成本和收益的大小关系。一般来说,每增加一个窗口,需要多配备三名服务人员以及一些配套的设施。所以增加窗口数所带来的成本等于新增服务人员的工资加上配套设施的维修与清洗费。新增窗口得到的收益是很难估量的。在此引入等待损失的概念,即由于排队等待食堂所减少的收益。如食堂每分钟可得收益a元,但是由于队列过长,顾客不得不排队等待服务,这意味着食堂无法及时为这些顾客服务,每等待1分钟,食堂就损失a元。所以得到等待损失等于食堂单位时间收益乘以平均等待时间乘以顾客数。经调查得知XX市餐饮行业服务人员的每月平均工资为1200元,即每周平均280元。至于配套设施的维修与清洗,经调查认为其每周不超过300元。由

26、此可知每增加一个窗口,食堂的成本就得增加1140元。至于食堂从每个学生身上可获得多少利润,因为学生要的菜不同,而且菜的利润也不同,所以是很难确定的,故由一般规律假定其每十秒钟可得1元利润。所以,学生因等待而使食堂发生的损失,Q=0.33059W,当窗口数从6变为7时,食堂可少损失Q=0.13059W=13059= 6659.44元。由此可知最佳的窗口数为7。至此,得到最终答案,但该模型将学生流完全看作泊松分布存在一定欠缺,学生流并不完全符合泊松分布,处在该模型建模考虑下,将其近似看作泊松分布。同时该模型仅仅考虑学校该食堂自身的问题,并没有结合周围教学楼宿舍的距离,学生对食堂的偏好,以及校内其他

27、食堂对该食堂的影响,存在一定的片面性,故该模型只是近似的得出欣苑食堂的最佳窗口数。学校在建立食堂之初肯定做过更全面细致的调查,该模型得出6个或7个是最佳窗口,此处还是与食堂现状基本吻合的。4 结束语通过对本次论文的设计,使我们进一步掌握了排队论及其相关理论知识,并学会如何将理论运用于实践,从而解决实际生活当中遇到的各种问题。排队论是通过研究由于随机因素而产生的拥挤现象,解决服务系统最优 设计和最优化控制的一门科学。本论文将根据食堂排队状况建立数学模型,运用排队论的观点进行分析,通过比较各方面因素的关系,为其拥挤状况找到了一个较合理的解决方案。根据模型分析,考虑到食堂成本等各个因素从 而得出解决

28、此问题的方法,即通过增加窗口来改善排队等待现象,以减少排队等待时间,从而提高学生对食堂的满意度。排队论作为研究服务系统中排队现象随机规律的学科,如能将其运用于食堂服务系统的规划当中,有重要的实践意义。文章根据排对论的思想建立了食堂的排队服务模型。通过对模型的优化设计,科学地确定了食堂服务的最佳窗口数量,并通过实例说明了该方法的计算过程,证明排队论在食堂服务系统优化中具有实际用途。排队论还可以运用到更为广泛的实际生活中,如火车站排队优化,客服电话排队优化,在考虑到更全面因素的情况下,可以让人们的日常生活更便捷。参考文献1 韩柏棠。管理运筹学,高等教育出版社20092 刘来福,曾文艺。数学模型与数

29、学建模,北京师范大学出版社20023 孙荣恒,李建平,排队论基础,科学出版社,4唐应辉,唐小我,排队论基础与应用,电子科技大学出版社,5Lester Lipsky,Queuing Theory , Springer New York,6Donald Gross, John F. Shortle, Carl M. Harris , Fundamentals of queueing theory ,J. Wiley & Sons, 英文摘要Queueing TheoryGexiangIn general we do not like to wait. But reduction of the wa

30、iting time usually requires extrainvestments. To decide whether or not to invest, it is important to know the e?ect ofthe investment on the waiting time. So we need models and techniques to analyse suchsituations.In this course we treat a number of elementary queueing models. Attention is paidto met

31、hods for the analysis of these models, and also to applications of queueing models.Important application areas of queueing models are production systems, transportation andstocking systems, communication systems and information processing systems. Queueingmodels are particularly useful for the desig

32、n of these system in terms of layout, capacitiesand control.致谢本设计的完成是在我们的导师王凯华老师的细心指导下进行的。在每次设计遇到问题时老师不辞辛苦的讲解才使得我的设计顺利的进行。从设计的选题到资料的搜集直至最后设计的修改的整个过程中,花费了高老师很多的宝贵时间和精力,在此向导师表示衷心地感谢！导师严谨的治学态度,开拓进取的精神和高度的责任心都将使学生受益终生！附录在计算系统中各效率指标和进行拟合时,我们用到了matlab,其程序如下：计算空闲概率P0和系统中排队顾客的平均数L：主程序： a=3.39; b=1.5; n=6 7 8 9 10; p=a*b; P0=f; L=f1;M文件f.m function P0=f for k=1:5 sum=1;a=1; for i=1:n for j=1:i a=a*j; end sum=sum+pi/a; end P0=sum