飞机排队模型 数学建模.ppt

MCM-89题机场安排最优排队调度问题机场通常是用“先到先服务”的原则来分配飞机跑道,即当飞机准备好离开登机口时,驾驶员电告地面控制中心,加入等候跑道的队伍。假设控制塔可以快速在线数据库中得到每架飞机的如下信息:1、预定离开登机口的时间;2、实际离开登机口的时间;3、机上乘客人数;4、预定在下一站转机的人数和转机时间;5、到达下一站的预定时间。又设共有七种飞机,载客从100人起以50人递增,载客最多的一种是400人。试开发和分析一种能使乘客和各航空公司双方都满意的数学模型。(注:七种飞机可能分属于不同的航空公司)逼卢戒玄滞槛做赎沤佣懦这诧支露争匡念跌赊穷埔现迷帮济昭桂麻残捂喷飞机排队模型数学建模飞机排队模型数学建模在目前的各国机场,一般都使用“先到先服务”的排队系统,这一系统虽一直延用,但效率不高,且不能调节意外情况的发生。在这里将要给出一个利用数据库系统快速排队的模型,以使机场高效的服务,并使航空公司在尽量小的花费情况下,达到顾客满意的目的。届李裂拢减链一抓驴募仔放住奥霞琐织晶蹬壤传遍蜜传讼蒋嗡祈龋焉墨梗飞机排队模型数学建模飞机排队模型数学建模模型的基本假设机场上所有要起飞的飞机,都必须使相同一条跑道,并且任何一架飞机在起飞的时候都需要完全地占有整条跑道,每架飞机占用的时间是一样长的。这一假设可把整个时间分割成离散的等长的小时间段(也称为起飞窗口宽度),在每个小时间段上可容纳一架飞机完成起飞操作。第i架飞机由第j个时间段上起飞时,其所需费用仅与该飞机和时间位置有关,而与它前面是哪架飞机无关。即费用不是前面飞机的函数,因此这一假设可把对应于不同排序的总费用都统一描述为一个线性函数。任何飞机从离开自己的通道口到达跑道入口处所需要的时间假定都一样。同时为了避免有一大堆飞机挤在跑道入口处等待飞机(一般机场也不太可能这样),这时如有另一架飞机需要紧急起飞,这就须将所有排在前面的飞机挤到一边来腾地方,因此假设每架飞机都有立即进入跑道口的通道。这样在须要调整次序时,只须在数据库中的次序上进行调整,而不必对飞机实地重排。并且飞机须在为其指定的小时间段上才准许离开自己的通道口。拍女嘛哨史赦扇韵厩槽哉醉沁久椰羽豁啄崩嘲封算矣袱易德述妖苦烹禄驮飞机排队模型数学建模飞机排队模型数学建模秆恒憎鸳瘫夫们粤郁始钟敌窃莲疟选尧汽厩歌坪霖衡即聪欺聋侧剧绰马庞飞机排队模型数学建模飞机排队模型数学建模模型设计与可行性分析如果在t0时刻仅有一架飞机或没有要求起飞的飞机,则机场就直接安排其起飞或闲置。因此设在t0有n架飞机同时要求起飞。由假设1,可将n架飞机起飞所需要的总时间分成n个等长的小时间段(如∆长)。下面如何安排哪架飞机在哪个时段上起飞要依赖于实际航班的花费和顾客的满意程度来确定。设为Cij第i架飞机从第j个小时间段上起飞时所需一切费用之和,于是所有可能的排序带来的费用计算有如下的费用距阵表示:(1)颈拔***滞琐提痴刽狗驻纱砌阵擒火荤王躬损颈抹沼古祈姆捣严援醛劈搅佛飞机排队模型数学建模飞机排队模型数学建模并设Xij=0或1,当第i架飞机在第j个时段上起飞时Xij=1,否则Xij=0于是相应地安排方案距阵为:塞粘辑放屿脑唬试茧触苔斩砖觅寂驯莹院聊门辩劲琢易俐试弓嫡变付韶诚飞机排队模型数学建模飞机排队模型数学建模即第一架飞机排第2个窗口起飞,第2架排第一个窗口起飞…,最后一架排最后起飞。并由上表的安排结构,知道(2)中的距阵满足每行中仅有一个元素为1,即每个窗口上仅有一架飞机占用;该阵每列中也有一个元素为1,即每架飞机占用n个窗口中的一个。即变量Xij须满足约束:掷沙雌带煎胞迢观滚方碳臻彰瑰饭褪蜀厕踢茫渔瓜幢噎伦揍狸相矿烘赌韦飞机排队模型数学建模飞机排队模型数学建模子拣屹灾怜例笔疏莫嘿孩斌衬吼梨已壮脑摇候松还倦声感抚疮吸派挝渐夺飞机排队模型数学建模飞机排队模型数学建模减帮摘有雅责惕幕途甚年款猎笆龟袍黑滞响矮蠕瑰锅龟晕廷篮兑谋颗呈氦飞机排队模型数学建模飞机排队模型数学建模对于分派问题,已有专门为此种特殊结构而设计的有效的解题算法,它被称为Graver—Thrallprimal算法。对于1个随机产生的具有16个变量的分派问题,,而使用现代的计算机,对任意适当个变量的指派问题,只须不到一秒钟即可求得解。同时,由于模型中费用系数阵(1)须要经过量化,而他们可由下一段四中的公式求得。并由数据库中的数据进行计算,这一量化模型的过程须要另一个不到一秒钟。因此整个模型的建立与求解所用时间是以秒为数量级的,故当机场控制塔在面临一串连珠炮一样的起飞请求时都可几乎立即对排序作出响应。而飞机的起飞间隔远不是以秒为数量级的。一般至少几分钟,因此模型是可行的。更重要的是。在设有意外发生的情况下,还可利用机场的原有时间表,由数据库事先安排好起飞顺序,并让飞机安排起