2020年國賽B題講解

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

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

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

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

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

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

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

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

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

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

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