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

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