第七章 动态规划

1、第七章第七章 动态规划动态规划 动态规划是解决多阶段决策过程最优化问题的一种方法，它将多阶段决策问题转化成一系列比较简单的最优化问题动态规划首先将复杂的问题分解才相互关联的若干阶段，每一个阶段都是一个最优化子问题，然后逐阶段的决策，当所有阶段决策都确定了，整个问题的决策也就确定了动态规划中阶段可以用时间表示，这就是“动态”的含义当然，对于与时间无关的一些静态问题也可以人为地引入“时间”转化成动态问题7.1 动态规划基本原理动态规划基本原理 一、动态规划的基本概念一、动态规划的基本概念 动态规划中所涉及到的概念有阶段、状态、决策与策略、状态转移、指标函数 (1)阶段 将所给问题的过程，按时间或空

2、间特征分解成若干互相联系的阶段，以便按顺序去求每阶段的解，常用字母k表示阶段变量 (2)状态 各阶段开始时的客观条件叫做状态描述各阶段状态的变量称为状态变量，常用sk表示第k阶段的状态变量，状态变量sk的取值集合称为状态集合，用Sk表示 动态规划中的状态必须具有无后效性，即当某阶段状态给定以后，在这阶段以后过程的发展不受这段以前各段状态的影响也就是说，当前的状态是过去历史的一个完整总结，过程的过去历史只能通过当前状态去影响它未来的发展 (3)决策和策略 当各段的状态取定以后，就可以作出不同的决定(或选择)，从而确定下一阶段的状态，这种决定称为决策表示决策的变量，称为决策变量，常用uk(sk)表

3、示第k阶段当状态为sk时的决策变量在实际问题中，决策变量的取值往往限制在一定范围内，称此范围为允许决策集合，常用Dk(sk)表示第k阶段从状态sk出发的允许决策集合，即uk(sk)Dk(sk) 一个按顺序排列的决策组成的集合称为策略一个n阶段决策过程，从第k阶段到第n阶段的过程称为问题的一个后部子过程，或k子过程由k子过程的每一阶段的决策按顺序排列组成的策略序列称为k子策略，记为pk，n(sk)，即 pk，n(sk)= uk(sk)， uk+1(sk+1)， uk+2 (sk+2)，un(sn) 当k=1时，p1，n(s1)就是全过程的一个策略 对每个实际问题，其k子过程可供选择的策略有一定范

4、围，称为允许策略集合，记作Pk，n，使整个问题达到最优效果的策略就是最优策略 (4)状态转移方程 动态规划中本阶段的状态往往是上一阶段状态和上一阶段的决策结果如果给定了第k阶段的状态sk，本阶段决策为uk，则第k+l阶段的状态sk+1也就完全确定，它们的关系可用公式 sk+lTk(sk，uk) 表示该公式表示了由第k阶段到第k+l阶段的状态转移规律，所以称为状态转移方程 (5)指标函数 用于衡量所选定策略优劣的数量指标称为指标函数，它是定义在全过程或则子过程上的数量函数，是各阶段的状态和决策变量的函数它分为阶段指标函数和过程指标函数两种阶段指标函数是指第k阶段状态sk采取决策uk时的效益，用d

5、k (sk，uk)表示过程指标函数指在第k阶段状态为sk采用策略pk，n时，后部子过程的收益，用Vk，n(sk，pk，n)表示Vk，n(sk，pk，n)与dk(sk，uk)之间的关系常见的有求和型和乘积型两种： 或nkjjjjnkknkusdpsV)()(,，nkjjjjnkknkusdpsV)()(,， 最优指标函数表示从第k阶段状态sk采用最优策略到过程终止时的最佳效益值，记为fk(sk)fk(sk)与Vk，n(sk，pk，n)间的关系为 式中opt表示最优化，根据具体问题表示为max或min 当k=1时，f1(s1)就是从初始状态s1到全过程结束的整体最优函数)()()(,*,nkknk

6、PpnkknkkkpsVoptpsVsfnknk， 二、动态规划的基本方程二、动态规划的基本方程 动态规划方法基于贝尔曼(R.Bellman)提出的最优化原理：一个过程的最优策略具有这种性质，即不管先前的状态和决策如何，余下的所有决策必构成的最优子策略 最优性原理是动态规划理论的核心这个原理说明，最优策略的任一后部子策略也是最优的根据这个原理，在求解多阶段决策问题时，前面的各状态和决策，对其后面的子问题来说，只不过相当于其初始条件而已，并不影响后面过程的最优决策因此，可以把多阶段决策问题求解过程表示成一个连续的递推过程，由后向前逐步计算这要利用第k阶段与第k+1阶段之间的关系，通常如下：)()

7、(11)()()(1111边界条件，已知，csfnnksfusdoptsfnnkkkkkukkK或边界条件，已知，)()(11)()()(1111csfnnksfusdoptsfnnkkkkkukkk该方程称为动态规划的基本方程 三、动态规划的求解方法三、动态规划的求解方法 动态规划的求解有两种基本方法：逆序解法(后向动态规划方法)、顺序解法(前向动态规划方法)当寻优的方向与多阶段决策过程的实际行进方向相反，从最后一段开始计算逐段前推，求得全过程的最优策略，称为逆序解法与之相反，顺序解法的寻优方向与过程的行进方向相同，计算时从第一段开始逐段向后递推，计算后一阶段要用到前一阶段的求优结果，最后一

8、段计算的结果就是全过程的最优结果一般而言，如果已知过程的初始状态 ，则用逆序解法；如果已知过程的终止状态 ，则用顺序解法这两种方法除了寻优方向不同外，状态转移方程、指标函数的定义和基本方程形式一般也有差异，但并无本质上的区别下面主要介绍逆序解法 1s1ns设已知初始状态为 1s 第 阶段：指标函数的最优值 此为一维极值问题，不妨设有最优解 ，于是可有最优值 n),()()(nnnsDxnnusvoptsfnnn)(nnnsuu )(nnsf 第 阶段：类似地有其中*表示“+”或“”， ，可解得最优解 ，于是最优值为 1n)(*),()(111)(11111nnnnnsDxnnsfusVopts

9、fnnn)(111nnnnusTs，)(111nnnsuu)(11nnsf 不妨设第k+1阶段的最优解为 和最优值，则对于第 阶段有)(111kkksuu)(11kksfk)(*)()(11)(kkkkksDxkksfusVoptsfkkk，其中 ，可解得最优解 和最优值为 )(1kkkkusTs，)(kkksuu )(kksf 依此类推，直到第1阶段，有，其中 ，可解得最优解 和最优值为 )(*)()(22111)(11111sfusVoptsfsDx，)(1112usTs，)(111suu )(11sf 由于已知 ，则可知u1与 从而可知，按上面的过程反推回去，即可得到每一阶段和全过程的最

10、优决策1s)(11sf)(2222sfus，例7.1 求解下面的优化问题，321010. .294)(max3212321ixxxxtsxxxXfi 解 这是一个静态问题，为了应用动态规划，先人为的赋予它“阶段”的概念首先考虑x1的取值，然后考虑x2的取值，x3的取值，这样就将原问题划分为3个阶段，下面的关键是如何选择状态变量，使各后部子过程之间具有递推关系 通常可以把决策变量uk定义为原静态问题中的变量xk，即uk=xk (k=1，2，3)状态变量一般为累计量或随递推过程变化的量这里可以把个阶段的决策变量的最大可能取值定为状态变量sk，初始状态s1=10这样就有k=1时，s1=10，u1=x

11、1；k=2时，s2= s1u1，u2=x2；k=1时，s3= s2u2，u3=x3 状态转移方程为sk+1= skuk，指标函数为 其中，基本方程为33 ,),(kiiiikusdV11114),(uusd22229),(uusd233332),(uusd，0)(123)(),(max)(44110sfksfusdsfkkkkksukkkk当k=3时， ，显 然 2max)(2303333usfsu 3*3su 当k=2时， )(29max)(9max)(222203320222222ususfusfsusu由高等数学知识可得 2/92s时， 2*2*20suu 或则时， ； 时， 2/92s

12、0*2u2/92s2*2su当k=1时 ， )(4max)(22101111sfusfsu当 时， ，2*2su 2229)(ssf) 0(90959max)( 94max)10(*1111100111100111usususufuu但是 与 矛盾，所以舍去；10*121uss2/92s当 时， 0*2u22222)(ssf)10(24max)10(21110011uufu由高等数学知识可得 0*1u200)10(1f由状态转移方程顺推，得 ，显然应取 10*121uss0*2u，所以 10*223uss，而 103*3 su所以最优解为 TTTuuuxxx，1000321321200maxz

13、7.2动态规划迭代算法动态规划迭代算法 上节的多阶段决策问题可以确定出阶段的数目，称为固定阶段的多阶段决策问题本节要讨论的是阶段数不固定的有限阶段决策过程及其求解方法 考虑如下的最短路问题假设有n个点：1，2，n，任意两点i与j之间的距离(或行程时间，运费等)为cij，0cij+cij=0表示i与j为同点，cij表示两点间无通路由点直接到另一点算作一步要求在不限定步数的条件下，找出点l到点n的最短路线 我们把类似上述不限定数的有限阶段决策问题柿为阶段数不固定的有限阶段决策过程在解此问题时可以不考虑回路，因为含有回路的路线一定不是最短路 设f (i) 表示由点i到点n的最短距离，则由贝尔曼最优性

14、原理，得，0)(121)(min)(1nfnijfcifijnj 这就是上述问题的动态规划函数的基本方程它是关于最优值函数的函数方程，而不是递推关系式这给求解带来一定的困难下面介绍求解的两种逐次逼近方法一、函数迭代法一、函数迭代法 函数迭代法的基本思想是构造一个函数序列来逼近最优值函数 首先令k=1，)(ifk)(if，0)(121)(11nfnicifin然后构造 ，0)(121)(min)(111nfnijfcifkkijnjk当 时，就取 niififkk，21)()(1niififk，21)()(否则令k=k+1再按上式迭代计算 的意义十分直观，表示由i点出发，至多走k步（即经过k1个

15、点）到达点n的最短路线的长度因为不考虑回路，所以算法的迭代次数一定不超过k1 )(ifk 例例7.2 设点1，2，3，4之间的距离如图图7.1所示试用函数迭代法求各点到点4的最短路线及相应的最短距离解：显然58674 图7.104840768705650)(44ijcC对点1，2，3到点4的最短距离计算过程如下： k=1时，f1(i)=ci4，i=1，2，3，即f1(1)=，f1(2)=8，f1(3)=4 ( fk(4)0， ，不必计算)kk=2时， ，故)(min)(112jfcifijnj) 1 (10046850min) 1 (12ff，) 2(80847805min) 2(12ff，)

16、 3 (40440876min) 3 (12ff，k=3时， ，故)(min)(213jfcifijnj) 1 (1004685100min) 1 (23ff，)2(8084780105min)2(23ff，) 3(4044087106min) 3(23ff， 因此，f2(i)就是点i到点4的最短距离点1到点4的最短距离为 ，最段路线为134类似可得点2，3到4的最短距离分别为8，4，最短路线分别为24，34)3()(min)1(113112fcjfcfijnj二、策略迭代法二、策略迭代法 策略迭代法的思想是先选取一个初始策略，然后调整得到新的策略，当策略不在发生改变的时候就得到最优策略具体计

17、算过程如下： 首先，任意选择一个初始策略 ，令k=1；121)(1niiu，然后，计算函数值，0)(121)()()(,nfniiufcifkkkiuikk并确定新策略 ，新策略满足:)(1iuk)(min)(11jfciufkijjkk 最后，如果对 ，则 为最优策略，否则令k=k+1，再按上式迭代计算)()(1iuiuikk，)(iuk 策略迭代法每次迭代包括求值和改善策略两步，要比函数迭代法复杂，计算量也大但是策略迭代法所需的迭代次数往往少于函数迭代法，特别是当初始策略选取较好时例例7.3 用策略迭代法求解例7.2解：设初始策略为 4 , 2 , 4 , 3)(11iuu 计算在策略u1

18、下的由点i到点4的路程f1(i)，i=1，2，3 ( fk(4)0， 不必计算)k808)4()2(1141fcf1587)2()3(1121fcf21156) 3() 1 (1131fcf计算指标函数值f2(i)并确定新的策略u2， in)(min) 1 (112jfcfjj，)1(2)1(12uu，80815780215min)(min)2(122jfcfjj，)2(4)2(12uu，40415087216min)(min)3(132jfcfjj)3(4)3(12uu计算指标函数值f3(i)并确定新的策略u3，1004685130min)(min) 1 (213jfcfjj) 1 (3) 1 (23uu，8084780135min)(min)2(223jfcfjj)2(4)2(23uu，4044087136min)(min)3(233jfcfjj)3(4)3(23uu计算指标函数值f4(i)并确定新的策略u4，1004685100min)(min) 1 (314jfcfjj) 1 (3) 1 (34uu，8084780105min)(min)2(324jfcfjj)2(4)2(34uu，4044087106min)(min)3(334jf