road(vertex,vertex)/A B1,A B2,B1 C1,B1 C2,B1 c3,B2 C2,B2 C3,B2 C4, C1 D1,C1 D2,C2 D1,C2 D2,C3 D2,C3 D3,C4 D2,C4 D3, D1 E1,D1 E2,D2 E2,D2 E3,D3 E2,D3 E3,
E1 F1,E1 F2,E2 F1,E2 F2,E3 F1,E3 F2,F1 G,F2 G/:D; endsets
data:
D=5 3 1 3 6 8 7 6 6 8 3 5 3 3 8 4 2 2 1 2 3 3 3 5 5 2 6 6 4 3; L=0,,,,,,,,,,,,,,,; enddata
@for(vertex(i)|i#GT#1:L(i)=@min(road(j,i):L(j)+D(j,i))); end
纵上所述，如果一个问题能用动态规划方法求解，那么，我们可以按下列步骤，首 先建立起动态规划的数学模型： （i）将过程划分成恰当的阶段。
（ii）正确选择状态变量k x ，使它既能描述过程的状态，又满足无后效性，同时确 定允许状态集合k X 。
（iii）选择决策变量k u ，确定允许决策集合( ) k k U x 。 （iv）写出状态转移方程。
（v）确定阶段指标( , ) k k k v x u 及指标函数kn V 的形式（阶段指标之和，阶段指标之 积，阶段指标之极大或极小等）。
（vi）写出基本方程即最优值函数满足的递归方程，以及端点条件。 §3 逆序解法的计算框图
-60-
以自由终端、固定始端、指标函数取和的形式的逆序解法为例给出计算框图，其它 情况容易在这个基础上修改得到。 一般化的自由终端条件为
1 1, 1, 1
( ) ( ), 1,2, , + + + + = = n n i n i n f x ?x i L n (3)
其中?为已知。固定始端条件可表示为{ } { *}
X = x = x 。
如果状态k x 和决策k u 是连续变量，用数值方法求解时需按照精度要求进行离散 化。设状态k x 的允许集合为
1 1 1
X x i n i n k n k ki k k = { | = 1,2,L, }, = 1,2,L, , = 1,2,L, .
决策( ) ki ki u x 的允许集合为
U u j n i n k n ki k
j
ki ki
= { ( ) | = 1,2,L, }, = 1,2,L, , = 1,2,L, .
状态转移方程和阶段指标应对k x 的每个取值ki x 和ki u 的每个取值( j)
u 计算，即 ( , ( j) )
k k ki ki T = T x u ，( , ( j) )
k ki ki v = v x u 。最优值函数应对k x 的每个取值ki x 计算。基本方
ki
程可以表为
1,2, , , 1,2, , , , ,2,1. ( ) opt ( ), ( ) ( , ) ( ( , )),
( ) ( ) 1 ( ) ( )
j L n i L n k n L f x f x
f x v x u f T x u
ki k ki j k j k ki j k k ki ki j ki k ki ki j k
= = = = = + +
（4）
图2 解法框图 -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 2 *
u x u x L u x 和最优轨线{ , * , , *}
1 n
x x L x 。
§4 动态规划与静态规划的关系
动态规划与静态规划（线性和非线性规划等）研究的对象本质上都是在若干约束条 件下的函数极值问题。两种规划在很多情况下原则上可以相互转换。
动态规划可以看作求决策n u ,u , ,u 1 2 L 使指标函数( , , , ) 1n 1 1 2 n V x u，u L u 达到最优 （最大或最小）的极值问题，状态转移方程、端点条件以及允许状态集、允许决策集等 是约束条件，原则上可以用非线性规划方法求解。
一些静态规划只要适当引入阶段变量、状态、决策等就可以用动态规划方法求解。 下面用例子说明。
例4 用动态规划解下列非线性规划
Σ
n k
=
k k 1
g u
max ( )；
s.t.
Σ
=
= ≥
n k k k 1
u a u
, 0 .
其中( ) k k g u 为任意的已知函数。
解按变量k u 的序号划分阶段，看作n段决策过程。设状态为1 2 1 , , , n+ x x L x ，取 问题中的变量n u ,u , ,u 1 2 L 为决策。状态转移方程为
, , 1,2, , . 1 1 x a x x u k n = k = k ?k = L +
取( ) k k g u 为阶段指标，最优值函数的基本方程为（注意到0 1 = n+ x ）
( ) max [ ( ) ( )] 0 1 1 ≤≤ + + = + k k u x k k k k f x g x f x
k k
；
0 ≤x ≤a, k = n,n ?1,L,2,1 k ； (0) 0 1 = n+ f .
按照逆序解法求出对应于k x 每个取值的最优决策* ( )
k k
u x ，计算至( ) 1 f a 后即可利
用状态转移方程得到最优状态序列{ *} k x 和最优决策序列{ * ( * )}
k k
u x 。
与静态规划相比，动态规划的优越性在于：
（i）能够得到全局最优解。由于约束条件确定的约束集合往往很复杂，即使指标
函数较简单，用非线性规划方法也很难求出全局最优解。而动态规划方法把全过程化为
-62-
一系列结构相似的子问题，每个子问题的变量个数大大减少，约束集合也简单得多，易 于得到全局最优解。特别是对于约束集合、状态转移和指标函数不能用分析形式给出的 优化问题，可以对每个子过程用枚举法求解，而约束条件越多，决策的搜索范围越小， 求解也越容易。对于这类问题，动态规划通常是求全局最优解的唯一方法。
（ii）可以得到一族最优解。与非线性规划只能得到全过程的一个最优解不同，动
态规划得到的是全过程及所有后部子过程的各个状态的一族最优解。有些实际问题需要 这样的解族，即使不需要，它们在分析最优策略和最优值对于状态的稳定性时也是很有 用的。当最优策略由于某些原因不能实现时，这样的解族可以用来寻找次优策略。 （iii）能够利用经验提高求解效率。如果实际问题本身就是动态的，由于动态规划
方法反映了过程逐段演变的前后联系和动态特征，在计算中可以利用实际知识和经验提 高求解效率。如在策略迭代法中，实际经验能够帮助选择较好的初始策略，提高收敛速 度。
动态规划的主要缺点是：
（i）没有统一的标准模型，也没有构造模型的通用方法，甚至还没有判断一个问 题能否构造动态规划模型的准则。这样就只能对每类问题进行具体分析，构造具体的模 型。对于较复杂的问题在选择状态、决策、确定状态转移规律等方面需要丰富的想象力 和灵活的技巧性，这就带来了应用上的局限性。
（ii）用数值方法求解时存在维数灾（curse of dimensionality）。若一维状态变量有m 个取值，那么对于n维问题，状态xk 就有mn个值，对于每个状态值都要计算、存储函 数( ) 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 d x u x f x k n L k k u x k k k k k k
k k
= + = + +
( ) 0. 1 1 = n+ n+ f x
利用这个模型可以算出例l的最短路线为AB C D E F G 1 2 1 2 2 ，相应的最短距离为18。 5.2 生产计划问题
对于例2 一类生产计划问题（Production planning problem），阶段按计划时间自然 划分，状态定义为每阶段开始时的储存量k x ，决策为每个阶段的产量k u ，记每个阶段 的需求量（已知量）为k d ，则状态转移方程为
, 0, 1,2, , . 1 x x u d x k n k = k + k ?k k ≥ = L + (5)
设每阶段开工的固定成本费为a ，生产单位数量产品的成本费为b ，每阶段单位数量产 品的储存费为c ，阶段指标为阶段的生产成本和储存费之和，即
??? + > = + 0 , 0 ( , ) k k
k k k k
a bu u v x u cx (6)
-63-
指标函数Vkn 为vk 之和。最优值函数( ) k k f x 为从第k 段的状态k x 出发到过程终结的最