最优飞行计划模型.doc

最优飞行计划模型 论文题目最优飞行计划模型队长杨璐学号41005234专业信计队员高春妮学号41005155专业数应队员贺瑞瑞学号41012186专业计科xx年07月14日1最优飞行计划模型摘要本文讨论了在甲乙双方的一场战争中，如何为被乙方部队包围的甲方部队安排一个最优飞行计划的问题。 在解决这个问题的过程中，根据题目中每名熟练飞行员可以作为教练每个月指导20名飞行员（包括他自己在内）进行训练和每名熟练飞行员可以作为教练每个月指导不超过20名飞行员（包括他自己在内）进行训练两个不同条件，利用线性规划的思想方法，建立了两个优化模型，即最优飞行计划模型一和最优飞行计划模型二。 在问题一中，就是要以整个飞行计划中所花的总费用作为以目标函数，以每个月可以执行飞行任务的熟练飞行员人数等于执行飞行任务的熟练飞行员人数、新飞行员人数、担任教练的熟练飞行员人数及闲置的熟练飞行员人数之和以及每个月可执行飞行任务的熟练飞行员人数不能少于执行飞行任务的熟练飞行员人数作为约束条件，建立相应的最优飞行计划模型。 利用Lingo数学软件求解出整个飞行计划中所花的最小总费用、每个月担任教练的熟练飞行员人数、新飞行员人数及闲置的熟练飞行员人数。 同时根据题目中其他相关数据和条件，可以计算出每个月需要购买新飞机的数目、执行飞行任务的熟练飞行员人数及休假期间的熟练飞行员人数。 由此可以安排出一个相应的最优飞行计划。 在问题二中，同样是建立一个相应的最优飞行计划模型的问题，目标函数还是以整个飞行计划中所花的总费用，不同之处是除了问题一中的两个约束条件，还有另一个约束条件，即每名熟练飞行员作为教练每个月指导训练的新飞行员人数不超过教练人数的19倍。 求解思路和过程与飞行计划优化模型一的类似，由此也可以安排出一个相应的最优飞行计划。 可以对这两个模型进行推广，假设甲方部队能够向第三方部队求助支援，即甲方部队从第三方部队借调一部分熟练飞行员进行物资运输，这部分熟练飞行员跟甲方部队原本的熟练飞行员除了所得报酬不一样以外其他都一样，在此基础上也可以建立不一样的相应最优飞行计划模型。 关键词飞行计划；线性规划;优化模型2一问题重述在甲乙双方的一场战争中，一部分甲方部队被乙方部队包围长达4个月。 由于乙方封锁了所有水陆交通通道，被包围的甲方部队只能依靠空中交通维持供给。 运送4个月的供给分别需要2次，3次，3次，4次飞行，每次飞行编队由50架飞机组成（每架飞机需3名飞行员），可以运送10万吨物资。 每架飞机每个月只能飞行一次，每名飞行员每个月也只能飞行一次。 在执行完运输任务后的返回途中有20%的飞机会被乙方部队击落，相应的飞行员也因此牺牲或失踪。 在第1月开始时，甲方拥有110架飞机和330名熟练的飞行员。 在每个月开始时，甲方可以招聘新飞行员和购买新飞机。 新飞机必须经过一个月检查才可以投入使用，新飞行员必须在熟练飞行员的指导下经过一个月的训练才能投入飞行，每名熟练飞行员可以作为教练每个月指导20名飞行员（包括他自己在内）进行训练。 每名飞行员在完成一个月的飞行任务后，必须有一个月的带薪假期，假期结束后才能再投入飞行。 已知各项费用（单位略去）如下表所示，请你为甲方安排一个飞行计划。 如果每名熟练飞行员可以作为教练每个月指导不超过20名飞行员（包括他自己在内）进行训练，模型和结果有哪些改变？表1飞行计划的各项费用第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二问题分析此题要求为甲方安排一个飞行计划，实际上是计划每个月购买多少新飞机、招聘多少新飞行员，以及熟练飞行员如何安排以使所花费的总费用最小的优化问题。 在问题一中，可以分别算出每个月各项费用之和，再相加便得到所花的总费用，即优化目标，还要根据题目中所给条件和基本假设列出各个约束条件。 首先，可以把每个月的费用项目分为六项执行飞行任务的熟练飞行员报酬、休假期间的熟练飞行员报酬、购买新飞机费用、新飞行员报酬、担任教练的熟练飞行员报3酬及闲置的熟练飞行员报酬。 其次，由题目中的相关数据和条件给出每个月各费用项目的数量，其中执行飞行任务和休假期间的熟练飞行员人数是常数，购买新飞机的数目可以直接算出，其余各费用项目数目是量，可以列出关系式作为约束条件在模型求解后得出其值。 约束条件列出的主要思路有两个一是每个月可以执行飞行任务的熟练飞行员人数等于执行飞行任务的熟练飞行员、新飞行员、教练及闲置熟练飞行员人数之和，二是每个月可执行飞行任务的熟练飞行员人数不能少于执行飞行任务的熟练飞行员人数。 在问题二中，每名熟练飞行员可以作为教练每个月指导不超过20名飞行（包括他自己在内）进行训练，而问题一中每名熟练飞行员可以作为教练每个月指导20名飞行员（包括他自己在内）进行训练，这时可以进行类似的分析与模型建立，只是注意增加的新约束条件，即每个教练训练的新飞行员人数不超过教练人数的19倍。 三基本假设1.除了新飞机其余飞机都可以投入使用；2.除了休假的熟练飞行员、教练和新飞行员其余熟练飞行员都可以投入飞行；3.每架飞机每个月只能飞行一次；4.每名飞行员每个月也只能飞行一次；5.每架新飞机经过一个月检查后都可以投入使用；6.每名新飞行员在熟练飞行员的指导下经过一个月的训练都可以投入飞行；7.每架执行完运输任务并顺利返回的飞机在下一个月仍然可以正常飞行；8.每名飞行员在完成一个月的飞行任务后，必须有一个月的带薪假期，假期结束后才能再投入飞行；9.飞行员的总数变化只由招聘的新飞行员和执行完运输任务后因飞机被乙方部队击落而牺牲或失踪的熟练飞行员的人数决定。 四符号表示符号表示意义ix第i个月担任教练的熟练飞行员人数iy第i个月闲置的熟练飞行员人数in模型二中第i个月招聘新飞行员的人数i w第i个月花费的总费用w四个月所花费的总费用4五模型建立与求解在甲乙双方的一场战争中，被乙方部队包围的甲方部队只能依靠空中交通维持供给，现需要为甲方部队安排一个飞行计划，使得所花的总费用最小。 在解决这个问题的过程中，根据题目中每名熟练飞行员可以作为教练每个月指导20名飞行员（包括他自己在内）进行训练和每名熟练飞行员可以作为教练每个月指导不超过20名飞行员（包括他自己在内）进行训练两个不同条件，利用线性规划的思想方法，建立了两个优化模型，即最优飞行计划模型一和最优飞行计划模型二。 5.1最优飞行计划模型一对于此优化模型的建立过程主要包括优化目标即整个飞行计划中所花的总费用的提出和约束条件的提出两个部分。 5.1.1优化目标的提出首先，把每个月的费用项目分为六项，即执行飞行任务的熟练飞行员报酬、休假期间的熟练飞行员报酬、购买新飞机费用、新飞行员报酬、担任教练的熟练飞行员报酬及闲置的熟练飞行员报酬。 其次，由题目中的相关数据和条件可以给出每个月各费用项目的数量，其中执行飞行任务和休假期间的熟练飞行员人数是常数，购买新飞机的数目根据刚够原则可以直接算出，其余各费用项目数目暂时定为量。 另外，第四个月初不需要购买新飞机和招聘新飞行员。 由此便可得到如下表格2表2最优飞行计划模型一各需要费用的项目数量第1个月第2个月第3个月第4个月执行飞行任务的熟练飞行员人数300450450600休假期间的熟练飞行员人数0240360360需要购买的新飞机架数6030800新飞行员人数191x192x193x0担任教练的熟练飞行员人数1x2x3x0闲置的熟练飞行员人数1y2y3y4y由题目中的表1和上面的表2分析可得每个月所花费的费用分别为第一个月1111300960xx9?10107wxxy? （1）第二个月22124508.9?2404.9?3019519?9.99.96.9wxxy? （2）5第三个月33334509.8?3604.88019019?9.89.86.8wxxy? （3）第四个月436009.7?3604.7?80190?6.7wy? （4）由 （1）、 （2）、 （3）及 （4）可得四个月花费的总费用即优化目标为4321ww? （5）5.1.2约束条件的提出约束条件提出的主要思路有两个一是每个月可以执行飞行任务的熟练飞行员人数等于执行飞行任务的熟练飞行员、新飞行员、教练及闲置熟练飞行员人数之和，二是每个月可执行飞行任务的熟练飞行员人数不能少于执行飞行任务的熟练飞行员人数。 另外，第四个月初不需要购买新飞机和招聘新飞行员。 因此，根据题目中的相关数据和条件可以得出以下表3表3最优飞行计划模型一跟约束条件有关的数据第1个月第2个月第3个月第4个月可执行飞行任务的熟练飞行员人数执行飞行任务的熟练飞行员人数33011119xxy?22219240xxy?33319360xxy?300450450600新飞行员人数191x192x193x0担任教练的熟练飞行员人数闲置的熟练飞行员人数休假期间的熟练飞行员人数1x2x3x01y2y3y4y0240360360下面是根据每个月具体情况列出的约束条件有上述表格分析可知，第一个月的飞行需要100架飞机，300名熟练飞行员，完成飞行任务之后，返回80架飞机和240名熟练飞行员。 又知第二个月的飞行需要150架飞机，450名熟练飞行员。 故可得第一个月的约束条件为1111130033019450xyxxy? （6）第二个月的飞行任务完成之后，返回的飞机架数和熟练飞行员的人数分别是120架和360人，休假人员即上月完成飞行任务返回的飞行员的人数有2406人，第一个月新招飞行员的人数为119x。 第三个月的飞行需要150架飞机和450名熟练飞行员。 故可得第二个月的约束条件为221112224501919240450xyxxyxxy? （7）同理可知，第三个月的飞行任务完成之后，返回的飞机架数和熟练飞行员的人数分别是120架和360人，休假人员即上月完成飞行任务返回的飞行员的人数有360人，第二个月新招飞行员的人数为219x。 第三个月的飞行需要150架飞机和450名熟练飞行员。 故可第三个月的约束条件为332223334501924019360600xyxxyxxy? （8）因为甲方部队被乙方部队包围的时间为四个月，故第四个月初不需要购买新飞机和招聘新飞行员。 故可得第四个月的约束条件为600360193334?yxxy （9）又从自然条件知0,0,0,0,0,0,04321321?yyyyxxx （10）由上述 （6） （10）式可得模型的约束条件为11111221112223322233343331231234300330194504501919240450450192401936060019360600?0,0,0,0,0,0,0xyxxyxyxxyxxyxyxxyxxyyxxyxxxyyyy?由LINGO求解可得?11671511234321321yyyyxxx优化目标的最小值即最小总费用为1.64403min?w5.2最优飞行计划模型二此模型与最优飞行计划模型一基本相似，也需要分别找出优化目标和约束，条件不同之处在于每名熟练飞行员可以作为教练每个月指导不超过20名飞行员7（包括他自己在内）进行训练，即每个教练训练的新飞行员人数不超过教练人数的19倍。 5.2.1优化目标的提出与前面模型进行类比可知，在每个月月初招聘的新飞行员人数发生了变化。 因此也可得到此模型各需要费用的项目数量的表4为表4最优飞行计划模型二各需要费用的项目数量第1个月第2个月第3个月第4个月执行飞行任务的熟练飞行员人数300450450600休假期间的熟练飞行员人数0240360360需要购买的新飞机架数6030800新飞行员人数1n2n3n0担任教练的熟练飞行员人数1x2x3x0闲置的熟练飞行员人数1y2y3y4y由题目中的表1和上面的表2分析可得每个月所花费的费用分别为第一个月111173009)(10xx0ynxw? （11）第二个月2409.4?9.6?4509.8?)(9.9?195302222?ynxw （12）第三个月3608.48.64508.9)(8.9190803333?ynxw （13）第四个月3607.47.6?6007.944?yw （14）由 （11）、 （12）、 （13）和 （14）可得四个月花费的总费用即优化目标为4321ww? （15）5.1.2约束条件的提出此最优化飞行计划模型的约束条件除了模型一中的两个约束条件，根据题中已知条件每名熟练飞行员可以作为教练每个月指导不超过20名飞行员（包括他自己在内）进行训练得知，还有另一个约束条件，即每名熟练飞行员作为教练每个月指导训练的新飞行员人数不超过教练人数的19倍。 因此，根据题目中的相关数据和条件可以得出最优飞行计划模型二跟约束条件有关的数据表58表5最优飞行计划模型二跟约束条件有关的数据第1个月第2个月第3个月第4个月可执行飞行任务的熟练飞行员人数执行飞行任务的熟练飞行员人数330111xny?222240xny?333360xny?300450450600新飞行员人数1n2n3n0担任教练的熟练飞行员人数闲置的熟练飞行员人数休假期间的熟练飞行员人数下面是根据每个月具体情况列出的约束条件1x2x3x01y2y3y4y0240360360在第一个月中新招聘的飞行员人数为1n，故可得第一个月的约束条件为111111130033045019xyxnynx? （16）同理可知，在第二个月中新招聘的飞行员人数为2n，故可得第二个月的约束条件为221112222245024045019xyxnyxnynx? （17）同理可知，在第三个月中新招聘的飞行员人数为3n，故可得第三个月的约束条件为332223333345024036060019xyxnyxnynx? （18）同理可知，第四个月的约束条件为4333360600?yxny? （19）又从自然条件知912312341230,0,0,0,0,0,0,0,0,0xxxyyyynnn? （20）由上述 （16） （20）式可得模型的约束条件为300330xy?由LINGO求解可得11111221112223322233343331122331231234123450450240450450240360600360600?1919190,0,0,0,0,0,0,0,0,0xnyxyxnyxnyxyxnyxnyyxnynxnxnxxxxyyyynnn?00072851521312432234321332211yyyynxnxnx优化目标的最小值及最小总费用为64347.50min?w。 六结果分析现对以上所建的两个模型的求解结果进行分析。 6.1最优飞行计划模型一结果分析在此模型中，要是优化目标有最小值即最小总费用为1.64403min?w。 就要这样来安排每个月担任教练的熟练飞行员人数分别为23，11，15，0；每个月闲置的熟练飞行员人数分别为7，6，1，1。 每个月招聘新飞行员的人数分别为437，209，285，0。 6.1最优飞行计划模型二结果分析在此模型中，要是优化目标有最小值即最小总费用为。 就要这样来安64347.50min?w排每个月担任教练的熟练飞行员人数分别为23，12，15，0；10每个月闲置的熟练飞行员人数分别为7，0，0，0；每个月招聘新飞行员的人数分别为432，213，285，0。 七模型推广在以上两个模型的建立与求解中，有一个假设是飞行员的总数变化只由招聘的新飞行员和执行完运输任务后因飞机被乙方部队击落而牺牲或失踪的熟练飞行员的人数决定，其中包括甲方部队不能向第三方部队借调飞行员。 现假设甲方部队能够从第三方部队借调一部分熟练飞行员进行物资运输，这部分熟练飞行员跟甲方部队原本的熟练飞行员除了所得报酬不一样以外其他都一样，在此基础上也可以建立不一样的相应最优飞行计划模型。 参考文献1姜启源，谢金星，叶俊，数学模型M，北京高等教育出版社，xx.11附录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 Globaloptimal solutionfound.Objective value:64403.10Objective bound:64403.10Infeasibilities:0.000000Extended solversteps:0Total solveriterations:238Variable ValueReduced CostX123.00000200.0000X211.00000198.0000X315.00000196.0000Y17.0000007.000000Y26.0000006.900000Y31.0000006.800000Y41.0000006.900000Row Slackor SurplusDual Price164403.10-1.00000020.0000000.000000317.000000.00000040.0000000.000000516.000000.0000001260.0000000.000000761.000000.00000080.0000000.0000002最优化