按照(3),(4)逆向计算出f1(x1),为全过程的最优值。记状态x的最优决策为 (x),由x和u(x)按照状态转移方程计算出最优状态,记作x。并得到相应的 最优决策,记作u(x)。于是最优策略为{u1(x1),2(x2),…,un(xn)}。 算法程序的框图如图2所示。 图的左边部分是函数序列的递推计算,可输出全过程最优值f1(x1),如果需要还 以输出后部子过程最优值函数序列f(x)和最优决策序列u4(x6)。计算过程中存 ∫(x后)是备计算∫1之用,在∫-1算完后可用∫1将∫替换掉;存l(xk)是备右边 部分读4(x)之用。 图的右边部分是最优状态和最优决策序列的正向计算,可输出最优策略 {a1(x1),u2(x2)…,un(xn)}和最优轨线{x1,x2,…,xn} §4动态规划与静态规划的关系 动态规划与静态规划(线性和非线性规划等)研究的对象本质上都是在若干约束条 件下的函数极值问题。两种规划在很多情况下原则上可以相互转换 动态规划可以看作求决策412…,Ln使指标函数Vn(x1,u1,l2…,n)达到最优 (最大或最小)的极值问题,状态转移方程、端点条件以及允许状态集、允许决策集等 是约束条件,原则上可以用非线性规划方法求解 些静态规划只要适当引入阶段变量、状态、决策等就可以用动态规划方法求解 下面用例子说明。 例4用动态规划解下列非线性规划 max∑g(ul) ll=a,lk≥ 其中gA(4)为任意的已知函数。 解按变量u的序号划分阶段,看作n段决策过程。设状态为x1 问题中的变量u13u2,…,ln为决策。状态转移方程为 x1=a,xk+1=xk-l42k=1,2,…,n 取gA(uk)为阶段指标,最优值函数的基本方程为(注意到xn1=0) f (x = max [g, (xk)+fk(kd] 0≤xk≤a,k=n,n-1…2l; fn+1(0)=0. 按照逆序解法求出对应于x每个取值的最优决策u(x),计算至f(a)后即可利 用状态转移方程得到最优状态序列{x}和最优决策序列{4(x)} 与静态规划相比,动态规划的优越性在于: (ⅱ)能够得到全局最优解。由于约束条件确定的约束集合往往很复杂,即使指标 函数较简单,用非线性规划方法也很难求出全局最优解。而动态规划方法把全过程化为-61- 按照（3），（4）逆向计算出 ( ) * 1 1 f x ，为全过程的最优值。记状态 ki x 的最优决策为 ( ) * ki ki u x ，由 * 1 x 和 ( ) * ki ki u x 按照状态转移方程计算出最优状态，记作 * k x 。并得到相应的 最优决策，记作 ( ) * * k k u x 。于是最优策略为{ ( ), ( ), , ( )} * * * 2 * 2 * 1 * 1 n n u x u x L u x 。 算法程序的框图如图 2 所示。 图的左边部分是函数序列的递推计算，可输出全过程最优值 ( ) * 1 1 f x ，如果需要还 可以输出后部子过程最优值函数序列 ( ) k ki f x 和最优决策序列 ( ) * k ki u x 。计算过程中存 ( ) k ki f x 是备计算 k −1 f 之用，在 k −1 f 算完后可用 k −1 f 将 k f 替换掉；存 ( ) * k ki u x 是备右边 部分读 ( ) * * k k u x 之用。 图的右边部分是最优状态和最优决策序列的正向计算，可输出最优策略 { ( ), ( ), , ( )} * * * 2 * 2 * 1 * 1 n n u x u x L u x 和最优轨线{ , , , } * * 2 * 1 n x x L x 。 §4 动态规划与静态规划的关系 动态规划与静态规划（线性和非线性规划等）研究的对象本质上都是在若干约束条 件下的函数极值问题。两种规划在很多情况下原则上可以相互转换。 动态规划可以看作求决策u u un , , , 1 2 L 使指标函数 ( , , , ) 1n 1 u1 u2 un V x ， L 达到最优 （最大或最小）的极值问题，状态转移方程、端点条件以及允许状态集、允许决策集等 是约束条件，原则上可以用非线性规划方法求解。 一些静态规划只要适当引入阶段变量、状态、决策等就可以用动态规划方法求解。 下面用例子说明。 例 4 用动态规划解下列非线性规划 ∑= n k gk uk 1 max ( ) ； s.t. ∑= = ≥ n k uk a uk 1 , 0 . 其中 ( ) gk uk 为任意的已知函数。 解 按变量uk 的序号划分阶段，看作n 段决策过程。设状态为 1 2 1 , , , n+ x x L x ，取 问题中的变量u u un , , , 1 2 L 为决策。状态转移方程为 , , 1,2, , . x1 = a xk +1 = xk − uk k = L n 取 ( ) gk uk 为阶段指标，最优值函数的基本方程为（注意到 xn+1 = 0 ） ( ) max [ ( ) ( )] 1 1 0 + + ≤ ≤ = k k + k k u x k k f x g x f x k k ； 0 ≤ xk ≤ a, k = n,n −1,L,2,1； f n+1 (0) = 0. 按照逆序解法求出对应于 k x 每个取值的最优决策 ( ) * k k u x ，计算至 ( ) 1f a 后即可利 用状态转移方程得到最优状态序列{ } * k x 和最优决策序列{ ( )} * * k k u x 。 与静态规划相比，动态规划的优越性在于： （i）能够得到全局最优解。由于约束条件确定的约束集合往往很复杂，即使指标 函数较简单，用非线性规划方法也很难求出全局最优解。而动态规划方法把全过程化为