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

第八章动态规划s 1多阶段决策最优化问题举例S2基本概念、基本方程与最优化原理83离散确定性动态规划求解2024-10-27

2024-10-27 2 第八章 动态规划 §1 多阶段决策最优化问题举例 §2 基本概念、基本方程与最优化原理 §3 离散确定性动态规划求解

$1多阶段决策过程最优化问题举例例1最短路径问题下图表示从起点A到终点E之间各点的距离。求A到E的最短路径。RDB2024-10-27

2024-10-27 3 §1 多阶段决策过程最优化问题举例 例1 最短路径问题 下图表示从起点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

动态规划是用来解决多阶段决策过程最优化的一种方法。多阶段决策：是动态决策问题的一种特殊形式：系统的动态过程可以按照时间等进程分为状态相互联系而又相互区别的各个阶段每个阶段都要进行决策,目的是使整个过程的决策达到最优效果。多阶段决策求解思路：将多阶段决策问题（n阶段）分解成n个具有递推关系的单阶段决策问题，进行正推或逆推计算。2024-10-27

2024-10-27 4 动态规划是用来解决多阶段决策过程最优化的一种方法。 多阶段决策： 是动态决策问题的一种特殊形式； 系统的动态过程可以按照时间等进程分为状态相互联系 而又相互区别的各个阶段； 每个阶段都要进行决策,目的是使整个过程的决策 达到 最优效果。 多阶段决策求解思路： 将多阶段决策问题（n阶段）分解成n个具有递推关系的单阶 段决策问题，进行正推或逆推计算

82基本概念、基本方程与最优化原理一、基本概念：1.阶段k：表示决策顺序的离散的量，阶段可以按时间或空间划分。（顺序编号法、逆序编号法）2.状态sk：反应前一阶段决策的结果，又是本阶段作决策的依据和出发点（能确定地表示决策过程当前特征的量）。状态可以是数量，也可以是字符，数量状态可以是连续的，也可以是离散的。3.决策x：从某一状态向下一状态过渡时所做的选择。决策是所在状态的函数，记为x,(s)。决策允许集合D（s）：在状态s下，允许采取决策的全体。2024-10-275

2024-10-27 5 一、基本概念： 1. 阶段k：表示决策顺序的离散的量，阶段可以按时间或空间划 分。(顺序编号法、逆序编号法） 2. 状态sk：反应前一阶段决策的结果，又是本阶段作决策的依据 和出发点（能确定地表示决策过程当前特征的量）。状态可以 是数量，也可以是字符，数量状态可以是连续的，也可以是离 散的。 3. 决策xk：从某一状态向下一状态过渡时所做的选择。决策是所 在状态的函数，记为xk(sk)。 决策允许集合Dk(sk)：在状态sk下，允许采取决策的全体。 §2 基本概念、基本方程与最优化原理

4.含n个阶段的全过程策略「xi(si),x2(s2)，…，xn(s）|：从第1阶段开始到最后第n阶段的决策序列；k子策略|xx(s),Xk+(Sk+1)，.….，xn(sn)「：从第k阶段开始到最后第n阶段的决策序列。5. 状态转移方程 Sk+I=T(Sk,xi)：某一状态以及该状态下的决策，与下一状态之间的函数关系。6.阶段指标函数V(Sk，X)：从状态s出发，选择决策x所产生的第k阶段指标。过程指标函数Vk.n(SXk，Xk+1.xn)：从状态t出发，选择决策xk,Xk+1，…,x,所产生的过程指标。2024-10-276

2024-10-27 6 4. 含n个阶段的全过程策略丨x1(s1), x2(s2), . , xn (sn )丨：从第1 阶段开始到最后第n阶段的决策序列； k子策略丨xk(sk), xk+1(sk+1), . , xn (sn )丨：从第k阶段开始到最 后第n阶段的决策序列。 5. 状态转移方程 sk+1=T(sk , xk)：某一状态以及该状态下的决 策，与下一状态之间的函数关系。 6. 阶段指标函数Vk(sk , xk)：从状态sk出发，选择决策xk所产生 的第k阶段指标。 过程指标函数Vk,n (sk , xk , xk+1 ,., xn )：从状态sk出发，选择 决策xk , xk+1 , ., xn所产生的过程指标

动态规划要求过程指标具有可分离性，即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