基于單目標線性規劃的穿越沙漠策略研究

楊誠靖 沈煒宏 郭小敏

摘? 要：單目標線性規劃模型是在一組線性條件約束下，尋求某一單一目標的最優值，適用于極值問題的求解。弗洛伊德算法是一種通過動態規劃的思想尋找給定的加權圖中多源點間最短路徑的算法。文章建立了基于背包問題的單目標線性規劃模型，給出了在只有一名玩家，且事先已知游戲階段天氣狀況下玩家的最優策略。通過弗洛伊德算法求解出了相應節點間的最短路徑，得到了玩家的最終剩余資金。

關鍵詞：單目標線性規劃；弗洛伊德算法；最優策略

中圖分類號：TP391? ? 文獻標識碼：A? 文章編號：2096-4706（2023）01-0127-05

Research on Desert Crossing Strategy Based on Single Objective Linear Programming

YANG Chengjing， SHEN Weihong， GUO Xiaomin

（Yancheng Institute of Technology， Yancheng? 224051， China）

Abstract： The single objective linear programming model seeks the optimal value of a single objective under a set of linear condition constraints and is suitable for solving extreme value problems. Freudian algorithm is an algorithm to find the shortest path among multiple source nodes in a given weighted graph based on dynamic programming idea. In this paper， a single objective linear programming model based on the knapsack problem is established， and the optimal strategy is given under the condition of only one player and the weather in the game stage is known in advance. The shortest path among corresponding nodes is solved by Freudian algorithm， and the final remaining funds of players are obtained.

Keywords： single objective linear programming; Floyd algorithm; optimal strategy

0? 引? 言

地球上沙漠的總面積近3 370萬平方千米，沙漠邊緣地帶以及沙漠中的山丘地區對人類、野生動物以及水循環具有重要意義。在廣袤的沙漠中蘊藏了豐富的礦產資源、礦物質、石油，對資源進行開發可以緩解我國資源緊張的問題。穿越沙漠游戲中，在已知天氣情況下要求玩家憑借一張地圖，利用初始資金購買一定數量的水和食物，從起點出發，在沙漠中行走，玩家可在礦山、村莊補充資金或資源，目標是在規定時間內到達終點，并保留盡可能多的資金。

1? 問題分析

穿越沙漠以在規定時間內到達終點，并保留盡可能多的資金為目標，制定玩家的最優策略，屬于圖論和優化問題[1]。在只有一名玩家的情況下，由于影響因素不同，所以為了統一衡量，將不同情況下的消耗轉化為資金消耗。介于題目中所給的地圖比較復雜，為優化地圖，將地圖中的區域轉化為賦權圖。將第一關的地圖轉化為帶權鄰接矩陣，用弗洛伊德算法對上面的帶權鄰接矩陣進行處理，得出各個節點之間的最短距離和路程，進而求得剩余資金。

2? 模型建立與求解

2.1? 模型建立前的準備

針對現有的情況：在整個時間段內每天天氣情況事先全部已知。在只有一名玩家的情況下，由于在游戲過程中所需要的水和食物在特定天氣下消耗不同，在行走過程和在村莊、礦山的消耗也不同，所以為了統一衡量，將不同情況下的消耗轉化為資金消耗。

由于問題中所給的地圖比較復雜，為優化地圖，將地圖中的一個個區域轉化為一個一個的點，即運用圖論的思想將地圖轉化為圖，就可以使地圖得到簡化，進而轉化為點到點的問題。將第一關的地圖轉化為帶權鄰接矩陣，用弗洛伊德算法對上面的帶權鄰接矩陣進行處理，得出各個節點之間的最短距離和路程。接著計算出直接向終點出發、先去礦山采礦，再去村莊購物，再向終點出發等多種方案的最終剩余資金。最后對不同方案的剩余資金進行比較，選擇剩余資金最多的方案，存入表中。

將相關信息轉化為矩陣信息，為模型建立提供條件。

2.1.1? 鄰接矩陣

假設從起點穿過沙漠到終點共經過n個區域，則鄰接矩陣為：

A=（aij）n×n

2.1.2? 基礎單位消耗量矩陣

設不同天氣下兩種物品的基礎單位消耗量矩陣為：

其中cij表示第i種食物在第j種天氣狀況下的基礎消耗量。i=1，2分別表示水和食物，j=1，2，3分別表示晴朗、高溫和沙暴。

2.1.3? 天氣情況矩陣

假設從起點到終點需要m天，則天氣狀況矩陣為：

其中，

2.1.4? 消耗系數矩陣

假設從起點到終點需要m天，則消耗系數矩陣為：

2.1.5? 消耗箱數矩陣

假設從起點到終點需要m天，則兩種物品的消耗箱數矩陣為：

H=CWξ=（hij）2×m

2.1.6? 購買系數矩陣

假設從起點到終點需要m天，則購買系數矩陣為：

2.1.7? 購買物品數量矩陣

假設在第l區域分別購買水b1l箱和食物b2l箱，則記購買物品數量矩陣為：

2.1.8? 購買物品消耗資金矩陣

水和食物的基礎單價分別為5元/箱和10元/箱，記 ，則購買兩種物品的消耗資金矩陣為：

2.2? 模型建立

問題假設只有一名玩家，事先已知整個游戲階段內的每天的天氣狀況。以到達終點時剩余資金盡可能多為目標，建立單目標線性規劃模型，給出一般情況下玩家的最優策略。

為統一衡量，將玩家在不同情況下的資源消耗轉化為資金消耗。針對問題現有的情況：在整個時間段內每天天氣情況事先全部已知。在只有一名玩家的情況下，由于在游戲過程中所需要的水和食物在特定天氣下消耗不同，在行走過程和在村莊、礦山的消耗也不同，在起點和村莊購買物資的價格不同，在特定天氣下挖礦收入不同，將不同情況下的消耗轉化為資金消耗，如表1所示。

考慮決策變量、目標函數、約束條件，建立資金優化模型。

2.2.1? 決策變量

要確定玩家的游戲策略，也就是確定玩家從起點經過哪些區域到達終點，設決策變量為：

2.2.2? 目標函數

以游戲結束保留盡可能多的資金煒目標，將剩余資金作為目標函數。用總收益減去總成本就可以得到到達終點時的總剩余資金：

M=S+R-P出發點-P山莊

其中M表示所剩資金，S表示10 000元初始資金，R表示挖礦所獲得的收益，P出發點表示出發點購買物資所消耗的資金，P山莊表示在村莊購買物資所消耗的資金。

2.2.3? 約束條件

玩家須在規定的時間內到達終點，即從起點到終點，總的天數須小于等于30：

；

背包具有固定容量，因此玩家擁有的水和食物的質量之和不超過背包容量上限[2]：

到達終點前，由于玩家必須存活，所以水和食物均不能耗盡，則

其中b1 j表示當天背包中所剩水的箱數，b2 j表示當天背包中所剩食物的箱數。h1 j表示當天消耗水的箱數，h2 j表示當天消耗食物的箱數。

綜合決策變量、目標函數和約束條件，得出在只有一名玩家，且事先已知游戲階段每天的天氣狀況時，玩家的最優策略模型為：

2.3? 弗洛伊德算法求最短路徑

弗洛伊德算法是一個經典的動態規劃算法。用通俗的語言來描述的話，首先目標是尋找從點i到點j的最短路徑。從動態規劃的角度看問題，需要為這個目標重新做一個詮釋：從任意節點i到任意節點j的最短路徑不外乎2種可能，一種是直接從i到j，另一種是從i經過若干個節點k到j。所以，假設Dis（i， j）為節點u到節點v的最短路徑的距離，對于每一個節點k，檢查Dis（i，k）+Dis（k， j）＜Dis（i， j）是否成立，如果成立，證明從i到k再到j的路徑比i直接到j的路徑短，便設置Dis（i， j）=Dis（i，k）+Dis（k， j），這樣一來，當遍歷完所有節點k，Dis（i， j）中記錄的便是i到j的最短路徑的距離。

由于題目中所給的地圖比較復雜，為優化地圖，將題中所給地圖轉化為帶權鄰接矩陣[3]。用弗洛伊德算法對上面的帶權鄰接矩陣進行處理，得出了各個節點之間的最短距離和對應路程，對所得的結果進行優化，將其轉換為賦權圖進行處理，如圖1所示。至此路線問題得到徹底解決，題中路線問題也轉化成對節點的方案選擇問題。

由圖2得到最優方案：起點 村莊 礦山 村莊 終點，路徑圖如圖2所示。

2.4? 方案求解

由于天氣、路線已知，所以游戲過程中所消耗的資源也是已知的。且由于目標是在規定時間內到達終點，并保留盡可能多的資金，所以到達終點時，水和糧食應該剛好或者趨于耗盡。

將第一關的地圖轉化為帶權鄰接矩陣，得到：

到達終點后所剩的資金模型為：M=S+R-P出發點-P山莊，其中M表示所剩資金，S表示10 000元初始資金，R表示挖礦所獲得的收益，P出發點表示出發點購買物資所消耗的資金，P山莊表示在村莊購買物資所消耗的資金。

對于R，由于挖礦的收益足夠大，所以挖礦的時間也是越長越好。對于P、Q，因為村莊內物資價格較高，所以在起點充分準備物資可以節約資金。

根據弗洛伊德算法求解的從起點到村莊的最短路徑，將所有的消耗、收入、支出轉化為資金消耗。根據上述方案，簡化并得到了新的賦權圖[4]。

首先，從起點到村莊，路徑為：1→25→24→23→22→9→15。天氣狀況及支出狀況如表2所示。

考慮到題目中負重上限為1 200 kg，初始資金為10 000元，食物價格比水貴的因素影響。所以在起點出發時，盡可能多的攜帶食物與水。待到第一次到達村莊時，僅補充水。經計算，在起點處攜帶540 kg水、660 kg食物，此時的起點花費為：

其中mw表示水的質量，mf表示食物的質量。計算可得在起點處的花費p=4 325元。

因為第4天與第7天存在沙塵暴天氣，所以為節省資源，玩家選擇在原地停留。根據路徑：1→25→24→23→22→9→15可知八天后到達村莊時剩余464 kg食物，246 kg水。此時需要在村莊補充489 kg水，以維持足夠長的挖礦時間。此時的村莊花費為：

代入數據，計算可得Q=1 630元。按照路線15→14→12從村莊到達礦場。由于第9日、第10日的天氣情況皆為高溫，此時每日行走消耗為200元。由于題目中規定到達礦山當天不能挖礦、沙暴日也可挖礦，因此將其作為約束條件，經過兩天到達礦場時需駐留一天。下面給出11日到20日的天氣情況及支出情況，如表3所示。

其中，11日駐留一日，因此11日看作沙暴日的基礎消耗。考慮到資源約束，所以在礦洞挖礦時間t礦洞為7天，即于19日前往村莊補充物資，路途花費兩天。此時共消耗422 kg食物與735 kg水。剩余42 kg食物、0 kg水。因而挖礦收益R為：

R=t礦洞×ω基礎

因而挖礦收益R=7 000元。由于到達村莊再次進行補給，此時補充38 kg食物、108 kg水。此時的村莊花費P村莊為：

帶入數據，計算可得此時的花費P村莊為740元。此時，在村莊所補充的物資剛好能夠支持游戲參與者回到終點，此時食物和水全部消耗完畢，無須退回。此刻挖礦總計7天，收入總計7 000元，支出6 510元。代入所剩資金模型[5]：

M=S+R-P出發點-P山莊

可得到資金剩余M方案一=10 490元，其資金剩余和資源剩余變化趨勢[6]如圖3、圖4所示。

利用弗洛伊德算法對該單目標線性規劃模型進行求解，得出游戲結束時的最優資金剩余量，并通過資源剩余變化圖看出再游戲結束時，資源剩余量剛好為0，資源利用最優。至此便得出了在時間、資金、背包容量等約束條件下的最優剩余資金。

本文建立了基于背包問題的單目標線性規劃模型，給出了在只有一名玩家，且事先已知游戲階段每天天氣狀況下，玩家的最優策略。

首先以游戲結束剩余資金為目標函數，以玩家是否經過區域為決策變量，以每天玩家的水和食品質量之和不能超過負重上限，游戲過程中水和食物不能耗盡為約束條件，建立了單目標線性規劃模型，給出了一般情況下玩家的最優策略。

然后，利用弗洛伊德算法求解出了相應節點間的最短路徑，得到了第一關玩家的最優策略為：1→25→24→23→22→9→15→14→12→14→15→9→21→27。此時，最終剩余資金為10 490元。

3? 結? 論

本文利用基于弗洛伊德算法的單目標線性規劃模型與圖論提供最優策略，使得所求剩余資金較為準確，具有說服力。該模型可以應用于最短路徑求解、旅行商問題的動態規劃、挖礦、淘金類游戲決策中，對解決此類問題有較好的效果。

參考文獻：

[1] 石兆.物流配送選址—運輸路徑優化問題研究 [D].長沙：中南大學，2014.

[2] 李炯城，鮑江宏.基于圖論求解多選擇背包問題 [J].計算機工程與設計，2009，30（13）：3144-3147.

[3] 賀軍忠.最短路徑問題Floyd算法的改進 [J].蘭州文理學院學報：自然科學版，2019，33（5）：27-30.

[4] 盧立果，劉立越，魯鐵定，等.一種改進的Floyd算法 [J].東華理工大學學報：自然科學版，2019，42（1）：78-81.

[5] 林浩楠.基于多目標遺傳算法和深度學習的投資分配模型研究與應用 [D].廣州：華南理工大學，2017.

[6] 高蘭芳.基于線性規劃的工程投資分配模型及優化 [J].四川輕化工大學學報：自然科學版，2020，33（1）：74-81.

作者簡介：楊誠靖（2001.12—），男，漢族，江蘇揚州人，本科在讀，研究方向：管理科學與工程；沈煒宏（2001.03—），男，漢族，江蘇常州人，本科在讀，研究方向：管理科學與工程；郭小敏（2001.07—），女，漢族，安徽阜陽人，本科在讀，研究方向：金融工程。

收稿日期：2022-08-19