针对穿越沙漠问题的最佳决策和最优策略的建模研究

张步昇 田帅军 张艳霞

（1.山西农业大学农业工程学院，山西 晋中 030800；2.山西农业大学动物医学学院，山西 晋中 030800）

1 “穿越沙漠”问题的提出

一名玩家在已知每天天气状况的条件下， 给出30 天之内到达终点的最优路径和资源分配的最佳方案。玩家根据地图提示，从起点出发，利用初始资金购买资源在沙漠中行走。 路途中可能会遇到不同天气，若遇到沙暴天气玩家即可以停留在原地，也可以选择挖矿。 将停留在原地所消耗的资源数为基础消耗量，若在沙暴天气挖矿即为基础消耗量的3 倍，但其可获得基础收益。若玩家资源不充足可用剩余的初始资金或挖矿所得的资金购买，但是每箱价格为基准价格的2 倍。 若到达终点时资源还有剩余可按每箱基准价格的一半退回。目的是在满足上述条件下回到终点尽可能多的保留资金。

题目中提到的地图线路以及相关的各种信息提示，包括每天的天气状况、初始资金、资源的价格和质量、在不同天气不同行为条件下消耗的资源配比和挖矿的收益等信息， 皆出自2020 年全国大学生数学建模竞赛B 题关于“穿越沙漠”问题的探讨，读者可根据所需自行查阅。

2 整体思路的构想

经分析认为， 该问题为最短路径和最优决策问题。 从起点到终点有许多条路径可供选择，先用穷举法确定有限个最优路径方案， 再用Dijkstra 算法求出任意两个区域的最小距离，最后用定量分析购买水和食物数量的最佳方案。 在行走过程中由于天气变化、物资是否充足、挖矿天数和负重上限等因素均会影响最优路径的选择。该问题为了达到最终剩余资金最大化的目的，基于资源的最佳分配下的最优路径，结合Dijkstra 算法规划下最优路径的假设， 对于此我们分开讨论。

3 模型的建立与求解

3.1 Dijkstra 算法规划下最优路径的假设

由地图提出基于最佳资源配置下的最优路径的假设：起点→村庄→矿山→村庄→终点。

3.2 针对最优路径假设的建模分析

不考虑天气的情况下，在基于该路径的算法并结合题中提供的地图可得：

（1） 起点到村庄再到矿山也需要花费8 天时间，其部分路线图规划方案如下：

1-25-24-23-21-9-15（村庄）-13-12（矿山）

1-25-24-23-21-9-15（村庄）-14-12（矿山）

1-25-24-23-22-9-15（村庄）-13-12（矿山）

1-25-24-23-22-9-15（村庄）-14-12（矿山）

（2）从矿山到村庄的路径可以通过上述村庄到矿山的路径反向推出，从矿山到终点的路径基于Dijkstra算法简化可以得出即：15（村庄）-9-21-27（终点）。

考虑天气的情况下，从起点到村庄最少需要用6天时间，前6 天时间里有一天沙暴天气，所以在原来的基础上加上1 天；在此基础上考虑到第7 天还是沙暴天气，所以在原来7 天的基础上加上1 天，也就是说首先从起点到村庄总共需要消耗8 天时间，其中6天行走，2 天在原地停留。 从村庄到矿山需要花费2天时间。 从矿山到终点需要花费5 天时间。 由于到达矿山后再次进行路线模拟假设。假设第一次到达村庄时挖矿7 天，休息1 天，随后路经村庄直接到达终点。基于该路径的模型下，显然挖矿的天数达到7 天时总体收益达到最大， 因此挖矿七天后选择放弃继续挖坑， 剩余资源正好可以满足再次到达村庄的需求，在村庄再次购买正好满足到达终点的资源即可，这样一来就使得到达终点时剩余资金最大化。

3.3 确定资源实时利用的最佳分配

前提假设：（1） 满足上述路径方案且保证到达终点的条件下，总共需要花费24 天的时间，即第24 天正好到达终点；（2） 在起点购买的食物和水必须能保证到达村庄所需要的基础消耗，由于从起点到村庄最少需要用6 天时间， 前6 天时间里有一天沙暴天气，所以在原来的基础上加上1 天；在此基础上考虑到第7 天还是沙暴天气， 所以在原来7 天的基础上加上1天，也就是说首先从起点到村庄总共需要消耗8 天时间，其中6 天行走，2 天在原地停留；通过简单计算可以求出在这种既定的时间天数和天气的条件下，总共需消耗水98 箱，食物98 箱，总负重为490 kg，总花费1 470 元，剩余资金为8 530 元。

在此基础上我们考虑到在村庄购买水和食物是在起点购买费用的2 倍，且食物的基准价格相对于水的基准价格更贵，所以我们设置最初在起点购买水和食物时，在满足基础消耗的前提下，将负重利用率达到最大，假设还可以购买水：食物为1∶2，考虑到剩余150 kg 达到最大负重上限1 200 kg，所以可以再次买75 箱食物，同理通过简单计算可以求出还可以带水80 箱， 食物235 箱， 总负重710 kg， 总花费2 750元，剩余资金为5 640 元；假设上述方案为起点购买水和食物的最佳方案，这样的话总体在起点需要购买水178 箱， 食物333 箱， 总负重1 200 kg， 总花费4 220 元，剩余资金5 780 元。

到达村庄后需要对食物和水进行再次购买，此时考虑到下次再回到村庄补给所需的基础消耗，且需满足尽量避免沙暴天气行走， 可以选择第20 天停止挖矿，再次回到村庄进行补给，这样的话，不仅可以避免在往返村庄时遇到沙暴天气，而且同时也能确定这段时间内需要的挖矿时间为7 天，那么这条路径下的时间和资源的分配也就可以通过简单的计算求出来，即整体这段时间内行走4 天，原地停留2 天，挖矿7 天，总共用时12 天， 在这段时间的基础消耗为： 水245箱，食物217 箱，总负重为1 169 kg，总花费3 395 元，总收益7 000 元。

所以在第一次到达村庄时需要补充水和食物必须能够满足村庄—矿山—村庄这条的路径的基础消耗，在到达村庄时剩余的水0 箱，食物24 箱，总负重48 kg，剩余资金不变为11 150 元，由此可知，我们如果要满足上述的基础消耗，就必须保证需要再补充水36 箱，食物再补充16 箱，通过简单的计算可以知道这种现有的物资满足村庄—矿山—村庄这条的路径的基础消耗。

3.4 建模结果分析与核算

由简化后的线路图结合附件中已知的天气情况、剩余天数、剩余资金、总负重量等因素可以推算出当前条件下未来3 天的最优线路安排为村庄—终点，通过算术简单计算可以求出在次路径下的基础消耗为：水36 箱，食物40 箱，总负重188 kg，剩余资金数不变为10 470 元。

由上可知，第二次到达村庄后需要补给的水和食物只要能够保证由村庄到终点线路的基础消耗即可，这样考虑的原因有以下两条：（1） 达到终点时水和食物正好消耗尽， 不需要用留下的水和食物来推换资金，（2）不会超出负重上限，同时花费保证最少。

所以在满足上述全部要求的条件下算出来的最优路径为：起点—村庄—矿山—村庄—终点，由此路径可以计算出0～24 天每一天的具体剩余资金， 剩余水量，剩余食物量； 且最后在满足题目所有给出的条件下推算出来的尽可能保留的资金为10 470 元。

综上所述：将关卡一整条路径所剩的资金、到达终点花费的时间、挖矿天数、是否超重进行核算，可知在规定的时间内且不超重的情况下该路径剩的资金最多，假设成立。

4 结语

通过对穿越沙漠问题的研究，让学生们更加重视基本理论和基本方法的学习，以及运用计算机建立数学模型解决实际问题的能力。尤其是学生们在建立数学模型时一定要严守结果的正确性和逻辑的合理性，走完解决问题的“最后一千米”。穿越沙漠本质上是一个物资合理化配给径和路最优化的综合性问题，其本身的约束条件多，涉及到物流、通信、TSP 问题、可以推广运用于军事领域的物资运输，解决疫情等紧急情况下的物资调配，线路规划等应用领域。