2021全国大学生数学建模竞赛B题思路

杨利霞

2021全国大学生数学建模竞赛B题思路
考虑如下的小游戏：玩家凭借一张地图，利用初始资金购买一定数量的水和食物（包括食品和其他日常用品），从起点出发，在沙漠中行走。途中会遇到不同的天气，也可在矿山、村庄补充资金或资源，目标是在规定时间内到达终点，并保留尽可能多的资金。
5 p7 S8 W- J3 x* ?) |) \6 l1 i# m) J/ S游戏的基本规则如下：
% s8 C# c' D5 ~/ V% D  V* w* ^; v（1）以天为基本时间单位，游戏的开始时间为第0天，玩家位于起点。玩家必须在截止日期或之前到达终点，到达终点后该玩家的游戏结束。
1 `; x% T1 `! }. o! I, }（2）穿越沙漠需水和食物两种资源，它们的最小计量单位均为箱。每天玩家拥有的水和食物质量之和不能超过负重上限。若未到达终点而水或食物已耗尽，视为游戏失败。
7 J/ w& J3 X* [4 q% s/ E0 `（3）每天的天气为“晴朗”、“高温”、“沙暴”三种状况之一，沙漠中所有区域的天气相同。
4 d% p' ~( S. O6 B7 ~" _; g) C5 B（4）每天玩家可从地图中的某个区域到达与之相邻的另一个区域，也可在原地停留。沙暴日必须在原地停留。
（5）玩家在原地停留一天消耗的资源数量称为基础消耗量，行走一天消耗的资源数量为基础消耗量的 倍。
（6）玩家第0天可在起点处用初始资金以基准价格购买水和食物。玩家可在起点停留或回到起点，但不能多次在起点购买资源。玩家到达终点后可退回剩余的水和食物，每箱退回价格为基准价格的一半。
# x2 W* W1 i% \- a% K3 x; A（7）玩家在矿山停留时，可通过挖矿获得资金，挖矿一天获得的资金量称为基础收益。如果挖矿，消耗的资源数量为基础消耗量的 倍；如果不挖矿，消耗的资源数量为基础消耗量。到达矿山当天不能挖矿。沙暴日也可挖矿。
6 T+ Z% O: }* J/ a4 ]（8）玩家经过或在村庄停留时可用剩余的初始资金或挖矿获得的资金随时购买水和食物，每箱价格为基准价格的2倍。
+ s  G1 h8 J7 p$ Z' l请根据游戏的不同设定，建立数学模型，解决以下问题。
9 Z6 [% i! J; ~+ n. w5 w+ ^' ]

& b' n/ H( ?. [* M# T9 n1 U假设只有一名玩家，在整个游戏时段内每天天气状况事先全部已知，试给出一般情况下玩家的最优策略。求解附件中的“第一关”和“第二关”，并将相应结果分别填入Result.xlsx。
假设只有一名玩家，玩家仅知道当天的天气状况，可据此决定当天的行动方案，试给出一般情况下玩家的最佳策略，并对附件中的“第三关”和“第四关”进行具体讨论。
7 c4 N, y  d8 N现有 名玩家，他们有相同的初始资金，且同时从起点出发。若某天其中的任意 名玩家均从区域A行走到区域B( )，则他们中的任一位消耗的资源数量均为基础消耗量的 倍；若某天其中的任意 名玩家在同一矿山挖矿，则他们中的任一位消耗的资源数量均为基础消耗量的 倍，且每名玩家一天可通过挖矿获得的资金是基础收益的 ；若某天其中的任意 名玩家在同一村庄购买资源，每箱价格均为基准价格的 倍。其他情况下消耗资源数量与资源价格与单人游戏相同。
（1）假设在整个游戏时段内每天天气状况事先全部已知，每名玩家的行动方案需在第 天确定且此后不能更改。试给出一般情况下玩家应采取的策略，并对附件中的“第五关”进行具体讨论。
（2）假设所有玩家仅知道当天的天气状况，从第 天起，每名玩家在当天行动结束后均知道其余玩家当天的行动方案和剩余的资源数量，随后确定各自第二天的行动方案。全国大学生数学建模竞赛即将开始，思路发布在这里
https://mathmodel.lanzoui.com/s/cumcm试给出一般情况下玩家应采取的策略，并对附件中的“第六关”进行具体讨论。
注1：附件所给地图中，有公共边界的两个区域称为相邻，仅有公共顶点而没有公共边界的两个区域不视作相邻。
6 M5 Z$ l: W# ~* q( R/ N" C注2：Result.xlsx中剩余资金数（剩余水量、剩余食物量）指当日所需资源全部消耗完毕后的资金数（水量、食物量）。若当日还有购买行为，则指完成购买后的资金数（水量、食物量）。
关键词
动态规划模型、博弈树、蒙特卡洛仿真模型、最优化原理
目标
- F& T+ X4 }2 W- \在规定时间内到达终点，并保留尽可能多的资金，注意是钱！不是尽快跑出沙漠！
问题一分析
2 t5 p# M; @: G( a题目给出了近30天的天气情况，所以玩家走出沙漠后身上剩余的资金是个定值，而我们要求的就是这个定值的最大值。因为整个游戏过程中，有矿山和村庄这两个特殊点，所以不能用平时学的最短路径来求解了。但可以将整个游戏分为若干阶段：第一阶段是玩家从起点出发到村庄或矿山的路径；第二阶段是玩家在村庄和矿山来回的路径；第三阶段是玩家从村庄或矿山出发到终点的路径。而第一阶段和第三阶段可以利用动态规划求解，第二阶段根据运筹学原理，计算出在村庄与矿山的时间分配以及受天气影响在起点应该购买的物资。整个阶段可以通过设置变量，求解出目标利益函数，分析函数曲线，找出最优解。
问题二分析
- A% R& ^; {  Z! H/ p. W3 |相较与问题一，问题二的天气未知，所以最后求出的结果也不是个定值，可以分类讨论，各种天气的出现比例给出不同的解决方案。同问题一，将整个游戏分为若干阶段，对最终结果影响最大的天气是沙暴，所以我们在确定天气出现比率时候，需要将沙暴出现的位置（第几阶段）进行分类讨论，而不是对接下来一天可能是哪种天气进行分类讨论（这样就算复杂了）。之后根据当天的天气以及玩家身上所剩下的资源数和游戏地图来规划后面的路线。对不同天气应进行分类讨论，采用分支界限法，并进行剪枝处理来降低计算量。
) I9 V1 e7 p% B/ R( P- u问题三分析
5 [) u7 V& u' N# \' a& [较大的变化是，游戏可以有多名玩家参与，而每个人的目标依然是使自己利益最大化，也就不存在牺牲小我，成就大我的那种情况，也不会干损人不利己的事。多玩家参与的游戏相对于一名玩家参与的游戏而言，原来设定的最佳路径会因为该路径上有其它玩家而选择原地等待或改变路径。每名玩家需要根据博弈论的原理，以其他玩家剩余水和食物资源的数量以及离矿山或村庄的位置为依据，来推测该名玩家下一步的行动方案。因为未来天气依然未知，这里使用蒙特卡洛仿真模型实现对不同比例天气的模拟，玩家在对应天气下依据博弈论原理进行选择。（蒙特卡洛仿真，博弈树均可用编程语言实现，我们用的是JAVA语言，写了三百行左右）
B 题是基本的旅游路线建模问题，这样的游戏在团建中经常出现，如果有熟悉游戏规则的小伙伴解题应该会很快就上手。关键需要搞懂题目中最基础的游戏规则。题目的本质是在资金既定的情况下，更快结束游戏，并保证能够保留更多的资金，
+ K8 n# ?- A/ G  l' }% i" ^$ e第一问：在第一关和第二关的探险过程中，运用初始的资金对于资源进行合理的分配，可以通过线性规划，确定好在未来一段时间的消耗与收益，制定好合理的规划，通过 MATLAB 计算出需要使用的资源。第一问的地图可以使用 TSP算法，可以通过 LINGO 和 MATLAB 两个软件进行计算，选择出最优路径。也可以使用神经网络算法，来对于路径的选择进行训练，最终也可以得到最优路径。方法较多，仅供参考。经过多次训练对比，最终计算出最优策略，对比资金数量。第一问相对而言比较简单。
' t( H' _: ^+ N0 c' s  e第二问：第二问与第一问相比提升了难度，如果玩家在进行策略安排的时候，不知道天气的状况那么小伙伴们可以自己商讨给出何种方案，比如多买水，多买食物等等方法，再这之后通过选择最优路径进行合理的方法选择并讨论，解题方法相对比较固定。也可以使用神经网络算法进行训练，并给出一般的情况说明。第三关和第四关相对来说，地图位置更加复杂，需要通过 LINGO 算法对其进行合理编排，编写代码是一项比较困难的工作，
第三问
1） 对于 n 名相同的初始资金，且同时从起点出发的玩家来说，游戏规则需要进一步注意规范，为了保证多方共赢，在天气状况已知的情况下，可以通过先前 MATLAB 中的神经网络算法算出的最优旅行路线，计算多次的结果进行对比，保证不会出现重复的状况， 剔除掉重复出现的次数。觉得次数比较慢，可以通过遗传算法、蚁群算法等来对其进行优化，体现模型的创新性。因为天气状况已知，所以相对比较好安排合理的路线，对于安排好的路线分别进行编号，再依次进行合理的计算，最终确定结果，
5 s% j; k6 V# h: j（2） 对于 n 名相同的初始资金，且同时从起点出发的玩家来说，游戏规则需要进一步注意规范，为了保证多方共赢，在天气状况未充分被知晓的情况下，可以通过先前 MATLAB 中的神经网络算法算出的最优旅行路线，分别对其进行最终受益进行计算，选择出比较合理的解决方案，在一般情况下，第六关的地图也相对较为复杂，通过 LINGO 进行编码，再带入模型中进行计算，再对理想化结果进行对比，确定两者之间的差距，对于自身的资源进行调整，对于不同的地图，携带的资源往往也会发生不同，那么就需要对其进行合理的解释即可
1 N6 H& ~9 X8 a1 R& H0 Z1 t( DB 题 穿越沙漠玩家凭借一张地图，利用初始资金购买一定数量的水和食物（包括食品和其他日常用品），从起点出发，在沙漠中行走。途中会遇到不同的天气，也可在矿山、村庄补充资金或资源，目标是在规定时间内到达终点，并保留尽可能多的资金。有8条游戏的基本规则。需要根据游戏的不同设定，建立数学模型，解决问题。
选定B题之后，光是这个矿山和村庄就把人搞得头疼，第六关的多人游戏就更是复杂，反正就是难。在这次比赛前，我们想都没想过会用计算机编程语言来求解建模问题，而我个人比较擅长的是JAVA，把整个问题改写成算法题，貌似就不是很难了。代码大致思路是这样的：三个人从起点出发，开起三个线程，控制天气比例后用随机函数给出每天的天气，每个人都用博弈树思想来规划路径，每种天气比例重复试验一万次得出平均结果。
$ v3 m  j* p% \2 g4 h最后我热爱数学建模希望的文章对你有帮助，我们的恭祝号：语文建模。今年的比赛思路会发布到上面的网址中。码字不易希望可以一键三连。全国大学生数学建模竞赛即将开始，思路发布在这里
https://mathmodel.lanzoui.com/s/cumcm
————————————————
) ^9 Q3 x* W7 w( k4 C- o版权声明：本文为CSDN博主「蓝桉跑过海边」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
9 P7 Y5 T) Z9 [原文链接：https://blog.csdn.net/mickeywang1998/article/details/119823410
# t# w$ F) J+ T, R8 l