《动态规划的基本原理和基本应用.ppt》由会员分享，可在线阅读，更多相关《动态规划的基本原理和基本应用.ppt（82页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、关于动态规划的基本原理和基本应用现在学习的是第1页，共82页2 现在学习的是第2页，共82页3现在学习的是第3页，共82页4现在学习的是第4页，共82页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分别投入两种生产方式分别投入两种生产
2、方式A，B后可以回收再生产，后可以回收再生产，回收率分别为回收率分别为a与与b。试求进行。试求进行n个阶段后的最大总个阶段后的最大总收入。收入。 现在学习的是第5页，共82页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-
3、1，使这，使这n个阶段的总收入最大。个阶段的总收入最大。 例例1 1现在学习的是第6页，共82页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现在学习的是第7页，共82页8例例2 2 生产和存储控制问题生产和存储控制问题 某工厂生产某种季节性商品，需
4、要作下一某工厂生产某种季节性商品，需要作下一年度的生产计划，假定这种商品的生产周期需年度的生产计划，假定这种商品的生产周期需要两个月，全年共有要两个月，全年共有6个生产周期，需要作出个生产周期，需要作出各个周期中的生产计划。各个周期中的生产计划。设已知各周期对该商品的需要量如下表所示设已知各周期对该商品的需要量如下表所示：周期周期123456需求量需求量551030508现在学习的是第8页，共82页9例例2 2 假设这个工厂根据需要可以日夜两班生产或只是日班生假设这个工厂根据需要可以日夜两班生产或只是日班生产，当开足日班时，每一个生产周期能生产商品产，当开足日班时，每一个生产周期能生产商品15
5、15个单位个单位，每生产一个单位商品的成本为，每生产一个单位商品的成本为100100元。当开足夜班时，每一元。当开足夜班时，每一生产周期能生产的商品也是生产周期能生产的商品也是1515个，但是由于增加了辅助性生产个，但是由于增加了辅助性生产设备和生产辅助费用，每生产一单位商品的成本为设备和生产辅助费用，每生产一单位商品的成本为120120元。由于元。由于生产能力的限制，可以在需求淡季多生产一些商品储存起生产能力的限制，可以在需求淡季多生产一些商品储存起来以备需求旺季使用，但存储商品是需要存储来以备需求旺季使用，但存储商品是需要存储费用的，假设费用的，假设每单位商品存储一周期需要每单位商品存储一
6、周期需要16元，已知开始时存储为零，年终也不元，已知开始时存储为零，年终也不存储商品备下年使用，问应该如何作生产和存储计划，才能使总的存储商品备下年使用，问应该如何作生产和存储计划，才能使总的生产和存储费用最小？生产和存储费用最小？现在学习的是第9页，共82页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
7、 xi 30, 0 uj , i=1,2,6 ; j=1,2, ,5 )1852345(16)(5432161xxxxxxfii3015,300120150 ,100)(iiiiixxxxxftjjiiuxf16116)(使使 S = =为最小，其中为最小，其中现在学习的是第10页，共82页11 运输网络问题：如图运输网络问题：如图1 1所示的运输网络，点间所示的运输网络，点间连线上的数字表示两地距离连线上的数字表示两地距离( (也可是运费、时间等也可是运费、时间等) )，要求从要求从v v1 1至至v v1010的最短路线。的最短路线。 这种运输网络问题也是静态决策问题。但是，按照这种运输网
8、络问题也是静态决策问题。但是，按照网络中点的分布，可以把它分为网络中点的分布，可以把它分为4 4个阶段，而作为多阶段个阶段，而作为多阶段决策问题来研究。决策问题来研究。现在学习的是第11页，共82页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 运输网络图示运输网络图示现在学习的是第12页，共82页13动态规划方法导引动态规划方法导引 为了说明动态规划的基本思想方法和特点，下面以为了说明动态规划的基本思想方法和特点，下面以图图1 1所示为例讨论求最短路问题的方法。所示为
9、例讨论求最短路问题的方法。 它的基本思想是它的基本思想是列举出所有可能发生的方案和结果，再对它们一一进行比列举出所有可能发生的方案和结果，再对它们一一进行比较，求出最优方案。这里从较，求出最优方案。这里从v v1 1到到v v1010的路程可以分为的路程可以分为4 4个阶个阶段。第一二段的走法有三种，第三段的走法有两种，第四段段。第一二段的走法有三种，第三段的走法有两种，第四段的走法仅一种，因此共有的走法仅一种，因此共有3 33 32 21 11818条可能的路线，条可能的路线，5454次加法算出各条路线的距离，最后进行次加法算出各条路线的距离，最后进行1717次两两比较，可次两两比较，可知最
10、优路线是知最优路线是v v1 1 v v2 2 v v5 5 v v8 8 v v10 10 , ,最短距离是最短距离是2727现在学习的是第13页，共82页14 显然，当组成交通网络的节点很多时，用穷举法求显然，当组成交通网络的节点很多时，用穷举法求最优路线的计算工作量将会十分庞大，而且其中包含着最优路线的计算工作量将会十分庞大，而且其中包含着许多重复计算许多重复计算 ，是说某人，是说某人从从k k出发，他并不顾及全线是否最短，只是选择当前最短途出发，他并不顾及全线是否最短，只是选择当前最短途径，径，“逢近便走逢近便走”，错误地以为局部最优会致整体最优，在，错误地以为局部最优会致整体最优，在
11、这种想法指导下，所取决策必是这种想法指导下，所取决策必是v v1 1 v v2 2 v v5 5 v v9 9 v v1010 ，全程长度是全程长度是3030；显然，这种方法的结果常是错误的；显然，这种方法的结果常是错误的现在学习的是第14页，共82页15 动态规划方法寻求该动态规划方法寻求该最短路问题的基本思想是，首先将问题划分为最短路问题的基本思想是，首先将问题划分为4 4个阶个阶段，每次的选择总是综合后继过程的一并最优进行考虑段，每次的选择总是综合后继过程的一并最优进行考虑，在各段所有可能状态的最优后继过程都已求得的情况，在各段所有可能状态的最优后继过程都已求得的情况下，全程的最优路线便
12、也随之得到。下，全程的最优路线便也随之得到。 为了找出所有可能状态的最优后继过程，动态为了找出所有可能状态的最优后继过程，动态规划方法是从过程的最后阶段开始考虑，然后逆着实规划方法是从过程的最后阶段开始考虑，然后逆着实际过程发展的顺序，逐段向前递推计算直至始点。际过程发展的顺序，逐段向前递推计算直至始点。现在学习的是第15页，共82页16具体说，此问题先从具体说，此问题先从v v1010开始，因为开始，因为v v1010是终点。再无后继过程，故可以接着考虑第是终点。再无后继过程，故可以接着考虑第4 4阶段上所有可能状态阶段上所有可能状态v v8 8 , ,v v9 9的最优后续过程因为从的最优
13、后续过程因为从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上，虽然到上，虽然到v v8 8是是6 6，到，到v v9 9是是5 5，但是，但是 v2 5 5 6 14 10
14、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页，共82页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上所有可能状态的最优后继过程都已求得后，便可以开始上所有可
15、能状态的最优后继过程都已求得后，便可以开始考虑阶段考虑阶段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）现在学习的是第17页，共82页18v v2 2v v5 5v v8 8v v10 10 ，最短距离是，最短距离是2222依此类推，最后可以得到从初始状态依此类推，最后可以得到从
16、初始状态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）现在学习的是第18页，共82页
17、19综上所述可见，全枚举法虽可找出最优方案，但不是个好算法，综上所述可见，全枚举法虽可找出最优方案，但不是个好算法，局部最优法则完全是个错误方法，只有动态规划方法属较科学有局部最优法则完全是个错误方法，只有动态规划方法属较科学有效的算法。它的基本思想是，把一个比较复杂的问题分解为一系效的算法。它的基本思想是，把一个比较复杂的问题分解为一系列同类型的更易求解的子问题，便于应用计算机。整个求解过程列同类型的更易求解的子问题，便于应用计算机。整个求解过程分为两个阶段，先按整体最优的思想逆序地求出各个子问题中所分为两个阶段，先按整体最优的思想逆序地求出各个子问题中所有可能状态的最优决策与最优路线值，然
18、后再顺序地求出整个问有可能状态的最优决策与最优路线值，然后再顺序地求出整个问题的最优策略和最优路线。计算过程中，系统地删去了所有中间题的最优策略和最优路线。计算过程中，系统地删去了所有中间非最优的方案组合，从而使计算工作量比穷举法大为减少。非最优的方案组合，从而使计算工作量比穷举法大为减少。现在学习的是第19页，共82页20拾火柴游戏拾火柴游戏: 桌子上放桌子上放30根火柴根火柴, 每人一次可每人一次可拾起拾起13根根, 谁拾起最后一根火柴谁输谁拾起最后一根火柴谁输, 如果你如果你先选择先选择, 如何保证你能赢得游戏？如何保证你能赢得游戏？2925211713951现在学习的是第20页，共82
19、页21动态规划是解决动态规划是解决多阶段决策问题多阶段决策问题的一种方法。所谓多阶段的一种方法。所谓多阶段决策问题是指这样的决策问题：其过程可分为若干个相互联决策问题是指这样的决策问题：其过程可分为若干个相互联系的阶段，每一阶段都对应着一组可供选择的决策，每一决系的阶段，每一阶段都对应着一组可供选择的决策，每一决策的选定即依赖于当前面临的状态，又影响以后总体的效果。策的选定即依赖于当前面临的状态，又影响以后总体的效果。ABCDE状态A状态B状态C状态D状态E状态F决策A决策D决策E当每一阶段的决策选定以后，就构成一个决策序列，称为一个当每一阶段的决策选定以后，就构成一个决策序列，称为一个决策B
20、决策C策略策略，它对应着一个确定的效果。它对应着一个确定的效果。多阶段决策问题就是寻找使多阶段决策问题就是寻找使此效果最好的策略。此效果最好的策略。现在学习的是第21页，共82页22动态规划问题实例动态规划问题实例例例 给定一个线路网络，给定一个线路网络，AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143要从要从A向向F铺设一条输油管道，铺设一条输油管道，各点间连线上的数字表示距离，问应选择什么路线，可使总各点间连线上的数字表示距离，问应选择什么路线，可使总距离最短？距离最短？现在学习的是第22页，共82页239.2 动态规划的基本概念和基本原理动
21、态规划的基本概念和基本原理一、基本概念一、基本概念阶段阶段：是指问题需要做出决策的步数。阶段总数常记为：是指问题需要做出决策的步数。阶段总数常记为n，相，相应的是应的是n个阶段的决策问题。阶段的序号常记为个阶段的决策问题。阶段的序号常记为k，称为，称为阶段阶段变量变量，k=1,2, ,n. k即可以是顺序编号也可以是逆序编号，即可以是顺序编号也可以是逆序编号，常用顺序编号。常用顺序编号。全过程全过程；后部子过程后部子过程。状态状态：各阶段开始时的客观条件，第：各阶段开始时的客观条件，第k阶段的状态常用阶段的状态常用状态状态变量变量 表示，状态变量取值的集合称为表示，状态变量取值的集合称为状态集
22、合状态集合，用，用表示。表示。kxkX例如，例中，例如，例中，.,2121BBXAX 现在学习的是第23页，共82页24AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第1阶段第2阶段第3阶段第4阶段第5阶段状态1状态2状态3状态4状态5状态6.,2121BBXAX 现在学习的是第24页，共82页25决策决策：是指从某阶段的某个状态出发，在若干个不同方案中：是指从某阶段的某个状态出发，在若干个不同方案中做出的选择。表示决策的变量，称为做出的选择。表示决策的变量，称为决策变量决策变量，用，用 表示表示)(kkxu例如：例如： 表示走到表示走到3阶段
23、阶段,当处于当处于C2 路口时，下一路口时，下一步奔步奔D1.123)(DCu 时的允许决策集合记为时的允许决策集合记为 ，例如：，例如：策略策略:全过程策略全过程策略 p1n；子策略；子策略pkn；最优策略最优策略。kx)(kkxU,)(32112CCCBU 状态转移方程状态转移方程：是从上一阶段的某一状态值转变为下一阶段：是从上一阶段的某一状态值转变为下一阶段某一状态值的转移规律，用某一状态值的转移规律，用 ),(1kkkkuxTx 表示。表示。决策变量允许的取值范围称为决策变量允许的取值范围称为允许决策集合允许决策集合，第，第k阶段状态为阶段状态为 现在学习的是第25页，共82页26AB
24、1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第1阶段第2阶段第3阶段第4阶段第5阶段状态1状态2状态3状态4状态5状态6123)(DCu ,)(32112CCCBU 现在学习的是第26页，共82页27指标函数指标函数：分：分阶段指标函数阶段指标函数和和过程指标函数过程指标函数。阶段指标函数阶段指标函数是指第是指第k阶段从状态阶段从状态 出发，采取决策出发，采取决策 时的效益，用时的效益，用kxku),(kkkuxv表示。而表示。而过程指标函数过程指标函数指从第指从第k阶段的某状态出发，阶段的某状态出发，采取子策略采取子策略,1nkkknuuup
25、时所得到的阶段效益之和：时所得到的阶段效益之和： nkjjjjknkknuxvpxV),(),(最优指标函数最优指标函数：表示从第：表示从第k阶段状态为阶段状态为 时采用最佳策略时采用最佳策略kx*knp到过程终止时的最佳效益。记为到过程终止时的最佳效益。记为),(),()()(*knkknxUpknkknkkpxVoptpxVxfkknkn 现在学习的是第27页，共82页28AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第1阶段第2阶段第3阶段第4阶段第5阶段状态1状态2状态3状态4状态5状态6212(,)3vB C 35211(,)11vC
26、D E F 现在学习的是第28页，共82页29其中其中 opt 可根据具体情况取可根据具体情况取max 或或min。基本方程基本方程：此为逐段递推求和的依据，一般为：此为逐段递推求和的依据，一般为： 0)(1 , 1,)(),()(1111)(nnkkkkksUukkxfnnkxfuxvoptxfkkk式中式中opt 可根据题意取可根据题意取 max 或或 min.例如，例的基本方程为：例如，例的基本方程为： 0)(1 , 2 , 3 , 4 , 5)(),(min)(6611xfkxfuxdxfkkkkkukkk现在学习的是第29页，共82页30v即确定各个变量及方程函数即确定各个变量及方程
27、函数v1 1、阶段变量、阶段变量v2 2、状态变量：选择时要满足两个条件：、状态变量：选择时要满足两个条件：v能正确描述受控过程的演变特性能正确描述受控过程的演变特性v要满足无后效性要满足无后效性v无后效性无后效性：给定了某阶段状态，在这阶段以后过程的发：给定了某阶段状态，在这阶段以后过程的发展不受这阶段以前各阶段状态的影响。展不受这阶段以前各阶段状态的影响。v3 3、决策变量、决策变量v4 4、列出状态转移方程、列出状态转移方程v5 5、指标函数、指标函数现在学习的是第30页，共82页31三、三、最优化原理最优化原理：最优策略的任一后部子策略都是最优的。：最优策略的任一后部子策略都是最优的。
28、无论以前状态决策如何，从眼下直到最后的诸决策必构成最优子策略无论以前状态决策如何，从眼下直到最后的诸决策必构成最优子策略。动态规划应用举例动态规划应用举例例例1 最短路线问题最短路线问题AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143现在学习的是第31页，共82页32逆序递推方程：逆序递推方程： 0)(1 , 2 , 3 , 4 , 5)(),(min)(6611xfkxfuxdxfkkkkkukkk（1）k=5 时，状态时，状态,215EEX 它们到它们到F 点的距离即为点的距离即为最短路。最短路。,4)(15 Ef;3)(25 Ef,)(1*
29、5FEu .)(2*5FEu AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143现在学习的是第32页，共82页33AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（2）k=4 时，状态时，状态,3214DDDX 它们到它们到F 点需经过中途点需经过中途点点E，需一一分析从，需一一分析从E 到到 F的最短路：先说从的最短路：先说从D1到到F 的最短路的最短路有两种选择：经过有两种选择：经过 E1, E2, 比较最短。比较最短。.)(2*5FEu,)(1*5FEu现在学习的是第33页，共82页34AB1B
30、2C1C2C3C4D1D2D3E1E2F452368775845348435623143)(),(),(),(min)(252141511414EfEDdEfEDdDf . 735 , 43min这说明由这说明由 D1 到到F 的最短距离为的最短距离为7，其路径为，其路径为.11FED相应的决策为：相应的决策为：.)(11*4EDu .)(2*5FEu,)(1*5FEu现在学习的是第34页，共82页35)(),(),(),(min)(252241512424EfEDdEfEDdDf . 532 , 46min 这说明由这说明由 D2 到到F 的最短距离为的最短距离为5，其路径为，其路径为.22
31、FED相应的决策为：相应的决策为：.)(22*4EDu AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143.)(2*5FEu,)(1*5FEu.)(11*4EDu现在学习的是第35页，共82页36AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143)(),(),(),(min)(252341513434EfEDdEfEDdDf . 533, 41min即即 D3 到到F 的最短距离为的最短距离为5，其路径为，其路径为31.DEF相应的决策为：相应的决策为：.)(13*4EDu .)(2*5FEu,)(1*
32、5FEu.)(11*4EDu.)(22*4EDu现在学习的是第36页，共82页37（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)(14Df现在学习的是第37页，共82
33、页38AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143)(),(),(),(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)(34Df现在学习的是第38页，
34、共82页39即由即由 C3 到到F 的最短距离为的最短距离为8，相应的决策为，相应的决策为.)(23*3DCu )(),(),(),(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)(34Df现在学习的是第39页
35、，共82页40AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（4）k=2时，状态时，状态,212BBX )(),(),(),(),(),(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)(1
36、3Cf10)(23Cf8)(33Cf现在学习的是第40页，共82页41)(),(),(),(),(),(min)(43422333222322222CfCBdCfCBdCfCBdBf .1597 , 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.)(2
37、1*2CBu9)(43Cf10)(23Cf8)(33Cf现在学习的是第41页，共82页42AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（5）k=1 时，只有一个状态点时，只有一个状态点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*3DC
38、u.)(34*3DCu.)(32*2CBu.)(21*2CBu13)(12Bf15)(22Bf现在学习的是第42页，共82页43,)(21*2CBu ,)(22*3DCu ,)(22*4EDu .)(2*5FEu 所以最优路线为：所以最优路线为：FEDCBA2221AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143.)(2*5FEu,)(1*5FEu.)(11*4EDu.)(22*4EDu.)(13*4EDu.)(11*3DCu.)(22*3DCu.)(23*3DCu.)(34*3DCu.)(32*2CBu.)(21*2CBu再按计算顺序反推可得最
39、优决策序列：再按计算顺序反推可得最优决策序列：,)(1*1BAu 现在学习的是第43页，共82页44顺序递推方程：顺序递推方程： 初初始始条条件件0)(5 , 4 , 3 , 2 , 1)(),(min)(10111xfkxfuxdxfkkkkkukkkAB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143例例1：1阶段2阶段3阶段4阶段5阶段行走方向行走方向第第k阶段阶段现在学习的是第44页，共82页45AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143K=1 时时)(),()()(10111121xfA
40、BdBfxf注意到：注意到：0)()(010Afxf所以所以ABu)(1*1)(),()()(10212121xfABdBfxf, 4)(11Bf, 5)(21BfABu)(2*1现在学习的是第45页，共82页46K=2 时时642)(),()()(111121232BfBCdCfxf11*2)(BCuAB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143ABu)(2*1ABu)(1*1)(),(),(),(min)()(21222111222232BfBCdBfBCdCfxf758 , 43min12*2)(BCu)(),(),(),(min)()(
41、21232111323232BfBCdBfBCdCfxf现在学习的是第46页，共82页4713*2)(BCu,1257)(),()()(212424232BfBCdCfxf24*2)(BCuK=3 时时)(),(),(),(min)()(22212121131343CfCDdCfCDdDfxf1174 , 65minAB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143ABu)(2*1ABu)(1*1,1057 , 46min11*2)(BCu12*2)(BCu6)(12Cf7)(22Cf现在学习的是第47页，共82页48AB1B2C1C2C3C4D1
42、D2D3E1E2F452368775845348435623143ABu)(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现在学习的是第48页，共82页4914)(14Ef11*4)(DEu14)(24Ef22*4)(DEu17)(5Ff2*5)(EFu最优策略：最优策略：2*5)(EFu 22*4)(DEu AB1B2C1C2C3C4D1D2D3
43、E1E2F452368775845348435623143ABu)(2*1ABu)(1*111*2)(BCu12*2)(BCu13*2)(BCu24*2)(BCu,)(11*3CDu或21*3)(CDu22*3)(CDu33*3)(CDu12)(23Df14)(33Df11)(13Df现在学习的是第49页，共82页5022*3)(CDu12*2)(BCuABu)(1*1最短路径：最短路径：FEDCBA2221最短路长：最短路长：17)(5 Ff注注：顺序解法与逆序解法无本质区别，一般来说，当初始状：顺序解法与逆序解法无本质区别，一般来说，当初始状态给定时用逆序解法，当终止状态给定时用顺序解法。
44、若问态给定时用逆序解法，当终止状态给定时用顺序解法。若问题给定了一个初始状态与一个终止状态，则两种方法均可使题给定了一个初始状态与一个终止状态，则两种方法均可使用。用。2*5)(EFu 22*4)(DEu 现在学习的是第50页，共82页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（双标号法，顺序逆序选一）（双标号法，顺序逆序选一）现在学习的是第51页，
45、共82页529.3 9.3 背背 包包 问问 题题 一般的提法为：一旅行者携带背包去登山。已知他所能承受一般的提法为：一旅行者携带背包去登山。已知他所能承受 的背包重量的极限为的背包重量的极限为a (千克千克)，现有，现有n种物品可供他选择装入种物品可供他选择装入背包。第背包。第i种物品的单位重量为种物品的单位重量为 (千克千克)，其价值（可以是表，其价值（可以是表明本物品对登山者的重要性指标）是携带数量明本物品对登山者的重要性指标）是携带数量 的函数的函数 （i=1 1，2 2，n）.问旅行者应如何选择携带物品的件问旅行者应如何选择携带物品的件数，以使总价值最大？数，以使总价值最大？ia()
46、iigxix此模型解决的是运输工具包括卫星的最优装载问题。此模型解决的是运输工具包括卫星的最优装载问题。其数学模型为：其数学模型为：现在学习的是第52页，共82页53设设 为第为第 i 种物品装入的件数，则背包问题可归结为如下种物品装入的件数，则背包问题可归结为如下 ix形式的整数规划模型：形式的整数规划模型：niiixgz1)(max), 2 , 101nixaxainiii（整数下面从一个例子来分析动态规划建模。下面从一个例子来分析动态规划建模。例例 有一辆最大货运量为有一辆最大货运量为10 t 的卡车，用以装载的卡车，用以装载3种种货物，每种货物的单位重量及相应单位价值如表货物，每种货物
47、的单位重量及相应单位价值如表4 所示。所示。应如何装载可使总价值最大？应如何装载可使总价值最大？现在学习的是第53页，共82页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.现在学习的是第54页，共82页
48、55状态变量状态变量 ：在第在第k段开始时，背包中允许装入前段开始时，背包中允许装入前k种种物品的总重量。物品的总重量。1ks决策变量决策变量 ：装入第装入第k种物品的件数。种物品的件数。kx状态转移方程：状态转移方程：kkkkxass1最优指标函数最优指标函数 ：在背包中允许装入物品的总重量不超在背包中允许装入物品的总重量不超过过 kg，采取最优策略只装前，采取最优策略只装前k种物品时的最大使用价值种物品时的最大使用价值。)(1kksf1ks货物1货物2货物3104s3435xss2324xss1213xss1114)(xxg2225)(xxg3336)(xxg24x35x13x321654
49、maxxxxz )3 , 2 , 1(, 010543321ixxxxi整数整数现在学习的是第55页，共82页56由此可得动态规划的顺序递推方程为：由此可得动态规划的顺序递推方程为：0)(3 , 2 , 1)()(max)(1011011sfkxasfxgsfkkkkkksxakkkkk货物1货物2货物3104s3435xss2324xss1213xss1114)(xxg2225)(xxg3336)(xxg24x35x13xK=1 时时)()(max)(10113021121sfxgsfxsx为整数4max130121xxsx为整数321654maxxxxz )3 , 2 , 1(, 0105
50、43321ixxxxi整数整数现在学习的是第56页，共82页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：321654maxxxxz )3 , 2 , 1(, 010543321ix