河流穿越问题 算法实现

landsat99

//   河流穿越模型
//   请给出解决方案、算法实现

landsat99

原型问题：设备性能一定情况下（耗油率、载油量）的最小消耗。 并产生核心算法。


那么可以引申为另一个问题：
什么样的设备性能，对总消耗最为敏感？ 降低设备耗油率、 增加设备载油量，对消耗的改善是否是线性关系？

分析如下

图形显示，
载油量接近拐点或更小，总消耗基本成 指数级增长，导致经济型极差。
耗油率，对最总消耗并不特别敏感。

因此增加油箱容量，是改善的关键因素。

1. import numpy as np
   
2. import matplotlib.pyplot as plt
   
3. 
   
4. def boat(trip_all, fuel, wear):
   
5.     dis_base = fuel / wear
   
6.     dis = dis_base
   
7.     n = 1
   
8.     while dis < trip_all:
   
9.         n = n + 1
   
10.         dis = dis_base / (2 * n - 1) + dis
    
11.         fuel = dis_base * n
    
12.     dis = dis - dis_base / (2 * n - 1)
    
13.     Rfuel = dis_base * (n - 1) + (trip_all - dis) * (2 * n - 1)
    
14.     return round(Rfuel, 1)
    
15. 
    
16. if __name__ == "__main__":
    
17.     fig = plt.figure()
    
18.     ax = fig.add_subplot(projection="3d")
    
19. 
    
20.     wear = np.arange(0.8, 1.2, 0.02)
    
21.     fuel = np.arange(600, 1200, 20)
    
22.     wear, fuel = np.meshgrid(wear, fuel)
    
23. 
    
24.     trip_all = 1500
    
25.     rows = []
    
26.     for Afuel in range(600, 1200, 20):
    
27.         row = []
    
28.         for Awear in range(80, 120, 2):
    
29.             row.append(boat(trip_all, Afuel, Awear / 100))
    
30.         rows.append(row)
    
31.     total_fuel = np.array(rows)
    
32. 
    
33.     ax.plot_surface(wear, fuel, total_fuel)
    
34.     ax.set_xlabel("Oil Wear")
    
35.     ax.set_ylabel("Space")
    
36.     ax.set_zlabel("Total_fuel")
    
37.     ax.set_title("Total Fuel Plot")
    
38.     plt.show()
    

import numpy as np<br /> import matplotlib.pyplot as plt<br /> <br /> def boat(trip_all, fuel, wear):<br />     dis_base = fuel / wear<br />     dis = dis_base<br />     n = 1<br />     while dis < trip_all:<br />         n = n + 1<br />         dis = dis_base / (2 * n - 1) + dis<br />         fuel = dis_base * n<br />     dis = dis - dis_base / (2 * n - 1)<br />     Rfuel = dis_base * (n - 1) + (trip_all - dis) * (2 * n - 1)<br />     return round(Rfuel, 1)<br /> <br /> if __name__ == "__main__":<br />     fig = plt.figure()<br />     ax = fig.add_subplot(projection="3d")<br /> <br />     wear = np.arange(0.8, 1.2, 0.02)<br />     fuel = np.arange(600, 1200, 20)<br />     wear, fuel = np.meshgrid(wear, fuel)<br /> <br />     trip_all = 1500<br />     rows = []<br />     for Afuel in range(600, 1200, 20):<br />         row = []<br />         for Awear in range(80, 120, 2):<br />             row.append(boat(trip_all, Afuel, Awear / 100))<br />         rows.append(row)<br />     total_fuel = np.array(rows)<br /> <br />     ax.plot_surface(wear, fuel, total_fuel)<br />     ax.set_xlabel("Oil Wear")<br />     ax.set_ylabel("Space")<br />     ax.set_zlabel("Total_fuel")<br />     ax.set_title("Total Fuel Plot")<br />     plt.show()<br />

landsat99

qjchen 发表于 2023-2-7 10:04
谢谢manhua兄的解答，不太懂是怎么能保证这个方法是最优的的证明

相关的问题网页及拓展问题

确实是有趣的问题。 感谢各位大咖朋友的交流和优秀见解

我个人理解：设备性能一定情况下（耗油率、载油量），最小消耗==最短的路径规划。
最短路径的约束条件，在终点最明显。从终点开始，倒推反向规划各节点位置及总里程，即为最小消耗。（如从其它位置开始施加约束条件，感觉难度较大。。）

qjchen

谢谢mahuan兄的解答，不太懂是怎么能保证这个方法是最优的的证明

相关的问题网页及拓展问题
https://www.cnblogs.com/bugY/archive/2011/08/19/2146180.html

2020大学生建模竞赛
https://www.doc88.com/p-58861702038642.html?r=1

https://max.book118.com/html/2022/0714/5310304331004304.shtm

这些问题，都是有趣且困难，一直不太懂，学习下

liuhe

你的题是不是少条件了？最少就是2个加油站（出发满油）。至少消耗1500l油，也只会消耗这么多。我猜测你是不是想搞军队运粮草问题，因为军队运粮自己也会消耗粮食。或者少了时间条件。

landsat99

liuhe 发表于 2023-1-29 08:40
你的题是不是少条件了？最少就是2个加油站（出发满油）。至少消耗1500l油，也只会消耗这么多。我猜测你是不 ...

感谢您的问题反馈。为避免歧义，题目已加强修改了文字描述。

向储油点运油 也要消耗燃油。全程消耗的最小燃油量，是问题的求解。

baitang36

到达科考站后还回来吗？

landsat99

baitang36 发表于 2023-1-30 08:35
到达科考站后还回来吗？

感谢您的问题反馈。为避免歧义，题目已加强修改了文字描述。

科考站内有足够燃油储备，不考虑回程油料。

mahuan1279

递归算法。

mahuan1279

650+650/3+650/5+650/7+…+650/29=1518.317>1500,故总耗油最少为（29+1）/2*650=9750升。

landsat99

mahuan1279 发表于 2023-2-3 14:42
650+650/3+650/5+650/7+…+650/29=1518.317>1500,故总耗油最少为（29+1）/2*650=9750升。

您的模型合理。

需要注意的是：
推至最后一站（出发的第一站）,是有剩余里程。 这个解貌似不是精确解。。

mahuan1279

精确解也好求。650*(27+1)/2+(1500-650-650/3-650/7-…-650/27)*29=总耗油最少

landsat99

mahuan1279 发表于 2023-2-3 22:31
精确解也好求。650*(27+1)/2+(1500-650-650/3-650/7-…-650/27)*29=总耗油最少

这组算法合理 清晰。赞一个