对动态规划的再认识

本文分两部分:第一部分,回顾规划论简史之后,讨论动态规划的最优性原理与递推公式。认为原理本身存在多方面不严密之处,并举出了反例;还证明了(定理1)当第一、第二两类最优策略集合相等时,原理与公式等价。第二部分,作者抛开上述原理与公式,另行建立嘉量原理以及与之等价的求解代数公式。它们不仅可以用来求解常义的最优策略,而且可以用来求解N阶最优策略,多目标非劣解以及其他问题,而这些是最优性原理不能概括、递推公式解决不了的。从代数的观点,作者讨论了摹方阵乘幂问题,得到了定理3。它说明可以代数地构造任意多个有效的算法求解网络上两类最优路问题;还讨论了摹多项式及其应用。本文目的是概述作者对动态规划的某些基本看法以及作者长期从事研究上述问题的基本思路与主要结果。

ON DYNAMIC PROGRAMMING

There are two parts in the article.First,after briefly reviewing the historical events of math- ematical programming,it discusses Bellman's principle of optimality and recursive formulas.It reasons that there are drawbacks in the principle shown by several counter-examples,and that the principle and formulas are equivalent if the sets of optimal policies of the first and second kinds are equal.Sec- ondly,forsaking the principle and formulas,it establishes the jar-metric principle and its equivalently algebric formula which can be used to solve,not counting ordinary optimal policy problems,optimal policy problems of the N-th order,multi-objective policy problems and others.All of them do not be included in the reach of Bellman's principle of optimality and solved by his recursive formulas.Theo- rem 3 states that in networks it can establish any number of efficient algorithms for optimum path problems of the first and second categories.Also it shows an application of modi-polynomials.The aim of this article is to show author's general view on dynamic programming and to describe his main re- search line and results in the field obtained in the last several years.