飞行计划问题

数学建模论文飞行计划问题摘要甲方飞行员飞行计划可用线性规划的方法实现，求解目标为在满足供给的前提下， 使总的费用最低的最优解。总费用为购买新飞机的花费、闲置的熟练飞行员报酬、教练 和飞行员报酬（包括培训费用）、执行飞行任务的熟练飞行员报酬、休假期间的熟练飞 行员报酬之和，其中执行飞行任务的熟练飞行员报酬和休假期间的熟练飞行员报酬是固 定的，总费用不会受它们影响。所以在计算总费用时，可以直接将执行飞行任务的熟练 飞行员报酬和休假期间的熟练飞行员报酬算出结果加到总费用中。对于这一类约束最优 解的模型，首先，我们可以根据题目给出要求写出对应的目标函数，其次再根据题目中 的约束条件建立相应的约束函数，最后用LING。软件输入相应的代码，求出约束条件 下目标函数的最优解。本文中根据对问题的理解，我们建立了一个约束最优化模型。由于题目给的变量和 约束条件较多，首先我们对题目做了相应的定性分析和定量计算，这样使得变量数目极 大地减少了，方便对问题的理解和具体的计算。这个约束最优解的模型的具体求解，我 们是用LING。软件来实现。在LING。软件中，我们只需输入有关的源代码，就可以 得到约束问题的最优解。前面对于问题所作的定性分析和定量计算，与由LING。软件 得到的最终答案是一致的。本题中两个问题的唯一不同点是问题一中每名熟练飞行员作为教练每个月指导20 名飞行员（包括自己在内）进行训练，而问题二中是每名熟练飞行员作为教练每个月指 导不超过20名飞行员（包括他自己在内）进行训练。这样使得两个问题中的教练和新 飞行员的总报酬不同，从而影响到最后的总费用不相同。通过用LING。软件求解得：问题一的约束最优解为：4个月开始时甲方购买的新飞机的数量分别为60, 30, 80, 0;每个月甲方闲置的飞 机的数量为10, 0, 0, 0;每个月甲方闲置的熟练飞行员数目为7, 6, 4, 4;每个月教练 和新飞行员的数量为460, 220, 240, 0;每月执行任务的飞行员数目分别为300, 450, 450, 600;每个月休假的熟练飞行员数目为0, 240, 360, 360,则最后求得总消费最低 为63855.40。问题二的约束最优解为：4个月开始时甲方购买的新飞机的数量分别为60, 30, 80, 0;每个月甲方闲置的飞 机的数量为10, 0, 0, 0;每个月甲方闲置的熟练飞行员数目为7, 0, 0, 0;每个月教练 的数量为23, 12, 12, 0;每个月的新飞行员数目为432, 210, 228, 0;每月执行任务的 飞行员数目分别为300, 450, 450, 600;每个月休假的熟练飞行员数目为0, 240, 360, 360,则最后求得总消费最低为63729.80。关键字：飞行员数 飞机数量 教练数目约束最优化模型重述这个问题是以第二次世界大战中的一个实际问题为背景，经过简化而提出来的。在 甲、乙双方的一场战争中，一部分甲方部队被乙方部队包围长达4个月。由于乙方封锁 了所有水陆交通通道，被包围的甲方部队只能依靠空中交通维持供给。运送4个月的供 给分别需要2次，3次，3次，4次飞行，每次飞行编队由50架飞机组成（每架飞机需要 3名飞行员），可以运送10万t物资。每架飞机每个月只能飞行一次，每名飞行员每个月 也只能飞行一次。在执行完运输任务后的返回途中有20%的飞机会被乙方部队击落，相 应的飞行员也因此牺牲或失踪。在第1个月开始时，甲方拥有110架飞机和330名熟练 的飞行员。在每个月开始时，甲方可以招聘新飞行员和购买新飞机。新飞机必须经过一 个月的检查后才可以投入使用，新飞行员必须在熟练飞行员的指导下经过一个月的训练 才能投入飞行。每名熟练飞行员可以作为教练每个月指导20名飞行员（包括他自己在内） 进行训练。每名飞行员在完成一个月的飞行任务后，必须有一个月的带薪假期，假期结束后才能再投入飞行。已知各项费用（单位略去）如下表所示，清为甲方安排一个飞行计划。第1个月第2个月第3个月第4个月新飞机价格200.0195.0190.0185.0闲置的熟练飞行员报酬7.06.96.86.7教练和飞行员报酬（包括培训费用）10.09.99.89.7执行飞行任务的熟练飞行员报酬9.08.99.89.7休假期间的熟练飞行员报酬5.04.94.84.7如果每名熟练飞行员可以作为教练每个月指导不超过20名飞行员（包括他自己在内）进行训练，模型和结果有哪些改变？二条件假设1、假设每个月甲方执行飞行计划时，无任何飞机被击落，在他们返回途中有20% 被击落，即在训练、运送物资及闲置等时候飞机不会出事。2、假设新飞机经一个月检查后都可以投入使用，新飞行员经一个月训练后都可以 投入飞行,而且被训练后的新飞行员便成为了熟练飞行员。3、假设没有援军等其它因素来干扰甲乙双方的战争，每月甲方的空中运送计划没有其他因素影响，空运的物资、次数及飞机数目不变。4、假设飞行员数目只会因为飞机被击落而减少，不受疾病、退休等因素干扰。5、假设新飞行员训练时不占用飞机，新飞机检查时不占用飞行员。三问题分析这个问题条件较多，看起来很复杂，但只要理解了这个题目中所描述的事实，我们 可以建立一个约束最优化模型。首先，由题目可以看出，执行飞行任务以及执行飞行任 务后休假的熟练飞行员的数量是确定的，所以这部分的报酬是固定的，在优化目标中可 以直接算出。根据题目要求，则每月参与飞行任务的飞机数量依次为10(), 150, 150和200架，这 些飞机最后能返回甲方，参与下个月的飞行任务的数量依次为80, 120和120。每月参 与飞行任务的飞行员数量依次为300, 450, 450和600人，这些飞行员最后能返回甲方 的人数依次为240, 360和360,但是这些飞行员紧接着的一个月是休假的，这些因素都 会影响下个月飞行任务的飞机和飞行员的安排。问题二中，如果每名熟练飞行员可以作为教练每个月指导不超过20名飞行员(包括他 自己在内)进行训练，则应将教练与新飞行员分开考虑。四符号及变量说明符号变量说明Xi甲方第i个月的购买的新飞机数目X甲方第i个月闲置的飞机数目甲方第i个月闲置的熟练飞行员数量甲方第i个月在熟练飞行员指导20名飞行员情况下教练和新飞行员总数量mj甲方第i个月在熟练飞行员指导不超过20名飞行员情况下教练数量小甲方第i个月在熟练飞行员指导不超过20名飞行员情况下新飞行员数量W总的花费五模型的建立与求解从表梏中可以得到各项消费项目的费用，利用这些参数再结合对应的各个变量，便 可以建立一个优化模型，运用线性规划的方法，通过LING。软件便可以解出约束条件 下的最优解，从而得到甲方人力，财力和物力的最佳分配。1、模型的建立在建立模型前不妨先作个表梏，记录一下每个月的一些数据:月份-四需要飞行次数2334需要飞机数1001501502(X)安全返回的飞机数80120120160需要飞行员数3004504506(X)安全返回的飞行员数240360360480休假的飞行员数0240360360表格1问题一的模型：每名熟练飞行员作为教练每个月指导20名飞行员情况下。分析题目可得，总的花费包括了：新飞机费用、闲置的熟练飞行员报酬、教 练和飞行员报酬（包括培训费用）、执行飞行任务的熟练飞行员报酬、休假期间的 熟练飞行员报酬。各项花费分别为： 新飞机费用：2（）0x1 + l 95X2+19OX3+185X4闲置的熟练飞行员报酬：7Z1+6.9Z2+6.8Z3+6.74教练和飞行员报酬（包括培训费用）：10u1+9.9u2+9.8u34-9.7u4由表格1可得，每个月执行飞行任务的熟练飞行员数目分别为：300, 450, 450, 600, 所以执行飞行任务的熟练飞行员报酬可表示为：9.0*300+8.9*450+9.8*450+9.7*6()0=16935由表梏1可得，每个月休假期间的熟练飞行员数目分别为：0, 240, 360, 360,所以休假期间的熟练飞行员报酬可表示为：5.0*0+4.9*240+4.8*360+4.7*360=4596所以，总的花费可表示为：W! =200Xj+1 95x2+1 90x3+ 186X4+72)+6.922+6.823+6.7244-1 OUj+9.9u2+9.8u3+9.7u4 +16935+4596=20()Xi + l 95X2+19()X3+1 85x4+72 +6.9z2+6.823+6.724+ 1 Ou +9.9u2+9.8u3+9.7u4+2 1531建立目标函数，使总的花费最低，即：min200X1+195x2+19()X3+185x4+721+6.922+6.8z3+6.7z4+IO5+9.9U2+9.8U3+9.7U4+2153I建立约束条件，从题中很容易得到：第1个月的飞机总数为110架，需要100架来完成飞行任务；飞行员总数为330 人，需要300人来执行飞行计划。第2、3、4月的飞机总数可表示为上个月安全返回的飞机、新飞机和闲置的飞 机三项之和，或者是本月投入飞行的飞机和闲置的飞机两项之和。第2、3、4月的飞行员总数可表示为上个月闲置的飞行员、教练员及他们训练 的新飞行员和休假回来的飞行员三项之和，或者是本月投入飞行的飞行员、教练员和闲 置的飞行员三项之和。于是，可得约束条件:(1)第一个月：飞机数为(不包括新飞机)：110=100+yi飞行员数为(不包括新飞行员)：330=300+0.055+Z(2)第二个月：飞机数为(不包括新飞机)：15()+y2=80+yi+Xi飞行员数为(不包括新飞行员)：450+0.05U2+Z2=Ui+Z(3)第三个月：飞机数为(不包括新飞机)：150+y3=120+y2+X2飞行员数为(不包括新飞行员)：450+0.05u3+23=u2+22+240(4)第四个月：飞机数为(不包括新飞机)：200+y4=1204-y3+x3飞行员数为(不包括新飞行员)：6()0+0.05U4+z4=u3+23+360综上，得到这个约束最优化模型为：min200X +195x2+190x3+185x4+721 +6.922+6.8z3+6.724+10u1+9.9u2+9.8u3+9.7u4+21531S.L110=100+71330=300+0-05u1+z1150+y2=80+yi+X450+0.05u2+22=u +z 150+y3=120+y2+X2450+0.05u3+23=U2+Z2+2402004-y4=1204-y3+X36()()+0.()5114+24=113+23+360X1 ,x2,x3,x4,y i ,y2,y3，y4，zbZ2,z3,24,u1 ,u23，u4 0 且为整数问题二的模型：每名熟练飞行员作为教练每个月指导不超过20名飞行员情况下。分析题目可得，总的花费包括了：新飞机费用、闲置的熟练飞行员报酬、a.教练报酬(包括培训费用)b.飞行员报酬、执行飞行任务的熟练飞行员报酬、休假期间的熟练飞行员报酬。不难看出，以上各项费用中除中费用与模型I的相应部分不同，其它各项都是相 同的，所以只需再求出的费用：10m 1 +9.9m2+9.8m3+9.7m4+1 On 1+9.9n2+9.8n3+9.7n4所以，总的花费可表示为：W2=200x1+195X2+19()X3+185x4+72+6.922+6.8z3+6.724+10m1+9.9m2+9.8m3+9.7 m4+ lOilj 4-9.9n2+9.8n3+9.7n4+21531建立目标函数，使总的花费最低，即：min 200X1 +195x2+190x3+185x4+7z1 +6.9z2+6.8z3+6.7z4+ l()m +9.9m2+9.8m3+9.7m4+1 On1 +9.9n24-9.8n3+9.7n4+21531建立约束条件，和模型I的约束条件比较可得，只有教练和新飞行员的数量发生了改变，所以，只需对飞行员的约束条件做相应的改变。于是，可得约束条件：(1)第一个月：飞机数为(不包括新飞机)：iio=ioo+y飞行员数为(不包括新飞行员)：33()=300+011+。(2)第二个月：飞机数为(不包括新飞机)：150+y2=80+y+X飞行员数为(不包括新飞行员)：450+m2+z2=m1+n1+z1(3)第三个月：飞机数为(不包括新飞机)：150+丫3=120+)”+*2飞行员数为(不包括新飞行员)：450+m3+z3=m2+n2+22+240(4)第四个月：飞机数为(不包括新飞机)：200+y4=120+y3+x3飞行员数为(不包括新飞行员)：6()0+m4+Z4=m3+n3+23+360又因为每名熟练飞行员作为教练每个月指导不超过20名飞行员(包括他自己在内),由此又可得到每个月的不等式约束条件：第一个月：无第二个月：m1+n120m1第三个月：m2+n220m2第四个月：m3+n320m3综上，得到这个约束最优化模型为：min 200Xi +195X2+19()X3+185X4+721 +6.9Z2+6.8Z3+6.7Z4+10m1+9.9m2+9.8m3+9.7m4+10n1+9.9n2+9.8n34-9.7n4+21531s.t.110=100+7,330=300+m1+z1150+y2=80+yi+X450+m2+z2=m1+n1+21150+y3=120+y2+X2450+m3+z3=m2+n2+22+2402004-y4=1204-y3+x3600+m4+24=m3+n3+Z3+360m1+n120m1m2+n220m2m3+n30 且为整数2、模型的求解分析以上两个模型不难看出，变量都比较多，模型I有16个，模型II有20个，用整数规划的方法来求解非常繁琐，但可以减少变量的数量。首先，我们可以对题目中的条件做定性的分析，从题中很容易能够得到：(1)第四个月不需要再购买新飞机了，也不需要再训练新飞行员，不用教练了。所 以，能够得到：x4=o , 口4=0，mq=o, n4二()(2)从题中不难看出，四个月的新飞机价格是越来越便宜的(分别为200.()、195.0、 190.0、185.0),为了让总花费最少，本月所买的新飞机数量能够满足下月使用便可以了， 又因为第二个月需要150架飞机，第一个月有安全返回的飞机和闲置飞机共90架。所以：Xj=150-90=60同理可得：X2=30, X3=80(3)为了使总费用最低，2、3、4月不能有闲置的飞机，必须全部投入飞行，下个 月不够可以在本月买新飞机。所以，能够得到：y2=o, y3=o, y4=o(4)很容易从式HO=iO()+yi得到：力=10这样，两个模型的变量便减少了：模型I的变量变为7个，模型II的变量变为10 个，这时再来求解便会容易许多。对于这样的求解约束最优解的模型，我们利用UNGO输入相应的代码，很快求出结果(源代码及运行结果见附录)。问题一的约束最优解为：X60, X2=30, X3=8(), X4=0, Vi 1(), 丫2=。，丫3=,4二，Z7, Z76, Z=4, Z4, Ll| -460,U722(),Ll240,11()目标函数值为63855.40问题二的约束最优解为：X1=602=30,x3=80,x4=0,y1=10,y2=0,y3=0,y4=0,z 1=7,z2=0,z3=0,z4=0,m =23,012= 12,rn3= 12,m4=0,n 1=4322=210,113=228,114=0目标函数值为63729.80六结果的分析与检验根据上面用L1NGC)软件的求解结果得：问题一的约束最优解为：Xi=60, X2=30, x3=80, x4=0, yi=10, y2=0, y3=0, y4=0,2j=7, z2=6, Z3=4, Z4=4, Ui =460,112=220,U3=24(),U4=0目标函数值为63855.40即：4个月开始时甲方购买的新飞机的数量分别为60, 30, 80, 0;每个月甲方闲置 的飞机的数量为10, 0, 0, 0;每个月甲方闲置的熟练飞行员数目为7, 6, 4, 4;每个月 教练和新飞行员的数量为460, 220, 240, 0;每月执行任务的飞行员数目分别为300, 450, 450, 600;每个月休假的熟练飞行员数目为0, 240, 360, 360,则最后求得总消费最低 为63855.40。问题二的约束最优解为：Xj 6(),X23(),XBOjX40,y 10,丫2=0,丫3=0,丫4=021=7 220,Z0,m =23,m2=12,m3= 12,m4=0,n1 =432,n2=210,n3=228,n4=0目标函数值为63729.80即：4个月开始时甲方购买的新飞机的数量分别为60, 30, 80, 0;每个月甲方闲置 的飞机的数量为10, 0, 0, 0;每个月甲方闲置的熟练飞行员数目为7, 0, 0, 0;每个月 教练的数量为23, 12, 12, 0;每个月的新飞行员数目为432, 210, 228, 0;每月执行任 务的飞行员数目分别为300 , 450 , 450 , 600;每个月休假的熟练飞行员数目为0, 240, 360, 360,则最后求得总消费最低为63729.80。在写模型的求解时，由于题目给出的约束变量较多，我们对部分变量作了定性的分 析和定量的计算，这些分析和计算都在用LING。软件求解时得到了验证，他们的最终 结果是一致的。七模型的评价与推广本题中根据题目条件我们建立了一个约束最优化模型，这样的求解约束最优化模型的方法和思路可以用来求解任何约束最优化的问题，并且用L1NGQ软件可很方便的求 解这一类问题，从而使得我们的模型易于理解和推广。由于题目的目标函数和约束函数 都是线性的，则这一类问题也可以划分为线性规划问题，那么本题的方法也同样适用于 求解线性规划的问题。从这个角度来看，约束最优化问题和线性规划具有统一性。本题 中这样的建模方法和求解思路可以用来求解实际生活中的很多问题，如合理下料问题 （题目给出几种不同长度的材料，问应如何裁截才能使这些管料，既能满足题目要求，又能使残料最少），这个问题的求解思路和方法与本题的几乎完全相同，还有运输问题 （不同型号的车，运送货物到不同的目的地，要求总的运费最少）这也是求解约束最优化的问题，等等。如果题目中没有约束条件，那么我们可以根据题目要求建立无约束最优化模型。对 于无约束最优化模型的求解一般采用迭代法，即先选择一个初始点，在寻找该点处的下 降方向（搜索方向）。然后求该方向上的极小点（一维搜索），得到一个新的点。这个 店要优于原来的点，即新点处的目标函数值小于原来点处的目标函数值。然后在新点处 在寻找下降方向和在该方向上的求极小点，如此下去，最终求得最优点。对于本题我们建立的模型比较单一，这样是模型的推广受到一定的限制。八参考文献1徐全智，杨晋浩，教学建模（第二版）M,北京：高等教育出版社，2008.62杨启帆，何勇，谈之奕，数学建模竞赛M,杭州：浙江大学出版社，2（X）5.53王向东，戎海武，文翰，数学实验M,北京：高等教育出版社，2004.54漆安慎，杜禅英，力学（第二版）M,北京：高等教育出版社，2005.65谢金星，薛毅，优化模型与口NDO/LINGC）软件M,北京：清华大学出版社，2006.4九附录以上两个问题用LING。软件求解的源代码及运行结果：问题一：在模型窗口中输入如下代码：min=200*x1 + l 95*X2+19O*x3+185*X4+7*z1+6.9*22+6.8*23+6.7*Z4+10*u1+9.9*U2+9.8 u3+9.7*u4+21531;110=100+y1;330=3()0+0.05*Ui+z1；150+y2=80+yi+X1;450+0.05*U2+z2=u i+z i ；150+y3=120+y2+X2；450+0.05*u3+23=u2+z2+240；200+y4=120+y3+x3;600+0.05*u4+z4= u3+23+360；n(Xi);gin(X2);ghi(X3);a(X4);n(yi)；n(y1)；gm(y1)；n(y1)；n(Z);gin(Z2);gin(Z3);gin(Z4);gjn(u1);gin(u2)；gin(u3);gin(u1);运行后得到：Global optimal solution found at iteration:277Objective value:638554)VariableValueReduced CostXI60.00000200.0000X230.00000195.0000X380.00000190.00(X)X4O.(X)OOOO185.0000Z17.0000007.000000Z26.0000006.900000Z34.000000200.8000Z44.000000-1873000UI460.000010.00000U2220.00(X)9.900000U3240.00(X)203.8000U4O.OOOO(X)O.(X)OOOOY110.00000().(X)0000Y20.0000000.000000Y30.000000().(X)00()0Y40.000000O.(X)(X)OORowSlack or SurplusDual Price163855.40-1.0000(X)20.0000000.00000030.0000()00.00000040.000()000.00000050.0000()00.00000060.0000000.00000070.000()000.0000008o.oooooo0.000000o.oooooo-194.0000即最优解为：X|60, X2=30, X3=8O, 乂4二。,V 10, 丫2=。，丫3=。，4=。，Z=7, Z?=6 Z=4, Zq=4, U =460,Ll)=22(),113=24(),114二()目标函数值为63855.40问题二：在模型窗口中输入如下代码：min=200*x + l 95*X2+19O*x3+185*X4+7*Z +6.9*22+6-8*z3+6-7*z4+1 *m 1 +9.9*m2+9.8*m3+9.7*m4+ io*n1+9.9*n2+9.8*n3+9.7*n4+2i 531 ；110=100+y1;330=300+m+z1;150+y2=80+y+X；450+m2+z2=m1+n1+z1;150+y3=120+y2+x2;450+m5+23=m2+n2+22+240；200+y4=l 20+y3+X3；6()04-m4+z4=m3+n3+z3+360；m+n1=20*m;m2+n2=20*m2;m3+n3=20*m3;gjn(X!);gin(X2)；gin(X3);gin(X4);gjn(yi)；n(yi)；gin(yi)；gin(yi)；&n(z i);n(Z2);gin(Z3);gin(Z4);gin(m1)；gin(m2.1；gin(m3);gin(m3);和(。1);酬(。2)；典(。3);3n(。叱运行后得到：Global optimal solution Gund at iteration:Objective value:63729.80VariableValueReduced CostXI60.00000200.0000X230.00000195.0000X380.00000190.0000X4O.(X)OOOO185.0000Z17.0000007.0000()0Z20.0000006.900000Z30.00000016.50000Z40.000000-3.(M)0000Ml23.0000010.00000M212.000009.900000M312.0000019.50000M40.0000000.00(X)00N1432.000010.00000N2210.00009.900000N3228.000019.50000N40.0000009.700000Y110.00000O.(X)(X)OOY20.000000O.(X)O()()OY30.000000o.ooooooY40.0000000.0()0000RowSlack or SurplusDual Price163729.80-1.00000020.0000()00X)0000030.0000()00.00000040.000()000.00000050.0000000.00000060.000()000.0000007o.oooooo0.00000080.0000000.0000009o.oooooo-9.700000105.00()0000.0000001118.00000o.oooooo12o.ooooooo.oooooo即最优解为：乂尸60,*2=3(),*3=8(),*4=。,丫1=10,丫2二,丫3=，丫4=()/1 = 7/2=()/3=0/4=0, m 尸23,012二 12,m3= 12,m4=0,nj=432,117=210,n3=228,114=0目标函数值为63729.8()