針對(duì)穿越沙漠問(wèn)題的最佳決策和最優(yōu)策略的建模研究

張步昇 田帥軍 張艷霞

（1.山西農(nóng)業(yè)大學(xué)農(nóng)業(yè)工程學(xué)院，山西 晉中 030800；2.山西農(nóng)業(yè)大學(xué)動(dòng)物醫(yī)學(xué)學(xué)院，山西 晉中 030800）

1 “穿越沙漠”問(wèn)題的提出

一名玩家在已知每天天氣狀況的條件下， 給出30 天之內(nèi)到達(dá)終點(diǎn)的最優(yōu)路徑和資源分配的最佳方案。玩家根據(jù)地圖提示，從起點(diǎn)出發(fā)，利用初始資金購(gòu)買(mǎi)資源在沙漠中行走。 路途中可能會(huì)遇到不同天氣，若遇到沙暴天氣玩家即可以停留在原地，也可以選擇挖礦。 將停留在原地所消耗的資源數(shù)為基礎(chǔ)消耗量，若在沙暴天氣挖礦即為基礎(chǔ)消耗量的3 倍，但其可獲得基礎(chǔ)收益。若玩家資源不充足可用剩余的初始資金或挖礦所得的資金購(gòu)買(mǎi)，但是每箱價(jià)格為基準(zhǔn)價(jià)格的2 倍。 若到達(dá)終點(diǎn)時(shí)資源還有剩余可按每箱基準(zhǔn)價(jià)格的一半退回。目的是在滿(mǎn)足上述條件下回到終點(diǎn)盡可能多的保留資金。

題目中提到的地圖線(xiàn)路以及相關(guān)的各種信息提示，包括每天的天氣狀況、初始資金、資源的價(jià)格和質(zhì)量、在不同天氣不同行為條件下消耗的資源配比和挖礦的收益等信息， 皆出自2020 年全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽B 題關(guān)于“穿越沙漠”問(wèn)題的探討，讀者可根據(jù)所需自行查閱。

2 整體思路的構(gòu)想

經(jīng)分析認(rèn)為， 該問(wèn)題為最短路徑和最優(yōu)決策問(wèn)題。 從起點(diǎn)到終點(diǎn)有許多條路徑可供選擇，先用窮舉法確定有限個(gè)最優(yōu)路徑方案， 再用Dijkstra 算法求出任意兩個(gè)區(qū)域的最小距離，最后用定量分析購(gòu)買(mǎi)水和食物數(shù)量的最佳方案。 在行走過(guò)程中由于天氣變化、物資是否充足、挖礦天數(shù)和負(fù)重上限等因素均會(huì)影響最優(yōu)路徑的選擇。該問(wèn)題為了達(dá)到最終剩余資金最大化的目的，基于資源的最佳分配下的最優(yōu)路徑，結(jié)合Dijkstra 算法規(guī)劃下最優(yōu)路徑的假設(shè)， 對(duì)于此我們分開(kāi)討論。

3 模型的建立與求解

3.1 Dijkstra 算法規(guī)劃下最優(yōu)路徑的假設(shè)

由地圖提出基于最佳資源配置下的最優(yōu)路徑的假設(shè)：起點(diǎn)→村莊→礦山→村莊→終點(diǎn)。

3.2 針對(duì)最優(yōu)路徑假設(shè)的建模分析

不考慮天氣的情況下，在基于該路徑的算法并結(jié)合題中提供的地圖可得：

（1） 起點(diǎn)到村莊再到礦山也需要花費(fèi)8 天時(shí)間，其部分路線(xiàn)圖規(guī)劃方案如下：

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）從礦山到村莊的路徑可以通過(guò)上述村莊到礦山的路徑反向推出，從礦山到終點(diǎn)的路徑基于Dijkstra算法簡(jiǎn)化可以得出即：15（村莊）-9-21-27（終點(diǎn)）。

考慮天氣的情況下，從起點(diǎn)到村莊最少需要用6天時(shí)間，前6 天時(shí)間里有一天沙暴天氣，所以在原來(lái)的基礎(chǔ)上加上1 天；在此基礎(chǔ)上考慮到第7 天還是沙暴天氣，所以在原來(lái)7 天的基礎(chǔ)上加上1 天，也就是說(shuō)首先從起點(diǎn)到村莊總共需要消耗8 天時(shí)間，其中6天行走，2 天在原地停留。 從村莊到礦山需要花費(fèi)2天時(shí)間。 從礦山到終點(diǎn)需要花費(fèi)5 天時(shí)間。 由于到達(dá)礦山后再次進(jìn)行路線(xiàn)模擬假設(shè)。假設(shè)第一次到達(dá)村莊時(shí)挖礦7 天，休息1 天，隨后路經(jīng)村莊直接到達(dá)終點(diǎn)。基于該路徑的模型下，顯然挖礦的天數(shù)達(dá)到7 天時(shí)總體收益達(dá)到最大， 因此挖礦七天后選擇放棄繼續(xù)挖坑， 剩余資源正好可以滿(mǎn)足再次到達(dá)村莊的需求，在村莊再次購(gòu)買(mǎi)正好滿(mǎn)足到達(dá)終點(diǎn)的資源即可，這樣一來(lái)就使得到達(dá)終點(diǎn)時(shí)剩余資金最大化。

3.3 確定資源實(shí)時(shí)利用的最佳分配

前提假設(shè)：（1） 滿(mǎn)足上述路徑方案且保證到達(dá)終點(diǎn)的條件下，總共需要花費(fèi)24 天的時(shí)間，即第24 天正好到達(dá)終點(diǎn)；（2） 在起點(diǎn)購(gòu)買(mǎi)的食物和水必須能保證到達(dá)村莊所需要的基礎(chǔ)消耗，由于從起點(diǎn)到村莊最少需要用6 天時(shí)間， 前6 天時(shí)間里有一天沙暴天氣，所以在原來(lái)的基礎(chǔ)上加上1 天；在此基礎(chǔ)上考慮到第7 天還是沙暴天氣， 所以在原來(lái)7 天的基礎(chǔ)上加上1天，也就是說(shuō)首先從起點(diǎn)到村莊總共需要消耗8 天時(shí)間，其中6 天行走，2 天在原地停留；通過(guò)簡(jiǎn)單計(jì)算可以求出在這種既定的時(shí)間天數(shù)和天氣的條件下，總共需消耗水98 箱，食物98 箱，總負(fù)重為490 kg，總花費(fèi)1 470 元，剩余資金為8 530 元。

在此基礎(chǔ)上我們考慮到在村莊購(gòu)買(mǎi)水和食物是在起點(diǎn)購(gòu)買(mǎi)費(fèi)用的2 倍，且食物的基準(zhǔn)價(jià)格相對(duì)于水的基準(zhǔn)價(jià)格更貴，所以我們?cè)O(shè)置最初在起點(diǎn)購(gòu)買(mǎi)水和食物時(shí)，在滿(mǎn)足基礎(chǔ)消耗的前提下，將負(fù)重利用率達(dá)到最大，假設(shè)還可以購(gòu)買(mǎi)水：食物為1∶2，考慮到剩余150 kg 達(dá)到最大負(fù)重上限1 200 kg，所以可以再次買(mǎi)75 箱食物，同理通過(guò)簡(jiǎn)單計(jì)算可以求出還可以帶水80 箱， 食物235 箱， 總負(fù)重710 kg， 總花費(fèi)2 750元，剩余資金為5 640 元；假設(shè)上述方案為起點(diǎn)購(gòu)買(mǎi)水和食物的最佳方案，這樣的話(huà)總體在起點(diǎn)需要購(gòu)買(mǎi)水178 箱， 食物333 箱， 總負(fù)重1 200 kg， 總花費(fèi)4 220 元，剩余資金5 780 元。

到達(dá)村莊后需要對(duì)食物和水進(jìn)行再次購(gòu)買(mǎi)，此時(shí)考慮到下次再回到村莊補(bǔ)給所需的基礎(chǔ)消耗，且需滿(mǎn)足盡量避免沙暴天氣行走， 可以選擇第20 天停止挖礦，再次回到村莊進(jìn)行補(bǔ)給，這樣的話(huà)，不僅可以避免在往返村莊時(shí)遇到沙暴天氣，而且同時(shí)也能確定這段時(shí)間內(nèi)需要的挖礦時(shí)間為7 天，那么這條路徑下的時(shí)間和資源的分配也就可以通過(guò)簡(jiǎn)單的計(jì)算求出來(lái)，即整體這段時(shí)間內(nèi)行走4 天，原地停留2 天，挖礦7 天，總共用時(shí)12 天， 在這段時(shí)間的基礎(chǔ)消耗為： 水245箱，食物217 箱，總負(fù)重為1 169 kg，總花費(fèi)3 395 元，總收益7 000 元。

所以在第一次到達(dá)村莊時(shí)需要補(bǔ)充水和食物必須能夠滿(mǎn)足村莊—礦山—村莊這條的路徑的基礎(chǔ)消耗，在到達(dá)村莊時(shí)剩余的水0 箱，食物24 箱，總負(fù)重48 kg，剩余資金不變?yōu)?1 150 元，由此可知，我們?nèi)绻獫M(mǎn)足上述的基礎(chǔ)消耗，就必須保證需要再補(bǔ)充水36 箱，食物再補(bǔ)充16 箱，通過(guò)簡(jiǎn)單的計(jì)算可以知道這種現(xiàn)有的物資滿(mǎn)足村莊—礦山—村莊這條的路徑的基礎(chǔ)消耗。

3.4 建模結(jié)果分析與核算

由簡(jiǎn)化后的線(xiàn)路圖結(jié)合附件中已知的天氣情況、剩余天數(shù)、剩余資金、總負(fù)重量等因素可以推算出當(dāng)前條件下未來(lái)3 天的最優(yōu)線(xiàn)路安排為村莊—終點(diǎn)，通過(guò)算術(shù)簡(jiǎn)單計(jì)算可以求出在次路徑下的基礎(chǔ)消耗為：水36 箱，食物40 箱，總負(fù)重188 kg，剩余資金數(shù)不變?yōu)?0 470 元。

由上可知，第二次到達(dá)村莊后需要補(bǔ)給的水和食物只要能夠保證由村莊到終點(diǎn)線(xiàn)路的基礎(chǔ)消耗即可，這樣考慮的原因有以下兩條：（1） 達(dá)到終點(diǎn)時(shí)水和食物正好消耗盡， 不需要用留下的水和食物來(lái)推換資金，（2）不會(huì)超出負(fù)重上限，同時(shí)花費(fèi)保證最少。

所以在滿(mǎn)足上述全部要求的條件下算出來(lái)的最優(yōu)路徑為：起點(diǎn)—村莊—礦山—村莊—終點(diǎn)，由此路徑可以計(jì)算出0～24 天每一天的具體剩余資金， 剩余水量，剩余食物量； 且最后在滿(mǎn)足題目所有給出的條件下推算出來(lái)的盡可能保留的資金為10 470 元。

綜上所述：將關(guān)卡一整條路徑所剩的資金、到達(dá)終點(diǎn)花費(fèi)的時(shí)間、挖礦天數(shù)、是否超重進(jìn)行核算，可知在規(guī)定的時(shí)間內(nèi)且不超重的情況下該路徑剩的資金最多，假設(shè)成立。

4 結(jié)語(yǔ)

通過(guò)對(duì)穿越沙漠問(wèn)題的研究，讓學(xué)生們更加重視基本理論和基本方法的學(xué)習(xí)，以及運(yùn)用計(jì)算機(jī)建立數(shù)學(xué)模型解決實(shí)際問(wèn)題的能力。尤其是學(xué)生們?cè)诮?shù)學(xué)模型時(shí)一定要嚴(yán)守結(jié)果的正確性和邏輯的合理性，走完解決問(wèn)題的“最后一千米”。穿越沙漠本質(zhì)上是一個(gè)物資合理化配給徑和路最優(yōu)化的綜合性問(wèn)題，其本身的約束條件多，涉及到物流、通信、TSP 問(wèn)題、可以推廣運(yùn)用于軍事領(lǐng)域的物資運(yùn)輸，解決疫情等緊急情況下的物資調(diào)配，線(xiàn)路規(guī)劃等應(yīng)用領(lǐng)域。