飞行计划问题.doc

数学建模论文飞行计划问题摘要甲方飞行员飞行计划可用线性规划的方法实现，求解目标为在满足供给的前提下，使总的费用最低的最优解。总费用为购买新飞机的花费、闲置的熟练飞行员报酬、教练和飞行员报酬（包括培训费用）、执行飞行任务的熟练飞行员报酬、休假期间的熟练飞行员报酬之和，其中执行飞行任务的熟练飞行员报酬和休假期间的熟练飞行员报酬是固定的，总费用不会受它们影响。所以在计算总费用时，可以直接将执行飞行任务的熟练飞行员报酬和休假期间的熟练飞行员报酬算出结果加到总费用中。对于这一类约束最优解的模型，首先，我们可以根据题目给出要求写出对应的目标函数，其次再根据题目中的约束条件建立相应的约束函数，最后用LINGO软件输入相应的代码，求出约束条件下目标函数的最优解。本文中根据对问题的理解，我们建立了一个约束最优化模型。由于题目给的变量和约束条件较多，首先我们对题目做了相应的定性分析和定量计算，这样使得变量数目极大地减少了，方便对问题的理解和具体的计算。这个约束最优解的模型的具体求解，我们是用LINGO软件来实现。在LINGO软件中，我们只需输入有关的源代码，就可以得到约束问题的最优解。前面对于问题所作的定性分析和定量计算，与由LINGO软件得到的最终答案是一致的。本题中两个问题的唯一不同点是问题一中每名熟练飞行员作为教练每个月指导20名飞行员（包括自己在内）进行训练，而问题二中是每名熟练飞行员作为教练每个月指导不超过20名飞行员（包括他自己在内）进行训练。这样使得两个问题中的教练和新飞行员的总报酬不同，从而影响到最后的总费用不相同。通过用LINGO软件求解得：问题一的约束最优解为：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、假设新飞行员训练时不占用飞机，新飞机检查时不占用飞行员。三 问题分析 这个问题条件较多，看起来很复杂，但只要理解了这个题目中所描述的事实，我们可以建立一个约束最优化模型。首先，由题目可以看出，执行飞行任务以及执行飞行任务后休假的熟练飞行员的数量是确定的，所以这部分的报酬是固定的，在优化目标中可以直接算出。根据题目要求，则每月参与飞行任务的飞机数量依次为100，150，150和200架，这些飞机最后能返回甲方，参与下个月的飞行任务的数量依次为80，120和120。每月参与飞行任务的飞行员数量依次为300，450，450和600人，这些飞行员最后能返回甲方的人数依次为240，360和360，但是这些飞行员紧接着的一个月是休假的，这些因素都会影响下个月飞行任务的飞机和飞行员的安排。问题二中，如果每名熟练飞行员可以作为教练每个月指导不超过20名飞行员(包括他自己在内)进行训练，则应将教练与新飞行员分开考虑。四 符号及变量说明 符号 变量说明xi 甲方第i个月的购买的新飞机数目 yi 甲方第i个月闲置的飞机数目 zi 甲方第i个月闲置的熟练飞行员数量 ui 甲方第i个月在熟练飞行员指导20名飞行员情况下教练和新飞行员总数量 mi 甲方第i个月在熟练飞行员指导不超过20名飞行员情况下教练数量ni 甲方第i个月在熟练飞行员指导不超过20名飞行员情况下新飞行员数量 W 总的花费五 模型的建立与求解 从表格中可以得到各项消费项目的费用，利用这些参数再结合对应的各个变量，便可以建立一个优化模型，运用线性规划的方法，通过LINGO软件便可以解出约束条件下的最优解，从而得到甲方人力，财力和物力的最佳分配。1、 模型的建立在建立模型前不妨先作个表格，记录一下每个月的一些数据：月份一二三四需要飞行次数2334需要飞机数100150150200安全返回的飞机数80120120160需要飞行员数300450450600安全返回的飞行员数240360360480休假的飞行员数0240360360表格1问题一的模型：每名熟练飞行员作为教练每个月指导20名飞行员情况下。分析题目可得，总的花费包括了：新飞机费用、闲置的熟练飞行员报酬、教练和飞行员报酬（包括培训费用）、执行飞行任务的熟练飞行员报酬、休假期间的熟练飞行员报酬。各项花费分别为： 新飞机费用： 200x1+195x2+190x3+185x4 闲置的熟练飞行员报酬： 7z1+6.9z2+6.8z3+6.7z4 教练和飞行员报酬（包括培训费用）：10u1+9.9u2+9.8u3+9.7u4 由表格1可得，每个月执行飞行任务的熟练飞行员数目分别为：300，450，450，600，所以执行飞行任务的熟练飞行员报酬可表示为：9.0*300+8.9*450+9.8*450+9.7*600=16935 由表格1可得，每个月休假期间的熟练飞行员数目分别为：0，240，360，360，所以休假期间的熟练飞行员报酬可表示为：5.0*0+4.9*240+4.8*360+4.7*360=4596所以，总的花费可表示为：W1=200x1+195x2+190x3+185x4+7z1+6.9z2+6.8z3+6.7z4+10u1+9.9u2+9.8u3+9.7u4+16935+4596=200x1+195x2+190x3+185x4+7z1+6.9z2+6.8z3+6.7z4+10u1+9.9u2+9.8u3+9.7u4+21531建立目标函数，使总的花费最低，即：min 200x1+195x2+190x3+185x4+7z1+6.9z2+6.8z3+6.7z4+10u1+9.9u2+9.8u3+9.7u4+21531建立约束条件，从题中很容易得到： 第1个月的飞机总数为110架，需要100架来完成飞行任务；飞行员总数为330人，需要300人来执行飞行计划。 第2、3、4月的飞机总数可表示为上个月安全返回的飞机、新飞机和闲置的飞机三项之和，或者是本月投入飞行的飞机和闲置的飞机两项之和。 第2、3、4月的飞行员总数可表示为上个月闲置的飞行员、教练员及他们训练的新飞行员和休假回来的飞行员三项之和，或者是本月投入飞行的飞行员、教练员和闲置的飞行员三项之和。于是，可得约束条件：（1）第一个月：飞机数为（不包括新飞机）： 110=100+y1飞行员数为（不包括新飞行员）：330=300+0.05u1+z1（2）第二个月：飞机数为（不包括新飞机）： 150+y2=80+y1+x1飞行员数为（不包括新飞行员）：450+0.05u2+z2=u1+z1（3）第三个月：飞机数为（不包括新飞机）： 150+y3=120+y2+x2飞行员数为（不包括新飞行员）：450+0.05u3+z3=u2+z2+240（4）第四个月：飞机数为（不包括新飞机）： 200+y4=120+y3+x3飞行员数为（不包括新飞行员）：600+0.05u4+z4=u3+z3+360综上，得到这个约束最优化模型为：min 200x1+195x2+190x3+185x4+7z1+6.9z2+6.8z3+6.7z4+10u1+9.9u2+9.8u3+9.7u4+21531s.t.110=100+y1330=300+0.05u1+z1150+y2=80+y1+x1450+0.05u2+z2=u1+z1150+y3=120+y2+x2450+0.05u3+z3=u2+z2+240200+y4=120+y3+x3600+0.05u4+z4=u3+z3+360x1,x2,x3,x4,y1,y2,y3,y4,z1,z2,z3,z4,u1,u2,u3,u40且为整数问题二的模型：每名熟练飞行员作为教练每个月指导不超过20名飞行员情况下。分析题目可得，总的花费包括了：新飞机费用、闲置的熟练飞行员报酬、 a.教练报酬（包括培训费用）b.飞行员报酬、执行飞行任务的熟练飞行员报酬、休假期间的熟练飞行员报酬。不难看出，以上各项费用中除中费用与模型的相应部分不同，其它各项都是相同的，所以只需再求出的费用：10m1+9.9m2+9.8m3+9.7m4+10n1+9.9n2+9.8n3+9.7n4所以，总的花费可表示为：W2=200x1+195x2+190x3+185x4+7z1+6.9z2+6.8z3+6.7z4+10m1+9.9m2+9.8m3+9.7m4+10n1+9.9n2+9.8n3+9.7n4+21531建立目标函数，使总的花费最低，即：min 200x1+195x2+190x3+185x4+7z1+6.9z2+6.8z3+6.7z4+10m1+9.9m2+9.8m3+9.7m4+10n1+9.9n2+9.8n3+9.7n4+21531建立约束条件，和模型的约束条件比较可得，只有教练和新飞行员的数量发生了改变，所以，只需对飞行员的约束条件做相应的改变。于是，可得约束条件：（1）第一个月：飞机数为（不包括新飞机）： 110=100+y1飞行员数为（不包括新飞行员）：330=300+m1+z1（2）第二个月：飞机数为（不包括新飞机）： 150+y2=80+y1+x1飞行员数为（不包括新飞行员）：450+m2+z2=m1+n1+z1（3）第三个月：飞机数为（不包括新飞机）： 150+y3=120+y2+x2飞行员数为（不包括新飞行员）：450+m3+z3=m2+n2+z2+240（4）第四个月：飞机数为（不包括新飞机）： 200+y4=120+y3+x3飞行员数为（不包括新飞行员）：600+m4+z4=m3+n3+z3+360又因为每名熟练飞行员作为教练每个月指导不超过20名飞行员(包括他自己在内)，由此又可得到每个月的不等式约束条件：第一个月： 无 第二个月： m1+n120m1第三个月： m2+n220m2第四个月： m3+n320m3综上，得到这个约束最优化模型为：min 200x1+195x2+190x3+185x4+7z1+6.9z2+6.8z3+6.7z4+10m1+9.9m2+9.8m3+9.7m4+10n1+9.9n2+9.8n3+9.7n4+21531s.t.110=100+y1330=300+m1+z1150+y2=80+y1+x1450+m2+z2=m1+n1+z1150+y3=120+y2+x2450+m3+z3=m2+n2+z2+240 200+y4=120+y3+x3600+m4+z4=m3+n3+z3+360m1+n120m1m2+n220m2m3+n320m3x1,x2,x3,x4,y1,y2,y3,y4,z1,z2,z3,z4,m1,m2,m3,m4,n1,n2,n3,n40且为整数2、 模型的求解分析以上两个模型不难看出，变量都比较多，模型有16个，模型有20个，用整数规划的方法来求解非常繁琐，但可以减少变量的数量。首先，我们可以对题目中的条件做定性的分析，从题中很容易能够得到：（1）第四个月不需要再购买新飞机了，也不需要再训练新飞行员，不用教练了。所以，能够得到：x4=0，u4=0，m4=0，n4=0（2）从题中不难看出，四个月的新飞机价格是越来越便宜的（分别为200.0、195.0、190.0、185.0），为了让总花费最少，本月所买的新飞机数量能够满足下月使用便可以了，又因为第二个月需要150架飞机，第一个月有安全返回的飞机和闲置飞机共90架。 所以： x1=150-90=60同理可得： x2=30, x3=80（3）为了使总费用最低，2、3、4月不能有闲置的飞机，必须全部投入飞行，下个月不够可以在本月买新飞机。所以，能够得到：y2=0，y3=0，y4=0（4）很容易从式110=100+y1得到：y1=10这样，两个模型的变量便减少了：模型的变量变为7个，模型的变量变为10个，这时再来求解便会容易许多。 对于这样的求解约束最优解的模型，我们利用LINGO输入相应的代码，很快求出结果（源代码及运行结果见附录）。问题一的约束最优解为：x1=60, x2=30, x3=80, x4=0, y1=10, y2=0, y3=0, y4=0,z1=7, z2=6, z3=4, z4=4, u1=460,u2=220,u3=240,u4=0目标函数值为63855.40问题二的约束最优解为：x1=60,x2=30,x3=80,x4=0,y1=10,y2=0,y3=0,y4=0,z1=7,z2=0,z3=0,z4=0,m1=23,m2=12,m3=12,m4=0,n1=432,n2=210,n3=228,n4=0目标函数值为63729.80六 结果的分析与检验根据上面用LINGO软件的求解结果得：问题一的约束最优解为：x1=60, x2=30, x3=80, x4=0, y1=10, y2=0, y3=0, y4=0,z1=7, z2=6, z3=4, z4=4, u1=460,u2=220,u3=240,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。问题二的约束最优解为：x1=60,x2=30,x3=80,x4=0,y1=10,y2=0,y3=0,y4=0,z1=7,z2=0,z3=0,z4=0,m1=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。在写模型的求解时，由于题目给出的约束变量较多，我们对部分变量作了定性的分析和定量的计算，这些分析和计算都在用LINGO软件求解时得到了验证，他们的最终结果是一致的。七 模型的评价与推广本题中根据题目条件我们建立了一个约束最优化模型，这样的求解约束最优化模型的方法和思路可以用来求解任何约束最优化的问题，并且用LINGO软件可很方便的求解这一类问题，从而使得我们的模型易于理解和推广。由于题目的目标函数和约束函数都是线性的，则这一类问题也可以划分为线性规划问题，那么本题的方法也同样适用于求解线性规划的问题。从这个角度来看，约束最优化问题和线性规划具有统一性。本题中这样的建模方法和求解思路可以用来求解实际生活中的很多问题，如合理下料问题（题目给出几种不同长度的材料，问应如何裁截才能使这些管料，既能满足题目要求，又能使残料最少），这个问题的求解思路和方法与本题的几乎完全相同，还有运输问题（不同型号的车，运送货物到不同的目的地，要求总的运费最少）这也是求解约束最优化的问题，等等。如果题目中没有约束条件，那么我们可以根据题目要求建立无约束最优化模型。对于无约束最优化模型的求解一般采用迭代法，即先选择一个初始点，在寻找该点处的下降方向（搜索方向）。然后求该方向上的极小点（一维搜索），得到一个新的点。这个店要优于原来的点，即新点处的目标函数值小于原来点处的目标函数值。然后在新点处在寻找下降方向和在该方向上的求极小点，.，如此下去，最终求得最优点。对于本题我们建立的模型比较单一，这样是模型的推广受到一定的限制。八 参考文献1 徐全智，杨晋浩，数学建模（第二版）M，北京：高等教育出版社，2008.62 杨启帆，何勇，谈之奕，数学建模竞赛M，杭州：浙江大学出版社，2005.53 王向东，戎海武，文翰，数学实验M，北京：高等教育出版社，2004.54 漆安慎，杜禅英，力学（第二版）M，北京：高等教育出版社，2005.65 谢金星，薛毅，优化模型与LINDO/LINGO软件M，北京：清华大学出版社，2006.4九 附录以上两个问题用LINGO软件求解的源代码及运行结果：问题一：在模型窗口中输入如下代码：min=200*x1+195*x2+190*x3+185*x4+7*z1+6.9*z2+6.8*z3+6.7*z4+10*u1+9.9*u2+9.8*u3+9.7*u4+21531;110=100+y1;330=300+0.05*u1+z1;150+y2=80+y1+x1;450+0.05*u2+z2=u1+z1;150+y3=120+y2+x2;450+0.05*u3+z3=u2+z2+240;200+y4=120+y3+x3;600+0.05*u4+z4=u3+z3+360;gin(x1);gin(x2);gin(x3);gin(x4);gin(y1);gin(y1);gin(y1);gin(y1);gin(z1);gin(z2);gin(z3);gin(z4);gin(u1);gin(u2);gin(u3);gin(u1);运行后得到：Global optimal solution found at iteration: 277 Objective value: 63855.40 Variable Value Reduced Cost X1 60.00000 200.0000 X2 30.00000 195.0000 X3 80.00000 190.0000 X4 0.000000 185.0000 Z1 7.000000 7.000000 Z2 6.000000 6.900000 Z3 4.000000 200.8000 Z4 4.000000 -187.3000 U1 460.0000 10.00000 U2 220.0000 9.900000 U3 240.0000 203.8000 U4 0.000000 0.000000 Y1 10.00000 0.000000 Y2 0.000000 0.000000 Y3 0.000000 0.000000 Y4 0.000000 0.000000 Row Slack or Surplus Dual Price 1 63855.40 -1.000000 2 0.000000 0.000000 3 0.000000 0.000000 4 0.000000 0.000000 5 0.000000 0.000000 6 0.000000 0.000000 7 0.000000 0.000000 8 0.000000 0.000000 9 0.000000 -194.0000即最优解为：x1=60, x2=30, x3=80, x4=0, y1=10, y2=0, y3=0, y4=0,z1=7, z2=6, z3=4, z4=4, u1=460,u2=220,u3=240,u4=0目标函数值为63855.40问题二：在模型窗口中输入如下代码：min=200*x1+195*x2+190*x3+185*x4+7*z1+6.9*z2+6.8*z3+6.7*z4+10*m1+9.9*m2+9.8*m3+9.7*m4+10*n1+9.9*n2+9.8*n3+9.7*n4+21531;110=100+y1;330=300+m1+z1;150+y2=80+y1+x1;450+m2+z2=m1+n1+z1;150+y3=120+y2+x2;450+m3+z3=m2+n2+z2+240; 200+y4=120+y3+x3;600+m4+z4=m3+n3+z3+360;m1+n1=20*m1;m2+n2=20*m2;m3+n3=20*m3;gin(x1);gin(x2);gin(x3);gin(x4);gin(y1);gin(y1);gin(y1);gin(y1);gin(z1);gin(z2);gin(z3);gin(z4);gin(m1);gin(m2);gin(m3);gin(m3);gin(n1);gin(n2);gin(n3);gin(n3);运行后得到：Global optimal solution found at iteration: 5 Objective value: 63729.80 Variable Value Reduced Cost X1 60.00000 200.0000 X2 30.00000 195.0000 X3 80.00000 190.0000 X4 0.000000 185.0000 Z1 7.000000 7.000000 Z2 0.000000 6.900000 Z3 0.000000 16.50000 Z4 0.000000 -3.000000 M1 23.00000 10.00000 M2 12.00000 9.900000 M3 12.00000 19.50000 M4 0.000000 0.000000 N1 432.0000 10.00000 N2 210.0000 9.900000 N3 228.0000 19.50000 N4 0.000000 9.700000 Y1 10.00000 0.000000 Y2 0.000000 0.000000 Y3 0.000000 0.000000 Y4 0.000000 0.000000 Row Slack or Surplus Dual Price 1 63729.80 -1.000000 2 0.000000 0.000000 3 0.000000 0.000000 4 0.000000 0.000000 5 0.000000 0.000000 6 0.000000 0.000000 7 0.000000 0.000000 8 0.000000 0.000000 9 0.000000 -9.700000 10 5.000000 0.000000 11 18.00000 0.000000 12 0.000000 0.000000即最优解为：x1=60,x2=30,x3=80,x4=0,y1=10,y2=0,y3=0,y4=0,z1=7,z2=0,z3=0,z4=0,m1=23,m2=12,m3=12,m4=0,n1=432,n2=210,n3=228,n4=0目标函数值为63729.80