数学建模——排队问题省名师优质课获奖课件市赛课一等奖课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本幻灯片资料仅供参考，不能作为科学依据，如有不当之处，请参考专业资料。谢谢,QuickPass,系统排队问题,谢瑶,03/03/,xieyao,电子工程与信息科学系,PB00006,第1页,排队,经常是件很令人恼火事情,尤其是在我们这么人口大国,电话亭,1978,年在北京,15%,电话要在,1,小时后才能接通。在电报大楼打电话人还要带着午饭去排队,银行窗口，,ATM,医院、剪发、火车售票,游乐场游乐项目,?,第2页,在游乐园中频频排队,会极为扫兴,DisneyLand,中,FastPass,(QuickPass),系统,就是想处理这,个问题,第3页,What is QuickPass?,工作原理：,抵达用户将自己票插入,FastPass,slot,中,FastPass,计算出提议用户返回时间间隔（,time interval,）或时间点或时间窗（,time window,）,用户无需排队，在指定时间返回就可持票进入,第4页,怎样缩短排队等候时间？,银行排队叫号机,只是有序组织了用户，并没有降低等候时间,假如能实现知道轮到自己需要等候多少时间，再选择适当时间来，岂不很好？,第5页,FastPass存在问题：,预知返回时间间隔存在误差,按时返回却仍需要排队,提议返回时间间隔太长,假如告诉你,4,小时以后再回来呢？,用户可能不会完全按照安排时间返回,假如新来用户不想使用,FastPass,系统？,现有,Fast Pass,真那么好用吗？,第6页,我们目标,就是对,FastPass,系统建立合理,离散统计模型（,Distributed Statistical Model,）,，求出最优用户返回时间。,建模普通步骤,以及：,*模型改进,*启发与待处理问题,第7页,1 模型假设,游乐园开放时间为8:00-18:00,一天中不一样时间用户流量不一样，比如早晨10:00和下午3:00用户流量是最大。,用户抵达时间符合非时间齐次泊松过程(Nonhomogeneous Possion Process)，抵达速率是,第8页,Poisson Process,第9页,Poisson Process,第10页,分析,1,：能否得到准确返回时间？,2,在我们开始动手建模之前，先要问几个问题：,第11页,分析,2,：使用,FastPass,后排队是不是能够防止？,FastPass,给出返回时间只是期望值，而非确定值,假设全部用户都使用,FastPass,但需考虑有用户可能会不恪守,FastPass,给出返回时间,2,在我们开始动手建模之前，先要问几个问题：,第12页,分析,3,：我们优化目标函数（或,cost function,）是什么？是排队时间吗？,2,在我们开始动手建模之前，先要问几个问题：,第13页,优化问题目标函数为：,3,模型建立（,1,）目标函数,第14页,3,模型建立（,1,）目标函数,第15页,依据排队论（,queueing theory,）分类规则,（,X/Y/Z/A,）代表一类排队规则，其中,X:,用户流抵达所符合分布,Y:,用户接收服务时间所服从分布,a,Z:,服务台个数,A:,服务台一次可服务用户数量（系统容量）,针对各个游乐项目标特点，我们主要讨论两种排队系统,:,模型建立（,2,）排队模型分类,第16页,特点：系统容量为,1,，用户抵达是,Poisson,流，服务时间服从指数分布，只有一条队列,模型建立（,3,）电话亭模型,第17页,加入QuickPass系统以后Poisson排队模型,模型建立（,3,）电话亭模型,第18页,求出这类系统代价函数表示式,模型建立（,3,）电话亭模型,第19页,近似将总优化目标函数等效为对用户i目标函数：,模型建立（,3,）电话亭模型,第20页,模型建立（,3,）电话亭模型,第21页,假如简化c1,c2为常数，并计算第二个人无需等候返回时间期望值，得,用MatLab能够作出 函数，并从图中得出结果,模型求解（,4,）电话亭模型,第22页,模型求解（,4,）电话亭模型,Average call time(min*10),U2,t2,50,8.0516,17.0,80,23.0516,32.5,第23页,第三个人无需等候返回时间期望值，同理能够算出，并用图解法求出,模型求解（,4,）电话亭模型,不过第,4,个人，第,5,个人,呢？,这种方法太繁琐，似乎不好用,可否有近似算法？,第24页,与前一个模型区分在于：系统容量是c1,服务时间固定，用户抵达依然是Poisson流。服务系统数量是1,模型建立（,5,）过山车模型,第25页,还要考虑：,实际,FastPass,系统有两条队列：,FastPass,和,Standby,队列,不考虑,standby,队列，,将得到,Greedy algorithm,模型,考虑,standby,队列，,将得到效用函数模型,模型建立（,5,）过山车,第26页,最简单情况：,只有一条队列即全部人都只用,FastPass,系统,为了预防前面人等时间太长，过山车只要载满一定数量人后就开车，假设为,80,c,。,用,贪心算法（,greedy algorithm),将每个用户尽可能安排在离用户抵达时间最近，且还没有安排满人一班车上。,假设被安排用户按照,Beta,分布抵达所被安排时间段内,模型建立（,5,）过山车模型,第27页,贪心算法,模型建立（,5,）过山车模型,第28页,很轻易想到，全局优化目标变量,1.,假如开车时间不固定，则,a%,是多少最优？就是说用户坐满多少就开车？,2.,假如,开车时间间隔,是固定，则多长时间开一次是最优？,衡量标准：目标函数,模型建立（,5,）过山车模型,第29页,一个区间内用户返回示意图,：,第30页,目标函数：,模型建立（,5,）过山车模型,第31页,模型建立（,5,）过山车模型,怎样求解最优,a%c,和最优开车间隔？,对于这类复杂问题，离散仿真是最好,方法了,第32页,仿真：用计算机生成一些符合某种分布随机数据点，模拟离散时间发生,这里仿真用,MatLab6.5,完成：,步骤：,1.,生成,Poisson,用户流（模拟抵达时间）,2.,给定不一样,a%c,开车时间间隔不定，计算代价函数，画出代价函数性能曲线,3.,开车时间固定，给出不一样开车时间间隔，计算画出代价函数性能曲线,4.,得出最优结论,模型仿真（,5,）过山车模型,第33页,过山车模型仿真（,5.1,）得到,在第,j,天某一固,定时刻,i,采集样本,i=1m,j=1100,形成样本空间,矩阵,第34页,过山车模型仿真（,5.1,）,用列向量均值,预计参数,样本更新用时间序列方法（,time serial analysis,）,计算列向量,Eucilid,距离,dthreshold,就更新一次,第35页,对某一个或一组变量,x,(,t,),进行观察测量，将在一系列时刻,t,1,t,2,tn,(,t,为自变量且,t,1,t,2,tn,),所得到离散数字组成序列集合,x,(,t,1),x,(,t,2),x,(,tn,),，我们称之为时间序列，这种有时间意义序列也称为动态数据。时间序列分析是依据系统观察得到时间序列数据，经过曲线拟合和参数预计来建立数学模型理论和方法,时间序列分析（,time serial analysis,）,第36页,过山车模型仿真（,5.1,）,启发：,有没有别方法判别样本怎样更新？,如：求样本矩阵秩，,求样本向量相关系数,第37页,生成样本空间,过山车模型仿真（,5.1,）,实用一个模拟,Poisson,流方法：,某个区间 个用户抵达时间,Uniform,第38页,Poisson,流用户抵达时间,过山车模型仿真（,5.2,）,按照贪心算法指定用户,乘坐过山车班次,第39页,两种a%c情况下用户等候时间,过山车模型仿真（,5.3,）第40页,a%c,性能曲线：可见,a%c=70,最优,过山车模型仿真（,5.3,）,第41页,开车间隔优化：可是,cost function,是间隔单调函数？怎么办？,过山车模型仿真（,5.4,）,第42页,处理：考虑开车成本：开车时间间隔越短，,次数愈多，运行成本越大找,平衡点,4.67min,最优,过山车模型仿真（,5.4,）,第43页,6,模型稳健性与优缺点,电话亭模型较准确，虽可行但复杂,过山车模型贪心算法，简单，但不是最优（,quasi-optimal,）（为何不是最优,?,）,Standby,队列会有什么影响？,每个人,c1,和,c2,可能不一样,第44页,将用户抵达看成是用户流traffic),用,Trunking Theory,中,Erlang C,公式，能够得出阻塞概率,P(Block),，系统容量,C,，用户流强度,A,（）三者关系,平均队列长度为：,可将用户安排在一天之内平均队列短时刻,7,过山车模型改进,第45页,Erlang C,图形,7,过山车模型改进,第46页,统计得出队列长度，以及仿真得出实际队列长度说明能够用统计曲线作安排返回时间依据,7,过山车模型改进,第47页,改进算法效果,7,过山车模型改进,第48页,7,过山车模型改进,统计队列长度曲线应该实时更新！,不过：,可能全部用户都被安排,到同一个队列长度短时,段了,第49页,假如考虑,Standby,队列？,7,过山车模型改进,使用边际效用函数,(Marginal Utility Function),思想：,FastPass,队列中每增加一个人，会对,Standby,队列中人造成目标函数损失,第50页,使用IC卡门票，统计用户特点，数据集中在中心数据库,给用户提供预计当日实时队列长度表，用户可自己选择返回时间，选择t1,t2时间长度,你更加好方法？,8,未来工作：设计更加好,FastPass,系统,第51页,怎样写数学建模论文？,怎样求解没有显式表示式子？,怎样模拟离散随机时间？,怎样经过仿真结果求参数优化,使用数学软件，仿真过程中经常也会到新想法与结论,灵活借鉴其它学科中方法：如,Queueing theory(,排队论,),Trunking Theory(,复用论,),Greedy Algorithm,（贪心算法）,Marginal Utility Function(,边际效用函数,),9,启发与收获,第52页,这是一类OpenEnd Problem,Homework:,相同问题比如,ICM C,题，,To Screen or not to screen?,飞机场调度以及安全检验问题,你将怎样安排？,Its upto you!,第53页,感激（Acknowledgement）,此次讲座内容来自,MCM#team624,paper,感激全体组员辛勤工作！以及杨老师指导与支持。,paper,下载：,