先将问题的过程分成几个相互联系的阶段,恰当的选取状态变量和决策变量,以及定义指标函数和 最优值函数,把大问题化成一族同类型的子问题,逐个求解,即从边界条件开始,逐段递推寻优,在每 一个子问题的求解中,均利用了它前面的子问题的最优化结果。依次进行,最后一个子问题所得的最优 解就是整个问题的最优解。 (2)在多阶段决策过程中,动态规划方法既把当前一段和未来各段分开,又把当前效益与未来效 益结合起来考虑,因此,每段决策的选取是从全局来考虑的,与该段的最优选择答案一般不同。 (3)由于初始状态己知,而每段的决策都是该段状态的函数,故最优策略所经过的各段状态便可 逐次变换得到,从而确定了最优路线。 如例411,初始状态A己知,则按下面箭头所指的方向逐次变换有: 4(A):→B 4(B)→C24(C2)→D 4,(D)→E2 4(E2)→F34,(E)→G C2 +E2 2 G 上述最短路线问题的计算过程,也可借助如下图形直观简明的表示出来。(PI98) 用直线连接的点表示该点到终点G的最短路线,未用直线连接的点说明它不是该点到终点G的最短 路线,圈上的数表示该点到终点G的最短距离。 上述在图上直接作业的方法叫标号法。 如果规定从A点到G点为顺行方向,则由G点到A点为逆行方向,从G点开始从后向前标号的解法 称为逆序解法。 由于从A点计算到G点和从G点计算到A点的最短路线是相同的,因而标号也可以由A开始从前向 后标号,视G点为起点,A为终点,按动态规划方法处理。以G为始端A为终端,从A到G的解法称为 顺序解法。 由上可见,顺序解法和逆序解法只表示行进方向的不同或对始端终端看法的颠倒。 但用动态规划方法求最优解时,都是在行进方向规定后,均逆着这个规定的行进方向,从最后一段 向前递推计算,逐段寻找最优途径。 3.动态规划与穷举法的比较 (1)计算量少。 (2)丰富了计算结果。在逆序(或顺序)解法中,不仅得到了由A(G)到G(A)的最短路线及相应的 最短距离,而且得到了从所有各中间点出发到$G(A)$的最短路线及相应的距离。亦即求出的不是一个最 优策略,而是一族的最优策略。 4.建立动态规划模型的前提 建立动态规划模型时,需做到: (1)将问题的过程划分为恰当的阶段: (2)正确选择状态变量$%,使它既能描述过程的演变,又能满足无后效性: (3)确定决策变量4及每阶段的允许决策集合U4(S): (4)正确写出状态转移方程s+1=T八s%,): (5)正确写出k后子过程的指标函数'km的关系,满足三个性质: (a)是定义在全过程和所有后部子过程上的数量函数: (b)具有可分离性,并满足递推关系,即5 先将问题的过程分成几个相互联系的阶段,恰当的选取状态变量和决策变量,以及定义指标函数和 最优值函数,把大问题化成一族同类型的子问题,逐个求解,即从边界条件开始,逐段递推寻优,在每 一个子问题的求解中,均利用了它前面的子问题的最优化结果。依次进行,最后一个子问题所得的最优 解就是整个问题的最优解。 (2)在多阶段决策过程中,动态规划方法既把当前一段和未来各段分开,又把当前效益与未来效 益结合起来考虑,因此,每段决策的选取是从全局来考虑的,与该段的最优选择答案一般不同。 (3)由于初始状态已知,而每段的决策都是该段状态的函数,故最优策略所经过的各段状态便可 逐次变换得到,从而确定了最优路线。 如例 4.1.1,初始状态 A 已知,则按下面箭头所指的方向逐次变换有: 1 1 uA B ( ):→ 21 2 uB C ( ):→ 32 1 uC D ( ):→ 41 2 uD E ( ):→ 52 2 uE F ( ):→ 6 2 uF G ( ):→ A B1 C2 D1 E2 F2 G 上述最短路线问题的计算过程,也可借助如下图形直观简明的表示出来。(P198) 用直线连接的点表示该点到终点 G 的最短路线,未用直线连接的点说明它不是该点到终点 G 的最短 路线,圈上的数表示该点到终点 G 的最短距离。 上述在图上直接作业的方法叫标号法。 如果规定从 A 点到 G 点为顺行方向,则由 G 点到 A 点为逆行方向,从 G 点开始从后向前标号的解法 称为逆序解法。 由于从 A 点计算到 G 点和从 G 点计算到 A 点的最短路线是相同的,因而标号也可以由 A 开始从前向 后标号,视 G 点为起点,A 为终点,按动态规划方法处理。以 G 为始端 A 为终端,从 A 到 G 的解法称为 顺序解法。 由上可见,顺序解法和逆序解法只表示行进方向的不同或对始端终端看法的颠倒。 但用动态规划方法求最优解时,都是在行进方向规定后,均逆着这个规定的行进方向,从最后一段 向前递推计算,逐段寻找最优途径。 3. 动态规划与穷举法的比较 (1)计算量少。 (2)丰富了计算结果。在逆序(或顺序)解法中,不仅得到了由 A(G)到 G(A)的最短路线及相应的 最短距离,而且得到了从所有各中间点出发到$G(A)$的最短路线及相应的距离。亦即求出的不是一个最 优策略,而是一族的最优策略。 4.建立动态规划模型的前提 建立动态规划模型时,需做到: (1)将问题的过程划分为恰当的阶段; (2)正确选择状态变量 sk,使它既能描述过程的演变,又能满足无后效性; (3)确定决策变量 uk及每阶段的允许决策集合 Uk(sk); (4)正确写出状态转移方程 sk+1=T(sk,uk); (5)正确写出 k 后子过程的指标函数 Vk,n 的关系,满足三个性质: (a)是定义在全过程和所有后部子过程上的数量函数; (b)具有可分离性,并满足递推关系,即