第8章动态规划 电气信息学院 8.1动态规划数学模型 Dynamic Programming 佃松宜、李彬、曾晓东 Mathematical model of dp 2021年1月26日星期 k阶段指标函数 从阶段状态s出发,选择决策κ所产生的第k阶段指标,称为k 阶段指标函数记为vA(SAx) 过程指标函数 从阶段状态出发,选择决策x4xk1,所产生的过程指标, 称为k子过程指标函数或简称过程指标函数,记为 kursk+15· x)或V,n为阶段数。 最优指标函数 从k阶段状态s出发,对所有的子策略,最优的过程指标函数 称为最优指标函数,记为∫(),通常取V的最大值或最小值。 f(Sk)=opt kn(Sk, Pkm)).(Opt=optimization dk∈Dk(Sk) 表示“max”或“min
第8章 动态规划 电气信息学院 Dynamic Programming 佃松宜、李彬、曾晓东 2021年1月26日星期二 Page 11 k阶段指标函数 从k阶段状态sk出发，选择决策xk所产生的第k阶段指标，称为k 阶段指标函数,记为vk (sk ,xk )。 从k阶段状态sk出发，选择决策xk ,xk+1,…,xn所产生的过程指标， 称为k子过程指标函数或简称过程指标函数，记为 Vk (sk ,xk ,xk+1,…,xn )或Vk，n为阶段数。 过程指标函数 最优指标函数 从k阶段状态sk出发，对所有的子策略，最优的过程指标函数 称为最优指标函数，记为fk (sk )，通常取Vk的最大值或最小值。 ( ) { ( , )} , , ( ) k n k k n d D s f k sk opt V s P k k k = （Opt＝optimization 表示“max”或“min” 8.1 动态规划数学模型 Mathematical Model of DP
电气信息学院 8.1动态规划数学模型 第8章动态规划 佃松宜、李彬、曾晓东 Mathematical model of Dp Dynamic Programming 2021年1月26日星期 Page 12 动态规划要求过程指标满足递推关系,即 k(kkk+12 X vSX k2k/,k+1(k+1k+ ,)(8-2) 连和形式: VK=Vk(S2x2,x12…,x) (Sk2x)+k(S+12x+12…,xn) (8-3) ∑v(s,x 最优指标函数是 f(sk)=Opt v(Sk,xk)+f+(skD),k=1, 2, (8-4) xk∈Dk(Sk)
第8章 动态规划 电气信息学院 Dynamic Programming 佃松宜、李彬、曾晓东 2021年1月26日星期二 Page 12 动态规划要求过程指标满足递推关系 ，即 1 1 1 1 ( , , , , ) [ ( , ), ( , , , )] V s x x x V v s x V s x x k k k k n k k k k k k n + + + + = (8-2) 连和形式： 1 1 1 1 ( , , , , ) ( , ( , , , ) ( , K K k k k n k k k K k k n n j j j n j k V V s x x x v s x V s x x v s x V + + − = = = = + ）＋ ＋ ） (8-3) 最优指标函数是 f s Opt vk sk xk f k sk k n x D s k k k k k ( ) { ( , } ( )}, 1,2, , 1 1 ( ) = + + + = (8-4) 8.1 动态规划数学模型 Mathematical Model of DP
第8章动态规划 电气信息学院 8.1动态规划数学模型 Dynamic Programming 佃松宜、李彬、曾晓东 Mathematical model of Dp 2021年1月26日星期 Page 13 连乘形式(0):TK=K(,2x,xk,…,x S K(k+1k+1 8-5) ∏v,(S,x,)·V 最优指标函数是 f (sk)=Opt vk (Sk, dk, fk ( ski,k=1,2 xk∈Dk(Sk) (8-6) 动态规划数学模型由式(8-4)或8-6)、边界条件及状态转移方程 构成。如连和形式的数学模型 f(Sk)=Opt{v(Sk2xk}+f+1(Sk+1)},k=1,2,…,n xk∈Dk(Sk) f(S,=0 T(Sk,X
第8章 动态规划 电气信息学院 Dynamic Programming 佃松宜、李彬、曾晓东 2021年1月26日星期二 Page 13 动态规划数学模型由式(8-4)或(8-6)、边界条件及状态转移方程 构成。如连和形式的数学模型 连乘形式(vj≠0) ： 1 1 1 1 ( , , , , ) ( , ) ( , , , ) ( , ) K K k k k n k k k K k k n n j j j n j k V V s x x x v s x V s x x v s x V + + − = = = ＋ = (8-5) 最优指标函数是 f s Opt vk sk dk f k sk k n x D s k k k k k ( ) { ( , } ( )}, 1,2, , 1 1 ( ) = + + = (8-6) = = = + = + + + ( , ) ( ) 0 ( ) { ( , } ( )}, 1,2, , 1 1 1 ( ) k k k n n k k k k k x D s k k s T s x f s f s Opt v s x f s k n k k k 8.1 动态规划数学模型 Mathematical Model of DP
电气信息学院 8.1动态规划数学模型 第8章动态规划 佃松宜、李彬、曾晓东 Mathematical model of dp Dynamic Programming 2021年1月26日星期 Page 14 对于可加性指标函数,上式可以写为 f(Sk)=opt vk(Sk,xx) +fk k+1(k+1 k=12.……n dk∈Dk(Sk) 上式中“opt”表示“max”或“min”。对于可乘性指标函数, 上式可以写为 fk(S)=Opt{(Sk2xk}×(Sk1)k=1,2…,n D 上式称为动态规划最优指标的递推方程,是动态规划的基本方 程。 终端条件:为了使以上的递推方程有递推的起点,必须要设定 最优指标的终端条件,即确定最后一个状态n下最优指标j厂(sn)的 值
第8章 动态规划 电气信息学院 Dynamic Programming 佃松宜、李彬、曾晓东 2021年1月26日星期二 Page 14 对于可加性指标函数，上式可以写为 f s v s x f s k n k k k k k d D s k k opt k k k ( ) { ( , } ( )} 1,2, , 1 1 ( ) = + + + = 上式中“ opt”表示“ max”或“ min”。对于可乘性指标函数， 上式可以写为 f s v s x f s k n k k k k k x D s k k opt k k k ( ) { ( , } ( )} 1,2, , 1 1 ( ) = + + = 上式称为动态规划最优指标的递推方程，是动态规划的基本方 程。 终端条件：为了使以上的递推方程有递推的起点，必须要设定 最优指标的终端条件，即确定最后一个状态n下最优指标f n (sn )的 值。 8.1 动态规划数学模型 Mathematical Model of DP
8.1动态规划数学模型 第8章动态规划 电气信息学院 Mathematical model of dp Dynamic Programming 佃松宜、李彬、曾晓东 2021年1月26日星期 Page 15 用逆序法列表求解例8 k==5时,f(v0)=0 k=4,递推方程为 f4(s4)=mn{v4(S42x4)+f5(S3)} 阶段第阶段第段⊥第猕段第猕段|第阶段 状态:V1 v213v4 x4∈D4(S4) D(s)|sv(sr;)n(s…x)5(s)|f()最优决策x v→ 10 5+0=5 10 10 8 8+0=8 v10 v9-少v0ovno 4+0=4 →v 10
第8章 动态规划 电气信息学院 Dynamic Programming 佃松宜、李彬、曾晓东 2021年1月26日星期二 Page 15 用逆序法列表求解例8-1 k=n=5 时，f5 (v10)＝0 ( ) min { ( , ) ( )} 4 4 4 5 5 ( ) 4 4 4 4 4 f s v s x f s x D s = + k=4，递推方程为 s4 D4 (s4 ) s5 v4 (s4 ,x4 ) v4 (s4 ,x4 )+f5 (s5 ) f4 (s4 ) 最优决策x4 * v7 v7→v10 v10 5 5+0=5* 5 v7→ v10 v8 v8→v10 v10 8 8+0＝8 * 8 v8→ v10 v9 v9→v10 v10 4 4+0=4* 4 v9→ v10 8.1 动态规划数学模型 Mathematical Model of DP