《运筹学》课程授课教案（讲稿）第24讲 动态规划模型及求解方法

课程名称：《运筹学》第_21_讲次授课题目动态规划模型及求解方法本讲目的要求及重点难点：「目的要求]1、掌握动态规划基本思想和基本方程2、牢固掌握动态规划的顺序解法和逆序解法。会处理动态与静态规划的关系【重点及难点】动态规划的求解方法。内容[本讲课程的引入]本讲我们开始学习动态规划的求解方法。[本讲课程的内容]三、动态规划模型及求解方法1、动态规划的数学模型1.动态规划的基本方程动态规划的基本方程是建立动态规划模型的关键。设第k阶段处于状态St，决策是u（s），状态转移方程为sk+I=Tk（sk，uk），k阶段和k+1阶段的递推关系式可以写为：[fi(s#)= opt [ve(Sk,us)* fk(Sk+1)]k =n,n-1,.,](7.2a)ueD,(s)(Jn+1(s+)=0或1(7.2b)式（7.2a)中运算符号*表示加“+”或乘“×”。当运算符号取加法时，边界条件f+1（s+1）=0，当运算符号取乘法时，边界条件fa+1（s+1）=1。求解时，根据边界条件从k=n开始，由后向前逆推，逐步求得各段最优决策和相应的最优值，最后求得f（s），得到整个问题的最优解。这种由后向前计算最优解的方法称为逆序解法（backwardinductionmethod），相应的基本方程称为逆序解法基本方程。2.建立动态规划模型的步骤（1）划分阶段（2）正确选择状态变量Sk（3）确定决策变量u及允许决策集合Dk（sk）（4）确定状态转移方程（5）确定阶段指标函数和最优指标函数，建立动态规划基本方程

课程名称：《运筹学》 第 21 讲次 授课题目 动态规划模型及求解方法 本讲目的要求及重点难点： 目的要求] 1、掌握动态规划基本思想和基本方程 2、牢固掌握动态规划的顺序解法和逆序解法。会处理动态与静态规划的关系 [重点及难点] 动态规划的求解方法。 内 容 [本讲课程的引入] 本讲我们开始学习动态规划的求解方法。 [本讲课程的内容] 三、 动态规划模型及求解方法 1、动态规划的数学模型 1. 动态规划的基本方程 动态规划的基本方程是建立动态规划模型的关键。设第 k 阶段处于状态 sk，决策是 uk（sk），状态 转移方程为 sk+1=Tk（sk，uk），k 阶段和 k+1 阶段的递推关系式可以写为：               ( ) 0 1 (7.2 ) ( ) [ ( , ) ( )] , 1, ,1 (7.2 ) 1 1 1 1 ( ) f s b f s opt v s u f s k n n a n n k k k k k u D s k k k k k 或  式(7.2a)中运算符号*表示加“＋”或乘“×”。当运算符号取加法时，边界条件 fn+1（sn+1）=0，当运 算符号取乘法时，边界条件 fn+1（sn+1）=1。求解时，根据边界条件从 k=n 开始，由后向前逆推，逐 步求得各段最优决策和相应的最优值，最后求得 f1（s1），得到整个问题的最优解。这种由后向前计 算最优解的方法称为逆序解法（backward induction method），相应的基本方程称为逆序解法基本方程。 2. 建立动态规划模型的步骤 （1）划分阶段 （2）正确选择状态变量 sk （3）确定决策变量 uk及允许决策集合 Dk（sk） （4）确定状态转移方程 （5）确定阶段指标函数和最优指标函数，建立动态规划基本方程

内容2、动态规划的求解方法逆序解法是求解动态规划问题的一般常用方法，即由k-n递推至k=1得到问题的最优解。下面通过举例阐述动态规划建模及求解。例7-4用动态规划方法解下列非线性规划问题max z= xi -x2 -x3X+X2+X≤c[x, ≥0 =1,2,3解解决这一类静态规划问题，需要人为地赋予时间概念，从而将该问题转化为多阶段决策过程。按问题的变量个数划分阶段，把它看作一个三阶段决策问题，k=1，2，3设状态变量为S1，S2，S3，S4并记s,≤c取问题中的变量x1，x2，x3为决策变量状态转移方程为：S3-X3S2+Xi=S1≤cS3+X2=S2允许决策集合为：X3=S30≤≤20≤x≤s1各阶段指标函数为：V（x）=X2（x2）=x2V3（xs）=x3，各指标函数以乘积方式结合，最优指标函数f（s）表示从第k阶段初始状态Ss出发到第3阶段所得到的最大值，则动态规划基本方程为：[Jr(sk) =max [vx(xx)- Jk+1(Sk+1)]k = 3,2,1XED,(S)(f4(s4)=1用逆序解法由后向前依次求解：k=3时,=$3f(s,)= max [y (x,)-f(s4)]=max(x)= S33E()k=2 时,f2(s,)= max [vz(x2).f(s,)]= max (x2 .s,)= max [x2 -(s, -x2)ELSISSX2 SS2令h2(s2，X2）=x2（s2—x2)用经典解析法求极值点：

内 容 2、动态规划的求解方法 逆序解法是求解动态规划问题的一般常用方法，即由 k=n 递推至 k=1 得到问题的最优 解。下面通过举例阐述动态规划建模及求解。 例 7-4 用动态规划方法解下列非线性规划问题            0 1,2,3 max 1 2 3 3 2 1 2 x i x x x c z x x x i 解 解决这一类静态规划问题，需要人为地赋予时间概念，从而将该问题转化为多阶段 决策过程。 按问题的变量个数划分阶段，把它看作一个三阶段决策问题，k=1，2，3 设状态变量为 s1，s2，s3，s4 并记 s1≤c 取问题中的变量 x1，x2，x3 为决策变量 状态转移方程为：s3=x3 s3+x2=s2 s2+x1=s1≤c 允许决策集合为：x3=s3 0≤x2≤s2 0≤x1≤s1 各阶段指标函数为：v1（x1）=x1 v2（x2）=x2 2 v3（x3）=x3，各指标函数以乘 积方式结合，最优指标函数 fk（sk）表示从第 k 阶段初始状态 sk出发到第 3 阶段所得到的 最大值，则动态规划基本方程为：            ( ) 1 ( ) max [ ( ) ( )] 3,2,1 4 4 1 1 ( ) f s f s v x f s k k k k k x D s k k k k k 用逆序解法由后向前依次求解： k=3 时， 3 3 4 4 3 3 ( ) 3 3 ( ) max [ ( ) ( )] max( ) 3 3 3 3 3 f s v x f s x s x D s x s       x3 * =s3 k=2 时， ( ) max [ ( ) ( )] max ( ) max [ ( )] 2 2 2 2 0 3 2 2 0 2 2 3 3 ( ) 2 2 2 2 2 2 2 2 2 f s v x f s x s x s x x D s x s x s             令 h2（s2，x2）=x2 2（s2－x2） 用经典解析法求极值点：

内容2dh = 2x 52 -3x =0解得：X2=X2=0（舍）=S23dx2d'hd'h,=2s,-6x=-2s,<02dx2dx2x2=s232所以x,=S是极大值点。32242(s2)=(gs)(s2 -s)=X2==S2-S233273k=1 时,44s2)f(s,)= max [y(x)- f,(s,)]= max(x) -x)31=max[x,(S,2727ED(s)0x≤s0≤m≤s14(s, -x,)3令h(s,x)=x27dh,_412(s, -x)3 +x, (s -x)’(-1) = 0dx,27271解得：x,=二Xi=SI（舍）d'h,121_122424-x)2+3-x,)(-1)x(s -x)=(s -x,)(2x, -s))(s(s,272727dx?27d'h.92s<01dx?27X.=-S141所以x=一s,是极大值点。41411s)3=AS(s)=5xi =-si(SI-274644由于s.未知，所以对s.再求极值，1st)max f (s ) = max(055Sc0sssc 641显然si=c时，fi（si）取得最大值fi(s,)=64反向追踪得各阶段最优决策及最优值：1￥1*1Xi--fi(s,) =Si=CX64

内 容 2 3 0 2 2 2 2 2 2  x s  x  dx dh 解得： 2 2 3 2 x  s x2=0（舍） 2 2 2 2 2 2 2s 6x dx d h   2 0 3 2 2 2 2 2 2 2 2     s dx x s d h 所以 2 2 3 2 x  s 是极大值点。 3 2 2 2 2 2 2 2 27 4 ) 3 2 ) ( 3 2 f (s )  ( s s  s  s 2 * 2 3 2 x  s k=1 时， ( ) ] 27 4 ) max [ 27 4 ( ) max [ ( ) ( )] max ( 3 1 1 1 0 3 1 2 0 1 1 2 2 ( ) 1 1 1 1 1 1 1 1 1 f s v x f s x s x s x x D s x s x s             令 3 1 1 1 1 1 1 ( ) 27 4 h (s , x )  x  s  x ( ) ( 1) 0 27 12 ( ) 27 4 2 1 1 1 3 1 1 1 1  s  x  x s  x   dx dh 解得： 1 1 4 1 x  s x1=s1（舍） ( )(2 ) 27 24 ( ) 27 24 ( ) 27 12 ( ) ( 1) 27 12 1 1 1 1 1 1 1 2 1 1 2 2 1 1 1 1 2 s x s x x s x s x x s dx d h           0 27 9 4 1 2 1 1 1 2 1 1 2     s dx x s d h 所以 1 1 4 1 x  s 是极大值点。 4 1 3 1 1 1 1 1 64 1 ) 4 1 ( 27 4 4 1 f (s )  s  s  s  s 1 * 1 4 1 x  s 由于 s1未知，所以对 s1 再求极值， ) 64 1 max ( ) max( 4 1 0 1 1 0 1 1 f s s s c s c  显然 s1=c 时，f1（s1）取得最大值 4 1 1 64 1 f (s )  c 反向追踪得各阶段最优决策及最优值： s1=c x s c 4 1 4 1 1 * 1   4 1 1 64 1 f (s )  c

内容13243-1c3f2(s2)=S, = S,XS2=-C32272164111xj=Ss=fs(ss)= Ss S, =S2 -X2XL4.11*1*-1c4所以最优解为：x, =c=2cfC,z4464一般地，如果阶段指标函数vk（sk，u）是线性函数或凸函数时，最优指标函数f（sk）的表达式比较容易得到，但是当v（sk，u）不具备上述特性时，最优指标函数f（s）的表达式不易得到，就需要采用数值法，即对连续变量进行离散化处理，再分散求解。例如静态规划模型max z=gi(x)+g2(x,)+...+g,(x,)X+x2++x.=a{x, ≥0 j=1,2,.,n其动态规划基本方程为：[ft(s.)= max [g:(x)+ Jk(Sk+1)]k=n,n-l,...,lKREDK(SA[fn+I(sn+1)= 0状态转移方程为Sk+=Sk-XkSi=a状态变量S及决策变量x都是连续变量，对其进行离散化处理，具体做法是：a1.对区间[0，a]进行分割，分割数m=，其中是分割后的小区间的长度，其大小△可以根据所求解问题要求的精度及计算机运算能力而定，分割点为0，△，2△，…，m△=a.2.规定状态变量Sk及决策变量x仅在离散点0，△，2△，，m△处取值，最优指标函数（s）也定义在这些离散点上。动态规划基本方程可以写为：k=n,n-l,...,lft(s)=max [g(pA)+ fk+I(s-pA)(Un+I(sn+1) = 0其中=，。3.由后向前逐段递推，直至求出整个过程最优解。例5-5max z=x.x2 -xjx+x2+x≤6[x, ≥0 j=1,2,3

内 容 s s x c 4 * 3 2  1  1  x s c 2 1 3 2 2 * 2   3 3 2 2 2 16 1 27 4 f (s )  s  c s s x c 4 * 1 3  2  2  x s c 4 1 3 * 3   f s s c 4 1 ( ) 3 3  3  所以最优解为： * * 4 3 * 2 * 1 64 1 , 4 1 , 2 1 , 4 1 x  c x  c x  c z  c 一般地，如果阶段指标函数 vk（sk，uk）是线性函数或凸函数时，最优指标函数 fk（sk） 的表达式比较容易得到，但是当 vk（sk，uk）不具备上述特性时，最优指标函数 fk（sk）的 表达式不易得到，就需要采用数值法，即对连续变量进行离散化处理，再分散求解。 例如静态规划模型              x j n x x x a z g x g x g x j n n n 0 1,2, , max ( ) ( ) ( ) 1 2 1 1 2 2    其动态规划基本方程为：               ( ) 0 ( ) max [ ( ) ( )] , 1, ,1 1 1 1 1 ( ) n n k k k k x D s k k f s f s g x f s k n n k k k  状态转移方程为 sk+1=sk－xk s1=a 状态变量 sk 及决策变量 xk都是连续变量，对其进行离散化处理，具体做法是： 1. 对区间[0，a]进行分割，分割数 m=  a ，其中Δ是分割后的小区间的长度，其大小 可以根据所求解问题要求的精度及计算机运算能力而定，分割点为 0，Δ，2Δ，.，mΔ = a。 2. 规定状态变量 sk 及决策变量 xk 仅在离散点 0，Δ，2Δ，.，mΔ处取值，最优指 标函数 fk（sk）也定义在这些离散点上。动态规划基本方程可以写为：                 ( ) 0 ( ) max [ ( ) ( )] , 1, ,1 1 1 1 0,1,2 , n n k k k p q k k f s f s g p f s p k n n   其中 sk=qΔ，xk=pΔ。 3. 由后向前逐段递推，直至求出整个过程最优解。 例 5-5            0 1,2,3 6 max 1 2 3 3 2 3 2 1 x j x x x z x x x j

内容解按变量个数将原问题分为三个阶段，阶段变量k=1，2，3：选择x为决策变量；状态变量s表示第k阶段至第3阶段决策变量之和：取小区间长度△=1，小区间数目m=6/1=6，状态变量s的取值点为[s+ = 0,1,2,3,4,5,6k≥2(s; = 6状态转移方程：Sk+1=Sk一Xk；允许决策集合：Dk（s）=（xl0≤x≤sh）k=1,2,3x，s均在分割点上取值；阶段指标函数分别为：g1（xi）=xg3（x3）=x3，最优指82（x2）=x2标函数f（sk）表示从第k阶段状态ss出发到第3阶段所得到的最大值，动态规划的基本方程为：[fe(s)= max [gx(xx)- fk(Sk+1)]k = 3,2,10≤XSs)(f4(s4)=1k=3时,Js(ss)= max(xs)= s)3;sS3及x取值点较多，计算结果以表格形式给出，见表5-1所示。表5-1xx3J(ss)2013456000011122883272734464 645512512562162166

内 容 解 按变量个数将原问题分为三个阶段，阶段变量 k=1，2，3； 选择 xk为决策变量； 状态变量 sk 表示第 k 阶段至第 3 阶段决策变量之和； 取小区间长度Δ=1，小区间数目 m=6/1=6，状态变量 sk的取值点为：       6 0,1,2,3,4,5,6 2 1 s s k k 状态转移方程：sk+1=sk－xk； 允许决策集合：Dk（sk）=｛xk|0≤xk≤sk｝ k=1，2，3 xk，sk 均在分割点上取值； 阶段指标函数分别为：g1（x1）=x1 2 g2（x2）=x2 g3（x3）=x3 3，最优指 标函数 fk（sk）表示从第 k 阶段状态 sk出发到第 3 阶段所得到的最大值，动态规划的基本 方程为：             ( ) 1 ( ) max [ ( ) ( )] 3,2,1 4 4 1 1 0 f s f s g x f s k k k k k x s k k k k k=3 时， 3 3 3 3 3 3 ( ) max( ) 3 3 f s x s x s    s3 及 x3 取值点较多，计算结果以表格形式给出，见表 5-1 所示。 表 5-1 x3 3 f3(s3) x3 * 0 1 2 3 4 5 6 0 1 2 3 4 5 6 0 1 8 27 64 125 216 0 1 8 27 64 125 216 0 1 2 3 4 5 6 f x3 s3

内容k=2时，f2(s2)= max [x2 : fe(s,)]= max [x2 fs(s2 -x2)]0SX2S3Sx2Ss计算结果见表5-2所示。表5-2X2fs(s2-X2)(s2)X223045S2160000000,111x0202x01x111301X82X13X081403x14x0271X272×81501 X 642X275x06413X84x1012821X1253X274X85X16X062X64k=1 时,f,(s,) = max[x? . f(s,)]= max[x? . f,(s, -x,)]0Sx≤s0Sx≤s其中si=6，计算结果见表5-3所示。表5-3x f(si-x1)xifi(st)X02345616021 X 644X279X816×125X036X0108由表5-3知，xl=2，Si=6，则s2=S1—x=6—2=4，查表5-2得：x2=1，则s-S2—x2=41=3，查表5-1得：x3=3，所以最优解为：x=2，xz=1，x3=3，f(s)=108

内 容 k=2 时， ( ) max [ ( )] max [ ( )] 2 3 2 2 0 2 3 3 0 2 2 2 2 2 2 f s x f s x f s x x s x s          计算结果见表 5-2 所示。 表 5-2 x2 f3(s2－x2) f2(s2) x2 * 0 1 2 3 4 5 6 0 1 2 3 4 5 6 0 0 0 0 0 0 0 1×0 1×1 1×8 1×27 1×64 1×125 2×0 2×1 2×8 2×27 2×64 3×0 3×1 3×8 3×27 4×0 4×1 4×8 5×0 5×1 6×0 0 0 1 8 27 64 128 0 0,1 1 1 1 1 2 k=1 时， ( ) max [ ( )] max [ ( )] 2 1 1 2 1 0 2 2 2 1 0 1 1 1 1 1 1 f s x f s x f s x x s x s          其中 s1=6，计算结果见表 5-3 所示。 表 5-3 x1 2 f2(s1－x1) f1(s1) x1 * 0 1 2 3 4 5 6 6 0 1×64 4×27 9×8 16×1 25×0 36×0 108 2 由表 5-3 知，x1 * =2，s1=6，则 s2= s1－x1 * =6－2=4，查表 5-2 得：x2 * =1，则 s3= s2－x2 * =4 －1=3，查表 5-1 得：x3 * =3，所以最优解为：x1 * =2，x2 * =1，x3 * =3，f1(s1)=108。 f x2 s2 f x1 s1

容内[本讲小结】今天我们给大家重点介绍了动态规划方程及其求解方法。[本讲课程的作业]136页第一题

内 容 [本讲小结] 今天我们给大家重点介绍了动态规划方程及其求解方法。 [本讲课程的作业] 136 页第一题