兰州交大2011数模竞赛某款台结算方式的优化模型

《兰州交大2011数模竞赛某款台结算方式的优化模型》由会员分享，可在线阅读，更多相关《兰州交大2011数模竞赛某款台结算方式的优化模型（20页珍藏版）》请在装配图网上搜索。

1、兰州交通大学2011年大学生数学建模竞赛论文基于排队论的某款台结算方式的优化模型一、摘要超市款台结算方式的优化调整是超市和顾客都共同关注的问题，从理论上 讲，这一问题兼有排队论和规划论的特点。考虑到顾客、收银台和购买商品付款服务之间的流程关系，确定出使用平均 排队等待时间、平均接受服务时间、平均逗留时间、各个服务台的平均服务速率（也即超市的服务效率）、平均每单位时间中系统可以为顾客服务的比例（也即 服务强度）来做为评价指标，这些指标可以充分反映超市款台结算方式安排的优 劣。题目中当前超市实行的规则可以看作是一个多队列多服务台的排队模型（M/M/s且当s=4的情况），所有的款台现金结算和银行卡与

2、支票结算这两种结 算方式都结算，这当然不能有效地分配超市收款台资源。因此，我们把顾客按照 结算方式类型不同分为4个队列，将收款台当作服务台，建立了一个4队列多服 务台的无优先权的排队模型，其中一个为快速服务款台，专为购买8个或8个以 下商品的顾客服务，另外两个为现金支付款台，只结算现金结算业务，最后一个 为两种结算方式都结算的传统服务款台。模型中的服务规则为“当前被服务的顾 客总平均逗留时间最短”和“同类型内部先到先服务”。为了实现该排队系统中 的实时服务台分配，在系统中嵌入了一个规划模型，模型目标是使“当前被服务 的顾客总平均逗留时间最短”，约束条件中考虑了服务台被服务顾客满员原则。 可以证

3、明该规划模型满足“同类型内部先到先服务”规则。我们使用了计算机系统仿真求解模型，仿真算法即排队论的蒙特卡洛算法， 编程语言使用Matlab编程仿真实现。得出结论：倡议模型比现有模型在客户满 意度上有较大的改善。建议超市采纳倡议模型以提高客户满意度和经营效率。关键词：排队模型系统仿真款台结算方式优化二、问题的提出款台结算方式的优化调整随着高科技在社会生活各个领域应用的不断深入，人们的生活方式也在逐渐 随着这种高科技的应用而发生重大的变化，尤其是与人们正常生活息息相关的各 社会服务行业都以一种人性化的方式在改进服务方式。其中服务台结算方式的改 变时几乎影响每个人的一种变化形式，以前的款台结算方式只

4、有现金结算，而目 前大多数服务行业的款台结算都采用两种形式：现金结算和银行卡与支票结算； 当然后者在某种程度上确实为人们的生活消费提供了方便，避免了诸如携带现金 的不便与不安全等因素，但在诸如超市等一些顾客流量交大而款台较少需要排队 等候结算的服务场所则出现课一个问题，尽管银行卡或支票结算方便了这些结算 的人，但这种结算方式比较耗时，因而对持现金结算而排队等候的人来说延长了 他们排队等候的时间，造成了他们情绪的不满，其中一部分人便放弃到该场所来 接受服务而转投别的同类服务机构，这样就势必给服务机构造成一定的损失，因 而作为该机构的负责人在资源有限的情形下就要对结算方式进行结构调整，以保 证两种

5、结算方式的顾客的总体满意程度只有达到最大才能保证自身的利益，然而 如何进行结算方式结构的合理调整，一直是服务机构经营者需要解决的问题。现有一小超市有4个付款台，所有的款台两种结算方式都结算，每个款台为 一位顾客计算货款数的时间与顾客所购得商品件数成正比（大约每件费时2 秒），约有20%的顾客用支票或银行卡等手段支付，这个过程需要1.5分钟，付 现金则仅需要0.5分钟；为了使顾客的总体满意程度达到最大，有人倡议设其中 一个为快速服务款台，专为购买8个或8个以下商品的顾客服务，指定另外两个 为现金支付款台，只结算现金结算业务；假设顾客到达的平均时间间隔是0.5分 钟，顾客购买商品的件数按一下频率表

6、分布：件数W891920 2930 3940 49$50相对频数0.120.100.180.28 分0.20 分0.12 分请你在合理的假设下，利用计算机的仿真功能建立一个模拟模型，对现有的 系统和倡议的系统的运转进行比较，针对超市的款台结算结构，对超市经营者提 供一种合理的建议。三、问题的分析超市款台服务系统具有以下特点：顾客的来源是无限的，以顾客到达超市购 物为标志，进入款台结算排队系统；排队等待的顾客如果暂时没有遇到可立刻对 其进行结算服务的空闲款台，则排队等待结算服务，因而等待的人数及空间在理 论上是无限制的。顾客按照先到先服务的规则，排成4队，依次等待结算服务；从顾客进入等 待队列到

7、结算完毕表示服务完成，离开排队系统。在本系统中先到先服务规则可 看作是一个多队列多服务台的排队系统，其中，服务台即为款台。题目主要要求比较现有的系统和倡议的系统的运转谁优谁劣，因此问题构成 了一个具有4个队列，4个服务台的排队系统，只是不同点在于现有系统的4个 服务台结算方式均相同而倡议的系统中4个服务台的结算方式各有不同罢了。当然，对于现有的系统，若按照先到先服务的规则进行排队可能会导致等待 结算的顾客队列越来越长，不能有效的利用超市款台资源。四、符号说明与模型假设1.符号说明c :结算台个数；九：最简单流(顾客流)的参数；卩：单个结算台单位时间平均服务完的顾客数：P :服务强度；N(t)

8、： t时刻结算系统内顾客人数；九：系统内已有n个顾客的到达率；n卩：系统内有n个顾客时，结算台单位时间平均服务的顾客数；nL :平均等待队长；qL :平均逗留的顾客人数；W :平均等待时间；qW :平均逗留时间；p :每位顾客购买n件商品的概率；nk :使用支票或者银行卡等手段支付的顾客占所有顾客的比例;t :现金支付所用时间；xt :支票或者银行卡等手段支付所需时间；yt :计算n件商品的时间；nk :顾客购买商品在第i个区间所占全部区间的比重；i2 模型假设本文所研究的排队系统是指顾客在超市里挑选好商品后，在收银台前排队等 待付款的排队系统。收银台是服务台，顾客付款被认为是接受服务。套用以

9、上三 方面规则：输入过程是指顾客挑选好商品后来到收银台前；排队规则是指顾客按 单队单服务台、多队多服务台或单队多服务台的方式排队；服务机构是服务台。经过我们的分析得出本系统是一个M/M/4模型。并做出如下假设：（1）顾客以最简单流到达结算台。（2）结伴顾客（同时到达结算台的顾客人数2）看成有时间间隔的到达结算 台，并且顾客到达结算台的相继到达时间间隔独立。若设九是顾客的平均到达11率，那么1是相邻两个顾客到达的平均间隔时间，并服从均值为1的指数分布 人人（即输入过程为Poisson过程）。（3）若设卩是一个连续工作服务台的平均服务率，那么丄是顾客的期望服务时间。对每个顾客的平均服务时间服从均值

10、为丄的指数分布。（4）顾客所购商品数量在给定区间aibi内服从均匀分布。（5）本系统中各个服务台工作相互独立（不搞协助）。（6）每个结算台的服务效率相同。（7）对于本系统中的多服务台模型，有效因子的公式为p=。p=表中中示每一个服务台都单独用来为顾客提供服务时花在服务上的平均时间。因此，为 了使每一个服务台都有一个可控的有效因子，仍然需要p VI,这使得排队系统 可以达到平稳条件。（8）顾客结算按照FIFS（先来先服务）原则进行。五、模型的建立1.模型的分析基于标准的M /M /c/s模型，我们在分析这个排队系统时，仍然从其状态转 移关系开始，其状态图如图（1）,转移模型如图（2）.如状态1转

11、移到状态0（系统中 有一名顾客被服务完了）的转移率为卩p 1，状态2转移到状态1（在两个服务台上有 一个顾客被服务完成而离去），因为不限是哪个服务台，所以转移率为2卩p2，同 理考虑状态n转移到状态n-1 （在n个服务台上有一个顾客被服务完成而离去）， 因为不限是哪个服务台，所以当n c得时候，转移率为gp ；当nc得时候，n因为只有c个服务台，换句话说，最多只有c个顾客被服务，n-c个顾客在等 待，转移率为仲p 。n顾客九图九AA 图根据图(2),可以得到转移方程:pp =kp1 0 (n +1) pp+Xp二(九 + np)p(1 n c)n+1n-1n其中：区p = 1，且p 1.ii=

12、0递推上述差分方程，可以求得：1(入)c -1=茅1(九)1 p =乙()k -0k=0k! pc!1-p pI 丄(1)p =inn!、p 叫(n c)0特别的，当只有一个服务台时，系统变为M /M/1/2，各个指标为:1 1p = 1 -p0 (L) nn=0p = p npn0九p (p-九)1p-九2.评价指标的建立题目要求使得顾客的总体满意度达到最大，故对现有模型和倡议模型进行对 比，为了建立恰当的满意度评价体系，结合排队论中的各个系统指标，在这里， 我们仅仅考虑顾客在整个付款系统中的逗留时间，将这个时间作为满意度的一个 最重要的指标，而将整个队长作为顾客满意度的另外一个指标，并给予

13、相应的权 系数，为了使得评价体系完整，具有说服力，我们先将评价指标归一化，应用简 单的线性函数归一化，如下：y =minx 一 xmax min统一化后数据后，对于现有系统模型及倡议系统模型，我们应用如下量化指 标来描述顾客的满意度:T= Li + W1wait1 s 2 s(其中：8 +8 = 1, Li,W 1为L ,W归一化数据).12s ss s其满意度定义为：dmanyiwait从而本文的满意度评价指标为:max dmanyi3.模型一(现有系统)建立对于单个顾客，其购买N件商品的概率为p，现在考虑购买商品数的所有N可能情况，根据题意，购买商品数在区间a ,b 的平均件数为N，贝廿：

14、i iiNb；x - p( x)dxia每位顾客购买商品的平均数量为：而本文为离散模型，即:(1)N = - piii=aiN =区艺 k - i - p (2)iii=0 j=a.结算人员为每位顾客计算结算时间为t-: Nt = N -1(3)N1结算人员为每位顾客服务的平均时间T为：T = (1 - k)(t +1 ) + k(t +1 )(4)N xN y从而:1根据模型分析，结算服务系统的运行指标如下:P c Pc!(l-p )2平均队长:L = (n - c) pqnnc+1到达结算台后必须等待的概率:p(n 4) piic+1cp 4 p 0c!( x - p)平均等待时间和逗留时

15、间，由Little公式求得:(10)4.模型二（倡议系统）的建立原四个结算款台中，现有一个款台（快速款台）专门为购买8个或者8个以下 商品的顾客服务，其服务的顾客只是在购买商品数量上有所限定，而并没有对付 款方式有所限定（现金支付和银行卡及支票支付）；另外三个款台为购买商品数量 大于8件的顾客服务，而其中两个被指定为只能使用现金支付；其支付系统可以 表示为如下图形（3）：图（3）：倡议系统的服务示意图对结算台1,专门为购买8个或者8个以下商品的顾客服务，其服务的顾客 只是在购买商品数量上有所限定，而并没有对付款方式有所限定（现金支付和银 行卡及支票支付），对其应用模型1,其中：(11)(12)

16、T = (1 k)(t +1 ) + k(t +1 )1N、xN y1i(13)对于结算台2,顾客的特征为购买商品数量在8个以上，但是并没有对支付 方式有所限制，故亦可以应用模型1，其中:X = X(14)21 k1T 二(1 k)(t_ +1 ) + k(t- +1 )(15)2N 2XN 2卩= (16)2 T2对于结算台3,4,顾客的特征为购买商品数量在8个以上，且对支付方式有所限制（现金支付），故亦可以应用模型1，其中:X =九(17)3,41 k(18)iT = (1 k)(t_ +1 )3,4N 2x(19)3,4六、模型的求解根据题意，些重要指标，联立等式（1）-（10）,可以求

17、得模型一（现有的系统）在平衡时候的如卜表（1）：模型一(1) M / M / 4/g服务台空闲的概率p00.4131平均队列长Lq0.9758平均队长Ls1.8591平均等待时间Wq1.9516(分钟)平均逗留时间Ws3.7182(分钟)表(1):现有的系统在平衡时候的指标联立等式(11)-(19)以及应用排队论中的M /M/I心及M /M/2心相关理论，可以求得模型二(倡议系统)在平衡时候的一些重要指标，如下表(2)：吉算台指标(1)M / M/1/g(2)M/M/1/g(3,4)M /M/2/g服务台空闲的概率p000.63110.6452平均队列长Lq00.21570.1683平均队长L

18、s00.58460.5996平均等待时间Wq00.94910.4443平均逗留时间Ws02.57241.5830表(2):倡议系统在平衡时候的指标七、结果分析与检验先对两个模型的系统指标应用满意地评价指标，可以求得,见下表(3):幺士皆厶吉口算台 归一化指标、模型一M /M/4/g 结算台 (1,2,3,4)模型二M / M/1/g结算台(1)模型二M / M/1/g结算台模型二M/M/2/g结算台(3,4)平均队长Ls平均逗留时间W1.00000.31450.3225s1.00000.69180.4257表(3):模型部分指标归一化后数据对于模型二，顾客分别可能从不同的结算台付款，因此需对四

19、个结算台都要 考虑，其满意度按照顾客进入结算台比例加权，具体：d =亡 k (e L +8 Wi)manyii 1 s 2 si=1经过计算，可以得到如下模型对比图(4)：图(4)：两个模型满意度对比图由上图可明显看出：倡议模型比现有模型在客户满意度上有较大的改善。所 以我们的建议是如果超市采纳了倡议模型，那么顾客的满意度将更高，从而超市 的经营效率会得到很大提升。八、模型的优缺点与改进方向九、参考文献1 盛 骤，谢氏千,潘承毅概率论与数理统计（第四版）M.北京:高等教育出版社.2009.2 徐玖平，胡知能运筹学数据模型决策（第二版）M.北京:科学出版社.2009.3 刘正君.MATLAB科学

20、计算与可视化仿真宝典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

21、*4*4*4*aA5*p0/4/24/(1-a/4)A2;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;

22、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,

23、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 suana=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(等待时间占满意度的百分

24、比)ylabel(满意度)legend(现有模型,倡议模型)%solution model 3lmd=0.5 t=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*aA4*p0)/(24*(4-a);lq=4*4*4*4*aA5*p0/4/24/(1-a/4)A2;ls=lq+a;wq=lq/lmd;ws=ls/lmd;tai2=p0,lq,ls,wq,wslmd=0.5j=30:40; t=0.8*(2*j/60+0.5)+0.2*(2*j/

25、60+1.5);miu=1./ta=lmd./miu p0=1./(1+a+a.*a/2+a.*a.*a/6+a.*a.*a.*a/24./(1-a) lq=1./(1+a+a.*a/2+a.*a.*a/6+a.*a.*a.*a/2 4./(1-a).*a/4.*a./(24*(1- a).A2)ls = 1./(1+a+a.*a/2+a.*a.*a/6+a.*a.*a.*a/2 4./(1-a).*a/4.*a./(24*(1- a).A2)+awq=(1+a+a.*a/2+a.*a.*a/6+a.*a.*a.*a/24./(1-a).*a4.*a./(24*(1- a).A2)*2ws=(

26、1+a+a.*a/2+a.*a.*a/6+a.*a.*a.*a/24./(1-a).*a.A4.*a./(24*(1- a).A2+a)*2lmd=0.5miu=0.566a=lmd/miu/4 p0=1/(1+a+a*a/2+a*a*a/6+a*a*a*a/24/(1a) lq=1/(1+a+a*a/2+a*a*a/6+a*a*a*a/24/(1a)*(4*a)T*a/(24*(1a)入2) ls=1/(1+a+a*a/2+a*a*a/6+a*a*a*a/24/(1a)*(4*a)八4*a/(24*(1a)八2)+a wq=(1/(1+a+a*a/2+a*a*a/6+a*a*a*a/24/(1a)*(4*a)入4*a/(24*(1a)入2)*2 ws=1/(1+a+a*a/2+a*a*a/6+a*a*a*a/24/(1a)*(4*a)A4*a/(24*(1a)A2)2.超市仿真模块与仿真结果File Edit Vi ew Inzert Tools Desktop Window HelpFigure 1匚File Edit Vi ew Inzer t Tools Desktop Windijw Help