最优飞行计划模型

论文题目：最优飞行计划模型

队长：杨璐 学号：******** 队员：高春妮 学号：******** 队员：贺瑞瑞 学号：******** 2012 年 07 月 14日 专业：信计专业：数应专业：计科

最优飞行计划模型

摘 要 本文讨论了在甲乙双方的一场战争中，如何为被乙方部队包围的甲方部队安排一个最优飞行计划的问题。

在解决这个问题的过程中，根据题目中每名熟练飞行员可以作为教练每个月指导20名飞行员（包括他自己在内）进行训练和每名熟练飞行员可以作为教练每个月指导不超过20名飞行员（包括他自己在内）进行训练两个不同条件，利用线性规划的思想方法，建立了两个优化模型，即最优飞行计划模型一和最优飞行计划模型二。

在问题一中，就是要以整个飞行计划中所花的总费用作为以目标函数，以每个月可以执行飞行任务的熟练飞行员人数等于执行飞行任务的熟练飞行员人数、新飞行员人数、担任教练的熟练飞行员人数及闲置的熟练飞行员人数之和以及每个月可执行飞行任务的熟练飞行员人数不能少于执行飞行任务的熟练飞行员人数作为约束条件，建立相应的最优飞行计划模型。利用Lingo数学软件求解出整个飞行计划中所花的最小总费用、每个月担任教练的熟练飞行员人数、新飞行员人数及闲置的熟练飞行员人数。同时根据题目中其他相关数据和条件，可以计算出每个月需要购买新飞机的数目、执行飞行任务的熟练飞行员人数及休假期间的熟练飞行员人数。由此可以安排出一个相应的最优飞行计划。

在问题二中，同样是建立一个相应的最优飞行计划模型的问题，目标函数还是以整个飞行计划中所花的总费用，不同之处是除了问题一中的两个约束条件，还有另一个约束条件，即每名熟练飞行员作为教练每个月指导训练的新飞行员人数不超过教练人数的19倍。求解思路和过程与飞行计划优化模型一的类似，由此也可以安排出一个相应的最优飞行计划。

可以对这两个模型进行推广，假设甲方部队能够向第三方部队求助支援，即甲方部队从第三方部队借调一部分熟练飞行员进行物资运输，这部分熟练飞行员跟甲方部队原本的熟练飞行员除了所得报酬不一样以外其他都一样，在此基础上也可以建立不一样的相应最优飞行计划模型。

关键词 飞行计划；线性规划;优化模型

1

一． 问题重述

在甲乙双方的一场战争中，一部分甲方部队被乙方部队包围长达4个月。由于乙方封锁了所有水陆交通通道，被包围的甲方部队只能依靠空中交通维持供给。运送4个月的供给分别需要2次，3次，3次，4次飞行，每次飞行编队由50架飞机组成（每架飞机需3名飞行员），可以运送10万吨物资。每架飞机每个月只能飞行一次，每名飞行员每个月也只能飞行一次。在执行完运输任务后的返回途中有20%的飞机会被乙方部队击落，相应的飞行员也因此牺牲或失踪。在第1月开始时，甲方拥有110架飞机和330名熟练的飞行员。在每个月开始时，甲方可以招聘新飞行员和购买新飞机。新飞机必须经过一个月检查才可以投入使用，新飞行员必须在熟练飞行员的指导下经过一个月的训练才能投入飞行，每名熟练飞行员可以作为教练每个月指导20名飞行员（包括他自己在内）进行训练。每名飞行员在完成一个月的飞行任务后，必须有一个月的带薪假期，假期结束后才能再投入飞行。已知各项费用（单位略去）如下表所示，请你为甲方安排一个飞行计划。

如果每名熟练飞行员可以作为教练每个月指导不超过20名飞行员（包括他自己在内）进行训练，模型和结果有哪些改变？

表1 飞行计划的各项费用

新飞机价格 闲置的熟练飞行员报酬 第1个月 第2个月 第3个月 第4个月 200.0 7.0 195.0 6.9 9.9 8.9 4.9 190.0 6.8 9.8 9.8 4.8 185.0 6.7 9.7 9.7 4.7 教练和新飞行员报酬（包括培训费用） 10.0 执行飞行任务的熟练飞行员报酬 休假期间的熟练飞行员报酬 9.0 5.0

二． 问题分析

此题要求为甲方安排一个飞行计划，实际上是计划每个月购买多少新飞机、招聘多少新飞行员，以及熟练飞行员如何安排以使所花费的总费用最小的优化问题。

在问题一中，可以分别算出每个月各项费用之和，再相加便得到所花的总费用，即优化目标，还要根据题目中所给条件和基本假设列出各个约束条件。首先，可以把每个月的费用项目分为六项：执行飞行任务的熟练飞行员报酬、休假期间的熟练飞行员报酬、购买新飞机费用、新飞行员报酬、担任教练的熟练飞行员报

2

酬及闲置的熟练飞行员报酬。其次，由题目中的相关数据和条件给出每个月各费用项目的数量，其中执行飞行任务和休假期间的熟练飞行员人数是常数，购买新飞机的数目可以直接算出，其余各费用项目数目是未知量，可以列出关系式作为约束条件在模型求解后得出其值。约束条件列出的主要思路有两个：一是每个月可以执行飞行任务的熟练飞行员人数等于执行飞行任务的熟练飞行员、新飞行员、教练及闲置熟练飞行员人数之和，二是每个月可执行飞行任务的熟练飞行员人数不能少于执行飞行任务的熟练飞行员人数。

在问题二中，每名熟练飞行员可以作为教练每个月指导不超过20名飞行（包括他自己在内）进行训练，而问题一中每名熟练飞行员可以作为教练每个月指导20名飞行员（包括他自己在内）进行训练，这时可以进行类似的分析与模型建立，只是注意增加的新约束条件，即每个教练训练的新飞行员人数不超过教练人数的19倍。

三．基本假设

1.除了新飞机其余飞机都可以投入使用；

2.除了休假的熟练飞行员、教练和新飞行员其余熟练飞行员都可以投入飞行； 3.每架飞机每个月只能飞行一次； 4.每名飞行员每个月也只能飞行一次；

5.每架新飞机经过一个月检查后都可以投入使用；

6.每名新飞行员在熟练飞行员的指导下经过一个月的训练都可以投入飞行； 7.每架执行完运输任务并顺利返回的飞机在下一个月仍然可以正常飞行； 8.每名飞行员在完成一个月的飞行任务后，必须有一个月的带薪假期，假期结束后才能再投入飞行；

9.飞行员的总数变化只由招聘的新飞行员和执行完运输任务后因飞机被乙方部队击落而牺牲或失踪的熟练飞行员的人数决定。

四．符号表示

符号 表示意义 第i个月担任教练的熟练飞行员人数 第i个月闲置的熟练飞行员人数 模型二中第i个月招聘新飞行员的人数 第i个月花费的总费用 四个月所花费的总费用 xi yi ni wi w

3

五．模型建立与求解

在甲乙双方的一场战争中，被乙方部队包围的甲方部队只能依靠空中交通维持供给，现需要为甲方部队安排一个飞行计划，使得所花的总费用最小。

在解决这个问题的过程中，根据题目中每名熟练飞行员可以作为教练每个月指导20名飞行员（包括他自己在内）进行训练和每名熟练飞行员可以作为教练每个月指导不超过20名飞行员（包括他自己在内）进行训练两个不同条件，利用线性规划的思想方法，建立了两个优化模型，即最优飞行计划模型一和最优飞行计划模型二。

5.1最优飞行计划模型一

对于此优化模型的建立过程主要包括优化目标即整个飞行计划中所花的总费用的提出和约束条件的提出两个部分。 5.1.1 优化目标的提出

首先，把每个月的费用项目分为六项，即执行飞行任务的熟练飞行员报酬、休假期间的熟练飞行员报酬、购买新飞机费用、新飞行员报酬、担任教练的熟练飞行员报酬及闲置的熟练飞行员报酬。

其次，由题目中的相关数据和条件可以给出每个月各费用项目的数量，其中执行飞行任务和休假期间的熟练飞行员人数是常数，购买新飞机的数目根据刚够 原则可以直接算出，其余各费用项目数目暂时定为未知量。另外，第四个月初不需要购买新飞机和招聘新飞行员。由此便可得到如下表格2：

表2最优飞行计划模型一各需要费用的项目数量

执行飞行任务的熟练飞行员人数 休假期间的熟练飞行员人数 需要购买的新飞机架数 新飞行员人数 担任教练的熟练飞行员人数 闲置的熟练飞行员人数 第1个月 第2个月 第3个月 第4个月 300 0 60 19x1 x1 y1 450 240 30 19x2 x2 y2 450 360 80 19x3 x3 y3 600 360 0 0 0 y4

由题目中的表1和上面的表2分析可得每个月所花费的费用分别为：

第一个月：w130096020019x110x1107y1 （1） 第二个月：w24508.92404.93019519x29.9x19.96.9y2 （2）

4

第三个月：w34509.83604.88019019x39.8x39.86.8y3 （3） 第四个月： w46009.73604.7801906.7y3 （4） 由（1）、（2）、（3）及（4）可得四个月花费的总费用即优化目标为：

ww1w2w3w4 （5）

5.1.2 约束条件的提出

约束条件提出的主要思路有两个：一是每个月可以执行飞行任务的熟练飞行员人数等于执行飞行任务的熟练飞行员、新飞行员、教练及闲置熟练飞行员人数之和，二是每个月可执行飞行任务的熟练飞行员人数不能少于执行飞行任务的熟练飞行员人数。另外，第四个月初不需要购买新飞机和招聘新飞行员。

因此，根据题目中的相关数据和条件可以得出以下表3：

表3 最优飞行计划模型一跟约束条件有关的数据

可执行飞行任 务的熟练飞行 员人数 执行飞行任务的熟练飞行员人数 新飞行员人数 担任教练的熟练飞行员人数 闲置的熟练飞行员人数 休假期间的熟练飞行员人数 第1个月 第2个月 330 x119x1y1 第3个月 第4个月 x219x2y2240 x319x3y3360 300 19x1 x1 y1 450 19x2 x2 y2 450 19x3 x3 y3 600 0 0 y4 0 240

360 360 下面是根据每个月具体情况列出的约束条件： 有上述表格分析可知，第一个月的飞行需要100架飞机，300名熟练飞行员，完成飞行任务之后，返回80架飞机和240名熟练飞行员。又知第二个月的飞行需要150架飞机，450名熟练飞行员。故可得第一个月的约束条件为：

x1y1300330 （6） x19xy450111第二个月的飞行任务完成之后，返回的飞机架数和熟练飞行员的人数分别

是：120架和360人，休假人员即上月完成飞行任务返回的飞行员的人数有240

5

人，第一个月新招飞行员的人数为19x1。第三个月的飞行需要150架飞机和450名熟练飞行员。故可得第二个月的约束条件为：

x2y2450x119x1y1 （7） x19xy240450222同理可知，第三个月的飞行任务完成之后，返回的飞机架数和熟练飞行员的

人数分别是：120架和360人，休假人员即上月完成飞行任务返回的飞行员的人数有360人，第二个月新招飞行员的人数为19x2。第三个月的飞行需要150架飞机和450名熟练飞行员。故可第三个月的约束条件为：

x3y3450x219x2y2240 （8） x19xy360600333因为甲方部队被乙方部队包围的时间为四个月，故第四个月初不需要购买新飞机

和招聘新飞行员。故可得第四个月的约束条件为：

y4x319x3y3360600 （9）

又从自然条件知：x10,x20,x30,y10,y20,y30,y40 （10）

由上述（6）~（10）式可得模型的约束条件为：

x1y1300330x19xy450111x2y2450x119x1y1x219x2y2240450 xy450x19xy24032223x319x3y3360600y4x319x3y3360600x0,x0,x0,y0,y0,y0,y02312341由LINGO求解可得：

x123x112x315y17 y62y31y41

优化目标的最小值即最小总费用为：wmin64403.1

5.2最优飞行计划模型二

此模型与最优飞行计划模型一基本相似，也需要分别找出优化目标和约束，条件不同之处在于每名熟练飞行员可以作为教练每个月指导不超过20名飞行员

6

（包括他自己在内）进行训练，即每个教练训练的新飞行员人数不超过教练人数的19倍。

5.2.1 优化目标的提出

与前面模型进行类比可知，在每个月月初招聘的新飞行员人数发生了变化。 因此也可得到此模型各需要费用的项目数量的表4为：

表4 最优飞行计划模型二各需要费用的项目数量

执行飞行任务的熟练飞行员人数 休假期间的熟练飞行员人数 需要购买的新飞机架数 新飞行员人数 担任教练的熟练飞行员人数 闲置的熟练飞行员人数 第1个月 第2个月 第3个月 第4个月 300 0 60 n1 x1 y1 450 240 30 n2 x2 y2 450 360 80 n3 x3 y3 600 360 0 0 0 y4

由题目中的表1和上面的表2分析可得每个月所花费的费用分别为：

第一个月：w16020010(x1n1)93007y1 （11） 第二个月： w2301959.9(x2n2)8.94506.9y24.9240 （12）

w3801909.8(x3n3)9.84506.8y34.8360 第三个月：（13）

第四个月：w49.76006.7y44.7360 （14） 由（11）、（12）、（13）和（14）可得四个月花费的总费用即优化目标为： ww1w2w3w4 （15） 5.1.2 约束条件的提出

此最优化飞行计划模型的约束条件除了模型一中的两个约束条件，根据题中已知条件每名熟练飞行员可以作为教练每个月指导不超过20名飞行员（包括他自己在内）进行训练得知，还有另一个约束条件，即每名熟练飞行员作为教练每个月指导训练的新飞行员人数不超过教练人数的19倍。 因此，根据题目中的相关数据和条件可以得出最优飞行计划模型二跟约束条件有关的数据表5：

7

表5 最优飞行计划模型二跟约束条件有关的数据

可执行飞行任 务的熟练飞行 员人数 执行飞行任务的熟练飞行员人数 新飞行员人数 第1个月 第2个月 330 x1n1y1 第3个月 x2n2y2240 第4个月 x3n3y3360 300 n1 450 n2 450 n3 600 0 0 y4 担任教练的熟x1 x2 x3 练飞行员人数 闲置的熟练飞y1 y2 y3 行员人数 休假期间的熟0 240 360 练飞行员人数 下面是根据每个月具体情况列出的约束条件：

360 在第一个月中新招聘的飞行员人数为n1，故可得第一个月的约束条件为：

x1y1300330 x1n1y1450 （16）

n19x11同理可知，在第二个月中新招聘的飞行员人数为n2，故可得第二个月的约束条件为：

x2y2450x1n1y1（17） x2n2y2240450

n19x22同理可知，在第三个月中新招聘的飞行员人数为n3，故可得第三个月的约束条件为：

x3y3450x2n2y2240 （18） x3n3y3360600n19x33同理可知，第四个月的约束条件为：

y4x3n3y3360600 （19）

又从自然条件知：

8

x10,x20,x30,y10,y20,y30,y40,n10,n20,n30 （ 20）

由上述（16）~（20）式可得模型的约束条件为：

x1y1300330x1n1y1450x2y2450x1n1y1x2n2y2240450xy450xny24033222 x3n3y3360600yxny3606003334n119x1n219x2n319x3x10,x20,x30,y10,y20,y30,y40,n10,n20,n30由LINGO求解可得：

x123n4321x212n2213x315 n2853y17y20y03y40优化目标的最小值及最小总费用为：wmin 64347.50 。

六．结果分析

现对以上所建的两个模型的求解结果进行分析。

6.1最优飞行计划模型一结果分析

在此模型中，要是优化目标有最小值即最小总费用为：wmin64403.1。就要这样来安排：

每个月担任教练的熟练飞行员人数分别为：23，11，15，0； 每个月闲置的熟练飞行员人数分别为：7，6，1，1。 每个月招聘新飞行员的人数分别为：437，209，285，0。

6.1最优飞行计划模型二结果分析

在此模型中，要是优化目标有最小值即最小总费用为： wmin 64347.50 。就要这样来安排：

每个月担任教练的熟练飞行员人数分别为：23，12，15，0；

9

每个月闲置的熟练飞行员人数分别为：7，0，0，0； 每个月招聘新飞行员的人数分别为：432，213，285，0。

七．模型推广

在以上两个模型的建立与求解中，有一个假设是飞行员的总数变化只由招聘的新飞行员和执行完运输任务后因飞机被乙方部队击落而牺牲或失踪的熟练飞行员的人数决定，其中包括甲方部队不能向第三方部队借调飞行员。现假设甲方部队能够从第三方部队借调一部分熟练飞行员进行物资运输，这部分熟练飞行员跟甲方部队原本的熟练飞行员除了所得报酬不一样以外其他都一样，在此基础上也可以建立不一样的相应最优飞行计划模型。

参考文献

[1] 姜启源，谢金星，叶俊，数学模型[M]，北京：高等教育出版社，2011.

10

附录

1.最优化飞行计划模型一计算结果

model:

min=200*x1+198*x2+196*x3+7*y1+6.9*y2+6.8*y3+6.9*y4+54581;

x1+y1=30;

x1+19*x1+y1>=450; x2+y2=x1+19*x1+y1-450; x2+y2+19*x2+240>=450; x3+y3=x2+19*x2+y2+240-450; x3+y3+19*x3+360>=600; y4=x3+19*x3+y3+300-600; @gin(x1); @gin(x2); @gin(x3); @gin(y1); @gin(y2); @gin(y3); @gin(y4); end

Global optimal solution found.

Objective value: 64403.10 Objective bound: 64403.10 Infeasibilities: 0.000000 Extended solver steps: 0 Total solver iterations: 238

Variable Value Reduced Cost X1 23.00000 200.0000 X2 11.00000 198.0000 X3 15.00000 196.0000 Y1 7.000000 7.000000 Y2 6.000000 6.900000 Y3 1.000000 6.800000 Y4 1.000000 6.900000

Row Slack or Surplus Dual Price 1 64403.10 -1.000000 2 0.000000 0.000000 3 17.00000 0.000000 4 0.000000 0.000000 5 16.00000 0.000000

11

6 0.000000 0.000000 7 61.00000 0.000000 8 0.000000 0.000000

2．最优化飞行计划模型二计算结果

model:

min=10*(x1+n1)+9.9*(x2+n2)+9.8*(x3+n3)+7*y1+6.9*y2+6.8*y3+6.9*y4+54581;

x1+y1=30; n1<=19*x1; x1+n1+y1>=450; x2+y2=x1+n1+y1-450; n2<=19*x2;

x2+y2+n2+240>=450; x3+y3=x2+n2+y2+240-450; n3<=19*x3;

x3+y3+n3+360>=600; y4=x3+n3+y3+300-600; @gin(x1); @gin(x2); @gin(x3); @gin(y1); @gin(y2); @gin(y3); @gin(y4); end

Global optimal solution found.

Objective value: 64347.50 Objective bound: 64347.50 Infeasibilities: 0.000000 Extended solver steps: 0 Total solver iterations: 18

Variable Value Reduced Cost X1 23.00000 0.000000 N1 432.0000 0.000000 X2 12.00000 10.00000 N2 213.0000 0.000000 X3 15.00000 9.900000 N3 285.0000 0.000000 Y1 7.000000 -3.000000

12

Y2 0.000000 7.000000 Y3 0.000000 6.900000 Y4 0.000000 16.70000

Row Slack or Surplus Dual Price 1 64347.50 -1.000000 2 0.000000 0.000000 3 5.000000 0.000000 4 12.00000 0.000000 5 0.000000 10.00000 6 15.00000 0.000000 7 15.00000 0.000000 8 0.000000 9.900000 9 0.000000 0.000000 10 60.00000 0.000000 11 0.000000 9.800000

13