飞机排队模型数学建模.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须满足约束： 对于分派问题，已有专门为此种特殊结构而设计的有效的解题 算法，它被称为GraverThrall primal算法。对于1个随机产生的 具有16个变量的分派问题，最多只须2.9秒即可完成求解，而使用现 代的计算机，对任意适当个变量的指派问题，只须不到一秒钟即可 求得解。 同时，由于模型中费用系数阵（1）须要经过量化，而他们 可由下一段四中的公式求得。并由数据库中的数据进行计算， 这一量化模型的过程须要另一个不到一秒钟。因此整个模型的 建立与求解所用时间是以秒为数量级的，故当机场控制塔在面 临一串连珠炮一样的起飞请求时都可几乎立即对排序作出响应 。而飞机的起飞间隔远不是以秒为数量级的。一般至少几分钟 ，因此模型是可行的。 更重要的是。在设有意外发生的情况下，还可利用机场的原有 时间表，由数据库事先安排好起飞顺序，并让飞机安排起飞顺 序起飞，而唯一需要重新安排的情况仅仅发生在有飞机晚点或 紧急的情况，而这时的运算也会在一秒钟左右解决问题。而且 由假设（3），也不会因改变而产生临时的拥挤情况。 四、模型中费用系数阵的量化 由于（1）中的Cij 是第i架飞机从第j个时间段上起飞的费 用，它与一架航班的型号及运行费用和其上载客情况和他们 的满意程度有关，为简化运算，把基本运行费设置为费用零 点，而只考虑由于飞机延迟起飞而引起的费用。这一费用包 括由于晚点而不再以最经济的速度而是以较快或最快速度飞 行带来的燃料损失；及乘客因耽误下站转机而重新安排旅途 的损失；以及顾客因各种延迟带来的不愉快而转化的损失。 将这三者分别归入费用计算并简记为： 费用: 1.燃料附加费 2.乘客误机费 3.乘客不满意的损失 下面分别建立几个费用的计算公式 1.燃料附加费 由于晚点，飞机必须以尽可能快的速度飞行，故燃料随晚 点的时间长短而变化，然而既使晚点，只要为达到最大时限 ，就可以以低于最大安全速度飞行。并在起飞后就可近似地 保持常速，因此燃料消耗在时间内应恒定，由于不知道燃料 消耗如何随飞行速度变化，选用了近似的线性函数，即单位 时间增加油耗的费用函数为： 由此公式看出，飞机晚点越久，则耗油越多，直至它 在离开时即以最大速度起飞（假设4）。 下面为了建模讨论的方便，将上述公式中及以后 要用到的一些参数给出一个总表： 2.乘客误机费 设为乘客耽误了转机而必须补偿的费用，这里取为常数（ 假设5）。如果对各人的补偿费确实不同，则取为各人费用 的数学期望-平均值，且重新安排旅程只发生在飞机晚点 时间超过了时限时才发生，故费用如下计算 3.乘客不满意的损失 由于飞机晚点越多，则乘客会越不满意，如果仅晚点一两分钟， 则顾客不会太不愿意；但如果晚点到误了转乘班机，则该乘客会顿 时变得焦躁不安并且非常愤怒，这一情况可以适当地摘述为一个指 数增长函数附加一个阶跃函数，则总的费用函数为： 但是只要将要到达的飞机一准备好降落，就可以准许其降 落的话，这模型仍适用，这只要将 为了防止那些还未准备好的飞机，在就绪之前就对其发出起飞 的命令，置一架飞机在它预定起飞时间以前的某窗口起飞的损 失为无穷大，并假如考虑1，2，3中的费用，得到计算费用的 通式： 4.排队模型小结： 2)求解线性规划模型（指派模型）的最优解，则可确定哪架飞机 在什么时刻起飞； 在正常运行情况下，上述小结中1），2）步骤仅须做一次即可按 部就班地运行，只有当意外发生时才启用3）部分。 五.模型检验 最重要的模型检验即在于检验此模型是否具有意义，编了一个 用单纯形法解线性规划的程序以及几个简单的例子来检查模型运 行的良好性，在后面第六部分中的具体结果中，可以看出所有结 果都与所期待的直观判断相吻合。随后，又进行了更彻底的检验 ；变动其中的参数，测试更为复杂的例子，以至实际运作此系统 ，如果实际运行的结果显示出为航空公司节省了开支，同时又能 维持顾客满意度在一个可接受的水平，则此模型将取得圆满成功 。 下面先进行的是变动其中参数的检验，即在参数受到扰动的情 况下模型是否稳定的检验，如果这个模型中一个或几个参数有轻 微的偏离真值，而模型结果不致有太大的偏离最优解，则可认为 模型是稳定的。另外,如果参数的微小变化带来模型的剧烈变化 ，则希望确定哪个参数更敏感。这样确定它时将利用更多的信息 ，以达到准确。 下面将指派模型（4）表运输模型： 由运输模型的有关理论知：运输问题有可行解，并对（9） 这样的运输模型，一定有一个最优且此最优的所有分量都取整 数值。又注意到约束条件（9）的限制，则可能的整数解一定非 0即1，因此运输问题等价于原问题（4）。将（9）式由目标函 数的向量形式（见（4）式定义）表出： 六、计算机模拟模型 为了了解模型运行的良好性，以及本模型的特点，用下述几 个计算机模拟例子来进行演示。 显然；理论模型要比计算机模型要少受限制。为了编程简单 并说明问题，在原有的基本假定基础上，再添加如下具体假定： 1. 1、在每一窗口至多有三架飞机已准备好可以起飞，当仅有 两架飞机准备好的情况发生时，可加入一个虚拟变量，以其对相应 的费用系数都为0即可。 2、凭直观给模型指定了参数值，在实际中，这些值应该通 过实验室或调查获得： 每一个起飞窗口为一分钟长，即任何飞机起飞需要至多一分钟 ，而且其他飞机不准在一分钟内占用跑道； 设有飞机降落情况； 误转机的赔偿费为每人350； 误了转机的乘客的愤怒长度等价于被耽误了15分钟的乘客的两倍 。 例1 （具有使最多乘客的飞机先走的功能） 考虑在早晨6：00，三架飞机同时要求起飞设他们的型号相同， 有距此机场相同距离的终点机场，（但可能飞往不同城市的机场） 。设三架飞机为A，B，C。并且他们都预定在7：20到达终点，但 A飞机上有350名乘客；B飞机上有100名；C飞机上有400名。且每 架飞机上都有100名乘客要求转机，计算结果见表1。 例2 （具有使晚点飞机最久者先走的功能 ） 当飞机C准备离开之际，飞机D要求紧急起飞。飞机D已经晚点 18分钟，它若想按时在7：06分到达终点，就必须在2分钟内起飞。 其上有200名乘客，150人要求转机，表2给出了结果 例3（具有按情况决定先后的功能） 假设又过了两分钟，这时D和A已走，剩下B已经晚点3分钟，而另 一架飞机E在此刻要求起飞。设E有如下条件： 1）按时准备就绪； 2）在可按时到达终点（7：42）之前，还富余42分钟可以闲置 ； （ 3）机上有122名乘客，89人要求转机； （ 4）晚点增加的费用为每分钟450。 编程序来解此题，如所设引入一个虚拟变量，飞机X，这一 飞机的一切费用系数都为0。得到如下结果： 在直观上不明显谁应先走，事实上，似乎应让B先走好些， 但可能由于E在高速飞行时增加的运行费用太昂贵及机上乘客的