数学建模-食堂排队问题

数学建模论文——食堂排队问题指导老师：党建利小组成员:姓名学号李晟源200807010409自己闲来无事做的，仅供参考！[摘要]通过应用排队论，为食堂窗口服务工作构建相应的定量模型，为节约学生排队就餐时间，提高食堂服务质量，效率，以及平衡学生排队时间与食堂收益之间的关系，优化食堂资源配置提供一种较有效的管理决策手段。[关键词]排队论；M/M/s模型；灵敏度；等待损失1.引言在学校里，常常可以看到这样的情况：下课后，许多同学正想跑到食堂买饭，小小的买饭窗口前没过几分钟便排成了长长的队伍，本来空荡荡的食堂立即变得拥挤不堪。饥肠辘辘的学生门见到这种长蛇阵，怎能不怨声载道。增加窗口数量，减少排队等待时间，是学生们十分关心的问题。然而就食堂的角度来说，虽说增加窗口数量可以减少排队等待时间，提高学生对该食堂的满意度，从而赢得更多的学生到该食堂就餐，但是同时也会增加食堂的运营成本，因此如何在这两者之间权衡，找到最佳的窗口数量，对学生和食堂双方来说都是很重要的。排队论是通过研究各种服务系统的排队现象，解决服务系统最优设计和最优化控制的一门科学。本文将根据食堂排队状况建立数学模型，运用排队论的观点进行分析，通过比较各方面因素的关系，为其拥挤状况找到一个较合理的解决方案。2.多服务台排队系统的数学模型2.1排队论及M/M/s模型。排队论是研究排队系统(又称为随即服务系统)的数学理论和方法，是运筹学的一个重要分支。在日常生活中，人们会遇到各种各样的排队问题。排队问题的表现形式往往是拥挤现象。排队系统的一般形式符号为：X/Y/Z/A/B/C。其中：X表示顾客相继到达时间间隔的分布；Y表示服务时间的分布；Z表示服务台的个数；A表示系统的容量，即可容纳的最多顾客数；B表示顾客源的数目；C表示服务规则。排队论的基本问题是研究一些数量指标在瞬时或平稳状态下的概率分布及其数字特征，了解系统运行的基本特征；系统数量指标的统计推断和系统的优化问题等。当系统运行一定时间达到平稳后，对任一状态n来说，单位时间内进入该状态的平均次数和单位时间内离开该状态的平均次数应相等，即系统在统计平衡下“流入=流出”。据此，可得任一状态下的平衡方程如下：由上述平衡方程，可求的：平衡状态的分布为：)1(,2,1,0npCpnn其中：)2(,2,1,11021nCnnnnn有概率分布的要求：10nnp，有：1100pCnn，则有：)3(1100nnCp注意：（3）式只有当级数onnC收敛时才有意义，即当onnC时才能由上述公式得到平稳状态的概率分布。2.2M/M/s等待制多服务台模型。设顾客单个到达，相继到达的时间间隔服从参数为的指数分布，系统中具有S个服务员，每个服务台的服务时间相互独立，且服从参数为的指数分布。当顾客到达时，若有空闲的服务台则可以马上接受服务，否则便排成一个队列等待，等待空间为无限。下面讨论这个排队系统的平稳分布：即nNpp),2,1,0(n为系统达到平稳状态后队长N的概率分布，注意到对个数为S的多服务台系统，有：,2,1,0,nn，和,1,,2,1,0ssnsnnn，即：sspps，则当P1时，由(1)式，(2)式，(3)式，得：snpsssnpnpnsnnn00!1)4(,,2,1!1其中：)5(!!1100nnipnnii公式(4)和公式(5)给出了在平和条件下系统中顾客数为n的概率，当sn时，即系统中顾客数大于或等于服务台的个数，这时来的顾客必须等待，因此即：)6(1,01pspscssnn！(6)式成为Erlang等待公式，它给出了顾客到达系统是需要等待的概率。对多服务台等待制排队系统，由已得到的平稳分布可得平均排队长qL为：2010011!!!sssnnssssnssnsnsnqspddspsnsppsnL记系统中正在接受服务的顾客的平均数为s，显然s也是正在忙的服务台的平均数，故：(7)式说明平均在忙的服务台个数不依赖于服务台个数S，这时一个特殊的结果。由(7)式，可得到平均队长L为：L=平均排队长+正在接受服务的顾客的平均数qL对多服务台系统，Little公式依然成立。即有平均逗留时间LW;平均等待时间1WLWqq。3.实例分析3.1模型假说3.1.1假定学生在高峰期这段时间达到的人数是无限的，并且一次以参数的泊松过程达到，达到的时间间隔是随机的，服从负指数分布。3.1.2每个服务窗口以并联的方式连接，且每个窗口对学生来说都是一样的，服务时间服从参数为的负指数分布。3.1.3食堂实行先来先服务原则，且学生可自由在队列间进行转移，并总向最短的对转移，没有学生会因为队列过长而离去，故可认为排队方式是单一队列等待制。由于周六周日学生没课，故学生去食堂的时间较为分散，很少发生排长队的现象，我们在此不做详细的分析了，我们仅就周一到周五的食堂拥挤情况进行分析。进我的同学观察发现，一般打到饭的同学都能找到座位吃饭，故我们可认为，食堂的可容纳学生数是足够的，所以解决食堂的拥挤现象，主要是解决排长队与服务窗口的问题。我的同学统计了从某周一到周五11:45到12:15高峰期食堂的学生流分布情况：共统计了3059人次的数据(以10秒为一个单位)，见下表：表一每10秒到达人数123457频数257441894956350161由概率论的知识可知，若分布满足kppkk1，则该分布为泊松分布。(其中kp为泊松分布的密度，为泊松分布的参数)由上表可知=3.39。经验证该分部近似于泊松分布。虽然我在此只调查了一周的的数据，但考虑到学生到食堂就餐具有较大的稳定性，所以认为调查的数据还是较为可靠的。另外在非高峰时段很少发生排队的现象，故在此我也不做分析。3.2模型建立及求解。基于以上的假设，我们的模型符合排队论中的多服务台等待模型(M/M/s).该模型的特点是：服务系统中有s个窗口(即s个服务员)，学生按泊松流来到服务系统，到达强度为；服务员的能力都是，服务时间服从指数分布，每个顾客的平均服务时间t。当顾客到达时，如果所有服务员都忙着，顾客便参加排队等待服务，一直等到有服务员为他服务为止。由我的调查数据可知6,5.1,39.3st(食堂现有窗口6个)带入以上各式可得：服务员能力：67.01t系统服务强度：09.5，因为85.0609.5ss1,所以极限存在。空闲概率：031.0!!1100nnipnnii系统中排队顾客的平均数：271!20sssqspL顾客平均排队时间：96.739.327qqLW顾客平均逗留时间：46.95.196.7tWWq系统中顾客的平均数：09.3209.527qLL由此可见，当我们在中午11:45到15:15这个时间段去食堂吃饭时，一进门就会发现里面已经是人满为患了，几乎不可能找到空闲的窗口。而且，已经有32个同学在排队买饭，27个人这在排队等待，平均一个窗口5人。当我们开始排队时要过80秒钟才轮到我们，要过95秒钟才能吃到可口的饭菜，来填饱我们的肚子。为了检验我的数据与事实相符，我拜托同学体验了一番，下表是我的统计数据：表二时间周一12:14周二12:10周三12:12周四12:10排队等待人数4546排队等待时间80857075忽略那些随即因素，我得到的那些结论和实际数据还是较为符合的，可见的的模型是比较成功的。3.3模型分析对于学生来说中午的时间是很有限的，能尽快吃上饭对我们来说是很重要的。同时，学生在食堂的排队的平均逗留时间qW很大程度上可以决定学生对食堂的选择，所以食堂的工作人员也希望尽可能的满足学生的要求。研究学生平均逗留时间qW将是解决本模型的关键所在，平均逗留时间qW是由平均排队时间W和平均服务时间t组成。我个人认为15秒的平均服务时间t对于服务员来说已经是极限了，如果在加快速度反而可能手忙脚乱，增大出错的可能性，到时反而会降低效率，一次我认为平均服务时间t不可改变，是个常数。至于平均排队时间W我们有公式可知它由顾客到达强度，每个顾客的平均服务时间t和窗口数S来决定的，由于学生对食堂的选择有一定的偏好，即一般都会去同一个食堂吃饭，因此我们可以认为学生流是稳定的，即为常数，由上面的分析可知t也是常数因此能对平均排队时间构成影响的就只有窗口S了，下面就对S的取值对W的影响进行分析：由Matlab我们可以得到他们两者之间的散点图：注：上图的W单位是秒。利用Matlab多项式拟合得到他们之间的二次多项式关系式：326.28366.9818.1123.4xxxy从图中可以看到，随着窗口数的增加，平均排队时间急剧减少，当窗口数达到5以后时，变化趋于平缓。为了得到更精确的分析，我在这里再用灵敏度的观点进行讨论。由于窗口数S只能是整数，得到表三：窗口数S678910平均排队时间05.231.640.580.23下面我们分析平均排队时间对窗口数的灵敏度：灵敏度sWsWWsQ,由此我们可得不同的窗口数S下的灵敏度：表四窗口数S678910灵敏度029.1317.5116.5417.62由此可见，平均排队时间W对窗口数十分敏感，均达到16以上，其中窗口数从6变成7是尤为明显，其平均排队时间由27秒变为5.23秒。二其他几种情况虽也很敏感，但是平均排队时间变化的绝对值很小，大小不超过4秒。3.4窗口数的优化设计对于学生方面来说当然是排队等待时间越短越好，而对于食堂方面来说，窗口数的增加一方面会导致成本的增加，带来大的成本压力，另一方面会缩短排队时间，即意味着它能为更多的学生服务，所以他是否会增加窗口数就取决于成本和收益的大小关系。因此，需要对系统进行优化，在成本和利益之间寻求可能的平衡点。我们可以把该系统优化表述为：寻求最佳的窗口数S，使系统总费用C(s)最小，即：minC(s)=LCsCws其中：S为并联的窗口台数量，C(s)是关于窗口台数量的费用，Cs是单位时间里平均每个窗口的费用，Cw为平均每个学生在系统中等待（或逗留）单位时间的等待损失，L是平均队长。在理论上上述目标函数存在着优化解。一般来说，每增加一个窗口，需要多配备一名服务人员以及一些配套的设施，所以增加窗口数所带来的成本等于新增服务人员的工作加上配套设施的维修与清洗费。新增窗口的收益是比较难估量的。在此我们引入等待损失的概念，即由于排队等待食堂所减少的收益，得到等待损失等于食堂单位时间收益乘以平均等待时间乘以顾客数。我们调查得知服务人员的每月平均工资是700元，即每周平均175元，至于配套设施的维修与清洗，我们大致可以认为每周不超过300元。由此可知每增加一个窗口，食堂的成本就得增加825元。由于学生要的菜不同，而且采的利润也不同，所以是很难估计的，故我们由一般规律假定每十秒钟可得0.5的利润。所以学生因等待让食堂发生的损失C=0.3*3059W,当窗口数由6变到7时，食堂可少损失WC30591.0=0.5*3059（2.7-0.523）=3329.72元。由此得知最佳窗口是7。参考文献：[1]胡运权，运筹学教程[M].清华大学出版社，1988。[2]许久平，胡只能等，运筹学（类）（第二版）[M].科学出版社，2004。[3]复旦大学.概率论基础[M].高等教育出版社，1984