第七章 动态规划方法建模

《第七章 动态规划方法建模》由会员分享，可在线阅读，更多相关《第七章 动态规划方法建模（20页珍藏版）》请在装配图网上搜索。

1、第七章动态规划方法建模动态规划是由理查德贝尔曼（Richard Bellman）所建立的，它是解最优化问题的一个特殊“技术”.我们这里用“技术”，是因为动态规划不是一个或一种特殊算法.7.1 动态规划的基本概念在生产和科学实验中，有一类活动的过程，由于它的特殊性，可将过程分为若干个互相联系的阶段，在它的每一个阶段都需要作出决策，从而使整个过程达到最好的活动效果.因此，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展.当各个阶段决策确定后，就组成了一个决策序列，因此也就决定了整个过程的一条活动路线.这种把一个问题可看作是一个前后关联具有链状结构的多阶段过程（如图7.1）

2、就称为多阶段决策过程，也称序贯决策过程.这种问题就称为多阶段决策问题.在多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前的状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义.因此，把处理它的方法称为动态规划方法.但是，一些与时间没有关系的静态规划（如线性规划、非线性规划等）问题，只要人为地引进“时间”因素，也可把它视为多阶段决策问题，用动态规划方法来处理.涉及到动态规划，总会有下面几个概念：7.1.17.1.1动态规划的基本概念动态规划的基本概念（）阶段把所给问题的过程，恰当地分为若干个相互联系的阶段阶段，以便能按一定的次序求解

3、.描述阶段的变量称为阶段变量阶段变量，常用k表示.阶段的划分，一般是根据时间和空间的自然特征来划分，但要便于把问题的过程能转化成为多阶段决策的过程.（）状态状态状态表示每个阶段开始所处的自然状况或客观条件，它描述了研究问题的状况，又称不可控因素.在最短路问题中，状态就是某阶段的出发位置.它既是该阶段某支路的起点，又是前一阶段某支路的终点.通常一个阶段有若干个状态（一般第一个阶段只有一个状态，它构成动态规划的递推方程的出口），每一个阶段的所有状态构成一个集合，叫做状态集合状态集合.用一个变量Si来描述在第i个阶段的状态集合上的取值，此变量Si称为状态变量状态变量（如 7.2 节中最短路问题中的S

4、i，以及后面要介绍的背包问题、分割问题及设备更新问题中的参数）.这里所说的状态是具体的属于某阶段的，它应具备下面的性质：如果某阶段状态给定后，则在这阶段以后过程的发展不受这阶段以前各阶段状态的影响.换句话说，过程的过去历史只能通过当前的状态去影响它未来的发展，当前的状态是以往历史的总结.这个性质称为无无后效性，后效性，也称马尔可夫（马尔可夫（MarkovMarkov）性）性.如果状态仅仅描述过程的具体特征，则并不是任何实际过程都能满足无后效性的要求.所以，在构造决策过程的动态规划模型时，不能仅由描述过程的具体特征这点着眼去规定状态变量，而要充分注意到是否满足无后效性的要求.如果状态的某种规定方

5、式可能导致不满足无后效性，则应适当地改变状态的规定方法，达到能使它满足无后效性的要求.（）决策决策决策表示当过程处于某一阶段的某一状态时，可以作出不同的决定（或选择），从而确定下一阶段的状态，这种决定称为决策决策.在最优控制中也称为控制控制（只有它才是我们能够控制的）.描述决策的变量称为决策变量.它可以用一个数、一组数或一个向量来描述.常用uk(sk)表示第k阶段当状态处于sk时的决策变量，它是状态或状态变量的函数（可能是向量值函数或多值函数）.在实际问题中，决策变量的取值往往限制在某一范围之内，此范围称为允许决策集合允许决策集合.常用Dk(sk)表示第k阶段当状态处于sk出发的允许决策集合，

6、显然有uk(sk)Dk(sk).例如，在最短路问题中，D2(v5)D2(v6)D2(v7)v8,v9.（）策略策略策略是一个按顺序排列的决策组成的集合.由过程的第k阶段开始到终止状态为止的过程，称为问题的后部子过程后部子过程.由每段的决策按顺序排列组成的决策函数序列称为子策略，记为pk,n(sk)uk(sk),uk1(sk1),un(sn)当k 1时，此决策函数序列即为一个策略.p1,n(sk)u1(s1),u2(s2),un(sn)在实际问题中，可供选择的策略有一定的范围，此范围称为允许策略集合允许策略集合.从允许策略集合中找到达到最优效果的策略称为最优策略最优策略.（）状态转移方程状态转移

7、方程式确定过程有一个状态到另一个状态的演变过程.若给定第k阶段状态sk和该阶段的决策变量uk(sk)，则第k 1阶段的状态sk1也就完全确定.即sk1的值随sk和uk(sk)的值变化而变化.这种确定的对应关系，记为sk1Tk(sk,uk(sk)，它描述了由第k阶段到第k 1阶段的状态转移规律，称为状态转移方程状态转移方程.Tk称为状态转移函数状态转移函数.例如，在最短路问题中，状态转移方程为sk1 uk(sk).（）指标函数和最优值函数用来衡量所实现过程优劣的数量指标，称为指标函数.它是定义在全过程和所有后部子过程上确定的函数.对于要构成动态规划模型的指标函数，应具有可分性，并满足递推关系（详

8、见文献），在实际问题中，很多指标函数都满足此性质.指标函数的最优值，称为最优值函数最优值函数.根据问题，取 min 或 max 之一.在动态规划模型中，总会出现一个或一组递推关系，我们把它称为动态规划的基本方程动态规划的基本方程.7.1.27.1.2动态规划方法的基本思想动态规划方法的基本思想现将动态规划方法的基本思想归纳如下：一、动态规划方法的关键在于正确写出基本的递推关系式和恰当的边界条件（基本方程）.要做到这一点，必须先将问题的整个过程分成几个相互联系的阶段，恰当地选取状态变量和决策变量及定义最优值函数，从而把一个大问题化成一族同类型的子问题，然后逐个求解.即从边界条件开始，逐段递推寻优

9、，在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题所得的最优解，就是整个问题的最优解.二、在多阶段决策过程中，动态规划方法是既把当前一段和未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法.因此，每段决策的选取是从全局来考虑的，与该段的最优选择答案一般是不同的.三、在求整个问题的最优策略时，由于初始状态是已知的，而每段的决策都是该段状态的函数，故最优策略所经过的各段状态便可逐次变换得到，从而确定了最优策略.动态规划的理论基础叫做动态规划的最优化原理动态规划的最优化原理，它是这样描述的：作为整个过程的最优策略具有这样的性质：即无论过去的状态和决策

10、如何，对前面决作为整个过程的最优策略具有这样的性质：即无论过去的状态和决策如何，对前面决策所形成的状态而言，余下的诸决策必须构成最优策略策所形成的状态而言，余下的诸决策必须构成最优策略.简言之，一个最优策略的子策略总简言之，一个最优策略的子策略总是最优的是最优的.动态规划的优劣：优点：（1）易于确定全局最优解.因为它求解的全是一维问题，所以容易确定.（2）能得到一族（全部的）最优解，有利于分析结果.（3）能利用经验，提高求解效率.缺点：（1）到目前为止，没有一个统一的标准模型可供应用.由于问题的不同，有时要将问题转化成满足条件（无后效性、目标函数的可分性）的多阶段决策过程是非常困难的，需要丰富

11、的想象力和灵活的技巧.（2）应用的局限性.“无后效性”条件的限制，降低了动态规划的通用性.（3）在数值计算时，存在所谓的“维数灾难”.当阶段数目较多且每一阶段的允许状态也较多时，计算成本变得非常昂贵，有时使得计算不可能进行下去.在二维或三维动态规划中，问题显得更加突出.7.2 最短路问题问题：某人想进行一次旅行.他住在城市 1，而希望到达城市10，见图 7.2.这是一次长途的旅行，而且他还必须进行三次中间停留.对他旅行中的三个中间停留站的每一站，都有两到三个不同的城市可供他选择.选择不同的中间站，旅行的花费是不同的.两城市之间的花费以及连接示于图 7.2 中.由于他希望为这次旅行付出的总花费达

12、到最小，他将确定哪些城市作为他的中间站，显然，它可以用枚举法来解决此问题，总的可能的路线有18 条（33218）.但问题肯定有更好的解法，下面我们用更好的方法来解决此问题.我们从终点（城市 10）逆序来分析这个问题.第一步：若我们处在第3 站，可通过城市8 或城市 9 到达城市 10.可用表 7.2.1（1）说明：表 7.2.1（1）第 3 站城市89最小花费380280路径810910第二步：现在假设在第 2 站，并问哪一条是到达城市 10 且花费最小的路径.若在城市 5，最小花费是 510，即（210380，230280）中的最小值，将选用路径 5910.同理，若在城市 6，最小花费是66

13、0，即（350380，380280）中的最小值，将选择路径6910.此结果列于表 7.2.1（2）中.表 7.2.1（2）第 2 站城市567最小花费510660670路径591069107810第三步：假定处在第 1 站.用类似于第 2 站的分析方法进行分析，例如，由城市2 到达城市 10 的最小花费是 830min（320510，350660，400670）括号中和式的第一项是由城市 2 到城市 5、6、7 的花费，第二项是城市 5、6、7 到城市 10 的最小花费，它可由表 31（2）查到，最小花费路径是 25910.第 1 站的所有计算结果有表7.2.1（3）给出.表 7.2.1（3）

14、第 1 站城市234最小花费830860810路径259103591045910第四步：假设处在城市1，这是起点.必须由城市 1 到城市 2、3、4 中的一个.最小花费的路径是那一条呢？应用表 7.2.1（3）的结果和由城市 1 到城市 2、3、4 的花费，则可计算出全旅程的最小花费为：min（300830，200860，350810）min（1130，1060，1160）1060最小花费路径是：135910.上面的解决非常简单.它是基于这样的思考：不论现在处于那一个城市，从最后一个城市开始，将总是选择最优（最小花费）的路径.若在城市 10（第 4 站），就留在那里.若在城市 5（第 3 站）

15、，则从城市 8 或 9 到达城市 10.如此继续下去，直到发现自己在城市1（第 0站），并且顺序地找到了最小花费的解，以及实现最小花费的路径.应当注意，即使没有达到第 0 站，最优解将是什么样，也是清楚的.我们注意到，在第 1 站，最小费用将是由城市 3到城市 10 的最小费用加上 200.另外，如果他改变了他的愿望，并决定从任何其它城市起始，我们也知道最优解是什么.上面的解法虽然简单，但它却富有启发性.一方面，在计算过程中，我们使用了已经计算出的数据，这大大的节约了计算成本；另一方面，我们得到了比我们预期多得多的信息，我们不仅仅解得了从城市 1（起点）到城市 10 的最小费用路径，而且还得到

16、了其它任何一个城市到达城市 10 的最小费用路径.显然，如果在原问题的旅行图前又增添了一些新的城市，我们已经计算出的数据仍然可以利用，并且进一步的计算不会比上面的计算更复杂.下面我们将上面的解法步骤用符号表示，以期望得到更一般的形式.用符号vi(i 1,2,10)表示 10 个城市.d(vi,vj)表示城市vi到城市vj的距离.如果城市vi到城市vj必须经过其它城市，则d(vi,vj).于是所有数据d(vi,vj)构成一个矩阵，即为 0320200350(d(vi,vj)32020035000032035040035028041030025020000032035030035028025040

17、041020021023035038029040000210350290230380400380280 3802800 用Si表示第i站所有城市构成的集合.即S0v1，S1v2,v3,v4，S2v5,v6,v7，S3v8,v9，S4v10.用fk(vi)表示从第k站的城市vi到目的地v10的最小费用值.于是上面的解题过程可由下面的递推公式完成：f4(v10)0f(v)minf(v)d(v,v),k 4,3,2,1(7.2.1)k1ikjjivjSk当然，在每步极小化时，应记住极小值点vi，这样才能确定最小费用路径.显然，根据对称性，你还可以使用“顺推法”.与之对应，上面的过程称为“逆推法”.7

18、.3 背包问题问题：有人在某地旅游结束后，决定购买一些“特产”，打算带回家，再卖给他的一些同事，指望得到一笔诚实无欺的利润.他知道在他的行李中最多只能带20，才不会超重.他可以购买四种不同类型的特产，其特征如见表7.3.1.表 7.3.1项目1234重量（）2354估计利润（元）110160260210由于这些项目不可能分割包装，这就限制了只能取其整数倍.根据第六章，此问题可以用整数线性规划来描述.设x1，x2，x3，x4表示准备带回家的各种特产的数量，则问题变为求解maxP 110 x1160 x2 260 x3 210 x4 (7.3.1)2x13x25x3 4x4 20(7.3.2)s.

19、t.xi 0为整数(i 1,2,3,4)*下面我们将用动态规划技术来解此问题.假设已知x2,x3,x4的最优值，记为x2.若是,x3,x4*这种情况，我们只需要解一个单变量问题，将x2代入式(7.3.1)(7.3.2)中，可得,x3,x4*max110 x1(160 x2 260 x3 210 x4)(7.3.3)约束为*(7.3.4)2x1 203x25x34x4x1 0,为整数(7.3.5)*由于160 x2是一个常数（若已知x2的值），则目标函数式(7.3.3)260 x3 210 x4,x3,x4仅仅是max110 x1(7.3.6)x10*自然，x2是未知的.但是，我们知道x2必须满

20、足,x3,x4,x3,x4*203x2(7.3.7)5x34x4否则的话，问题式(7.3.3)-(7.3.5)是无解的.若我们规定一个新的变量，通常称为状态变量，则可将式(7.3.4)写成为2x1(7.3.8)*其中，可为，20 中任何一个值，因为在这里实际上x2是未知的.,x3,x4现在来解由式(7.3.6)和式(7.3.8)给出的一维问题，即max110 x1（7.3.9）x10约束为2x1(0,1,20)(7.3.10)*2x1 0得出x1(0)0*2x1 4得出x1(4)220对于每一个值，此问题是易于求解的.例如：max110 x1,max110 x1,若定义g1()max110 x

21、1(7.3.11)x10则g1()给出110 x1的最大值，并且x1()是给出极大值的x1的值.g1()和x1()二者为的函数，因此极大化将限制在的某些特定值上.若对全部的求解(7.3.9)，可得表 7.3.2（1）：表 7.3.2（1）*g1()x1()g1()x1()g1()x1()*012300110110001178910330440440550344514151617770770880880778845622022033022311121355066066056618192099099011009910*考虑到，现在已经知道满足原问题(7.3.1)-(7.3.2)的约束的最优值x1(

22、)是怎样地取决于，以及怎样地取决于原问题的任一可能的限制.现在来考虑下述问题：g2()maxmax110 x1160 x2(7.3.12)x20 x10约束为2x13x2(7.3.13)为什么要考虑式(7.3.12)和(7.3.13)形式的最优化问题呢？首先我们注意到，这个问题的所有可行解，也是原问题的可行解.其次，若固定于某些值上，则问题是单变量问题，这可从下面的一些论述看出.利用定义式(7.3.11)可看出，max110 x1在式(7.3.12)中是g1(3x2).x10所以，式(7.3.12)可写为g2()maxg1(3x2)160 x2(7.3.14)x20注意，对于固定的，式(7.3

23、.14)是一个单变量最优化问题.然而，式(7.3.14)不是完全的.由式(7.3.13)和x1,x2,x3,x4的非负性，可看出3x2 0，所以有0 x2(7.3.15)3其中，a 小于等于a的最大的整数.于是可将式(7.3.14)写为g2()max g1(3x2)160 x2(7.3.16)0 x2/3其中 0,1,2,20.式(7.3.16)是相当重要的.首先，它是一个单变量最优化问题，易于求解；而且对于全部可能的g1()值，在表 7.3.1（1）中已经给出，求g1(3x2)只需查表 7.3.1（1）就行.这样，利用式(7.3.16)和表 7.3.1（1）可计算出g2()的值.结果见表 7

24、.3.2（2）中.表 7.3.2（）*g2()x2()g2()x2()g2()x2()012345600110160220270330000101078910111213380440490550600660710101010114151617181920770820880930990104011000101010同理，下面我们来考虑问题g3()maxmax(max110 x1)160 x2 260 x3(7.3.17)x30 x20 x10约束为2x13x25x3(7.3.18)此外，若用式(7.3.12)给出的g2()，式(7.3.17)可写为g2()maxg2(5x3)260 x3(7.3

25、.19)x30并且，由于5x3 0，可获得类似于式(7.3.16)的形式，即g3()max g2(5x3)260 x3(7.3.20)0 x3/5其中 0,1,2,20.现在可以用式(7.3.20)和表 7.3.2（2）可求出g3()的值.见表 7.3.2（3）：表 7.3.2（3）*()g3()x3()g3()x3()g3()x3012345600110160220270330000000078910111213380440490550600660710000000014151617181920770820880930990104011000000000最后，我们来考察如下问题：g4()ma

26、xg3(4x4)210 x4(7.3.21)x40其中极大化是从 0 到之间的整数x4上考虑的.4回到原问题，因为意味着允许携带物品的总重量，故此时只须求 20时的值，即g4(20)maxg3(20 4x4)210 x40 x45利用表 7.3.2（2）的值，可知道g4(20)maxg3(20 4x4)210 x40 x45g3(20 40)2100g3(20)1100g(20 41)2101g(16)210109033g(2042)2102g3(12)4201080 max3 max max1100.此g3(20 43)2103g3(8)6301070g3(2044)2104g3(4)840

27、1060g(2045)2105g(0)1050105033*时，x4(20)0.我们已经得到了最优值P 1100以及x4 0，注意到P*g3(20)，从*表 7.3.2（3）可知道x3而且P*g2(20).同理，表 7.3.2（2）告诉x2 0和P*g1(20).0，*最后，在表 7.3.1（1）中得到x110.于是原问题的解为：*x1 0，x3 0，P 1100.10，x2 0，x4*在这个例子中，我们的解题方法有类似于上一节最短路问题求解的特征：(1)用解四个单变量的最优化问题，代替解一个四变量的最优化问题.(2)就象最短路问题一样，我们先来处理一个变量（最短路问题中，先考虑最后1 站），

28、接着是两个变量，直到最后我们才处理了全部变量.(3)尽管我们感兴趣的是 20的情形，但是除了最后一步仅是对 20求解外，我们对的全部可能的整数值（0 20），求解了问题.如果用wi和pi分别表示第i种物品的重量和获利（i 1,2,3,4）.表示剩余下的用于携带物品的重量.gi()表示用于携带物品的重量为时带第i种物品的最大利润.则有下面的递推方程可表示上面的解题过程：0 20,xi为整数（i 1，2，3，4）g0()0(7.3.22)g()max g(w x)p x,i 1,2,3,4ii1iiii0wixi用此方法解题，可以节约计算.7.4 分割问题问题：给定一个正数a，将其分成n个部分，使

29、这n部分的乘积最大.下面我们用动态规划的方法来解决这个问题.注意到是未指定的.首先我们令ngn()maxxii1xi;xi 0;i 1,2,ni1n即gn()表示任何一个正数分成n部分，它们乘积的最大值.乘积的最大值gn()可这样分解：它的第 1 部分为x，且剩余的为分成n 1部分时乘积的最大值.第一步：考虑n 1的情形（最简单的情形）.对于这个问题，即任何一个正数分成部分，显然乘积的最大值为.因此，我们定义g1()(7.4.1)第二步：考虑n 2的情形.即将数分成乘积最大的部分.设其中的一部分为x，则另一部分为 x，于是g2()max xg1(x)(7.4.2)0 x利用式(7.4.1)上式

30、也可写成g2()max x(x)0 x这是一个含参数的单变量最大化问题，可用数学分析的方法求最大化.对右端函数x(x)2的变量x求导数并令其导数等于，就得到x 时有最大值.因此我们求得了g2()的24显式表达式：g2()24且其第部分为x*.(7.4.3)2第三步：考虑n 3的情形.即将数分成乘积最大的部分.设其中的一部分为x，则剩余部分的和为 x，于是g3()max xg2(x)(7.4.4)0 x利用式(7.4.1)上式也可写成g3()max x(x)2/40 x这是一个含 参数的单 变量 最大化问 题，可用 数学 分析的方 法求最大 化.对右端函 数x(x)2/4的变量x求导数并令其导数

31、等于就得到x 得了g3()的显式表达式：3时有最大值().因此我们求33g3()()3且其第部分为x*.(7.4.5)33第四步：根据(7.4.1)(7.4.3)(7.4.5)，现在我们猜测gn()()n且其第部分为x*.(7.4.6)nn下面用归纳法来证明.事实上，n 1,2,3的情形已经证明.假设n k时(7.4.6)成立.第五步：当n k 1时，因为gk1()max xgk(x)(7.4.7)0 x利用假设，则gk1()max x(0 x xk)k这仍然是一个单变量的最优化问题.利用数学分析的知识可求得gk1()(k 1)k1且其第部分为x*k 1.这样就完成了归纳法的证明.n最后：将

32、a代入式(7.4.6)，我们得到正数a分割成n部分时最大乘积为()且分anaa，剩余部分为(n 1)，将此部分分割成n 1份，使得乘积最大的分割nn(n 1)a/naa，又剩余了(n 2)，再将此部分分割成n 2份，依中第一部分为n 1nna次下去，我们会得到每一部分都是.于是，原问题就解决了.答案是：给定一个正数a，将n割的第一部分为其等分成n个部分，这样n部分的乘积最大.我们仍然将上面的计算方法归结为下面的递推方程：0g1()(7.4.8)g()max xg(x),k 1,2,n 1k0 xk1值的注意的是，我们的方法当问题改变为如下时仍然有效：将一个正整数m分割成n（m n）个正整数使其

33、乘积最大.但在每一步求解最优化时不能使用经典方法.建议读者动手做做.7.5简单的设备更新问题一部用于化学处理的设备，特别易于遭到腐蚀的损坏，致使影响生产效率.设当用了t年后，从运转中得到的净收入（扣除运转费用后），可用下式给出1262t t2(0 t 4)I(7.5.1)20(t 4)由式(7.5.1)可看出，这部设备在使用一定年限后应该淘汰.更新的价值为 22，并且当它被更换后，它又有了五年的生产寿命.经常保持有一部已用了一年的设备在运转.若每年做一次决策，继续保持这部设备或更换它，那么采用什么策略会使一个规划期限内（五年）的总赢利为最大？由于式子(7.5.1)给出了净收入，可看出，年赢利是

34、收入与花费之差（即扣除运转费用）.由此，若保持这部现用设备，则赢利为1262t t2(0 t 4)P(t)(7.5.2)20(t 4)而更换这部设备，赢利为P(t)26 22 4(7.5.3)由于这部设备已没有挽救的价值，所以从新设备中的净赢利不取决于所更新设备的使用年限.所以P(0)4为从新设备中第一年的赢利.现在让我们把问题公式化.我们希望求出五个逐年决策的序列，即，保持(K)或更换(R)，使从五年运转中的赢利为最大.所以希望max(Kj,Rj)P(t)(7.5.4)jj15其中，Pj(t)由式(7.5.2)或式(7.5.3)给出，哪一个由作出的决策来定.现在让我们来处理这个多级最佳化问题

35、.若倒过来排各级的序号，则分析起来将方便些，即，第一级表示还剩下一年，因此从第五级开始.图 7.3 上表示了我们将采用的符号，对于时间(tj)，将做出保持(K)或更换(R)的决策(dj).若决策保持这个设备，可看出tj可由下式给出tj tj11(7.5.5)若更换这个设备，则tj1.图 7.4 更详细地解释了上述记号与约定.现在假设剩下的运转时间为一年（最后一级）.定义g1(t2)当设备使用了t1年时，进入最后一个运转年，采取K或R时获得的最大赢利.那么，很清楚有g1(t2)max用式(7.5.6)的采样计算如下：d1K,RP(t2)(7.5.6)1g1(1)max26 2(1)(1)2,4

36、23.5(K)21g1(3)max26 2(3)(3)2,415.5(K)2表 7.5.1 中第一栏包含了，当设备还剩一年运转时间时，对不同使用期的设备全部计算.表 7.5.1设备役令剩下的运转年限23.5(K)20(K)15.5(K)10(K)4(R)4(R)43.5(K)59(K)71(K)67.5(K)91(K)83(K)tj12345635.5(K)47.5(K或R)27.5(R)27.5(R)27.5(R)27.5(R)47.5(R)47.5(R)47.5(R)47.5(R)63（K或R）78.5(K)63(R)63(R)63(R)75(R)75(R)75(R)现在我们需要对还剩下两

37、年或更多年运转期的设备，发展一种计算最大赢利的一般方法.定义gj(tj1)具有役令tj1的设备进入第j运转年时采用K或 R 的最大赢利.可由gj(tj1)定义很清楚地给出jgj(tj1)maxPk(tk1)(7.5.7)K,Rk1应用最佳化原理、gj(tj1)定义和式(7.5.7),可得gj(tj1)max Pj(tj1)gj1(tj)djK,R(j 2,3,4,5)(7.5.8)现在用式(7.5.8)计算g2(t3).由式(7.5.5)知tj tj11.一些采样计算为P(1)g1(2)g2(1)maxP(0)g(1)1我们前面已经计算了g1(t2).由此得126 2(1)(1)2 20 43

38、.5(K)g2(1)max24 23.5 27.5(R)43.5(K)同理P(3)g1(4)g2(3)maxP(0)g1(1)126 2(3)(3)210 25.5(K)max24 23.5 27.5(R)27.5(R)剩余的计算结果列表于 7.5.1 的各栏中.现在我们能够回答原始的问题了.若目前有一运转了一年的设备，查表 7中tj11行的第五栏，由此可计算最佳的五年策略.可看出，最大的赢利为91，并保持这个设备一年.现在移到第四栏的第二行，应为现在设备已用了两年.可看出，最佳的策仍是保持设备.现在移到第三栏第三行，则必需更换设备.若这样做，则移到了第二栏第一行.继续保持设备，并移到第一栏第

39、二行.这条路径已描绘在表 7.5.1 中.可看出，最佳策略是(KKRKK).这就是说，在运转的前两年我们保持设备，在第三年更换，然后继续保持两年.最大的赢利将为 91.当然，我们可以用这个算出来的表，来回答可能提出的其它问题.例如，假设我们希望在下一个五年里获得最大的赢利，起始点是使用了两年的设备.对于这种情况，存在有两种最佳的策略，得出相同的赢利为83.这些最佳策略是K(K K R K)或(KRKKK)读者可通过表 74 绘出这些路径.当这两种策略得到相同的总赢利 83 时，若一个是考虑到(KKRKK)在五年周期中的前两年产生 43.5 的赢利，另一个(KRKKK)在前两年中只产生35.5，

40、如果企求获得较多赢利越早越好（实际上常是这样），则第一个策略比第二个更好.练习用动态规划解下面问题：2max z 4x19x2 2x32max z 4x19x2 2x3（）x1 x2 x310 xi 0;i 1,2,32max z x1x2x3（）xi 0是整数;i 1,2,32max z x1x2x3x1 x2 x310（）x1 x2 x310（）xi 0;i 1,2,3xi 0是整数;i 1,2,3x1 x2 x310某工业部门根据国家计划的安排，拟将某种高效率的设备五台，分配给所属的甲、乙、丙三个工厂，各工厂若获得这种设备之后，可为国家提供的盈利如表7.5.2 所示.问：这五台设备如何分

41、配给各工厂，才能使国家得到的盈利最大.表 7.5.2工厂设备台数甲乙丙某工厂要对一种产品制订今后四个时期的生产计划，据估计在今后四个时期内，市场对于该产品的需求量如表7.5.3 所示.表 7.5.3时期需求量假定该厂生产每批产品的固定成本为千元，若不生产就为；每单位产品成本为千元；每个时期生产能力所允许的最大生产批量不超过个单位；每个时期末未售出的产品，每单位需付存储费.5 千元.还假定在第一个时期的初始库存为，第四个时期末的库存量也为.试问该厂应如何安排各个时期的生产与库存，才能在满足市场需求的条件下，使总成本最小.阅读材料渡河问题渡河问题人、狼、鸡、米渡河问题人、狼、鸡、米渡河问题：人、狼

42、、鸡、米各一均要过河，船一只.船需要人划，另外至多还能载一物，而当人不在时，狼要吃鸡，鸡要吃米.问人、狼、鸡、米怎样过河才能无一损失？这是一个有趣的数学游戏，问题比较简单，可用递推方法解决.但我们并不想这样做，我们希望更有意义的解决方案.解法一：因为问题中出现了四种不同的元素，故我们期望用四维向量表示它们，即（Man,Wolf,Cock,Rice）又因为当河的一岸上的情形已知时，另一岸上的情形必然已知.故可用 1 或 0 表示是否在该岸上，具体如下：左岸（1，1，1，1）（1，1，1，0）右岸（0，0，0，0）（0，0，0，1）（1，1，0，0）（1，0，0，0）（1，0，1，0）（1，0，0

43、，1）（1，0，1，1）（1，1，0，1）（0，0，1，1）（0，1，1，1）（0，1，0，1）（0，1，1，0）（0，1，0，0）（0，0，1，0）表中列出了所有可能的 16 种状态，当然，根据对称性，河的一岸还会出现另一岸的 8种情形.这种向量的表示意义也很明确，如（1，0，1，1）表示人、鸡、米在该处，而狼在另一处，等等.根据题意，有些状态是不能允许的，就是表中用标记的6 种，因为这 6 种状态中会出现河的一岸一物被另一物所吃的情况.剩下的 10 种状态我们用标记出，这些都是系统允许出现的，所以我们称为可取状态.接下来的问题是如何表示船的一次运载.船上的状态也可以用前面的四维向量表示，例

44、如，船上装有人（人必须在船上）和鸡表示为（1，0，1，0）.因为“船需要人划，另外至多还能载一物”，故船上只有 4 种可能状态：（1，0，0，0），（1，1，0，0），（1，0，1，0），（1，0，0，1）.我们在这四个向量前面加上(1)i表示第i次渡河.这样我们可以通过加法运算来表示船的一次运载.例如：在状态（1，0，1，1）之下船运载了米，即（1，0，1，1）(1)1（1，0，0，1）（0，0，1，0）.自然，由于问题的要求，运算的结果状态必须是可取状态.在上面的处理下，问题有了如下的的提法：寻求一种齐数步的系统状态转移过程，使系统从初始状态（1，1，1，1）变换到状态（0，0，0，0）.

45、如果没有这样的转移过程，或所有状态转移过程陷入循环状态，则问题无解.具体解答过程为：(1,0,0,0)(0,1,1,1)(1,0,0,0)(1,1,0,1)(1,1,0,0)(0,0,1,1)(1,1,0,0)(1,2,0,1)(1,1,1,1)(0,1,0,1)(1,0,1,0)(0,1,0,1)(1,0,1,0)(1,1,1,1)!(1,0,0,1)(0,1,1,0)(1,0,0,1)(1,1,0,2)(1,0,0,0)(0,1,0,1)!(1,1,0,0)(0,0,0,1)(1,1,0,1)(1,0,1,0)(0,1,1,1)(1,0,0,1)(0,1,0,0)(1,0,0,0)(1,0

46、,0,1)(1,1,0,0)(1,1,0,1)!(0,0,0,1)(1,0,1,0)(1,0,1,1)(1,0,0,1)(1,0,0,2)(1,0,0,0)(1,1,0,0)(1,1,0,0)(1,2,0,0)(0,1,00)(1,0,1,0)(1,1,1,0)(1,0,0,1)(1,1,0,1)!(1,0,0,0)(0,0,1,1)(1,1,0,0)(0,1,1,1)(1,0,1,1)(1,0,1,0)(0,0,0,1)(1,0,0,1)(0,0,1,0)(1,0,0,0)(0,1,1,0)(1,1,0,0)(0,0,1,0)(1,1,1,0)(1,0,1,0)(0,1,0,0)!(1,0,

47、0,1)(0,1,0,1)(1,0,0,0)(1,0,1,0)(1,0,0,0)(0,0,1,0)1(1,1,0,0)(1,1,1,0)!(1,1,0,0)(0,1,1,0)(0,0,1,0)(1,0,1,0)(1,0,1,0)(1,0,2,0)(1,0,1,0)(0,0,0,0)(1,0,0,1)(1,0,1,1)!(1,0,0,1)(0,0,1,1)上面过程中标记“”的为不允许状态（或不可取状态），标记“”的为不可能状态，标记“！”的为虽然是可取状态但产生了循环的情形.从上面的过程看出，经过 7 次状态转移，就能使状态从初始状态（1，1，1，1）变为（0，0，0，0），所以经过 7 次渡河

48、就能全部安全过河.解法二：此问题可用图解法求解.将 10 个可取状态用 10 个点来表示，如果某一个可取状态可转移到达另一可取状态，则用一条边相连，否则，不连.这样就可以得到下图G（图 7.5）：ajbichdgef图 7.5（图 G）idafchejgb图 7.6其中，顶点 a,b,c,d,e 分别表示状态（1，1，1，1）、（1，1，1，0）、（1，1，0，1）、（1，0，1，1）、（1，0，1，0），顶点 f,g,h,i,j 分别表示状态（0，1，0，1）、（0，1，0，0）、（0，0，1，0）、（0，0，0，1）、（0，0，0，0）.问题变为在图 G（图 7.5）中寻找一条从顶点 a

49、到顶点 j 的路径，每条路径就是问题的一个解.我们在图 7.6 中给出了从顶点 a 到顶点 j 的所有路径，有两条.这说明原问题有两个不同的解答.这两个解是等优的.夫妻渡河问题夫妻渡河问题：有三对夫妻要过河，船最多能载二人，由于封建意识严重，要求任意一位妻子不能在自己的丈夫不在场时与另外的男人在一起.问如何安排三对夫妻过河？此问题是阿拉伯早期的一道趣味数学题，有多种解法.有些书中将此问题提为商仆渡河商仆渡河问题：问题：三个商人各带一名仆人过河.商人已经知道，仆人密谋当仆人人数大于商人人数时，他们就杀人越货.渡河方案由商人安排，问怎样才能安全过河？此问题与前面的人、狼、鸡、米渡河问题有相似之处，

50、都是带约束条件的渡河问题，但此问题较复杂.我们用类似的方法来求解.解法一：问题中出现了男子和女子两种元素，所以我们用二维向量（H,W）来表示各种状态，当然，应满足0 H 3;0 W 3.一共有 10 种可取状态，他们是（0，0）、（0，1）、（0，2）、（0，3）、（3，0）、（3，1）、（3，2）、（3，3）、（1，1）、（2，2）.状态转移用下面向量的加法实现，(1)j(m,n)其中m,n 0,1,2;1 m n 2;j 1,2,3,在以上假设下，问题转化为：寻求由初始状态（3，3）到达状态（0，0）的奇数步的转移过程.此问题可用计算机编程求解.具体求解过程和前面的人、狼、鸡、米渡河问题的求解过程类似.请读者自己动手做做.W图 7.73。A（3，3）在 H-W 平面坐标系中，以小圆点“。”表示可取状态.在下面的运动规则之下：2。(1)第奇数次运动向下或向左运动，1。步数为 2 格；O。H(2)第偶数次运动向上或向右运动，步数为 1 或 2 格；(3)每次运动必须落在可取状态上，即在“。”上运动.寻求从初始状态 A（3，3）到达状态 O（0，0）的运动路径.图 7.7 表示了图解法的一个可实现的运动过程.其中实线表示奇数次运动，虚线表示偶数解法二：图解法步运动.此问题的答案为：经过11次状态转移，就能实现安全渡河.事实上，此问题共有四个不同的解答，读者不妨试寻找其它的解答.