动态规划理论部分

1、动态规划理论部分第一页，共53页。 动态规划是解决多阶段决策过程最优化问题的一种方法。在二十世纪五十年代由美国数学家理查德.贝尔曼(RichardBa11man)首先提出的。它可以把一个 n 维最优化问题转化为 n 个一维最优化问题来求解。 一个决策问题，往往可以分解成若干个相互联系，又相对独立的阶段，对于每一个阶段，存在着很多方案可供选择，我们要对每个阶段作出一个决策。 而各阶段之间又有密切的联系，某一个阶段的不同决策，将会对其它阶段的决策产生重大的影响，某个阶段局部的较优方案，未必是整个问题的最好方案，某个阶段局部的不好方案，也未必是整个问题的不好方案。 我们要寻找的是整个问题，也就是所有

2、阶段总体的一个最优方案，这就是动态规划所要讨论的问题。第二页，共53页。一、多阶段决策问题 所谓多阶段决策问题是有这样一类决策过程，它可以划分为若干个相互联系的阶段，在任一阶段都有若干种方案可供选择，选择哪一种方案需要作出决策，这样就形成一个决策序列，通常称为一种策略。不同的策略就产生不同的效果，在所有可能的策略当中，选择一个效果最好的最优策略，就是解决多阶段决策问题的主要目的。下面举几个例子来说明。第三页，共53页。 例1： （最短路程问题）设从A地到E地要铺设一条管道，其中要经过若干个中间点(如图)。图中两点之间连线上的数字表示两地间的距离。现在要选择一条铺设管道的路线，使总长度最短。25

3、11214106104131112396581052C1C3D1 AB1B3B2D2EC2第四页，共53页。 在这个问题中，从A到B 1 ，B2 ， B3中的哪一个点要作出一项决策，从B 1 ，B2 ， B3某点到 C 1，C2，C3 中的哪一个点又要作出一项决策等等。所以总共要作出四个决策。因此，我们可以把整个路程分为A，B ( 包括B 1 ，B2 ， B3) ，C ( 包括C 1，C2 ， C3 ， ) ，D (包括D1和D2)，E 五个阶段。这就是一个多阶段的决策问题。二、动态规划的基本思想 用动态规划求解多阶段决策问题，是把整个问题划分为若干阶段后，依次地为每一个阶段作出最优决策，而每

4、个阶段的最优决策应该是包含本阶段和所有以前各阶段在内的最优决策，也就是到本阶段为止，包含以前各阶段在内的最优总决策。因此，在确定了最后一个阶段的决策之后，整个问题的最优决策序列也就随之产生。这就是用动态规划解多阶段决策问题的基本思想。第五页，共53页。以上面的例1来说明动态规划解决问题的思想。设：Sk-第k阶段的起点（状态变量）dk(x, y) -第k阶段的顶点 x 到顶点 y 的“距离”；fk(Sk) -第k阶段从顶点Sk到终点的最短“路”长。 最短路线的重要特性就是：如果最短路线在第K站通过点Pk。则由点Pk 出发到达终点的这条路线，对于从点Pk 出发到达终点的所有可能选择的不同路经来说，

5、必定也是最短路线。第六页，共53页。例如，在最短路线问题中，如果找到了A到E的最短路：121ABCDE 则 应该是由C2 出发到E点的所有可能不同线路中的最短路线21CDE 最短路线这一特性，启发我们找最短路线的方法：那就是从最后一段开始，用由后向前逐步递推的方法，求出各点到E点的最短路线，最后求得由A点到E点的最短路线。所以，动态规划的常用的方法是从终点逐段向始点方向寻找“最短路线” 。如图所示：行进方向起点终点动态规划寻优途径第七页，共53页。 下面按上述思想，将例1从最后一段开始计算，由后向前逐步推移至A点。2511214106104131112396581052C1C3D1AB1B3B

6、2D2EC2f5(E)=0设想有k 5 时， f5(E) 0 。第八页，共53页。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=04115()(,)( )505fDd D EfEK=4时：第九页，共53页。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=54225()(,)( )202fDd D EfE第十页，共53页。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E

7、)=0f3(C1)=8f4(D1)=5311242114111()min(,)()minmin8最优 决 策9(,)()358211f CC DfDfDC DCDK=3时：第十一页，共53页。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=8222422141223DC7711min2556min)D(f)D,C()D(f)D,C(min)C(f最优决策第十二页，共53页。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)

8、=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=7232423141333DC121213min21058min)D(f)D,C()D(f)D,C(min)C(f最优决策第十三页，共53页。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B1)=20f3(C2)=7f3(C1)=81131211232133311(,)()12820()min (,)()min 147min 2120(,)()10 1222最优 决 策:B Cf CfBB Cf C

9、B Cf CBCK=2时：第十四页，共53页。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B2)=14f3(C2)=7f3(C1)=8f2(B1)=212222322333212131()min (,)()min 107min 1714(,)(,)()4 1216最优 决 策:)6814B CffBB Cf CB Cf CCBC第十五页，共53页。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3

10、)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f2(B1)=21f2(B2)=143131233232333332(,)()13 821()min (,)()min 127min 1919(,)()11 1223最优 决 策:B Cf CfBB Cf CB Cf CBC第十六页，共53页。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=2112113232222(

11、 ,)()22123( )minminmin19( ,)()1 1920最优 决( ,)()5 14策9:1A BfBf AA BfBA BfBABK=1时：第十七页，共53页。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态AB2C1D1E（ A，B2）（ B2 ，C1 ）（ C1 , D1 ）（ D1 ,E）第十八页

12、，共53页。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态A （ A，B2） B2 （B2，C1） C1 （C1，D1） D1 （D1，E） E从A到E的最短路径为19，路线为AB 2C1 D1 E 第十九页，共53页。三、动态规划的基本概念 (1) 阶段（stage） 把所研究的决策问题，按先后顺序划分为若 （2）状

13、态（state） 状态表示每个阶段开始时所处的自然状况或 (3) 决策（decision）决策表示在某一阶段处于某种状态时，决策者在若干种方案中作出的选择决定。描述决策的变量称决策变量，第k阶段的决策变量常用uk表示。决策变量的取值会受到状态变量的制约，被限制在某一范围之内。干相互联系的决策步骤，以便按一定的次序进行求解。描述阶段的变量称阶段变量，常用k表示。客观条件，它描述了影响决策的因素随决策进程的变化情况，它既是前面阶段所作决策的结果又是本阶段作出决策的出发点和依据。描述状态的变量称为状态变量，第k阶段的状态变量常用sk表示。通常，在第一阶段状态变量s1是确定的，称初始状态。第二十页，共

14、53页。T1S1S2V1u1T2S3V2u2TkSkSk+1VkukTnSnSn+1Vnun多阶段决策过程如下：n个决策子问题k称为阶段变量Sk描述k阶段初的状态，即状态变量一般把输入状态称为该阶段的阶段状态。uk的取值代表k阶段对第k子问题所进行的决策，称为k阶段的决策变量Vk为k阶段从状况Sk出发,做出决策uk之后的后果，第二十一页，共53页。(4)策略（policy） 把从第一阶段开始到最后阶段终止的整个决策过程，称为问题的全过程；而把从第k阶段开始到最后阶段终止的决策过程，或称为k子过程。在全过程上，各阶段的决策按顺序排列组成的决策序列 p1,n u1,u2,un 称为全过程策略，简称

15、策略；而在k子过程上的决策序列 pk,n uk,uk+1,un 称为k子过程策略，也简称子策略。第二十二页，共53页。(5)(5)状态转移方程状态转移方程(6)指标函数（准则函数）,目标函数和最优值函数 指标函数分为阶段指标函数和过程指标函数。 阶段指标函数是对某一阶段的状态和决策产生的效益值的度量用Vk(sk,uk)表示。 从第k阶段到最终阶段的过程称为k-后部子过程，简称为：k-子过程。 若第k阶段的状态变量值为sk，当决策变量uk 的取值决定后，下一阶段状态变量Sk+1的值也就完全确定。即Sk+1的值对应于Sk和uk的值。这种对应关系记为: sk+1Tk(sk,uk)，称为状态转移方程。

16、状态转移方程描述了由一个阶段的状态到下一阶段的状态的演变规律。第二十三页，共53页。 过程指标函数是指从第k阶段至第n阶段所包含的各阶段的状态和决策所产生的总的效益值，记为: Vk,nVk,n(Sk,uk,Sk+1,uk+1,Sn,un)TkSkSk+!Vk (Sk,uk)uk (Sk)TnSnSn+1Vn (Sn,un)un (Sn)K子过程 定义在全过程上的准则函数相当于目标函数，一般记为: V1,nV1,n(S1,u1, Sk,uk ,Sn,un)，或简记为V1,n 第二十四页，共53页。,11,()(,)knkkk nkkkknnuufSopt VSuSuSu()kkfS 把过程指标函

17、数Vk,n对k子过程策略pk,n求最优，得到一个关于状态Sk的函数，称为最优值函数或贝尔曼函数，记为: 。即各阶段指标函数的和: ,(,)nk njjjj kVV S u,(,)nk njjjj kVV S u各阶段指标函数的积: 动态规划所要求的过程指标函数应具有可分离性，即可表达为它所包含的各阶段指标函数的函数形式。常见的两种过程指标函数形式是： 也就是说在阶段k从初始状态Sk出发，执行最优决策序列或策略，到达过程终点时，整个k-子过程中的最优目标函数取值。第二十五页，共53页。 式中式中的的“optopt”（optimizationoptimization）可根据具体问题的可根据具体问题

18、的实际实际意而取意而取minmin或或maxmax。,()(,)knnkkjjjuuj kfSoptV S u,()(,)knnkkjjjuuj kfSoptVSu或第二十六页，共53页。,1,1,11,1,11,11()(;)(,)(;)(,)(;)(,)()k nk nkkknkkkkk nkk npkkkknkknpkkkknkknuUpkkkkkuUfSoptvSpopt vSuVSpopt vSuoptVSpopt vSufS由最优性定理可知：四、动态规划基本方程 逆序法由此逆序算法的递归方程如下：第二十七页，共53页。 其中：fk(sk)表示第k阶段初始状态为sk 时，k后部子过程

19、的最优准则函数 。1111()(,)()()0kkkkkkkkkuUnnfsopt vs ufsfs逆序递归方程：1(,)kkkksT s u状态转移方程：第二十八页，共53页。正序递归方程：1100()(,)()()0kkkkkkkkkuUfsopt vs ufsfs111(,)kkkksTs u状态转移方程： 其中：fk(sk)表示第k阶段初始状态为sk 时，k前部子过程的最优准则函数 。第二十九页，共53页。 动态规划建模有以下过程：确定阶段与阶段变量明确状态变量和状态可能集合。确定决策变量和决策允许集合。确定状态转移方程。明确阶段效应和目标。五、动态规划的建模第三十页，共53页。k=n

20、时，动态规划基本方程是 11() (,)()nnnnnnnnufSopt v S ufS11()0nnfx边界条件：() (,)nnnnnnufSopt v S u即 ：逆序地求出条件最优目标函数值集合和条件最优决策集合，仅就逆序法说明求解步骤：六、动态规划问题求解的一般步骤式中的“opt” 可根据具体问题的实际意义，而取 min或 max。第三十一页，共53页。k = n1时，动态规划的基本方程是111111()(,)()nnnnnnnnufsopt Vsufs 因所有的 都已经求出，因此可以根据 就阶段n-1每个可能状态 ，求出条件最优决策及相应的条件最优目标函数值。111(,)nnnns

21、Tsu()nnfs1ns 因所有 都已求出，因此可以根据 就阶段n-2每个可能状态 ，求出条件最优决策及相应的条件最优目标函数值。1222(,)nnnnsTsu11()nnfs2ns k = n2时，动态规划的基本方程是22222211()(,)()nnnnnnnnufsopt Vsufs第三十二页，共53页。k=1时，动态规划的基本方程是11111122( ) ( ,)()uf sopt v s ufs 由于所有的 f2(s2) 都已经求出，因此可以根据 s2=T1(s1,u1)就阶段1每个可能状态s1 ,求条件最优决策及相应的条件最优目标函数值 f1(s1) . 依次下去 .最后，顺序地求

22、出最优目标值、最优策略和最优路线第三十三页，共53页。 解 该问题可以作为三段决策过程。对A、B、C三个部门分配资金分别形成1，2，3三个阶段。sk表示给部门k分配资金时拥有的资金数。uk表示给部门k分配的资金数（万元为单位）。状态转移方程是 sk+1=sk- uk。目标函数是阶段效应求和。 例2：某公司拟将5百万元资金投放下属A、B、C三个部门，其中A与C的投资额不超过4百万元，B的投资额不超过3百万元，C投资额至少是1百万元。各部门在获得资金后的收益如表所示，用动态规划方法求总收益最大的投资分配方案（投资数以百万元为单位）。151184C121050B1210630A收益 （万元） 432

23、1投放资金(万元)0第三十四页，共53页。44()0fs递归方程为： （1）K=3时（第3阶段） 注意到C的投资额不超过4百万元， 至少是1百万元. 允许状态集合 S3 1, 2, 3, 4 , 即用剩余额S31，2，3，4 投资部门C，得到的收益为：3333(1)4,(2)8,(3)11,(4)15ffff （2） K=2时（第2阶段） 注意到C的投资额至少是1百万元， 允许状态集合 S2 1, 2, 3, 4, 5 , 下面是各种可能方案的列表11()max()(),3,2,1kkkkkkkufsgufsk第三十五页，共53页。s21s2 2s2 3s2 4s2 5 B C B C B C

24、 B C B C0 10 20 30 41 4 1 11 21 32 32 12 23 23 1故223(1)(0)(1)4fgf23232(1)(0)(2)0 8(2)m1)54axmax9gffgf2322233104(2)(1)(0)(3)0 1(3)max(1)(2)max 5 814gffffgg第三十六页，共53页。232322323(0)(4)0 15(1)(3)5 11(4)maxmax18124(3)(1)(2)(2)10 8ggfgffgff2223332(1)(4)5 15(5)maxmax2112 8(3)(2)(2)(3)10 11gffgfgf（3）K=1时 （第1

25、阶段） S1 = 5 允许决策集合 D1(S1) 0, 1, 2, 3, 4, 第三十七页，共53页。11121212212(5)max(2)(3)max 6 1421109(3)(2)124(4)(1)(0)(5)021(1)(4)3 18fgfgfgfgfgf应用顺序追踪可知：最优方案有两个：方案 1：*1230,2,3uuu方案 2：*1231,2,2uuu最大收益都为21百万元。第三十八页，共53页。例例3：逆推解法求解下面问题: 2123123123max,0zx x xxxxcx x x解: 按问题的变量个数划分阶段,把它看作一个三阶段决策问题。设状态变量为s1，s2，s3，s4。

26、并记s1c；令变量x1，x2，x3为决策变量；各阶段指标按乘积方式结合。即令: 2111122223333( ,),(,),(,)v s xx vsxxv sxx第三十九页，共53页。令最优值函数令最优值函数f k k(s(sk k) )表示为第表示为第k k阶段的初始状态为阶段的初始状态为s sk k时，从第时，从第k k阶段到第阶段到第3 3阶段所得到的最大值。阶段所得到的最大值。 设: s3= x3, s3+ x2=s2, s2+ x1=s1=c则有：x3=s3, 0 x2s2, 0 x1s1=c即状态转移方程为： s3=s2x2, s2 =s1x1由逆推解法，即最优解x3=s3, 33

27、3333( )max(),xsf sxs第四十页，共53页。23222222222223233,0222222200()maxmax( )max()max(,)xxxsxsxsfsxxxf sxsxh sx由,得和（舍去）222222230dhx sxdx2223xs20 x 第四十一页，共53页。又，而故为极大值点。 22222226d hsxdx222222223|20 xsd hsdx 2223xs所以 ，即最优解。22224()27fss*2223xs第四十二页，共53页。123111111211123122,0311111100( )maxmax()4max() max( ,)27x

28、 xxxsxsxsf sxxxxfsxsxh s x求导并令导数等于0可得：，故 *1114xs41111( )64f ss由于s1=c，*114xc411( )64f cc由s2 =s1x1，, *222132xsc3221()16fsc由s3 =s2x2，*3314xsc331()4fsc第四十三页，共53页。因此最优解为：， *114xc*212xc*314xc最大值为：411max( )64zf cc第四十四页，共53页。例例：正推解法求解下面问题: 2123123123max,0zx x xxxxcx x x解：设s4c，决策变量仍为x1，x2，x3；最优值函数f k(sk+1)表示

29、为第k阶段末的结束状态为sk+1，从第1阶段到第k阶段所得到的最大值。设: s2= x1, s2+ x2=s3, s3+ x3=s4=c则有：x1=s2, 0 x2s3, 0 x3s4=c即状态转移方程为： s2=s3x2, s3=s4x3第四十五页，共53页。由顺推解法， 即最优解x1=s2,121212()max( ),xsf sxs122323222312212,02323230( )maxmax()4max()27x xxsxsfsxxxf sxsxs最优解。 *2323xs第四十六页，共53页。1233434234123323,03434340()maxmax( )41max() 2764x xxxsxsf sxxxxfsxsxs最优解 *3414xs由于s4=c，*314xc4341()64fsc由s3=s4x3，,*23213