Abstract: The National Mathematical Modeling Competition for College Students, which began on September 10, 2020, has three questions for the undergraduate group: A, B, and C, which are furnace temperature curve, crossing desert, and credit decision-making for small and medium-sized enterprises. The number of teams participating in the national competition for topic selection is 8722 for question A, 8888 for question B, and 19619 for question C; the distribution of submission teams for question A is 8344, question B is 8398, and question C is 18500; the total number of teams choosing questions A and B is much smaller than that choosing question C. This indicates that in the judgment of the contestants, most of them believe that problems A and B are relatively difficult to solve, and the most important and difficult thing is the establishment of the corresponding mathematical model. Especially for problem B, how to accurately represent the constraints of reality with the expression of the model is a very difficult innovative process in model construction. However, in the authoritative commentary of this competition, only the modeling direction of some constraints was briefly suggested, and the specific expression construction of each realistic constraint model was not given, which is sufficient to illustrate the difficulty of modeling this problem. This article explores the game of crossing the desert, where players use a map and initial funds to purchase a certain amount of water and food (including food and other daily necessities), starting from the starting point and walking in the desert. On their way, different weather conditions may be encountered, and the optimal decision problem is to supplement funds or resources separately in mines and villages, reach the destination within the specified time, and maintain as many funds as possible.
   Take whether the player reaches (or is in) a j region on an i day as the decision variable, and take the initial capital, load limit, resources consumption, and daily movement of the player between adjacent regions in the map as the constraint conditions, to reach the end within the specified time, and maximize the remaining capital at the end of the destination as the goal. A constrained nonlinear integer programming model for optimal strategy selection of players crossing the desert is established. The constraint expression that the player can only reach one area and move between adjacent areas is given before reaching the end point. With symbol function, argmax function and absolute value, a unified expression of water and food resources consumption is constructed under two different choices of staying and walking when players arrive at non-mining areas and three different choices of staying, mining and walking when players arrive at mines. The objective function containing the expression structure of mining income is established. The decision problem of the optimal strategy selection for crossing the desert under the condition of known weather conditions is studied.
   By solving the corresponding model, it is obtained that the optimal strategy for the player in the first level of the desert is to reach the destination on the 23rd day, mine in the mine for 8 days and rest for one day to obtain the maximum remaining capital of 10,430 yuan. The optimal strategy for the player in the second level of the desert is to reach the destination on the 29th day and mine in the mine for 14 days to obtain the maximum remaining capital of 12,345 yuan. And the general ideas and methods for modeling the optimal strategy selection for crossing the desert when the weather conditions are known are given.

Key words: graph, adjacency matrix, 0-1 variable, nonlinear integer programming

摘要： 以玩家第i天是否到达(或在)第j个区域等为决策变量,以初始资金、负重上限、资源消耗、玩家每天在地图中的相邻区域间移动等为约束条件,在规定时间内到达终点,并以到达终点时剩余资金最大化为目标,建立了玩家穿越沙漠的优化策略选择的带约束的非线性整数规划模型。构建了玩家在到达终点前每天在相邻区域间移动和在矿山停留、行走及挖矿不同选择的资源消耗的表达式等约束条件,以及包含挖矿收益项的表达结构的目标函数;研究了在天气状况已知条件下穿越沙漠最优策略选择的决策问题。通过对相应模型求解得玩家在沙漠第一关的最优策略是第23天到达终点,在矿山挖矿8天休息一天获得最大剩余资金10430元,玩家在沙漠第二关的最优策略是第29天到达终点,在矿山挖矿14天获得最大剩余资金12345元。并给出了在天气状况已知时穿越沙漠的最优策略选择的一般建模的思路和方法。

关键词: 图, 邻接矩阵, 0-1变量, 非线性整数规划