2020年國(guó)賽B題講解

2020年國(guó)賽B題講解優(yōu)化與仿真2021年數(shù)學(xué)建模時(shí)間周6月28日讀題——審題——邏輯和量化認(rèn)真審題，選擇隊(duì)伍優(yōu)勢(shì)題目。（A題機(jī)理模型，C題數(shù)據(jù)分析，B題優(yōu)化仿真——編程）問題分析：——關(guān)鍵字求什么？——給出數(shù)據(jù)結(jié)果，用數(shù)據(jù)說話目標(biāo)是什么？——量化的數(shù)學(xué)表達(dá)式（模型）關(guān)鍵因素都有哪些？——充分討論，展開想象（不完全依靠文獻(xiàn)）問題之間的區(qū)別和聯(lián)系？——大局觀注意：B題目一般很少有合適的參考文獻(xiàn)2020年國(guó)賽B題——穿越沙漠考慮如下的小游戲：玩家憑借一張地圖，利用初始資金購買一定數(shù)量的水和食物（包括食品和其他日常用品），從起點(diǎn)出發(fā)，在沙漠中行走。途中會(huì)遇到不同的天氣，也可在礦山、村莊補(bǔ)充資金或資源，目標(biāo)是在規(guī)定時(shí)間內(nèi)到達(dá)終點(diǎn)，并保留盡可能多的資金。

分析：優(yōu)化問題——決策變量，約束條件，目標(biāo)函數(shù)？游戲的基本規(guī)則如下：（1）以天為基本時(shí)間單位，游戲的開始時(shí)間為第0天，玩家位于起點(diǎn)。玩家必須在截止日期或之前到達(dá)終點(diǎn)，到達(dá)終點(diǎn)后該玩家的游戲結(jié)束。（2）穿越沙漠需水和食物兩種資源，它們的最小計(jì)量單位均為箱。每天玩家擁有的水和食物質(zhì)量之和不能超過負(fù)重上限。若未到達(dá)終點(diǎn)而水或食物已耗盡，視為游戲失敗。（3）每天的天氣為“晴朗”、“高溫”、“沙暴”三種狀況之一，沙漠中所有區(qū)域的天氣相同。（4）每天玩家可從地圖中的某個(gè)區(qū)域到達(dá)與之相鄰的另一個(gè)區(qū)域，也可在原地停留。沙暴日必須在原地停留。（5）玩家在原地停留一天消耗的資源數(shù)量稱為基礎(chǔ)消耗量，行走一天消耗的資源數(shù)量為基礎(chǔ)消耗量的2倍。（6）玩家第0天可在起點(diǎn)處用初始資金以基準(zhǔn)價(jià)格購買水和食物。玩家可在起點(diǎn)停留或回到起點(diǎn)，但不能多次在起點(diǎn)購買資源。玩家到達(dá)終點(diǎn)后可退回剩余的水和食物，每箱退回價(jià)格為基準(zhǔn)價(jià)格的一半。（7）玩家在礦山停留時(shí)，可通過挖礦獲得資金，挖礦一天獲得的資金量稱為基礎(chǔ)收益。如果挖礦，消耗的資源數(shù)量為基礎(chǔ)消耗量的3倍；如果不挖礦，消耗的資源數(shù)量為基礎(chǔ)消耗量。到達(dá)礦山當(dāng)天不能挖礦。沙暴日也可挖礦。（8）玩家經(jīng)過或在村莊停留時(shí)可用剩余的初始資金或挖礦獲得的資金隨時(shí)購買水和食物，每箱價(jià)格為基準(zhǔn)價(jià)格的2倍。分析：規(guī)則——分類：天氣，行為，消耗&收益——資金變化請(qǐng)根據(jù)游戲的不同設(shè)定，建立數(shù)學(xué)模型，解決以下問題。1.假設(shè)只有一名玩家，在整個(gè)游戲時(shí)段內(nèi)每天天氣狀況事先全部已知，試給出一般情況下玩家的最優(yōu)策略。求解附件中的“第一關(guān)”和“第二關(guān)”，并將相應(yīng)結(jié)果分別填入Result.xlsx。2.假設(shè)只有一名玩家，玩家僅知道當(dāng)天的天氣狀況，可據(jù)此決定當(dāng)天的行動(dòng)方案，試給出一般情況下玩家的最佳策略，并對(duì)附件中的“第三關(guān)”和“第四關(guān)”進(jìn)行具體討論。分析：求最優(yōu)策略——行動(dòng)方案（路線，行為）——結(jié)果寫在Result文件中。強(qiáng)調(diào)一般到特殊實(shí)例的計(jì)算——要突出一般化模型進(jìn)一步分析：優(yōu)化問題決策變量：路線，行為約束條件：有限時(shí)間，資源限制（負(fù)重，生存）目標(biāo)函數(shù)：剩余資金最多

注1：附件所給地圖中，有公共邊界的兩個(gè)區(qū)域稱為相鄰，僅有公共頂點(diǎn)而沒有公共邊界的兩個(gè)區(qū)域不視作相鄰。注2：Result.xlsx中剩余資金數(shù)（剩余水量、剩余食物量）指當(dāng)日所需資源全部消耗完畢后的資金數(shù)（水量、食物量）。若當(dāng)日還有購買行為，則指完成購買后的資金數(shù)（水量、食物量）。分析：附件數(shù)據(jù)特點(diǎn)（第一關(guān)——第六關(guān)）參數(shù)設(shè)定：負(fù)重，時(shí)間限制，基礎(chǔ)收益，資源（重量，價(jià)格，基礎(chǔ)消耗）不同天氣：已知&未知——關(guān)系地圖：規(guī)則形狀，不規(guī)則形狀——如何表達(dá)Result結(jié)果表格分析路線，剩余資金，剩余水量，剩余食物問題之間的關(guān)系——大局觀聯(lián)系與區(qū)別：人數(shù)（1&n），天氣（已知&未知）人數(shù)（1&n）：目標(biāo)函數(shù)，競(jìng)爭(zhēng)&共贏——第一問和第二問是第三問的基礎(chǔ)天氣（已知&未知）：未知變?yōu)橐阎?，隨機(jī)變&依概率變——第一問是第二問的基礎(chǔ)關(guān)系：層層遞進(jìn)，由易到難對(duì)應(yīng)實(shí)際：第一問：?jiǎn)螜C(jī)版，離線游戲第二問：?jiǎn)螜C(jī)版，在線游戲第三問：聯(lián)網(wǎng)多人游戲，博弈進(jìn)一步細(xì)致分析——規(guī)則游戲的基本規(guī)則如下：（1）以天為基本時(shí)間單位，游戲的開始時(shí)間為第0天，玩家位于起點(diǎn)。玩家必須在截止日期或之前到達(dá)終點(diǎn)，到達(dá)終點(diǎn)后該玩家的游戲結(jié)束?！拗疲?）穿越沙漠需水和食物兩種資源，它們的最小計(jì)量單位均為箱。每天玩家擁有的水和食物質(zhì)量之和不能超過負(fù)重上限。若未到達(dá)終點(diǎn)而水或食物已耗盡，視為游戲失敗。——限制（3）每天的天氣為“晴朗”、“高溫”、“沙暴”三種狀況之一，沙漠中所有區(qū)域的天氣相同。（4）每天玩家可從地圖中的某個(gè)區(qū)域到達(dá)與之相鄰的另一個(gè)區(qū)域，也可在原地停留。沙暴日必須在原地停留?！鞖馀c行為的關(guān)系——天氣和消耗的關(guān)系（附件）（5）玩家在原地停留一天消耗的資源數(shù)量稱為基礎(chǔ)消耗量，行走一天消耗的資源數(shù)量為基礎(chǔ)消耗量的2倍。

——走停行為的消耗（6）玩家第0天可在起點(diǎn)處用初始資金以基準(zhǔn)價(jià)格購買水和食物。玩家可在起點(diǎn)停留或回到起點(diǎn)，但不能多次在起點(diǎn)購買資源。玩家到達(dá)終點(diǎn)后可退回剩余的水和食物，每箱退回價(jià)格為基準(zhǔn)價(jià)格的一半。

——資源折現(xiàn)——資源變資金（7）玩家在礦山停留時(shí)，可通過挖礦獲得資金，挖礦一天獲得的資金量稱為基礎(chǔ)收益。如果挖礦，消耗的資源數(shù)量為基礎(chǔ)消耗量的3倍；如果不挖礦，消耗的資源數(shù)量為基礎(chǔ)消耗量。到達(dá)礦山當(dāng)天不能挖礦。沙暴日也可挖礦。——礦山的特殊性，挖礦行為帶來的收益和消耗（8）玩家經(jīng)過或在村莊停留時(shí)可用剩余的初始資金或挖礦獲得的資金隨時(shí)購買水和食物，每箱價(jià)格為基準(zhǔn)價(jià)格的2倍?！迩f特殊性，可以進(jìn)行資源購置——村莊：資金變資源分析：規(guī)則——分類：天氣，行為，消耗&收益——資金變化整理規(guī)則游戲目標(biāo)為在規(guī)定時(shí)間內(nèi)到達(dá)終點(diǎn)并保留盡可能多的資金。游戲開始時(shí)，玩家位于起點(diǎn)，時(shí)間記為第0天，玩家需在規(guī)定時(shí)間內(nèi)到達(dá)終點(diǎn)，游戲方可結(jié)束；若在途中耗盡食物跟水，則認(rèn)為游戲失敗。游戲規(guī)則如下：沙漠天氣可分為“晴朗”、“高溫”與“沙暴”，“晴朗”跟“高溫”天氣玩家可選擇到下一區(qū)域或逗留，沙暴天氣玩家需留在原地；停留在原地時(shí)的耗能為基礎(chǔ)耗能，行走一天的耗能為基礎(chǔ)耗能的兩倍；——天氣——行為——消耗（關(guān)系）途中有村莊與礦山兩個(gè)地點(diǎn)，村莊可進(jìn)行物資補(bǔ)充，價(jià)格為起點(diǎn)物資購買時(shí)的基準(zhǔn)價(jià)格的兩倍；玩家可在礦山中挖礦，獲得收益，挖礦時(shí)的耗能為基礎(chǔ)耗能的三倍，不挖礦時(shí)的耗能為基礎(chǔ)耗能；

——特殊地點(diǎn)——新的行為——收益&消耗，資金&資源玩家回到終點(diǎn)后可將剩余的物資退回，退回價(jià)格為基準(zhǔn)價(jià)格的1/2。——資源&資金決策變量時(shí)間，地點(diǎn)，行為（剩余水，剩余食物）——盡可能簡(jiǎn)化決策變量空間維數(shù)——細(xì)致分析降低算法難度目標(biāo)函數(shù)剩余資金數(shù)約束條件時(shí)間限制，負(fù)重限制，生存消耗問題1在給定所有條件下的單人最優(yōu)決策問題。由于地圖、消耗、收入、時(shí)間期限等已給定，玩家事先知道所有天氣情況，且是單人決策。所以玩家的所有決策方案是有限種，這意味著若存在使玩家成功到達(dá)終點(diǎn)的解，則至少存在一種最優(yōu)方案，使得玩家到達(dá)終點(diǎn)時(shí)資金最多。由于玩家在決策時(shí)已知游戲時(shí)段內(nèi)所有天氣情況，一般可采用動(dòng)態(tài)規(guī)劃模型、整數(shù)規(guī)劃模型，改進(jìn)的Floyd算法，啟發(fā)式算法或者M(jìn)etaheuristic算法等求解出最優(yōu)策略。

整數(shù)規(guī)劃

簡(jiǎn)化求解——降低算法難度簡(jiǎn)化求解，可以對(duì)最優(yōu)解的性質(zhì)進(jìn)行討論，從而縮小可行解的范圍，比如：玩家在起點(diǎn)，終點(diǎn)，礦山，村莊這樣的特殊區(qū)域之間的路徑必為兩者之間的最短路，其他普通區(qū)域可以有更便捷的方式。注意：有些簡(jiǎn)化不對(duì)，“玩家必在第T天到達(dá)終點(diǎn)”，“玩家不會(huì)兩次到達(dá)礦山”之類的可視化表達(dá)Result結(jié)果呈現(xiàn)——正文中體現(xiàn)問題2未給定整個(gè)游戲規(guī)定時(shí)間段內(nèi)的天氣狀況，要求得出此情況下穿越沙漠的最佳策略。由于玩家在通過沙漠的過程中可能碰到的天氣未知，故玩家能否達(dá)到終點(diǎn)存在不確定性。玩家沒有達(dá)到終點(diǎn)將會(huì)直接導(dǎo)致游戲失敗。由于玩家在決策時(shí)未來各天的天氣情況是未知的，因此無法求得像第一問那樣的最優(yōu)策略。對(duì)此，有兩種思路可在未來信息不確定情況下尋得較理想的解決方案?；陔S機(jī)的方法：——未知變已知假設(shè)天氣是一個(gè)隨機(jī)事件?？梢约僭O(shè)天氣狀況相互獨(dú)立，服從某一離散分布；也可以假設(shè)當(dāng)日天氣已知條件下，次日天氣服從某一條件分布，甚至可以根據(jù)前一天的天氣動(dòng)態(tài)調(diào)整未來各種天氣狀況發(fā)生的概率。核心：天氣的狀態(tài)轉(zhuǎn)移矩陣這一假設(shè)下，玩家在游戲結(jié)束時(shí)的資金是一個(gè)隨機(jī)變量，可以用在各種可行策略下的選擇數(shù)學(xué)期望較大的策略借鑒在線問題的競(jìng)爭(zhēng)比分析方法?！顗闹笜?biāo)不斷改善對(duì)當(dāng)天采取的某種策略，可以求得該策略在未來各種天氣狀況下的某種最壞指標(biāo)。

如游戲結(jié)束時(shí)資金數(shù)值的最小值，或?qū)嶋H獲得資金數(shù)值與最優(yōu)解所獲資金數(shù)值比值的最小值。玩家應(yīng)在各種可行策略中選擇上述最壞指標(biāo)最佳的策略，又比如可以制定“最壞情況”下的策略，在題目給定的條件下，將未知的天氣都視為最差的天氣考慮。在這種情況下求出最佳路線，這條路線就一定能保證玩家在通關(guān)的基礎(chǔ)上，并隨著天氣的改善從而收益增加。在第三關(guān)和第四關(guān)的參數(shù)設(shè)置中，高溫天氣的資源消耗超過晴朗天氣資源消耗的兩倍，因此從局部來看高溫天氣停留一日優(yōu)于行走。但是也要考慮到停留可能減少挖礦的時(shí)間從而減少挖礦收入。如果停留天數(shù)過多，可能因未來沙暴天氣而無法到達(dá)終點(diǎn)。挖礦與否也與天氣狀況有關(guān)，晴朗天氣挖礦純收益較為明顯，對(duì)高溫天氣，特別是起點(diǎn)購買資源不足需要從村莊補(bǔ)給，或礦山遠(yuǎn)離起點(diǎn)到終點(diǎn)的最短路時(shí)，挖礦將無利可圖。因此，決策既需隨時(shí)間推移和信息披露逐步作出，也需整體考慮剩余游戲進(jìn)程。對(duì)第三關(guān)，由于區(qū)域數(shù)較少，游戲時(shí)間較短，這使得枚舉所有的行動(dòng)方案或天氣狀況成為可能。在第四關(guān)決策時(shí)，可能需要反復(fù)求解不同情況下的最優(yōu)解。由于該實(shí)例有一定規(guī)模，一般只能通過啟發(fā)式算法予以實(shí)現(xiàn)。第三關(guān)分析1：全晴朗天氣與全高溫天氣下的最優(yōu)路線都是1-5-6-13。高溫天氣行進(jìn)的消耗為2×135=270（元），大于晴朗天氣行進(jìn)消耗的兩倍，遇到高溫天氣時(shí)，局部的最優(yōu)方案是停留一天，但考慮到在第三關(guān)中高溫天氣與晴朗天氣是隨機(jī)出現(xiàn)的，如若遇到高溫天氣就不行進(jìn)，會(huì)有無法到達(dá)終點(diǎn)的風(fēng)險(xiǎn)。所以不論二者的出現(xiàn)概率如何，第三關(guān)的最優(yōu)路線是1-5-6-13。分析2：“第三關(guān)”玩家在沙漠共待的時(shí)間??不能超過10天，且10天內(nèi)沙暴天氣也不會(huì)出現(xiàn)。故此時(shí)玩家在通過沙漠時(shí)的天氣情況就剩下晴朗和高溫兩種情況，且只含起點(diǎn)、礦山和終點(diǎn)三個(gè)位置點(diǎn)，根據(jù)題目要求，應(yīng)在規(guī)定的10天內(nèi)到達(dá)終點(diǎn)，且為了保留盡可能多的資金。可以判斷出將玩家在第三關(guān)的路線分為兩類：起點(diǎn)→終點(diǎn)起點(diǎn)→礦山→終點(diǎn)分別計(jì)算相同天氣狀況下，玩家通過第一類最佳路線到達(dá)終點(diǎn)第二類最佳路線達(dá)到終點(diǎn)時(shí)的剩余總資金，將兩者進(jìn)行比較，得出所有情況下的剩余總資金最大值，將其作為最佳方案。經(jīng)過分析：對(duì)于任意天氣，都是第一類路線的最終剩余資金較多，即應(yīng)從起點(diǎn)直接向終點(diǎn)前進(jìn)。為保證玩家成功到終點(diǎn)，物資購買應(yīng)按照三天天氣狀況全部是“高溫”，即購買54箱水，54箱食物，總重量為270kg，最終資金剩余量由當(dāng)天的天氣決定。第三關(guān)結(jié)果第四關(guān)

問題3第三問為博弈問題。本問題設(shè)置了兩種情景。（第五關(guān)，第六關(guān)）第一種情景在決策方式上類似于第一問，但玩家最終的資金會(huì)受到其他玩家策略的影響。在玩家理性的假設(shè)下，所有玩家的行動(dòng)形成一Nash均衡。由于假設(shè)資源消耗或挖礦收益僅與同時(shí)采用同一對(duì)區(qū)域間行走或同時(shí)挖礦的玩家數(shù)量有關(guān)，而與具體玩家無關(guān)。篩選出每位參與者的占優(yōu)策略后，可求得博弈的Nash均衡。根據(jù)第3關(guān)模型，當(dāng)前兩天的天氣出現(xiàn)高溫后，則不前往礦山最劃算。因此將路線定為不前往礦山，則可能選擇的路線情況有：①1→5→6→13②1→4→6→13③1→4→7→12→13路線1為單人游戲情況下的最優(yōu)情況，可將此路線分給玩家1。對(duì)于玩家2來說，為了盡可能與玩家2分開行動(dòng)，可以采用的行走策略包括：與玩家1同路線但出發(fā)時(shí)間適當(dāng)延后；或同時(shí)出發(fā)但選擇不同路線。問題3（第六關(guān)）在第二種情景下，玩家的策略可以在每天作出。此時(shí)玩家不僅要像第二問那樣考慮每天的天氣狀況，還要考慮其他玩家的行動(dòng)對(duì)自身的影響。玩家的策略應(yīng)是其他玩家策略的一個(gè)最優(yōu)反應(yīng)，這是很難完整給出的。可以在第二問基礎(chǔ)上，給出若干原則性方案，也可以通過機(jī)器學(xué)習(xí)或模擬的方法，給出若干經(jīng)驗(yàn)性判斷。優(yōu)秀論文展示要點(diǎn)難點(diǎn)展示復(fù)雜過程邏輯呈現(xiàn)符號(hào)語言&文字解釋難關(guān)思路呈現(xiàn)（第五關(guān)，第六關(guān)）結(jié)果呈現(xiàn)結(jié)果呈現(xiàn)總結(jié)模型的數(shù)學(xué)表達(dá)：優(yōu)化模型——要素齊全算法的細(xì)節(jié)描述：邏輯清楚——分類表達(dá)結(jié)果呈現(xiàn)：圖，表——不可缺參數(shù)靈敏性分析&模型檢驗(yàn)——盡量完成2019年國(guó)賽B題“同心協(xié)力”策略研究

“同心協(xié)力”（又稱“同心鼓”）是一項(xiàng)團(tuán)隊(duì)協(xié)作能力拓展項(xiàng)目。該項(xiàng)目的道具是一面牛皮雙面鼓，鼓身中間固定多根繩子，繩子在鼓身上的固定點(diǎn)沿圓周呈均勻分布，每根繩子長(zhǎng)度相同。團(tuán)隊(duì)成員每人牽拉一根繩子，使鼓面保持水平。項(xiàng)目開始時(shí)，球從鼓面中心上方豎直落下，隊(duì)員同心協(xié)力將球顛起，使其有節(jié)奏地在鼓面上跳動(dòng)。顛球過程中，隊(duì)員只能抓握繩子的末端，不能接觸鼓或繩子的其他位置。38項(xiàng)目所用排球的質(zhì)量為270g。鼓面直徑為40cm，鼓身高度為22cm，鼓的質(zhì)量為3.6kg。隊(duì)員人數(shù)不少于8人，隊(duì)員之間的最小距離不得小于60cm。項(xiàng)目開始時(shí)，球從鼓面中心上方40cm處豎直落下，球被顛起的高度應(yīng)離開鼓面40cm以上，如果低于40cm，則項(xiàng)目停止。項(xiàng)目的目標(biāo)