动态规划的基本原理和基本应用课件.ppt

1、12 345例例1 1 多阶段资源分配问题多阶段资源分配问题 设有数量为设有数量为x的某种资源，将它投入两种的某种资源，将它投入两种生产方式生产方式A和和B中：以数量中：以数量y投入生产方式投入生产方式A，剩，剩下 的 量 投 入 生 产 方 式下 的 量 投 入 生 产 方 式 B，则 可 得 到 收 入，则 可 得 到 收 入g(y)+h(x-y)，其中，其中g(y)和和h(y)是已知函数，并且是已知函数，并且g(0)=h(0)=0；同时假设以；同时假设以y与与x-y分别投入两种分别投入两种生产方式生产方式A，B后可以回收再生产，回收率分别后可以回收再生产，回收率分别为为a与与b。试求进行

2、。试求进行n个阶段后的最大总收入。个阶段后的最大总收入。6 若以若以y与与x-y分别投入生产方式分别投入生产方式A与与B，在第一，在第一阶段生产后回收的总资源为阶段生产后回收的总资源为x1=ay+b(x-y)，再将，再将x1投入生产方式投入生产方式A和和B，则可得到收入，则可得到收入g(y1)+h(x1-y1)，继续回收资源继续回收资源x2=ay1+b(x1-y1)，若上面的过程进行若上面的过程进行n个阶段，我们希望选择个阶段，我们希望选择n个变量个变量y,y1,y2,yn-1，使这，使这n个阶段的总收入最大。个阶段的总收入最大。例例1 17 因此，我们的问题就变成：求因此，我们的问题就变成：

3、求y,y1,y2,yn-1，以使，以使g(y)+h(x-y)+g(y1)+h(x1-y1)+g(yn-1)+h(xn-1-yn-1)达到最大，且满足条件达到最大，且满足条件 x1=ay+b(x-y)x2=ay1+b(x1-y1)xn-1=ayn-2+b(xn-2-yn-2)yi与与xi均非负均非负,i=1,2,n-1 例例1 18例例2 2 生产和存储控制问题生产和存储控制问题 某工厂生产某种季节性商品，需要作下一某工厂生产某种季节性商品，需要作下一年度的生产计划，假定这种商品的生产周期需年度的生产计划，假定这种商品的生产周期需要两个月，全年共有要两个月，全年共有6个生产周期，需要作出个生产周

4、期，需要作出各个周期中的生产计划。各个周期中的生产计划。设已知各周期对该商品的需要量如下表所示设已知各周期对该商品的需要量如下表所示：周期周期123456需求量需求量5510305089例例2 2 假设这个工厂根据需要可以日夜两班生产或只是日假设这个工厂根据需要可以日夜两班生产或只是日班生产，当开足日班时，每一个生产周期能生产商品班生产，当开足日班时，每一个生产周期能生产商品1515个单位，每生产一个单位商品的成本为个单位，每生产一个单位商品的成本为100100元。当开足元。当开足夜班时，每一生产周期能生产的商品也是夜班时，每一生产周期能生产的商品也是1515个，但是由个，但是由于增加了辅助性

5、生产设备和生产辅助费用，每生产一单于增加了辅助性生产设备和生产辅助费用，每生产一单位商品的成本为位商品的成本为120120元。由于生产能力的限制，可以在元。由于生产能力的限制，可以在需求淡季多生产一些商品储存起来以备需求旺季使用，需求淡季多生产一些商品储存起来以备需求旺季使用，但存储商品是需要存储但存储商品是需要存储费用的，假设每单位商品存储一费用的，假设每单位商品存储一周期需要周期需要16元，已知开始时存储为零，年终也不存储商元，已知开始时存储为零，年终也不存储商品备下年使用，问应该如何作生产和存储计划，才能使品备下年使用，问应该如何作生产和存储计划，才能使总的生产和存储费用最小？总的生产和

6、存储费用最小？10例例2 2 设第设第i个周期的生产量为个周期的生产量为xi，周期末的存储量为，周期末的存储量为ui，那，那么这个问题用式子写出来就是：求么这个问题用式子写出来就是：求x1,x2,x6，满足条件：，满足条件：x1=5+u1 x2+u1=5+u2 x3+u2=10+u3 x4+u3=30+u4 x5+u4=50+u5 x6+u5=8 0 xi 30,0 uj,i=1,2,6;j=1,2,5 )1852345(16)(5432161xxxxxxfii3015,300120150,100)(iiiiixxxxxftjjiiuxf16116)(使使 S=为最小，其中为最小，其中11 运

7、输网络问题：如图运输网络问题：如图1 1所示的运输网络，所示的运输网络，点间连线上的数字表示两地距离点间连线上的数字表示两地距离(也可是运费、也可是运费、时间等时间等)，要求从，要求从v v1 1至至v v1010的最短路线。的最短路线。这种运输网络问题也是静态决策问题。但这种运输网络问题也是静态决策问题。但是，按照网络中点的分布，可以把它分为是，按照网络中点的分布，可以把它分为4 4个阶个阶段，而作为多阶段决策问题来研究。段，而作为多阶段决策问题来研究。12 v2 5 5 6 14 10 9 3 8 8 7 7 8 8 6 5 6 11 7 9 5 v1 v3 v4 v6 v5 v7 v9

8、v8 v10 1234图图1 1 运输网络图示运输网络图示13动态规划方法导引动态规划方法导引 为了说明动态规划的基本思想方法和特点，下面以为了说明动态规划的基本思想方法和特点，下面以图图1 1所示为例讨论求最短路问题的方法。所示为例讨论求最短路问题的方法。它的基本思它的基本思想是列举出所有可能发生的方案和结果，再对它们一想是列举出所有可能发生的方案和结果，再对它们一一进行比较，求出最优方案。这里从一进行比较，求出最优方案。这里从v v1 1到到v v1010的路程可的路程可以分为以分为4 4个阶段。第一二段的走法有三种，第三段的个阶段。第一二段的走法有三种，第三段的走法有两种，第四段的走法仅

9、一种，因此共有走法有两种，第四段的走法仅一种，因此共有3 33 32 21 11818条可能的路线，条可能的路线，5454次加法算出各条路次加法算出各条路线的距离，最后进行线的距离，最后进行1717次两两比较，可知最优路线是次两两比较，可知最优路线是v v1 1 v v2 2 v v5 5 v v8 8 v v10 10,最短距离是最短距离是272714 显然，当组成交通网络的节点很多时，用穷举显然，当组成交通网络的节点很多时，用穷举法求最优路线的计算工作量将会十分庞大，而且其法求最优路线的计算工作量将会十分庞大，而且其中包含着许多重复计算中包含着许多重复计算 ，是，是说某人从说某人从k k出

10、发，他并不顾及全线是否最短，只是选出发，他并不顾及全线是否最短，只是选择当前最短途径，择当前最短途径，“逢近便走逢近便走”，错误地以为局部，错误地以为局部最优会致整体最优，在这种想法指导下，所取决策最优会致整体最优，在这种想法指导下，所取决策必是必是v v1 1 v v2 2 v v5 5 v v9 9 v v1010 ，全程长度是，全程长度是3030；显；显然，这种方法的结果常是错误的然，这种方法的结果常是错误的15 动态规划方法动态规划方法寻求该最短路问题的基本思想是，首先将问题划寻求该最短路问题的基本思想是，首先将问题划分为分为4 4个阶段，每次的选择总是综合后继过程的一个阶段，每次的选

11、择总是综合后继过程的一并最优进行考虑，在各段所有可能状态的最优后并最优进行考虑，在各段所有可能状态的最优后继过程都已求得的情况下，全程的最优路线便也继过程都已求得的情况下，全程的最优路线便也随之得到。随之得到。为了找出所有可能状态的最优后继过程，为了找出所有可能状态的最优后继过程，动态规划方法是从过程的最后阶段开始考虑，然动态规划方法是从过程的最后阶段开始考虑，然后逆着实际过程发展的顺序，逐段向前递推计算后逆着实际过程发展的顺序，逐段向前递推计算直至始点。直至始点。16具体说，此问题先从具体说，此问题先从v v1010开始，因为开始，因为v v1010是终点。再无后继过程，故可以是终点。再无后

12、继过程，故可以接着考虑第接着考虑第4 4阶段上所有可能状态阶段上所有可能状态v v8 8,v v9 9的最优后续过程因为从的最优后续过程因为从v v8 8,v v9 9 到到v v1010的路线是唯一的，所以的路线是唯一的，所以v v8 8,v v9 9 的最优决策和最优后继过程就是到的最优决策和最优后继过程就是到v v1010 ，它们的最短距离分别是，它们的最短距离分别是1010和和1414。接着考虑阶段接着考虑阶段3 3上可能的状态上可能的状态v v5 5,v v6 6,v v7 7 到到v v1010的最优决策和最优的最优决策和最优后继过程在状态后继过程在状态V V5 5上，虽然到上，虽

13、然到v v8 8是是6 6，到，到v v9 9是是5 5，但是，但是 v2 5 5 6 14 10 9 3 8 8 7 7 8 8 6 5 6 11 7 9 5 v1 v3 v4 v6 v5 v7 v9 v8 v10 1234（10）（14）17综合考虑后继过程整体最优，取最优决策是到综合考虑后继过程整体最优，取最优决策是到v v8 8,最优后继过程是最优后继过程是v v5 5v v8 8 v v10 10，最短距离是，最短距离是1616同理，状态同理，状态v v6 6的最优决策是至的最优决策是至v v8 8 ；v v7 7的最优决策是到的最优决策是到v v9 9 。同样，当阶段同样，当阶段3

14、 3上所有可能状态的最优后继过程都已求得后，便可上所有可能状态的最优后继过程都已求得后，便可以开始考虑阶段以开始考虑阶段2 2上所有可能状态的最优决策和最优后继过程，如上所有可能状态的最优决策和最优后继过程，如v v2 2的的最优决策是到最优决策是到v v5 5,最优路线是最优路线是 v2 5 5 6 14 10 9 3 8 8 7 7 8 8 6 5 6 11 7 9 5 v1 v3 v4 v6 v5 v7 v9 v8 v10 1234（10）（14）（16）（15）（17）18v v2 2v v5 5v v8 8v v10 10，最短距离是，最短距离是2222依此类推，最后可以得到从初始状

15、态依此类推，最后可以得到从初始状态v v1 1的最优决策是到的最优决策是到v v2 2最优路线是最优路线是v v1 1v v2 2v v5 5v v8 8v v10 10，全程的最短距离，全程的最短距离是是2727。图。图1 1中红线表示最优路线，每点上圆括号内的数字表示该点到终中红线表示最优路线，每点上圆括号内的数字表示该点到终点的最短路距离。点的最短路距离。v2 5 5 6 14 10 9 3 8 8 7 7 8 8 6 5 6 11 7 9 5 v1 v3 v4 v6 v5 v7 v9 v8 v10 1234（10）（14）（16）（15）（17）（22）（22）（21）（27）19综上

16、所述可见，全枚举法虽可找出最优方案，但不是个好算综上所述可见，全枚举法虽可找出最优方案，但不是个好算法，局部最优法则完全是个错误方法，只有动态规划方法属法，局部最优法则完全是个错误方法，只有动态规划方法属较科学有效的算法。它的基本思想是，把一个比较复杂的问较科学有效的算法。它的基本思想是，把一个比较复杂的问题分解为一系列同类型的更易求解的子问题，便于应用计算题分解为一系列同类型的更易求解的子问题，便于应用计算机。整个求解过程分为两个阶段，先按整体最优的思想逆序机。整个求解过程分为两个阶段，先按整体最优的思想逆序地求出各个子问题中所有可能状态的最优决策与最优路线值，地求出各个子问题中所有可能状态

17、的最优决策与最优路线值，然后再顺序地求出整个问题的最优策略和最优路线。计算过然后再顺序地求出整个问题的最优策略和最优路线。计算过程中，系统地删去了所有中间非最优的方案组合，从而使计程中，系统地删去了所有中间非最优的方案组合，从而使计算工作量比穷举法大为减少。算工作量比穷举法大为减少。20拾火柴游戏拾火柴游戏:桌子上放桌子上放30根火柴根火柴,每人一次每人一次可拾起可拾起13根根,谁拾起最后一根火柴谁输谁拾起最后一根火柴谁输,如果你先选择如果你先选择,如何保证你能赢得游戏？如何保证你能赢得游戏？292521171395121动态规划是解决动态规划是解决多阶段决策问题多阶段决策问题的一种方法。所谓

18、多阶段的一种方法。所谓多阶段决策问题是指这样的决策问题：其过程可分为若干个相互联决策问题是指这样的决策问题：其过程可分为若干个相互联系的阶段，每一阶段都对应着一组可供选择的决策，每一决系的阶段，每一阶段都对应着一组可供选择的决策，每一决策的选定即依赖于当前面临的状态，又影响以后总体的效果。策的选定即依赖于当前面临的状态，又影响以后总体的效果。ABCDE状态A状态B状态C状态D状态E状态F决策A决策D决策E当每一阶段的决策选定以后，就构成一个决策序列，称为一个当每一阶段的决策选定以后，就构成一个决策序列，称为一个决策B决策C策略策略，它对应着一个确定的效果。它对应着一个确定的效果。多阶段决策问题

19、就是寻找使多阶段决策问题就是寻找使此效果最好的策略。此效果最好的策略。22动态规划问题实例动态规划问题实例例例 给定一个线路网络，给定一个线路网络，AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143要从要从A向向F铺设一条输油管道，铺设一条输油管道，各点间连线上的数字表示距离，问应选择什么路线，可使总各点间连线上的数字表示距离，问应选择什么路线，可使总距离最短？距离最短？239.2 动态规划的基本概念和基本原理动态规划的基本概念和基本原理一、基本概念一、基本概念阶段阶段：是指问题需要做出决策的步数。阶段总数常记为：是指问题需要做出决策的步数。阶段总

20、数常记为n，相，相应的是应的是n个阶段的决策问题。阶段的序号常记为个阶段的决策问题。阶段的序号常记为k，称为，称为阶段阶段变量变量，k=1,2,n.k即可以是顺序编号也可以是逆序编号，即可以是顺序编号也可以是逆序编号，常用顺序编号。常用顺序编号。全过程全过程；后部子过程后部子过程。状态状态：各阶段开始时的客观条件，第：各阶段开始时的客观条件，第k阶段的状态常用阶段的状态常用状态状态变量变量 表示，状态变量取值的集合称为表示，状态变量取值的集合称为状态集合状态集合，用，用表示。表示。kxkX例如，例中，例如，例中，.,2121BBXAX 24AB1B2C1C2C3C4D1D2D3E1E2F452

21、368775845348435623143第1阶段第2阶段第3阶段第4阶段第5阶段状态1状态2状态3状态4状态5状态6.,2121BBXAX 25决策决策：是指从某阶段的某个状态出发，在若干个不同方案中：是指从某阶段的某个状态出发，在若干个不同方案中做出的选择。表示决策的变量，称为做出的选择。表示决策的变量，称为决策变量决策变量，用，用 表示表示)(kkxu例如：例如：表示走到表示走到3阶段阶段,当处于当处于C2 路口时，下一路口时，下一步奔步奔D1.123)(DCu 时的允许决策集合记为时的允许决策集合记为 ，例如：，例如：策略策略:全过程策略全过程策略 p1n；子策略；子策略pkn；最优策

22、略最优策略。kx)(kkxU,)(32112CCCBU 状态转移方程状态转移方程：是从上一阶段的某一状态值转变为下一阶段：是从上一阶段的某一状态值转变为下一阶段某一状态值的转移规律，用某一状态值的转移规律，用),(1kkkkuxTx 表示。表示。决策变量允许的取值范围称为决策变量允许的取值范围称为允许决策集合允许决策集合，第，第k阶段状态为阶段状态为 26AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第1阶段第2阶段第3阶段第4阶段第5阶段状态1状态2状态3状态4状态5状态6123)(DCu,)(32112CCCBU 27指标函数指标函数：分：

23、分阶段指标函数阶段指标函数和和过程指标函数过程指标函数。阶段指标函数阶段指标函数是指第是指第k阶段从状态阶段从状态 出发，采取决策出发，采取决策 时的效益，用时的效益，用kxku),(kkkuxv表示。而表示。而过程指标函数过程指标函数指从第指从第k阶段的某状态出发，阶段的某状态出发，采取子策略采取子策略,1nkkknuuup 时所得到的阶段效益之和：时所得到的阶段效益之和：nkjjjjknkknuxvpxV),(),(最优指标函数最优指标函数：表示从第：表示从第k阶段状态为阶段状态为 时采用最佳策略时采用最佳策略kx*knp到过程终止时的最佳效益。记为到过程终止时的最佳效益。记为),(),(

24、)()(*knkknxUpknkknkkpxVoptpxVxfkknkn 28AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第1阶段第2阶段第3阶段第4阶段第5阶段状态1状态2状态3状态4状态5状态6212(,)3vB C 35211(,)11vCD E F 29其中其中 opt 可根据具体情况取可根据具体情况取max 或或min。基本方程基本方程：此为逐段递推求和的依据，一般为：此为逐段递推求和的依据，一般为：0)(1,1,)(),()(1111)(nnkkkkksUukkxfnnkxfuxvoptxfkkk式中式中opt 可根据题意取可根据

25、题意取 max 或或 min.例如，例的基本方程为：例如，例的基本方程为：0)(1,2,3,4,5)(),(min)(6611xfkxfuxdxfkkkkkukkk30v即确定各个变量及方程函数即确定各个变量及方程函数v1 1、阶段变量、阶段变量v2 2、状态变量：选择时要满足两个条件：、状态变量：选择时要满足两个条件：v能正确描述受控过程的演变特性能正确描述受控过程的演变特性v要满足无后效性要满足无后效性v无后效性无后效性：给定了某阶段状态，在这阶段以后过：给定了某阶段状态，在这阶段以后过程的发展不受这阶段以前各阶段状态的影响。程的发展不受这阶段以前各阶段状态的影响。v3 3、决策变量、决策

26、变量v4 4、列出状态转移方程、列出状态转移方程v5 5、指标函数、指标函数31三、三、最优化原理最优化原理：最优策略的任一后部子策略都是最优的。：最优策略的任一后部子策略都是最优的。无论以前状态决策如何，从眼下直到最后的诸决策必构成最无论以前状态决策如何，从眼下直到最后的诸决策必构成最优子策略。优子策略。动态规划应用举例动态规划应用举例例例1 最短路线问题最短路线问题AB1B2C1C2C3C4D1D2D3E1E2F45236877584534843562314332逆序递推方程：逆序递推方程：0)(1,2,3,4,5)(),(min)(6611xfkxfuxdxfkkkkkukkk（1）k=

27、5 时，状态时，状态,215EEX 它们到它们到F 点的距离即为点的距离即为最短路。最短路。,4)(15 Ef;3)(25 Ef,)(1*5FEu.)(2*5FEu AB1B2C1C2C3C4D1D2D3E1E2F45236877584534843562314333AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（2）k=4 时，状态时，状态,3214DDDX 它们到它们到F 点需经过中途点需经过中途点点E，需一一分析从，需一一分析从E 到到 F的最短路：先说从的最短路：先说从D1到到F 的最短路的最短路有两种选择：经过有两种选择：经过 E1,E

28、2,比较最短。比较最短。.)(2*5FEu,)(1*5FEu34AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143)(),(),(),(min)(252141511414EfEDdEfEDdDf .735,43min这说明由这说明由 D1 到到F 的最短距离为的最短距离为7，其路径为，其路径为.11FED相应的决策为：相应的决策为：.)(11*4EDu.)(2*5FEu,)(1*5FEu35)(),(),(),(min)(252241512424EfEDdEfEDdDf .532,46min 这说明由这说明由 D2 到到F 的最短距离为的最短距离为

29、5，其路径为，其路径为.22FED相应的决策为：相应的决策为：.)(22*4EDu AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143.)(2*5FEu,)(1*5FEu.)(11*4EDu36AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143)(),(),(),(min)(252341513434EfEDdEfEDdDf .533,41min即即 D3 到到F 的最短距离为的最短距离为5，其路径为，其路径为31.DEF相应的决策为：相应的决策为：.)(13*4EDu.)(2*5FEu,)(1*5FEu

30、.)(11*4EDu.)(22*4EDu37（3）k=3 时，状态时，状态,43214CCCCX )(),(),(),(min)(242131411313DfDCdDfDCdCf .1258,75min这说明由这说明由 C1 到到F 的最短距离为的最短距离为12，相应的决策为，相应的决策为.)(11*3DCu AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143.)(2*5FEu,)(1*5FEu.)(11*4EDu.)(22*4EDu.)(13*4EDu5)(24Df7)(14Df38AB1B2C1C2C3C4D1D2D3E1E2F45236877

31、5845348435623143)(),(),(),(min)(242231412323DfDCdDfDCdCf .1055,74min即由即由 C2 到到F 的最短距离为的最短距离为10，相应的决策为，相应的决策为.)(22*3DCu)(),(),(),(min)(343332423333DfDCdDfDCdCf .854,53min.)(2*5FEu,)(1*5FEu.)(11*4EDu.)(22*4EDu.)(13*4EDu.)(11*3DCu7)(14Df5)(24Df5)(34Df39即由即由 C3 到到F 的最短距离为的最短距离为8，相应的决策为，相应的决策为.)(23*3DCu)

32、(),(),(),(min)(343432424343DfDCdDfDCdCf .954,58min即由即由 C4 到到F 的最短距离为的最短距离为9，相应的决策为，相应的决策为.)(34*3DCu AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143.)(2*5FEu,)(1*5FEu.)(11*4EDu.)(22*4EDu.)(13*4EDu.)(11*3DCu.)(22*3DCu5)(24Df5)(34Df40AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（4）k=2时，状态时，状态,212BB

33、X)(),(),(),(),(),(min)(33312232121311212CfCBdCfCBdCfCBdBf .1386,103,122min这说明由这说明由 B1 到到F 的最短距离为的最短距离为13，相应的决策为，相应的决策为.)(21*2CBu.)(2*5FEu,)(1*5FEu.)(11*4EDu.)(22*4EDu.)(13*4EDu.)(11*3DCu.)(22*3DCu.)(23*3DCu.)(34*3DCu12)(13Cf10)(23Cf8)(33Cf41)(),(),(),(),(),(min)(43422333222322222CfCBdCfCBdCfCBdBf .1

34、597,87,108min即由即由 B2到到F 的最短距离为的最短距离为15，相应的决策为，相应的决策为.)(32*2CBu AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143.)(2*5FEu,)(1*5FEu.)(11*4EDu.)(22*4EDu.)(13*4EDu.)(11*3DCu.)(22*3DCu.)(23*3DCu.)(34*3DCu.)(21*2CBu9)(43Cf10)(23Cf8)(33Cf42AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（5）k=1 时，只有一个状态点时，只

35、有一个状态点A,则则)(),(),(),(min)(222112111BfBAdBfBAdAf .17155,134min即由即由 A到到F 的最短距离为的最短距离为17，相应的决策为，相应的决策为.)(1*1BAu.)(2*5FEu,)(1*5FEu.)(11*4EDu.)(22*4EDu.)(13*4EDu.)(11*3DCu.)(22*3DCu.)(23*3DCu.)(34*3DCu.)(32*2CBu.)(21*2CBu13)(12Bf15)(22Bf43,)(21*2CBu,)(22*3DCu,)(22*4EDu.)(2*5FEu 所以最优路线为：所以最优路线为：FEDCBA2221

36、AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143.)(2*5FEu,)(1*5FEu.)(11*4EDu.)(22*4EDu.)(13*4EDu.)(11*3DCu.)(22*3DCu.)(23*3DCu.)(34*3DCu.)(32*2CBu.)(21*2CBu再按计算顺序反推可得最优决策序列：再按计算顺序反推可得最优决策序列：,)(1*1BAu 44顺序递推方程：顺序递推方程：初初始始条条件件0)(5,4,3,2,1)(),(min)(10111xfkxfuxdxfkkkkkukkkAB1B2C1C2C3C4D1D2D3E1E2F452368

37、775845348435623143例例1：1阶段2阶段3阶段4阶段5阶段行走方向行走方向第第k阶段阶段45AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143K=1 时时)(),()()(10111121xfABdBfxf注意到：注意到：0)()(010Afxf所以所以ABu)(1*1)(),()()(10212121xfABdBfxf,4)(11Bf,5)(21BfABu)(2*146K=2 时时642)(),()()(111121232BfBCdCfxf11*2)(BCuAB1B2C1C2C3C4D1D2D3E1E2F4523687758453

38、48435623143ABu)(2*1ABu)(1*1)(),(),(),(min)()(21222111222232BfBCdBfBCdCfxf758,43min12*2)(BCu)(),(),(),(min)()(21232111323232BfBCdBfBCdCfxf4713*2)(BCu,1257)(),()()(212424232BfBCdCfxf24*2)(BCuK=3 时时)(),(),(),(min)()(22212121131343CfCDdCfCDdDfxf1174,65minAB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143A

39、Bu)(2*1ABu)(1*1,1057,46min11*2)(BCu12*2)(BCu6)(12Cf7)(22Cf48AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143ABu)(2*1ABu)(1*112*2)(BCu11*2)(BCu13*2)(BCu24*2)(BCu,)(11*3CDu21*3)(CDu或或类似地，可算出：类似地，可算出：12)(23Df22*3)(CDu14)(33Df33*3)(CDu6)(12Cf7)(22Cf12)(42Cf10)(32Cf4914)(14Ef11*4)(DEu14)(24Ef22*4)(DEu17)

40、(5Ff2*5)(EFu最优策略：最优策略：2*5)(EFu 22*4)(DEu AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143ABu)(2*1ABu)(1*111*2)(BCu12*2)(BCu13*2)(BCu24*2)(BCu,)(11*3CDu或21*3)(CDu22*3)(CDu33*3)(CDu12)(23Df14)(33Df11)(13Df5022*3)(CDu12*2)(BCuABu)(1*1最短路径：最短路径：FEDCBA2221最短路长：最短路长：17)(5 Ff注注：顺序解法与逆序解法无本质区别，一般来说，当初始状：顺序解

41、法与逆序解法无本质区别，一般来说，当初始状态给定时用逆序解法，当终止状态给定时用顺序解法。若问态给定时用逆序解法，当终止状态给定时用顺序解法。若问题给定了一个初始状态与一个终止状态，则两种方法均可使题给定了一个初始状态与一个终止状态，则两种方法均可使用。用。2*5)(EFu 22*4)(DEu 51AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（4，F）（3，F）（5，E1）（5，E2）（7，E1）（12，D1）（10，D2）（8，D2）（9，D3）（13，C2）（15，C3）（17，B1）v作业：作业：vP235 5.2（双标号法，顺序逆序选

42、一）（双标号法，顺序逆序选一）529.3 9.3 背背 包包 问问 题题 一般的提法为：一旅行者携带背包去登山。已知他所能承受一般的提法为：一旅行者携带背包去登山。已知他所能承受 的背包重量的极限为的背包重量的极限为a(千克千克)，现有，现有n种物品可供他选择装入种物品可供他选择装入背包。第背包。第i种物品的单位重量为种物品的单位重量为 (千克千克)，其价值（可以是表，其价值（可以是表明本物品对登山者的重要性指标）是携带数量明本物品对登山者的重要性指标）是携带数量 的函数的函数 （i=1 1，2 2，n）.问旅行者应如何选择携带物品的件问旅行者应如何选择携带物品的件数，以使总价值最大？数，以使

43、总价值最大？ia()iigxix此模型解决的是运输工具包括卫星的最优装载问题。此模型解决的是运输工具包括卫星的最优装载问题。其数学模型为：其数学模型为：53设设 为第为第 i 种物品装入的件数，则背包问题可归结为如下种物品装入的件数，则背包问题可归结为如下 ix形式的整数规划模型：形式的整数规划模型：niiixgz1)(max),2,101nixaxainiii（整数下面从一个例子来分析动态规划建模。下面从一个例子来分析动态规划建模。例例 有一辆最大货运量为有一辆最大货运量为10 t 的卡车，用以装载的卡车，用以装载3种种货物，每种货物的单位重量及相应单位价值如表货物，每种货物的单位重量及相应

44、单位价值如表4 所示。所示。应如何装载可使总价值最大？应如何装载可使总价值最大？54货物编号i 1 2 3单位重量（t）3 4 5单位价值 ci 4 5 6表 4 设第设第 种货物装载的件数为种货物装载的件数为 ix),3,2,1(ii则问题可表为：则问题可表为：321654maxxxxz)3,2,1(,010543321ixxxxi整数阶段阶段k:将可装入物品按将可装入物品按1，2，3的顺序排序，每段装入一的顺序排序，每段装入一种物品，共划分种物品，共划分3个阶段，即个阶段，即k=1,2,3.55状态变量状态变量 ：在第在第k段开始时，背包中允许装入前段开始时，背包中允许装入前k种种物品的总

45、重量。物品的总重量。1ks决策变量决策变量 ：装入第装入第k种物品的件数。种物品的件数。kx状态转移方程：状态转移方程：kkkkxass1最优指标函数最优指标函数 ：在背包中允许装入物品的总重量不超在背包中允许装入物品的总重量不超过过 kg，采取最优策略只装前，采取最优策略只装前k种物品时的最大使用价值种物品时的最大使用价值。)(1kksf1ks货物1货物2货物3104s3435xss2324xss1213xss1114)(xxg2225)(xxg3336)(xxg24x35x13x321654maxxxxz )3,2,1(,010543321ixxxxi整数整数56由此可得动态规划的顺序递推

46、方程为：由此可得动态规划的顺序递推方程为：0)(3,2,1)()(max)(1011011sfkxasfxgsfkkkkkksxakkkkk货物1货物2货物3104s3435xss2324xss1213xss1114)(xxg2225)(xxg3336)(xxg24x35x13xK=1 时时)()(max)(10113021121sfxgsfxsx为整数4max130121xxsx为整数321654maxxxxz )3,2,1(,010543321ixxxxi整数整数57货物1货物2货物3104s3435xss2324xss1213xss1114)(xxg2225)(xxg3336)(xxg2

47、4x35x13xK=1 时时)()(max)(10113021121sfxgsfxsx为整数4max130121xxsx为整数注意到：注意到：10,1,02s例如：例如：72s时，时，4max)7(1730111xfxx为整数4max12,1,01xx 88,4,0max2*1x其它计算结果见表其它计算结果见表5：321654maxxxxz )3,2,1(,010543321ixxxxi整数整数581x2s14x)(21sf1x0 1 2 3 0 1 2 3 4 5 6 7 8 9 104 40 04 40 0 4 40 0 4 40 0 4 41 1 4 40 40 41 41 42 24

48、40 40 41 41 42 42 43 3000448121200011233表 559货物1货物2货物3104s3435xss2324xss1213xss1114)(xxg2225)(xxg3336)(xxg24x35x13xK=2 时时)()(max)(21224032232sfxgsfxsx为整数)4(5max231240232xsfxxsx为整数其中其中10,1,03s例如：例如：103s时时，)410(5max)10()(212104023222xfxfsfxx为整数)410(5max2122,1,02xfxx)0(10),6(5),10(0max111fff321654maxxx

49、xz )3,2,1(,010543321ixxxxi整数整数60)0(10),6(5),10(0max111fff13010,85,120max1*2x1x2s14x)(21sf1x0 1 2 3 0 1 2 3 4 5 6 7 8 9 104 40 04 40 0 4 40 0 4 40 0 4 41 1 4 40 40 41 41 42 24 40 40 41 41 42 42 43 30004812000123表 561其它计算结果见表其它计算结果见表6：2x3s)4(52312xsfx)(32sf2x 0 1 2 0 1 2 3 4 5 6 7 8 9 105 50 00 0 5 50

50、 04 4 5 51 10 0 5 50 012 512 51 18 58 52 20 0 0513011表 662货物1货物2货物3104s3435xss2324xss1213xss1114)(xxg2225)(xxg3336)(xxg24x35x13xK=3 时时)()(max)10()(323350343343sfxgfsfxsx为整数)510(6max323105033xfxxx为整数)510(6max3232,1,03xfxx)0(12),5(6),10(0max222fff632x3s)4(52312xsfx)(32sf2x 0 1 2 0 1 2 3 4 5 6 7 8 9 10