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

《飞机排队模型数学建模.ppt》由会员分享，可在线阅读，更多相关《飞机排队模型数学建模.ppt（38页珍藏版）》请在一课资料网上搜索。

1、MCM-89题机场安排最优排队调度问题题机场安排最优排队调度问题 机场通常是用“先到先服务”的原则来分配飞机跑道，即当飞机准备好离开登机口时，驾驶员电告地面控制中心，加入等候跑道的队伍。假设控制塔可以快速在线数据库中得到每架飞机的如下信息： 1、预定离开登机口的时间； 2、实际离开登机口的时间； 3、机上乘客人数； 4、预定在下一站转机的人数和转机时间； 5、到达下一站的预定时间。 又设共有七种飞机，载客从100人起以50人递增，载客最多的一种是400人。试开发和分析一种能使乘客和各航空公司双方都满意的数学模型。（注：七种飞机可能分属于不同的航空公司） 在目前的各国机场，一般都使用在目前的各国

2、机场，一般都使用“先到先到先服务先服务”的排队系统，这一系统虽一直延用，的排队系统，这一系统虽一直延用，但效率不高，且不能调节意外情况的发生。但效率不高，且不能调节意外情况的发生。在这里将要给出一个利用数据库系统快速排在这里将要给出一个利用数据库系统快速排队的模型，以使机场高效的服务，并使航空队的模型，以使机场高效的服务，并使航空公司在尽量小的花费情况下，达到顾客满意公司在尽量小的花费情况下，达到顾客满意的目的。的目的。模型的基本假设模型的基本假设 机场上所有要起飞的飞机，都必须使相同一条跑道，并且任机场上所有要起飞的飞机，都必须使相同一条跑道，并且任何一架飞机在起飞的时候都需要完全地占有整条

3、跑道，每架何一架飞机在起飞的时候都需要完全地占有整条跑道，每架飞机占用的时间是一样长的。这一假设可把整个时间分割成飞机占用的时间是一样长的。这一假设可把整个时间分割成离散的等长的小时间段（也称为起飞窗口宽度），在每个小离散的等长的小时间段（也称为起飞窗口宽度），在每个小时间段上可容纳一架飞机完成起飞操作。时间段上可容纳一架飞机完成起飞操作。第第i i架飞机由第架飞机由第j j个时间段上起飞时，其所需费用仅与该飞机个时间段上起飞时，其所需费用仅与该飞机和时间位置有关，而与它前面是哪架飞机无关。即费用不是和时间位置有关，而与它前面是哪架飞机无关。即费用不是前面飞机的函数，因此这一假设可把对应于不同

4、排序的总费前面飞机的函数，因此这一假设可把对应于不同排序的总费用都统一描述为一个线性函数。用都统一描述为一个线性函数。任何飞机从离开自己的通道口到达跑道入口处所需要的时间任何飞机从离开自己的通道口到达跑道入口处所需要的时间假定都一样。同时为了避免有一大堆飞机挤在跑道入口处等假定都一样。同时为了避免有一大堆飞机挤在跑道入口处等待飞机（一般机场也不太可能这样），这时如有另一架飞机待飞机（一般机场也不太可能这样），这时如有另一架飞机需要紧急起飞，这就须将所有排在前面的飞机挤到一边来腾需要紧急起飞，这就须将所有排在前面的飞机挤到一边来腾地方，因此假设每架飞机都有立即进入跑道口的通道。这样地方，因此假设

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

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

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

8、 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 的的位位置置不不同同而而已已。 于于是是设设1c为为安安排排第第一一架架飞飞机机的

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

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

12、问题，只须不到一秒钟即可代的计算机，对任意适当个变量的指派问题，只须不到一秒钟即可求得解。求得解。 同时，由于模型中费用系数阵（同时，由于模型中费用系数阵（1）须要经过量化，而他们可由）须要经过量化，而他们可由下一段四中的公式求得。并由数据库中的数据进行计算，这一量化下一段四中的公式求得。并由数据库中的数据进行计算，这一量化模型的过程须要另一个不到一秒钟。因此整个模型的建立与求解所模型的过程须要另一个不到一秒钟。因此整个模型的建立与求解所用时间是以秒为数量级的，故当机场控制塔在面临一串连珠炮一样用时间是以秒为数量级的，故当机场控制塔在面临一串连珠炮一样的起飞请求时都可几乎立即对排序作出响应。而

13、飞机的起飞间隔远的起飞请求时都可几乎立即对排序作出响应。而飞机的起飞间隔远不是以秒为数量级的。一般至少几分钟，因此模型是可行的。不是以秒为数量级的。一般至少几分钟，因此模型是可行的。更重要的是。在设有意外发生的情况下，还可利用机场的原有时间更重要的是。在设有意外发生的情况下，还可利用机场的原有时间表，由数据库事先安排好起飞顺序，并让飞机安排起飞顺序起飞，表，由数据库事先安排好起飞顺序，并让飞机安排起飞顺序起飞，而唯一需要重新安排的情况仅仅发生在有飞机晚点或紧急的情况，而唯一需要重新安排的情况仅仅发生在有飞机晚点或紧急的情况，而这时的运算也会在一秒钟左右解决问题。而且由假设（而这时的运算也会在一

14、秒钟左右解决问题。而且由假设（3 3），也不），也不会因改变而产生临时的拥挤情况。会因改变而产生临时的拥挤情况。四、模型中费用系数阵的量化四、模型中费用系数阵的量化 由于（由于（1）中的）中的C Cijij 是第是第i i架飞机从第架飞机从第j j个时间段上起飞的费用，个时间段上起飞的费用，它与一架航班的型号及运行费用和其上载客情况和他们的满意程它与一架航班的型号及运行费用和其上载客情况和他们的满意程度有关，为简化运算，把基本运行费设置为费用零点，而只考虑度有关，为简化运算，把基本运行费设置为费用零点，而只考虑由于飞机延迟起飞而引起的费用。这一费用包括由于晚点而不再由于飞机延迟起飞而引起的费用

15、。这一费用包括由于晚点而不再以最经济的速度而是以较快或最快速度飞行带来的燃料损失；及以最经济的速度而是以较快或最快速度飞行带来的燃料损失；及乘客因耽误下站转机而重新安排旅途的损失；以及顾客因各种延乘客因耽误下站转机而重新安排旅途的损失；以及顾客因各种延迟带来的不愉快而转化的损失。将这三者分别归入费用计算并简迟带来的不愉快而转化的损失。将这三者分别归入费用计算并简记为：记为： 费用费用: 1.燃料附加费燃料附加费 2.乘客误机费乘客误机费 3.乘客不满意的损失乘客不满意的损失 下面分别建立几个费用的计算公式下面分别建立几个费用的计算公式 1.燃料附加费燃料附加费 由于晚点，飞机必须以尽可能快的速

16、度飞行，故燃料随晚点的由于晚点，飞机必须以尽可能快的速度飞行，故燃料随晚点的时间长短而变化，然而既使晚点，只要为达到最大时限，就可以时间长短而变化，然而既使晚点，只要为达到最大时限，就可以以低于最大安全速度飞行。并在起飞后就可近似地保持常速，因以低于最大安全速度飞行。并在起飞后就可近似地保持常速，因此燃料消耗在时间内应恒定，由于不知道燃料消耗如何随飞行速此燃料消耗在时间内应恒定，由于不知道燃料消耗如何随飞行速度变化，选用了近似的线性函数，即单位时间增加油耗的费用函度变化，选用了近似的线性函数，即单位时间增加油耗的费用函数为：数为： 0k t t 0( )F t （/单位时间） 0k t 其中扣

17、除了飞行的一般油耗， 只计入增加的油耗， 并且式中：其中扣除了飞行的一般油耗， 只计入增加的油耗， 并且式中： t：为飞机晚点的时间； （为飞机晚点的时间； （t=0 即为飞机预定起飞的时间） ；即为飞机预定起飞的时间） ；实际上实际上t作为压缩因子。作为压缩因子。 0k： 为晚点单位时间由加速引起的增加油耗的价格， 同时： 为晚点单位时间由加速引起的增加油耗的价格， 同时0k与与不同引擎的飞机有关。不同引擎的飞机有关。 又由于飞机蚝油总数还与飞行距离有关，因此总费又由于飞机蚝油总数还与飞行距离有关，因此总费用应为用应为max0)(vdtF， 其中， 其中 d为飞行距离， 它可由为飞行距离，

18、它可由d=max()AvT计计算，算，AT为飞机预定到达时间，为飞机预定到达时间，maxv为最大安全飞行速度，为最大安全飞行速度，是常数。是常数。因此将常数因此将常数 maxv并入并入 0k中，记为中，记为 0k于是有一架于是有一架飞机因晚点增加的总费用为：飞机因晚点增加的总费用为： 由此公式看出，飞机晚点越久，则耗油越多，直至它在离由此公式看出，飞机晚点越久，则耗油越多，直至它在离开时即以最大速度起飞（假设开时即以最大速度起飞（假设4）。）。 下面为了建模讨论的方便，将上述公式中及以后要用下面为了建模讨论的方便，将上述公式中及以后要用到的一些参数给出一个总表：到的一些参数给出一个总表： ()

19、Akt T t ( )F t （5） ()Akt T t 模型参数总表模型参数总表 0t：第一个窗口（小时间段：第一个窗口（小时间段 ）的起始时间；）的起始时间； t：飞机晚点时间，或从：飞机晚点时间，或从 0t计起，飞机真正起飞时间；计起，飞机真正起飞时间； :dt为一架飞机预定起飞的时间（为一架飞机预定起飞的时间（ d 为为 departure）; AT：为一架飞机预定到达的时间（：为一架飞机预定到达的时间（A 为为 Arrive）; ：为等长的时间间隔时间段的长度，也称为起飞窗口；：为等长的时间间隔时间段的长度，也称为起飞窗口； j：为第：为第 j个窗口的标号；个窗口的标号； k：用来决

20、定某飞机单位时间增加燃料费用的常系数，它一般与飞：用来决定某飞机单位时间增加燃料费用的常系数，它一般与飞机型号有关；机型号有关； maxv：一种飞机的：一种飞机的最大安全飞行速度；最大安全飞行速度； avv：一种飞机按时起飞的平均速度，它也与飞机型号有关；：一种飞机按时起飞的平均速度，它也与飞机型号有关；（av,acerage） r:用来计算耽误了转机的乘客重新安排旅程的费用；用来计算耽误了转机的乘客重新安排旅程的费用； ：机上须转乘的人数；：机上须转乘的人数； :p机上登机的总人数；机上登机的总人数； a：将由晚点而引起的乘客的不满意程度转换成美元的：将由晚点而引起的乘客的不满意程度转换成美

21、元的转换系数；转换系数； b：将由晚点而耽误转机的乘客的愤怒转换成美元的转换系数；：将由晚点而耽误转机的乘客的愤怒转换成美元的转换系数； a：反映乘客对晚点不满意上升的快慢程度的因子；：反映乘客对晚点不满意上升的快慢程度的因子； ijc：第：第 i架飞机在第架飞机在第 j个窗口起飞的总费用；个窗口起飞的总费用； 于是于是，0(1)dtttj， 这里要求0dtt，因为如果飞机未准备好而令其起飞，则该窗口将不能很好的利用。只有当它的预定时间到时，才可考虑它在第 j个 （1j ） 窗口起飞的问题， 并计算式 （5）中 maxAdTv ()AdavdTT v 2.2.乘客误机费乘客误机费 设为乘客耽误

22、了转机而必须补偿的费用，这里取为常数（假设设为乘客耽误了转机而必须补偿的费用，这里取为常数（假设5）。如果对各人的补偿费确实不同，则取为各人费用的数学期）。如果对各人的补偿费确实不同，则取为各人费用的数学期望望-平均值，且重新安排旅程只发生在飞机晚点时间超过了时平均值，且重新安排旅程只发生在飞机晚点时间超过了时限时才发生，故费用如下计算限时才发生，故费用如下计算 ( )()R tr u t （6） ：为为须须转转乘乘的的人人数数； ( ):u t为为单单位位阶阶跃跃函函数数，即即00()10tutt 由假设由假设 5，如果飞机晚点，则所有须转机的，如果飞机晚点，则所有须转机的 个乘客都将个乘客

23、都将将误了转机，若放宽此条件，则将误了转机，若放宽此条件，则 ( )R t将是一些阶跃函数之和将是一些阶跃函数之和（当相应顾客晚点时，其对应的函数变为（当相应顾客晚点时，其对应的函数变为 1） 。） 。 3.乘客不满意的损失乘客不满意的损失 由于飞机晚点越多，则乘客会越不满意，如果仅晚点一两分钟，由于飞机晚点越多，则乘客会越不满意，如果仅晚点一两分钟，则顾客不会太不愿意；但如果晚点到误了转乘班机，则该乘客会顿则顾客不会太不愿意；但如果晚点到误了转乘班机，则该乘客会顿时变得焦躁不安并且非常愤怒，这一情况可以适当地摘述为一个指时变得焦躁不安并且非常愤怒，这一情况可以适当地摘述为一个指数增长函数附加

24、一个阶跃函数，则总的费用函数为：数增长函数附加一个阶跃函数，则总的费用函数为： ( )(1)()atD teaPb u t （7） 其中 ,ab都是常数，且 :p为乘客数；为乘客数； ：为要转乘的乘客数；：为要转乘的乘客数； ：为反映乘客等待时不满意上升快慢的因子；：为反映乘客等待时不满意上升快慢的因子； 1ate ：中（：中（-1）是为了使）是为了使 0t （即飞机准时起飞）（即飞机准时起飞）时最小的不满意置零的项；时最小的不满意置零的项； , a b：为将相应的不满意转化为美元的系数；：为将相应的不满意转化为美元的系数； ():u t为单位阶跃函数， 它表达了因误机而顿时产生为单位阶跃函数

25、， 它表达了因误机而顿时产生的不满意。的不满意。 常数常数, a b一般不相等，这是由于误了转机的乘客一般一般不相等，这是由于误了转机的乘客一般要只是晚了一会的乘客不满意程度要大得多些。要只是晚了一会的乘客不满意程度要大得多些。 综综上上所所述述。则则费费用用系系数数 ijc为为由由于于第第i架架飞飞机机从从第第 j个个窗窗口口起起飞飞时时增增加加燃燃料料、重重新新安安排排旅旅程程、和和不不满满意意程程度度而而引引起起的的三三项项费费用用的的总总和和。 在假设在假设3中规定每架飞机从离开自己的通道口到达跑中规定每架飞机从离开自己的通道口到达跑道入口所需要的时间是一样的， 这一假定可使得我们置道

26、入口所需要的时间是一样的， 这一假定可使得我们置预定时间为预定时间为 0t ，并加入计算（，并加入计算（5） 、 （） 、 （6） 、 （） 、 （7）式。）式。如如果这条假设放宽， 则可令果这条假设放宽， 则可令 t等于对应飞机所需时间为起等于对应飞机所需时间为起点，而取代原式中的点，而取代原式中的 0t ，即如（，即如（5）式中：）式中： ()AKt T 0tt ( )F t ()AKt T t 其其中中0t为为起起飞飞时时间间，当当0tt时时，才才附附加加油油耗耗。 模型还可以在某种条件下处理降落的请求，但不能同时模型还可以在某种条件下处理降落的请求，但不能同时对起飞和降落都达到最优排序

27、。对起飞和降落都达到最优排序。如果要做到此项，则费用如果要做到此项，则费用系数系数 ijc将依赖于前面的飞机的排序情况， 因此目标函数将将依赖于前面的飞机的排序情况， 因此目标函数将不在是线性的了不在是线性的了。 但是只要将要到达的飞机一准备好降落，就可以准许其降但是只要将要到达的飞机一准备好降落，就可以准许其降落的话，这模型仍适用，这只要将落的话，这模型仍适用，这只要将t；设为飞机将要达到的时间；设为飞机将要达到的时间； ：设为一架飞机着陆并最终不再占用跑道所需的时间。：设为一架飞机着陆并最终不再占用跑道所需的时间。 为了防止那些还未准备好的飞机，在就绪之前就对其发出起飞为了防止那些还未准备

28、好的飞机，在就绪之前就对其发出起飞的命令，置一架飞机在它预定起飞时间以前的某窗口起飞的损的命令，置一架飞机在它预定起飞时间以前的某窗口起飞的损失为无穷大，并假如考虑失为无穷大，并假如考虑1，2，3中的费用，得到计算费用的中的费用，得到计算费用的通式：通式： ttd ijc= ()(1)atAK Tteap 0tt ()(1)atAK Treapb t 这这里里 0(1)dtttj amax()AdvATT vTv 1,2,., ,1,2,.,in jn 由于有上述的统一公式，则原设在由于有上述的统一公式，则原设在 0t时刻有时刻有 n架飞机架飞机可扩展到一天有可扩展到一天有 n架飞机要求起飞的

29、情形。架飞机要求起飞的情形。模型中的参模型中的参数数 , ,dAt Tp都可由数据库提供，而事先给定的参数（或机都可由数据库提供，而事先给定的参数（或机场设定的）为场设定的）为 max, ,avk vvr及变量及变量 t都容易算出来。都容易算出来。0t可由可由计算机系统时钟提供。计算机系统时钟提供。而三个参数而三个参数 , ,ab可由飞机以往可由飞机以往记录和惯例估算出来。记录和惯例估算出来。 4.4.排队模型小结：排队模型小结： 1） 对每架飞机都有一个起飞点对每架飞机都有一个起飞点 dt，终点，终点 ,AT0t为凌晨为凌晨12.01，则带入公式，则带入公式 ijc可求得它在第可求得它在第

30、j个窗口起飞时个窗口起飞时的费用， （可把机场所有飞机都算在内共的费用， （可把机场所有飞机都算在内共 n架） ；架） ； 2)2)求解线性规划模型（指派模型）的最优解，则可确定哪架飞求解线性规划模型（指派模型）的最优解，则可确定哪架飞机在什么时刻起飞；机在什么时刻起飞；3)当当有有特特殊殊情情况况发发生生后后，则则重重新新置置剩剩下下的的飞飞机机为为1,2,.,in， 起起点点为为当当时时的的 0t时时刻刻， 将将剩剩余余飞飞机机重重排排后后求求解解，然然后后按按顺顺序序起起飞飞 在正常运行情况下，上述小结中在正常运行情况下，上述小结中1），），2）步骤仅须做一次即可按）步骤仅须做一次即可按

31、部就班地运行，只有当意外发生时才启用部就班地运行，只有当意外发生时才启用3）部分。）部分。 五五. .模型检验模型检验 最重要的模型检验即在于检验此模型是否具有意义，编了一个最重要的模型检验即在于检验此模型是否具有意义，编了一个用单纯形法解线性规划的程序以及几个简单的例子来检查模型运用单纯形法解线性规划的程序以及几个简单的例子来检查模型运行的良好性，在后面第六部分中的具体结果中，可以看出所有结行的良好性，在后面第六部分中的具体结果中，可以看出所有结果都与所期待的直观判断相吻合。随后，又进行了更彻底的检验；果都与所期待的直观判断相吻合。随后，又进行了更彻底的检验；变动其中的参数，测试更为复杂的例

32、子，以至实际运作此系统，变动其中的参数，测试更为复杂的例子，以至实际运作此系统，如果实际运行的结果显示出为航空公司节省了开支，同时又能维如果实际运行的结果显示出为航空公司节省了开支，同时又能维持顾客满意度在一个可接受的水平，则此模型将取得圆满成功。持顾客满意度在一个可接受的水平，则此模型将取得圆满成功。 下面先进行的是变动其中参数的检验，即在参数受到扰动的情下面先进行的是变动其中参数的检验，即在参数受到扰动的情况下模型是否稳定的检验，如果这个模型中一个或几个参数有轻况下模型是否稳定的检验，如果这个模型中一个或几个参数有轻微的偏离真值，而模型结果不致有太大的偏离最优解，则可认为微的偏离真值，而模

33、型结果不致有太大的偏离最优解，则可认为模型是稳定的。另外模型是稳定的。另外, ,如果参数的微小变化带来模型的剧烈变化，如果参数的微小变化带来模型的剧烈变化，则希望确定哪个参数更敏感。这样确定它时将利用更多的信息，则希望确定哪个参数更敏感。这样确定它时将利用更多的信息，以达到准确。以达到准确。 虽然利用分派模型对求解很有效， 但在作敏感性分析时却不虽然利用分派模型对求解很有效， 但在作敏感性分析时却不在适应。在适应。因为在进行敏感性分析时，变量的限制因为在进行敏感性分析时，变量的限制 0,1ijx 将不将不利于分析扰动情况， 为此我们必须利用分派模型是运输模型利于分析扰动情况， 为此我们必须利用

34、分派模型是运输模型的特列事实，并将的特列事实，并将 0,1ijx 的限制换成取一组非负整数的限的限制换成取一组非负整数的限制，即约束条件化为制，即约束条件化为 0ijx ，并利用运输模型是一类线性规，并利用运输模型是一类线性规划模型的事实，即可用单纯形求解。划模型的事实，即可用单纯形求解。 下面将指派模型（下面将指派模型（4）表运输模型：）表运输模型： 11minnnijijijc x 11nijjx 1,2,.,in （9） 11nijix 1,2,.,jn 0,ijx 1,2,.,in 1,2,.,jn 由运输模型的有关理论知：运输问题有可行解，并对（由运输模型的有关理论知：运输问题有可行

35、解，并对（9）这样的运输模型，一定有一个最优且此最优的所有分量都取整这样的运输模型，一定有一个最优且此最优的所有分量都取整数值。又注意到约束条件（数值。又注意到约束条件（9）的限制，则可能的整数解一定非）的限制，则可能的整数解一定非0 0即即1，因此运输问题等价于原问题（，因此运输问题等价于原问题（4）。将（）。将（9）式由目标函）式由目标函数的向量形式（见（数的向量形式（见（4）式定义）表出：）式定义）表出： minc x Axb （10） 0 x 其中其中b的所有分量为的所有分量为 1，A 的元素为的元素为 0，1，对应约束，对应约束（9） 中的等式， 就可利用线性规划模型的结果来检验参数

36、） 中的等式， 就可利用线性规划模型的结果来检验参数的敏感性了。的敏感性了。 显然显然 A 和和 b 的元素只有的元素只有 0 和和 1，对给定了飞机数目，对给定了飞机数目后是相对固定的，因此参数所产生的变化只影响向量后是相对固定的，因此参数所产生的变化只影响向量 c，假设得到一个最优解，假设得到一个最优解 *x，并假定已解决了其对偶问，并假定已解决了其对偶问题：题： maxb y A yc （11） 其中y为列向量， 维数与 A 阵的行数相同， A,b,c 阵都如 （10）式，由对偶定理知：若原问题（10）或对偶问题存在有限最优解，则另一个亦有有限最优解，且有minc x=maxb y（*y

37、为对偶问题的最优解） ， 现在给 c一个增量 （扰动）,c则记ccc，将 c 带入 （10） 和 （11） 式， 看其对原模型带来何影响， 由 （10）式中的约束Axb，0 x ， 知其未受 c 的影响， 故原最优解 *x仍是原问题的一个可行解，但它有可能不再是最优解了。而保持 *x仍是最优解的充要条件，为：*A yC，即 *CcA y，此式可作为判断原解在扰动下是否仍保持最优（即稳定）的判别条件，但当上述条件不满足时，*x不再是最优解，此时目标函数的新值为 *()min()Zc xccxc xZcx 即即 Z 的的变变化化是是关关于于c的的线线性性函函数数，因因此此只只要要 c的的分分量量变

38、变化化很很小小，则则指指派派问问题题的的不不确确定定性性也也将将很很小小。 由于由于 c是费用系数向量，由它计算公式（是费用系数向量，由它计算公式（5）（8）即可）即可看出它的不确定性来自两个方面。一个方面是来自实际参看出它的不确定性来自两个方面。一个方面是来自实际参数的准确度（如燃料费用、误机费等） ，对于航空公司来说数的准确度（如燃料费用、误机费等） ，对于航空公司来说是一个确切的已知量；而另一方面来自与乘客不满意的费是一个确切的已知量；而另一方面来自与乘客不满意的费用有关的参数，如用有关的参数，如 , ,ab三参数（不满增长因子及费用转换三参数（不满增长因子及费用转换系数） ， 而模型的

39、主要误差将来源于此三者， 并且解对系数） ， 而模型的主要误差将来源于此三者， 并且解对 a最最为敏感，因为为敏感，因为 a是在指数部分，下面决定这三个心理参数是在指数部分，下面决定这三个心理参数是如何影响是如何影响 Z 变化的。变化的。 假假设设得得到到了了相相应应的的 , ,ab的的估估计计及及相相关关联联的的不不确确定定性性（扰扰动动方方差差） ： ,abaab 其中其中 a表示表示 a 的估计，可由统计方面的顾问来决定，他可经的估计，可由统计方面的顾问来决定，他可经过飞行情况数据的研究及顾客的不满意在长期运营中实际为过飞行情况数据的研究及顾客的不满意在长期运营中实际为顾客赔偿的损失中估

40、计顾客赔偿的损失中估计，a表示估计与真值的误差方差，余表示估计与真值的误差方差，余者类似。者类似。则将（则将（8）式中的）式中的 ijc分别对分别对 , ,ab求偏导得：求偏导得： (1);ijijijatatcccepteapab 则则 ijc由由 , ,ab引引起起的的不不稳稳定定性性变变化化， 可可由由全全增增量量公公式式近近似似表表示示： ijijijijccccabab 并并可可进进一一步步假假设设各各参参数数的的变变动动之之间间相相互互独独立立，因因此此由由独独立立和和方方差差公公式式有有 ijc的的方方差差为为： 2222222222222()()()(1) ()ijijijij

41、atatccccababa epbte ap 同同理理，对对 11nnijijijZC x有有 ijijzxC， 故故 Z 的的方方差差 2z可可由由下下式式给给出出： 222221111()()nnnnzijijijijijijzxc 因因此此带带入入 , ,ab及及 222,ab等等数数据据，则则可可算算得得 2z的的值值，为为了了达达到到要要求求的的 2z，还还可可进进一一步步对对各各参参数数的的精精度度加加以以要要求求，但但通通过过求求出出 2z即即可可对对模模型型在在随随机机扰扰动动下下的的不不稳稳定定性性的的方方差差有有所所估估计计了了。 六、计算机模拟模型六、计算机模拟模型 为了

42、了解模型运行的良好性，以及本模型的特点，用下述几为了了解模型运行的良好性，以及本模型的特点，用下述几个计算机模拟例子来进行演示。个计算机模拟例子来进行演示。 显然；理论模型要比计算机模型要少受限制。为了编程简单显然；理论模型要比计算机模型要少受限制。为了编程简单并说明问题，在原有的基本假定基础上，再添加如下具体假定：并说明问题，在原有的基本假定基础上，再添加如下具体假定： 1. 1、在每一窗口至多有三架飞机已准备好可以起飞，当仅有在每一窗口至多有三架飞机已准备好可以起飞，当仅有两架飞机准备好的情况发生时，可加入一个虚拟变量，以其对相应两架飞机准备好的情况发生时，可加入一个虚拟变量，以其对相应的

43、费用系数都为的费用系数都为0即可。即可。 2 2、凭直观给模型指定了参数值，在实际中，这些值应该通、凭直观给模型指定了参数值，在实际中，这些值应该通过实验室或调查获得：过实验室或调查获得： 每一个起飞窗口为一分钟长，即任何飞机起飞需要至多一分每一个起飞窗口为一分钟长，即任何飞机起飞需要至多一分钟，而且其他飞机不准在一分钟内占用跑道；钟，而且其他飞机不准在一分钟内占用跑道； 设有飞机降落情况；设有飞机降落情况； 误转机的赔偿费为每人误转机的赔偿费为每人350； 误了转机的乘客的愤怒长度等价于被耽误了误了转机的乘客的愤怒长度等价于被耽误了15分钟的乘客的两倍。分钟的乘客的两倍。 例例1 （具有使最

44、多乘客的飞机先走的功能）（具有使最多乘客的飞机先走的功能） 考虑在早晨考虑在早晨6：00，三架飞机同时要求起飞设他们的型号相同，三架飞机同时要求起飞设他们的型号相同，有距此机场相同距离的终点机场，（但可能飞往不同城市的机场）。有距此机场相同距离的终点机场，（但可能飞往不同城市的机场）。设三架飞机为设三架飞机为A，B，C。并且他们都预定在。并且他们都预定在7：20到达终点，但到达终点，但A飞机上有飞机上有350名乘客；名乘客；B飞机上有飞机上有100名；名；C飞机上有飞机上有400名。且每架名。且每架飞机上都有飞机上都有100名乘客要求转机，计算结果见表名乘客要求转机，计算结果见表1。 表表 1

45、 具有最多乘客的飞机先走的功能演示具有最多乘客的飞机先走的功能演示 飞机飞机 乘客乘客 费用距阵费用距阵 最优解距阵最优解距阵 X A B C 350 100 400 0.00 0.00 0.00 0.48 0.41 0.50 0.97 0.83 1.00 0 0 1 1 0 0 0 1 0 最最低低费费用用 minZ=0.31，最最优优解解距距阵阵表表明明 C，A，B 是是最最优优排排序序，这这与与常常识识相相符符。由由于于其其他他条条件件设设定定一一样样，故故最最优优的的安安排排是是让让乘乘客客多多者者先先走走。 例例2 （具有使晚点飞机最久者先走的功能（具有使晚点飞机最久者先走的功能 ）

46、 当飞机当飞机C准备离开之际，飞机准备离开之际，飞机D要求紧急起飞。飞机要求紧急起飞。飞机D已经晚点已经晚点18分钟，它若想按时在分钟，它若想按时在7：06分到达终点，就必须在分到达终点，就必须在2分钟内起飞。分钟内起飞。其上有其上有200名乘客，名乘客，150人要求转机，表人要求转机，表2给出了结果给出了结果 表表 3 一一飞飞机机已已晚晚点点很很久久的的结结果果（表表中中第第二二例例为为：机机上上人人数数/转转乘乘人人数数） 飞飞机机 乘乘客客 晚晚点点 费费用用系系数数距距阵阵 最最优优解解 D 210/150 18min 0.82 0.92 1.00 1 0 0 B 100/100 1

47、min 0.07 0.15 0.22 0 0 1 A 350/100 1min 0.09 0.17 0.26 0 1 0 最低费用为最低费用为 minZ=1.22,最优起飞顺序为最优起飞顺序为 D，B，A，与，与直观吻直观吻合：即晚点很久者应优先走，否则航空公司就须付误机费了。合：即晚点很久者应优先走，否则航空公司就须付误机费了。标准化了的费用距阵标准化了的费用距阵 C 表明飞机表明飞机 D 花费很大。花费很大。 而另外两个却而另外两个却相对很小。相对很小。 例例3 3（具有按情况决定先后的功能）（具有按情况决定先后的功能） 假设又过了两分钟，这时假设又过了两分钟，这时D和和A已走，剩下已走，

48、剩下B已经晚点已经晚点3分钟，而另分钟，而另一架飞机一架飞机E在此刻要求起飞。设在此刻要求起飞。设E有如下条件：有如下条件： 1 1）按时准备就绪；）按时准备就绪； 2 2）在可按时到达终点（）在可按时到达终点（7：42）之前，还富余）之前，还富余42分钟可以闲置分钟可以闲置；（ 3 3）机上有）机上有122名乘客，名乘客，89人要求转机；人要求转机；（ 4 4）晚点增加的费用为每分钟）晚点增加的费用为每分钟450。 编程序来解此题，如所设引入一个虚拟变量，飞机编程序来解此题，如所设引入一个虚拟变量，飞机X，这一，这一飞机的一切费用系数都为飞机的一切费用系数都为0。得到如下结果：。得到如下结果

49、： 表表 4 按情况决定排序按情况决定排序 飞机飞机 乘客乘客 晚 点晚 点时间时间 费用距阵费用距阵 最优解最优解 B 100/100 3min 0.60 0.80 1.00 0 1 0 E 122/89 0min 0.00 0.28 0.56 1 0 0 X 0/0 0min 0.00 0.00 1.00 0 0 1 在直观上不明显谁应先走，事实上，似乎应让在直观上不明显谁应先走，事实上，似乎应让B先走好些，先走好些，但可能由于但可能由于E在高速飞行时增加的运行费用太昂贵及机上乘客的在高速飞行时增加的运行费用太昂贵及机上乘客的缘故，使模型选定让缘故，使模型选定让E先走。先走。 七、总结七、

50、总结 模型有易实施的特点，可结合于数据库中使用。它可对数目很模型有易实施的特点，可结合于数据库中使用。它可对数目很大的机场、任意可装载的乘客数及转机的乘客数，都可实现快速最大的机场、任意可装载的乘客数及转机的乘客数，都可实现快速最优排序，并可处理同时要求起飞的请求、照顾晚点飞机很久的先走优排序，并可处理同时要求起飞的请求、照顾晚点飞机很久的先走功能，及可对不同型号和不同油耗的飞机进行适当的酌情考虑。功能，及可对不同型号和不同油耗的飞机进行适当的酌情考虑。 模型很稳定，即使某些参数偏离了真值，它们对总的模型很稳定，即使某些参数偏离了真值，它们对总的费用造成的偏离也不过是参数偏离量的线性函数（正比