孙鹏飞，刘建永

(解放军理工大学 野战工程学院，南京　210007)



启发式伏格尔法求解多阶段决策问题

孙鹏飞，刘建永

(解放军理工大学 野战工程学院，南京210007)

摘要：针对动态规划求解多阶段决策问题存在的一些不足，首次创新性地将启发式伏格尔法运用到求解多阶段决策问题中，给出相关定义，列出其算法步骤，并分析其时间复杂度；通过案例具体说明启发式伏格尔法求解过程，总结该算法优缺点，为研究多阶段决策问题提供一种新型并且具有实效的思路方法。

关键词：启发式伏格尔法；时间复杂度；多阶段决策问题

Citation format:SUN Peng-fei，LIU Jian-yong.Heuristic Vogel Method for Solving Multistage Decision-Making Problems [J].Journal of Ordnance Equipment Engineering,2016(3):171-174.

求解多阶段决策问题(Multistage Decision-Making Problems)，最常用的求解方法是动态规划(Dynamic Programming)方法[1-2]。实践也证明了求解此类问题用动态规划方法比线性规划方法或非线性规划方法更加有效[3-4]。但利用动态规划求解多阶段决策问题，存在着一些条件限制，算法复杂度也较大，并且只适用维数相对较低的问题[5-6]。现实中，在考虑决策灵活机动和方案最优时，并不一定要严格采用最优方案，有时决策容易、易于改动的次优方案可能更适合现实需求。本文中考虑是否有较好的启发式算法(Heuristic Algorithm)[7]，在解决此类问题时更加地灵活机动、易于操作。

查阅国内外文献资料[8-10]，伏格尔法(Vogel)主要应用于求解运输问题和指派问题，目前还未有关于伏格尔法在求解多阶段决策问题方面的相关研究。本文探索利用启发式伏格尔法(Heuristic Vogel Method，HVM)求解多阶段决策问题，并分析其时间复杂度。

1基于启发式伏格尔法求解最短路线问题