安徽农业大学食堂排队优化与统计.doc

安 徽 农 业 大 学毕 业 论 文（设计）论文题目 安徽农业大学欣苑食堂排队模型统计与优化 姓 名 葛 翔 学 号 08141012 院 系 信息与计算机学院 专 业 物流工程 指导教师 高羽佳 职 称 讲师 中国合肥二零一二 年 五 月安徽农业大学毕业论文（设计）任务书论文（设计）题目 安徽农业大学欣苑食堂 排队模型统计与优化 院系名称 信息与计算机学院 专业（班级） 08物流工程1班 学生姓名 葛翔 学 号 08141012 指导教师 高羽佳 下发任务书日期 2011年12月 20日一、毕业论文（设计）的主要内容1.排队模型基本理论的介绍与排队论的现状。2.收集安徽农业大学欣苑食堂排队模型的数据。3.针对安徽农业大学欣苑食堂具体问题建立排队模型。 4.根据所列模型及搜集的数据进行统计分析。二、毕业论文（设计）的基本要求1. 按进度计划完成毕业论文（设计）的撰写（研究）；2. 通过相关资料的查阅与研究完成项目的制作；3. 论文撰写应符合学术论文的格式要求；4. 要求参加论文答辩并要求通过；5. 文责自负，严禁抄袭。三、应收集的资料及主要参考文献 1 韩柏棠。管理运筹学(M)，高等教育出版社（2009）2 刘来福，曾文艺。数学模型与数学建模(M)，北京师范大学出版社（2002）3 孙荣恒,李建平,排队论基础(M),科学出版社,(2002)4唐应辉,唐小我,排队论基础与应用(M),电子科技大学出版社,(2000)5 Lester Lipsky, Queuing Theory (M), Springer New York, (2009)6 Donald Gross, John F. Shortle, Carl M. Harris , Fundamentals of queueing theory (M), J. Wiley & Sons, (2008)四、毕业论文（设计）进度计划起讫时间工作内容备注2011年11月至2012年2月2012年3月2012年3月至2012年4月2012年4月至2012年5月中2012年5月底计划论文方向并收集资料实地调查数据撰写论文修改论文定稿并准备答辩安徽农业大学学士学位论文（设计）开题报告课题名称安徽农业大学欣苑食堂排队模型统计与优化课题来源导师指定学生姓名葛翔专业物流工程学号08141012指导教师姓名高羽佳职称讲师研究内容1. 排队模型基本理论的介绍与排队论的现状。2. 收集安徽农业大学欣苑食堂排队模型的数据。3. 针对安徽农业大学欣苑食堂具体问题建立排队模型。4. 根据所列模型及搜集的数据进行统计分析。研究计划2011年11月至2012年2月 计划论文方向并收集资料2012年3月 实地调查数据2012年3月至2012年4月 撰写论文2012年4月至2012年5月中 修改论文2012年5月底 定稿并准备答辩特色与创新1. 统计推断，根据资料建立模型；2. 对系统进行优化，能正确设计和有效运行各个服务系统，使之发挥最佳效益。指导教师意见教研室意见学院意见目录1 引言12 排队论概述22.1 排队论简介22.2 排队论发展概况22.3 排队论主要研究方向32.4 排队论的展望32.5 多服务台排队系统的数学模型42.5.1 排队论及M/M/s 模型42.5.2 M/M/s 等待制多服务台模型53 模型的建立与分析63.1 调查数据63.2 模型假设73.3 模型建立73.4 模型求解83.5 模型分析83.6 窗口数的优化设计114 结束语12参考文献12英文摘要13致谢13附录14安徽农业大学欣苑食堂排队模型统计与优化学生：葛翔 导师：高羽佳(安徽农业大学 信息与计算机学院 合肥 230036)摘要：近年来，随着大学不断扩招，大学在校学生人数不断增加，学生食堂用餐排队拥挤现象也日益严重。排队论的理论和方法已经广泛应用于各种服务系统，如通信系统、交通系统、计算机存储系统、生产管理系统等。目前很多服务机构的的排队系统利用排队论知识对其排队系统建立数学模型并进行分析优化，从而可使系统达到最佳的运营状态，具有十分重要的经济价值和实际意义。本论文从安徽农业大学欣苑食堂数据的统计调研入手，建立了食堂学生排队的数学模型，并运用排队论的方法进行分析。通过比较各方面因素的关系，在窗口数量、投入成本、收益和学生排队等待时间上找到一个合理的解决方案。通过对优化方案在可行性上的分析，该方案为安徽农业大学欣苑食堂以后的改进提供了理论指导。关键词：排队论，M/M/s 模型，灵敏度，等待损失1 引言在学校里，常常可以看到这样的情景：下课后，许多同学争先恐后跑向食堂去买饭，小小的卖饭窗口前没过几分钟便排成了长长的队伍，本来空荡荡的食堂也立即变得拥挤不堪。安徽农业大学由于近年来学校学生人数的增加，这种现象变得尤为严重。增加窗口数量，减少排队等待时间，是学生十分关心的问题。然而就食堂的角度来说，虽说增加窗口数量可以减少排队等待时间，提高学生对该食堂的满意度，从而赢得更多的学生到该食堂就餐，但是同时也会增加食堂的运营成本，因此如何在这两者之间进行权衡，找到最佳的窗口数量，对学生和食堂双方来说都是很重要的。排队论是研究服务系统因“需求”拥挤而产生等待行列(即排队)的现象，以及合理协调“需求”与“服务”关系的一种数学理论，是运筹学中以概率论为基础的一门重要分支，亦称“随机服务系统理论”。是通过研究各种服务系统的排队现象，解决服务系统最优设计和最优化控制的一门科学。2 排队论概述2.1 排队论简介排队（queuing）是日常生活中经常遇到的现象。如顾客去商店买东西、病人到医院看病等，当售货员、医生等的数量满足不了顾客或病人及时服务的需要时，就出现了排队的现象。出现这样排队的现象，使人感到厌烦，但由于顾客到达人数（即顾客到达率）和服务时间的随机性，可以说排队现象又是不可避免的。当然增加服务设施（如售货员、医生等）可以减少排队现象，但这势必会增加投资且因供大于求使设施常常空闲进而导致浪费，所以这通常不是一个最经济的解决办法。作为管理人员来说，就要研究排队问题，把排队时间控制在一定的限度内， 在服务质量的提高和成本的降低之间取得平衡，找到最适当的解。排队论（queuing theory，又称随机服务系统理论）是通过研究各种服务系统在排队等待现象中的概率特性从而解决服务系统最优设计与最优控制的一门学科，它被广泛的应用于解决诸如电话局占线问题、车站码头机场等交通枢纽的堵塞与 疏导、故障机器的停机待修、水库的存储调节等有形无形的排队问题。2.2 排队论发展概况随机服务系统理论起源于电话系统的研究，从1909年开始，丹麦的电话工程师爱尔朗用概率论方法研究电话通话问题，从而开创了这门应用数学学科，并为这门学科建立许多基本原则，取得了随机服务系统理论最早的成果。他在热力学统计平衡理论的启发下，成功地建立了电话统计平衡模型，并由此得到一组递推状态方程，从而导出著名的Erlang电话损失率公式。1930年以后，当W.Feller引进了生灭过程时，排队论才被数学界承认为一门重要的学科，开始更为一般情形的研究，得到了早期的一些重要结果，1940年前后，开始了对机器管理、陆空交通等方面的应用。在第二次世界大战期间及以后，排队论在运筹学这个新领域中变成了一个重要的内容。1951年以后，理论工作有了新的进展，逐渐奠定了现代随机服务系统理论的基础与此同时，应用的范围也木断扩大；开拓了很多新的应用领域，如存储(水库)问题、定货间题、可靠性问题、计数器、计算机性能分析与设计等等。2.3 排队论主要研究方向随机服务系统的主要研究方“可分”三方面：1. 系统的性态问题队长、等待时间和忙期是随机服务系统的三个主要数量指标，对各种系统研究各项数量指标的变化规律，这就是性态研究这是随机服务系统理论最主要的研究方向，绝大部分文献都是属于这一类的。早期的研究集中于系统的平稳性态(极限性态)，五十年代中期以后开始注意到瞬时性态的研究，并遥渐成为研究的焦点。2. 系统的最优化问题最优化问题的研究可以追溯到Erlang的年代，他早已考虑过电话最优线路数的确定，但在六十年代以后才受到了普遍的重视，系统的最优化可以分为设计的(静态的)最优化和控制的(动态的)最优化两类。3. 系统的统计问题从历史上看，统计问题的研究是先于性态研究的，但是在随机服务系统理论的发展过程中，统计问题的进展是缓慢的。2.4 排队论的展望1随机服务系统理论中还有很多重要的问题悬而未决或解决得很不彻底，M/G/n等系统的瞬时性态的明显表达式；如各种经典系统的便于计算的渐近公式或近似算法；如复杂的随机服务网络的分析；如用各种简单系统逼近复杂系统的问题；如由输出过程与服务分布来识别输人过程等各种所谓逆问题，等等，这些问题的研究需要耗费人们艰苦的劳动，它们的解决将会大大推动随机服务系统理论的进展。另外，也还有很多问题的研究刚刚开始，如各种最优化问题、统计问题，一这些都是概率统计和运筹学工作者可以充分发挥才能的用武之地。2. 随机服务系统理论与存储论、定货论、可靠性理论之间存在极为密切的关系，相互渗透，相互促进。因此，应该深人研究它们之间在问题提法和处理方法上的共性和特性，探索建立它们的统一理论。3. 应该重视随机服务系统理论与计算机科学的数学理论之间的密切联系。计算机有着极其广阔的发展前途，它的严格的数学理论的建立势在必行，目前国际上已普遍予以重视，我们也必须不失时机，大力从事计算机设计与性能分析中的随机服务系统理论与组合数学等研究，为计算机设计的数学理论的奠基工作做出贡献。2.5 多服务台排队系统的数学模型2.5.1 排队论及M/M/s 模型排队论是研究排队系统（又称为随机服务系统）的数学理论和方法，是运筹学的一个重要分支。在日常生活中，人们会遇到各种各样的排队问题。排队问题的表现形式往往是拥挤现象。排队系统的符号一般形式为：X/Y/Z/A/B/C。其中：X 表示顾客相继到达时问间隔的分布；Y 表示服务时间的分布；Z 表示服务台的个数；A 表示系统的容量，即可容纳的最多顾客数；B 表示顾客源的数目；C 表示服务规则。排队论的基本问题是研究一些数量指标在瞬时或平稳状态下的概率分布及其数字特征，了解系统运行的基本特征；系统数量指标的统计推断和系统的优化问题等。当系统运行一定时间达到平稳状态后，对任一个状态n 来说，单位时间内进入该状态的平均次数和单位时间内离开该状态的平均次数应相等，即系统在统计平衡下“流入=流出”。据此可得任一状态下的平衡方程如下：0：1p1=0p01：0p0+2p2=(1+1)p12： 1p1+3p3=(2+2)p2n： n-1pn-1+n+1pn+1=(n+n)pn由上述平衡方程，可求得平衡状态的分布为：pn=Cnp0，n=1,2（1）其中：Cn=n-1n-2。0nn-1。1，n=1,2（2）由概率分布的要求：n=0pn=1，有：1+n=0Cnp0=1，于是：p0=11+n=0Cn（3）注意：（3）式只有当级数n=0Cn收敛时才有意义， 即当n=0Cn时，才能由上述公式得到平稳状态的概率分布。2.5.2 M/M/s 等待制多服务台模型设顾客单个到达，相继到达的时间间隔服从参数为的指数分布，系统中共有S个服务员，每个服务台的服务时间相互独立，且服从参数为的指数分布。当顾客到达时，若有空闲的服务台则可以马上接受服务，否则便排成一个队列等待，等待空间为无限。下面讨论这个排队系统的平稳分布。记：p=pN=n（n= 0,1,2)为系统达到平稳状态后队长N的概率分布，注意到对个数为S的多服务台系统，有：n=，n= 0,1,2，和n n=0,1,2ss n=s,s+1,，记s=s=s，则当1时，由（1）（2）（3）式，有pn=1n!np0 n=1,s1s!sn-snp0 ns (4)其中：p0=i=0nii!+n+1n!n-1 (5)公式（4）和公式（5）给出了在平衡条件下系统中顾客数为n的概率，当ns时，即系统中顾客数大于或等于服务台个数，这时再来的顾客必须等待，因此记：C(s,)=n=1npn=ss!(1-s)p0 (6)式（6）称为Erlang等待公式，它给出了顾客到达系统时需要等待的概率。对多服务台等待制排队系统，由已得到的平稳分布可得平均排队长Lq为：Lq=n=s+1(n-s)pn=p0sss!(1-s)2记系统中正在接受服务的顾客的数为s，显然s也是正在忙的服务台的平均数，故：s=n=0s-1npn+sn=spn=p0n=1s-1n-1n-1!+s-1s-1!(1-s)= (7)式（7）说明，平均在忙的服务台个数不依赖于服务台个数s，这是一个有趣的结果。由（7）式，可得到平均队长L 为：L = 平均排队长+正在接受服务的顾客的平均数=Lq+对多服务台系统，Little公式仍成立，即平均逗留时间W=L；平均等待时间Wq=W-1 。3 模型的建立与分析由于周六周日学校没课，故学生去食堂的时间较为分散，很少发生排长队的现象，在此就不做分析了。仅就周一至周五的食堂拥挤情况进行分析。经观察发现，一般打到饭的同学都能找到座位吃饭，故可认为，食堂里的座位数是足够的，无需添加新的桌椅。所以解决食堂拥挤状况，主要是解决排长队的问题，此问题建立进行分析。3.1 调查数据统计了从3月19日到3月23日（周一到周五）11：40至12：10高峰期欣苑食堂的学生流分布情况：共统计了3060人次的数据，见下表：表3-1 不同时间段学生就餐人流量表11：40至11：45到达人数11：40至11：45到达人数11：40至11：45到达人数11：40至11：45到达人数11：40至11：45到达人数11：40至11：45到达人数周一50951801857428周二451001751806330周三52831951866635周四38931631997039周五72711812067729总计257442894956350161由泊松分布定义可知，若分布满足pkpk-1=k，则该分布为泊松分布。由上表可得=3.39。经检验，该分布近似于泊松分布。（其中pk为泊松分布的密度，为泊松分布的参数）虽然仅仅调查了一周的数据，但考虑到学生到食堂就餐具有较大的稳定性，所以认为调查的数据还是较为可靠的。另外在非高峰时段很少发生排队现象，故在此也不做分析。3.2 模型假设1、由于学校学生多，而食堂少，在中午时段，学生又大都集中在11：40至12：10这一时间段赶去食堂吃饭，故可认为在该时间段中学生源是无限的，且学生单独到来且相互独立。 2、学生对菜色没有特别偏好，每个窗口对学生来说都是一样的。 3、食堂实行先来先服务原则，且学生可自由在队列间进行转移，并总向较短的队进行转移，没有学生会因为队列过长而离去，故可认为排队方式是单一队列等待制。 4、食堂共有6个窗口，经观察可发现，每个窗口服务员的工作效率是随机的，很难对其进行精确的分析。所以由一般统计规律，认为其满足指数分布，平均每个学生的服务时间是15秒，且服务员之间无差异。 5、以10秒为一个时间单位。3.3 模型建立基于以上的假设，此次建立的模型符合排队论中的多通道等待模型（M/M/n）。该模型的特点是：服务系统中有n个服务员，顾客按泊松流来到服务系统，到达强度为；服务员的能力都是，服务时间服从指数分布。当顾客到达时，如果所有服务员都忙着，顾客便参加排队，等待服务，一直等到有服务员为他服务为止。这个系统的效率指标有： 顾客到达