第七章 动态规划.

第七章动态规划动态规划是解决多阶段决策过程最优化问题的一种方法，它将多阶段决策问题转化成一系列比较简单的最优化问题．动态规划首先将复杂的问题分解才相互关联的若干阶段，每一个阶段都是一个最优化子问题，然后逐阶段的决策，当所有阶段决策都确定了，整个问题的决策也就确定了．动态规划中阶段可以用时间表示，这就是“动态”的含义．当然，对于与时间无关的一些静态问题也可以人为地引入“时间”转化成动态问题．§7.1动态规划基本原理一、动态规划的基本概念动态规划中所涉及到的概念有阶段、状态、决策与策略、状态转移、指标函数．(1)阶段将所给问题的过程，按时间或空间特征分解成若干互相联系的阶段，以便按顺序去求每阶段的解，常用字母k表示阶段变量．(2)状态各阶段开始时的客观条件叫做状态．描述各阶段状态的变量称为状态变量，常用sk表示第k阶段的状态变量，状态变量sk的取值集合称为状态集合，用Sk表示．动态规划中的状态必须具有无后效性，即当某阶段状态给定以后，在这阶段以后过程的发展不受这段以前各段状态的影响．也就是说，当前的状态是过去历史的一个完整总结，过程的过去历史只能通过当前状态去影响它未来的发展．(3)决策和策略当各段的状态取定以后，就可以作出不同的决定(或选择)，从而确定下一阶段的状态，这种决定称为决策．表示决策的变量，称为决策变量，常用uk(sk)表示第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子过程可供选择的策略有一定范围，称为允许策略集合，记作Pk，n，使整个问题达到最优效果的策略就是最优策略．(4)状态转移方程动态规划中本阶段的状态往往是上一阶段状态和上一阶段的决策结果．如果给定了第k阶段的状态sk，本阶段决策为uk，则第k+l阶段的状态sk+1也就完全确定，它们的关系可用公式sk+l＝Tk(sk，uk)表示．该公式表示了由第k阶段到第k+l阶段的状态转移规律，所以称为状态转移方程．(5)指标函数用于衡量所选定策略优劣的数量指标称为指标函数，它是定义在全过程或则子过程上的数量函数，是各阶段的状态和决策变量的函数．它分为阶段指标函数和过程指标函数两种．阶段指标函数是指第k阶段状态sk采取决策uk时的效益，用dk(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到全过程结束的整体最优函数．)()()(,,*,,,,nkknkPpnkknkkkpsVoptpsVsfnknk，，二、动态规划的基本方程动态规划方法基于贝尔曼(R.Bellman)提出的最优化原理：一个过程的最优策略具有这种性质，即不管先前的状态和决策如何，余下的所有决策必构成的最优子策略．最优性原理是动态规划理论的核心．这个原理说明，最优策略的任一后部子策略也是最优的．根据这个原理，在求解多阶段决策问题时，前面的各状态和决策，对其后面的子问题来说，只不过相当于其初始条件而已，并不影响后面过程的最优决策．因此，可以把多阶段决策问题求解过程表示成一个连续的递推过程，由后向前逐步计算．这要利用第k阶段与第k+1阶段之间的关系，通常如下：)()(11))()(()(1111边界条件，已知，，，，，，，csfnnksfusdoptsfnnkkkkkukkK或．边界条件，已知，，，，，，，)()(11))()(()(1111csfnnksfusdoptsfnnkkkkkukkk该方程称为动态规划的基本方程．三、动态规划的求解方法动态规划的求解有两种基本方法：逆序解法(后向动态规划方法)、顺序解法(前向动态规划方法)．当寻优的方向与多阶段决策过程的实际行进方向相反，从最后一段开始计算逐段前推，求得全过程的最优策略，称为逆序解法．与之相反，顺序解法的寻优方向与过程的行进方向相同，计算时从第一段开始逐段向后递推，计算后一阶段要用到前一阶段的求优结果，最后一段计算的结果就是全过程的最优结果．一般而言，如果已知过程的初始状态，则用逆序解法；如果已知过程的终止状态，则用顺序解法．这两种方法除了寻优方向不同外，状态转移方程、指标函数的定义和基本方程形式一般也有差异，但并无本质上的区别．下面主要介绍逆序解法．1s1ns设已知初始状态为．1s第阶段：指标函数的最优值此为一维极值问题，不妨设有最优解，于是可有最优值．n),()()(nnnsDxnnusvoptsfnnn)(nnnsuu)(nnsf第阶段：类似地有其中*表示“+”或“”，，可解得最优解，于是最优值为．1n)(*),()(111)(11111nnnnnsDxnnsfusVoptsfnnn)(111nnnnusTs，)(111nnnsuu)(11nnsf不妨设第k+1阶段的最优解为和最优值，则对于第阶段有)(111kkksuu)(11kksfk)(*)()(11)(kkkkksDxkksfusVoptsfkkk，其中，可解得最优解和最优值为．)(1kkkkusTs，)(kkksuu)(kksf依此类推，直到第1阶段，有，其中，可解得最优解和最优值为．)(*)()(22111)(11111sfusVoptsfsDx，)(1112usTs，)(111suu)(11sf由于已知，则可知u1与．从而可知，按上面的过程反推回去，即可得到每一阶段和全过程的最优决策．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=x1；k=2时，s2=s1－u1，u2=x2；k=1时，s3=s2－u2，u3=x3．状态转移方程为sk+1=sk－uk，指标函数为其中，基本方程为33,),(kiiiikusdV11114),(uusd22229),(uusd233332),(uusd．，，，，0)(123)}(),({max)(44110sfksfusdsfkkkkksukkkk当k=3时，，显然．}2{max)(2303333usfsu3*3su当k=2时，})(29{max)}(9{max)(222203320222222ususfusfsusu由高等数学知识可得2/92s时，2*2*20suu或则时，；时，．2/92s0*2u2/92s2*2su当k=1时，．)}(4{max)(22101111sfusfsu当时，，2*2su2229)(ssf)0(909}59{max)}(94{max)10(*1111100111100111usususufuu但是与矛盾，所以舍去；10*121uss2/92s当时，0*2u22222)(ssf})10(24{max)10(21110011uufu由高等数学知识可得0*1u200)10(1f由状态转移方程顺推，得，显然应取10*121uss0*2u，所以10*223uss，而．103*3su所以最优解为TTTuuuxxx］，，［］，，［］，，［1000321321200maxz§7.2动态规划迭代算法上节的多阶段决策问题可以确定出阶段的数目，称为固定阶段的多阶段决策问题．本节要讨论的是阶段数不固定的有限阶段决策过程及其求解方法．考虑如下的最短路问题．假设有n个点：1，2，…，n，任意两点i与j之间的距离(或行程时间，运费等)为cij，0≤cij≤+∞．cij=0表示i与j为同—点，cij＝∞表示两点间无通路．由—点直接到另一点算作一步．要求在不限定步数的条件下，找出点l到点n的最短路线．我们把类似上述不限定数的有限阶段决策问题柿为阶段数不固定的有限阶段决策过程．在解此问题时可以不考虑回路，因为含有回路的路线一定不是最短路．设f(i)表示由点i到点n的最短距离，则由贝尔曼最优性原理，得．，，，，，0)(121)}({min)(1nfnijfcifijnj这就是上述问题的动态规划函数的基本方程．它是关于最优值函数的函数方程，而不是递推关系式．这给求解带来一定的困难．下面介绍求解的两种逐次逼近方法．一、函数迭代法函数迭代法的基本思想是构造一个函数序列来逼近最优值函数．首先令k=1，)}({ifk)(if．，，，，，0)(121)(11nfnicifin然后构造．，，，，，0)(121)}({min)(111nfnijfcifkkijnjk当时，就取niififkk，，，，21)()(1niififk，，，，21)()(否则令k=k+1再按上式迭代计算．的意义十分直观，表示由i点出发，至多走k步（即经过k－1个点）到达点n的最短路线的长度．因为不考虑回路，所以算法的迭代次数一定不超过k－1．)(ifk例7.2设点1，2，3，4之间的距离如图7.1所示．试用函数迭代法求各点到点4的最短路线及相应的最短距离．解：显然58674②③①④图7.104840768705650)(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，，不必计算)．kk=2时，，故｝｛)(min)(112jfcifijnj)1(10046850min)1(12ff｝，，，｛)2(80847805min)2(12ff｝，，，｛)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的最短距离为，最段路线为1→3→4．类似可得点2，3到4的最短距离分别