針對穿越沙漠問題的最佳決策和最優策略的建模研究

張步昇 田帥軍 張艷霞

（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 問題、可以推廣運用于軍事領域的物資運輸，解決疫情等緊急情況下的物資調配，線路規劃等應用領域。