2020年數(shù)學(xué)建模大賽穿越沙漠B

2020年數(shù)學(xué)建模大賽穿越沙漠BCUMCM2020模型概述CUMCM2020模型概述整體模型指導(dǎo)思想：不采用遍歷搜索方法，而突出決策行為將指導(dǎo)策略和定量模型兩者結(jié)合，做出決策對一般情況進(jìn)行分析，同時(shí)對具體問題深入研究問題一：在確定信息下最優(yōu)決策最優(yōu)策略性質(zhì)和無向圖簡化貪心策略動(dòng)態(tài)規(guī)劃指導(dǎo)策略CUMCM2020穿越沙漠B模型概述問題二：在不確定天氣下最優(yōu)決策基于天氣概率模型決策簡化模型（路線規(guī)劃一致性）與無向圖簡化直接前往終點(diǎn)模式：基于概率的直達(dá)終點(diǎn)最短花費(fèi)決策模型挖礦賺錢模式：基于逃離閾值的挖礦停止策略問題三：基于完全信息的博弈基于Nash均衡模型最大最小策略多人挖礦博弈策略CUMCM2020穿越沙漠B具體分析CUMCM2020具體分析CUMCM2020穿越沙漠B問題一：在確定天氣下最優(yōu)決策最優(yōu)策略：游戲成功且結(jié)束時(shí)持有資金最多玩家資源在游戲結(jié)束時(shí)無剩余關(guān)鍵點(diǎn)之間的最短路徑為最優(yōu)策略的組成部分地圖化簡：僅包含起點(diǎn)、終點(diǎn)、村莊和礦山這四類關(guān)鍵點(diǎn)刪除非最短路徑的邊——多余邊化簡示意圖CUMCM2020穿越沙漠B礦山村莊起點(diǎn)終點(diǎn)6233化簡示意圖CUMCM2020穿越沙漠B礦山30村莊39起點(diǎn)終點(diǎn)1937礦山55村莊6291222具體分析問題一：在確定天氣下最優(yōu)決策通用策略：貪心晴朗天氣不停留最多挖礦原則：無論天氣如何，在資源足夠的情況下一定挖礦最多補(bǔ)貨原則：最大化利用背包限重指導(dǎo)策略：動(dòng)態(tài)規(guī)劃由第ts天到第te天經(jīng)過d次轉(zhuǎn)移的最小花費(fèi)C[ts,te,d]=min{C[ts,te-1,d-1]+2*cost(weather),C[ts,te-1,d-1]+cost(weather)}初始化：C[ts,ts,0]=0,C[ts,ts+1,1]=2*cost(weather)圖為C在ts=0的投影，為盡快到達(dá)目的地，非沙暴天氣絕不停留CUMCM2020穿越沙漠B動(dòng)態(tài)規(guī)劃結(jié)果具體分析第一關(guān)策略：不考慮去礦山，直接前往終點(diǎn)，耗費(fèi)590元資源前往礦山：挖礦（資源充足時(shí)）>移動(dòng)>停留兩輪挖礦：起點(diǎn)→礦山→村莊→礦山→終點(diǎn)，剩余9800元一輪挖礦：起點(diǎn)→礦山→終點(diǎn)，最終10430元第二關(guān)策略：不去礦山：起點(diǎn)→村莊62→終點(diǎn)，耗費(fèi)2610元前往礦山：挖礦（資源充足時(shí)）>移動(dòng)>停留起點(diǎn)→礦山55（去村莊62補(bǔ)給）→終點(diǎn)，最終11115元起點(diǎn)→礦山30→村莊39→礦山55→終點(diǎn)，最終12355元起點(diǎn)→村莊62→礦山55→村莊62→礦山55→終點(diǎn)，最終12470元CUMCM2020穿越沙漠B具體分析

CUMCM2020穿越沙漠B具體分析

CUMCM2020穿越沙漠B具體分析第三關(guān)：地圖中沒有村莊，因此所有的資源都必須在起點(diǎn)處購買，故可以直接按1x基準(zhǔn)價(jià)格估計(jì)消耗資源對應(yīng)的價(jià)值。玩家在途中不會(huì)遇到沙暴天氣。本關(guān)的礦山挖礦收益(200元)

相對較少。CUMCM2020穿越沙漠B關(guān)鍵點(diǎn)訪問規(guī)劃說明方案1起點(diǎn)—終點(diǎn)(直接前往終點(diǎn)模式)至少須安排3天行走。方案2起點(diǎn)—礦山—終點(diǎn)(挖礦賺錢模式)行程開頭和結(jié)尾須至少分別安排3天和2天的行走，（在滿足資源約束的條件下）余下最多5天可安排為挖礦。行動(dòng)收益期望行走-190/天停留-135/天挖礦-85/天僅晴朗天挖礦-50/天已知不會(huì)出現(xiàn)沙暴天氣，假設(shè)晴天和高溫的出現(xiàn)頻率為1:1，每天采取行走和挖礦行動(dòng)的收益期望如下表。晴天和高溫1:1下每天行動(dòng)收益期望表在礦山挖礦的收益期望為負(fù)值。這意味著挖礦的收入都無法填補(bǔ)挖礦行為自身的資源消耗期望支出；更何況前往礦山還需要付出更多行走的天數(shù)和支出。使用該收益期望來預(yù)估兩種方案，從而選擇直接前往終點(diǎn)模式。具體分析CUMCM2020穿越沙漠B12345678910晴朗高溫晴朗晴朗晴朗晴朗高溫高溫高溫高溫晴朗1123455555高溫0111112345沙暴-1-1-1-1-1-1-1-1-1-1晴朗0.6666670.50.60.6666670.7142860.750.6666670.60.5454550.5高溫0.3333330.50.40.3333330.2857140.250.3333330.40.4545450.5沙暴000000000決策前進(jìn)停留前進(jìn)前進(jìn)前進(jìn)前進(jìn)停留停留停留停留金錢消耗ci55cj135ck150具體分析第四關(guān)：資源參數(shù)和第三關(guān)一致，但礦山挖礦收益為1000元/天；且截止日期為第30天，時(shí)間相對充裕。地圖且有村莊且位于礦山附近，可以中途購買資源補(bǔ)給。CUMCM2020穿越沙漠B關(guān)鍵點(diǎn)訪問規(guī)劃說明方案1起點(diǎn)—終點(diǎn)(直接前往終點(diǎn)模式)至少須安排5+3天行走。方案2起點(diǎn)—(礦山?村莊)—終點(diǎn)(挖礦賺錢模式)行程開頭和結(jié)尾須至少分別安排5天和3天的行走，（在滿足資源約束的條件下）余下最多22天可安排為在村莊和礦山之間往返以及挖礦。已知較少出現(xiàn)沙暴天氣，假設(shè)晴天:高溫:沙暴的出現(xiàn)頻率為2:2:1，則可以得到每天采取行動(dòng)的收益期望如下表。晴天:高溫:沙暴為2:2:1下每天行動(dòng)收益期望表行動(dòng)資源消耗量期望(kg)收益期望(1x)收益期望(2x)行走62-190/天-380/天停留46.67-140/天-280/天挖礦104.4+682/天+364/天挖礦(但沙暴天停留)84.4+542/天+284/天具體分析第四關(guān)：如右表，礦山挖礦的收益期望均為正值。根據(jù)1x和2x的差距，可知：起點(diǎn)所購資源占比多的情況下，挖礦的收益期望高。村莊和礦山之間的最短距離為2，可知【村莊補(bǔ)給->礦山挖礦->村莊補(bǔ)給】這樣的往返補(bǔ)給行程中至少包含2+2天的行走：行走部分的收益期望為-380×2=-760元至少需要挖礦兩次才能使整體收益為正。行走部分花費(fèi)62×2×2=248kg資源理想狀態(tài)下(忽略細(xì)節(jié))，從村莊出來最多可滿載1200kg資源，經(jīng)過跋涉后還剩余952kg，一般情況下足以支撐≥2次挖礦。CUMCM2020穿越沙漠B晴天:高溫:沙暴為2:2:1下每天行動(dòng)收益期望表行動(dòng)資源消耗量期望(kg)收益期望(1x)收益期望(2x)行走62-190/天-380/天停留46.67-140/天-280/天挖礦104.4+682/天+364/天挖礦(但沙暴天停留)84.4+542/天+284/天因此，沙暴較少的以及起點(diǎn)所購資源占比多的情況下，前往礦山挖礦有較大可能獲得正收益，從而選擇挖礦賺錢模式。具體分析

CUMCM2020穿越沙漠B具體分析第五關(guān)策略：預(yù)決策：直接前往終點(diǎn)（同第三關(guān)）基于最短路徑貪心的無向圖簡化最短路徑對稱等效等決策概率第六關(guān)策略：預(yù)決策：挖礦（同第四關(guān)）多人挖礦對應(yīng)凈收入同時(shí)在村莊相遇時(shí)購買物資虧損嚴(yán)重前往終點(diǎn)決策基于逃離閾值CUMCM2020穿越沙漠B5起點(diǎn)46終點(diǎn)挖礦晴朗高溫沙暴1人8355955502人33595503人168-72-117挖礦晴朗高溫沙暴1人6701901002人170-310-4003人3-477-567挖礦晴朗高溫沙暴1人340-620-8002人-160-1120-13003人-327-1287-1467模型總結(jié)模型方法多樣原問題等效簡化、降維簡化綜合指導(dǎo)策略定量決策判定原理直觀從基本的貪心原則、動(dòng)態(tài)規(guī)劃、概率模型、Nash均衡出發(fā)決策符合直覺，并且具有合理性最終形式直接最終形式多以線性方式展示無通用定量策略CUMCM2020穿越沙漠B參考文獻(xiàn)和支撐材料參考文獻(xiàn)：[1]姜啟源,謝金星,葉俊.數(shù)學(xué)模型(第四版)[M].高等教育出版社,2011.[2]【算法復(fù)習(xí)】動(dòng)態(tài)規(guī)劃/hithongming/p/9229871.html[3]【動(dòng)態(tài)規(guī)劃】01背包問題/