智能优化-动态规划

1、 4 动态规划动态规划 4.1 多阶段决策问题与动态规划 4.2 动态规划的基本概念 4.3 动态规划的步骤 4.4 动态规划的应用 1 求解静态规划问题 2 资源分配问题 3 背包问题 4 库存问题4.1 多阶段决策问题与动态规划多阶段决策问题与动态规划例1最 短 路 问 题求求AG的最短路径？的最短路径？ 例例2 2 机器负荷分配问题机器负荷分配问题 某种机器可以在高低两种不同的负荷下进行生产在高负荷下进行生产时，产品的年产量g和投入生产的机器数量u的关系为 gg(u), 这时机器的年完好率为a（0a1)在低负荷下生产时，产品的年产量h和投入生产的机器数量v的关系为hh(v), 这时机器的

2、年完好率为b（ab1）假定开始生产时完好的机器数量为s1，要求制定一个五年计划,在每年开始时决定机器在两种不同负荷下生产的数量,使五年内产品的总产量最高。以上两个问题都可以划分为先后多个决策阶段。这类问题就称为多阶段决策问题。多阶段决策问题的过程如下图所示： 状态状态状态状态决策决策决策状态 多阶段决策问题和我们前面遇到的决策问题不同，它是和时间有关的。与时间有关的活动过程称为动态过程，其优化方法称为动态规划。而与时间无关的活动过程称为静态过程，相应的的优化方法称为静态规划。最优性原理最优性原理作为整个过程的最优策略具有这样的性质，作为整个过程的最优策略具有这样的性质，无论过去的状态和决策如何

3、，相对于前面无论过去的状态和决策如何，相对于前面决策所形成的状态，余下的决策序列必然决策所形成的状态，余下的决策序列必然构成最优子序列。构成最优子序列。这种过去的状态和决策对于今后的决策所形成的状态没有影响，也称为无后效性无后效性或者马尔可夫性。 (1)阶段（stage）把所研究的决策问题，按先后顺序划分为若干相互联系的决策步骤，以便按一定的次序进行求解。描述阶段的变量称阶段变量，常用k表示。 (2)状态（state）状态表示每个阶段开始时所处的自然状况或客观条件，它描述了影响决策的因素随决策进程的变化情况，它既是前面阶段所作决策的结果，又是本阶段作出决策的出发点和依据。描述状态的变量称为状态

4、变量，第k阶段的状态变量常用sk表示。通常，在第一阶段状态变量s1是确定的，称初始状态。 (3)决策（decision）决策表示在某一阶段处于某种状态时，决策者在若干种方案中作出的选择决定。描述决策的变量称决策变量，第k阶段的决策变量常用uk表示。决策变量的取值会受到状态变量的制约，被限制在某一范围之内。4.2 动态规划的基本概念（一） (4)策略（policy）把从第一阶段开始到最后阶段终止的整个决策过程，称为问题的全过程；而把从第k阶段开始到最后阶段终止的决策过程，或称为k子过程。在全过程上，各阶段的决策按顺序排列组成的决策序列p1,n u1,u2,un 称为全过程策略，简称 策 略 ；

5、而 在 k 子 过 程 上 的 决 策 序 列 pk , n uk,uk+1,un 称为k子过程策略，简称子策略。 (5)状态转移方程 若第k阶段的状态变量值为sk，当决策变量uk的取值决定后，下一阶段状态变量sk+1的值也就完全确定。即sk+1的值对应于sk和uk的值。这种对应关系记为sk+1Tk(sk,uk)，称为状态转移方程。状态转移方程描述了由一个阶段的状态到下一阶段的状态的演变规律。 (6)6)指标函数和最优值函数指标函数和最优值函数 指标函数分为指标函数分为阶段指标阶段指标函数和函数和过程指标函数。阶段指标函数是对某一阶段的状态和决策产过程指标函数。阶段指标函数是对某一阶段的状态和

6、决策产生的效益值的度量，用生的效益值的度量，用v vk k(s(sk k,u,uk k) )表示。表示。过程指标过程指标函数是指过函数是指过程所包含的各阶段的状态和决策所产生的总的效益值，记为程所包含的各阶段的状态和决策所产生的总的效益值，记为 V Vk,nk,nV Vk,nk,n(s(sk k,u,uk k,s,sk+1k+1,u,uk+1k+1, ,s,sn n,u,un n) ) 动态规划所要求的过程指标函数应具有可分离性，即可表动态规划所要求的过程指标函数应具有可分离性，即可表达为它所包含的各阶段指标函数的函数形式。常见的两种过达为它所包含的各阶段指标函数的函数形式。常见的两种过程指标

7、函数形式是：程指标函数形式是： 各阶段指标函数的和各阶段指标函数的和 V Vk,nk,nvvj j(s(sj j,u,uj j) )； 各阶段指标函数的积各阶段指标函数的积 V Vk,nk,nvvj j(s(sj j,u,uj j) )。 把过程指标函数把过程指标函数V Vk,nk,n对对k k子过程策略子过程策略p pk,nk,n求最优，得到一个求最优，得到一个关于状态关于状态s sk k的函数，称为最优值函数，记为的函数，称为最优值函数，记为f fk k(s(sk k) )。即即 f fk k(s(sk k) ) opt V opt Vk,nk,n(s(sk k,u,uk k, ,s,sn

8、 n,u,un n) ) u uk k, ,u,un n式中式中的的“opt”opt”（optimizationoptimization）根据具体问题而取根据具体问题而取minmin或或maxmax。 (7)基本方程 通常动态规划问题的最优值函数满足递推关系式。设过程指标函数为各阶段指标函数的和的形式，即Vk,nvj(sj,uj)，则有 fk(sk) opt vk(sk,uk)+fk+1(sk+1) ukDk(sk) (kn,n-1,1) 递推方程 fn+1(sn+1)0 边界条件递推方程和边界条件一起称为动态规划的基本方程。 可根据边界条件，从k=n开始，由后向前逆推，逐步求得各阶段的最优决

9、策和相应的最优值，最后求出f1(s1)时，就得到整个问题的最优解。 例 最 短 路 问 题此问题的基本方程为此问题的基本方程为fk(sk)Mindk(uk)+fk+1(sk+1) ukDk(sk) k6,5,4,3,2,1f7(s7)04.3 动态规划的步骤（一）动态规划的步骤（一）当k=6时s6 u6 D(u6)+f7(s7) F6(s6) F1 F1G 4+0=4* 4 F2 F2G 3+0=3* 3 按基本方程由后向前按基本方程由后向前继续继续递推有递推有:当k=5时当k=4时s4 u4 d(u4)+f5(s5) f4(s4) D1 D1E1 D1E2 2+7=9 2+5=7* 7 D2

10、 D2E2 D2E3 1+5=6* 2+9=11 6 D3 D3E2 D3E3 3+5=8* 3+9=12 8 s s5 5 u u5 5 d d( (u u5 5) )+ +f f6 6( (s s6 6) ) f f5 5( (s s5 5) ) E E1 1 E E1 1F F1 1 E E1 1F F2 2 3 3+ +4 4= =7 7* * 5 5+ +3 3= =8 8 7 7 E E2 2 E E2 2F F1 1 E E2 2F F2 2 5 5+ +4 4= =9 9 2 2+ +3 3= =5 5* * 5 5 E E3 3 E E3 3F F1 1 E E3 3F F2

11、 2 6 6+ +4 4= =1 10 0 6 6+ +3 3= =9 9* * 9 9 当当k=3时时s s3 3 u u3 3 d d( (u u3 3) )+ +f f4 4( (s s4 4) ) f f3 3( (s s3 3) ) C C1 1 C C1 1D D1 1 C C1 1D D2 2 6 6+ +7 7= =1 13 3* * 8 8+ +6 6= =1 14 4 1 13 3 C C2 2 C C2 2D D1 1 C C2 2D D2 2 3 3+ +7 7= =1 10 0* * 5 5+ +6 6= =1 11 1 1 10 0 C C3 3 C C3 3D D

12、2 2 C C3 3D D3 3 3 3+ +6 6= =9 9* * 3 3+ +8 8= =1 11 1 9 9 C C4 4 C C4 4D D2 2 C C4 4D D3 3 8 8+ +6 6= =1 14 4 4 4+ +8 8= =1 12 2* * 1 12 2 当当k=2时时当当k=1时时s s2 2 u u2 2 d d( (u u2 2) )+ +f f3 3( (s s3 3) ) f f2 2( (s s2 2) ) B B1 1 B B1 1C C1 1 B B1 1C C2 2 B B1 1C C3 3 1 1+ +1 13 3= =1 14 4 3 3+ +1

13、10 0= =1 13 3* * 6 6+ +9 9= =1 15 5 1 13 3 B B2 2 B B2 2C C2 2 B B2 2C C3 3 B B2 2C C4 4 8 8+ +9 9= =1 17 7 7 7+ +9 9= =1 16 6* * 6 6+ +1 12 2= =1 18 8 1 16 6 s s1 1 u u1 1 d d( (u u1 1) )+ +f f2 2( (s s2 2) ) f f1 1( (s s1 1) ) A A A AB B1 1 A AB B2 2 5 5+ +1 13 3= =1 18 8* * 3 3+ +1 16 6= =1 19 9

14、1 18 8 由此可以看出，由此可以看出，A到到G的最短路长为的最短路长为18，路径为：，路径为： AB1C2D1E2F2G现在把动态规划法的步骤归纳如下：现在把动态规划法的步骤归纳如下：(1) (1) 将所研究问题的过程划分为将所研究问题的过程划分为n n个恰当的阶段，个恰当的阶段， k k 1,2, 1,2,n,n；(2) (2) 正确地选择状态变量正确地选择状态变量S Sk k，并确定初始状态并确定初始状态S S1 1的值；的值；(3) (3) 确定决策变量确定决策变量u uk k以及各阶段的允许决策集以及各阶段的允许决策集D Dk k(S(Sk k) )；(4) (4) 给出状态转移方

15、程；给出状态转移方程；(5) (5) 给出满足要求的过程指标函数给出满足要求的过程指标函数V Vk,nk,n及相应的最优及相应的最优 值函数；值函数；(6) (6) 写出递推方程和边界条件，建立基本方程；写出递推方程和边界条件，建立基本方程；(7) (7) 按照基本方程递推求解。按照基本方程递推求解。 以上步骤是动态规划法处理问题的基本步骤，其以上步骤是动态规划法处理问题的基本步骤，其中的前六步是建立动态规划模型的步骤。中的前六步是建立动态规划模型的步骤。4.3 动态规划的步骤（二）动态规划的步骤（二）例例2 2：机器负荷问题：机器负荷问题 某种机器可以在高低两种不同的负荷下进行生某种机器可以

16、在高低两种不同的负荷下进行生产在高负荷下进行生产时，产品的年产量产在高负荷下进行生产时，产品的年产量g g和和投入生产的机器数量投入生产的机器数量u u的关系为的关系为 g g8u, 8u, 这时机这时机器的年完好率为器的年完好率为a=0.7a=0.7在低负荷下生产时，产在低负荷下生产时，产品的年产量品的年产量h h和投入生产的机器数量和投入生产的机器数量v v的关系为的关系为h h5v, 5v, 这时机器的年完好率为这时机器的年完好率为b=0.9b=0.9假定开始假定开始生产时完好的机器数量为生产时完好的机器数量为s s1 110001000，要求制定一，要求制定一个五年计划个五年计划, ,

17、在每年开始时决定机器在两种不同在每年开始时决定机器在两种不同负荷下生产的数量负荷下生产的数量, ,使五年内产品的总产量最高。使五年内产品的总产量最高。(1)按年数划分为5个阶段，k=1,2,3,4,5(2)取第k年初完好的机器数sk为状态变量, s1=1000(3)取第k年投入高负荷的机器数xk为决策变量, 0 xksk(4)状态转移方程为 sk+1=0.7xk+0.9(sk-xk)=0.9sk-0.2xk(5)指标函数为Vk,5=8xj+5(sj-xj)=(5sj+3xj)(6)基本方程为 fk(sk) max 5sk+3xk +fk+1(sk+1) k=5,4,3,2,1 0 xksk f

18、6(s6)0解解:当k=5时f5(s5) max5s5+3x5+f6(s6)= max5s5+3x5=8s5 (x5*=s5) 0 x5s5 0 x5s5当k=4时f4(s4)max5s4+3x4+8s5=max5s4+3x4+8(0.9s4-0.2x4) 0 x4s4 0 x4s4 = max12.2s4+1.4x4=13.6s4 (x4*=s4) 0 x4s4当k=3时f3(s3)max5s3+3x3+13.6s4=max5s3+3x3+13.6(0.9s3-0.2x3) 0 x3s3 0 x3s3 = max17.24s3+0.28x3=17.5s3 (x3*=s3) 0 x3s3当k=

19、2时f2(s2)=max5s2+3x2+17.52s3=max5s2+3x2+17.52(0.9s2-0.2x2) 0 x2s2 0 x2s2 = max20.77s2-0.504x2=20.7s4 (x2*=0) 0 x2s2当k=1时f1(s1)=23.7s1 (x1*=0)f1(1000)=23700s1=1000, x1*=0s2=900, x2*=0s3=810, x3*=810s4=576, x4*=576s5=397, x5*=397 某些静态规划问题可用动态规划法来求解。某些静态规划问题可用动态规划法来求解。 例例 用动态规划法求解用动态规划法求解 max z=x1.x22.x

20、3 x1+x2+x3=c xi0 i=1,2,34.4 动态规划的应用动态规划的应用(一一) 1 求解静态规划问题求解静态规划问题该题在课本该题在课本p145页例页例3解: 把问题看成一个三阶段决策问题，对应关系状态变量: s1, s2, s3, s4; sk表示从第k阶段到最后 一个阶段可以分配的资源，s1=c 。决策变量： x1,x2,x3,x3 ; s.t. 0=xk=sk;允许决策集: Dk(sk)=xk| 0=xk0所以 d2(x2)=d2|13-x2d217-x2由此 f2(x2)=5(13-x2)-13x2+377 =-18x2+442, d2*=13-x2对于k=1f1(x1)

21、=minc1d1+f2(x2) d1D1(x1) =min11d1+442-18x2 d1D1(x1) =min11d1+442-18(x1-r1+d1) d1D1(x1) =min11d1+442-18(x1-0+d1) d1D1(x1) =min-7d1-18x1+442 d1D1(x1) D D1 1( (x x1 1)=)=d d1 1| |d d1 1 0,0,r r2 2 x x1 1- -r r1 1+ +d d1 1 H H = =d d1 1| |d d1 1 0,0,r r2 2+ +r r1 1- -x x1 1 d d1 1 H H+ +r r1 1- -x x1 1

22、= =d d1 1| |d d1 1 0,8-0,8-x x1 1 d d1 1 9-9-x x1 1 根据题意 x1=2所以 D1(x1)=d1| 6d17由此 d1=7f1(x1)=-7d1-18x1+442 =-77182442 =357将以上结果总结成下表：k 1 2 3 4 5 6 7 ck 11 18 13 17 20 10 15 rk 0 8 5 3 2 7 4 xk 2 9 5 9 9 7 4 dk 7 13-x2=4 14-x3=9 12-x4=3 9-x5=0 11-x6=4 0 设设 备备 更更 新新 问问 题题 一台设备的价格为P，运行寿命为n年，每年的维修费用是设备役

23、龄的函数，记为C(t)，新设备的役龄为t=0。旧设备出售的价格是设备役龄的函数，记为S(t)。在n年末，役龄为t的设备残值为R(t)。现有一台役龄为T的设备，在使用过程中，使用者每年都面临“继续使用”或“更新”的策略，设设 备备 更更 新新 问问 题题阶段k：运行年份； 状态变量xk：设备的役龄t； 决策变量dk： 继续使用更新)()(ReKeepKplaceRdk 状态转移方程： KdxRdxkkkk111 阶段指标： KdtCRdtSCPKdxCRdxSCPvkkkkkkk)()()0()()()0( 递推方程： KdtftCRdftSCPKdxfxCRdxfxSCPxfkkkkkkkkk

24、kkkkk) 1()() 1 ()()0(min)()()()()0(min)(111111 终端条件： fn(t)=-R(t) 设设 备备 更更 新新 问问 题题例5.10：设具体数据如下：T 0 1 2 3 4 5 6 7 C(t) 10 13 20 40 70 100 100 - S(t) - 32 21 11 5 0 0 0 R(t) - 25 17 8 0 0 0 0 且 n=5，T=2，P=50 由上表开始，终端条件为： f6(1)=-25，f6(2)=-17，f6(3)=-8 f6(4)=f6(5)=f6(6)=f6(7)=0 对于k=5: KdRdtftCftSCPtf5566

25、5) 1()() 1 ()() 0(min)( KdfCfSCPf*5665, 443min)17(13)25(321050min) 2() 1 () 1 () 1 () 0 (min) 1 ( KdfCfSCPf*5665,121214min) 8(20)25(211050min) 3 () 2() 1 () 2() 0 (min) 2( RdfCfSCPf*5665,244024min040)25(111050min) 4() 3() 1 () 3() 0(min) 3( RdfCfSCPf*5665,307030min070)25(51050min)5()4() 1 ()4()0(min

26、)4(RdfCfSCPf*5665,3510035min0100)25(01050min) 6() 5 () 1 () 5 () 0(min) 5 (RdfCfSCPf*5665,3510035min0100)25(01050min) 7() 6() 1 () 6() 0(min) 6( KdRdtftCftSCPtf44554) 1()() 1 ()() 0 (min)( RdfCfSCPf*4554,242524min1213) 4(321050min) 2() 1 () 1 () 1 () 0(min) 1 ( 对于k=4: RdfCfSCPf*4554,354435min2420)4(211050min)3()2()1 ()2()0(min)2( RdfCfSCPf*4554,457045min3040)4(111050min)4()3() 1 ()3()0(min)3( RdfCfSCPf*4554,5110551min3570) 4(51050min) 5 () 4() 1 () 4() 0(min) 4( RdfCfSCPf*5554,