第5章动态规划5

1、 5.1动态规划的基本概念和基本原理动态规划的基本概念和基本原理 5.2动态规划模型的建立动态规划模型的建立 5.3动态规划的求解动态规划的求解 5.4动态规划的应用举例动态规划的应用举例第第5章章 动态规划动态规划 如最优路径问题、生产调度问题、库存管理如最优路径问题、生产调度问题、库存管理问题、设备更新问题等等。许多问题用动态问题、设备更新问题等等。许多问题用动态规划的方法去处理，往往比线性规划或非线规划的方法去处理，往往比线性规划或非线性规划更有效，特别是对于离散性问题，动性规划更有效，特别是对于离散性问题，动态规划可以发挥其所长而成为非常有用的工态规划可以发挥其所长而成为非常有用的工具

2、。动态规划是求解某一类问题的一种方法，具。动态规划是求解某一类问题的一种方法，它必须对问题进行具体分析处理。它必须对问题进行具体分析处理。本章首先介绍动态规划的基本概念与基本原本章首先介绍动态规划的基本概念与基本原理，然后介绍动态规划的模型和求解方法，理，然后介绍动态规划的模型和求解方法，最后通过一些典型的动态规划模型来介绍它最后通过一些典型的动态规划模型来介绍它的应用。的应用。 5.1动态规划的基本概念和基本原理动态规划的基本概念和基本原理 5.1.1 多阶段决策多阶段决策12n决策 决策 状态 决策 状态 状态 状态 状态 图5.1.1 如图如图5.1.15.1.1，这种把一个问题可看作一

3、个前后关联具有链状，这种把一个问题可看作一个前后关联具有链状结构的多阶段过程的决策就称为多阶段决策过程，也称为结构的多阶段过程的决策就称为多阶段决策过程，也称为序贯决策过程序贯决策过程。这种使整个活动过程的总体效果达到最优。这种使整个活动过程的总体效果达到最优的相关问题称为的相关问题称为多阶段决策问题多阶段决策问题。多阶段决策问题的目标：多阶段决策问题的目标： 使整个过程达到最优使整个过程达到最优 解决多阶段决策问题的方法：解决多阶段决策问题的方法： 动态规划方法动态规划方法 一般来说，各阶段采取的决策都与时间有关，一般来说，各阶段采取的决策都与时间有关， 决策依赖于当前的状态，又随即引起状态

4、的转移，决策依赖于当前的状态，又随即引起状态的转移， 一个决策序列就是在变化的状态中产生出来的，故一个决策序列就是在变化的状态中产生出来的，故 有有“动态的动态的”含义。含义。 一些与时间没有关系的静态规划一些与时间没有关系的静态规划 （如线性规划、非线性规划等）问题，（如线性规划、非线性规划等）问题， 引入引入“时间时间”要要 素，素， 亦可把它视为多阶段决策问题，亦可把它视为多阶段决策问题， 用动态规划方法用动态规划方法处理。处理。例例5.1.1 （最短路问题）（最短路问题）假设要从假设要从A城市到城市到 E城市铺设一条输油管道，中间需要经城市铺设一条输油管道，中间需要经过三个地区，每个地

5、区都有若干个转运站，构成了许多不过三个地区，每个地区都有若干个转运站，构成了许多不同的输油路线，转运站间的数字表示站间的运输路径的长同的输油路线，转运站间的数字表示站间的运输路径的长度，由于地理条件等原因，某些地区之间不能直接铺设相度，由于地理条件等原因，某些地区之间不能直接铺设相通的管道。现需求出一条使总路径最短的管道路线。通的管道。现需求出一条使总路径最短的管道路线。AB1B2B3C1C2C3D1D2E359677523835433496图5.1.2 在第一阶段，在第一阶段， 从从A点出发，点出发， 有有123,B B B1,B3,C123,C C C1D2D三个转运站可三个转运站可 以抵

6、达，以抵达， 即有三个不同的决策。即有三个不同的决策。 若选择若选择 则则 1B既是既是 该阶段的终点，该阶段的终点， 又是下一个阶段的起点，又是下一个阶段的起点， 选择选择 23,B B同样如此。同样如此。 类似地，类似地， 在第二阶段有在第二阶段有 三个不同三个不同 的决策，的决策， 在第三阶段无论起点是在第三阶段无论起点是 12,C C还是还是 都只都只 有选择有选择 和和 两种不同的决策。两种不同的决策。 而在最后一个阶段，而在最后一个阶段， 无论起点是无论起点是 1D还是还是 2,D都只有都只有E这个唯一的决策。这个唯一的决策。 这这 样整个决策过程就划分成这样四个决策阶段，样整个决

7、策过程就划分成这样四个决策阶段， 总共有总共有14条不同的路线方案，条不同的路线方案， 即构成即构成14个不同的决策，个不同的决策， 我们我们就必须从中找出总路径最短的路线。就必须从中找出总路径最短的路线。 ;AB根据线路图，根据线路图， 可以把从可以把从A到到E点的过程分成四个阶段：点的过程分成四个阶段： ;BC;CDDE1. 4. 2. 3. 类似地，类似地， 还有各种资源分配问题、还有各种资源分配问题、 生产的存贮生产的存贮问题、问题、最优装载问题、最优装载问题、 水库调运优化问题和最优控水库调运优化问题和最优控 制问题等等，制问题等等， 均具有多阶段决策问题的特征，均具有多阶段决策问题

8、的特征， 可用可用 动态规划方法来求解。动态规划方法来求解。 该问题即为多阶段决策问题。该问题即为多阶段决策问题。5.1.2 动态规划的基本概念动态规划的基本概念一、一、 阶段阶段Stage 对于一个多阶段决策过程，对于一个多阶段决策过程， 可以根据问题的特可以根据问题的特 点，点， 把整个过程划分为几个相互联系的阶段，把整个过程划分为几个相互联系的阶段， 以便以便 可以按一定的顺序去求解。可以按一定的顺序去求解。 这个根据时间和空间的这个根据时间和空间的自然特征来划分的次序称为自然特征来划分的次序称为阶段阶段， 描述阶段的变量描述阶段的变量 称为称为阶段变量阶段变量， 一般用一般用k表示。表

9、示。 如例如例5.1.1中的多阶段决策问题可划分为四个阶中的多阶段决策问题可划分为四个阶记为记为 1,2,3,4k 。段，段， 123,C C C二、状态二、状态State状态状态：表示系统每个阶段开始时所处的自然状况或：表示系统每个阶段开始时所处的自然状况或客观条件。客观条件。 如例如例5.1.1中，中， 状态就是某阶段的出状态就是某阶段的出 发位置，发位置， 它既是该阶段某支路的起点，它既是该阶段某支路的起点， 又是前又是前 一阶段某支路的终点。一阶段某支路的终点。 第一个阶段有一个状态第一个阶段有一个状态 即为点即为点A， 第二个阶段有三个状态第二个阶段有三个状态 3sks123,B B

10、 B 。状态变量状态变量：描述状态的变量。常用：描述状态的变量。常用 表示第表示第k阶段阶段 的状态变量。的状态变量。 如例如例5.1.1中第三个阶段有中第三个阶段有3个状个状 态，态， 则状态则状态 可取三个值，可取三个值， 即即 这三这三 个点构成的集合个点构成的集合 123,C C C称为第三个阶段称为第三个阶段的的允许状态集允许状态集，记为记为 .kS31,2,3,S 1,2,3,3123,SC C C。有时为了方有时为了方 便起见，便起见， 也将阶段的状态编上号码也将阶段的状态编上号码 即有即有 一般地，一般地， 第第 k个阶段的允许状态集个阶段的允许状态集 记为记为 当某个阶段的状

11、态给定后，当某个阶段的状态给定后， 则这个阶段以后过程则这个阶段以后过程 的发展不受这个阶段及以前各阶段状态的影响。也的发展不受这个阶段及以前各阶段状态的影响。也 是说，当前的状态只是以往历史的一个总结，过程是说，当前的状态只是以往历史的一个总结，过程 的过去历史只能通过当前的状态去影响它未来的发的过去历史只能通过当前的状态去影响它未来的发 展，这种性质称为展，这种性质称为无后效性无后效性。 kkus三、决策三、决策Decision决策决策： 各阶段状态确定后，各阶段状态确定后， 确定下一个阶段的状态确定下一个阶段的状态 的各种选择。的各种选择。 决策变量决策变量： 描述决策的变量。描述决策的

12、变量。 常用常用 kskkDskskskkus表示第表示第k 阶段状态处于阶段状态处于 时的决策变量，它是状态时的决策变量，它是状态 变量变量 的函数。的函数。 允许决策集允许决策集： 决策变量的取值构成的集合，决策变量的取值构成的集合， 表明决策表明决策的约束条件，的约束条件， 常用常用 表示第表示第k阶段系统阶段系统 处于状态处于状态 时的允许决策集合，时的允许决策集合， 即有即有 ,kkDs2,C212.uBC2112,DBC C1B如例如例5.1.1中，中， 第二阶段决策时，若从状第二阶段决策时，若从状 态态 出发，出发， 则可做出两种不同决策，其允许决策集则可做出两种不同决策，其允许

13、决策集 合为合为 若选定的下一个状态是若选定的下一个状态是 则则 四、策略四、策略Policy策略策略： 从初始阶段到最终阶段，从初始阶段到最终阶段， 每个阶段均有一决每个阶段均有一决 策，策， 各阶段决策形成一个决策序列，各阶段决策形成一个决策序列， 称为系统的一个称为系统的一个策略策略。 此序列此序列最优策略最优策略： 使系统达到最优效果的策略。 全过程策略全过程策略： 对于具有几个阶段的多阶段决策问题， 从第一个阶段的某一状态出发到终止阶 段的状态做出的决策序列而形成的策略。 记为 1,11122,nnnpsususus1,np即 k后部子过程后部子过程： 从第k阶段到终止阶段状态的过程

14、。简称为 k子过程子过程。 后部子过程策略后部子过程策略： k后部子过程相应的决策序列 。简ks称为称为 k子策略子策略。 记为记为 1ksku,11,k nkkkkknnpsususus,k np即即 允许策略集允许策略集： 在实际问题中，可供选择的策略所在在实际问题中，可供选择的策略所在 的范围，常记为的范围，常记为 P。五、状态转移方程五、状态转移方程状态转移方程状态转移方程： 描述系统由一个阶段到下一个阶段描述系统由一个阶段到下一个阶段的状态转移规律。的状态转移规律。 例如，设系统第例如，设系统第k阶段的阶段的 状态变量状态变量 的值给定，的值给定， 该阶段的状态变量该阶段的状态变量

15、确定，确定， 则第则第k+1阶段阶段 的状态变量的状态变量 的值的值 kT也就确定了，也就确定了， 即即 kuks1ks的值随的值随 和和 变化而变化，这种对应关系我们记为变化而变化，这种对应关系我们记为的值的的值的ks1,kkkksTs u以上状态转移规律，即为以上状态转移规律，即为状态转移方程状态转移方程。 称为称为状态转移函数状态转移函数。六、指标函数与最优指标函数六、指标函数与最优指标函数k阶段指标函数阶段指标函数： 第第k阶段状态为阶段状态为 决策变量决策变量 ku取取 某个值后得到的一个反映这个局部策略效某个值后得到的一个反映这个局部策略效 应的数量指标。应的数量指标。 也称为k阶

16、段的效应函数阶段的效应函数 。,kkfs全过程的指标函数全过程的指标函数： 常用 ks,k nkk nVsp1,11,nnVs p1,np,kkd s u表示 。采用全过程的策略 的数量指标。 其指标函数值记为 用 表示第k阶段状态为 *,k npks,k np采用策略 时，后部子过程的指标函数值。 最优指标函数最优指标函数： 指标函数的最优值。 记为 表示从第k阶段的状态 开始到第 n 阶段的终止过程采取最优策略 所得到的21fB指标函数值，即指标函数值，即 1,fA2,51VB1B12,6d B C2C,*,k nkkk nkk nk nkk npfsVspoptVsp在不同问题中，在不同

17、问题中， 指标函数的含义是不同的，指标函数的含义是不同的， 它可能指它可能指 距离、利润、成本、产品的产量或资源消耗等。距离、利润、成本、产品的产量或资源消耗等。 如如 例例5.1.1中，中， 指标函数是距离，指标函数是距离， 如第二阶段状态为如第二阶段状态为 时，时， 表示由表示由 1B出发采用决策到下一个出发采用决策到下一个 阶段阶段 点的距离，点的距离， 表示从表示从 1B出发到出发到F的总的总 距离，而距离，而表示从表示从B1 出发到出发到E的最短距离。的最短距离。 该问该问题的总目标是求题的总目标是求 即从即从A到终点到终点E的最短距离。的最短距离。 5.1.3动态规划的基本原理动态

18、规划的基本原理下面我们结合例下面我们结合例5.1.1的最短路问题来介绍动态的最短路问题来介绍动态规划的基本思想与基本原理。规划的基本思想与基本原理。穷举法的计算量将非常大，显然不适合。穷举法的计算量将非常大，显然不适合。考虑最短路线的一个重要特征：考虑最短路线的一个重要特征： 若从起点若从起点A经过经过 B、C、D点而达到终点点而达到终点 E是一条最短路线，是一条最短路线， 则由则由B点出点出 发经过发经过C、D点到达终点点到达终点E点的这条子路线，对于从点的这条子路线，对于从 B点点 出发达到终点出发达到终点E点的所有可能选择的不同路线来说，点的所有可能选择的不同路线来说，必定也是最短路线。

19、必定也是最短路线。122ABCDE122BCDE在例在例5.1.1中，中， 若找到了若找到了 是由是由 A到到E的最短路线，的最短路线， 则则 也应是从B1 出发到发到E点的所有可能选择的不同路线中的最短路线。点的所有可能选择的不同路线中的最短路线。 如果不是这样，如果不是这样， 则从则从B1点到点到 E点有另一条距离更短的点有另一条距离更短的路线存在，路线存在， 把它和原来的最短路线有把它和原来的最短路线有A点到点到B1点的那点的那部分连接起来，部分连接起来， 就会得到一条从就会得到一条从A点到点到E点的新路线，点的新路线， 且比原来的那条最短路线的距离还要短些，这就与且比原来的那条最短路线

20、的距离还要短些，这就与假设矛盾。假设矛盾。 基于最短路线的这一特性，基于最短路线的这一特性， 我们考虑寻找我们考虑寻找最短路线的方法，最短路线的方法， 就是从最后一段开始，就是从最后一段开始， 用由后向前用由后向前逆向递推的方法，逆向递推的方法，逐步求出各点到终点的最短路线，逐步求出各点到终点的最短路线， 最后求得由起点到终点的最短路线。最后求得由起点到终点的最短路线。以例以例5.1.1为例，我们按上述思想寻找从为例，我们按上述思想寻找从A到到E的最的最 短路线。短路线。 AB1B2B3C1C2C3D1D2E359677523835433496图5.1.2 311413131242,34min

21、min753,dC DfDfCdC DfD第一步，第一步， 从从k=4出发，出发， 状态变量状态变量4s12,D D41424,3fDfD3s1C123,C C C可取状态可取状态 它们到它们到E点的路长分别为点的路长分别为 第二步，第二步，k=3， 状态变量状态变量 可取三个值可取三个值 这是经过一个中途点到达终点这是经过一个中途点到达终点E的两级决策变量。的两级决策变量。 从从 到到E有两条路线，有两条路线， 需加以比较取其中最短的，需加以比较取其中最短的，即即11CD,E311.uCD321413232242,44minmin633,dCDfDfCdCDfD1C这说明由这说明由 到到E的

22、最短距离为的最短距离为7， 其路径为其路径为 相应的决策为相应的决策为 同理同理2C22,CDE322.uCD331413333242,64minmin1093,dC DfDfCdC DfD即即 到终点到终点E的最短距离为的最短距离为6， 其路径为其路径为 相应的决策为相应的决策为 即即3C31CD,E2222211,fBuBC2121212,fBuBC331.uCD到终点到终点E的最短距离为的最短距离为10 。 其路径为其路径为 相应的决策为相应的决策为 类似地，类似地， k=2时时 11115,fAuAB232329,fBuBCk=1时，时， 出发点只有一个出发点只有一个A点，点， 则则

23、1121232242,uAB uBC uCD uDE122.ABCDE11min4,3,2,1kkkkkkkkufsdsufsk，550fs ,ku即从起点即从起点A到终点到终点 E的最短距离为的最短距离为15。 反推可得最优决策序列反推可得最优决策序列 再按计算顺序再按计算顺序即即 所以得最短路线为所以得最短路线为 注注1： 从例从例5.1.1的计算过程可以看出，在各阶段，都的计算过程可以看出，在各阶段，都 利用了第利用了第k阶段和第阶段和第 k+1阶段的如下关系：阶段的如下关系： （5.1.1） 550fs这种递推关系称为动态规划的基本方程，这种递推关系称为动态规划的基本方程， 称为边界条

24、件。称为边界条件。 上述最短路线的计算过程也可用图直观表示出上述最短路线的计算过程也可用图直观表示出来，如图来，如图5.1.3：AB1B2B3C1C2C3D1D2E356333346(15)(9)(11)(12)(10)(6)(7)(3)(4)(0)这里，每个节点上方的括号内的数字，这里，每个节点上方的括号内的数字， 表示该点到表示该点到 E点的最短距离，点的最短距离， 连接各点到E点的线表示最短路径。 这种在图上直接计算的方法称为这种在图上直接计算的方法称为标号法标号法。动态规划方法相对于穷举法来说有以下优点：动态规划方法相对于穷举法来说有以下优点： （1）减少了计算量；）减少了计算量； （

25、2）丰富了计算结果。）丰富了计算结果。 动态规划方法存在的不足之处：动态规划方法存在的不足之处： （1）静态规划模型转化为动态规划模型十分困难；）静态规划模型转化为动态规划模型十分困难； （2）状态变量的）状态变量的“无后效性无后效性”条件难以满足。条件难以满足。 动态规划的动态规划的基本思想基本思想总结：总结： 先将多阶段决策的过程划分成几个相互联系先将多阶段决策的过程划分成几个相互联系的阶段，的阶段， 恰当地选取状态变量、决策变量，恰当地选取状态变量、决策变量， 定义最定义最优指标函数，优指标函数， 从而把问题化成一族同类型的子问题，从而把问题化成一族同类型的子问题， 然后逐个求解。然后逐

26、个求解。 求解时从边界条件开始，求解时从边界条件开始， 逆方向逐逆方向逐段递推寻优。段递推寻优。 在每一个子问题求解时，在每一个子问题求解时， 都要使用它都要使用它前面已求出的子问题的最优结果，前面已求出的子问题的最优结果， 最后一个子问题最后一个子问题的最优解，的最优解， 就是整个问题的最优解。就是整个问题的最优解。 动态规划的基本方程是递推逐段求解的根据。动态规划的基本方程是递推逐段求解的根据。 动态规划基本方程可表述为：动态规划基本方程可表述为： ku,ks(,)kkkv s u11()11()(,)(),1,1()0kkkkkkkkkkuDsnnfsoptv s ufskn nfs式中

27、式中opt可根据实际问题选取可根据实际问题选取min或或max， 表示状态为表示状态为 决策为决策为 时对应的第时对应的第k阶段的指标阶段的指标函数值。函数值。5.1.4 最优化原理最优化原理定理定理5.1.1（最优性定理）（最优性定理） 对阶段数为对阶段数为n的多阶段决的多阶段决 策，策， 设其阶段编号为设其阶段编号为 111,.kkkksTsuks 1,1,1,(,),nkk nppp*1,12,nnpu uu1,1,*1,11,1,111,1,kk nnnkkk nkk nppVs poptVs poptVsp11sS(1),kkn1,2, ,kn允许策略为允许策略为 是最优策略的充要条件是是最优策略的充要条件是 当初始状态当初始状态 时，时， 最优指标函数为最优指标函数为 其中其中 是由是由1,1,1,111,1,kk nkkk nkk nppopt opt V