第八九讲动态规划运筹学基础清华大学王永县课件.ppt

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状态到达终点取最短路线时应到达的下一个状态

3、（站）号。1）假设旅客已到达第4阶段的状态(i)若已到达状态，则只一条路可到达故 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 =

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

5、优路线，则根据最优化原理，路线II必是从B到C的最优路线。A CBII 图3-2II 第十七、十八讲 三、动态规划中的主要名词术语1阶段（Stage）：把问题分成几个相互联系的有顺序的几个环节，通常用k表示。2状态（State）：表示某阶段的出发位置或状态值，通常用x表示。3决策（Decision）：从某阶段的1个状态演变到下一阶段某状态的选择，通常用d或u表示。第十七、十八讲 三、动态规划中的主要名词术语4策略（Policy）：由开始到终点的全过程中，由每段决策组成的决策序列称为全过程策略，简称策略，通常用P表示。5目标函数（或费用函数）：在优化过程中，衡量实现过程的优劣的准则，通常用f或J

6、表示。第十七、十八讲根据动态规划所求解问题的不同情况可采用后向（逆序）动态规划和前向（顺序）动态规划两种。一、后向动态规划法已知：目标函数 J=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供电系统的投资规划问题某工厂为满足用电需求增加量，

7、计划在1980年，1985年及1990年投资兴建发电站。电站有500MW和1000MW两种，每年最多兴建一座电站，其投资额示如表3-1，下列表内金额全折合到1980年标准。表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以内需罚款，罚款数目

8、示如表3-3。表3-3 历年缺电罚款表 （单位：106元）罚款 年份缺电量 1980 1985 1990100MW200MW300MW400MW 0.2 0.1 0.050.4 0.2 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）。第十七、十八讲令

9、x(0)=0，工厂最大需求新增电量为1200MW，因此，x的离散值为0，500，1000，1500，u的离散值为0，500，1000。把建站费用和罚款费用表达成k，x及u的关系式，令L1(u，k)表示 k阶段决策值为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 ku 0 1 2 3

10、050010001500 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年不需建电站)根据题意，将表达离散状态变量值的初始网格示如图3-3。计算时，从k=3起步，逐步后退进行。)1()()(min21kuxIkxLkuLu，x1500500100000123 k80859095年图3-3 初始网格第十七、十八讲1）设已到达k=3阶段，此时，不需再建新电站，因新电站兴建后5年，即2000年才提供电力，而本题对2000年的电力未提要求，于是，此时建站费用（L1（u，3）=

11、0，故该阶段的最优费用I（x，3）=L2(x，3)（罚款费用）。查表3-5知：x=1500，I(1500，3)=0 不罚款x=1000，I(1000，3)=0.1 罚款 不允许0500 xx第十七、十八讲2）退回k=2阶段(i)设x(2)=1500，此时u(2)必为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(100

12、0，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)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

13、)+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。第十七、十八讲x1500100050000.000.00.00.1D0.100.1A 5001000k=0123k1.6B5000.61.70C 00.65500图3-4 最终网格图中，网格右上方数字表示最优费用；网格右下方数字表示最优决策（即此时应兴建的电站容量）；号表示不允许状态。根据网格数据，k=0阶段追踪最优轨迹

14、，显然是ABCD。即1980年兴建500MW电站，1985年建500MW电站，以后不建。这样使建站费用与罚款费用和达到最小，只有1.6106元。第十七、十八讲前面的旅行路线问题和供电系统投资规划问题都具有明显的“时间”阶段，因此采用动态规划比较直观。但这决不意味着动态规划只能解决动态问题，它同样可以解决静态问题，此时的“阶段”表明空间的分割。下面将举例说明该类问题的处理方式。例3-3货物分配问题（或投资问题）有6箱货物需分配给4个商店，每个商店出售该货物可获利润如表3-6中所示。问：每个商店应分多少箱才能使总利润最大？第十七、十八讲表3-6 商店销售货物利润表 利润 店号箱数 1 2 3 40

15、123456 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；xk状态变量，分配给k及以后阶段的箱数；uk决策变量，分配给k阶段的箱数；I(xk，k)分配给k及以后阶段的总箱数为xk时所能获得的最大利润。则状态转移方程为 xk+1=xkuk第十七、十八讲迭代公式为I(xk，uk)=起步：I(x4，4)=L(u4，4)=L(x4，4)其中

16、，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。即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 6第十七、十八讲2)设货物分配车已开到k=3阶段，车上载货量x3=0，1，6。(i)若x3=

17、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同理：若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，uxIuLxu第十七、十八讲4)退

18、到起始阶段k=1时，x1=6则I(6，1)=17u1=1，2全部结果示于最终网格中（参见图3-6）。图中，网格点右上方表示最优收益，网格点右下方表示最优决策。共有下述6种最优分配方案（收益全为17）)26()1(max11)60(1，uIuLu第十七、十八讲1171,2x6543210000k04253646566133,4123,4113927140004070,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 第十七、十八讲二、前向动态规划

19、法虽然大多数阶段决策问题采用后向动态规划比较直观，但对某些情况（例如，初始点明确给定）采用前向动态规划更为方便。本部分首先一般性引出前向动态规划的递推关系，然后举一简例说明。定义极小数值函数I(x，k)为I(x，k)=且x(k)=gx(k1)，u(k1)，k1(状态转移方程)10)1()1()0()()(minkjkuuujjujxL，第十七、十八讲为研究方便，又可写成x(k1)=g1x(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)表示从起始点到

20、达k阶段x状态所获得的最小费用，显然，这个费用是k=0，1，k1阶段的直接费用和，而与k阶段x状态时的本身直接费用无关；1)1()1(min11，kkuxgIkuxgLu第十七、十八讲I(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状态时，前一阶段采取的决策u(k1)。显然，u不同，则来自于k1阶段的状态x(k1)也不同。起步：I(x，0)为已知，设x(0)=c，则通常定义：I(x，0)=0，当x=c时；I(x，0)=，当xc时这样可迫使满足起始约束条

21、件。第十七、十八讲由此，可得出最优决策 为 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阶段及以前的直接费用和。210101第十七、十八讲计算时，从k=0起步，逐步向下计算：其中，x(k)表示k阶段取的状态值。u(x，k)表示到达k

22、阶段x状态时，前段的决策值。1）k=0时，因x(0)=2，故I(2，0)=0其余I(1，0)=，I(0，0)=(即不可行点，将此网格点划号)。x021012345 k 图3-7 初始网络 第十七、十八讲2）前进到（k=1）(i)当x(1)=2，显然只能来自k=0阶段的x(0)=2，即u(2，1)=0I(2，1)=L(2，0，0)+I(2，0)=x2(0)+u2(2，1)+I(2，0)=22+02+0=4 u(2，1)=0(ii)当x(1)=1，只能来自于k=0阶段的x(0)=2，则 u(1，1)=1 I(1，1)=L(2，1，0)+I(2，0)=x2(0)+u2(1，1)+I(2，0)=22+

23、(1)2+0=5(iii)当x(1)=0，k=0阶段无可行点达到此点，即 I(0，1)=第十七、十八讲3）前进到k=2（略）依此类推，可计算出全部数据并列于图3-8的最终网格中。图中，网格点的右上方数字表示从起始点到达该点的最优费用I(x，k)；网格点的右下方数字表示从起始点到达该点采用的最优路线时的来自前一阶段的决策值u(x，k)。图3-8 最终网格x2100478910k=0 12k345AB1817-10007777865-1001,00111CDFE第十七、十八讲根据最终网格，找出k=5阶段时的最优目标I(x，5)=7，对应 x(5)=0，u(0，5)=0依次返回找出最优轨迹为：ABCDEF三、变量取连续值时的递推算法（略）