摘 要：单目标线性规划模型是在一组线性条件约束下，寻求某一单一目标的最优值，适用于极值问题的求解。弗洛伊德算法是一种通过动态规划的思想寻找给定的加权图中多源点间最短路径的算法。文章建立了基于背包问题的单目标线性规划模型，给出了在只有一名玩家，且事先已知游戏阶段天气状况下玩家的最优策略。通过弗洛伊德算法求解出了相应节点间的最短路径，得到了玩家的最终剩余资金。
关键词：单目标线性规划；弗洛伊德算法；最优策略
DOI:10.19850/j.cnki.2096-4706.2023.01.034
中图分类号：TP391 文献标识码：A 文章编号：2096-4706（2023）01-0127-05
Research on Desert Crossing Strategy Based on Single Objective Linear Programming
YANG Chengjing, SHEN Weihong, GUO Xiaomin
(Yancheng Institute of Technology, Yancheng 224051, China)
Abstract: The single objective linear programming model seeks the optimal value of a single objective under a set of linear condition constraints and is suitable for solving extreme value problems. Freudian algorithm is an algorithm to find the shortest path among multiple source nodes in a given weighted graph based on dynamic programming idea. In this paper, a single objective linear programming model based on the knapsack problem is established, and the optimal strategy is given under the condition of only one player and the weather in the game stage is known in advance. The shortest path among corresponding nodes is solved by Freudian algorithm, and the final remaining funds of players are obtained.
Keywords: single objective linear programming; Floyd algorithm; optimal strategy
参考文献：
[1] 石兆 . 物流配送选址—运输路径优化问题研究 [D]. 长沙：中南大学，2014.
[2] 李炯城，鲍江宏 . 基于图论求解多选择背包问题 [J]. 计算机工程与设计，2009，30（13）：3144-3147.
[3] 贺军忠 . 最短路径问题 Floyd 算法的改进 [J]. 兰州文理学院学报：自然科学版，2019，33（5）：27-30.
[4] 卢立果，刘立越，鲁铁定，等 . 一种改进的 Floyd 算法 [J].东华理工大学学报：自然科学版，2019，42（1）：78-81.
[5] 林浩楠 . 基于多目标遗传算法和深度学习的投资分配模型研究与应用 [D]. 广州：华南理工大学，2017.
[6] 高兰芳 . 基于线性规划的工程投资分配模型及优化 [J]. 四川轻化工大学学报：自然科学版，2020，33（1）：74-81.
作者简介：杨诚靖（2001.12—），男，汉族，江苏扬州人，本科在读，研究方向：管理科学与工程；沈炜宏（2001.03—），男，汉族，江苏常州人，本科在读，研究方向：管理科学与工程；郭小敏（2001.07—），女，汉族，安徽阜阳人，本科在读，研究方向：金融工程。