陈淑琪1 张瑞丰2 赵晟凯2
（1.曲阜师范大学统计学院 山东 济宁 曲阜 273100；2.曲阜师范大学数学科学学院 山东 济宁 曲阜 273100）
摘要：本文主要针对穿越沙漠游戏的最优线路进行了相关研究。利用博弈论、非线性规划和图论等分别建立各个关卡的最优线路模型，并借助线性规划算法进行迭代求解。首先在游戏规则基础上另外推理出了五条限制要求，给出了一般情况下的最优策略模型，分别提出了最短路模型与收益最多的规划模型。其次从起点到终点中途不在矿山挖矿的最优化模型，并在此基础上运用非线性规划计算了最多收益，给出最佳策略。最后分析出到矿山挖矿与不到矿山挖矿的最短路径，并在此基础上计算了最多收益，给出最佳策略，运用策论中所讲的平衡局势，反复迭代，得到对于三人而言的相对最优方案。
关键词：博弈论；非线性规划；图论；最佳策略
引言：
现有初始资金，玩家可用其购买水和食物，自起点经过不同的天气（晴朗、高温和沙暴）、地域（包括矿山、村庄和普通沙漠）最终在规定日期内到达终点，目标是最终剩余资金最多。结合游戏规则与地图，首先依据地图，分析了到矿山挖矿与不到矿山挖矿的最短路，并在此基础上计算了最多费用，给出了两人从起点出发到终点的分别的最佳策略。其次探讨三种不同条件下最优的行进策略，并分别赋予给三位玩家，然后使他们沿最优行进策略行进到对应点处。最后根据将过程反复迭代，得到对于三人而言的相对最优方案，亦即对策论中所讲的平衡局势。
1、问题分析
结合游戏规则与地图，根据游戏规定提出了限制要求，给出了一般情况下的最优策略模型，分别提出了最短路模型与收益最多的规划模型。首先对各个关键点间最短距离求解，在此基础上分别讨论了5种情况，然后对这四个问题的结果进行统筹考虑，得到最优化结合，并建立了相应的模型。并分成6种情形进行讨论，通过比较、筛选与剔除等数据处理手段。其次从起点到终点中途不在矿山挖矿的最优化模型，并得到相应的可行结果以及总花销。最后搜索了塔克拉玛干沙漠22个观测站2001-2010年沙暴发生次数统计图，得出某一天的部分时间出现沙暴，为讨论方便，记作一天。分成多种情况进行考虑，希冀可以得到最优方案。
2、模型的建立与求解
由于目标要求最终在规定时间内到达终点时尽可能拥有更多的金钱，由此可知要尽可能多在矿山停留挖矿：无论是高温、晴朗还是沙暴，都不影响在矿山挖矿，每天获益为1000元，而资源消耗最多为（10×5+10×10）×3=450元小于1000元，故最小获益为550元；况且平常行走时最大资金消耗为10×5+10×10=150元，最大获益-150元，二者相比选择在矿山停留挖矿更好。由上可知对于剩余的76kg，结合水和食物的最小计量单位均为箱，背包容量分析以下三种情况：
1.全用于买水；
2.全用于买食物；
3.既买水又买食物；
由于无论如何分配，总需要在村庄再次购买大量水和食物，否则无法走到终点；又因为在村庄买的货物是在起始点时的二倍，食物价格又是水的二倍，所以尽可能多买食物的的金额最节省。在能够规定时间内返回终点的基础上保留尽可能多的资金。“能够在规定时间内返回终点”是一个先决条件，而“保留尽可能多的资金”则是总目标。沙暴天气下不能行进只能停留，而对其它两种天气则没有这样的限制。因此，需要解决的第一个目标就是在另外两种天气下尽可能减少路上的消耗。此外还发现，村庄是补充食物和水的，而矿山是获得收益的，所以，可以设置四组目标点对分别如下：
（1）（起点，矿山）； （2）（起点，村庄）；
（3）（矿山，终点）； （4）（村庄，终点）；
（5）（村庄，矿山）；
并把目标点对构成的集合称作“核心集”，记为S，S的具体表示如下所示：S=｛(S1,S15),(S1,S12),(S12,S15),(S12,S27),(S15,S27)｝
首先目标就是要寻求他们任意两点间的最短路径，即目标为
minΩ(S1,S15),inΩ(S1,S12),inΩ(S12,S15),inΩ(S12,S27),inΩ(S15,S27)，其中Ω(Si,Sj)代表了目标点对(Si,Sj)∈S的两点间的“距离”（此距离其本质上是由一点出发，想要到达另一点时最少经过的点数（点数统计时包含终点））。此外，还考虑到，在行进过程中，必须保证食品和水始终充足，且不能超过负重上限，所以，我们可以得到两类限制条件：
（一）行进途中遇到k天沙尘暴；
（二）行进途中未遇沙尘暴。
现在就这两类条件分别予以讨论，并提出收益最多的规划模型。设在起点S的食物和水的质量分别为m2和m1，相应的箱数为x2，x1，初始资金为α。在行进过程中，遵循相应的参数设定消耗食物和水，所以，若在遇到沙尘暴k天时，不妨记之为.jpg)
。ui为0-1变量，其设定如下：
.jpg)
在每一段关键节点处取定最短路后，接下来就是要考虑是否在矿山采矿或在村庄购买食物和水，是否采取在村庄与矿山之间进行循环，以及要进行循环的次数。运用shortestpath函数通过Matlab编码分别得出：起点到村庄、起点到矿山、村庄到矿山、矿山到村庄、村庄到终点和矿山到终点的最短路径。
.jpg)
图1关键点间的最短时间图
利用Matlab内置函数shortestpath求得玩家从起点直接走到终点的距离等于玩家从起点先到村庄S39不停留，再到终点的距离；大于从起点到村庄S62不停留，再到终点的距离。因为在村庄补充水与食物的价格是起点处的两倍。故选择在起点备好恰好在走到终点的那天消耗完的水和食物。不经过矿山，经过村庄到终点或者不经过矿山和村庄，直接到终点。这三条路线均为消耗类路线，即只消耗金钱，不赚取资金。从而选择最短路径，配好物资，使得到达终点后的资金消耗最少，剩余资金最多。故这三条路线中最优路线为从起点先到村庄S62不停留，再到终点。首先从起点S1出发沿最短路线到达S30，在S30采矿直至食物和水仅够维持1天时前往村庄，再前往矿山S55，待剩余资源仅够到达终点后，立即离开此矿山，前往终点。经计算，可得在起点补充资源水223箱，食物209箱。以支撑玩家可从起点到矿山再到村庄补充资源。剩余113千克负重用于买56箱食物。共计223箱水，265箱食物。共花3765元。第10日开始挖矿，直至13日结束，共挣得收益4000元。14日到达村庄39，购买了186箱水，118箱食物，共花费4220，支撑玩家在矿山挖矿6天，且可到达村庄62补充资源。根据Matlab编程计算可知，从起点出发，中途经过两个点后即可到达终点，由于十天内没有遇到沙暴天气，于是只须考虑限制从起点到终点的时间在10日内即可。不同时经过村庄和矿山，且不在任意一块区域中停留:则在没有沙暴的情况下，最佳路径的时间总是唯一的，即第八天到达终点。但是大多数天究竟是高温还是晴朗，这是所不知道的。此外，还多了一天沙暴，于是需要首先单独取出沙暴这一天来单独考虑。设沙暴所发生的天是第λ天，当λ＞8时，则沙暴的存在不会导致中途的停留；否则，沙暴的发生，会导致玩家的停留，从而延长1天，使之成为9天，从而相较于沙暴在第八天以后发生而言，增加了1天对食物与水的消耗。但即使如此，也十分容易说明食品和水的消耗量的总和低于玩家的负重上限，并且所花资金也低于10000元。
结论:
首先采用shortestpath函数，较好地解决了多变量多限制条件下，讨论难度很大的问题。其次引入0-1-∞变量进行随机考虑，扩大了适用领域、增大了真实性，求解各关问题时采用试触法，依据限制缩小讨论范围，极大简化了运算过程。确定较少沙暴等概率范围时，通过研究典型的塔克拉玛干沙漠来确定概率，具有较好的科学行和可行性。最后从起点到终点中途不在矿山挖矿的最优化模型，并在此基础上运用非线性规划计算了最多收益，给出最佳策略。
参考文献：
[1]刁在筠，刘桂真，戎晓霞，王光辉. 运筹学[M]. 北京：高等教育出版社，2016.7：84-87，210-213.
[2]胡运权，郭耀煌. 运筹学教程[M]. 5版. 北京：清华大学出版社，2018:11-14,170-181.
[3]宋甫.塔里木盆地地面风场与FNL风要素的误差分析[D].南京：南京信息工程大学.2013:43.