fs(C3)=min d(C3,D1)+f4(D1) 1+4 1ac2,D2)+(D2) -min =5 3+3 即从C3到E的最短距离为5,其路径为C3→D1→E,相应的决策为 U3(C3)=D 第三步,k=2,这是一个具有三个状态,要经过两个中间站才能到达终点 的三级决策问题。由于第3段各点C1,C2C3到终点E的最短距离f(C1) f3C2)fC3),已知所以要求城市B1到E的最短距离,只需以它们为基础, 分别加上B1到达C1,C2,C3的一段距离,加以比较取其最短者即可 d(B1,C1)+f3(C1) f2(B)=mn1dB,C2)+f(C2)=mn14+5}=9 d(B1,C3)+f3(C3) 5+5 即B1到终点E的最短距离为9,其路径为B1→C2→D2→E,本段的相应 决策为U,(B1)=C 2021/2/24
2021/2/24 11 3 f （C3）＝min + + ( , ) ( ) ( , ) ( ) 3 2 4 2 3 1 4 1 d C D f D d C D f D =min + + 3 3 1 4 |=5 即从 C3 到 E 的最短距离为 5,其路径为 C3→D1→E,相应的决策为 * U3 （C3）= D1。 第三步,k=2,这是一个具有三个状态,要经过两个中间站才能到达终点 的三级决策问题。由于第 3 段各点 C1,C2,C3 到终点 E 的最短距离 f3(C1), f3(C2), f3(C3),已知,所以要求城市 B1 到 E 的最短距离,只需以它们为基础, 分别加上 B1 到达 C1,C2,C3 的一段距离,加以比较取其最短者即可。 ( ) 2 B1 f =min + + + ( , ) ( ) ( , ) ( ) ( , ) ( ) 1 3 3 3 1 2 3 2 1 1 3 1 d B C f C d B C f C d B C f C =min + + + 5 5 4 5 6 7 =9 即 B1 到终点 E 的最短距离为 9,其路径为 B1→C2→D2→E,本段的相应 决策为 * U 2 （ B1 ）=C2
同理有 d(B2,C1)+f3(C1) 8+7 f(B2)=mn014(B2C2)+/C2)=mn17+5}=11 (B2,C3)+f3(C3) 6+5 即U2(B2)=C3 d(B32C1)+f3(C 7+7 f2(B3)=mnd(B,C2)+/C2)=mn18+5}=13 B3,C3)+f3(C3) 9+5 即U2(B3)=C2 第四步k=1,只有一个状态点A则 d(A,B1)+f2(B1) 8+9 f(4)=mn1(A,B2)+f(B2)}=mn19+11=17 d(A,B3)+f3(B3 5+13 2021/2/24 即U1(A)=B 12
2021/2/24 12 同理有: ( ) 2 B2 f =min + + + ( , ) ( ) ( , ) ( ) ( , ) ( ) 2 3 3 3 2 2 3 2 2 1 3 1 d B C f C d B C f C d B C f C =min + + + 6 5 7 5 8 7 =11 即 * U2 （ B2 ）＝C3 ( ) 2 B3 f =min + + + ( , ) ( ) ( , ) ( ) ( , ) ( ) 3 3 3 3 3 2 3 2 3 1 3 1 d B C f C d B C f C d B C f C =min + + + 9 5 8 5 7 7 =13 即 * U 2 （ B3 ）＝C2 第四步,k=1, 只有一个状态点 A,则 ( ) f1 A =min + + + ( , ) ( ) ( , ) ( ) ( , ) ( ) 3 3 3 2 3 2 1 2 1 d A B f B d A B f B d A B f B =min + + + 5 13 9 11 8 9 =17 即 * U1 （A）＝ B1
从城市A到城市E的最短距离为17。把各段的最优决策按计算顺序 反推即得到最优决策序列即U(A)=B1,U2(B1)=C2,U3(C2) =D2,U4(D2)=E,所以最短路线为A→B1→C2→D2→E。 上述最优路线是通过计算最优指标函数得到的,可以称作 指标函教法。还可以采用在图上直接标记的方法求得,这种直 接标记的方法可称作图上作业法( Click to show) 7 B1 CI 4 5气 2 2 13 5 EDA BSC (课堂练习参教材) 这种方式使用起来更简单明了,最佳路线的确定方法也 3很容易[f)-d(s)=fsn),是一种值得推存的方法
2021/2/24 13 从城市 A 到城市 E 的最短距离为 17。把各段的最优决策按计算顺序 反推,即得到最优决策序列,即 * U1 （A）＝ B1 , * U2 （ B1 ）=C2 , * U3 （ C2 ） ＝ D2 ， * U 4 （ D2 ）＝E，所以最短路线为:A→B1→C2→D2→E。 4 3 7 5 13 5 11 9 17 上述最优路线是通过计算最优指标函数得到的，可以称作 指标函数法。还可以采用在图上直接标记的方法求得，这种直 接标记的方法可称作图上作业法（Click to show） 这种方式使用起来更简单明了，最佳路线的确定方法也 很容易[f(sk )－d(sk ,sk+1)=f(sk+1)]，是一种值得推荐的方法。 （课堂练习参教材）
在上述的求解过程中,各段的计算都利用了第k段和第k+1段的如下 关系: fr (sk)=min dk (sk, uk)+fu+(sk+(k=4, 3, 2, 1)(1) f5(s)=0 (2) 这种递推关系称为动态规划的基本方程(2)式称边界条件,容易算出 运用动态规划方法解例51只进行了17次加法运算,11次比较运算,就 获得了最优解,比穷举法的计算量明显地要少,而且随着问题段数的增加 和变量数目的增多,计算量将呈指数规律减少。其次,动态规划的计算结果 不仅得到了A到E的最短路线,而且得到了任意一点到E点的最优路线 这可由图52来描述(用彩色线表示最优路线,各点上的数字表最短距离) B11 C1 ④AB2 图5.2 13 1B3 ℃3 2021/2/24
2021/2/24 14 在上述的求解过程中,各段的计算都利用了第 k 段和第 k+1 段的如下 关系： k f （ k s ）＝min{ dk （ k s ，Uk ）＋ ( ) k+1 k+1 f s (k=4,3,2,1) (1) ( ) 5 5 f s ＝0 (2) 这种递推关系称为动态规划的基本方程,(2)式称边界条件,容易算出, 运用动态规划方法解例 5.1 只进行了 17 次加法运算,11 次比较运算，就 获得了最优解,比穷举法的计算量明显地要少,而且随着问题段数的增加 和变量数目的增多,计算量将呈指数规律减少。其次 ,动态规划的计算结果 不仅得到了 A 到 E 的最短路线,而且得到了任意一点到 E 点的最优路线。 这可由图5.2 来描述(用彩色线表示最优路线,各点上的数字表最短距离) 图5.2
根据例5.1动态规划的基本思想可总结如下 将多阶段决策过程划分阶段恰当地选取状态变量,决策变量和 定义最优指标函数,从而把问题化成一族同类型的子问题,然后逐 求解。 求解时总是从边界条件开始,沿过程行进方向,逐段递推寻 优。在每一个子问题求解时,都要利用它前边已求出的子问题的最优 结果。最后一个子问题的最优解,就是整个问题的最优解 动态规划方法是既把当前一段与未来各段分开,又把当前效益 和未来效益结合起来考虑的一种最优化方法。因此每段的最优策略 的选取都是从全局考虑的,它与该段的最优选择是不同的。 §52动态规划的基本原理、模型和解法 5.2.1最优化原理 动态规划方法是由美国数学家贝尔曼( R Bellman)等人于本世纪50 年代提出的。他们针对多阶段决策问题的特点提出了解决这类问题 的“最优化原理”,并成功地解决了生产管理、工程技术许多方面的 2021 实际间题。 15
2021/2/24 15 根据例5.1,动态规划的基本思想可总结如下： 一、将多阶段决策过程划分阶段,恰当地选取状态变量,决策变量和 定义最优指标函数,从而把问题化成一族同类型的子问题，然后逐个 求解。 二、求解时总是从边界条件开始, 沿过程行进方向，逐段递推寻 优。在每一个子问题求解时,都要利用它前边已求出的子问题的最优 结果。最后一个子问题的最优解,就是整个问题的最优解。 三、动态规划方法是既把当前一段与未来各段分开,又把当前效益 和未来效益结合起来考虑的一种最优化方法。因此,每段的最优策略 的选取都是从全局考虑的，它与该段的最优选择是不同的。 §5.2 动态规划的基本原理、模型和解法 5.2.1 最优化原理 动态规划方法是由美国数学家贝尔曼(R.Bellman)等人于本世纪50 年代提出的。他们针对多阶段决策问题的特点,提出了解决这类问题 的“最优化原理” ,并成功地解决了生产管理、工程技术许多方面的 实际问题