2020年国赛B题讲解

2020年国赛B题讲解优化与仿真2021年数学建模时间周6月28日读题——审题——逻辑和量化认真审题，选择队伍优势题目。（A题机理模型，C题数据分析，B题优化仿真——编程）问题分析：——关键字求什么？——给出数据结果，用数据说话目标是什么？——量化的数学表达式（模型）关键因素都有哪些？——充分讨论，展开想象（不完全依靠文献）问题之间的区别和联系？——大局观注意：B题目一般很少有合适的参考文献2020年国赛B题——穿越沙漠考虑如下的小游戏：玩家凭借一张地图，利用初始资金购买一定数量的水和食物（包括食品和其他日常用品），从起点出发，在沙漠中行走。途中会遇到不同的天气，也可在矿山、村庄补充资金或资源，目标是在规定时间内到达终点，并保留尽可能多的资金。

分析：优化问题——决策变量，约束条件，目标函数？游戏的基本规则如下：（1）以天为基本时间单位，游戏的开始时间为第0天，玩家位于起点。玩家必须在截止日期或之前到达终点，到达终点后该玩家的游戏结束。（2）穿越沙漠需水和食物两种资源，它们的最小计量单位均为箱。每天玩家拥有的水和食物质量之和不能超过负重上限。若未到达终点而水或食物已耗尽，视为游戏失败。（3）每天的天气为“晴朗”、“高温”、“沙暴”三种状况之一，沙漠中所有区域的天气相同。（4）每天玩家可从地图中的某个区域到达与之相邻的另一个区域，也可在原地停留。沙暴日必须在原地停留。（5）玩家在原地停留一天消耗的资源数量称为基础消耗量，行走一天消耗的资源数量为基础消耗量的2倍。（6）玩家第0天可在起点处用初始资金以基准价格购买水和食物。玩家可在起点停留或回到起点，但不能多次在起点购买资源。玩家到达终点后可退回剩余的水和食物，每箱退回价格为基准价格的一半。（7）玩家在矿山停留时，可通过挖矿获得资金，挖矿一天获得的资金量称为基础收益。如果挖矿，消耗的资源数量为基础消耗量的3倍；如果不挖矿，消耗的资源数量为基础消耗量。到达矿山当天不能挖矿。沙暴日也可挖矿。（8）玩家经过或在村庄停留时可用剩余的初始资金或挖矿获得的资金随时购买水和食物，每箱价格为基准价格的2倍。分析：规则——分类：天气，行为，消耗&收益——资金变化请根据游戏的不同设定，建立数学模型，解决以下问题。1.假设只有一名玩家，在整个游戏时段内每天天气状况事先全部已知，试给出一般情况下玩家的最优策略。求解附件中的“第一关”和“第二关”，并将相应结果分别填入Result.xlsx。2.假设只有一名玩家，玩家仅知道当天的天气状况，可据此决定当天的行动方案，试给出一般情况下玩家的最佳策略，并对附件中的“第三关”和“第四关”进行具体讨论。分析：求最优策略——行动方案（路线，行为）——结果写在Result文件中。强调一般到特殊实例的计算——要突出一般化模型进一步分析：优化问题决策变量：路线，行为约束条件：有限时间，资源限制（负重，生存）目标函数：剩余资金最多

注1：附件所给地图中，有公共边界的两个区域称为相邻，仅有公共顶点而没有公共边界的两个区域不视作相邻。注2：Result.xlsx中剩余资金数（剩余水量、剩余食物量）指当日所需资源全部消耗完毕后的资金数（水量、食物量）。若当日还有购买行为，则指完成购买后的资金数（水量、食物量）。分析：附件数据特点（第一关——第六关）参数设定：负重，时间限制，基础收益，资源（重量，价格，基础消耗）不同天气：已知&未知——关系地图：规则形状，不规则形状——如何表达Result结果表格分析路线，剩余资金，剩余水量，剩余食物问题之间的关系——大局观联系与区别：人数（1&n），天气（已知&未知）人数（1&n）：目标函数，竞争&共赢——第一问和第二问是第三问的基础天气（已知&未知）：未知变为已知，随机变&依概率变——第一问是第二问的基础关系：层层递进，由易到难对应实际：第一问：单机版，离线游戏第二问：单机版，在线游戏第三问：联网多人游戏，博弈进一步细致分析——规则游戏的基本规则如下：（1）以天为基本时间单位，游戏的开始时间为第0天，玩家位于起点。玩家必须在截止日期或之前到达终点，到达终点后该玩家的游戏结束。——限制（2）穿越沙漠需水和食物两种资源，它们的最小计量单位均为箱。每天玩家拥有的水和食物质量之和不能超过负重上限。若未到达终点而水或食物已耗尽，视为游戏失败。——限制（3）每天的天气为“晴朗”、“高温”、“沙暴”三种状况之一，沙漠中所有区域的天气相同。（4）每天玩家可从地图中的某个区域到达与之相邻的另一个区域，也可在原地停留。沙暴日必须在原地停留。——天气与行为的关系——天气和消耗的关系（附件）（5）玩家在原地停留一天消耗的资源数量称为基础消耗量，行走一天消耗的资源数量为基础消耗量的2倍。

——走停行为的消耗（6）玩家第0天可在起点处用初始资金以基准价格购买水和食物。玩家可在起点停留或回到起点，但不能多次在起点购买资源。玩家到达终点后可退回剩余的水和食物，每箱退回价格为基准价格的一半。

——资源折现——资源变资金（7）玩家在矿山停留时，可通过挖矿获得资金，挖矿一天获得的资金量称为基础收益。如果挖矿，消耗的资源数量为基础消耗量的3倍；如果不挖矿，消耗的资源数量为基础消耗量。到达矿山当天不能挖矿。沙暴日也可挖矿。——矿山的特殊性，挖矿行为带来的收益和消耗（8）玩家经过或在村庄停留时可用剩余的初始资金或挖矿获得的资金随时购买水和食物，每箱价格为基准价格的2倍。——村庄特殊性，可以进行资源购置——村庄：资金变资源分析：规则——分类：天气，行为，消耗&收益——资金变化整理规则游戏目标为在规定时间内到达终点并保留尽可能多的资金。游戏开始时，玩家位于起点，时间记为第0天，玩家需在规定时间内到达终点，游戏方可结束；若在途中耗尽食物跟水，则认为游戏失败。游戏规则如下：沙漠天气可分为“晴朗”、“高温”与“沙暴”，“晴朗”跟“高温”天气玩家可选择到下一区域或逗留，沙暴天气玩家需留在原地；停留在原地时的耗能为基础耗能，行走一天的耗能为基础耗能的两倍；——天气——行为——消耗（关系）途中有村庄与矿山两个地点，村庄可进行物资补充，价格为起点物资购买时的基准价格的两倍；玩家可在矿山中挖矿，获得收益，挖矿时的耗能为基础耗能的三倍，不挖矿时的耗能为基础耗能；

——特殊地点——新的行为——收益&消耗，资金&资源玩家回到终点后可将剩余的物资退回，退回价格为基准价格的1/2。——资源&资金决策变量时间，地点，行为（剩余水，剩余食物）——尽可能简化决策变量空间维数——细致分析降低算法难度目标函数剩余资金数约束条件时间限制，负重限制，生存消耗问题1在给定所有条件下的单人最优决策问题。由于地图、消耗、收入、时间期限等已给定，玩家事先知道所有天气情况，且是单人决策。所以玩家的所有决策方案是有限种，这意味着若存在使玩家成功到达终点的解，则至少存在一种最优方案，使得玩家到达终点时资金最多。由于玩家在决策时已知游戏时段内所有天气情况，一般可采用动态规划模型、整数规划模型，改进的Floyd算法，启发式算法或者Metaheuristic算法等求解出最优策略。

整数规划

简化求解——降低算法难度简化求解，可以对最优解的性质进行讨论，从而缩小可行解的范围，比如：玩家在起点，终点，矿山，村庄这样的特殊区域之间的路径必为两者之间的最短路，其他普通区域可以有更便捷的方式。注意：有些简化不对，“玩家必在第T天到达终点”，“玩家不会两次到达矿山”之类的可视化表达Result结果呈现——正文中体现问题2未给定整个游戏规定时间段内的天气状况，要求得出此情况下穿越沙漠的最佳策略。由于玩家在通过沙漠的过程中可能碰到的天气未知，故玩家能否达到终点存在不确定性。玩家没有达到终点将会直接导致游戏失败。由于玩家在决策时未来各天的天气情况是未知的，因此无法求得像第一问那样的最优策略。对此，有两种思路可在未来信息不确定情况下寻得较理想的解决方案。基于随机的方法：——未知变已知假设天气是一个随机事件。可以假设天气状况相互独立，服从某一离散分布；也可以假设当日天气已知条件下，次日天气服从某一条件分布，甚至可以根据前一天的天气动态调整未来各种天气状况发生的概率。核心：天气的状态转移矩阵这一假设下，玩家在游戏结束时的资金是一个随机变量，可以用在各种可行策略下的选择数学期望较大的策略借鉴在线问题的竞争比分析方法。——最坏指标不断改善对当天采取的某种策略，可以求得该策略在未来各种天气状况下的某种最坏指标。

如游戏结束时资金数值的最小值，或实际获得资金数值与最优解所获资金数值比值的最小值。玩家应在各种可行策略中选择上述最坏指标最佳的策略，又比如可以制定“最坏情况”下的策略，在题目给定的条件下，将未知的天气都视为最差的天气考虑。在这种情况下求出最佳路线，这条路线就一定能保证玩家在通关的基础上，并随着天气的改善从而收益增加。在第三关和第四关的参数设置中，高温天气的资源消耗超过晴朗天气资源消耗的两倍，因此从局部来看高温天气停留一日优于行走。但是也要考虑到停留可能减少挖矿的时间从而减少挖矿收入。如果停留天数过多，可能因未来沙暴天气而无法到达终点。挖矿与否也与天气状况有关，晴朗天气挖矿纯收益较为明显，对高温天气，特别是起点购买资源不足需要从村庄补给，或矿山远离起点到终点的最短路时，挖矿将无利可图。因此，决策既需随时间推移和信息披露逐步作出，也需整体考虑剩余游戏进程。对第三关，由于区域数较少，游戏时间较短，这使得枚举所有的行动方案或天气状况成为可能。在第四关决策时，可能需要反复求解不同情况下的最优解。由于该实例有一定规模，一般只能通过启发式算法予以实现。第三关分析1：全晴朗天气与全高温天气下的最优路线都是1-5-6-13。高温天气行进的消耗为2×135=270（元），大于晴朗天气行进消耗的两倍，遇到高温天气时，局部的最优方案是停留一天，但考虑到在第三关中高温天气与晴朗天气是随机出现的，如若遇到高温天气就不行进，会有无法到达终点的风险。所以不论二者的出现概率如何，第三关的最优路线是1-5-6-13。分析2：“第三关”玩家在沙漠共待的时间𝑡不能超过10天，且10天内沙暴天气也不会出现。故此时玩家在通过沙漠时的天气情况就剩下晴朗和高温两种情况，且只含起点、矿山和终点三个位置点，根据题目要求，应在规定的10天内到达终点，且为了保留尽可能多的资金。可以判断出将玩家在第三关的路线分为两类：起点→终点起点→矿山→终点分别计算相同天气状况下，玩家通过第一类最佳路线到达终点第二类最佳路线达到终点时的剩余总资金，将两者进行比较，得出所有情况下的剩余总资金最大值，将其作为最佳方案。经过分析：对于任意天气，都是第一类路线的最终剩余资金较多，即应从起点直接向终点前进。为保证玩家成功到终点，物资购买应按照三天天气状况全部是“高温”，即购买54箱水，54箱食物，总重量为270kg，最终资金剩余量由当天的天气决定。第三关结果第四关

问题3第三问为博弈问题。本问题设置了两种情景。（第五关，第六关）第一种情景在决策方式上类似于第一问，但玩家最终的资金会受到其他玩家策略的影响。在玩家理性的假设下，所有玩家的行动形成一Nash均衡。由于假设资源消耗或挖矿收益仅与同时采用同一对区域间行走或同时挖矿的玩家数量有关，而与具体玩家无关。筛选出每位参与者的占优策略后，可求得博弈的Nash均衡。根据第3关模型，当前两天的天气出现高温后，则不前往矿山最划算。因此将路线定为不前往矿山，则可能选择的路线情况有：①1→5→6→13②1→4→6→13③1→4→7→12→13路线1为单人游戏情况下的最优情况，可将此路线分给玩家1。对于玩家2来说，为了尽可能与玩家2分开行动，可以采用的行走策略包括：与玩家1同路线但出发时间适当延后；或同时出发但选择不同路线。问题3（第六关）在第二种情景下，玩家的策略可以在每天作出。此时玩家不仅要像第二问那样考虑每天的天气状况，还要考虑其他玩家的行动对自身的影响。玩家的策略应是其他玩家策略的一个最优反应，这是很难完整给出的。可以在第二问基础上，给出若干原则性方案，也可以通过机器学习或模拟的方法，给出若干经验性判断。优秀论文展示要点难点展示复杂过程逻辑呈现符号语言&文字解释难关思路呈现（第五关，第六关）结果呈现结果呈现总结模型的数学表达：优化模型——要素齐全算法的细节描述：逻辑清楚——分类表达结果呈现：图，表——不可缺参数灵敏性分析&模型检验——尽量完成2019年国赛B题“同心协力”策略研究

“同心协力”（又称“同心鼓”）是一项团队协作能力拓展项目。该项目的道具是一面牛皮双面鼓，鼓身中间固定多根绳子，绳子在鼓身上的固定点沿圆周呈均匀分布，每根绳子长度相同。团队成员每人牵拉一根绳子，使鼓面保持水平。项目开始时，球从鼓面中心上方竖直落下，队员同心协力将球颠起，使其有节奏地在鼓面上跳动。颠球过程中，队员只能抓握绳子的末端，不能接触鼓或绳子的其他位置。38项目所用排球的质量为270g。鼓面直径为40cm，鼓身高度为22cm，鼓的质量为3.6kg。队员人数不少于8人，队员之间的最小距离不得小于60cm。项目开始时，球从鼓面中心上方40cm处竖直落下，球被颠起的高度应离开鼓面40cm以上，如果低于40cm，则项目停止。项目的目标