飞机排队模型数学建模PPT课件

1、 在目前的各国机场，一般都使用“先到先服务”的排队系统，这一系统虽一直延用，但效率不高，且不能调节意外情况的发生。在这里将要给出一个利用数据库系统快速排队的模型，以使机场高效的服务，并使航空公司在尽量小的花费情况下，达到顾客满意的目的。第1页/共38页模型的基本假设 1.1. 机场上所有要起飞的飞机，都必须使相同一条跑道，并且任何一架飞机在起飞的时候都需要完全地占有整条跑道，每架飞机占用的时间是一样长的。这一假设可把整个时间分割成离散的等长的小时间段（也称为起飞窗口宽度），在每个小时间段上可容纳一架飞机完成起飞操作。2.2. 第i i架飞机由第j j个时间段上起飞时，其所需费用仅与该飞机和时间

2、位置有关，而与它前面是哪架飞机无关。即费用不是前面飞机的函数，因此这一假设可把对应于不同排序的总费用都统一描述为一个线性函数。3.3. 任何飞机从离开自己的通道口到达跑道入口处所需要的时间假定都一样。同时为了避免有一大堆飞机挤在跑道入口处等待飞机（一般机场也不太可能这样），这时如有另一架飞机需要紧急起飞，这就须将所有排在前面的飞机挤到一边来腾地方，因此假设每架飞机都有立即进入跑道口的通道。这样在须要调整次序时，只须在数据库中的次序上进行调整，而不必对飞机实地重排。并且飞机须在为其指定的小时间段上才准许离开自己的通道口。 第2页/共38页4.设设 是一架飞机要按时到达目的地所必须起飞的最是一架飞

3、机要按时到达目的地所必须起飞的最晚时限，并假设如果一架飞机在晚时限，并假设如果一架飞机在 时限以后才起飞，时限以后才起飞，则它必须以最大安全速度飞完全程。则它必须以最大安全速度飞完全程。 （而在（而在 以内起以内起飞者可着情加速） 。飞者可着情加速） 。 5.如果一架飞机在时限如果一架飞机在时限 以后起飞， 则该机上所有需以后起飞， 则该机上所有需转机的乘客都将误下次班机，并设给每个乘客用于赔转机的乘客都将误下次班机，并设给每个乘客用于赔偿重新安排旅行计划的补偿费用是一样的。偿重新安排旅行计划的补偿费用是一样的。 第3页/共38页模型设计与可行性分析 如果在t t0 0时刻仅有一架飞机或没有要

4、求起飞的飞机，则机场就直接安排其起飞或闲置 。因此设在t t0 0有n n架飞机同时要求起飞。由假设1，可将n n架飞机起飞所需要的总时间分成n n个等长的小时间段（如长）。下面如何安排哪架飞机在哪个时段上起飞要依赖于实际航班的花费和顾客的满意程度来确定。 设为C Cijij第i i架飞机从第j j个小时间段上起飞时所需一切费用之和，于是所有可能的排序带来的费用计算有如下的费用距阵表示： 111212122212.nnnnnncccccccccc（1） 第4页/共38页并设X Xijij=0=0或1 1，当第i i架飞机在第j j个时段上起飞时X Xijij=1=1，否则X Xijij=0=0

5、 于是相应地安排方案距阵为 ：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 第5页/共38页 即第一架飞机排第2个窗口起飞，第2架排第一个窗口起飞，最后一架排最后起飞。并由上表的安排结构，知道（2）中的距阵满足每行中仅有一个元素为1，即每个窗口上仅有一架飞机占用；该阵每列中也有一个元素为1，即每架飞机占用n n个窗口中的一个。即变量X Xijij须满足约束：1nijjx =1 1,2,.,in (3) 1nijix =1

6、 1,2,.,jn 由于由于ijx为取为取 0，1 值的变量，因此不同的分派安值的变量，因此不同的分派安排对应的仅仅是排对应的仅仅是ijx取取 1 的位置不同而已。的位置不同而已。 第6页/共38页于于是是设设1c为为安安排排第第一一架架飞飞机机的的费费用用 11111121211.nncc xc xc x 由由此此全全部部飞飞机机安安排排的的总总费费用用为为： 11nnijijijzc x即构成目标函数。 （由于假设即构成目标函数。 （由于假设 2，ijc独立于独立于ijx的取值，的取值，故此目标函数是一线性函数） 。故此目标函数是一线性函数） 。 为求得使为求得使 c达最小的达最小的ijx

7、，构造了如下的线性规划模型：，构造了如下的线性规划模型： 第7页/共38页minc x 11,1,2,.nijjxin 11,1,2,.,nijixjn 01ijx 或 此模型是一个运输问题的特例此模型是一个运输问题的特例-指派模型，其中指派模型，其中 c=111212122212(,.,.,.,.,)nnnnnnccccccccc为一行向量。为一行向量。 111212122212 x=(,.,.,.,.,)nnnnnnxxxxxxxxx为一列向量，为一列向量，为转为转置符号。置符号。 第8页/共38页 对于分派问题，已有专门为此种特殊结构而设计的有效的解题算法，它被称为GraverThral

8、l primal算法。对于1个随机产生的具有16个变量的分派问题，最多只须2.9秒即可完成求解，而使用现代的计算机，对任意适当个变量的指派问题，只须不到一秒钟即可求得解。 同时，由于模型中费用系数阵（1）须要经过量化，而他们可由下一段四中的公式求得。并由数据库中的数据进行计算，这一量化模型的过程须要另一个不到一秒钟。因此整个模型的建立与求解所用时间是以秒为数量级的，故当机场控制塔在面临一串连珠炮一样的起飞请求时都可几乎立即对排序作出响应。而飞机的起飞间隔远不是以秒为数量级的。一般至少几分钟，因此模型是可行的。更重要的是。在设有意外发生的情况下，还可利用机场的原有时间表，由数据库事先安排好起飞顺

9、序，并让飞机安排起飞顺序起飞，而唯一需要重新安排的情况仅仅发生在有飞机晚点或紧急的情况，而这时的运算也会在一秒钟左右解决问题。而且由假设（3 3），也不会因改变而产生临时的拥挤情况。第9页/共38页四、模型中费用系数阵的量化 由于（1）中的C Cijij 是第i i架飞机从第j j个时间段上起飞的费用，它与一架航班的型号及运行费用和其上载客情况和他们的满意程度有关，为简化运算，把基本运行费设置为费用零点，而只考虑由于飞机延迟起飞而引起的费用。这一费用包括由于晚点而不再以最经济的速度而是以较快或最快速度飞行带来的燃料损失；及乘客因耽误下站转机而重新安排旅途的损失；以及顾客因各种延迟带来的不愉快而

10、转化的损失。将这三者分别归入费用计算并简记为： 费用: 1.燃料附加费 2.乘客误机费 3.乘客不满意的损失 下面分别建立几个费用的计算公式 第10页/共38页1.燃料附加费 由于晚点，飞机必须以尽可能快的速度飞行，故燃料随晚点的时间长短而变化，然而既使晚点，只要为达到最大时限，就可以以低于最大安全速度飞行。并在起飞后就可近似地保持常速，因此燃料消耗在时间内应恒定，由于不知道燃料消耗如何随飞行速度变化，选用了近似的线性函数，即单位时间增加油耗的费用函数为： 0k t t 0( )F t （/单位时间） 0k t 第11页/共38页其中扣除了飞行的一般油耗， 只计入增加的油耗， 并且式中：其中扣

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

12、间，为飞机预定到达时间，maxv为最大安全飞行速度，为最大安全飞行速度，是常数。是常数。因此将常数因此将常数 maxv并入并入 0k中，记为中，记为 0k于是有一架于是有一架飞机因晚点增加的总费用为：飞机因晚点增加的总费用为： 第12页/共38页由此公式看出，飞机晚点越久，则耗油越多，直至它在离开时即以最大速度起飞（假设4）。 下面为了建模讨论的方便，将上述公式中及以后要用到的一些参数给出一个总表： ()Akt T t ( )F t （5） ()Akt T t 第13页/共38页模型参数总表模型参数总表 0t：第一个窗口（小时间段：第一个窗口（小时间段 ）的起始时间；）的起始时间； t：飞机晚

13、点时间，或从：飞机晚点时间，或从 0t计起，飞机真正起飞时间；计起，飞机真正起飞时间； :dt为一架飞机预定起飞的时间（为一架飞机预定起飞的时间（ d 为为 departure）; AT：为一架飞机预定到达的时间（：为一架飞机预定到达的时间（A 为为 Arrive）; ：为等长的时间间隔时间段的长度，也称为起飞窗口；：为等长的时间间隔时间段的长度，也称为起飞窗口； j：为第：为第 j个窗口的标号；个窗口的标号； k：用来决定某飞机单位时间增加燃料费用的常系数，它一般与飞：用来决定某飞机单位时间增加燃料费用的常系数，它一般与飞机型号有关；机型号有关； maxv：一种飞机的：一种飞机的最大安全飞行

14、速度；最大安全飞行速度； avv：一种飞机按时起飞的平均速度，它也与飞机型号有关；：一种飞机按时起飞的平均速度，它也与飞机型号有关；（av,acerage） r:用来计算耽误了转机的乘客重新安排旅程的费用；用来计算耽误了转机的乘客重新安排旅程的费用； ：机上须转乘的人数；：机上须转乘的人数； :p机上登机的总人数；机上登机的总人数； a：将由晚点而引起的乘客的不满意程度转换成美元的：将由晚点而引起的乘客的不满意程度转换成美元的转换系数；转换系数； b：将由晚点而耽误转机的乘客的愤怒转换成美元的转换系数；：将由晚点而耽误转机的乘客的愤怒转换成美元的转换系数； a：反映乘客对晚点不满意上升的快慢程

15、度的因子；：反映乘客对晚点不满意上升的快慢程度的因子； ijc：第：第 i架飞机在第架飞机在第 j个窗口起飞的总费用；个窗口起飞的总费用； 第14页/共38页于是于是，0(1)dtttj， 这里要求0dtt，因为如果飞机未准备好而令其起飞，则该窗口将不能很好的利用。只有当它的预定时间到时，才可考虑它在第 j个 （1j ） 窗口起飞的问题， 并计算式 （5）中 maxAdTv ()AdavdTT v 第15页/共38页2.2.乘客误机费 设为乘客耽误了转机而必须补偿的费用，这里取为常数（假设5）。如果对各人的补偿费确实不同，则取为各人费用的数学期望-平均值，且重新安排旅程只发生在飞机晚点时间超过

16、了时限时才发生，故费用如下计算 ( )()R tru t （6） ：为须转乘的人数；为须转乘的人数； ( ):u t为单位阶跃函数，即为单位阶跃函数，即00()10tutt 第16页/共38页由由假假设设 5，如如果果飞飞机机晚晚点点，则则所所有有须须转转机机的的 个个乘乘客客都都将将将将误误了了转转机机，若若放放宽宽此此条条件件，则则 ( )R t将将是是一一些些阶阶跃跃函函数数之之和和（当当相相应应顾顾客客晚晚点点时时，其其对对应应的的函函数数变变为为 1） 。 3.乘客不满意的损失 由于飞机晚点越多，则乘客会越不满意，如果仅晚点一两分钟，则顾客不会太不愿意；但如果晚点到误了转乘班机，则该

17、乘客会顿时变得焦躁不安并且非常愤怒，这一情况可以适当地摘述为一个指数增长函数附加一个阶跃函数，则总的费用函数为： ( )(1)()atD teaPb u t （7） 其中 ,ab都是常数，且 第17页/共38页:p为乘客数；为乘客数； ：为要转乘的乘客数；：为要转乘的乘客数； ：为反映乘客等待时不满意上升快慢的因子；：为反映乘客等待时不满意上升快慢的因子； 1ate ：中（：中（-1）是为了使）是为了使 0t （即飞机准时起飞）（即飞机准时起飞）时最小的不满意置零的项；时最小的不满意置零的项； , a b：为将相应的不满意转化为美元的系数；：为将相应的不满意转化为美元的系数； ():u t为单

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

19、机从离开自己的通道口到达跑道入口所需要的时间是一样的， 这一假定可使得我们置道入口所需要的时间是一样的， 这一假定可使得我们置预定时间为预定时间为 0t ，并加入计算（，并加入计算（5） 、 （） 、 （6） 、 （） 、 （7）式。）式。如如果这条假设放宽， 则可令果这条假设放宽， 则可令 t等于对应飞机所需时间为起等于对应飞机所需时间为起点，而取代原式中的点，而取代原式中的 0t ，即如（，即如（5）式中：）式中： ()AKt T 0tt ( )F t ()AKt T t 其中其中0t为起飞时间，当为起飞时间，当0tt时，才附加油耗。时，才附加油耗。 第19页/共38页模型还可以在某种条件

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

21、绪之前就对其发出起飞的命令，置一架飞机在它预定起飞时间以前的某窗口起飞的损失为无穷大，并假如考虑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 第21页/共38页由于有上述的统一公式，则原设在由于有上述的统一公式，则原设在 0t时刻有时刻有 n架飞机架飞机可扩展到一天有可扩展到一天有 n架飞机要求起飞的情形。架飞机要求起飞的情形。模型中的参模型中的参数数 , ,dAt Tp都可由数据库提供，而事先给定的

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

23、） ； 2)2)求解线性规划模型（指派模型）的最优解，则可确定哪架飞机在什么时刻起飞；第22页/共38页3)当有特殊情况发生后，则重新置剩下的飞机为当有特殊情况发生后，则重新置剩下的飞机为1,2,.,in，起点为当时的，起点为当时的 0t时刻，将剩余飞机重排后时刻，将剩余飞机重排后求解，然后按顺序起飞求解，然后按顺序起飞 在正常运行情况下，上述小结中1），2）步骤仅须做一次即可按部就班地运行，只有当意外发生时才启用3）部分。 五. .模型检验 最重要的模型检验即在于检验此模型是否具有意义，编了一个用单纯形法解线性规划的程序以及几个简单的例子来检查模型运行的良好性，在后面第六部分中的具体结果中，

24、可以看出所有结果都与所期待的直观判断相吻合。随后，又进行了更彻底的检验；变动其中的参数，测试更为复杂的例子，以至实际运作此系统，如果实际运行的结果显示出为航空公司节省了开支，同时又能维持顾客满意度在一个可接受的水平，则此模型将取得圆满成功。第23页/共38页 下面先进行的是变动其中参数的检验，即在参数受到扰动的情况下模型是否稳定的检验，如果这个模型中一个或几个参数有轻微的偏离真值，而模型结果不致有太大的偏离最优解，则可认为模型是稳定的。另外, ,如果参数的微小变化带来模型的剧烈变化，则希望确定哪个参数更敏感。这样确定它时将利用更多的信息，以达到准确。 虽然利用分派模型对求解很有效， 但在作敏感

25、性分析时却不虽然利用分派模型对求解很有效， 但在作敏感性分析时却不在适应。在适应。因为在进行敏感性分析时，变量的限制因为在进行敏感性分析时，变量的限制 0,1ijx 将不将不利于分析扰动情况， 为此我们必须利用分派模型是运输模型利于分析扰动情况， 为此我们必须利用分派模型是运输模型的特列事实，并将的特列事实，并将 0,1ijx 的限制换成取一组非负整数的限的限制换成取一组非负整数的限制，即约束条件化为制，即约束条件化为 0ijx ，并利用运输模型是一类线性规，并利用运输模型是一类线性规划模型的事实，即可用单纯形求解。划模型的事实，即可用单纯形求解。 第24页/共38页下面将指派模型（4）表运输

26、模型： 11minnnijijijc x 11nijjx 1,2,.,in （9） 11nijix 1,2,.,jn 0,ijx 1,2,.,in 1,2,.,jn 由运输模型的有关理论知：运输问题有可行解，并对（9）这样的运输模型，一定有一个最优且此最优的所有分量都取整数值。又注意到约束条件（9）的限制，则可能的整数解一定非0 0即1，因此运输问题等价于原问题（4）。将（9）式由目标函数的向量形式（见（4）式定义）表出： 第25页/共38页 minc x Axb （10） 0 x 其中其中b的所有分量为的所有分量为 1，A 的元素为的元素为 0，1，对应约束，对应约束（9） 中的等式， 就可

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

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

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

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

31、运营中实际为过飞行情况数据的研究及顾客的不满意在长期运营中实际为顾客赔偿的损失中估计顾客赔偿的损失中估计，a表示估计与真值的误差方差，余表示估计与真值的误差方差，余者类似。者类似。则将（则将（8）式中的）式中的 ijc分别对分别对 , ,ab求偏导得：求偏导得： (1);ijijijatatcccepteapab 第29页/共38页则则 ijc由由 , ,ab引起的不稳定性变化， 可由全增量公式引起的不稳定性变化， 可由全增量公式近似表示：近似表示： ijijijijccccabab 并并可可进进一一步步假假设设各各参参数数的的变变动动之之间间相相互互独独立立，因因此此由由独独立立和和方方差差

32、公公式式有有 ijc的的方方差差为为： 2222222222222()()()(1) ()ijijijijatatccccababa epbte ap 同理，对同理，对 11nnijijijZC x有有 第30页/共38页 ijijzxC， 故故 Z 的方差的方差 2z可由下式给出：可由下式给出： 222221111()()nnnnzijijijijijijzxc 因此带入因此带入 , ,ab及及 222,ab等数据，则可算得等数据，则可算得 2z的值，为的值，为了达到要求的了达到要求的 2z，还可进一步对各参数的精度加以要，还可进一步对各参数的精度加以要求，但通过求出求，但通过求出 2z即可

33、对模型在随机扰动下的不稳定性即可对模型在随机扰动下的不稳定性的方差有所估计了。的方差有所估计了。 第31页/共38页六、计算机模拟模型 为了了解模型运行的良好性，以及本模型的特点，用下述几个计算机模拟例子来进行演示。 显然；理论模型要比计算机模型要少受限制。为了编程简单并说明问题，在原有的基本假定基础上，再添加如下具体假定： 1. 1、在每一窗口至多有三架飞机已准备好可以起飞，当仅有两架飞机准备好的情况发生时，可加入一个虚拟变量，以其对相应的费用系数都为0即可。 2 2、凭直观给模型指定了参数值，在实际中，这些值应该通过实验室或调查获得： 每一个起飞窗口为一分钟长，即任何飞机起飞需要至多一分钟

34、，而且其他飞机不准在一分钟内占用跑道； 设有飞机降落情况； 第32页/共38页误转机的赔偿费为每人350； 误了转机的乘客的愤怒长度等价于被耽误了15分钟的乘客的两倍。 例1 （具有使最多乘客的飞机先走的功能） 考虑在早晨6：00，三架飞机同时要求起飞设他们的型号相同，有距此机场相同距离的终点机场，（但可能飞往不同城市的机场）。设三架飞机为A，B，C。并且他们都预定在7：20到达终点，但A飞机上有350名乘客；B飞机上有100名；C飞机上有400名。且每架飞机上都有100名乘客要求转机，计算结果见表1。 第33页/共38页表表 1 具有最多乘客的飞机先走的功能演示具有最多乘客的飞机先走的功能演

35、示 飞机飞机 乘客乘客 费用距阵费用距阵 最优解距阵最优解距阵 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 （具有使晚点飞机最久者先走的功能 ） 当飞机C准备离开之际，飞机D要求紧急起飞。飞机D已经晚点18分钟，它若想按时在7：06分到达终点，就必须在2分钟内起飞。其上有200名乘客，150人要求转机，表2给出了结果 第34页/共38页表表 3 一一飞飞机机已已晚晚点点很很久久的的结结果果（表表中中第第二二例例为为：机机上上人人数数/转转乘乘人人数