空中加油问题

论文题目：空中加油问题参赛选手:题目：空中加油的优化解法［摘要］本文讨论了空中加油问题中如何获取最大的作战半径的加油方式。首先我们通过逻辑推理，算出在总辅机数n4情况下的最佳作战方案，找出其一般规律。然后证明了对称性方法的最优性，求解时将辅机分为两类，一类专为飞机前进服务，第二类专为飞机返回服务，通过对称性方法、逐层分析和对比，利用穷尽列举法，得出了在满足假设条件下，按照n取值不同而确定的最优作战方案，依据得出的数据结果，利用spss软件拟合函数，预测出在n*时的七关于n的渐进关系式。接着在前两问的基础上，引进飞机可重复飞行的条件，通过对称性方法将模型简化为问题2的一种情况，求得r。在第4问中先通过图解法，以1架辅机确定另两个基地的位置，由于基地的不可移动性：联系问题3,讨论出r。最后利用图解法，与前几问联系求出第5问的解。期间用到的大部分模型都做出了选择或舍去的证明。本模型虽然在假设条件的限制下有一定的约束性，可是其通过计算机穷尽列举的方法，在许多问题中都有所应用，具有普遍性，也不失为一种算法。本模型对于其它运输规划问题有一定的参考价值。关键词：图解计算机穷尽列举逐层分析渐进关系式一、问题的重述对飞行中的飞机进行空中加油，可以大大提高飞机的直航能力。为了简化问题，便于讨论，我们作如下假设。设A为空军基地，基地有一架作战飞机（简称主机）和n架加油机（简称辅机）。主机与辅机的速度和单位时间的耗油量均相同且为常数，油箱装满油后的最大航程均为L（公里）。辅机可以对主机加油，辅机之间也可以相互加油。今主机要执行某作战任务（如侦察或空投），所有飞机在完成自身的任务后均要求返回基地。主机的最大作战半径（简称作战半径）是指主机在n架辅机的协助下所能飞到的（并安全返回）离基地A的最远距离。显然当n=0时，作战半径,0=L/2。问题1设飞机垂直起飞、垂直降落、空中转向、在地面或空中加油的耗时均忽略不计，每架飞机只能上天一次，在上述假设下的作战半径记为r.。当n=1,2,3,4时，求作战半径r〃。问题2在问题1的假设下，当n>4时，尽你的可能求出二（提示：先假设辅机可以分为两类，第一类专为主机前进服务，第二类专为主机返回服务，再考虑一般情形）或给出rn的上、下界；讨论当n*的过程中七与n的渐近关系；试给出判断最优作战方案（主机能够飞到r处）的必要条件或充分条件:n问题3若每架辅机可以多次上天，辅机从机场上空降落及在地面检修、加油、再起飞到机场上空的时间相当于飞行L/12的时间，飞机第一次起飞、转向、在空中加油的耗时仍忽略不计，此时的作战半径记为Rn，讨论与问题1、问题2类似的问题。问题4若另有2个待建的空军基地（或航空母舰）A】,气，有n架辅机，主机从基地A起飞，向一给定的方向飞行，必须在基地A降落，辅机可在任一基地待命，可多次起飞，且可在任一基地降落。其它同问题3的假设，讨论A1，A2的选址和主机的作战半径R*。问题5设ABCD为矩形，AB=4L，AD=2L，A,B,D为三个空军基地，主机从A起飞，到C执行任务（执行任务时间仍忽略不计）再返回A。假设辅机起飞、降落的基地可任意选择，其它同问题3的假设，试按最快到达并返回和最少辅机架数两种情况给出你的作战方案。二、模型假设辅机可以对主机加油，辅机之间也可以相互加油；辅机在同一时刻可以给多加飞机加油；油箱装满油后的最大航程为L，为了便于计算我们以油量代替航程，假设一架飞机每公里耗油量为1，即一架最大载油量为L；假设飞机的航速为1；飞机垂直起飞、垂直降落、空中转向、空中加油的耗时均忽略不计；三、符号说明七：第i个加油点与基地的距离;::n架辅机时的作战半径乙：飞机最大航程或最大载油量四、模型建立与求解问题1问题分析：根据假设4,飞机垂直起飞、垂直降落、空中转向、在地面或空中加油的耗时均忽略不计，每架飞机只能上天一次，我们不难得出，在辅机数量一定的情况下，要使主机航行最远，需使每一架飞机的油量都用于飞行，并且回到基地时无剩余。根据条件：主机与辅机的速度和单位时间的耗油量均相同且为常数，使得辅机给主机加油只能有两种情况：①与主机同时起飞在某一地点加过油后返回；②接应主机，相遇后加油在与主机一起返回。题目中要求求出n=1，2,3,4时的作战半径〃〃，必须先确定此要求下的加油最优方式，然后按照最优的加油方式分别求出结果。根据最直观的想法我们让尽可能少的辅机在空中飞行，这要求辅机在接应主机时是陆续起飞的。模型建立和求解：补充假设：辅机可同时给其它飞机加油，并且有足够的油量使自己返回基地。某个加油机在某个地点给其它每架飞机的加油量相等(使送走的飞机的储油量最大)，并且加完油后立即返回。定理1(引理)：每次加油均将其它飞机油箱装满，所有返回基地时油量刚好用完的情况下作战半径最大。证明：在每次加油未将其它飞机油箱均装满的情况下，设加油点为X；，我们知道所有飞机的油，要么用于主机飞行，要么用于辅机飞行。即辅机飞行的越多主机飞行的越少。第i个辅机，其在没有其它辅机的接应情况下安全返回基地的条件L+玄1T-T-2X>0k=1。•为要使飞行距离最远，即二最大，则条件是应该取等号，即辅机返回基地时油量刚好用完。i-1L+左T-Tki又X=k=12V'―-当存在第i架飞机未将其它飞机油箱均装满的情况下返航，则由T减减小推出X•>七,即辅机总飞行距离增大，主机飞行距离减少。'证毕。按照给出的最优加油方式，k+1架飞机一起起飞，到x1点处辅机W](第一架飞机)给其它飞机加满油并返回，则可视为.的油量用于k+1架飞机走完、的距离，即气=上。那么对于辅机w(i<k),有ix+(k-i+3)(x,-x,)=1由类推关系式得iLx=ik+2kL...一L一..一.王机在距离基地为伟处加完油’此时王机有两种选择，。向前飞笊后自行返回3由辅机接应返回。当增加一架飞机时’对于第一种选择’其作战半径为♦空半当增加一架飞机时，对于第二种选择，由这一架飞机接应则有,kLLL—+r=_L+k+23k1k+22化简得_(k+1)LLk1=k+2~6显然，rk1<rk1那么当增加i架飞机时，其中i<k(k+i+1)L对于第一种选择’其作战半径为rki=M对于第二种选择(k+1)LiLrki=k+2*2(+2)'用数学归纳法容易证明七>rk，显然％是关于i的单调递增函数。那么，最优的加油方式是k架辅机送主机，k架辅机接主机。但此时总的辅机数量n=2k始终为偶数。当n为奇数时’最优的加油方式：料架辅机送主

机，旦架辅机接主机。2在此种加油方式下当n=2k时nLL

nn+42当n=2k-1时_(n+3)L(n,—1jnn+52(n+3)(n=2k)nLL

n+42

(n+3)L(n-1)L(k=3，4，5，(n=2k)k+E……(n=2k-1)1.n=1时，主机与辅机同时起飞，辅机在位置\为处给主机加满油，厂手如图:1.n=1时，主机与辅机同时起飞，辅机在位置\为处给主机加满油，2.n=2时，一辅机负责送主机，另一辅机负责接主机，这种方案满足同一时刻在空中飞行的辅机数量最少，则此时r2=羊.如图：

3.n=3时，两个辅机送主机一个辅机接主机，与一个辅机送主机两个辅机接主机情况相同（对称性原则）。作战半径了肯如图：4.n=4时，两个辅机送，两个辅机接，此时L结果如下表xxXXrn=1n=2n=3n=41/32L/31/31/35L/61/41/21/311L/121/41/21/21/4L问题2问题分析：由第一问建立的模型对于n比较小时是有积极意义的，但通过计算，当n>16时，增加飞机数对rn的增大贡献不大。并且这一模型有极值为1.5。与实际有矛盾，那么，当n>15时，需要另外建立模型。模型建立和求解：按照第一问的结果(n=2k)jnL+L_n+42n+52(n+3)T(n+3)L(-1)L(n=2k_1)当nT8时rr1.5L，显然当n到达某个值之后，在增加辅机数对作战半径的增加贡献小到n(n=2k)n+52(n+3)没有意义了。那么，改进模型，假设存在辅机接辅机的情况，即递返模型。如图，最上面的一层表示k架辅机送主机，第二层表示上架飞机被k2送，以此类推得出当有/层时（不包括主机的最后一层）。此时n=2（k+1>-2n+2r=与业*—^L+-

nlg(k+1)k+22求导得，当k=1时q取最大值。所以lg¥Llg23以上只讨论了每一层均为k送1的情况，而实际情况可以每一层的几送几是一个组合情况，例如最上面一层选择2送1，则倒数第二层可选择m送3的情况，其中m可取大于3的符合组合数的整数，例如6,9,12等。由此，当n一定时，用穷举法列举出所有可能，求其使半径最大的最优解，就是最优方案，当n过大时，在实际过程中难以实现，没有实际意义，并且计算量过于庞大，下面，我们用MATLAB6.5编程计算出当n<1200，有8个加油点，由于6送1到7送1时△［很小，所以只讨论最多6送1的情况下的最优解。（程序见附录）将数据做处理后用spss10.0作出拟合曲线并作出图像如下：结果显示其可绝系数R2=0.99194，拟合残差平方和为0.360665，拟合函数为r=0.448252ln(n)+0.268119拟合效果较好。最优作战方案(主机能够飞到%处)的必要条件通过解题过程，基于对第一问和第二问的认识，我们认为判断一种作战方案是否为最优方案必须满足以下条件：Q让尽可能少的辅机同时在天空飞行。Q辅机可同时给其它飞机加油，并且有足够的油量使自己返回前一次加油地点。Q每次加油均将其它飞机油箱装满，并且加完油后立即返回。Q任意一架飞机返回基地时的油量为空。Q送主机的辅机同时起飞。问题3辅机从机场上空降落及在地面检修、加油、再起飞到机场上空的时间相当于飞行L/12的时间，我们取辅机的二次起飞间隔为L12每架辅机可以多次上天，在不考虑二次起飞间隔时，就与问题2模型类似，相当于有2n架飞机，其中n架为主机前进服务，n架为主机返航服务。我们只以问题2中的1送1模型求解由于所有送主机的飞机都是同时起飞，所以无论有多少层，只要一层的飞机可以二次起飞，则所有的飞机都可以。

当k架飞机送主机时，第i(iWk)架飞机的加油点(距离上一次加油点)为:x=-^(k=1,2,3......)ik+2则第i架飞机最大等待时间(i=1,2,3......k)kLt八iLk+1-iTt=+L-2L1k+2k+2k+2即：(i=1,2,3......k)k+1-i

t=ik+2则：1t=imink+2也就是说’当z。时’不用考虑飞机二次起飞的时间间隔’它们都小或等于!|,可按照问题2中的情况讨论。当k>10时，第10架以后的飞机都不能保证作战半径最大前提下按时起飞，因此可以减少主机在被第k架辅机加油后飞行的距离，即主机提前返航，从而保证每架飞机都能二次起飞并1接到主机。由于辅机最大等待时间的最小值t=—，如下图所示：未考虑二次起飞时间间隔主机返航点八、、i未考虑二次起飞时间间隔主机返航点八、、B^S-1/12-1/(k+2)v厂考虑二次起L/2—Fl^~C飞时间间隔主机返航点主机须在返航点不能超过B,设放航点为C点只要2BC2L-y所有辅机就都有足够的二次起飞时间，可得:BC=L(上--^-)min212k+2则最大作战半径

.kL=ik2+ACrkmax=C^L+L-BCmaxk+22min.kL=ik2+ACrkmax即:rkmax=上+L-L(_!，k+22212k+2综上可得化简得:rkmax=上+L-L(_!，k+22212k+2综上可得化简得:r=kmax2k+4"哮(k>10)必+Lk+222k+111r=〈1n2k+4242ik+1(11k+4+24k<1015>k>10k>15表1最大作战半径rn辅机架次n主机作战半径r(L)辅机架次n主机作战半径rn(L)10.8333111.342921.0000121.351231.1000131.358341.1667141.364651.214151.5

由于k>15时r=——里2+旦k>15，显然当n—8,r—8n2k+424n问题4为了获得最大的作战半径，我们将A】,气与A建在同一条直线上。我们假定待建的空军基地位置一旦确定就不再变动，因此我们首先讨论n=1时的情况:首先，我们将加油机始初位置置于A1当主机飞向A1，加油机来接应，此点主机将油全部用完。其飞行路程为L，在此地点接受第一次加油后同加油机一同飞至A1。在此时主机剩余油量L，在空中盘旋顶油机油量为零，在基地中；然后经£的时间后加油机飞出，将主机加满，然后飞回基地；主机仍盘旋与空中，L11仍的时间后与'加油机再次将王机加满然后一同飞至A2。其油量分别为王机L，加油机为正L，到A时，主机仍剩余L，再次重复A时的做法，使油量为主机L，加油机为11L。然后一212112

同飞行往F,到达D时，加油机将油加给主机，留足油量返回。主机依旧向前飞行，到达F返回，加油机再次去迎接，然后一同返回。重复去时的过程。详细过程如图：第-沔胃二f加油第四欧油第三次加油AiAs蓝色箭头代表1：机，瞿色代表加油机箭头方向表示飞行方向其最大作战半径就为AF，以飞行方式列出方程组:3BA+—=L\o"CurrentDocument"112<2A1A2+—=L+当1212L4711109求解得AA=—L,AA=—L,AF=—9L\o"CurrentDocument"136121236AD+—=L2122AiAs蓝色箭头代表1：机，瞿色代表加油机箭头方向表示飞行方向其最大作战半径就为AF，以飞行方式列出方程组:3BA+—=L\o"CurrentDocument"112<2A1A2+—=L+当1212L4711109求解得AA=—L,AA=—L,AF=—9L\o"CurrentDocument"136121236AD+—=L2122DF=Ln=1时，.R*=109L\o"CurrentDocument"136当n=2时，我们可以将一量加油机置于A2，一量置于A】。因此主机与加油机1飞至一同飞至A2次过程同n=1。然后问题相当于1辆主机2两主机从气往前飞，，+80L362k+111,当15>k>10时R*=+Ln2k+4242(k+1)当k>15R*n当k>15R*nin+12—Lk+1lg2+112k+4242(k+1)史L+80L

36问题5如图5.1情况①，以最短时间到达C,则必须沿路线AC并且不能停止，即始终向前，利用递返模型（k=1）求解，即.n+1lg^Llg23当r=2寸'5L时，解得n=7730n5.2情况②，用最少飞机到达C，则必须充分利用基地B和D，由第4问，为了获得最长半径基地最好在其飞行路线上，那么现在有两种飞行路线：当飞机沿A-B-C路线飞行时，由第3问的模型求解，需要主机相对于A，B的作战半径为2L,由此对照第3问中的软件结果得总辅机数为48x3+1=145架，分配方式是，A点48架，B点97架。当飞机沿A-D-C路线飞行时，由第3问模型求解，只研究D到C这一段路程就需要大于300架辅机。已经大于第一种飞行路线所需的辅机数量，所以，飞行路线为A-BfC的结果，那么依据假设条件，最少飞机为145架。五、模型的评价和推广本模型分为5个小问，每一问所包含的问题基本是要求选择最优的加油方式，这种问题在实际生活中有重要意义，基于问题的限制。此模型还可用于空中运输，沙地推车等问题的解决，当然对于不同的限制条件与实际问题，此模型还需要修正，但其解题思想不变：优中选优，以求最优。六、总结评价优点：①本模型通过逐步证明求解，以发散式思想，在限制条件下不断优化加油方式，寻求最优结果，这在思考方式上是一种创新。。整体