北航最优控制ppt第六章

6.1多级决策的例子——最短时间问题6.2最优性原理6.3用动态规划解资源分配问题6.4用动态规划求离散最优控制6.5连续系统的动态规划6.6动态规划与极小值原理6.7小结第六章动态规划动态规划是贝尔曼(Bellman)在五十年代为解决多级决策过程而提出来的。它可以解决很多领域中的问题，如生产过程的决策，收益和投资问题，有多级反应器的化工装置的设计，多级轧钢机的最速轧制问题，资源分配、机器负荷分配、生产计划编制，特别是控制工程问题。它和极小值原理一样，可解决控制变量受约束的最优控制问题，而且在这两种方法之间存在某种内在的联系。动态规划的中心思想是利用所谓“最优性原理”，把一个级决策过程化为个单级决策过程，从而使问题简单。NN6.1多级决策的例子——最短时间问题设有人要从点开车到站，中间要经过任意三个中间站，站名在图中圆圈内表示。站与站之间称为段，每段路程所需时间（小时）标在段上。现要问，这人应如何选择路线才能最快到达目的地？AE为了便于理解动态规划的思想，我们来研究图6-1所示的最短时间问题。1C3C2CA2B1B2D1DE15414132)6()5()6(367)9()10()5()1()4(2最短时间的到由EB1图6-1按最短时间的路径选择（一）穷举法从走到一共有六条路线，每条路线由四段组成。这六条路线和对应的行车时间如下AE路线行车时间（小时）13111413129EDCAB232EDCAB222EDCAB122111ABCDEEDCAB121EDCAB221显然最优路线是，它所花时间为9小时。EDCAB221这里每条路线由四段组成，也可以说是四级决策。为了计算每条路线所花时间，要做三次加法运算，为了计算六条路线所花的时间要作3×6=18次运算。这种方法称为“穷举法”。显然当段数很多时，计算量是很大的。这种方法的特点是从起点站往前进行，而且把这四级决策一起考虑。应注意从到下一站所花的时间为1，而到所花时间为3，但最优路线却不经过。这说明只看下一步的“眼前利益”来作决策是没有意义的。A2B1B2B（二）动态规划法为将问题表达得清楚，引进下面的术语。令表示由某点到终点的段数（如到为2段）。nE2CE令表示当前所处点的位置（如），称为状态变量。x12,,ABC令为决策（控制）变量，它表示当处在位置而还有段要走时，所要选取的下一点。例如，从出发，下一点为时，则表示为。)(xunxn2C2D222)(DCu令表示在位置，向终点还有段要走时，由到终点的最短时间。例如，从C2到E的最短时间为4，可表示为T2（C2）=4。)(xTnxnxE令表示从点到点的时间。例如，从到的时间为),(nnuxtx)(xun2C2D3),(22DCnt有了这些术语后，就可用动态规划来解这个例子。从最后一段出发进行计算，并将计算出的最短时间用括号表示在相应的点处（见图6-1）。)(xTnx1（倒数第一段）考虑从和到的路线，由定义可知，最短时间分别为1D2DE5)(11DT1)(21DTn=12（倒数第二段）12211122,2212(,)()25minmin4(,)()31DDtCDTDTCtCDTD考虑从、或到的路线。由到有两种路线：，。两种路线中的最短时间由下式确定：1C2C3C2CEEDC12EDC22E最优决策为。222DCu由到只有一种路线，其时间为1CEEDC1165112CT由到E也只有一种路线，其时间为3C51432CTEDC233（倒数第三段）考虑从B1或B2到E的路线。B1到E有两种路线：和。最短时间为ECB11ECB2164264min)(),()(),(min22211211,1321CTCBtCTCBtBTCC最优决策213)(CBu从B2到E有两种路线：和。最短时间为ECB32ECB22104657min)(),()(),(min)(22223232,2332CTCBtCTCBtBTCC最优决策为。223CBu4（倒数第四段）从到的路线有两种：和。最短时间为：AEEAB1EAB2910163min)(),()(),(min232131,421BTBAtBTBAtATBB最优决策为。14)(BAu至此求出了A到E的最短时间为9，最优路线为。在图6-1中用粗线表示。这里，为决定最优路线进行了10次加法，比穷举法的18次少了8次。当段数n更多时，节省计算将会更多。EDCAB221从上面解题过程可见，动态规划解题的两个特点：它是从最后一级往后倒着计算的；它把一个级决策问题（这里是决定一整条路线）化为个单级决策问题，即把一个复杂问题化为多个简单问题来求解。我们可看出阶段与阶段有下面的关系（）NNn1nNn,2,1)()(,min1)(xuTxuxtxTnnnxunn（6-1）),(11ExtxT（表示最后一级）Nn2,1(6-1)式称为函数方程，从(6-1)式可见,在选择了决策后有两个影响，其一是直接影响下一段的时间（眼前利益），其二是影响以后段的最短时间（未来利益）。因此动态规划方法可以说是把眼前利益和未来利益区分开来又结合起来考虑的一种优化方法。这些特点都是由动态规划法的基本原理——最优性原理所决定的。)(xun1n1nT6.2最优性原理贝尔曼的最优性原理可叙述如下：“一个多级决策问题的最优决策具有这样的性质：当把其中任何一级及其状态作为初始级和初始状态时，则不管初始状态是什么，达到这个初始状态的决策是什么，余下的决策对此初始状态必定构成最优策略。”以上面的最短时间问题为例，如把当作初始状态，则余下的决策2E对来讲是最优策略；如把当初始状态，则余下的决策对来讲也构成最优策略。一般来说，如果一个最优过程用状态来表示，最优决策为，则对状态来讲，必定是最优的，这可用图6-2来表示。2CDC22C1BEDCB2211BNxxx,,,10110,,,Nuuukx11,,,Nkkuuu1kN0x1x01kxkxNx0u1ku最优解图6-2最优性原理示意图在多数实际问题中，级决策的性能指标取如下形式NJ10,NkkkNuxFJ是由某级状态和决策决定的性能函数，要求寻找决策使J取极小值。(,)F110,,,Nuuu*NJ最优性原理可表示为*1001111,00111100,*),(min)]},(),([min),({min),(),(),(min011010NuNNuuuNNuuNJuxFuxFuxFuxFuxFuxFuxFJNN（6-2）根据上式就可证明最优性原理的正确性。若以为初态时，余下的决策不是最优的，那么就存在另一决策序列所决定的指标值，于是1x11,,Nuu11,,Nuu*11NNJJ100*100*),(min),(min00NuNNuNJuxFJJuxFJ这与是极小值发生矛盾，所以余下的决策必须是最优的。*NJ（6-1）式的函数方程与（6-2）式所表示的最优性原理是一致的，只是表示方法不同。（6-1）式中的下标n表示离终点的级数，（6-2）式中的下标表示离起点的级数。两式的对照留给读者去做。)(xunkuk),(min),(min),(minmin111100,11010NNuuuNuuuxFuxFuxFJNN（6-3）由上式可见，最优化的过程是从最里面的方括号开始向外扩展的，即寻找最优控制的次序是。因此根据最优性原理，动态规划是从最后一级倒退计算的。0121,,,,uuuuNN将（6-2）式进一步分解为6.3用动态规划解资源分配问题我们提到过，动态规划的应用范围是非常广的。这里介绍用动态规划解决资源分配问题。假定有种资源用来生产种产品（资源可以指工人、机床、资金等，每种资源的总数为）。如果生产第种产品时投入的各种资源量为则可以得到的收益为，它是所分配的资源量的函数，可写成。现在问应如何分配这些资源到各个产品上，使得所有产品的总收益为最大？mnmxxx,,21i,,,21imiixxxig),,(1imiixxg),,(11iminiixxgJ0ig（6-4）取最大，其中满足约束jniijxx1mj,,2,1（6-5）0ijxmjni,,1;,,1（6-6）写成数学形式，即要使上面的问题可以用动态规划求解。为了说明问题简单起见，这里只考虑单资源分配问题，即如何将一种资源分配给种产品，使总收益最大。设这种资源的总数为，分配给第种产品的数量为，则性能指标为nxiixniiixgJ1)(0ig（6-7）取最大，约束条件是niixx10ix（6-8）为了用动态规划求解，引进一个函数，它表示将资源量分配给第1至第种产品时所能得到的最大收益。显然表示将总资源分配到所有种产品上所得到的最大收益，即)(TKxfxxTK)(xfnxnmax)(Jxfn（6-9）容易看出，函数有下列性质)(TKxf即没有资源投入时收益为零。0)0()(Kfi这表明将资源量只用于生产一种产品时的总收益，就是这种产品本身收益。)()()(11TTxgxfiii0)()(0Txfii即不生产产品时收益为零。这些性质构成了以后解题的边界的条件。现在来推导所应满足的关系式。已知投入前种产品的资源量为。如果投入第种产品的资源量为，则投入前（）种产品的资源量为。)(TKxfKKTxKx1KKTxx如果把种产品的资源分配看成是步决策，则表示步决策的指标最优值，表示用决策量时第步的指标值，表示余下步决策的指标最优值，根据最优性原理（对照（6-2）式），则有KKK)(TKxf)(KKxgKxK)(1KTKxxf1K)()()(1KTKKKxTKxxfxgxmaxfK（6-10）这表明若在第1至种产品上的最优分配为，则一定是资源量在前-1种产品上的最优分配。TxKKxx,,111,,KxxKTxxK例1-1假定某一种资源的量有四个单元（如重量单元千克，体积单元公升等），把它分配到三种产品的生产中，每种产品的收益函数如下表所表示，表示所分配的资源的单元数。问怎样分配资源才能使总收益最大？)(xgixx)(1xg)(2xg)(3xg（投入资源单元数）1234（第一种产品增益）8182224（第二种产品增益）36912（第三种产品增益）67810解由边界条件知。现在虑，它表示用1个单元资源分配到2个产品上的最大收益。表示投入第2个产品的资源，则可取值1或0，对应地将有下表。)()(11xgxf)1()(2fxfTK2xxK2x2x2xxT)0()0(11fg)1(2g)1()1(11fg)0(2g第一产品收益第二产品收益1001根据（6-10）式可得22121(1)max(1)(0),(0)(1)max30,088fgfgf表示用2个单元的资源分配到2个产品上，显然可取值2、1、0。类似地可得)2(2f2x2212121(2)max(2)(0),(1)(1),(0)(2)max60,38,01818fgfgfgf同理，当可取值3，2，1，0时可求得2212121212(3)max(3)(0),(2)(1),(1)(2),(0)(3)max9,14,21,2222(4)max12,17,24,25,2425fgfgfgfgff再考虑3个产品的资源分配，可得这三个产品投入资源的单元数为1，2，3，4时的，最优值如下33232332323233(1)max(1)(0),(0)(1)max60,088(2)max(2)(0),(1)(1),(0)(2