系列结构相似的子问题,每个子问题的变量个数大大减少,约束集合也简单得多,易 于得到全局最优解。特别是对于约束集合、状态转移和指标函数不能用分析形式给出的 优化问题,可以对每个子过程用枚举法求解,而约束条件越多,决策的搜索范围越小 求解也越容易。对于这类问题,动态规划通常是求全局最优解的唯一方法。 (ⅱi)可以得到一族最优解。与非线性规划只能得到全过程的一个最优解不同,动 态规划得到的是全过程及所有后部子过程的各个状态的一族最优解。有些实际问题需要 这样的解族,即使不需要,它们在分析最优策略和最优值对于状态的稳定性时也是很有 用的。当最优策略由于某些原因不能实现时,这样的解族可以用来寻找次优策略。 (ⅲi)能够利用经验提高求解效率。如果实际问题本身就是动态的,由于动态规划 方法反映了过程逐段演变的前后联系和动态特征,在计算中可以利用实际知识和经验提 髙求解效率。如在策略迭代法中,实际经验能够帮助选择较好的初始策略,提高收敛速 动态规划的主要缺点是 (i)没有统一的标准模型,也没有构造模型的通用方法,甚至还没有判断一个问 题能否构造动态规划模型的准则。这样就只能对每类问题进行具体分析,构造具体的模 型。对于较复杂的问题在选择状态、决策、确定状态转移规律等方面需要丰富的想象力 和灵活的技巧性,这就带来了应用上的局限性 (ⅱ)用数值方法求解时存在维数灾( curse of dimensionality)。若一维状态变量有m 个取值,那么对于n维问题,状态xk就有m"个值,对于每个状态值都要计算、存储函 数f(x),对于n稍大的实际问题的计算往往是不现实的。目前还没有克服维数灾的 有效的一般方法。 §5若干典型问题的动态规划模型 51最短路线问题 对于例1一类最短路线问题( shortest path problem),阶段按过程的演变划分,状 态由各段的初始位置确定,决策为从各个状态出发的走向,即有xk+1=l4(xk),阶段 指标为相邻两段状态间的距离d4(xk,u4(x),指标函数为阶段指标之和,最优值函数 f4(xk)是由x出发到终点的最短距离(或最小费用),基本方程为 f(x =min[d,(k, u,(xk))+r+ (xk1)]k=n,, 1; 利用这个模型可以算出例1的最短路线为ABC2D1E2F2G,相应的最短距离为18 52生产计划问题 对于例2一类生产计划问题( Production planning problem),阶段按计划时间自然 划分,状态定义为每阶段开始时的储存量x,决策为每个阶段的产量l4,记每个阶段 的需求量(已知量)为d,则状态转移方程为 xkI=xk+uk-dk, xk 设每阶段开工的固定成本费为a,生产单位数量产品的成本费为b,每阶段单位数量产 品的储存费为c,阶段指标为阶段的生产成本和储存费之和,即 a+ buk, uk>0-62- 一系列结构相似的子问题，每个子问题的变量个数大大减少，约束集合也简单得多，易 于得到全局最优解。特别是对于约束集合、状态转移和指标函数不能用分析形式给出的 优化问题，可以对每个子过程用枚举法求解，而约束条件越多，决策的搜索范围越小， 求解也越容易。对于这类问题，动态规划通常是求全局最优解的唯一方法。 （ii）可以得到一族最优解。与非线性规划只能得到全过程的一个最优解不同，动 态规划得到的是全过程及所有后部子过程的各个状态的一族最优解。有些实际问题需要 这样的解族，即使不需要，它们在分析最优策略和最优值对于状态的稳定性时也是很有 用的。当最优策略由于某些原因不能实现时，这样的解族可以用来寻找次优策略。 （iii）能够利用经验提高求解效率。如果实际问题本身就是动态的，由于动态规划 方法反映了过程逐段演变的前后联系和动态特征，在计算中可以利用实际知识和经验提 高求解效率。如在策略迭代法中，实际经验能够帮助选择较好的初始策略，提高收敛速 度。 动态规划的主要缺点是： （i）没有统一的标准模型，也没有构造模型的通用方法，甚至还没有判断一个问 题能否构造动态规划模型的准则。这样就只能对每类问题进行具体分析，构造具体的模 型。对于较复杂的问题在选择状态、决策、确定状态转移规律等方面需要丰富的想象力 和灵活的技巧性，这就带来了应用上的局限性。 （ii）用数值方法求解时存在维数灾（curse of dimensionality）。若一维状态变量有m 个取值，那么对于n 维问题，状态 k x 就有 n m 个值，对于每个状态值都要计算、存储函 数 ( ) k k f x ，对于n 稍大的实际问题的计算往往是不现实的。目前还没有克服维数灾的 有效的一般方法。 §5 若干典型问题的动态规划模型 5.1 最短路线问题 对于例 1 一类最短路线问题（shortest Path Problem），阶段按过程的演变划分，状 态由各段的初始位置确定，决策为从各个状态出发的走向，即有 ( ) k 1 k k x = u x + ，阶段 指标为相邻两段状态间的距离 ( , ( )) k k k k d x u x ，指标函数为阶段指标之和，最优值函数 ( ) k k f x 是由 k x 出发到终点的最短距离（或最小费用），基本方程为 ( ) min[ ( , ( )) ( )], , ,1; 1 1 ( ) f x dk xk uk xk f k xk k n L u x k k k k = + + + = ( ) 0. f n+1 xn+1 = 利用这个模型可以算出例 l 的最短路线为 AB1C2D1E2F2G ，相应的最短距离为 18。 5.2 生产计划问题 对于例 2 一类生产计划问题（Production planning problem），阶段按计划时间自然 划分，状态定义为每阶段开始时的储存量 k x ，决策为每个阶段的产量uk ，记每个阶段 的需求量（已知量）为dk ，则状态转移方程为 , 0, 1,2, , . xk +1 = xk + uk − dk xk ≥ k = L n (5) 设每阶段开工的固定成本费为a ，生产单位数量产品的成本费为b ，每阶段单位数量产 品的储存费为c ，阶段指标为阶段的生产成本和储存费之和，即 ⎩ ⎨ ⎧ + > = + 0 , 0 ( , ) k k k k k k a bu u v x u cx (6)