《飞机排队模型数学建模学习教案.pptx》由会员分享，可在线阅读，更多相关《飞机排队模型数学建模学习教案.pptx（39页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、会计学1飞机飞机(fij)排队模型数学建模排队模型数学建模第一页，共39页。第2页/共38页第二页，共39页。4.设设 是一架飞机要按时到达目的地所必须起飞的最是一架飞机要按时到达目的地所必须起飞的最晚时限，并假设如果一架飞机在晚时限，并假设如果一架飞机在 时限以后才起飞，时限以后才起飞，则它必须以最大安全速度飞完全程。则它必须以最大安全速度飞完全程。 （而在（而在 以内起以内起飞者可着情加速） 。飞者可着情加速） 。 5.如果一架飞机在时限如果一架飞机在时限 以后起飞， 则该机上所有需以后起飞， 则该机上所有需转机的乘客都将误下次班机，并设给每个乘客用于赔转机的乘客都将误下次班机，并设给每个
2、乘客用于赔偿重新安排旅行计划的补偿费用是一样的。偿重新安排旅行计划的补偿费用是一样的。 第3页/共38页第三页，共39页。（1） 第4页/共38页第四页，共39页。第5页/共38页第五页，共39页。 即第一架飞机排第即第一架飞机排第2 2个窗口起飞，第个窗口起飞，第2 2架排第一个窗口起飞架排第一个窗口起飞，最后一，最后一架排最后起飞。并由上表的安排结构，知道（架排最后起飞。并由上表的安排结构，知道（2 2）中的距阵满足）中的距阵满足(mnz)(mnz)每每行中仅有一个元素为行中仅有一个元素为1 1，即每个窗口上仅有一架飞机占用；该阵每列中也有，即每个窗口上仅有一架飞机占用；该阵每列中也有一个
3、元素为一个元素为1 1，即每架飞机占用，即每架飞机占用n n个窗口中的一个。即变量个窗口中的一个。即变量XijXij须满足须满足(mnz)(mnz)约束：约束：1nijjx =1 1,2,.,in (3) 1nijix =1 1,2,.,jn 由于由于ijx为取为取 0，1 值的变量，因此不同的分派安值的变量，因此不同的分派安排对应的仅仅是排对应的仅仅是ijx取取 1 的位置不同而已。的位置不同而已。 第6页/共38页第六页，共39页。于于是是设设1c为为安安排排第第一一架架飞飞机机的的费费用用 11111121211.nncc xc xc x 由由此此全全部部飞飞机机安安排排的的总总费费用用
4、为为： 即构成目标函数。 （由于假设即构成目标函数。 （由于假设 2，ijc独立于独立于ijx的取值，的取值，故此目标函数是一线性函数） 。故此目标函数是一线性函数） 。 为求得使为求得使 c达最小的达最小的ijx，构造了如下的线性规划模型：，构造了如下的线性规划模型： 第7页/共38页第七页，共39页。minc x 11,1,2,.nijjxin 11,1,2,.,nijixjn 01ijx 或 此模型是一个运输问题的特例此模型是一个运输问题的特例-指派模型，其中指派模型，其中 c=111212122212(,.,.,.,.,)nnnnnnccccccccc为一行向量。为一行向量。 1112
5、12122212 x=(,.,.,.,.,)nnnnnnxxxxxxxxx为一列向量，为一列向量，为转为转置符号。置符号。 第8页/共38页第八页，共39页。第9页/共38页第九页，共39页。第10页/共38页第十页，共39页。第11页/共38页第十一页，共39页。其中扣除了飞行的一般油耗， 只计入增加的油耗， 并且式中：其中扣除了飞行的一般油耗， 只计入增加的油耗， 并且式中： t：为飞机晚点的时间； （为飞机晚点的时间； （t=0 即为飞机预定起飞的时间） ；即为飞机预定起飞的时间） ；实际上实际上t作为压缩因子。作为压缩因子。 0k： 为晚点单位时间由加速引起的增加油耗的价格， 同时：
6、为晚点单位时间由加速引起的增加油耗的价格， 同时0k与与不同引擎的飞机有关。不同引擎的飞机有关。 又由于飞机蚝油总数还与飞行距离有关，因此总费又由于飞机蚝油总数还与飞行距离有关，因此总费用应为用应为max0)(vdtF， 其中， 其中 d为飞行距离， 它可由为飞行距离， 它可由d=max()AvT计计算，算，AT为飞机预定到达时间，为飞机预定到达时间，maxv为最大安全飞行速度，为最大安全飞行速度，是常数。是常数。因此将常数因此将常数 maxv并入并入 0k中，记为中，记为 0k于是有一架于是有一架飞机因晚点增加的总费用为：飞机因晚点增加的总费用为： 第12页/共38页第十二页，共39页。 (
7、)Akt T t ( )F t （5） ()Akt T t 第13页/共38页第十三页，共39页。模型参数总表模型参数总表 0t：第一个窗口（小时间段：第一个窗口（小时间段 ）的起始时间；）的起始时间； t：飞机晚点时间，或从：飞机晚点时间，或从 0t计起，飞机真正起飞时间；计起，飞机真正起飞时间； :dt为一架飞机预定起飞的时间（为一架飞机预定起飞的时间（ d 为为 departure）; AT：为一架飞机预定到达的时间（：为一架飞机预定到达的时间（A 为为 Arrive）; ：为等长的时间间隔时间段的长度，也称为起飞窗口；：为等长的时间间隔时间段的长度，也称为起飞窗口； j：为第：为第 j
8、个窗口的标号；个窗口的标号； k：用来决定某飞机单位时间增加燃料费用的常系数，它一般与飞：用来决定某飞机单位时间增加燃料费用的常系数，它一般与飞机型号有关；机型号有关； maxv：一种飞机的：一种飞机的最大安全飞行速度；最大安全飞行速度； avv：一种飞机按时起飞的平均速度，它也与飞机型号有关；：一种飞机按时起飞的平均速度，它也与飞机型号有关；（av,acerage） r:用来计算耽误了转机的乘客重新安排旅程的费用；用来计算耽误了转机的乘客重新安排旅程的费用； ：机上须转乘的人数；：机上须转乘的人数； :p机上登机的总人数；机上登机的总人数； a：将由晚点而引起的乘客的不满意程度转换成美元的：
9、将由晚点而引起的乘客的不满意程度转换成美元的转换系数；转换系数； b：将由晚点而耽误转机的乘客的愤怒转换成美元的转换系数；：将由晚点而耽误转机的乘客的愤怒转换成美元的转换系数； a：反映乘客对晚点不满意上升的快慢程度的因子；：反映乘客对晚点不满意上升的快慢程度的因子； ijc：第：第 i架飞机在第架飞机在第 j个窗口起飞的总费用；个窗口起飞的总费用； 第14页/共38页第十四页，共39页。于是于是，0(1)dtttj， 这里要求0dtt，因为如果飞机未准备好而令其起飞，则该窗口将不能很好的利用。只有当它的预定时间到时，才可考虑它在第 j个 （1j ） 窗口起飞的问题， 并计算式 （5）中 ma
10、xAdTv ()AdavdTT v 第15页/共38页第十五页，共39页。( )()R tru t （6） ：为须转乘的人数；为须转乘的人数； ( ):u t为单位阶跃函数，即为单位阶跃函数，即00()10tutt 第16页/共38页第十六页，共39页。由由假假设设 5，如如果果飞飞机机晚晚点点，则则所所有有须须转转机机的的 个个乘乘客客都都将将将将误误了了转转机机，若若放放宽宽此此条条件件，则则 ( )R t将将是是一一些些阶阶跃跃函函数数之之和和（当当相相应应顾顾客客晚晚点点时时，其其对对应应的的函函数数变变为为 1） 。 3.乘客不满意(mny)的损失 由于飞机晚点由于飞机晚点(wn d
11、in)(wn din)越多，则乘客会越不满意，如果仅晚点越多，则乘客会越不满意，如果仅晚点(wn din)(wn din)一两分钟，则顾客不会太不愿意；但如果晚点一两分钟，则顾客不会太不愿意；但如果晚点(wn (wn din)din)到误了转乘班机，则该乘客会顿时变得焦躁不安并且非常愤到误了转乘班机，则该乘客会顿时变得焦躁不安并且非常愤怒，这一情况可以适当地摘述为一个指数增长函数附加一个阶跃函怒，这一情况可以适当地摘述为一个指数增长函数附加一个阶跃函数，则总的费用函数为：数，则总的费用函数为： ( )(1)()atD teaPb u t （7） 其中 ,ab都是常数，且 第17页/共38页第十
12、七页，共39页。:p为乘客数；为乘客数； ：为要转乘的乘客数；：为要转乘的乘客数； ：为反映乘客等待时不满意上升快慢的因子；：为反映乘客等待时不满意上升快慢的因子； 1ate ：中（：中（-1）是为了使）是为了使 0t （即飞机准时起飞）（即飞机准时起飞）时最小的不满意置零的项；时最小的不满意置零的项； , a b：为将相应的不满意转化为美元的系数；：为将相应的不满意转化为美元的系数； ():u t为单位阶跃函数， 它表达了因误机而顿时产生为单位阶跃函数， 它表达了因误机而顿时产生的不满意。的不满意。 常数常数, a b一般不相等，这是由于误了转机的乘客一般一般不相等，这是由于误了转机的乘客一
13、般要只是晚了一会的乘客不满意程度要大得多些。要只是晚了一会的乘客不满意程度要大得多些。 第18页/共38页第十八页，共39页。综上所述。综上所述。则费用系数则费用系数 ijc为由于第为由于第i架飞机从第架飞机从第 j个窗个窗口起飞时增加燃料、重新安排旅程、和不满意程度而引起口起飞时增加燃料、重新安排旅程、和不满意程度而引起的三项费用的总和。的三项费用的总和。 在假设在假设 3中规定每架飞机从离开自己的通道口到达跑中规定每架飞机从离开自己的通道口到达跑道入口所需要的时间是一样的， 这一假定可使得我们置道入口所需要的时间是一样的， 这一假定可使得我们置预定时间为预定时间为 0t ，并加入计算（，并
14、加入计算（5） 、 （） 、 （6） 、 （） 、 （7）式。）式。如如果这条假设放宽， 则可令果这条假设放宽， 则可令 t等于对应飞机所需时间为起等于对应飞机所需时间为起点，而取代原式中的点，而取代原式中的 0t ，即如（，即如（5）式中：）式中： ()AKt T 0tt ( )F t ()AKt T t 其中其中0t为起飞时间，当为起飞时间，当0tt时，才附加油耗。时，才附加油耗。 第19页/共38页第十九页，共39页。模型还可以在某种条件下处理降落的请求，但不能同时模型还可以在某种条件下处理降落的请求，但不能同时对起飞和降落都达到最优排序。对起飞和降落都达到最优排序。如果要做到此项，则费
15、用如果要做到此项，则费用系数系数 ijc将依赖于前面的飞机的排序情况， 因此目标函数将将依赖于前面的飞机的排序情况， 因此目标函数将不在是线性的了不在是线性的了。 但是只要将要到达的飞机一准备好降落，就可以但是只要将要到达的飞机一准备好降落，就可以(ky)(ky)准许其降落的话，这模型仍适用，这只要将准许其降落的话，这模型仍适用，这只要将t；设为飞机将要达到的时间；设为飞机将要达到的时间； ：设为一架飞机着陆并最终不再占用跑道所需的时间。：设为一架飞机着陆并最终不再占用跑道所需的时间。 第20页/共38页第二十页，共39页。为了防止那些还未准备好的飞机，在就绪之前就对其发出起飞为了防止那些还未
16、准备好的飞机，在就绪之前就对其发出起飞(qfi)(qfi)的命令，置一架飞机在它预定起飞的命令，置一架飞机在它预定起飞(qfi)(qfi)时间以前的某时间以前的某窗口起飞窗口起飞(qfi)(qfi)的损失为无穷大，并假如考虑的损失为无穷大，并假如考虑1 1，2 2，3 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页第二十一页，共39页。由于有上述的统一公式，则原
17、设在由于有上述的统一公式，则原设在 0t时刻有时刻有 n架飞机架飞机可扩展到一天有可扩展到一天有 n架飞机要求起飞的情形。架飞机要求起飞的情形。模型中的参模型中的参数数 , ,dAt Tp都可由数据库提供，而事先给定的参数（或机都可由数据库提供，而事先给定的参数（或机场设定的）为场设定的）为 max, ,avk vvr及变量及变量 t都容易算出来。都容易算出来。0t可由可由计算机系统时钟提供。计算机系统时钟提供。而三个参数而三个参数 , ,ab可由飞机以往可由飞机以往记录和惯例估算出来。记录和惯例估算出来。 4.4.排队模型小结排队模型小结(xioji)(xioji)： 1） 对每架飞机都有一
18、个起飞点对每架飞机都有一个起飞点 dt，终点，终点 ,AT0t为凌晨为凌晨12.01，则带入公式，则带入公式 ijc可求得它在第可求得它在第 j个窗口起飞时个窗口起飞时的费用， （可把机场所有飞机都算在内共的费用， （可把机场所有飞机都算在内共 n架） ；架） ； 2)求解线性规划(xin xn u hu)模型（指派模型）的最优解，则可确定哪架飞机在什么时刻起飞；第22页/共38页第二十二页，共39页。3)当有特殊情况发生后，则重新置剩下的飞机为当有特殊情况发生后，则重新置剩下的飞机为1,2,.,in，起点为当时的，起点为当时的 0t时刻，将剩余飞机重排后时刻，将剩余飞机重排后求解，然后按顺序
19、起飞求解，然后按顺序起飞 在正常运行情况下，上述小结中在正常运行情况下，上述小结中1 1），），2 2）步骤仅须做一次即可按部就班地运）步骤仅须做一次即可按部就班地运行，只有行，只有(zhyu)(zhyu)当意外发生时才启用当意外发生时才启用3 3）部分。）部分。 五五. .模型模型(mxng)(mxng)检验检验 最重要的模型检验即在于检验此模型是否具有意义，编了一个用单纯最重要的模型检验即在于检验此模型是否具有意义，编了一个用单纯形法解线性规划的程序以及几个简单的例子来检查模型运行的良好性，形法解线性规划的程序以及几个简单的例子来检查模型运行的良好性，在后面第六部分中的具体结果中，可以看出
20、所有结果都与所期待的直观在后面第六部分中的具体结果中，可以看出所有结果都与所期待的直观判断相吻合。随后，又进行了更彻底的检验；变动其中的参数，测试更判断相吻合。随后，又进行了更彻底的检验；变动其中的参数，测试更为复杂的例子，以至实际运作此系统，如果实际运行的结果显示出为航为复杂的例子，以至实际运作此系统，如果实际运行的结果显示出为航空公司节省了开支，同时又能维持顾客空公司节省了开支，同时又能维持顾客(gk)(gk)满意度在一个可接受的水满意度在一个可接受的水平，则此模型将取得圆满成功。平，则此模型将取得圆满成功。第23页/共38页第二十三页，共39页。 下面先进行的是变动其中参数的检验，即在参
21、数受到扰动的情况下面先进行的是变动其中参数的检验，即在参数受到扰动的情况下模型是否稳定的检验，如果下模型是否稳定的检验，如果(rgu)(rgu)这个模型中一个或几个参数有这个模型中一个或几个参数有轻微的偏离真值，而模型结果不致有太大的偏离最优解，则可认为轻微的偏离真值，而模型结果不致有太大的偏离最优解，则可认为模型是稳定的。另外模型是稳定的。另外, ,如果如果(rgu)(rgu)参数的微小变化带来模型的剧烈参数的微小变化带来模型的剧烈变化，则希望确定哪个参数更敏感。这样确定它时将利用更多的信变化，则希望确定哪个参数更敏感。这样确定它时将利用更多的信息，以达到准确。息，以达到准确。 虽然利用分派
22、模型对求解很有效， 但在作敏感性分析时却不虽然利用分派模型对求解很有效， 但在作敏感性分析时却不在适应。在适应。因为在进行敏感性分析时，变量的限制因为在进行敏感性分析时，变量的限制 0,1ijx 将不将不利于分析扰动情况， 为此我们必须利用分派模型是运输模型利于分析扰动情况， 为此我们必须利用分派模型是运输模型的特列事实，并将的特列事实，并将 0,1ijx 的限制换成取一组非负整数的限的限制换成取一组非负整数的限制，即约束条件化为制，即约束条件化为 0ijx ，并利用运输模型是一类线性规，并利用运输模型是一类线性规划模型的事实，即可用单纯形求解。划模型的事实，即可用单纯形求解。 第24页/共3
23、8页第二十四页，共39页。下面将指派下面将指派(zhpi)(zhpi)模型（模型（4 4）表运输模型）表运输模型： 11minnnijijijc x 11nijjx 1,2,.,in （9） 11nijix 1,2,.,jn 0,ijx 1,2,.,in 1,2,.,jn 由运输模型的有关理论由运输模型的有关理论(lln)(lln)知：运输问题有可行解，并对（知：运输问题有可行解，并对（9 9）这样的运输模型，一定有一个最优且此最优的所有分量都取整数值）这样的运输模型，一定有一个最优且此最优的所有分量都取整数值。又注意到约束条件（。又注意到约束条件（9 9）的限制，则可能的整数解一定非）的限制
24、，则可能的整数解一定非0 0即即1 1，因此，因此运输问题等价于原问题（运输问题等价于原问题（4 4）。将（）。将（9 9）式由目标函数的向量形式（见）式由目标函数的向量形式（见（4 4）式定义）表出：）式定义）表出： 第25页/共38页第二十五页，共39页。 minc x Axb （10） 0 x 其中其中b的所有分量为的所有分量为 1，A 的元素为的元素为 0，1，对应约束，对应约束（9） 中的等式， 就可利用线性规划模型的结果来检验参数） 中的等式， 就可利用线性规划模型的结果来检验参数的敏感性了。的敏感性了。 显显然然 A 和和 b 的的元元素素只只有有 0 和和 1，对对给给定定了了
25、飞飞机机数数目目后后是是相相对对固固定定的的，因因此此参参数数所所产产生生的的变变化化只只影影响响向向量量 c，假假设设得得到到一一个个最最优优解解 *x，并并假假定定已已解解决决了了其其对对偶偶问问题题： 第26页/共38页第二十六页，共39页。maxb y A yc （11） 其中y为列向量， 维数与 A 阵的行数相同， A,b,c 阵都如 （10）式，由对偶定理知：若原问题（10）或对偶问题存在有限最优解，则另一个亦有有限最优解，且有minc x=maxb y（*y为对偶问题的最优解） ， 现在给 c一个增量 （扰动）,c则记ccc，将 c 带入 （10） 和 （11） 式， 看其对原模
26、型带来何影响， 由 （10）式中的约束Axb，0 x ， 知其未受 c 的影响， 故原最优解 *x仍是原问题的一个可行解，但它有可能不再是最优解了。而保持 *x仍是最优解的充要条件，为：*A yC，即 *CcA y，此式可作为判断原解在扰动下是否仍保持最优（即稳定）的判别条件，但当上述条件不满足时，*x不再是最优解，此时目标函数的新值为 第27页/共38页第二十七页，共39页。*()min()Zc xccxc xZcx 即即 Z 的变化是关于的变化是关于c的线性函数，因此只要的线性函数，因此只要 c的分的分量变化很小，则量变化很小，则指指派问题的不确定性也将很小。派问题的不确定性也将很小。 由
27、于由于 c是费用系数向量，由它计算公式（是费用系数向量，由它计算公式（5）（8）即可）即可看出它的不确定性来自两个方面。一个方面是来自实际参看出它的不确定性来自两个方面。一个方面是来自实际参数的准确度（如燃料费用、误机费等） ，对于航空公司来说数的准确度（如燃料费用、误机费等） ，对于航空公司来说是一个确切的已知量；而另一方面来自与乘客不满意的费是一个确切的已知量；而另一方面来自与乘客不满意的费用有关的参数，如用有关的参数，如 , ,ab三参数（不满增长因子及费用转换三参数（不满增长因子及费用转换系数） ， 而模型的主要误差将来源于此三者， 并且解对系数） ， 而模型的主要误差将来源于此三者，
28、 并且解对 a最最为敏感，因为为敏感，因为 a是在指数部分，下面决定这三个心理参数是在指数部分，下面决定这三个心理参数是如何影响是如何影响 Z 变化的。变化的。 第28页/共38页第二十八页，共39页。假假设设得得到到了了相相应应的的 , ,ab的的估估计计及及相相关关联联的的不不确确定定性性（扰扰动动方方差差） ： ,abaab 其中其中 a表示表示 a 的估计，可由统计方面的顾问来决定，他可经的估计，可由统计方面的顾问来决定，他可经过飞行情况数据的研究及顾客的不满意在长期运营中实际为过飞行情况数据的研究及顾客的不满意在长期运营中实际为顾客赔偿的损失中估计顾客赔偿的损失中估计，a表示估计与真
29、值的误差方差，余表示估计与真值的误差方差，余者类似。者类似。则将（则将（8）式中的）式中的 ijc分别对分别对 , ,ab求偏导得：求偏导得： (1);ijijijatatcccepteapab 第29页/共38页第二十九页，共39页。则则 ijc由由 , ,ab引起的不稳定性变化， 可由全增量公式引起的不稳定性变化， 可由全增量公式近似表示：近似表示： ijijijijccccabab 并并可可进进一一步步假假设设各各参参数数的的变变动动之之间间相相互互独独立立，因因此此由由独独立立和和方方差差公公式式有有 ijc的的方方差差为为： 2222222222222()()()(1) ()ijij
30、ijijatatccccababa epbte ap 同理，对同理，对 11nnijijijZC x有有 第30页/共38页第三十页，共39页。 ijijzxC， 故故 Z 的方差的方差 2z可由下式给出：可由下式给出： 222221111()()nnnnzijijijijijijzxc 因此带入因此带入 ,ab及及 222,ab等数据，则可算得等数据，则可算得 2z的值，为的值，为了达到要求的了达到要求的 2z，还可进一步对各参数的精度加以要，还可进一步对各参数的精度加以要求，但通过求出求，但通过求出 2z即可对模型在随机扰动下的不稳定性即可对模型在随机扰动下的不稳定性的方差有所估计了。的方
31、差有所估计了。 第31页/共38页第三十一页，共39页。六、计算机模拟六、计算机模拟(mn)(mn)模型模型 为了了解为了了解(lioji)(lioji)模型运行的良好性，以及本模型的特点，用下述模型运行的良好性，以及本模型的特点，用下述几个计算机模拟例子来进行演示。几个计算机模拟例子来进行演示。 显然；理论模型显然；理论模型(mxng)(mxng)要比计算机模型要比计算机模型(mxng)(mxng)要少受限制。为要少受限制。为了编程简单并说明问题，在原有的基本假定基础上，再添加如下具体假了编程简单并说明问题，在原有的基本假定基础上，再添加如下具体假定：定： 1.1、在每一窗口至多有三架飞机已
32、准备好可以起飞，当仅有两架在每一窗口至多有三架飞机已准备好可以起飞，当仅有两架飞机准备好的情况发生时，可加入一个虚拟变量，以其对相应的费用系数飞机准备好的情况发生时，可加入一个虚拟变量，以其对相应的费用系数都为都为0即可。即可。 2 2、凭直观给模型指定了参数值，在实际中，这些值应该通过、凭直观给模型指定了参数值，在实际中，这些值应该通过实验室或调查获得：实验室或调查获得： 每一个起飞窗口为一分钟长，即任何飞机起飞需要至多一分钟，每一个起飞窗口为一分钟长，即任何飞机起飞需要至多一分钟，而且其他飞机不准在一分钟内占用跑道；而且其他飞机不准在一分钟内占用跑道；设有飞机降落情况；设有飞机降落情况；
33、第32页/共38页第三十二页，共39页。误转机误转机(zhunj)(zhunj)的赔偿费为每人的赔偿费为每人350350； 误了转机误了转机(zhunj)(zhunj)的乘客的愤怒长度等价于被耽误了的乘客的愤怒长度等价于被耽误了1515分钟的乘客的两分钟的乘客的两倍。倍。 例例1 1 （具有（具有(jyu)(jyu)使最多乘客的飞机先走的功能使最多乘客的飞机先走的功能） 考虑在早晨考虑在早晨6：00，三架飞机同时要求起飞设他们的型号相同，有距此机，三架飞机同时要求起飞设他们的型号相同，有距此机场相同距离的终点机场，（但可能飞往不同城市的机场）。设三架飞机为场相同距离的终点机场，（但可能飞往不同
34、城市的机场）。设三架飞机为A，B，C。并且他们都预定在。并且他们都预定在7：20到达终点，但到达终点，但A飞机上有飞机上有350名乘客；名乘客；B飞飞机上有机上有100名；名；C飞机上有飞机上有400名。且每架飞机上都有名。且每架飞机上都有100名乘客要求转机名乘客要求转机，计算结果见表，计算结果见表1。第33页/共38页第三十三页，共39页。表表 1 具有最多乘客的飞机先走的功能演示具有最多乘客的飞机先走的功能演示 飞机飞机 乘客乘客 费用距阵费用距阵 最优解距阵最优解距阵 X A B C 350 100 400 0.00 0.00 0.00 0.48 0.41 0.50 0.97 0.83
35、 1.00 0 0 1 1 0 0 0 1 0 最低费用最低费用 minZ=0.31，最优解距阵表明，最优解距阵表明 C，A，B 是最优是最优排序，这与常识相符。排序，这与常识相符。由于其他条件设定一样，故最优由于其他条件设定一样，故最优的安排是让乘客多者先走。的安排是让乘客多者先走。 例例2 2 （具有（具有(jyu)(jyu)使晚点飞机最久者先走使晚点飞机最久者先走的功能的功能 ） 当飞机当飞机C C准备离开之际，飞机准备离开之际，飞机D D要求紧急起飞。飞机要求紧急起飞。飞机D D已经晚点已经晚点1818分钟分钟，它若想按时在，它若想按时在7 7：0606分到达终点，就必须分到达终点，就
36、必须(bx)(bx)在在2 2分钟内起飞。其上有分钟内起飞。其上有200200名乘客，名乘客，150150人要求转机，表人要求转机，表2 2给出了结果给出了结果 第34页/共38页第三十四页，共39页。表表 3 一一飞飞机机已已晚晚点点很很久久的的结结果果（表表中中第第二二例例为为：机机上上人人数数/转转乘乘人人数数） 飞飞机机 乘乘客客 晚晚点点 费费用用系系数数距距阵阵 最最优优解解 D 210/150 18min 0.82 0.92 1.00 1 0 0 B 100/100 1min 0.07 0.15 0.22 0 0 1 A 350/100 1min 0.09 0.17 0.26 0
37、 1 0 最低费用为最低费用为 minZ=1.22,最优起飞顺序为最优起飞顺序为 D，B，A，与，与直观吻直观吻合：即晚点很久者应优先走，否则航空公司就须付误机费了。合：即晚点很久者应优先走，否则航空公司就须付误机费了。标准化了的费用距阵标准化了的费用距阵 C 表明飞机表明飞机 D 花费很大。花费很大。 而另外两个却而另外两个却相对很小。相对很小。 例例3 3（具有（具有(jyu)(jyu)按情况决定先后的功能）按情况决定先后的功能） 假设又过了两分钟，这时假设又过了两分钟，这时D D和和A A已走，剩下已走，剩下B B已经晚点已经晚点3 3分钟，而另一架飞机分钟，而另一架飞机E E在在此刻要
38、求起飞。设此刻要求起飞。设E E有如下条件：有如下条件： 1 1）按时准备就绪；）按时准备就绪； 2 2）在可按时到达终点）在可按时到达终点(zhngdin)(zhngdin)（7 7：4242）之前，还富余）之前，还富余4242分钟可以闲置；分钟可以闲置；（ 3 3）机上有）机上有122122名乘客，名乘客，8989人要求转机；人要求转机；（ 4 4）晚点增加的费用为每分钟）晚点增加的费用为每分钟450450。第35页/共38页第三十五页，共39页。 编程序来解此题，如所设引入一个编程序来解此题，如所设引入一个(y )(y )虚拟变量，飞机虚拟变量，飞机X X，这一飞，这一飞机的一切费用系数
39、都为机的一切费用系数都为0 0。得到如下结果：。得到如下结果： 表表 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 在直观上不明显在直观上不明显(mngxin)(mngxin)谁应先走，事实上，似乎应让谁应先走，事实上，似乎应让B B先走先走好些，但可能由于好些，但可能由于E E在高速飞行时增加的运行费用太昂贵及机上乘客在高速飞行
40、时增加的运行费用太昂贵及机上乘客的缘故，使模型选定让的缘故，使模型选定让E E先走。先走。 第36页/共38页第三十六页，共39页。七、总结七、总结(zngji) (zngji) 模型有易实施的特点，可结合于数据库中使用。它可对数目很模型有易实施的特点，可结合于数据库中使用。它可对数目很大的机场、任意可装载的乘客数及转机的乘客数，都可实现大的机场、任意可装载的乘客数及转机的乘客数，都可实现(shxin)(shxin)快速最优排序，并可处理同时要求起飞的请求、照顾晚快速最优排序，并可处理同时要求起飞的请求、照顾晚点飞机很久的先走功能，及可对不同型号和不同油耗的飞机进行适点飞机很久的先走功能，及可
41、对不同型号和不同油耗的飞机进行适当的酌情考虑。当的酌情考虑。 模型很稳定，即使某些参数偏离了真值，它们对总的模型很稳定，即使某些参数偏离了真值，它们对总的费用造成的偏离也不过是参数偏离量的线性函数（正比例费用造成的偏离也不过是参数偏离量的线性函数（正比例函数） 。模型中的三个参数函数） 。模型中的三个参数 , ,ab虽不太容易精确度量其真虽不太容易精确度量其真值，但是他们可以通过实验近似估计到。值，但是他们可以通过实验近似估计到。 模型虽不能对起飞模型虽不能对起飞(qfi)(qfi)和降落同时达到优化，但却可达到和降落同时达到优化，但却可达到在起飞在起飞(qfi)(qfi)的间隙中安排降落。的
42、间隙中安排降落。 可以确信此模型是既可达到使航空公司节省费用，又可达到使顾客满可以确信此模型是既可达到使航空公司节省费用，又可达到使顾客满意的理想模型。意的理想模型。 第37页/共38页第三十七页，共39页。感谢您的观看感谢您的观看(gunkn)！第38页/共38页第三十八页，共39页。NoImage内容(nirng)总结会计学。任何飞机从离开自己的通道口到达(dod)跑道入口处所需要的时间假定都一样。并且飞机须在为其指定的小时间段上才准许离开自己的通道口。下面如何安排哪架飞机在哪个时段上起飞要依赖于实际航班的花费和顾客的满意程度来确定。并由数据库中的数据进行计算，这一量化模型的过程须要另一个不到一秒钟。下面为了建模讨论的方便，将上述公式中及以后要用到的一些参数给出一个总表：。感谢您的观看第三十九页，共39页。