飞机排队模型_数学建模

《飞机排队模型_数学建模》由会员分享，可在线阅读，更多相关《飞机排队模型_数学建模（38页珍藏版）》请在文档大全上搜索。

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、道口的通道。这样地方，因此假设每架飞机都有立即进入跑道口的通道。这样在须要调整次序时，只须在数据库中的次序上进行调整，而在须要调整次序时，只须在数据库中的次序上进行调整，而不必对飞机实地重排。并且飞机须在为其指定的小时间段上不必对飞机实地重排。并且飞机须在为其指定的小时间段上才准许离开自己的通道口。才准许离开自己的通道口。 4.设设 是一架飞机要按时到达目的地所必须起飞的最是一架飞机要按时到达目的地所必须起飞的最晚时限，并假设如果一架飞机在晚时限，并假设如果一架飞机在 时限以后才起飞，时限以后才起飞，则它必须以最大安全速度飞完全程。则它必须以最大安全速度飞完全程。 （而在（而在 以内起以内起飞

6、者可着情加速） 。飞者可着情加速） 。 5.如果一架飞机在时限如果一架飞机在时限 以后起飞， 则该机上所有需以后起飞， 则该机上所有需转机的乘客都将误下次班机，并设给每个乘客用于赔转机的乘客都将误下次班机，并设给每个乘客用于赔偿重新安排旅行计划的补偿费用是一样的。偿重新安排旅行计划的补偿费用是一样的。 模型设计与可行性分析模型设计与可行性分析 如果在如果在t t0 0时刻仅有一架飞机或没有要求起飞的飞机，则机场就时刻仅有一架飞机或没有要求起飞的飞机，则机场就直接安排其起飞或闲置直接安排其起飞或闲置 。因此设在因此设在t t0 0有有n n架飞机同时要求起飞。架飞机同时要求起飞。由假设由假设1，

7、可将，可将n n架飞机起飞所需要的总时间分成架飞机起飞所需要的总时间分成n n个等长的小时个等长的小时间段（如间段（如长）。下面如何安排哪架飞机在哪个时段上起飞要依长）。下面如何安排哪架飞机在哪个时段上起飞要依赖于实际航班的花费和顾客的满意程度来确定。赖于实际航班的花费和顾客的满意程度来确定。 设为设为C Cijij第第i i架飞机从第架飞机从第j j个小时间段上起飞时所需一切费用之个小时间段上起飞时所需一切费用之和，于是所有可能的排序带来的费用计算有如下的费用距阵表示：和，于是所有可能的排序带来的费用计算有如下的费用距阵表示： 111212122212.nnnnnncccccccccc（1）

8、 并设并设X Xijij=0=0或或1 1，当第，当第i i架飞机在第架飞机在第j j个时段上起飞时个时段上起飞时X Xijij=1=1，否则，否则X Xijij=0=0 于是相应地安排方案距阵为于是相应地安排方案距阵为 ：111212122212.nnnnnnxxxxxxxxxx（2） 由于ijx只取0，1值，故如下的一个距阵（2）即对应一个排序方案： 飞机 窗口 1 2 3 n 1 0 1 0 0 2 1 0 0 0 n 0 0 0 1 即第一架飞机排第即第一架飞机排第2个窗口起飞，第个窗口起飞，第2架架排第一个窗口起飞排第一个窗口起飞，最后一架排最后起飞。并由上表的安排结构，知道（最后一

9、架排最后起飞。并由上表的安排结构，知道（2）中的距）中的距阵满足每行中仅有一个元素为阵满足每行中仅有一个元素为1，即每个窗口上仅有一架飞机占，即每个窗口上仅有一架飞机占用；该阵每列中也有一个元素为用；该阵每列中也有一个元素为1，即每架飞机占用，即每架飞机占用n n个窗口中的个窗口中的一个。即变量一个。即变量X Xijij须满足约束：须满足约束：1nijjx =1 1,2,.,in (3) 1nijix =1 1,2,.,jn 由于由于ijx为取为取 0，1 值的变量，因此不同的分派安值的变量，因此不同的分派安排对应的仅仅是排对应的仅仅是ijx取取 1 的位置不同而已。的位置不同而已。 于于是是

10、设设1c为为安安排排第第一一架架飞飞机机的的费费用用 11111121211.nncc xc xc x 由由此此全全部部飞飞机机安安排排的的总总费费用用为为： 11nnijijijzc x即构成目标函数。 （由于假设即构成目标函数。 （由于假设 2，ijc独立于独立于ijx的取值，的取值，故此目标函数是一线性函数） 。故此目标函数是一线性函数） 。 为求得使为求得使 c达最小的达最小的ijx，构造了如下的线性规划模型：，构造了如下的线性规划模型： minc x 11,1,2,.nijjxin 11,1,2,.,nijixjn 01ijx 或 此模型是一个运输问题的特例此模型是一个运输问题的特例

11、-指派模型，其中指派模型，其中 c=111212122212(,.,.,.,.,)nnnnnnccccccccc为一行向量。为一行向量。 111212122212 x=(,.,.,.,.,)nnnnnnxxxxxxxxx为一列向量，为一列向量，为转为转置符号。置符号。 对于分派问题，已有专门为此种特殊结构而设计的有效的解题对于分派问题，已有专门为此种特殊结构而设计的有效的解题算法，它被称为算法，它被称为GraverThrall primal算法。对于算法。对于1个随机产生的个随机产生的具有具有16个变量的分派问题，最多只须个变量的分派问题，最多只须2.9秒即可完成求解，而使用现秒即可完成求解，