田欣宇

河北工程大學 河北邯鄲 056002

1 問題分析

一名玩家知道游戲時間段內(nèi)30天內(nèi)的全部天氣情況[1]，則可以根據(jù)高溫、晴朗和沙暴天氣不同的基礎(chǔ)消耗量來決定初始攜帶的最大資源數(shù)量。由于在村莊的資源價格高于較高，因此為保證成功完成穿越沙漠則是否在此購買資源需要結(jié)合路線進行具體分析。根據(jù)基準價格、基礎(chǔ)消耗量的條件，列出相對應(yīng)的關(guān)系式，并結(jié)合負重上限、初始資金得出約束條件，得到線性規(guī)劃的模型。首先對地圖應(yīng)用圖論模型和迪杰斯特拉算法[2]，求解出不同方案下的最短路徑。再結(jié)合天氣情況對具體的路線的資源消耗以及收益進行計算，進而確定初始購買資源數(shù)量和最終到達終點時的資金。最后用靈敏度分析對第一關(guān)和第二關(guān)的具體問題進行檢驗，驗證問題的答案是否具有合理性。

2 模型的建立與求解

假設(shè)在晴朗天氣和高溫天氣時玩家不原地停留，向相鄰區(qū)域前進。目標是在規(guī)定時間內(nèi)到達終點，并保留盡可能多的資金。需要考慮1。初始的水和食物的購買量2。再不超過負重的基礎(chǔ)上水和食物的占比3。所消耗的天數(shù)其中包括了受沙暴天氣影響的天數(shù)[5]和受不同地區(qū)[6]所消耗的天數(shù)。所以列出未知數(shù)函數(shù)方程，使最終收益最大來求解方程。針對最短天數(shù)到達終點或最短天數(shù)到達礦場兩種情況，采用最短路徑方案，并基于最短路徑下的最大收益模型,得到最大收益要使購買消耗品的資金盡可能少。設(shè)在出發(fā)地購買水質(zhì)量為箱，購買食物重量為箱，花費為，則：

并考慮到食物的價值大于水的價值且水的質(zhì)量大于食物的質(zhì)量采用0-1背包模型，在基于最短路徑下到達村莊補充食物和水至少需要98箱水和98箱食物即補充約束條件為：

狀態(tài)加選擇，定義為裝載重量為W的背包和N個物品，每個物品有重量和價值兩個屬性，其中第i個物品的重量為wt[i],價值為val[i]。代入W=1200，N=2，價值分別為5和10，重量分別為3和2。設(shè)在村莊購買的水質(zhì)量為箱，購買食物重量為箱，花費為，則：

設(shè)玩家到達終點之后的總資金為Y，則：

要盡可能使得Y最大，基礎(chǔ)收益最大，基礎(chǔ)消耗最小，同時使得得到終點的水和食物盡可能小。即：

得到線性規(guī)劃模型如下：

3 結(jié)語

由以上敘述可知此玩家在第一關(guān)最佳優(yōu)化策略分為不經(jīng)過礦山和經(jīng)過礦山兩種決策方案，此兩種決策方案分別對應(yīng)一種最短路徑。對第一關(guān)情況進行圖論分析[3]，通過應(yīng)用迪杰斯特拉算法，得到如圖1所示不經(jīng)過礦山的最短路徑情況圖，不經(jīng)過礦山的最短路線為1→25→26→27，此路線僅需考慮天氣因素和食物與水的消耗，不許考慮其他因素。

則可得以下結(jié)論：針對本路線假設(shè)玩家購買的水和食物剛好到達終點，即剩余資源為零。所以=50+80×2+140+120×2=590在第四天到終點，且剩余資金為9410元。對第一關(guān)情況進行圖論分析，通過應(yīng)用迪杰斯特拉算法,分析可得經(jīng)過礦場的最短路線為1→25→24→23→21→9→10→11→12→11→10→9→21→27。為獲得途中的補充資源，采取經(jīng)過村莊的路線，即1→25→24→23→21→9→15→13→12→13→15→9→21→27。計算得到初始購買98箱水和453箱食物即=453，結(jié)合天數(shù)到達村莊為第八天經(jīng)歷了兩天沙暴，三天晴朗，三天高溫到達村莊剛好水耗盡繼而購買163箱水不購買食物，沿著區(qū)域14，進入礦區(qū)12，進行挖礦到十四天然后返回村莊進行購買223箱水，再次趕回礦區(qū)進行挖礦在26號出發(fā)到村莊購買11箱食物，然后出發(fā)至終點實現(xiàn)零剩余。最終資金剩余9900。