基于線性規劃模型的沙漠穿越問題研究

曾俊博 孫基元 黎淳丞 黃宇杰 林慶彬

【摘? 要】本文主要針對以最優路徑穿越沙漠游戲的研究，利用優化算法，建立數學模型來分析最大效益，從而得到最大資金的最優路徑。首先將第一關所給地圖轉化為圖論中的無向圖，我們用離散數學中的圖論，建立一個最優路徑模型，通過考慮各類基本情況，然后在對最優路徑模型改進的基礎上加入考慮食物與水資源問題，是否進行補給，補給幾次，挖礦多久進行分析。其次對模型進行合理的理論計算及推導，然后借助于matlab矩陣運算，窮舉算法，對所提供的數據進行計算，最后我們需要在模型上進行修改，建立一個模型，最終得到結果。

【關鍵詞】最優路徑;圖論;matlab矩陣運算;窮舉算法

引言

該題是一個穿越游戲問題，初始情況下官方會給予一定的資金，可以用這筆資金進行購買路上所需要的水和食物。該游戲總共有六關，每次會給予一張地圖，玩家憑借地圖，從起點出發，穿越沙漠到達終點，在路上有村莊和礦山可以進行補給和賺取資金。游戲以天為基本、時間為單位，游戲開始時時間玩家在起點處，且當天時間為第0天，玩家須在截止日期或之前到達終點，到達終點后游戲結束。食物和水的最小計量單位為箱。由于存在負重上限，所以每天玩家所攜帶的水和質量不能超過這個上限，在穿越過程中，如果玩家的水和食物都消耗完了，則該玩家游戲失敗。每天的天氣為“晴朗”、“高溫”、“沙暴”三種狀況之一，沙漠中所有區域的天氣相同。玩家每天可選擇從地圖中的一個區域到達與之相鄰的另一個區域，也可以選擇在原地停留。

1.問題分析

在已知所有天氣情況下，給出最優策略，這屬于最優路徑問題，首先我們應考慮到物資及資金，然后再考慮到物資及資金還有挖礦的天數配置，從而考慮如何節省資金且的情況下到達礦山，再從礦山回到起點。在于使到達終點時的資金最大化，難點在于在起點所攜帶食物與水的計算和在礦山中所待天數的多少以及前往村莊的補給。我們對所給數據進行圖論分析，利用窮舉算法算出各類前往村莊和礦山的路徑如何消耗最少，在礦山進行挖礦幾次后再進行分析，比較哪次所積攢資金最多，最后得到結果。

2.模型建立與求解

在已知天氣的情況下進行求解玩家的最佳策略，可得之天氣每天的情況與第一關第二關的地圖，利用圖論將其地圖轉化為無向圖。

要求一般情況下玩家的最優策略，在所給數據中水的資源數量為每箱5千克，食物為每箱2千克，但是不同的天氣下食物和水的消耗量不同，在晴天時，水消耗5千克，食物消耗7千克，在高溫天氣情況下，水消耗為8千克，食物為6千克，在沙暴天氣下，食物和水的消耗都為10千克。由于在沙暴天氣下不可以行走，所以我們選擇在沙暴天氣下停留。我們希望建立一個可以包含路程所需天數，水資源的購買消耗情況，食物的購買消耗情況的數學模型。從起點直接前往終點路上的最優路徑為，經過計算，前往該終點所用時間t為3天，且已知三天內的天氣狀況為高溫，高溫，晴朗，經過計算，這三天所消耗的資金損耗求得S=295剩余資金為求得剩余資金W為9705，在礦山中挖礦所獲得的收益為1000元，前往村莊最短時間8天，在礦山挖礦的時間為7天，在礦山停留1天度過沙暴，已知這8天中4天為高溫，1天晴朗，3天沙暴。挖礦時的收益以及虧損比較挖礦一天的收益與最大挖礦遭遇的沙暴天氣最大消耗進行比較假設在沙暴天氣，為了使剩余的資金最大化，我們需要在礦山中停留挖礦的時間盡可能長，從而補充之前所虧損的，由此建立一個數學模型來探討最優路徑以及挖礦的時間。由于玩家所攜帶的負重上限為1200千克，而水的質量為每箱3千克，食物的質量為每箱2千克。在模型中，我們應該考慮是否在起點處購買所攜帶的水和物資是否支撐到礦山以及在礦山中挖礦時所消耗的食物與水。經過計算獲得，在起點處應攜帶540千克的水和660千克的食物由于攜帶物資的上限，加上又要在礦山中進行挖礦所需要的食物以及水在規定30天內到達終點，所以還有此約束條件。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?由于考慮在起點處與村莊處所購買的食物和水不可以在途中消耗完，不然視為游戲失敗，故還需要一個約束條件。

其中xi是x的列向量，yi是y的列向量。單純形法是單純形法是求解線性規劃問題最常用、最有效的算法之一。第二關附件中已知30天的所有情況，在負重上限為1200千克的情況下，購買能夠盡可能挖礦的資源。然后去求解最優策略，第二關所使用的模型與第一關相同，由模型一可得所以第二關的最優路徑是：