基于线性规划的沙漠生存游戏探究.pdf

2023年6 月第8 卷2 期西安交通工程学院学术研究Academic Research of Xian Traffic Engineering InstituteJun.2023Vol.8No.2基于线性规划的沙漠生存游戏探究张钰婷（西安交通工程学院陕西西安7 10 30 0)摘要：在沙漠生存游戏中，要求玩家凭借一张地图和初始资金10 0 0 0 元，在食物不耗尽的情况下，在30 天内到达终点并且保留尽可能多的资金。在不同关卡中，天气、行走区域、玩家人数等均是变化的，本文针对不同情况给出玩家最佳策略。建立线性规划模型并求解，可给出玩家在前两关中的生存策略。在第一关中，玩家第8 天在村庄第一次补给，第10 天到达矿区，第2 2 天到达村庄进行第二次补给，整个过程一共挖矿7 天，在第2 3天到达终点，保留资金为10 430 元。第二关中第9天到达矿山，第一次共挖矿5天。第15天返回到村庄，第16 天到达矿山，第二次挖矿共9 天。第2 6 号到达村庄再次进行补给，第2 9天到达终点，且保留资金为1346 5元。若玩家仅知道当天的天气状况，根据所给的限定条件，给出第三关的策略。即玩家不经过矿区，直接走到终点时消耗最小，用时最短，且计算得到保留资金最多，是96 7 0 元。关键词：线性规划；最短路径；最优方案中国分类号：0 12 1.8;G558文献标识码：AResearch on Desert Survival Game Based on Linear ProgrammingZHANG Yuting(Xian Traffic Engineering Institute,Xian Shaanxi 710300,China)Abstract:In the desert survival game,players are required to arrive at the destination within 30 days with a map and an initial capitalof 10,oo0 yuan,without running out of food,and to keep as much money as possible.In the different levels,the weather,walkingarea,the number of players are changing,this paper gives the best strategy for different situations players.The linear programming model is established and solved,which can give the players survival strategy in the first two levels.In thefirst level,the player makes his first supply in the village on the 8th day,arrives at the mining area on the 1oth day,arrives at thevillage on the 22nd day to make his second supply.The whole process takes a total of 7 days of mining,and reaches the destinationon the 23rd day,the reserved fund is 10,430 yuan.The second pass arrived at the mine on the 9th day,the first total mining 5 days.Return to the village 15 days,16 days arrived at the mine,the second mining a total of 9 days.The 26th arrived at the village again tosupply,the 29th day arrived at the end of the fund is 13465 Yuan.If players only know the weather conditions of the day,according to the given conditions,given the third stage of the strategy.Thatis,the player does not go through the mining area,directly to the end of the minimum consumption,the shortest time,and thecalculation to get the most reserves,is 9670 yuan.Keywords:Linear programming;Shortest path;Optimal solution引言本文研究背景是沙漠中的生存问题，玩家用初始资金自行购买一定数量的食物和水，从起点出发在沙漠中行走。途中会遇到不同的天气，也可在矿，山、村庄补充资金或资源，目标是在规定时间30天内到达终点，并保留尽可能多的资金。其中要考虑的主要影响因素有三个。首先是必需品水和食物的购买和携带，起点处水每箱3千克，单价是5元，食物每箱2 千克，单价是10 元，玩家可以用初始资金购买水和食物，但每天的负重上限是12 0 0 千克，且玩家在行走时所消耗的水和食物的量是原地停留时的2 倍。其次是天气的影响，作者简介：张钰婷（1991-），女，讲师，硕士，数学学科教学。沙漠中的天气有晴朗、高温或者沙尘暴三种情况，沙尘暴必须在原地停留，不能行进到下一个区域，但若在矿区可以挖矿。最后是途径区域的影响，经过村庄时可补充水和食物，但价格是出发时的两倍，在矿区停留时，可通过挖矿获得资金，但资源的消耗原地停留时的3倍。在诸多条件下，目标是在30天内到达终点，并留有尽可能多的资金。1每天天气、地域已知（第一关)1.1 问题分析玩家初始资金10 0 0 0 元，玩家在30 天内到达终点，并留有尽可能多的资金。玩家的路径受到物18基于线性规划的沙漠生存游戏探究资负重上限12 0 0 kg等诸多因素的影响。在这一关，30 天中有15天是高温，9天是晴朗，6 天是沙尘暴。我们将到达终点时玩家保留的资金作为目标函数，建立模型给出最优方案。为了方便表示，我们将公式中出现的符号说明如表1。表1符号说明符号符号含义a第一问中，在起点购买水的箱数b在起点购买食物的箱数al第一次补给水的箱数b第一次补给食物的箱数a2第二次补给水的箱数b2第二次补给食物的箱数第一次采矿的天数2第二次采矿的天数1.2模型建立与求解玩家要在规定时间内到达终点，且需要留有尽可能多的资金。我们将资金的数目作为目标函数，结合已有的信息给出约束条件，建立如下的线性规划模型：MaxZ=10000-5a-10b-10a,-20b-10az-20b,+1000(v+v2)3a+2b1200a,b06a,+2b,+3a+2(b+b,)-1140 1200S.t.aj,b,a2,b,00V70V2 3利用LINGO软件计算出最优解，如下：a=180,b=330,i=7,a=153a2=b,=b,=V2=0 玩家从起点出发，经过十天到达矿山，途中在第八天去到村庄进行第一次补给；于第十一天开始挖矿，至第十七天结束，第一次共挖矿七天；第十八天在矿山停留一天，不挖矿；再经过两天于第二十天到达村庄进行第二次补给，最后经过三天于第二十三天到达终点。具体路线如图1：19起点图1第一关路线图在如上图所示的情况下，玩家的行走区域编号顺序为：1-2 5-2 4-2 3-2 2-9-15-13-12-13-12-13-15-9-21-27。玩家要按要求走到终点，其在整个过程中的所在区域、剩余资源和资金消耗详细情况如表2：表2 第一关方案日期所在区域剩余资金剩余水量0112522432342352269798159131012111212121313141215121612171218121913201521922212327利用计算结果可以得出，玩家按照表2 给出的方案行走，是符合条件的最优方案，从起点出发，历时2 3天可以到达终点，其中在途径村庄时，补充了一次水，食物未额外补充，到终点时剩余的资金为10 430 元。2天气、区域变化（第二关)2.1问题分析第二关中，首先是天气情况有所变化，和第一关相比，高温天气减少1天，沙尘暴天气增加1天。25242367228910村庄1516111314矿山1258001805800164580014858001385800128580011858001025800924170245417022941702135170183617015971701448170120917096101707211170421117032111701610430361043026104301610430026终点272120191718剩余实物量330318306292282268256246232220208178160139121103855545334026120基于线性规划的沙漠生存游戏探究其实玩家会拿到新的地图，其途径的区域也会有较大改变。在这一关中目标函数不变，依旧将资金的数目作为目标函数，约束条件会根据天气和地区的不同而产生变化，建立如下的线性规划模型并求解。2.2模型建立与求解利用第二关数据和给定条件，把目标函数和约束条件联系起来，可以建立线性规划模型：MaxZ=10000-5a-10b-10a,-20b,-10az-20b,+1000(vi+v2)3a+2b1200a,b 0a,+2b,+3a+2b 1199 1200S.t.6a,+3a+2(b,+b,)-2378 1200ar,br,a2,b,00V/50V29利用LINGO软件计算出最优解，如下：a=247,b=229,a,=223,b,=217,Vi=5,V2=9,a2=b,=0从起点出发历时九天到达矿山，于第十天开始挖矿，至第十四天结束，第一次共挖矿5天。第十五天到达村庄，第十六天到达矿山，于第十七天开始挖矿，至第二十五天结束，第二次挖矿共九天。第二十六号到达村庄进行补给（适当补给，足以到达终点即可，可能减少不必要的消耗），最后经过三天于第二十九天到达终点。具体路线如图2：起点1910111718192025262728293334353637384142434445464748495051525354矿山55565758596061村庄63终点6264图2 第二关路线图在新地图中，玩家的行走区域编号顺序为：1-2-3-4-5-13-22-30-39-30-39-47-56-64。玩家要按要求走到终点，其在整个过程中的所在区域、剩余资源和资金消耗详细情况如表3：表3第二关方案日期所在区域剩余资金剩余水量011223344551361372283093010301130123013301430153016301730183019302030213022302330243025302639274728564671415162324313240剩余食物量6475247647523164752156475205647519564751856475169647515964751496475133747510984757994755510475401147516446523944652235465193646516374651458465127946510610465851146567124654613465161346536134652613465162964玩家若按上图给出的方案前进，既能在规定时间到达终点，又可使玩家所剩资金尽可能的多。玩家从起点出发，历时2 9天可以到达终点，其中在途径村庄时，补充了一次水和食物，在矿区挖矿共14天，到终点时剩余的资金为1346 5元。3仅知道当天天气（第三关）3.1 问题分析玩家仅知道当天的天气状况，但已知10 天内不会出现沙尘暴。根据限定条件，天气情况有所变化，地图也已经改变。这一关中，如图3所示。22921720519118116715514513111910171533214231219189159141123102816342124026121346500204总结基于线性规划的沙漠生存游戏探究点时所剩余的资金数目为96 7 0 元。108矿山9324起点1玩家只知道当天的天气，后续的天气可以进行合理的假设。这也就使得这一关可能出现的情况会很多。在天气变化较多的情况下，要将这个问题的分析求解程序化，难度还比较大。故本文用列举法，分情况讨论玩家的行走路径，通过对比给出最优方案。3.2模型建立与求解第一种情况：若当天是晴天，后续两天刚好也是晴天。玩家不经过矿区，以最短路径1-5-6-13到达终点。这个过程共消耗18 箱水，2 4箱食物，资金消耗最低，共花费330 元，初始资金还剩余96 7 0元，如表4所示：表4情况一区域号码5消耗水/箱6消耗食物/箱8消耗水钱/元30消耗食物/元80总花费/元330元第二种情况：在理想化的假设下，未来10 天均是晴朗的天气。玩家要经过矿山挖矿，这个过程中需要消耗水9 9 箱，食物10 0 箱，共花费137 5元。第三种情况：假设这10 天均为高温天气，玩家的资源消耗则更大，为晴朗时的资源消耗的3倍。计算上述三种情况的总花费，列表如下表5：表5费用对比情况一总花费/元330若玩家只知道当天天气，然后对后续的天气进行理想化的假设，若要按规定到达终点，第一种情况用时最短，花费的资金最少。综上分析，给出的方案是玩家不经过矿区，途径区域1-5-6-13，利用最短路径到达终点，到达终1112756图3第三关地图6683080二1375终点13本文是依托于沙漠生存游戏这个背景，探讨了在区域、天气和资源等诸多限制条件下玩家的行进策略问题，结合线性规划模型给出符合要求的最优方案。在本文研究过程中，未涉及玩家的主观性，只讨论客观因素。所考虑的因素都是独立的，可控的，采用的数据也是较为理想状态下的数据。但在类似的场景中，比如旅行者徒步穿越秦林、驴友西藏骑行等实例中，在考虑主观能动性的前提下，要分析的客观因素会更多，更复杂。在本文的基础上，将模型如何优化，以便其有更强的推广性，这是作者后续需要花更多时间去探讨和研究的有趣问题。参考文献1司守奎,孙兆亮.数学建模算法与应用 M.北京:国防工业出版社,2 0 2 0.2林军,陈翰林.数学建模教程 M.北京:科学出版社,2 0 11.3赵树螈.微积分(第五版)M.北京：中国人民大学出版社,2 0 2 1.4曹建莉,程涛,肖留超.数学建模与数学实验 M.西安:西安电子科技大学出版社,2 0 18.5肖华勇.大学生数学建模竞赛指南 M.北京：电子工业出版13社,2 0 2 0.66姜启源,谢金星,叶俊.数学模型(第五版)M.北京:高等教育出版社,2 0 2 2.87韩中庚.数学建模竞赛：获奖论文精选与点评 M.北京：科30学出版社,2 0 18.808韩明,张积林,李林,等.数学建模案例 M.上海:同济大学出版社,2 0 18.9薛定宇,陈阳泉.高等应用数学问题的MATLAB求解 M北京：清华大学出版社,2 0 2 1.10桑杨阳,朱万红,但兵兵.非线性规划建模与LINGO软件的编程应用 .计算机工程应用技术,2 0 12,8(10):2 419-2 42 2.11李佩红.作家们穿越塔克拉玛干 .地火.2 0 19,2 2(1):10 8.12郭伟.数学建模思想方法及其问题研究 M.长春：吉林大学出版社,2 0 17.13承小华.例谈线性规划的常见题型及其解法 .语数外学习,2 0 2 1,(0 3):45.三14徐晓辉.数学建模应用中整数线性规划问题的常用解法初探 J.现代职业教育,2 0 2 1,(0 7):17 8-17 9337515孙梦娇.数学建模优化经济题型的思路及策略分析 1.才智,2 0 2 0,(11)18 2.16张瑜,李长友.基于数学软件工具下的案例分析 .南方农机,2 0 18,49(2 2):2 30.17陈华,刘妍.概率论思想在高等数学解题中的应用 .高教学刊,2 0 2 0(2 0):7 0-7 3.21