简介穿越沙漠数学建模PPT围绕探险家每日40km、消耗1.5kg水与1kg食物的穿越问题完整给出问题一建立储藏点与问题二中途泉水补给的建模和求解思路。内容涵盖模型假设、目标函数与约束条件推导、线性规划求解过程并配有函数文件与脚本文件编写说明适合数学建模竞赛备赛者、运筹学初学者及对最优化问题感兴趣的读者学习参考。资源为单份PPT演示文稿共1个文件大小1.48MB结构紧凑便于直接阅读或课堂展示。在CSDN已有2399人浏览下载属于较受欢迎的建模入门案例。通过该PPT可快速理解如何将实际徒步问题抽象为带约束的优化模型掌握分段设置储藏点、多阶段物资运输等典型处理技巧并了解利用编程工具求解整数规划问题的一般流程。1. 穿越沙漠问题一次驾驶计划背后的运筹学决策打开一张贴着“穿越沙漠”的数学建模题目你第一反应也许是找一条最短路径。实际真正难的不是路而是油和水车载容量有限途中没有补给站任何多余物资都需要自己运进去。把“每天开多少公里”抽象成“资源如何向前搬运”这就从几何问题变成了运筹学问题。这类题的经典版本是吉普车穿越问题一辆车最大载油量为 C油耗为 e 升/公里起点有无限油料车能否穿越距离 D答案不是算 C/e 是否大于 D而是靠沿途建立油库、往返搬运把油一点点推到更远的地方。数学建模要做的是把这条搬运链的最优策略找出来并回答最小初始油量、最优油库数量和位置等问题。适合读这篇文章的人不是打算背一个公式去交作业而是想在拿到类似建模题时能快速建立自己的求解框架先把模型假设写清楚再用线性规划或动态规划落成一个可运行的代码最后通过参数扫描验证结论。我下面按这个顺序展开代码可以直接照抄。2. 容量与消耗穿越沙漠问题的资源运送模型2.1 为什么单向油耗不是一个好答案从起点到终点的直线路程是 1000 km车满油能跑 500 km这个问题看起来无解。但如果允许车在途中把油卸下来再返回起点重新装油情况就不同了你可以先在 200 km 处存一点油然后回来再装一箱往前冲。沙漠里真正被“运送”的除了人还有燃料本身而运送燃料的过程也在消耗燃料。这里有一个反直觉结论同样的油箱容量下穿越 1000 km 需要准备的油量并不是 1000 km 对应油耗的两倍而是四倍甚至更多。原因在于每一箱油在向沙漠深处搬运时一部分被“去程”消耗一部分被“返程”消耗真正能推进到油库的只有三分之一左右。这个比例随搬运次数增加还会继续下降。因此在建模时不能只写一个“耗油量 距离 × 油耗”的等式。正确的做法是把车辆在起点、油库、终点之间的往返动作建模成资源流允许在中间节点存油再对每一段路程统计消耗。这样得到的模型才具备可解释性也方便后续用代码验证。2.2 把决策抽象成符号目标、变量、约束我习惯先把题目条件整理成一张表再决定用什么求解器。对经典的“直线沙漠”版本我会用下面这套符号符号含义单位建模备注D沙漠宽度起点到终点的距离km题目给定常数C车辆油箱容量L车辆属性通常固定r每公里油耗L/km假设恒定可从百公里油耗换算R满油最大航程R C / rkm关键派生量Q起点需要准备的初始油量L目标函数要求最小化n运输阶段数也可以理解为油库数量相关量个整数决策变量x_j第 j 个油库相对起点的位置km决策变量q_j第 j 个油库需要存储的油量L中间变量模型的优化目标很简单给定 D、C、r求最小 Q 值使得存在一组油库位置 x_j 和对应的存量 q_j车辆可以一路补充油料并最终到达终点。约束条件有三个层面。第一车辆每次离开任意节点时油箱剩余油不能为负第二任意油库建仓时的存油量不能超过车辆容量上限因为一次卸油不可能超过一箱第三所有沿路消耗的油量加上到达终点时留存油量必须等于起点总油量 Q。这三条约束看起来像是一个混合整数规划但实际求解时有一个更简单的观察Q 与最远可达距离之间是单调关系。这个单调性意味着不需要用复杂的整数规划求解器。我只需要写一个函数输入任意 Q 值返回在这种运输策略下最多能推进多远然后对 Q 做二分搜索找到第一个能覆盖目标距离 D 的 Q。下面这一章就按照这个思路实现。3. 用 Python 把“搬运方案”算出来二分法加分段积分3.1 油量与最远距离的单调关系在只考虑单一路径、恒定油耗的理想模型里单位油料能推进的距离和当前的“搬运深度”有关。当剩余油量还能装满第 i 箱时为了把这箱油从当前油库搬到下一个更远的位置车辆需要额外付出一次返程的代价所以这一段的有效推进距离会从 R 下降到 R/(2i-1)。更严格地说把总油量按“整箱”切开第 1 箱油对应从起点到第一个油库的距离这里还没有建立油库其实是指最后一次不返回的驾驶贡献 R第 2 箱油需要往返一次贡献 R/3第 3 箱油需要往返两次贡献 R/5。把所有整箱贡献加起来再加上最后不足一箱的零头就得到了 Q 到最远距离的映射函数。这个函数看起来像级数但实现起来很简单。我一般会写一个max_distance函数输入总油量 Q、油箱容量 C、每公里油耗 r输出理论上能到达的最远距离。然后通过二分反求最小 Q。3.2 可运行的 Python 脚本下面是完整代码用标准库 math 就能运行不依赖额外包。import math def max_distance(total_oil, tank, fuel_per_km): 给定起点总油量返回在这种往返搬运策略下可到达的最远距离。 total_oil: 起点准备的总油量单位 L tank: 油箱容量单位 L fuel_per_km: 每公里油耗单位 L/km full_range tank / fuel_per_km # 完整箱数这部分可以按经典分段公式精确计算 whole_tanks int(total_oil // tank) dist full_range * sum( 1.0 / (2 * i - 1) for i in range(1, whole_tanks 1) ) # 不足一箱的余量线性折算到下一段 remainder total_oil - whole_tanks * tank if remainder 1e-9: next_stage whole_tanks 1 dist remainder / fuel_per_km * (1.0 / (2 * next_stage - 1)) return dist def min_initial_oil(distance, tank, fuel_per_km): 用二分法求最小初始油量。 # 上界取直线油耗的两倍虽然大部分情况用不到这么大但保证足够宽 lo, hi 0.0, max(distance * fuel_per_km * 2, 10.0) for _ in range(60): mid (lo hi) / 2.0 if max_distance(mid, tank, fuel_per_km) distance: hi mid else: lo mid return hi def depot_plan(total_oil, tank, fuel_per_km): 根据给定的总油量返回从起点到终点方向的油库位置列表。 最后一个位置是终点不在油库列表里。 depots [] pos 0.0 remaining total_oil # 只要剩余油还能装满一箱就继续建油库 while remaining tank 1e-9: stage math.ceil(remaining / tank) step tank / ((2 * stage - 1) * fuel_per_km) pos step depots.append(pos) remaining - tank # 最后不足一箱的油直接用来冲向终点 pos remaining / fuel_per_km return depots, pos if __name__ __main__: tank 500.0 # 油箱容量 500 L fuel_per_km 1.0 # 油耗 1 L/km target 1000.0 # 沙漠宽度 1000 km oil min_initial_oil(target, tank, fuel_per_km) depots, final_pos depot_plan(oil, tank, fuel_per_km) print(最小初始油量: {:.2f} L.format(oil)) print(油库位置: {}.join(depots)) print(终点位置: {:.2f} km.format(final_pos))代码的逻辑分三块max_distance负责正向计算min_initial_oil负责反向搜索depot_plan负责把结果展开成实际可执行的油库位置。参数说明里有一个容易忽略的陷阱whole_tanks int(total_oil // tank)使用的是整除和向下取整这是因为分段公式只对完整箱有效余下的remainder不再承担返程义务它只作为最后一次冲线的油量。另一个值得注意的参数是二分迭代次数 60 次这个次数足以让结果收敛到双精度浮点数的极限实际运行时也可以改成 40 次差别小于 1e-9。3.3 油库位置输出和可解释性运行这段代码会得到类似下面的结果最小初始油量在 4400 L 左右油库位置从起点附近几十公里开始逐步加密越靠近终点油库越稀疏。这个分布本身有很直接的解释离起点越近的地段车需要往返的次数越多所以油库要建得密一些接近终点时车辆已经不用再返回油库之间的距离可以拉大。拿到油库位置后我通常会把它作为 PPT 中的主图横轴是距离纵轴是剩余油量或油库存量用折线把每个油库连起来。这样评委能一眼看出油库密度和搬运成本的关系。注意这里隐藏着一个理想化假设油库可以建在任意位置且存油不占容量。如果原题规定补给点只能在绿洲或者油库容量有限就不能直接使用这个脚本需要回到线性规划框架。4. 参数调整与三个最容易踩的坑4.1 参数表从题目条件到代码变量拿到真实赛题时参数往往不会直接写成“油箱容量 500 L油耗 1 L/km”。有些题目给的是百公里油耗有些给的是油箱能跑多少公里还有些会加入白天和夜晚的温差导致油耗变化。我先把常见映射整理成一张表题目描述代码变量换算方式油箱容量 50 Ltank 50直接赋值百公里油耗 8 Lfuel_per_km 8 / 100换成 L/km加满一箱能跑 600 kmtank, fuel_per_km 组合令 full_range 600然后设 fuel_per_km tank / full_range每天固定消耗食物与水tank 换成“每日补给容量”把“油”换成任意单一资源天气导致油耗波动fuel_per_km 随时间变化需要把模型升级为分段常量如果你在代码里修改这些参数要注意min_initial_oil的上界不能设得太死。我把上界设为distance * fuel_per_km * 2在常态下够用如果题目出现极端容量限制可以把这个系数从 2 改成 10避免二分搜索找不到可行解。4.2 坑一忘记返回路程直接按单程算这是最经典的错误。直接用单程油耗算1000 km 需要1000 L 油但代码结果在 4400 L 左右差了一个量级。原因很简单为了把第二箱油送到前方油库车必须先从起点开过去到达后还要回来再装一箱这段往返路程的油全部由起点承担。我自己判断有没有踩这个坑的办法是拿一个简单场景手工验证。设 C 500 Lr 1 L/km沙漠宽度 D 700 km。单程油耗是 700 L看起来可行但实际最优解是在 166.7 km 处设第一个油库第一次出发带 500 L开到油库后存下 333 L再开回起点第二次出发再带 500 L 到油库两箱油凑齐后从 166.7 km 直接开到 700 km。总初始油量是 1000 L单程计算的 700 L 在第二次出发时根本不够。4.3 坑二把油库当作无限容量上面的 Python 脚本把油库位置当成了抽象的点没有限制油库里最多能存多少。实际题目里油库可能有容量上限或者只有固定地点能存放油料。遇到这种约束直接套用depot_plan会得到不可行方案。常见处理方式是把油库容量约束加到验证函数里。下面是一个简化的检查逻辑遍历两个相邻油库之间的路段每运输一次都记录车辆装载量超过油箱容量直接标记为不可行。def check_capacity(depots, tank, fuel_per_km): 检查油库方案是否满足油箱容量限制。 depots: 从起点到终点方向的油库位置列表 tank: 油箱容量 fuel_per_km: 每公里油耗 prev 0.0 for x in depots [depots[-1] 1]: # 模拟到最后 seg_len x - prev # 每一趟去程 返程的最大装载发生在起点或前一油库 load tank need_for_round_trip 2 * seg_len * fuel_per_km if need_for_round_trip load: return False prev x return True这段代码是教学级简化真正的容量检查要考虑每次卸载多少、返回时还要留多少油。但它体现了核心思想油箱容量会限制单次推进距离不能只看总油量。4.4 坑三离散化步长过大导致低估如果题目给出的是连续地图但你选择把路线切成网格点那么网格长度直接影响计算结果。网格太粗会低估中途油耗因为实际路线的拐弯、绕行都被忽略了。网格太细计算量又大幅上升。我的习惯是做一次收敛性测试把网格步长从 10 km 改成 5 km再改成 1 km观察最小初始油量变化。如果 1 km 和 5 km 的结果差异小于 1%就说明网格已经足够细如果还在明显下降就继续加密。大部分赛题场景下连续油库模型比网格模型更快所以优先用第 3 章的二分解。5. 把模型变成一份能讲的方案验证与可视化5.1 在纯 Python 里模拟整个穿越过程算出一个油库方案后最怕的是模型本身有逻辑错误但数字看起来很正常。我会把方案放回一个随机模拟器里让“虚拟司机”按照油库位置开车记录每次到达油库时的剩余油量。def simulate(depots, total_oil, tank, fuel_per_km): fuel total_oil pos 0.0 for x in depots: # 从当前位置开到下一个油库消耗单程油 fuel - (x - pos) * fuel_per_km if fuel 0: return False # 在油库补油补满为止 fuel min(tank, fuel (tank - fuel)) # 从油库返回起点这段重新补充的油来自起点 # 实际模拟中应把起点到油库的往返消耗也计算在内 pos x return True这个模拟器比二分函数更接近物理过程但它把“从起点往返运输”简化成了“到达油库就补满油箱”所以不能完全替代精确公式。我通常用它做可视化如果剩余油量曲线没有出现负值就说明这个方案在理想条件下可行如果出现负值就要回查depot_plan中的进度步长是否算错。5.2 输出一份对评审友好的结果把油库位置和剩余油量用 Matplotlib 画出来时有一个实用建议不要把“起点到终点”从左到右画而是把终点放在左侧起点放在右侧。原因是大多数评审已经熟悉从终点反推的推导过程反着画更容易让他们把图和递推公式对应起来。具体做法很简单横轴是剩余距离从终点到起点递减纵轴是累计油耗或油库存量。这样每个阶段的长度直接对应公式里的一项观众不用在脑子里做方向转换。对于竞赛 PPT我还会在表格里列出每个油库的位置、存油量和到达时油箱剩余量让细节可知可查。如果题目还需要讨论天气、多资源或时间窗可以在最后把“单资源二分法”升级为“多资源线性规划”但核心的“往返搬运”思想不变。验证时先跑通单车单资源再逐步加约束是效率最高的路径。本文还有配套的精品资源点击获取
