沙漠行车问题的最优方案.doc

沙漠行车问题的最优方案尤克众  赵小平  俞琴燕一、问题重述某探险队驾驶一辆越野吉普车穿行2000km的大沙漠除起点能得到足够的汽油供应外，行车途中的燃料供应必须在沿途设立若干的储油点，依靠自己运输汽油来解决该车在沙漠中行车平均每公里耗油0.25L，车载油箱及油桶总共只能装载250L汽油请设计一个最优的行车方案，使汽车耗油最少而通过沙漠 我们需要考虑的是，储油点的个数及具体位置、汽车在起点与第一个储油点之间及相邻两个储油点之间单向行驶运输汽油的次数，最后得到最优的一个行车方案和最少耗油量在解决该问题的过程中，我们得到的数据主要有相邻两点间的距离S[i],储油点离终点的距离为dis[i],汽车在相邻两点间单向行驶运输汽油的次数2i+1 , 各个储油点的储油量oil[i]本题需要的也就是一个最优行车方案和对应的各项数据，以及一般情况的讨论二、问题假设1．汽车在沙漠中按直线行驶2．行车过程中汽车各项性能及每公里耗油量不受天气等外部因素的影响3．汽车不出现抛锚等状况，而影响其正常行驶4．装油及储油时无油损失5．符号说明：An+1：起点 A0 ：终点                    n ：储油点的个数Ai ：第n-i+1个储油点(i=1,2,…….n)        V：总耗油量Si ：Ai-1 与Ai之间的距离oil[i]：第n-i+1个储油点所储油量dis[i]：第n-i+1个储油点离终点的距离des：沙漠的距离三、数学模型在解决本问题的过程中，我们需要考虑的问题主要有一个，即使本次行车耗油最少而通过沙漠，由于只有起点能得到足够的汽油供应外，行车途中的燃料供应必须在沿途设立若干的储油点，依靠自己运输汽油来解决，因此相邻两点间的距离应小于500km，且储油点的个数应相应多一点，至少应大于或等于3以保证能有足够的汽油完成此项任务。

另外，汽车在Ai-1 与Ai 之间单向行驶运输汽油的次数是奇数基于以上讨论，我们得到该题的一个详细分析：图一：从终点到起点是2000公里.我门从终点开始考虑,也就是从终点到起点是:A0、A1、A2……An、An+1首先我们考虑是从A1到A0需要的油是250L，也就是我们在A1的位置存放250L的汽油才能保证车子到终点我们把两个A之间的距离写为Si,耗油量为Vi；这样第一步我们知道了A0—A1之间距离S1=1000km，V1=250 L下一步，A1—A2之间，我们必须至少要从A2处向A1开两趟车子（单向）才能保证A1处的储油量为250L这样因为我们是从A2开向A1处，所以，来回加（双向）在一起应该至少是3趟才能保证A1处有250L的汽油能保证3次往返最低的耗油量就是250L，那么我们来求出3次往返的250L耗油量的距离就是：S2=1000/ 3A0—A2的距离dis[2] 就是：S1+S2=1000+1000/3而同时在A2处的储油量为：V2=250L+250L=500L继续向下考虑，A2—A3之间，保证A2处有500L的汽油，我们必须要使卡车最少从A1向A2开3趟（单趟），来回就是5趟，路上的耗油量是250L，也就是我们在A3处存放750L汽油。

那么我们来回的距离是S3=1000/5，A0—A3的距离dis[3]是：S1+S2+S3=1000+1000/3+1000/5,同时A3的储存油量是：750L由此推断：如果需要Ai处储存油，那么要i*250的储存量车子从Ai+1到Ai处（单向）的至少要i次加上返回的次数一共是2*i+1次而这2*i+1次的最小耗油量是250L那么Si+1的距离就是1000/（2*i+1）最后i=n到开始地点的距离是2000-(∑Si)  (i为1、2、……,n)，也就是起点至第一个储油点的距离第一个储油点所存油：n*250车子至少要从起点开n+1次满油到n处，加上返回的，一共是2n+1次我们2n+1次的耗油量是0.25*（2000-∑Si ）*(2n+1) 这样起点的油量V=Vn+0.25*（2000-∑Si）*(2n+1)Vn就是从An点到终点A0总的需求油量，即250*n）四、问题求解我们用倒推法得到了本题的一个详细分析，然后再利用C语言程序（具体程序见附一）进行求解最后，我们代入数据，得到本题的最少耗油量为：V=1918.248291L；沿途要设立7个储油点对于题目中的解题方案，我们得出方案的数据如下所示：（沙漠长度des=2000km）表一：AiSi  ( km)Vi  (L)dis[i]  (km)A110002501000A21000/35001333.333374A31000/57501533.333374A41000/710001676.190552A51000/912501787.301636A61000/1115001878.210693A71000/1317501955.133789 再将此算法推广至一般情况的过程中可以看到，只需改变约束条件，就可得出相应的行车方案。

以上所采取的算法很显然是适应于一般情况的，只需我们给定其他数据就可得到所需的最优行车方案另外，我们还可以利用数学分析中化求和为积分的方法解不等式来计算解n：{250/0.25[1+1/3+1/5+ …… +1/（2n-1）]<2000    250/0.25[1+1/3+1/5+ …… +1/（2n-1）+1/ (2n+1)]>2000   (其中n为正整数)解得i=7, 表示要设立7个储油点，结果同表一五、模型的讨论与推广我们可以从简单一些的情形开始考虑：1.沙漠只有500千米或者更短，这时很简单，一次加足油量就可以到达终点2.沙漠1100千米怎么办呢？我们需要保证的是；车到了离沙漠终点有1000km的地方，能恰恰加油而且不会有任何多余，好了，方案其实很简单，从起点处加75L油，这75L油怎么用呢：开出100km，存下25L，剩下25L刚好使得汽车返回起点再在起点处加满250L油，这时就可以一路狂奔了，当然，要记得开了100km后，把存放在那儿的25L油也加上这在起点的油一共是250＋75=325L）3.我们先看看2的情况，符合这种情况的沙漠的最大距离是多少呢：答案是（1000+1000/3）km。

即在起点准备500L油，第一次装250L，跑了1000km后存放250/3L油，然后返回起点，这时车里的油也正好用完，然后再在起点处装250L，跑了1000/3km后，把车内的（250－250/3）L油先放下，然后再一次性把250L油装入车中4.当沙漠的距离超过了（1000+1000/3）km（但又超过得不多）又当如何？这时我们可把  前面的（1000＋1000/3）km看成一段整体，需要保证的是：在距离沙漠终点（1000+1000/3）km处恰恰有500L油（由3的分析可知）怎么来保证呢，我们假设沙漠的距离只比（1000＋1000/3）多了1km，因为汽车的容量是250L，所以500L油最少从起点装3次油才能倒满除了3次装油，还有两次折回，所以往返正好有5次，这5次的能保证的距离是1000/5km，所以这时我们又把沙漠的距离延伸到了：（1000+1000/3+1000/5），起点应该储备750L油4.当沙漠的距离超过了（1000+1000/3+1000/5）km，我们要保证的是在距离沙漠终点（1000+1000/3+1000/5）km的地方有750L油根据以上的详细且比较合理的分析，易知，总可以找到一个值使得dis =1000+1000/3+1000/5+..+1000/(2i-1)<2000, 但是1000+1000/3+1000/5+..+1000/(2i-1)+1000/(2i+1)>2000，应该在起点准备多少油呢？这时多了一小段出来，很像情形2的分析了，说白了，在起点准备的油应当是：0.25*(2000 - dis)*往返次数 + i*250。

详细解法（具体程序见附二）另外，我们在解题过程中提到还可以利用数学分析中化求和为积分的方法计算，一般公式为：a/b[1+1/3+1/5+ …… +1/（2n-1）]des六、模型的优缺点分析1.本模型利用倒推法简化问题,运用C语言程或者化求和为积分对问题进行求解,简单易懂,且较直观2.本模型还给出了一些推广以及一般情况的讨论，使模型更具普遍性3.本模型具备一定的实用性，但没有考虑汽车在沙漠中行驶的各种非主观因素的影响，如：沙漠风暴、风向、汽车抛锚、漏油、汽车在行驶中的磨损导致耗油量的增加、未直线行驶等等七、模型的改进根据以上情况，我们可以适当缩短两个储油点之间的距离，使汽车通过沙漠的安全系数增加八、模型总结本模型基于实际情况给出了较为简单的C语言程序和化求和为积分的方法解不等式，并给出了一般情况的讨论，使模型不论在理论上还是在实际上都显得比较易懂与实用，所以本模型是较为成功的。