飞机排队模型-数学建模省名师优质课赛课获奖课件市赛课一等奖课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,MCM-89题机场安排最优排队调度问题,机场通常是用“先到先服务”标准来分配飞机跑道，即当飞机准备好离开登机口时，驾驶员电告地面控制中心，加入等候跑道队伍。假设控制塔能够快速在线数据库中得到每架飞机以下信息：,1、预定离开登机口时间；,2、实际离开登机口时间；,3、机上乘客人数；,4、预定在下一站转机人数和转机时间；,5、抵达下一站预定时间。,又设共有七种飞机，载客从100人起以50人递增，载客最多一个是400人。试开发和分析一个能使乘客和各航空企业双方都满意数学模型。（注：七种飞机可能分属于不一样航空企业）,1/38,在当前各国机场，普通都使用“先到先服务”排队系统，这一系统虽一直延用，但效率不高，且不能调整意外情况发生。在这里将要给出一个利用数据库系统快速排队模型，以使机场高效服务，并使航空企业在尽可能小花费情况下，到达用户满意目标。,2/38,模型基本假设,机场上全部要起飞飞机，都必须使相同一条跑道，而且任何一架飞机在起飞时候都需要完全地占有整条跑道，每架飞机占用时间是一样长。这一假设可把整个时间分割成离散等长小时间段（也称为起飞窗口宽度），在每个小时间段上可容纳一架飞机完成起飞操作。,第i架飞机由第j个时间段上起飞时，其所需费用仅与该飞机和时间位置相关，而与它前面是哪架飞机无关。即费用不是前面飞机函数，所以这一假设可把对应于不一样排序总费用都统一描述为一个线性函数。,任何飞机从离开自己通道口抵达跑道入口处所需要时间假定都一样。同时为了防止有一大堆飞机挤在跑道入口处等候飞机（普通机场也不太可能这么），这时如有另一架飞机需要紧急起飞，这就须将全部排在前面飞机挤到一边来腾地方，所以假设每架飞机都有马上进入跑道口通道。这么在须要调整次序时，只须在数据库中次序上进行调整，而无须对飞机实地重排。而且飞机须在为其指定小时间段上才准许离开自己通道口。,3/38,4/38,模型设计与可行性分析,假如在t,0,时刻仅有一架飞机或没有要求起飞飞机，则机场就直接安排其起飞或闲置,。,所以设在t,0,有n架飞机同时要求起飞。由假设,1,，可将n架飞机起飞所需要总时间分成n个等长小时间段（如长）。下面怎样安排哪架飞机在哪个时段上起飞要依赖于实际航班花费和用户满意程度来确定。,设为,C,ij,第i架飞机从第j个小时间段上起飞时所需一切费用之和，于是全部可能排序带来费用计算有以下费用距阵表示：,（,1,）,5/38,并设X,ij,=0或1，当第i架飞机在第j个时段上起飞时X,ij,=1，不然X,ij,=0,于是对应地安排方案距阵为,：,6/38,即第一架飞机排第,2,个窗口起飞，第,2,架,排第一个窗口起飞，最终一架排最终起飞。并由上表安排结构，知道（,2,）中距阵满足每行中仅有一个元素为,1,，即每个窗口上仅有一架飞机占用；该阵每列中也有一个元素为,1,，即每架飞机占用n个窗口中一个。即变量X,ij,须满足约束：,7/38,8/38,9/38,对于分配问题，已经有专门为此种特殊结构而设计有效解题算法，它被称为,GraverThrall primal,算法。对于,1,个随机产生含有,16,个变量分配问题，最多只须,2.9,秒即可完成求解，而使用当代计算机，对任意适当个变量指派问题，只须不到一秒钟即可求得解。,同时，因为模型中费用系数阵（,1,）须要经过量化，而他们可由下一段四中公式求得。并由数据库中数据进行计算，这一量化模型过程须要另一个不到一秒钟。所以整个模型建立与求解所用时间是以秒为数量级，故当机场控制塔在面临一串连珠炮一样起飞请求时都可几乎马上对排序作出响应。而飞机起飞间隔远不是以秒为数量级。普通最少几分钟，所以模型是可行。,更主要是。在设有意外发生情况下，还可利用机场原有时间表，由数据库事先安排好起飞次序，并让飞机安排起飞次序起飞，而唯一需要重新安排情况仅仅发生在有飞机晚点或紧急情况，而这时运算也会在一秒钟左右处理问题。而且由假设（,3,），也不会因改变而产生暂时拥挤情况。,10/38,四、模型中费用系数阵量化,因为（,1,）中C,ij,是第i架飞机从第j个时间段上起飞费用，它与一架航班型号及运行费用和其上载客情况和他们满意程度相关，为简化运算，把基本运行费设置为费用零点，而只考虑因为飞机延迟起飞而引发费用。这一费用包含因为晚点而不再以最经济速度而是以较快或最快速度飞行带来燃料损失；及乘客因耽搁下站转机而重新安排旅途损失；以及用户因各种延迟带来不愉快而转化损失。将这三者分别归入费用计算并简记为：,费用:1.燃料附加费 2.乘客误机费 3.乘客不满意损失,下面分别建立几个费用计算公式,11/38,1.,燃料附加费,因为晚点，飞机必须以尽可能快速度飞行，故燃料随晚点时间长短而改变，然而既使晚点，只要为到达最大时限，就能够以低于最大安全速度飞行。并在起飞后就可近似地保持常速，所以燃料消耗在时间内应恒定，因为不知道燃料消耗怎样随飞行速度改变，选取了近似线性函数，即单位时间增加油耗费用函数为：,12/38,13/38,由此公式看出，飞机晚点越久，则耗油越多，直至它在离开时即以最大速度起飞（假设,4,）。,下面为了建模讨论方便，将上述公式中及以后要用到一些参数给出一个总表：,14/38,15/38,16/38,2.乘客误机费,设为乘客耽搁了转机而必须赔偿费用，这里取为常数（假设,5,）。假如对各人赔偿费确实不一样，则取为各人费用数学期望,-,平均值，且重新安排旅程只发生在飞机晚点时间超出了时限时才发生，故费用以下计算,17/38,3.,乘客不满意损失,因为飞机晚点越多，则乘客会越不满意，假如仅晚点一两分钟，则用户不会太不愿意；但假如晚点到误了转乘班机，则该乘客会顿时变得焦躁不安而且非常愤恨，这一情况能够适当地摘述为一个指数增加函数附加一个阶跃函数，则总费用函数为：,18/38,19/38,20/38,不过只要将要抵达飞机一准备好降落，就能够准许其降落话，这模型仍适用，这只要将,21/38,为了预防那些还未准备好飞机，在就绪之前就对其发出起飞命令，置一架飞机在它预定起飞时间以前某窗口起飞损失为无穷大，并假如考虑,1,，,2,，,3,中费用，得到计算费用通式：,22/38,4.排队模型小结：,2)求解线性规划模型（指派模型）最优解，则可确定哪架飞机在什么时刻起飞；,23/38,在正常运行情况下，上述小结中,1,），,2,）步骤仅须做一次即可按部就班地运行，只有当意外发生时才启用,3,）部分。,五.模型检验,最主要模型检验即在于检验此模型是否含有意义，编了一个用单纯形法解线性规划程序以及几个简单例子来检验模型运行良好性，在后面第六部分中详细结果中，能够看出全部结果都与所期待直观判断相吻合。随即，又进行了更彻底检验；变动其中参数，测试更为复杂例子，以至实际运作此系统，假如实际运行结果显示出为航空企业节约了开支，同时又能维持用户满意度在一个可接收水平，则此模型将取得圆满成功。,24/38,下面先进行是变动其中参数检验，即在参数受到扰动情况下模型是否稳定检验，假如这个模型中一个或几个参数有轻微偏离真值，而模型结果不致有太大偏离最优解，则可认为模型是稳定。另外,假如参数微小改变带来模型猛烈改变，则希望确定哪个参数更敏感。这么确定它时将利用更多信息，以到达准确。,25/38,下面将指派模型（,4,）表运输模型：,由运输模型相关理论知：运输问题有可行解，并对（,9,）这么运输模型，一定有一个最优且此最优全部分量都取整数值。又注意到约束条件（,9,）限制，则可能整数解一定非0即,1,，所以运输问题等价于原问题（,4,）。将（,9,）式由目标函数向量形式（见（,4,）式定义）表出：,26/38,27/38,28/38,29/38,30/38,31/38,32/38,六、计算机模拟模型,为了了解模型运行良好性，以及本模型特点，用下述几个计算机模拟例子来进行演示。,显然；理论模型要比计算机模型要少受限制。为了编程简单并说明问题，在原有基本假定基础上，再添加以下详细假定：,1.1,、,在每一窗口至多有三架飞机已准备好能够起飞，当仅有两架飞机准备好情况发生时，可加入一个虚拟变量，以其对对应费用系数都为,0,即可。,2、凭直观给模型指定了参数值，在实际中，这些值应该经过试验室或调查取得：,每一个起飞窗口为一分钟长，即任何飞机起飞需要至多一分钟，而且其它飞机不准在一分钟内占用跑道；,设有飞机降落情况；,33/38,误转机赔偿费为每人,350,；,误了转机乘客愤恨长度等价于被耽搁了,15,分钟乘客两倍。,例,1,（含有使最多乘客飞机先走功效）,考虑在早晨,6,：,00,，三架飞机同时要求起飞设他们型号相同，有距此机场相同距离终点机场，（但可能飞往不一样城市机场）。设三架飞机为,A,，,B,，,C,。而且他们都预定在,7,：,20,抵达终点，但,A,飞机上有,350,名乘客；,B,飞机上有,100,名；,C,飞机上有,400,名。且每架飞机上都有,100,名乘客要求转机，计算结果见表,1,。,34/38,例,2,（含有使晚点飞机最久者先走功效,）,当飞机,C,准备离开之际，飞机,D,要求紧急起飞。飞机,D,已经晚点,18,分钟，它若想按时在,7,：,06,分抵达终点，就必须在,2,分钟内起飞。其上有,200,名乘客，,150,人要求转机，表,2,给出了结果,35/38,例3（含有按情况决定先后功效）,假设又过了两分钟，这时,D,和,A,已走，剩下,B,已经晚点,3,分钟，而另一架飞机,E,在此刻要求起飞。设,E,有以下条件：,1）按时准备就绪；,2）在可按时抵达终点（,7,：,42,）之前，还充裕,42,分钟能够闲置；,（3）机上有,122,名乘客，,89,人要求转机；,（4）晚点增加费用为每分钟,450,。,36/38,编程序来解此题，如所设引入一个虚拟变量，飞机,X,，这一飞机一切费用系数都为,0,。得到以下结果：,在直观上不显著谁应先走，实际上，似乎应让,B,先走好些，但可能因为,E,在高速飞行时增加运行费用太昂贵及机上乘客缘故，使模型选定让,E,先走。,37/38,七、总结,模型有易实施特点，可结合于数据库中使用。它可对数目很大机场、任意可装载乘客数及转机乘客数，都可实现快速最优排序，并可处理同时要求起飞请求、照料晚点飞机很久先走功效，及可对不一样型号和不一样油耗飞机进行适当酌情考虑。,模型虽不能对起飞和降落同时到达优化，但却可到达在起飞间隙中安排降落。,能够确信此模型是既可到达使航空企业节约费用，又可到达使用户满意理想模型。,38/38,