基于單目標(biāo)線性規(guī)劃的穿越沙漠策略研究

楊誠靖 沈煒宏 郭小敏

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

關(guān)鍵詞：單目標(biāo)線性規(guī)劃；弗洛伊德算法；最優(yōu)策略

中圖分類號：TP391? ? 文獻(xiàn)標(biāo)識碼：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萬平方千米，沙漠邊緣地帶以及沙漠中的山丘地區(qū)對人類、野生動物以及水循環(huán)具有重要意義。在廣袤的沙漠中蘊(yùn)藏了豐富的礦產(chǎn)資源、礦物質(zhì)、石油，對資源進(jìn)行開發(fā)可以緩解我國資源緊張的問題。穿越沙漠游戲中，在已知天氣情況下要求玩家憑借一張地圖，利用初始資金購買一定數(shù)量的水和食物，從起點(diǎn)出發(fā)，在沙漠中行走，玩家可在礦山、村莊補(bǔ)充資金或資源，目標(biāo)是在規(guī)定時間內(nèi)到達(dá)終點(diǎn)，并保留盡可能多的資金。

1? 問題分析

穿越沙漠以在規(guī)定時間內(nèi)到達(dá)終點(diǎn)，并保留盡可能多的資金為目標(biāo)，制定玩家的最優(yōu)策略，屬于圖論和優(yōu)化問題[1]。在只有一名玩家的情況下，由于影響因素不同，所以為了統(tǒng)一衡量，將不同情況下的消耗轉(zhuǎn)化為資金消耗。介于題目中所給的地圖比較復(fù)雜，為優(yōu)化地圖，將地圖中的區(qū)域轉(zhuǎn)化為賦權(quán)圖。將第一關(guān)的地圖轉(zhuǎn)化為帶權(quán)鄰接矩陣，用弗洛伊德算法對上面的帶權(quán)鄰接矩陣進(jìn)行處理，得出各個節(jié)點(diǎn)之間的最短距離和路程，進(jìn)而求得剩余資金。

2? 模型建立與求解

2.1? 模型建立前的準(zhǔn)備

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

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

將相關(guān)信息轉(zhuǎn)化為矩陣信息，為模型建立提供條件。

2.1.1? 鄰接矩陣

假設(shè)從起點(diǎn)穿過沙漠到終點(diǎn)共經(jīng)過n個區(qū)域，則鄰接矩陣為：

A=（aij）n×n

2.1.2? 基礎(chǔ)單位消耗量矩陣

設(shè)不同天氣下兩種物品的基礎(chǔ)單位消耗量矩陣為：

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

2.1.3? 天氣情況矩陣

假設(shè)從起點(diǎn)到終點(diǎn)需要m天，則天氣狀況矩陣為：

其中，

2.1.4? 消耗系數(shù)矩陣

假設(shè)從起點(diǎn)到終點(diǎn)需要m天，則消耗系數(shù)矩陣為：

2.1.5? 消耗箱數(shù)矩陣

假設(shè)從起點(diǎn)到終點(diǎn)需要m天，則兩種物品的消耗箱數(shù)矩陣為：

H=CWξ=（hij）2×m

2.1.6? 購買系數(shù)矩陣

假設(shè)從起點(diǎn)到終點(diǎn)需要m天，則購買系數(shù)矩陣為：

2.1.7? 購買物品數(shù)量矩陣

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

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

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

2.2? 模型建立

問題假設(shè)只有一名玩家，事先已知整個游戲階段內(nèi)的每天的天氣狀況。以到達(dá)終點(diǎn)時剩余資金盡可能多為目標(biāo)，建立單目標(biāo)線性規(guī)劃模型，給出一般情況下玩家的最優(yōu)策略。

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

考慮決策變量、目標(biāo)函數(shù)、約束條件，建立資金優(yōu)化模型。

2.2.1? 決策變量

要確定玩家的游戲策略，也就是確定玩家從起點(diǎn)經(jīng)過哪些區(qū)域到達(dá)終點(diǎn)，設(shè)決策變量為：

2.2.2? 目標(biāo)函數(shù)

以游戲結(jié)束保留盡可能多的資金煒目標(biāo)，將剩余資金作為目標(biāo)函數(shù)。用總收益減去總成本就可以得到到達(dá)終點(diǎn)時的總剩余資金：

M=S+R-P出發(fā)點(diǎn)-P山莊

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

2.2.3? 約束條件

玩家須在規(guī)定的時間內(nèi)到達(dá)終點(diǎn)，即從起點(diǎn)到終點(diǎn)，總的天數(shù)須小于等于30：

；

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

到達(dá)終點(diǎn)前，由于玩家必須存活，所以水和食物均不能耗盡，則

其中b1 j表示當(dāng)天背包中所剩水的箱數(shù)，b2 j表示當(dāng)天背包中所剩食物的箱數(shù)。h1 j表示當(dāng)天消耗水的箱數(shù)，h2 j表示當(dāng)天消耗食物的箱數(shù)。

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

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

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

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

由圖2得到最優(yōu)方案：起點(diǎn) 村莊 礦山 村莊 終點(diǎn)，路徑圖如圖2所示。

2.4? 方案求解

由于天氣、路線已知，所以游戲過程中所消耗的資源也是已知的。且由于目標(biāo)是在規(guī)定時間內(nèi)到達(dá)終點(diǎn)，并保留盡可能多的資金，所以到達(dá)終點(diǎn)時，水和糧食應(yīng)該剛好或者趨于耗盡。

將第一關(guān)的地圖轉(zhuǎn)化為帶權(quán)鄰接矩陣，得到：

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

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

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

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

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

其中mw表示水的質(zhì)量，mf表示食物的質(zhì)量。計算可得在起點(diǎn)處的花費(fèi)p=4 325元。

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

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

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

R=t礦洞×ω基礎(chǔ)

因而挖礦收益R=7 000元。由于到達(dá)村莊再次進(jìn)行補(bǔ)給，此時補(bǔ)充38 kg食物、108 kg水。此時的村莊花費(fèi)P村莊為：

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

M=S+R-P出發(fā)點(diǎn)-P山莊

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

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

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

首先以游戲結(jié)束剩余資金為目標(biāo)函數(shù)，以玩家是否經(jīng)過區(qū)域為決策變量，以每天玩家的水和食品質(zhì)量之和不能超過負(fù)重上限，游戲過程中水和食物不能耗盡為約束條件，建立了單目標(biāo)線性規(guī)劃模型，給出了一般情況下玩家的最優(yōu)策略。

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

3? 結(jié)? 論

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

參考文獻(xiàn)：

[1] 石兆.物流配送選址—運(yùn)輸路徑優(yōu)化問題研究 [D].長沙：中南大學(xué)，2014.

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

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

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

[5] 林浩楠.基于多目標(biāo)遺傳算法和深度學(xué)習(xí)的投資分配模型研究與應(yīng)用 [D].廣州：華南理工大學(xué)，2017.

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

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

收稿日期：2022-08-19