动态规划的基本原理和基本应用讲稿.ppt

《动态规划的基本原理和基本应用讲稿.ppt》由会员分享，可在线阅读，更多相关《动态规划的基本原理和基本应用讲稿.ppt（82页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于动态规划的基本原理和基本应用第一页，讲稿共八十二页哦2 第二页，讲稿共八十二页哦3第三页，讲稿共八十二页哦4第四页，讲稿共八十二页哦5例例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后可以

2、回收再生产，回收后可以回收再生产，回收率分别为率分别为a与与b。试求进行。试求进行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个阶段的

3、总收入最大。个阶段的总收入最大。例例1 1第六页，讲稿共八十二页哦7 因此，我们的问题就变成：求因此，我们的问题就变成：求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 1第七页，讲稿共八十二页哦8例例2 2 生产和存储控制问题生产和存储控制问题 某工厂生产某种季节性商品，需要作下一某工厂生产某种季节性商品，需要作下一年

4、度的生产计划，假定这种商品的生产周期需年度的生产计划，假定这种商品的生产周期需要两个月，全年共有要两个月，全年共有6个生产周期，需要作出个生产周期，需要作出各个周期中的生产计划。各个周期中的生产计划。设已知各周期对该商品的需要量如下表所示设已知各周期对该商品的需要量如下表所示：周期周期123456需求量需求量551030508第八页，讲稿共八十二页哦9例例2 2 假设这个工厂根据需要可以日夜两班生产或只是日班生产假设这个工厂根据需要可以日夜两班生产或只是日班生产，当开足日班时，每一个生产周期能生产商品，当开足日班时，每一个生产周期能生产商品1515个单位，每生个单位，每生产一个单位商品的成本为

5、产一个单位商品的成本为100100元。当开足夜班时，每一生产周期能元。当开足夜班时，每一生产周期能生产的商品也是生产的商品也是1515个，但是由于增加了辅助性生产设备和生产辅助个，但是由于增加了辅助性生产设备和生产辅助费用，每生产一单位商品的成本为费用，每生产一单位商品的成本为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

7、)1852345(16)(5432161xxxxxxfii3015,300120150,100)(iiiiixxxxxftjjiiuxf16116)(使使 S=为最小，其中为最小，其中第十页，讲稿共八十二页哦11 运输网络问题：如图运输网络问题：如图1 1所示的运输网络，点间所示的运输网络，点间连线上的数字表示两地距离连线上的数字表示两地距离(也可是运费、时间等也可是运费、时间等)，要，要求从求从v v1 1至至v v1010的最短路线。的最短路线。这种运输网络问题也是静态决策问题。但是，这种运输网络问题也是静态决策问题。但是，按照网络中点的分布，可以把它分为按照网络中点的分布，可以把它分为4

8、 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 v8 v10 1234图图1 1 运输网络图示运输网络图示第十二页，讲稿共八十二页哦13动态规划方法导引动态规划方法导引 为了说明动态规划的基本思想方法和特点，下面以为了说明动态规划的基本思想方法和特点，下面以图图1 1所示为例讨论求最短路问题的方法。所示为例讨论求最短路问题的方法。它的基本思想是列它的基本思想是列举出所有可能发生的方案和结果，再对它们一一

9、进行比较，举出所有可能发生的方案和结果，再对它们一一进行比较，求出最优方案。这里从求出最优方案。这里从v v1 1到到v v1010的路程可以分为的路程可以分为4 4个阶段。第一个阶段。第一二段的走法有三种，第三段的走法有两种，第四段的走法二段的走法有三种，第三段的走法有两种，第四段的走法仅一种，因此共有仅一种，因此共有3 33 32 21 11818条可能的路线，条可能的路线，5454次加次加法算出各条路线的距离，最后进行法算出各条路线的距离，最后进行1717次两两比较，可知次两两比较，可知最优路线是最优路线是v v1 1 v v2 2 v v5 5 v v8 8 v v10 10,最短距离

10、是最短距离是2727第十三页，讲稿共八十二页哦14 显然，当组成交通网络的节点很多时，用穷举法显然，当组成交通网络的节点很多时，用穷举法求最优路线的计算工作量将会十分庞大，而且其中包含求最优路线的计算工作量将会十分庞大，而且其中包含着许多重复计算着许多重复计算 ，是说某人从，是说某人从k k出发，他并不顾及全线是否最短，只是选择当前最短出发，他并不顾及全线是否最短，只是选择当前最短途径，途径，“逢近便走逢近便走”，错误地以为局部最优会致整体最优，错误地以为局部最优会致整体最优，在这种想法指导下，所取决策必是，在这种想法指导下，所取决策必是v v1 1 v v2 2 v v5 5 v v9 9

11、v v1010 ，全程长度是，全程长度是3030；显然，这种方法的结果常是错误的；显然，这种方法的结果常是错误的第十四页，讲稿共八十二页哦15 动态规划方法寻求该最动态规划方法寻求该最短路问题的基本思想是，首先将问题划分为短路问题的基本思想是，首先将问题划分为4 4个阶段，每个阶段，每次的选择总是综合后继过程的一并最优进行考虑，在次的选择总是综合后继过程的一并最优进行考虑，在各段所有可能状态的最优后继过程都已求得的情况下各段所有可能状态的最优后继过程都已求得的情况下，全程的最优路线便也随之得到。，全程的最优路线便也随之得到。为了找出所有可能状态的最优后继过程，动态规为了找出所有可能状态的最优后

12、继过程，动态规划方法是从过程的最后阶段开始考虑，然后逆着实际过划方法是从过程的最后阶段开始考虑，然后逆着实际过程发展的顺序，逐段向前递推计算直至始点。程发展的顺序，逐段向前递推计算直至始点。第十五页，讲稿共八十二页哦16具体说，此问题先从具体说，此问题先从v v1010开始，因为开始，因为v v1010是终点。再无后继过程，故可以接着考虑第是终点。再无后继过程，故可以接着考虑第4 4阶段上所有可能状态阶段上所有可能状态v v8 8,v v9 9的最优后续过程因为从的最优后续过程因为从v v8 8,v v9 9 到到v v1010的路线是唯一的，所的路线是唯一的，所以以v v8 8,v v9 9

13、 的最优决策和最优后继过程就是到的最优决策和最优后继过程就是到v v1010 ，它们的最短距离分别是，它们的最短距离分别是1010和和1414。接着考虑阶段接着考虑阶段3 3上可能的状态上可能的状态v v5 5,v v6 6,v v7 7 到到v v1010的最优决策和最优后继过程在状的最优决策和最优后继过程在状态态V V5 5上，虽然到上，虽然到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）第十六页，讲

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 3上所有可能状态的最优后继过程都已求得后，便可以开始考上所有可能状态的最优后继过程都已求得后，便可以开始考虑阶段虑阶段2 2上所有可能状态的最优决策和最优后继过程，如上所有可能状态的最优决策和最优后继过程，如v v2 2的最优决

15、策是到的最优决策是到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依此类推，最后可以得到从初始状态依此类推，最后可以得到从初始状态v v1 1的最优决策是到的最优决策是到v v2 2最优路线是最优路线是v v1 1v v2 2v v5 5v v8 8v v10 10，全程的最短距离是，全程的最短距离

16、是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综上所述可见，全枚举法虽可找出最优方案，但不是个好算法，局部综上所述可见，全枚举法虽可找出最优方案，但不是个好算法，局部最优法则完全是个错误方法，只有动态规划方法属较科学有效的算法最

17、优法则完全是个错误方法，只有动态规划方法属较科学有效的算法。它的基本思想是，把一个比较复杂的问题分解为一系列同类型的更。它的基本思想是，把一个比较复杂的问题分解为一系列同类型的更易求解的子问题，便于应用计算机。整个求解过程分为两个阶段，先易求解的子问题，便于应用计算机。整个求解过程分为两个阶段，先按整体最优的思想逆序地求出各个子问题中所有可能状态的最优决策按整体最优的思想逆序地求出各个子问题中所有可能状态的最优决策与最优路线值，然后再顺序地求出整个问题的最优策略和最优路线。与最优路线值，然后再顺序地求出整个问题的最优策略和最优路线。计算过程中，系统地删去了所有中间非最优的方案组合，从而使计算计

18、算过程中，系统地删去了所有中间非最优的方案组合，从而使计算工作量比穷举法大为减少。工作量比穷举法大为减少。第十九页，讲稿共八十二页哦20拾火柴游戏拾火柴游戏:桌子上放桌子上放30根火柴根火柴,每人一次可每人一次可拾起拾起13根根,谁拾起最后一根火柴谁输谁拾起最后一根火柴谁输,如果你如果你先选择先选择,如何保证你能赢得游戏？如何保证你能赢得游戏？2925211713951第二十页，讲稿共八十二页哦21动态规划是解决动态规划是解决多阶段决策问题多阶段决策问题的一种方法。所谓多阶段的一种方法。所谓多阶段决策问题是指这样的决策问题：其过程可分为若干个相互联决策问题是指这样的决策问题：其过程可分为若干个

19、相互联系的阶段，每一阶段都对应着一组可供选择的决策，每一决系的阶段，每一阶段都对应着一组可供选择的决策，每一决策的选定即依赖于当前面临的状态，又影响以后总体的效果。策的选定即依赖于当前面临的状态，又影响以后总体的效果。ABCDE状态A状态B状态C状态D状态E状态F决策A决策D决策E当每一阶段的决策选定以后，就构成一个决策序列，称为一个当每一阶段的决策选定以后，就构成一个决策序列，称为一个决策B决策C策略策略，它对应着一个确定的效果。它对应着一个确定的效果。多阶段决策问题就是寻找使多阶段决策问题就是寻找使此效果最好的策略。此效果最好的策略。第二十一页，讲稿共八十二页哦22动态规划问题实例动态规划

20、问题实例例例 给定一个线路网络，给定一个线路网络，AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143要从要从A向向F铺设一条输油管道，铺设一条输油管道，各点间连线上的数字表示距离，问应选择什么路线，可使总各点间连线上的数字表示距离，问应选择什么路线，可使总距离最短？距离最短？第二十二页，讲稿共八十二页哦239.2 动态规划的基本概念和基本原理动态规划的基本概念和基本原理一、基本概念一、基本概念阶段阶段：是指问题需要做出决策的步数。阶段总数常记为：是指问题需要做出决策的步数。阶段总数常记为n，相，相应的是应的是n个阶段的决策问题。阶段的序号常记为个阶

21、段的决策问题。阶段的序号常记为k，称为，称为阶段阶段变量变量，k=1,2,n.k即可以是顺序编号也可以是逆序编号，即可以是顺序编号也可以是逆序编号，常用顺序编号。常用顺序编号。全过程全过程；后部子过程后部子过程。状态状态：各阶段开始时的客观条件，第：各阶段开始时的客观条件，第k阶段的状态常用阶段的状态常用状态状态变量变量 表示，状态变量取值的集合称为表示，状态变量取值的集合称为状态集合状态集合，用，用表示。表示。kxkX例如，例中，例如，例中，.,2121BBXAX 第二十三页，讲稿共八十二页哦24AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143

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

23、x)(kkxU,)(32112CCCBU 状态转移方程状态转移方程：是从上一阶段的某一状态值转变为下一阶段：是从上一阶段的某一状态值转变为下一阶段某一状态值的转移规律，用某一状态值的转移规律，用),(1kkkkuxTx 表示。表示。决策变量允许的取值范围称为决策变量允许的取值范围称为允许决策集合允许决策集合，第，第k阶段状态为阶段状态为 第二十五页，讲稿共八十二页哦26AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第1阶段第2阶段第3阶段第4阶段第5阶段状态1状态2状态3状态4状态5状态6123)(DCu,)(32112CCCBU 第二十六页，

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

25、为到过程终止时的最佳效益。记为),(),()()(*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

26、)(nnkkkkksUukkxfnnkxfuxvoptxfkkk式中式中opt 可根据题意取可根据题意取 max 或或 min.例如，例的基本方程为：例如，例的基本方程为：0)(1,2,3,4,5)(),(min)(6611xfkxfuxdxfkkkkkukkk第二十九页，讲稿共八十二页哦30v即确定各个变量及方程函数即确定各个变量及方程函数v1 1、阶段变量、阶段变量v2 2、状态变量：选择时要满足两个条件：、状态变量：选择时要满足两个条件：v能正确描述受控过程的演变特性能正确描述受控过程的演变特性v要满足无后效性要满足无后效性v无后效性无后效性：给定了某阶段状态，在这阶段以后过程的发展：给

27、定了某阶段状态，在这阶段以后过程的发展不受这阶段以前各阶段状态的影响。不受这阶段以前各阶段状态的影响。v3 3、决策变量、决策变量v4 4、列出状态转移方程、列出状态转移方程v5 5、指标函数、指标函数第三十页，讲稿共八十二页哦31三、三、最优化原理最优化原理：最优策略的任一后部子策略都是最优的。：最优策略的任一后部子策略都是最优的。无论以前状态决策如何，从眼下直到最后的诸决策必构成最优子策略。无论以前状态决策如何，从眼下直到最后的诸决策必构成最优子策略。动态规划应用举例动态规划应用举例例例1 最短路线问题最短路线问题AB1B2C1C2C3C4D1D2D3E1E2F45236877584534

28、8435623143第三十一页，讲稿共八十二页哦32逆序递推方程：逆序递推方程：0)(1,2,3,4,5)(),(min)(6611xfkxfuxdxfkkkkkukkk（1）k=5 时，状态时，状态,215EEX 它们到它们到F 点的距离即为点的距离即为最短路。最短路。,4)(15 Ef;3)(25 Ef,)(1*5FEu.)(2*5FEu AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第三十二页，讲稿共八十二页哦33AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（2）k=4 时，状态时，状态

29、,3214DDDX 它们到它们到F 点需经过中途点需经过中途点点E，需一一分析从，需一一分析从E 到到 F的最短路：先说从的最短路：先说从D1到到F 的最短路的最短路有两种选择：经过有两种选择：经过 E1,E2,比较最短。比较最短。.)(2*5FEu,)(1*5FEu第三十三页，讲稿共八十二页哦34AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143)(),(),(),(min)(252141511414EfEDdEfEDdDf .735,43min这说明由这说明由 D1 到到F 的最短距离为的最短距离为7，其路径为，其路径为.11FED相应的决策为

30、：相应的决策为：.)(11*4EDu.)(2*5FEu,)(1*5FEu第三十四页，讲稿共八十二页哦35)(),(),(),(min)(252241512424EfEDdEfEDdDf .532,46min 这说明由这说明由 D2 到到F 的最短距离为的最短距离为5，其路径为，其路径为.22FED相应的决策为：相应的决策为：.)(22*4EDu AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143.)(2*5FEu,)(1*5FEu.)(11*4EDu第三十五页，讲稿共八十二页哦36AB1B2C1C2C3C4D1D2D3E1E2F4523687758

31、45348435623143)(),(),(),(min)(252341513434EfEDdEfEDdDf .533,41min即即 D3 到到F 的最短距离为的最短距离为5，其路径为，其路径为31.DEF相应的决策为：相应的决策为：.)(13*4EDu.)(2*5FEu,)(1*5FEu.)(11*4EDu.)(22*4EDu第三十六页，讲稿共八十二页哦37（3）k=3 时，状态时，状态,43214CCCCX )(),(),(),(min)(242131411313DfDCdDfDCdCf .1258,75min这说明由这说明由 C1 到到F 的最短距离为的最短距离为12，相应的决策为，相

32、应的决策为.)(11*3DCu AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143.)(2*5FEu,)(1*5FEu.)(11*4EDu.)(22*4EDu.)(13*4EDu5)(24Df7)(14Df第三十七页，讲稿共八十二页哦38AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143)(),(),(),(min)(242231412323DfDCdDfDCdCf .1055,74min即由即由 C2 到到F 的最短距离为的最短距离为10，相应的决策为，相应的决策为.)(22*3DCu)(),(),(

33、),(min)(343332423333DfDCdDfDCdCf .854,53min.)(2*5FEu,)(1*5FEu.)(11*4EDu.)(22*4EDu.)(13*4EDu.)(11*3DCu7)(14Df5)(24Df5)(34Df第三十八页，讲稿共八十二页哦39即由即由 C3 到到F 的最短距离为的最短距离为8，相应的决策为，相应的决策为.)(23*3DCu)(),(),(),(min)(343432424343DfDCdDfDCdCf .954,58min即由即由 C4 到到F 的最短距离为的最短距离为9，相应的决策为，相应的决策为.)(34*3DCu AB1B2C1C2C3C

34、4D1D2D3E1E2F452368775845348435623143.)(2*5FEu,)(1*5FEu.)(11*4EDu.)(22*4EDu.)(13*4EDu.)(11*3DCu.)(22*3DCu5)(24Df5)(34Df第三十九页，讲稿共八十二页哦40AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（4）k=2时，状态时，状态,212BBX)(),(),(),(),(),(min)(33312232121311212CfCBdCfCBdCfCBdBf .1386,103,122min这说明由这说明由 B1 到到F 的最短距离为的最

35、短距离为13，相应的决策为，相应的决策为.)(21*2CBu.)(2*5FEu,)(1*5FEu.)(11*4EDu.)(22*4EDu.)(13*4EDu.)(11*3DCu.)(22*3DCu.)(23*3DCu.)(34*3DCu12)(13Cf10)(23Cf8)(33Cf第四十页，讲稿共八十二页哦41)(),(),(),(),(),(min)(43422333222322222CfCBdCfCBdCfCBdBf .1597,87,108min即由即由 B2到到F 的最短距离为的最短距离为15，相应的决策为，相应的决策为.)(32*2CBu AB1B2C1C2C3C4D1D2D3E1E

36、2F452368775845348435623143.)(2*5FEu,)(1*5FEu.)(11*4EDu.)(22*4EDu.)(13*4EDu.)(11*3DCu.)(22*3DCu.)(23*3DCu.)(34*3DCu.)(21*2CBu9)(43Cf10)(23Cf8)(33Cf第四十一页，讲稿共八十二页哦42AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（5）k=1 时，只有一个状态点时，只有一个状态点A,则则)(),(),(),(min)(222112111BfBAdBfBAdAf .17155,134min即由即由 A到到F

37、的最短距离为的最短距离为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)(22Bf第四十二页，讲稿共八十二页哦43,)(21*2CBu,)(22*3DCu,)(22*4EDu.)(2*5FEu 所以最优路线为：所以最优路线为：FEDCBA2221AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143.)(2*5FEu

38、,)(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)(10111xfkxfuxdxfkkkkkukkkAB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143例例1：1阶段2阶段3阶段4阶段5阶段行走方向行走

39、方向第第k阶段阶段第四十四页，讲稿共八十二页哦45AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143K=1 时时)(),()()(10111121xfABdBfxf注意到：注意到：0)()(010Afxf所以所以ABu)(1*1)(),()()(10212121xfABdBfxf,4)(11Bf,5)(21BfABu)(2*1第四十五页，讲稿共八十二页哦46K=2 时时642)(),()()(111121232BfBCdCfxf11*2)(BCuAB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143ABu)

40、(2*1ABu)(1*1)(),(),(),(min)()(21222111222232BfBCdBfBCdCfxf758,43min12*2)(BCu)(),(),(),(min)()(21232111323232BfBCdBfBCdCfxf第四十六页，讲稿共八十二页哦4713*2)(BCu,1257)(),()()(212424232BfBCdCfxf24*2)(BCuK=3 时时)(),(),(),(min)()(22212121131343CfCDdCfCDdDfxf1174,65minAB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143AB

41、u)(2*1ABu)(1*1,1057,46min11*2)(BCu12*2)(BCu6)(12Cf7)(22Cf第四十七页，讲稿共八十二页哦48AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143ABu)(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)(32Cf第四十八页，讲稿共八十二页哦4914)(14Ef11

42、*4)(DEu14)(24Ef22*4)(DEu17)(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)(13Df第四十九页，讲稿共八十二页哦5022*3)(CDu12*2)(BCuABu)(1*1最短路径：最短路径：FEDCBA2221最短路长：最短路

43、长：17)(5 Ff注注：顺序解法与逆序解法无本质区别，一般来说，当初始状：顺序解法与逆序解法无本质区别，一般来说，当初始状态给定时用逆序解法，当终止状态给定时用顺序解法。若问态给定时用逆序解法，当终止状态给定时用顺序解法。若问题给定了一个初始状态与一个终止状态，则两种方法均可使题给定了一个初始状态与一个终止状态，则两种方法均可使用。用。2*5)(EFu 22*4)(DEu 第五十页，讲稿共八十二页哦51AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（4，F）（3，F）（5，E1）（5，E2）（7，E1）（12，D1）（10，D2）（8，D2）

44、（9，D3）（13，C2）（15，C3）（17，B1）v作业：作业：vP235 5.2（双标号法，顺序逆序选一）（双标号法，顺序逆序选一）第五十一页，讲稿共八十二页哦529.3 9.3 背背 包包 问问 题题 一般的提法为：一旅行者携带背包去登山。已知他所能承受一般的提法为：一旅行者携带背包去登山。已知他所能承受 的背包重量的极限为的背包重量的极限为a(千克千克)，现有，现有n种物品可供他选择装入种物品可供他选择装入背包。第背包。第i种物品的单位重量为种物品的单位重量为 (千克千克)，其价值（可以是表，其价值（可以是表明本物品对登山者的重要性指标）是携带数量明本物品对登山者的重要性指标）是携带

45、数量 的函数的函数 （i=1 1，2 2，n）.问旅行者应如何选择携带物品的件问旅行者应如何选择携带物品的件数，以使总价值最大？数，以使总价值最大？ia()iigxix此模型解决的是运输工具包括卫星的最优装载问题。此模型解决的是运输工具包括卫星的最优装载问题。其数学模型为：其数学模型为：第五十二页，讲稿共八十二页哦53设设 为第为第 i 种物品装入的件数，则背包问题可归结为如下种物品装入的件数，则背包问题可归结为如下 ix形式的整数规划模型：形式的整数规划模型：niiixgz1)(max),2,101nixaxainiii（整数下面从一个例子来分析动态规划建模。下面从一个例子来分析动态规划建模

46、。例例 有一辆最大货运量为有一辆最大货运量为10 t 的卡车，用以装载的卡车，用以装载3种种货物，每种货物的单位重量及相应单位价值如表货物，每种货物的单位重量及相应单位价值如表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的顺序排序，每段装

47、入一的顺序排序，每段装入一种物品，共划分种物品，共划分3个阶段，即个阶段，即k=1,2,3.第五十四页，讲稿共八十二页哦55状态变量状态变量 ：在第在第k段开始时，背包中允许装入前段开始时，背包中允许装入前k种种物品的总重量。物品的总重量。1ks决策变量决策变量 ：装入第装入第k种物品的件数。种物品的件数。kx状态转移方程：状态转移方程：kkkkxass1最优指标函数最优指标函数 ：在背包中允许装入物品的总重量不超在背包中允许装入物品的总重量不超过过 kg，采取最优策略只装前，采取最优策略只装前k种物品时的最大使用价值种物品时的最大使用价值。)(1kksf1ks货物1货物2货物3104s343

48、5xss2324xss1213xss1114)(xxg2225)(xxg3336)(xxg24x35x13x321654maxxxxz )3,2,1(,010543321ixxxxi整数整数第五十五页，讲稿共八十二页哦56由此可得动态规划的顺序递推方程为：由此可得动态规划的顺序递推方程为：0)(3,2,1)()(max)(1011011sfkxasfxgsfkkkkkksxakkkkk货物1货物2货物3104s3435xss2324xss1213xss1114)(xxg2225)(xxg3336)(xxg24x35x13xK=1 时时)()(max)(10113021121sfxgsfxsx为

49、整数4max130121xxsx为整数321654maxxxxz )3,2,1(,010543321ixxxxi整数整数第五十六页，讲稿共八十二页哦57货物1货物2货物3104s3435xss2324xss1213xss1114)(xxg2225)(xxg3336)(xxg24x35x13xK=1 时时)()(max)(10113021121sfxgsfxsx为整数4max130121xxsx为整数注意到：注意到：10,1,02s例如：例如：72s时，时，4max)7(1730111xfxx为整数4max12,1,01xx 88,4,0max2*1x其它计算结果见表其它计算结果见表5：3216

50、54maxxxxz )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 40 40 41 41 42 42 43 3000448121200011233表 5第五十八页，讲稿共八十二页哦59货物1货物2货物3104s3435xss2324xss1213xss1114)(xxg2225)(xxg3336)(xxg24x35x13xK=2 时时)()(max)(2122