《运筹学》课程教学课件（讲稿）第八章 动态规划

动态规划要求过程指标具有可分离性，即Vk.n(Sk, Xk, Xk+1, .., Xn) = Vk(Sk, Xk)+Vk+i(Sk+1, Xk+1, .., Xn)称指标具有可加性，或Vk.n(Sk, Xk, Xk+1, .., Xn) = Vk(Sk, Xk)XVk+i(Sk+1, Xk+1, ..., X)称指标具有可乘性简写为：和式Vk.n(s)=Vk(Sk,Xk)+Vk+1,n(Sk+1)乘式Vk.n(St) = Vk(Sk, Xk)+Vk+1,n(Sk+1)k最优子策略：fi(si)=opt Vk,n2024-10-27

2024-10-27 7 动态规划要求过程指标具有可分离性，即 Vk,n (sk , xk , xk+1 , ., xn ) = vk (sk , xk )+Vk+1(sk+1 , xk+1 , ., xn ) 称指标具有可加性，或 Vk,n (sk , xk , xk+1 , ., xn ) = vk (sk , xk )×Vk+1(sk+1 , xk+1 , ., xn ) 称指标具有可乘性。 简写为： 和式 Vk,n (sk ) = vk (sk , xk )+Vk+1,n (sk+1) 乘式 Vk,n (sk ) = vk (sk , xk )+Vk+1,n (sk+1) k最优子策略：fk(sk)=opt Vk,n

对于可加性指标函数，上式可以写为k=12,..,nfi(sk)= Opt (v(Sk,Xx)+ fk+i(Sk+1))XREDk(SK)上式中“opt”表示“max”或“min”对于可乘性指标函数，上式可以写为k=12,...,nfr(sh)= Opt (vs(Sk,X)× fk+1(Sk+1)XREDk(Sk)以上式子称为动态规划最优指标的递推方程，是动态规划的基本方程。终端条件：为了使以上的递推方程有递推的起点，必须要设定最优指标的终端条件，一般可加性指标f,+1（sn+1）= 0;可乘性指标fn+i（sn+1）=1。82024-10-27

2024-10-27 8 对于可加性指标函数，上式可以写为 上式中“opt”表示“max”或“min” 。 对于可乘性指标函数，上式可以写为 以上式子称为动态规划最优指标的递推方程，是动态规划的 基本方程。 终端条件：为了使以上的递推方程有递推的起点，必须要设 定最优指标的终端条件，一般可加性指标fn+1(sn+1) = 0； 可乘性指标fn+1(sn+1) = 1。 f s vk sk xk f k sk k n x D s k k opt k k k ( ) { ( , ) ( )} 1,2, , 1 1 ( )        f s vk sk xk f k sk k n x D s k k opt k k k ( ) { ( , ) ( )} 1,2, , 1 1 ( )       

二、动态规划基本方程：最优指标函数f(s)：从状态sr出发，对所有的策略Pk,n’过程指标Vk.n的最优值，即：J.(st)= opt(v (st,xx)+fk(sk+1) k=n,n-1,n-2,1和式:(sk)eD;(sk)fn+1 (sn+l)= 0f.(st)=, opt,(v (sk,xx) k+1 (sk+1) k =n,n-1,n-2,.1乘式：X (sk)eDA(skn+ (sn+1)=1Vk,=p(sk,xk）为状态sk，决策为x时对应的第k阶段阶段指标函数。2024-10-27

2024-10-27 9 二、动态规划基本方程： 最优指标函数fk(sk)：从状态sk出发，对所有的策略Pk,n， 过程指标Vk,n的最优值，即：             1 1 1 1 , , 1, 2, 1 0 k k k k k k k k k k k x s D s n n f s opt v s x f s k n n n f s                              1 1 1 1 , , 1, 2, 1 1 k k k k k k k k k k k x s D s n n f s opt v s x f s k n n n f s                  Vk ,n   sk , xk  为状态sk，决策为xk时对应的第k阶段阶段指 标函数。 和式： 乘式：

三、最优化原理作为整个过程的最优策略具有如下性质：不管在此最优策略上的某个状态以前的状态和决策如何，对该状态来说，以后的所有决策必定构成最优子策略。就是说，最优策略的任意子策略都是最优的。2024-10-2710

2024-10-27 10 三、最优化原理 作为整个过程的最优策略具有如下性质： 不管在此最优策略上的某个状态以前的状 态和决策如何，对该状态来说，以后的所有决 策必定构成最优子策略。就是说，最优策略的 任意子策略都是最优的

最优化原理最短路径问题：下图表示从起点A到终点E之间各点的距离。求A到E的最短路径。DB2024-10-2711

2024-10-27 11 最优化原理 最短路径问题： 下图表示从起点A到终点E之间各点的距离。求A到E的最 短路径。 A B B C D B C D E C 2 1 2 3 1 2 3 1 2 5 7 6 3 2 4 5 1 5 1 4 6 3 3 3 3 4 3