运筹学-动态规划(一)(名校讲义)

1、第十七、十八讲第十七、十八讲 1 引言 2 动态规划的计算方法递推方式 动态规划是运筹学的重要分支之一，它是解决多阶段决策过程最优化的一种方法。该法是由美国数学家贝尔曼（R. Bellman）等人在二十世纪50年代首先提出的。R.Bellman于1957年发表的“动态规划”一书是动态规划方面的第一本著作。目前，动态规划已成功地用于解决资源分配、货物装运、设备更新、生产计划以及复合系统可靠性等许多问题。 一、动态规划求解问题的思路某旅客需从号站到达号站，试指出一条最短路径。交通状况如图3-1所示。 解一种习惯求解法是首先计算所有可能路线的距离，然后经比较选出一条最短路线，这称为显枚举或穷举法，当

2、维数增大时，该法计算量将急剧增大，从而变得不可行。动态规划是采用递推方式使计算量大减，现简介其思路。 108976543211644236136176619103710988,96129109895468444108108第5阶段 第4阶段第3阶段第2阶段第1阶段图3-1 最优旅行路线问题 图3-1中，圆圈内数字表示旅行可能通过的站号（状态号）；共分5个阶段；箭头表示旅行路线，箭头旁边数字表示距离。 令x表示状态(站)号；fi(x)表示从第i阶段x状态到达终点的最短距离；di(x)表示从第i阶段x状态到达终点取最短路线时应到达的下一个状态（站）号。1）假设旅客已到达第4阶段的状态(i) 若已到

3、达状态，则只一条路可到达故 f4(8)=8 d4(8)=10(ii)若已到达状态，同理得f4(9)=4，d4(9)=10。 2）假设旅客已到达第3阶段的状态 (i) 若已到达状态，有2条路可选：及此时应检查这两种选择中能达到的最短距离，即，比较下述i)及ii）并找出最小值。i)从到的距离与到终点的最短距离和ii）从到的距离与到终点的最短距离和。这两个值分别为4+f4(8)=12和8+f4(9)=12，两种费用相等，故得 f3(5)=12 d3(5)=8或9 （ii）若已到达状态，同理可得f3(6)=min =min =10对应d3(6)=9(iii)若已到达状态，同样得f3(7)=min =8

4、d3(7)=9按照同样方法，可算出旅客已到第2阶段和第1阶段的结果。 )9(6)8(944ff4689)9(4)8(544ff 把上述计算结果全部标在图3-1上的状态点附近。其中，圆圈上方数字表示该状态点的最短距离，圆圈下方数字表示该状态点的最优决策。最后，根据计算结果，可找出从到的最短路线为。 二、最优化原理最优化原理可阐述如下：“一个最优策略具有这样的性质：不论初始状态和初始决策如何，相对于第1个决策所形成的状态来说，余下决策必定构成一个最优策略”。如图3-2中，若路线I和II是A到C的最优路线，则根据最优化原理，路线II必是从B到C的最优路线。A CBII 图3-2II 三、动态规划中的

5、主要名词术语1阶段（Stage）：把问题分成几个相互联系的有顺序的几个环节，通常用k表示。2状态（State）：表示某阶段的出发位置或状态值，通常用x表示。3决策（Decision）：从某阶段的1个状态演变到下一阶段某状态的选择，通常用d或u表示。 三、动态规划中的主要名词术语4策略（Policy）：由开始到终点的全过程中，由每段决策组成的决策序列称为全过程策略，简称策略，通常用P表示。5目标函数（或费用函数）：在优化过程中，衡量实现过程的优劣的准则，通常用f或J表示。根据动态规划所求解问题的不同情况可采用后向（逆序）动态规划和前向（顺序）动态规划两种。 一、后向动态规划法已知：目标函数 J

6、= min 约束条件 （状态转移方程） x(k+1)=gx(k)，u(k)，k则，递推公式为NkkuxL0),(1)()(min)(kkuxgIkuxLkxIUu，起步：其中，I（x，k）从k阶段x状态出发采取最优策略到达过程终点所获得的最优目标值；L（x，u，k）k阶段x状态采取决策u所获得的本段目标函数值，又称直接项；U决策变量u的集合。)(min)(NuxLNxIUu，例3-2供电系统的投资规划问题某工厂为满足用电需求增加量，计划在1980年，1985年及1990年投资兴建发电站。电站有500MW和1000MW两种，每年最多兴建一座电站，其投资额示如表3-1，下列表内金额全折合到1980

7、年标准。表3-1 兴建电站投资表 （单位：106元） 投资额 年份容量 1980 1985 1990500MW1000MW 1.0 0.5 0.25 1.6 0.8 0.4电站投资兴建后5年发电。工厂各年需新增加的累积电功率示如表3-2。 表3-2 工厂各年需新增电功率年份 需新增电功率（MW）1985199019954008001200工厂任何一年缺电量不能超过400MW，缺电400MW以内需罚款，罚款数目示如表3-3。 表3-3 历年缺电罚款表 （单位：106元） 罚款 年份缺电量 1985 1990 1995100MW200MW300MW400MW 0.2 0.1 0.050.4 0.2

8、 0.1 0.6 0.3 0.150.8 0.4 0.2问：在1980年、1985年、1990年及1995年应如何兴建电站才能使建电站费与罚款费用总和最小？解 依据题意，选阶段变量k=0，1，2，3分别对应1980年、1985年、1990年及1995年；状态变量x(k)表示阶段k时已有的新增总电量，单位为兆瓦（MW）；决策变量u(k)表示阶段 k时兴建的电站容量，单位为兆瓦（MW）。令x(0)=0，工厂最大需求新增电量为1200MW，因此，x的离散值为0，500，1000，1500，u的离散值为0，500，1000。把建站费用和罚款费用表达成k，x及u的关系式，令L1( u，k)表示 k阶段决

9、策值为u时的建站费用，L2（x，k）表示k阶段状态值为x时的罚款费用。L1和L2的值分别列于表3-4及表3-5中。 表3-4 建站费用L1( u，k)表 （单位：106元） L1 ku 0 1 205001000 0.0 0.0 0.0 1.0 0.5 0.25 1.6 0.8 0.4表3-5 罚款费用L2（x，k）表 （单位：106元） L2 kx 0 1 2 3050010001500 0 0.8 0 0 0.3 0 0 0 0.1 0 0 0 0号表示不容许状态 则，递推公式为I (x，k)= k=0，1，2I(x，3)=L2(x，3) (1995年不需建电站)根据题意，将表达离散状态变

10、量值的初始网格示如图3-3。计算时，从k=3起步，逐步后退进行。) 1()()(min21kuxIkxLkuLu，x1500500100000123 k80859095年图3-3 初始网格1）设已到达k=3阶段，此时，不需再建新电站，因新电站兴建后5年，即2000年才提供电力，而本题对2000年的电力未提要求，于是，此时建站费用（L1（u，3）=0，故该阶段的最优费用I（x，3）=L2(x，3)（罚款费用）。查表3-5知：x=1500，I(1500，3)=0 不罚款x=1000，I(1000，3)=0.1 罚款 不允许0500 xx2）退回k=2阶段(i) 设x(2)=1500，此时u(2)必

11、为0，最优费用为I(1500，2)=L1(0，2)+L2(1500，2)+I(1500，3) =0+0+0=0(ii) 设x(2)=1000令u(2)=0，得此时的最优费用为I(1000，2)=L1(0，2)+L2(1000，2)+I(1000+0，3) =0+0+0.1=0.1令u(2)=500，得此时的最优费用为I(1000，2)=L1(500，2)+L2(1000，2)+I(1000+500，3) =0.25+0+0=0.25令u(2)=1000，得x(3)=2000，越界故最优决策u(2)=0，最优费用I(1000，2)=0.1 (iii) 设x(2)=500令u(2)=0，得x(3)

12、x(2)u(2)500，不满足条件。令u(2)=500，得x(3)5005001000，此时最优费用 I(500，2)=L1(500，2)+L2(500，2)+I(1000，3)=0.25+0.30+0.1=0.65令u(2)=1000，得x(3)50010001500，此时最优费用I(500，2)=L1(1000，2)+L2(500，2)+I(1500，3)=0.4+0.3+0=0.7比较得出最优决策u(2)=500，最优费用I(500，2)=0.65 (iv) 设x(2)=0，查表3-5，不允许出现。同理，可退回到k=1和0阶段，分别求出相应状态的最优决策和费用值。全部计算结果示如图3-4

13、。 x1500100050000.000.00.00.1D0.100.1A 5001000k=0123k1.6B5000.61.70C 00.65500图3-4 最终网格图中，网格右上方数字表示最优费用；网格右下方数字表示最优决策（即此时应兴建的电站容量）；号表示不允许状态。根据网格数据，k=0阶段追踪最优轨迹，显然是ABCD。即1980年兴建500MW电站，1985年建500MW电站，以后不建。这样使建站费用与罚款费用和达到最小，只有1.6106元。前面的旅行路线问题和供电系统投资规划问题都具有明显的“时间”阶段，因此采用动态规划比较直观。但这决不意味着动态规划只能解决动态问题，它同样可以解

14、决静态问题，此时的“阶段”表明空间的分割。下面将举例说明该类问题的处理方式。例3-3货物分配问题（或投资问题）有6箱货物需分配给4个商店，每个商店出售该货物可获利润如表3-6中所示。 问：每个商店应分多少箱才能使总利润最大？ 表3-6 商店销售货物利润表 利润 店号箱数 1 2 3 40123456 0 0 0 0 4 2 3 4 6 4 5 5 7 6 7 6 7 8 8 6 7 9 8 6 7 10 8 6解尽管商店分配货物无时间阶段问题，但用动态规划求解时，可假定分配时按店号1、2、3、4次序分配（当然按其他店号次序也行）。于是可设：阶段k=1、2、3、4，分别对应店号1、2、3、4；x

15、k状态变量，分配给k及以后阶段的箱数；uk决策变量，分配给k阶段的箱数；I(xk，k)分配给k及以后阶段的总箱数为xk时所能获得的最大利润。 则状态转移方程为 xk+1=xkuk迭代公式为I(xk，uk)= 起步：I(x4，4)=L(u4，4)=L(x4，4)其中，L（uk，k）第k阶段分配uk箱货物时所获利润（参见表3-6）。 于是，可作出初始网格，并示于图3-5。 ) 1()(maxkuxIkuLkkkuk，615x42301234k商店1 商店2 商店3 商店4图3-5 初始网格 计算时，从k=4起步，逐步后退计算。1）设货物分配车已开到k=4阶段，显然所剩货物x4应全部卸下，分给商店4

16、。即I(x4，4)= L(x4，4)，u4=x4，u4=0，1，6 x4u4I(x4，4)0 1 2 3 4 5 60 1 2 3 4 5 60 4 5 6 6 6 62)设货物分配车已开到k=3阶段，车上载货量x3=0，1，6。(i) 若x3=0，则u3=0，I(0，3)=0(ii) 若x3=1，则I(1，3)= =max =max =4 u3=0)41 () 3(max33103，uIuLu)40()31 ()41 ()30(，ILIL0340(iii)若x3=2， I(2，3)=7，u3=1(iv)若x3=3，I(3，3)=9，u3=2(v)若x3=4，I(4，3)=11，u3=3同理：

17、若x3=5得I(5，3)=12，u3=3或4若x3=6得I(6，3)=13，u3=3或43）设货物分配车开到k=2阶段，车上货物量为x2，则相应最优目标函数值为I(x2，2)= ) 3()2(max222)10(22，uxIuLxu4)退到起始阶段k=1时，x1=6则I(6，1) = = 17u1=1，2全部结果示于最终网格中（参见图3-6）。图中，网格点右上方表示最优收益，网格点右下方表示最优决策。共有下述6种最优分配方案（收益全为17） )26() 1(max11)60(1，uIuLu1171,2x6543210000k04253646566133,4123,411392714000407

18、0,190,1,2111,2,3132,3,415k=1234图3-6 最终网络06 商店号 分配箱数 1 2 3 4 1 1 3 11 2 2 11 3 1 12 0 3 12 1 2 12 2 1 1 二、前向动态规划法虽然大多数阶段决策问题采用后向动态规划比较直观，但对某些情况（例如，初始点明确给定）采用前向动态规划更为方便。本部分首先一般性引出前向动态规划的递推关系，然后举一简例说明。定义极小数值函数I(x，k)为I(x，k)= 且x(k)=gx(k1)，u(k1)，k1(状态转移方程) 10)1()1()0()()(minkjkuuujjujxL，为研究方便，又可写成x(k1)=g1

19、x(k)，u(k1)，k1即把x(k1)表达成x(k)及u(k1)的函数。则迭代方程变为I(x，k)=其中，Lx(j)，u(j)，j表示j阶段的x(j)状态选择决策u(j)时的直接费用。I(x，k)表示从起始点到达k阶段x状态所获得的最小费用，显然，这个费用是k =0，1，k1阶段的直接费用和，而与k阶段x状态时的本身直接费用无关； 1) 1() 1(min11，kkuxgIkuxgLuI(x，k)由2项组成，一项是k1阶段的直接费用Lx(k1)，u(k1)，k1=Lg1(x，u， k1)，u，k1另一项是递推项Ix(k1)，k1= Ig1(x，u， k1)，k1u表示到达k阶段x状态时，前一

20、阶段采取的决策u(k1)。显然，u不同，则来自于k1阶段的状态x( k1)也不同。起步：I(x，0)为已知，设x(0)=c，则通常定义：I(x，0)=0，当x=c时；I(x，0)=，当xc时这样可迫使满足起始约束条件。由此，可得出最优决策 为 Lg1(x，u， k1)，u，k1 + Ig1(x，u， k1)，k1例3-4已知 x(k+1)=x(k)+u(k) minJ= )( kxu，minarg)( ukxu， )()(4022jjujx约束： 1 u(k) 1 0 x(k) 2 x(0)=2离散单位为1，即 x= ，u=求满足上式的解值。解首先划出初始网格如图3-7所示。（注意，应计算k=0，1，5等6个阶段，比原问题多出一个阶段，因为I(x，k)是k1阶段及以前的直接费