基于線性規(guī)劃模型的沙漠穿越問(wèn)題研究

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

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

【關(guān)鍵詞】最優(yōu)路徑;圖論;matlab矩陣運(yùn)算;窮舉算法

引言

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

1.問(wèn)題分析

在已知所有天氣情況下，給出最優(yōu)策略，這屬于最優(yōu)路徑問(wèn)題，首先我們應(yīng)考慮到物資及資金，然后再考慮到物資及資金還有挖礦的天數(shù)配置，從而考慮如何節(jié)省資金且的情況下到達(dá)礦山，再?gòu)牡V山回到起點(diǎn)。在于使到達(dá)終點(diǎn)時(shí)的資金最大化，難點(diǎn)在于在起點(diǎn)所攜帶食物與水的計(jì)算和在礦山中所待天數(shù)的多少以及前往村莊的補(bǔ)給。我們對(duì)所給數(shù)據(jù)進(jìn)行圖論分析，利用窮舉算法算出各類(lèi)前往村莊和礦山的路徑如何消耗最少，在礦山進(jìn)行挖礦幾次后再進(jìn)行分析，比較哪次所積攢資金最多，最后得到結(jié)果。

2.模型建立與求解

在已知天氣的情況下進(jìn)行求解玩家的最佳策略，可得之天氣每天的情況與第一關(guān)第二關(guān)的地圖，利用圖論將其地圖轉(zhuǎn)化為無(wú)向圖。

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

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