提 要： 动态规划求最优解是一个反向递推的求解过程，笔者以实例说明为依据，用正向递推的方法求解动态规划的最优值，并推出动态规划的基本方程和密尔顿-雅可比方程，是对动态规划求最优解方法的探讨。利用动态规划的正向递推方法，在应用中可以大大减少计算量，扩大了它的应用范围。
    关键词： 动态规划; 多级决策; 泛函; 最优值
   中图分类号 O221.3 文献标识码 A 文章编号 1009-1742(2004)05-0000-00

The Forward Recurrent Method of Dynamic Programming

Zhang Zhao 1,2 ， Pei Yanling 2， Zhang Renbao 1
(1.School of Electrical and Automation Engineering, TianjingUniversity, Tianjin 300072, China；2．ShandongProvincial ArchitecturalDesign & ResearchInstitute Introduction，Jinan250001, China)

    Abstract:Backward recurrent method is usually adopted in seeking optimal solution by dynamic programming. A forward recurrent method to find optimal solution by dynamic programming is presented on the basis of a instance. The fundamental equation of dynamic programming and Millton-Jacobi’s equation is also derived. It’s a exploratory study on optimal solution of dynamic programming. A amount of work is reduced in calculating by using forward recurrent method, while applied range of the method is expanded.
    Key words:dynamic programming; multi-level decision; functional equation; optimal solution

1 引言
    20世纪50年代初，美国数学家贝尔曼提出了最优性原理和动态规划方法，它和前苏联数学家庞里亚特金同期提出的最大值原理共同构成现代控制理论的重要的定理[1]，引起了控制理论的重大变革。从此、控制理论由频域法转为时域法；由经典控制理论时代进入现代控制理论时代。
    动态规划现今在许多技术领域，特别是在管理科学、运筹学、经济学等方面得到了广泛的应用，它是处理控制变量限制在一定闭集内的最优控制问题的有效的数学方法，它把复杂的控制问题变为多级决策过程的递推函数关系[2, 3]，其基础和核心是最优原理，动态规划的求解过程是一个反向递推的求解过程，很多文献中有详尽的求解过程[4, 5]，近几年，人们从各方面对动态规划的求解过程进行了探讨，取得了一定的成果[6~8]，由于求解过程是反向递推的，从终端开始，所以无论实际解决的问题是前面的多少，都要求解全部过程，这使动态规划的计算量大大增加，限制了它的应用，笔者用正向递推方法求解动态规划的最优值，并推导出哈密尔顿—雅可比方程，是对动态规划求最优解方法的探讨
2 多级决策的正向求解
   多级决策是指把一个过程按时间或空间顺序分成若干级，然后对每一级做出决策，以使整个过程取得最优结果。动态规划是解决多级决策过程优化问题的强有力的工具，传统动态规划的求解方法是从终端开始，用反向递推的办法，下面以行车问题为例，说明动态规划的正向求解过程。
    设汽车从A城出发到B城，图中需经过三条河流，它们各有两座桥P, Q 可供选择通过，如图1，各段间的行车时间(h)如图中标注，现在确定一条最优路线，使从A城到B城的行车时间最短。

图1 段间行车时间
Fig.1Running Time Between Segments

    动态规划正向求解的原则：所选择的最优路线必须保证其前部子路线是最优的。在图中，如果AQ1P2Q3B是最优路线，那么从起始点到这条路线上任一中间点的子路线必定也是最优的，否则AQ1P2Q3B就不是最优路线了。
     根据这一原则求解最优路线，从起始点开始，按时间最短为目标，逐步向后，求出起始点至各中间站的最优值，直至求出至终点的最优值。
    第一段，起点A的后一站是P1、Q1，无论汽车到终点B的路径如何，总要经过P1或Q1，到P1和Q1都只有一条路线，所以到P1的最优路线是AP1，历时3h；到Q1的最优路线是AQ1，历时4h。
    第二段，P1、Q1的后一站是P2、Q2，到P2有两条路线，从P1到P2：AP1P2，历时10h；从Q1到P2：AQ1P2，历时8h，最短历时8h。到Q2也有两条路线，从P1到Q2：AP1Q2，历时9 h；从Q1到Q2：AQ1Q2，历时12 h，最短历时9h。
    第三段，P2、Q2的后一站是P3、Q3，到P3有两条路线，从P2到P3，要想使历时最短，从A到P2一定是走路线AQ1 P2，即AQ1P2P3，历时10h；从Q2到P3，要使历时最短，从A到Q2一定走路线AP1Q2，即AP1Q2P3，历时12h，最短历时10h。到Q3也有两条路线，从P2到Q3，要想使历时最短，从A到P2一定是走路线AQ1P2，即AQ1P2Q3，历时10h；从Q2到Q3，要使历时最短，从A到Q2一定走路线AP1Q2，即AP1Q2Q3，历时12h，最短历时10h。
    第四段，P3、Q3的后一站是终点站B，到终点站B有两条路线，从P3到B，要想使历时最短，从A到P3一定是走路线AQ1P2P3，即AQ1P2P3B，历时14h；从Q3到B，要使历时最短，从A到Q3一定走路线AQ1P2Q3，即AQ1P2Q3B，历时12h，最短历时12h。
    所以最优路线是AQ1P2Q3B，最优值是12h。图2为正向递推求解的图示过程

图2 正向递推求解过程
Fig.2Recursion Solution Process in Positive Direction

图3 反向递推求解过程
Fig.3Recursion Solution Process in Reverse Direction

3 离散系统动态规划的正向递推方法
设离散系统的状态方程xk+1=f[xk,uk]k=0, 1, …, N-1
式中xk+1=x(k+1) ——n维状态矢量在(k+1)T时刻的值；
    uk=u(k)——r维控制矢量在kT时刻的值；
    f——n维矢量函数。
    状态初值x(0)=x0
    控制约束g[xk, uk]≤0
    性能泛函J=Ф[xN]+L[xk, uk]
式中Ф[xN]——对终端状态xN=x(N)的要求
寻求一个最优控制序列{u*k}(k=0, 1, …, N-1),使上述性能泛函取极值。

图4 离散系统多级决策求解
Fig.4Multistage Decision Solution to Discrete Systems

根据多级决策的正向求解的方法，N段最优决策过程中，前k段决策一定是最优决策。
    J*k(xk)=min{ J*k-1 [xk-1]+L[xk-1,uk-1]}    xk=f[xk-1,uk-1]
即：J*0(x0)= Ф[xN]
    J*1(x1)= min{ J*0 [x0]+L[x0,u0]}           x1=f[x0,u0]
    …………………………
    J*N(xN)=min{ J*N-1 [xN-1]+L[xN-1,uN-1]}    xk=f[xk-1,uk-1]
    对于一个多段决策的最优求解过程，其初始值和终端状态都是给定的，利用正向求解，很容易求出前Ｋ段的最优值。

4连续系统动态规划的正向递推方法
设连续系统的状态方程
    状态初值x(t0)=x0
    终端约束N[x(tf), tf]=0
    性能泛函J[x,t]=Ф[x(tf)]+
寻求一个最优控制u*(t)，使上述性能泛函取极值。

图5连续系统多级决策求解
Fig.5Multistage Decision Solution to Continuous Systems

这就是连续系统动态规划基本方程即贝尔曼方程

5结论
    笔者以实例说明为依据，用正向递推的方法求解动态规划的最优值，并推出动态规划的基本方程和密尔顿-雅可比方程，是对动态规划求最优解方法的探讨。利用动态规划的正向递推方法，在应用中不仅可以大大减少计算量，而且使一些很难利用反向递推求解的问题得到解决，扩大了动态规划的应用范围。在实际技术领域中，尤其对于离散的控制系统，如何充分的利用动态规划的正向递推方法，简化最优值的求解过程，解决传统动态规划方法难以解决的问题，还有待于进一步探讨。

参考文献
[1] Acquot R G. Modern Digital Control System [M]. Marcel: Dekker Inc, 1981
[2] Burghes D, Graham A. Introduction to Control, Including Optimal Control [M]. Ellis:     Horword Limited, 1980
[3] Csaki F. Modern Control Theories Nonlinear Optimal and Adaptive System [ M].     Akademial: Kiado, 1975
[4] 刘豹．现代控制理论[M]．北京：机械工业出版社，1996．5
[5] 胡寿松. 自动控制原理[M]. 北京：国防工业出版社，2000.4
[6] Sadr J, Malhame R P. Decomposition/aggregation-based dynamic programming optimization     of partially homogeneous unreliable transfer lines [J]. IEEE Transactions on Automatic     Control, 2004, 49(1): 68-81
[7] Kossmann D, Stocker K. Iterative Dynamic Programming: A New Class of Query     Optimization Algorithms [J]. ACM Transactions on Database Systems,2000,25(1): 43-82.
[8] Liu Y A, Stoller S D.Dynamic programming via static incrementalization [J].
    Higher-Order and Symbolic Computation, 2003,16(1-2): 37-62.