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