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

尤克众 赵小平 俞琴燕一、问题重述某探险队驾驶一辆越野吉普车穿行2000km的大沙漠。除起点能得到足够的汽油供应外,行车途中的燃料供应必须在沿途设立若干的储油点,依靠自己运输汽油来解决。,车载油箱及油桶总共只能装载250L汽油。请设计一个最优的行车方案,使汽车耗油最少而通过沙漠。我们需要考虑的是,储油点的个数及具体位置、汽车在起点与第一个储油点之间及相邻两个储油点之间单向行驶运输汽油的次数,最后得到最优的一个行车方案和最少耗油量。在解决该问题的过程中,我们得到的数据主要有相邻两点间的距离S[i],储油点离终点的距离为dis[i],汽车在相邻两点间单向行驶运输汽油的次数2i+1,各个储油点的储油量oil[i]。本题需要的也就是一个最优行车方案和对应的各项数据,以及一般情况的讨论。二、。。,而影响其正常行驶。。: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之间单向行驶运输汽油的次数是奇数。基于以上讨论,我们得到该题的一个详细分析:图一:,也就是从终点到起点是:A0、A1、A2……An、An+1。首先我们考虑是从A1到A0需要的油是250L,也就是我们在A1的位置存放250L的汽油才能保证车子到终点。我们把两个A之间的距离写为Si,耗油量为Vi;这样第一步我们知道了A0—A1之间距离S1=1000km,V1=250L。下一步,A1—A2之间,我们必须至少要从A2处向A1开两趟车子(单向)才能保证A1处的储油量为250L。这样因为我们是从A2开向A1处,所以,来回加(双向)在一起应该至少是3趟才能保证A1处有250L的汽油。能保证3次往返最低的耗油量就是250L,那么我们来求出3次往返的250L耗油量的距离就是:S2=1000/ 3。A0—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处储存油,那么