大学生数学建模竞赛论文-基于排队论的某款台结算方式的优化模型.doc

兰州交通大学2011年大学生数学建模竞赛论文题目： 基于排队论的某款台结算方式 的优化模型 参赛人1： 姓名 学院 自动化与电气工程学院 班级 电气084班 参赛人2： 姓名 学院 自动化与电气工程学院 班级 电气084班 参赛人3： 姓名 学院 自动化与电气工程学院 班级 电气084班 学校统一编号，个人不得填写论文编号： 基于排队论的某款台结算方式的优化模型一、摘要超市款台结算方式的优化调整是超市和顾客都共同关注的问题，从理论上讲，这一问题兼有排队论和规划论的特点。考虑到顾客、收银台和购买商品付款服务之间的流程关系，确定出使用平均排队等待时间、平均接受服务时间、平均逗留时间、各个服务台的平均服务速率（也即超市的服务效率）、平均每单位时间中系统可以为顾客服务的比例（也即服务强度）来做为评价指标，这些指标可以充分反映超市款台结算方式安排的优劣。题目中当前超市实行的规则可以看作是一个多队列多服务台的排队模型（m/m/s且当s=4的情况），所有的款台现金结算和银行卡与支票结算这两种结算方式都结算，这当然不能有效地分配超市收款台资源。因此，我们把顾客按照结算方式类型不同分为4个队列，将收款台当作服务台，建立了一个4队列多服务台的无优先权的排队模型，其中一个为快速服务款台，专为购买8个或8个以下商品的顾客服务，另外两个为现金支付款台，只结算现金结算业务，最后一个为两种结算方式都结算的传统服务款台。模型中的服务规则为“当前被服务的顾客总平均逗留时间最短”和“同类型内部先到先服务”。为了实现该排队系统中的实时服务台分配，在系统中嵌入了一个规划模型，模型目标是使“当前被服务的顾客总平均逗留时间最短”，约束条件中考虑了服务台被服务顾客满员原则。可以证明该规划模型满足“同类型内部先到先服务”规则。我们使用了计算机系统仿真求解模型，仿真算法即排队论的蒙特卡洛算法，编程语言使用matlab编程仿真实现。得出结论：倡议模型比现有模型在客户满意度上有较大的改善。建议超市采纳倡议模型以提高客户满意度和经营效率。关键词：排队模型 系统仿真 款台结算方式优化二、问题的提出款台结算方式的优化调整随着高科技在社会生活各个领域应用的不断深入，人们的生活方式也在逐渐随着这种高科技的应用而发生重大的变化，尤其是与人们正常生活息息相关的各社会服务行业都以一种人性化的方式在改进服务方式。其中服务台结算方式的改变时几乎影响每个人的一种变化形式，以前的款台结算方式只有现金结算，而目前大多数服务行业的款台结算都采用两种形式：现金结算和银行卡与支票结算；当然后者在某种程度上确实为人们的生活消费提供了方便，避免了诸如携带现金的不便与不安全等因素，但在诸如超市等一些顾客流量交大而款台较少需要排队等候结算的服务场所则出现课一个问题，尽管银行卡或支票结算方便了这些结算的人，但这种结算方式比较耗时，因而对持现金结算而排队等候的人来说延长了他们排队等候的时间，造成了他们情绪的不满，其中一部分人便放弃到该场所来接受服务而转投别的同类服务机构，这样就势必给服务机构造成一定的损失，因而作为该机构的负责人在资源有限的情形下就要对结算方式进行结构调整，以保证两种结算方式的顾客的总体满意程度只有达到最大才能保证自身的利益，然而如何进行结算方式结构的合理调整，一直是服务机构经营者需要解决的问题。现有一小超市有4个付款台，所有的款台两种结算方式都结算，每个款台为一位顾客计算货款数的时间与顾客所购得商品件数成正比（大约每件费时2秒），约有20%的顾客用支票或银行卡等手段支付，这个过程需要1.5分钟，付现金则仅需要0.5分钟；为了使顾客的总体满意程度达到最大，有人倡议设其中一个为快速服务款台，专为购买8个或8个以下商品的顾客服务，指定另外两个为现金支付款台，只结算现金结算业务；假设顾客到达的平均时间间隔是0.5分钟，顾客购买商品的件数按一下频率表分布：件数891920293039404950相对频数0.120.100.180.28分0.20分0.12分请你在合理的假设下，利用计算机的仿真功能建立一个模拟模型，对现有的系统和倡议的系统的运转进行比较，针对超市的款台结算结构，对超市经营者提供一种合理的建议。三、问题的分析超市款台服务系统具有以下特点：顾客的来源是无限的，以顾客到达超市购物为标志，进入款台结算排队系统；排队等待的顾客如果暂时没有遇到可立刻对其进行结算服务的空闲款台，则排队等待结算服务，因而等待的人数及空间在理论上是无限制的。顾客按照先到先服务的规则，排成4队，依次等待结算服务；从顾客进入等待队列到结算完毕表示服务完成，离开排队系统。在本系统中先到先服务规则可看作是一个多队列多服务台的排队系统，其中，服务台即为款台。题目主要要求比较现有的系统和倡议的系统的运转谁优谁劣，因此问题构成了一个具有4个队列，4个服务台的排队系统，只是不同点在于现有系统的4个服务台结算方式均相同而倡议的系统中4个服务台的结算方式各有不同罢了。当然，对于现有的系统，若按照先到先服务的规则进行排队可能会导致等待结算的顾客队列越来越长，不能有效的利用超市款台资源。四、符号说明与模型假设1符号说明 ：结算台个数； ：最简单流(顾客流)的参数； ：单个结算台单位时间平均服务完的顾客数： ：服务强度； ：时刻结算系统内顾客人数； ：系统内已有个顾客的到达率； ：系统内有个顾客时，结算台单位时间平均服务的顾客数; ：平均等待队长； ：平均逗留的顾客人数； ：平均等待时间； ：平均逗留时间； ：每位顾客购买件商品的概率； ：使用支票或者银行卡等手段支付的顾客占所有顾客的比例； ：现金支付所用时间； ：支票或者银行卡等手段支付所需时间； ：计算件商品的时间； ：顾客购买商品在第个区间所占全部区间的比重；2模型假设本文所研究的排队系统是指顾客在超市里挑选好商品后，在收银台前排队等待付款的排队系统。收银台是服务台，顾客付款被认为是接受服务。套用以上三方面规则：输入过程是指顾客挑选好商品后来到收银台前；排队规则是指顾客按单队单服务台、多队多服务台或单队多服务台的方式排队；服务机构是服务台。经过我们的分析得出本系统是一个m/m/4模型。并做出如下假设：（1）顾客以最简单流到达结算台。（2）结伴顾客(同时到达结算台的顾客人数)看成有时间间隔的到达结算台，并且顾客到达结算台的相继到达时间间隔独立。若设是顾客的平均到达率，那么是相邻两个顾客到达的平均间隔时间,并服从均值为的指数分布（即输入过程为poisson过程）。（3）若设是一个连续工作服务台的平均服务率，那么是顾客的期望服务时间。对每个顾客的平均服务时间服从均值为的指数分布。（4）顾客所购商品数量在给定区间内服从均匀分布。（5）本系统中各个服务台工作相互独立(不搞协助) 。（6）每个结算台的服务效率相同。（7）对于本系统中的多服务台模型，有效因子的公式为。表示每一个服务台都单独用来为顾客提供服务时花在服务上的平均时间。因此，为了使每一个服务台都有一个可控的有效因子，仍然需要1，这使得排队系统可以达到平稳条件。（8）顾客结算按照fifs(先来先服务)原则进行。五、模型的建立1模型的分析基于标准的模型，我们在分析这个排队系统时，仍然从其状态转移关系开始，其状态图如图(1),转移模型如图(2).如状态1转移到状态0(系统中有一名顾客被服务完了)的转移率为，状态2转移到状态1(在两个服务台上有一个顾客被服务完成而离去)，因为不限是哪个服务台，所以转移率为，同理考虑状态转移到状态(在个服务台上有一个顾客被服务完成而离去)，因为不限是哪个服务台，所以当得时候，转移率为；当得时候，因为只有个服务台，换句话说，最多只有个顾客被服务，个顾客在等待，转移率为。 。顾客离开超市结算台结算台1结算台2结算台3结算台4完成顾客图(1)图(2)根据图(2)，可以得到转移方程：其中：，且.递推上述差分方程，可以求得：特别的，当只有一个服务台时，系统变为，各个指标为：，2评价指标的建立题目要求使得顾客的总体满意度达到最大，故对现有模型和倡议模型进行对比，为了建立恰当的满意度评价体系，结合排队论中的各个系统指标，在这里，我们仅仅考虑顾客在整个付款系统中的逗留时间，将这个时间作为满意度的一个最重要的指标，而将整个队长作为顾客满意度的另外一个指标，并给予相应的权系数，为了使得评价体系完整，具有说服力，我们先将评价指标归一化，应用简单的线性函数归一化，如下：统一化后数据后，对于现有系统模型及倡议系统模型，我们应用如下量化指标来描述顾客的满意度： (其中:,为归一化数据).其满意度定义为：从而本文的满意度评价指标为：3模型一(现有系统)建立对于单个顾客，其购买件商品的概率为，现在考虑购买商品数的所有可能情况，根据题意，购买商品数在区间的平均件数为，则：每位顾客购买商品的平均数量为：而本文为离散模型，即： （1） (2)结算人员为每位顾客计算结算时间为： (3)结算人员为每位顾客服务的平均时间为： (4)从而： (5)根据模型分析，结算服务系统的运行指标如下：平均队长： (6) (7)到达结算台后必须等待的概率： (8)平均等待时间和逗留时间，由公式求得： (9) (10)4模型二(倡议系统)的建立原四个结算款台中，现有一个款台(快速款台)专门为购买8个或者8个以下商品的顾客服务，其服务的顾客只是在购买商品数量上有所限定，而并没有对付款方式有所限定(现金支付和银行卡及支票支付)；另外三个款台为购买商品数量大于8件的顾客服务，而其中两个被指定为只能使用现金支付；其支付系统可以表示为如下图形(3)：顾客离开超市结算台快速台1()2()3()现4()现完成顾客 图(3)：倡议系统的服务示意图对结算台1，专门为购买8个或者8个以下商品的顾客服务，其服务的顾客只是在购买商品数量上有所限定，而并没有对付款方式有所限定(现金支付和银行卡及支票支付)，对其应用模型1,其中： (11) (12) (13)对于结算台2，顾客的特征为购买商品数量在8个以上，但是并没有对支付方式有所限制，故亦可以应用模型1，其中： (14) (15) (16)对于结算台3,4，顾客的特征为购买商品数量在8个以上，且对支付方式有所限制(现金支付)，故亦可以应用模型1，其中： (17) (18) (19)六、模型的求解根据题意，联立等式(1)-(10),可以求得模型一(现有的系统)在平衡时候的一些重要指标，如下表(1)： 模型一 指标 (1) 服务台空闲的概率平均队列长平均队长平均等待时间平均逗留时间0.41310.97581.85911.9516(分钟)3.7182(分钟)表(1)：现有的系统在平衡时候的指标联立等式(11)-(19)以及应用排队论中的及相关理论，可以求得模型二(倡议系统)在平衡时候的一些重要指标，如下表(2)： 结算台 指标(1) (2) (3,4) 服务台空闲的概率平均队列长平均队长平均等待时间平均逗留时间000000.63110.21570.58460.94912.57240.64520.16830.59960.44431.5830表(2)：倡议系统在平衡时候的指标七、结果分析与检验先对两个模型的系统指标应用满意地评价指标，可以求得,见下表(3)： 结算台归一化指标 模型一结算台(1,2,3,4)模型二结算台(1)模型二结算台(2)模型二结算台(3,4)平均队长平均逗留时间1.0001.000000.31450.69180.32250.4257表(3)：模型部分指标归一化后数据对于模型二，顾客分别可能从不同的结算台付款，因此需对四个结算台都要考虑，其满意度按照顾客进入结算台比例加权，具体：经过计算，可以得到如下模型对比图(4)：满意度图(4)：两个模型满意度对比图由上图可明显看出：倡议模型比现有模型在客户满意度上有较大的改善。所以我们的建议是如果超市采纳了倡议模型，那么顾客的满意度将更高，从而超市的经营效率会得到很大提升。八、模型的优缺点与改进方向 九、参考文献1盛 骤,谢氏千,潘承毅.概率论与数理统计（第四版）m.北京:高等教育出版社.2009.2徐玖平,胡知能.运筹学数据模型决策（第二版）m.北京:科学出版社.2009.3刘正君.matlab科学计算与可视化仿真宝典m.北京:电子工业出版社.2009.4叶 向.实用运筹学上机实验指导及习题解答m.北京:中国人民大学出版社.2007.5刘 露.眼科病床安排模型及仿真算法.全国大学生数学建模竞赛优秀论文汇g.2010, 4(3):76-96. 十、附录部分1模型计算及仿真源代码（使用matlab语言）%solution model 1lmd=0.5t=0.8*(64/60+0.5)+0.2*(64/60+1.5);miu=1/t;a=lmd/miu;p0=1/(1+a+a*a/2+a*a*a/6+a*a*a*a/24/(1-a/4);pd=(4*a4*p0)/(24*(4-a);lq=4*4*4*4*a5*p0/4/24/(1-a/4)2;ls=lq+a;wq=lq/lmd;ws=ls/lmd;tai2=p0,lq,ls,wq,ws%solution model 2%station 1lmd=0.5/0.12t=0.8*(9/60+0.5)+0.2*(9/60+1.5);miu=1/ta=lmd/miup0=1-alq=a*a/(1-a)ls=a/(1-a)wq=lmd/miu/(miu-lmd)ws=1/(miu-lmd)%station2lmd=0.5/0.88/3*6/5;t=0.8*(55.4/60+0.5)+0.2*(55.4/60+1.5);miu=1/t;a=lmd/miu;p0=1-a;lq=a*a/(1-a);ls=a/(1-a);wq=lmd/miu/(miu-lmd);ws=1/(miu-lmd);tai2=p0,lq,ls,wq,ws %station3.4lmd=0.5/0.88/3*2;t=0.8*(55.4/60+0.5);miu=1/t;a=lmd/miu;p0=1/(1+a+a*a/2/(1-a/2);lq=8*(a/2)*a*a*p0/2/(1-a/2)2;ls=lq+a;wq=lq/lmd;ws=ls/lmd;tai34=p0,lq,ls,wq,ws%guiyihuals=1.8591,0.5846,0.5996,0;ws=3.7182,2.5724,1.5830,0;ls1=(ls-min(ls)./(max(ls)-min(ls)ws1=(ws-min(ws)./(max(ws)-min(ws)%man yi du ji suan a=0.1:0.1:0.9;b=1-a;d1=1./(1*a+1*b)/4;d2=0.88*(1./(0.6918*a+0.3145*b)+1./(0.4257*a+0.3225*b);d2=(d2-min(d2)/(max(d2)-min(d2)plot(b,d1,r,b,d2)title(现有模型(红线)与倡议模型满意度对比)xlabel(等待时间占满意度的百分比)ylabel(满意度)legend(现有模型,倡议模型)%solution model 3lmd=0.5t=0.8*(64/60+0.5)+0.2*(64/60+1.5);miu=1/t;a=lmd/miu;p0=1/(1+a+a*a/2+a*a*a/6+a*a*a*a/24/(1-a/4);pd=(4*a4*p0)/(24*(4-a);lq=4*4*4*4*a5*p0/4/24/(1-a/4)2;ls=lq+a;wq=lq/lmd;ws=ls/lmd;tai2=p0,lq,ls,wq,wslmd=0.5j=