基于线性规划模型的沙漠穿越问题研究

曾俊博 孙基元 黎淳丞 黄宇杰 林庆彬

【摘  要】本文主要针对以最优路径穿越沙漠游戏的研究，利用优化算法，建立数学模型来分析最大效益，从而得到最大资金的最优路径。首先将第一关所给地图转化为图论中的无向图，我们用离散数学中的图论，建立一个最优路径模型，通过考虑各类基本情况，然后在对最优路径模型改进的基础上加入考虑食物与水资源问题，是否进行补给，补给几次，挖矿多久进行分析。其次对模型进行合理的理论计算及推导，然后借助于matlab矩阵运算，穷举算法，对所提供的数据进行计算，最后我们需要在模型上进行修改，建立一个模型，最终得到结果。

【关键词】最优路径;图论;matlab矩阵运算;穷举算法

引言

该题是一个穿越游戏问题，初始情况下官方会给予一定的资金，可以用这笔资金进行购买路上所需要的水和食物。该游戏总共有六关，每次会给予一张地图，玩家凭借地图，从起点出发，穿越沙漠到达终点，在路上有村庄和矿山可以进行补给和赚取资金。游戏以天为基本、时间为单位，游戏开始时时间玩家在起点处，且当天时间为第0天，玩家须在截止日期或之前到达终点，到达终点后游戏结束。食物和水的最小计量单位为箱。由于存在负重上限，所以每天玩家所携带的水和质量不能超过这个上限，在穿越过程中，如果玩家的水和食物都消耗完了，则该玩家游戏失败。每天的天气为“晴朗”、“高温”、“沙暴”三种状况之一，沙漠中所有区域的天气相同。玩家每天可选择从地图中的一个区域到达与之相邻的另一个区域，也可以选择在原地停留。

1.问题分析

在已知所有天气情况下，给出最优策略，这属于最优路径问题，首先我们应考虑到物资及资金，然后再考虑到物资及资金还有挖矿的天数配置，从而考虑如何节省资金且的情况下到达矿山，再从矿山回到起点。在于使到达终点时的资金最大化，难点在于在起点所携带食物与水的计算和在矿山中所待天数的多少以及前往村庄的补给。我们对所给数据进行图论分析，利用穷举算法算出各类前往村庄和矿山的路径如何消耗最少，在矿山进行挖矿几次后再进行分析，比较哪次所积攒资金最多，最后得到结果。

2.模型建立与求解

在已知天气的情况下进行求解玩家的最佳策略，可得之天气每天的情况与第一关第二关的地图，利用图论将其地图转化为无向图。

要求一般情况下玩家的最优策略，在所给数据中水的资源数量为每箱5千克，食物为每箱2千克，但是不同的天气下食物和水的消耗量不同，在晴天时，水消耗5千克，食物消耗7千克，在高温天气情况下，水消耗为8千克，食物为6千克，在沙暴天气下，食物和水的消耗都为10千克。由于在沙暴天气下不可以行走，所以我们选择在沙暴天气下停留。我们希望建立一个可以包含路程所需天数，水资源的购买消耗情况，食物的购买消耗情况的数学模型。从起点直接前往终点路上的最优路径为，经过计算，前往该终点所用时间t为3天，且已知三天内的天气状况为高温，高温，晴朗，经过计算，这三天所消耗的资金损耗求得S=295剩余资金为求得剩余资金W为9705，在矿山中挖矿所获得的收益为1000元，前往村庄最短时间8天，在矿山挖矿的时间为7天，在矿山停留1天度过沙暴，已知这8天中4天为高温，1天晴朗，3天沙暴。挖矿时的收益以及亏损比较挖矿一天的收益与最大挖矿遭遇的沙暴天气最大消耗进行比较假设在沙暴天气，为了使剩余的资金最大化，我们需要在矿山中停留挖矿的时间尽可能长，从而补充之前所亏损的，由此建立一个数学模型来探讨最优路径以及挖矿的时间。由于玩家所携带的负重上限為1200千克，而水的质量为每箱3千克，食物的质量为每箱2千克。在模型中，我们应该考虑是否在起点处购买所携带的水和物资是否支撑到矿山以及在矿山中挖矿时所消耗的食物与水。经过计算获得，在起点处应携带540千克的水和660千克的食物由于携带物资的上限，加上又要在矿山中进行挖矿所需要的食物以及水在规定30天内到达终点，所以还有此约束条件。                                                                                                                                 由于考虑在起点处与村庄处所购买的食物和水不可以在途中消耗完，不然视为游戏失败，故还需要一个约束条件。

其中xi是x的列向量，yi是y的列向量。单纯形法是单纯形法是求解线性规划问题最常用、最有效的算法之一。第二关附件中已知30天的所有情况，在负重上限为1200千克的情况下，购买能够尽可能挖矿的资源。然后去求解最优策略，第二关所使用的模型与第一关相同，由模型一可得所以第二关的最优路径是：