基于数学规划模型的“穿越沙漠”路线最优策略的研究

基于数学规划模型的“穿越沙漠”路线最优策略 的研究

刘子凯 曾秋云 樊雨童 张瀚 陈晔

湖南文理学院 常德 415000

【摘要】本文主要针对“穿越沙漠”游戏在规定条件下，对数学规划模型的建立进行了相关研究。通过MATLAB求解分析得到最优路线，通过结合分析在食物、水物资、天气、采矿收益、路线、补给日期的选择等多种条件相互约束下，利用0-1规划、线性规划建立在规定时间内最大收益的最优策略的数学规划模型。

【关键词】0-1规划，线性规划，最优路线

基金：湖南文理学院2020年大学生创新性试验计划一般资助项目，项目编号：YB2005；

根据该游戏规则，玩家拥有一张沙漠地图、10000元的初始资金。资金可以在起点和村庄购买所需数量的水和食物，玩家拥有水和食物的重量不能超过玩家负重上限。玩家在每天根据天气、活动的情况不同，所消耗的物资不同。玩家在矿山可以选择挖矿赚取基础资金。若在到达终点之前食物或水资源耗尽，则游戏失败。在天气已知的情况下，玩家从起点出发，须在规定时间内到达终点，并保留尽可能多的资金。

1、问题分析

游戏规定：可能有三种天气情况—晴朗、高温、沙暴，且每天的天气状况已知，若遇沙暴天气，则必须原地休息或挖矿。从第0天开始，须在30天内到达终点，且每次行动只能从所在区域前往相邻区域或者在原地停留。村庄的水和食物的价格为起点的2倍，玩家在原地停留一天消耗的资源数量称为基础消耗量，行走一天消耗的资源数量为基础消耗量的2倍，挖矿一天消耗的资源数量为基础消耗量的3倍。

2.1、模型的建立与求解

首先结合游戏规则以及地图进行分析，发现两种相对较优的可行策略。一是直接从起点到最终点，不进行采矿工作，力求行走过程中花费最少；二是从起点到矿场进行采矿获取资金，再回到终点，力求获取的资金尽可能多。针对第一种策略，找到了一条最优路线。针对第二种策略，利用0-1规划和线性规划建立模型，求得了一条最优路线。比较两种策略下，回到终点剩余的总费用，最终决定采用哪种策略。

针对第一种策略：

利用MATLAB软件求解起点到终点的最短路径，即1—25—26—27。由于在整个游戏时段内每天天气状况事先全部已知，因此可以直观计算出来每天所需的水和食物量，则可求得花费的资金。故最终剩余资金为：（ 表示最终剩余资金， 表示第 天水的消耗箱数， 表示第 天食物的消耗箱数。）

针对第二种策略：

首先利用MATLAB软件求出起点到矿山、矿山到终点的最短路径，经过计算发现，从起点到矿山最少耗时10天，从矿山到终点最少耗时5天。为使获取的资金尽可能多，则需要玩家在第11天到第25天在矿山挖矿的天数尽可能多。我们将其分为三段：起点到矿山、矿山策略、矿山到终点。

起点到矿山：利用MATLAB软件计算求得，从起点到矿山至少需要10天（中间两天沙暴天气在原地停留休息），最优路线为：1—25—26—23—23（停留）—22—9—15—15（停留）—14—12。

结合天气、食物和水的消耗等条件，利用MATLAB软件计算求得，从起点到村庄需98箱水、98箱食物，因食物的补给价格较昂贵且村庄物资补给价格为起点物资补给价格的两倍，则在起点处尽可能的多带食物，而所带水的数量为98箱，即从起点到村庄的消耗量。又因最大负重为1200kg，故初始阶段背包内所背负的物资分别为食物452箱、水98箱。从起点到村庄，在村庄补给下一段路程的消耗，即补充水164箱，再出发到矿山，这段路程的水、食物消耗量为确定的值。利用MATLAB软件计算求得：在这期间消耗了食物122箱，消耗水130箱，补充水164箱，第十天的剩余食物量为330箱，水的剩余量为132箱。此时，资金剩余3350元。

矿山策略：为使最终资金尽可能多，则需要挖矿的天数尽可能多。由于从矿山回到终点至少需要5天，则将第11天至第25天划分为第二阶段的耗时天数。

第11天开始挖矿，因第17、18天为沙暴天气，只能挖矿或停留休息，经过分析发现，若从第11天一直挖矿到第17天，则物资不足以支撑到第17天并返回村庄补给食物，故需要在沙暴天气停工休息并及时返回村庄补给食物。又因为从矿山返回村庄再返回矿山至少需要行走4天，由于中间有两天沙暴天气，因此至少需要耗费6天时间。 补给物资的花费为：

矿场到终点：利用MATLAB软件计算求得，从矿山返回起点至少需要五天时间，最优路线为：13---15---9---21---27。要保留尽可能多的资金，则挖矿天数应尽可能多，故第26天开始从矿山经过村庄到达终点并在村庄进行一次补给，以求能顺利到达终点，又因为在终点水和食物的换算价格为起点的一半，故使最终物资剩余量尽可能为0。

结合上述分析，通过0-1规划和线性规划，建立如下数学规划模型：

利用lingo软件编程求得最终剩余资金为10230元。求得最优路线为：1--25--26--23--23（停留）--22--9--15--15（停留）--13--12--12（挖矿）--12（挖矿）--12（挖矿）--13--15--13--13（停留）--13（停留）--12---12（挖矿）--12（挖矿）--12（挖矿）--12（挖矿）--12（挖矿）--12（挖矿）--13--15--9--21--27路线图如下（图1）：

图1 最终路线

3、总结

该模型解决了天气情况已知条件下，在规定时间内获得最大收益的最优策略的问题。在天气未知的情况下需要建立仿真模拟程序，模拟多组可能出现的天气情况，使用该模型求解各种情况的最优策略，通过对所有情况的求解结果分析，以保证结果的可靠性。

参考文献

1. 冯凯,吉星,杨昕.A*算法在自动驾驶车辆路径规划中的应用[J].汽车实用技术,2020,45(22):25-28.

2. 陈道蓄.最短路径问题[J].中国信息技术教育,2020(Z3):18-22.

3. 董飞.基于0-1规划模型旅游团路线的设计[J].时代金融,2020(05):144-145.

4. 刘建军,司光亚,王艳正,何大川.基于模型的多目标优化问题方法研究[J].系统仿真学报,2020,32(11):2138-2145.