張步昇 田帥軍 張艷霞
(1.山西農(nóng)業(yè)大學(xué)農(nóng)業(yè)工程學(xué)院,山西 晉中 030800;2.山西農(nóng)業(yè)大學(xué)動(dòng)物醫(yī)學(xué)學(xué)院,山西 晉中 030800)
一名玩家在已知每天天氣狀況的條件下, 給出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ù)所需自行查閱。
經(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)討論。
由地圖提出基于最佳資源配置下的最優(yōu)路徑的假設(shè):起點(diǎn)→村莊→礦山→村莊→終點(diǎn)。
不考慮天氣的情況下,在基于該路徑的算法并結(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í)剩余資金最大化。
前提假設(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ǔ)消耗。
由簡(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è)成立。
通過(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)域。