动态规划的基本原理和基本应用精选PPT.ppt

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

1、关于动态规划的基本原理和基本应用第1页，讲稿共82张，创作于星期日2 动动态态规规划划是是解解决决多多阶阶段段决决策策过过程程最最优优化化问问题题的的一一种种方方法法。由由美美国国数数学学家家贝贝尔尔曼曼（Bellman）等等人人在在20世世纪纪50年年代代提提出出。他他们们针针对对多多阶阶段段决决策策问问题题的的特特点点，提提出出了了解解决决这这类类问问题题的的“最最优优化化原原理理”，并并成成功功地地解解决决了了生生产产管管理理、工工程程技技术术等等方方面的许多实际问题。面的许多实际问题。第2页，讲稿共82张，创作于星期日3 动动态态规规划划是是现现代代企企业业管管理理中中的的一一种种重重

2、要要决决策策方方法法，可可用用于于最最优优路路径径问问题题、资资源源分分配配问问题题、生生产产计计划划和和库库存存问问题题、投投资资问问题题、装装载载问问题题、排排序序问问题题及及生生产产过过程程的的最最优控制等。优控制等。第3页，讲稿共82张，创作于星期日4 9.1多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例多阶段决策过程最优化多阶段决策过程最优化 多阶段决策过程是指这样一类特殊的活动过程，多阶段决策过程是指这样一类特殊的活动过程，他们可以按时间顺序分解成若干相互联系的阶段，在他们可以按时间顺序分解成若干相互联系的阶段，在每个阶段都要做出决策，全部过程的决策是一个决策每个阶段都要

3、做出决策，全部过程的决策是一个决策序列，所以多阶段决策问题也称为序贯决策问题。序列，所以多阶段决策问题也称为序贯决策问题。第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分分别别投投入入两两种种生生产产方方式式A，B

4、后后可可以以回回收收再再生生产产，回回收收率率分分别别为为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-1，使这，使

5、这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 生产和存储控制问题生产和存储控制问题 某工厂生产某种季节性商品，需

6、要作下一某工厂生产某种季节性商品，需要作下一年度的生产计划，假定这种商品的生产周期需年度的生产计划，假定这种商品的生产周期需要两个月，全年共有要两个月，全年共有6个生产周期，需要作出个生产周期，需要作出各个周期中的生产计划。各个周期中的生产计划。设已知各周期对该商品的需要量如下表所示设已知各周期对该商品的需要量如下表所示：周期周期123456需求量需求量551030508第8页，讲稿共82张，创作于星期日9例例2 2 假设这个工厂根据需要可以日夜两班生产或只是日班生假设这个工厂根据需要可以日夜两班生产或只是日班生产，当开足日班时，每一个生产周期能生产商品产，当开足日班时，每一个生产周期能生产商

7、品1515个单位，个单位，每生产一个单位商品的成本为每生产一个单位商品的成本为100100元。当开足夜班时，每一元。当开足夜班时，每一生产周期能生产的商品也是生产周期能生产的商品也是1515个，但是由于增加了辅助性生产个，但是由于增加了辅助性生产设备和生产辅助费用，每生产一单位商品的成本为设备和生产辅助费用，每生产一单位商品的成本为120120元。由于生元。由于生产能力的限制，可以在需求淡季多生产一些商品储存起来以备产能力的限制，可以在需求淡季多生产一些商品储存起来以备需求旺季使用，但存储商品是需要存储需求旺季使用，但存储商品是需要存储费用的，假设每单位商费用的，假设每单位商品存储一周期需要品

8、存储一周期需要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+u

9、5=8 0 xi 30,0 uj,i=1,2,6;j=1,2,5 使使 S=为最小，其中为最小，其中第10页，讲稿共82张，创作于星期日11 例例例例3 3 3 3 运运输输网网络络问问题题：如如图图1 1所所示示的的运运输输网网络络，点点间间连连线线上上的的数数字字表表示示两两地地距距离离(也也可可是是运运费费、时时间间等等)，要求从要求从v v1 1至至v v1010的最短路线。的最短路线。这这种种运运输输网网络络问问题题也也是是静静态态决决策策问问题题。但但是是，按按照照网网络络中中点点的的分分布布，可可以以把把它它分分为为4 4个个阶阶段段，而而作作为多阶段决策问题来研究。为多阶段决策

10、问题来研究。第11页，讲稿共82张，创作于星期日121234图图1 1 运输网络图示运输网络图示第12页，讲稿共82张，创作于星期日13动态规划方法导引动态规划方法导引 为了说明动态规划的基本思想方法和特点，下面以为了说明动态规划的基本思想方法和特点，下面以图图1 1所示为例讨论求最短路问题的方法。所示为例讨论求最短路问题的方法。第第第第一一一一种种种种方方方方法法法法称称称称做做做做全全全全枚枚枚枚举举举举法法法法或或或或穷穷穷穷举举举举法法法法，它它的的基基本本思思想想是是列列举举出出所所有有可可能能发发生生的的方方案案和和结结果果，再再对对它它们们一一一一进进行行比比较较，求求出出最最优

11、优方方案案。这这里里从从v v1 1到到v v1010的的路路程程可可以以分分为为4 4个个阶阶段段。第第一一二二段段的的走走法法有有三三种种，第第三三段段的的走走法法有有两两种种，第第四四段段的的走走法法仅仅一一种种，因因此此共共有有332133211818条条可可能能的的路路线线，5454次次加加法法算算出出各各条条路路线线的的距距离离，最最后后进进行行1717次次两两两两比比较较，可可知最优路线是知最优路线是v v1 1 v v2 2 v v5 5 v v8 8 v v10 10,最短距离是最短距离是2727第13页，讲稿共82张，创作于星期日14 显显然然，当当组组成成交交通通网网络络

12、的的节节点点很很多多时时，用用穷穷举举法法求求最最优优路路线线的的计计算算工工作作量量将将会会十十分分庞庞大大，而而且且其其中中包包含含着着许许多重复计算多重复计算 第第第第二二二二种种种种方方方方法法法法即即即即所所所所谓谓谓谓“局局局局部部部部最最最最优优优优路路路路径径径径”法法，是是说说某某人人从从k k出出发发，他他并并不不顾顾及及全全线线是是否否最最短短，只只是是选选择择当当前前最最短短途途径径，“逢逢近近便便走走”，错错误误地地以以为为局局部部最最优优会会致致整整体体最最优优，在在这这种种想想法法指指导导下下，所所取取决决策策必必是是v v1 1 v v2 2 v v5 5 v

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

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

15、是唯唯一一的的，所所以以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，但是，但是1234（10）（14）第16页，讲稿共82张，创作于星期日17综综合合考考虑虑后后继继过过程程整整体体最最优优，取取最最优优决决策策是是

16、到到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的的最最优优决决策策是到是到v v5 5,最优路线是最优路线是1234（10）（14）（16）（15）（17

17、）第17页，讲稿共82张，创作于星期日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，全程的最短距离是，全程的最短距离是2727。图。图1 1中红线表示最中红线表示最优路线，每点上圆括号内的数字表示该点到终点的最短路距离。优路线，每点上圆括号内的数字表示该点到终点的最短路距离。1234（10）（14）（16）（15）（17）（22）（22）（21）（27）

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

19、态的最优决策与最优路线值，然后再顺序地问题中所有可能状态的最优决策与最优路线值，然后再顺序地求出整个问题的最优策略和最优路线。计算过程中，系统地删求出整个问题的最优策略和最优路线。计算过程中，系统地删去了所有中间非最优的方案组合，从而使计算工作量比穷举法去了所有中间非最优的方案组合，从而使计算工作量比穷举法大为减少。大为减少。第19页，讲稿共82张，创作于星期日20拾火柴游戏拾火柴游戏:桌子上放桌子上放30根火柴根火柴,每人一次可每人一次可拾起拾起13根根,谁拾起最后一根火柴谁输谁拾起最后一根火柴谁输,如果你如果你先选择先选择,如何保证你能赢得游戏？如何保证你能赢得游戏？29252117139

20、51动态规划与倒推求解动态规划与倒推求解:第20页，讲稿共82张，创作于星期日21动态规划是解决动态规划是解决多阶段决策问题多阶段决策问题的一种方法。所谓多阶段的一种方法。所谓多阶段决策问题是指这样的决策问题：其过程可分为若干个相互联决策问题是指这样的决策问题：其过程可分为若干个相互联系的阶段，每一阶段都对应着一组可供选择的决策，每一决系的阶段，每一阶段都对应着一组可供选择的决策，每一决策的选定即依赖于当前面临的状态，又影响以后总体的效果。策的选定即依赖于当前面临的状态，又影响以后总体的效果。ABCDE状态A状态B状态C状态D状态E状态F决策A决策D决策E当每一阶段的决策选定以后，就构成一个决

21、策序列，称为一个当每一阶段的决策选定以后，就构成一个决策序列，称为一个决策B决策C策略策略，它对应着一个确定的效果。它对应着一个确定的效果。多阶段决策问题就是寻找使多阶段决策问题就是寻找使此效果最好的策略。此效果最好的策略。第21页，讲稿共82张，创作于星期日22动态规划问题实例动态规划问题实例例例 给定一个线路网络，给定一个线路网络，AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143要从要从A向向F铺设一条输油管道，铺设一条输油管道，各点间连线上的数字表示距离，问应选择什么路线，可使总各点间连线上的数字表示距离，问应选择什么路线，可使总距离最短？

22、距离最短？第22页，讲稿共82张，创作于星期日239.2 动态规划的基本概念和基本原理动态规划的基本概念和基本原理一、基本概念一、基本概念阶段阶段：是指问题需要做出决策的步数。阶段总数常记为：是指问题需要做出决策的步数。阶段总数常记为n，相，相应的是应的是n个阶段的决策问题。阶段的序号常记为个阶段的决策问题。阶段的序号常记为k，称为，称为阶段阶段变量变量，k=1,2,n.k即可以是顺序编号也可以是逆序编号，即可以是顺序编号也可以是逆序编号，常用顺序编号。常用顺序编号。全过程全过程；后部子过程后部子过程。状态状态：各阶段开始时的客观条件，第：各阶段开始时的客观条件，第k阶段的状态常用阶段的状态常

23、用状态状态变量变量 表示，状态变量取值的集合称为表示，状态变量取值的集合称为状态集合状态集合，用，用表示。表示。例如，例中，例如，例中，第23页，讲稿共82张，创作于星期日24AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第1阶段第2阶段第3阶段第4阶段第5阶段状态1状态2状态3状态4状态5状态6第24页，讲稿共82张，创作于星期日25决策决策：是指从某阶段的某个状态出发，在若干个不同方案中：是指从某阶段的某个状态出发，在若干个不同方案中做出的选择。表示决策的变量，称为做出的选择。表示决策的变量，称为决策变量决策变量，用，用 表示表示例如：例如

24、：表示走到表示走到3阶段阶段,当处于当处于C2 路口时，路口时，下一下一步奔步奔D1.时的允许决策集合记为时的允许决策集合记为 ，例如：，例如：策略策略:全过程策略全过程策略 p1n；子策略；子策略pkn；最优策略最优策略。状态转移方程状态转移方程：是从上一阶段的某一状态值转变为下一阶段：是从上一阶段的某一状态值转变为下一阶段某一状态值的转移规律，用某一状态值的转移规律，用 表示。表示。决策变量允许的取值范围称为决策变量允许的取值范围称为允许决策集合允许决策集合，第，第k阶段状态为阶段状态为 第25页，讲稿共82张，创作于星期日26AB1B2C1C2C3C4D1D2D3E1E2F4523687

25、75845348435623143第1阶段第2阶段第3阶段第4阶段第5阶段状态1状态2状态3状态4状态5状态6第26页，讲稿共82张，创作于星期日27指标函数指标函数：分：分阶段指标函数阶段指标函数和和过程指标函数过程指标函数。阶段指标函数阶段指标函数是指第是指第k阶段从状态阶段从状态 出发，采取决策出发，采取决策 时的效益，用时的效益，用表示。而表示。而过程指标函数过程指标函数指从第指从第k阶段的某状态出发，阶段的某状态出发，采取子策略采取子策略时所得到的阶段效益之和：时所得到的阶段效益之和：最优指标函数最优指标函数：表示从第：表示从第k阶段状态为阶段状态为 时采用最佳策略时采用最佳策略到过

26、程终止时的最佳效益。记为到过程终止时的最佳效益。记为第27页，讲稿共82张，创作于星期日28AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第1阶段第2阶段第3阶段第4阶段第5阶段状态1状态2状态3状态4状态5状态6第28页，讲稿共82张，创作于星期日29其中其中 opt 可根据具体情况取可根据具体情况取max 或或min。基本方程基本方程：此为逐段递推求和的依据，一般为：此为逐段递推求和的依据，一般为：式中式中opt 可根据题意取可根据题意取 max 或或 min.例如，例的基本方程为：例如，例的基本方程为：第29页，讲稿共82张，创作于星期日

27、30v即确定各个变量及方程函数即确定各个变量及方程函数v1 1、阶段变量、阶段变量v2 2、状态变量：选择时要满足两个条件：、状态变量：选择时要满足两个条件：v能正确描述受控过程的演变特性能正确描述受控过程的演变特性v要满足无后效性要满足无后效性v无后效性无后效性：给定了某阶段状态，在这阶段以后过程的发：给定了某阶段状态，在这阶段以后过程的发展不受这阶段以前各阶段状态的影响。展不受这阶段以前各阶段状态的影响。v3 3、决策变量、决策变量v4 4、列出状态转移方程、列出状态转移方程v5 5、指标函数、指标函数二、模型的构成（因素）二、模型的构成（因素）第30页，讲稿共82张，创作于星期日31三、

28、三、最优化原理最优化原理：最优策略的任一后部子策略都是最优的。：最优策略的任一后部子策略都是最优的。无论以前状态决策如何，从眼下直到最后的诸决策必构成最优子策略。无论以前状态决策如何，从眼下直到最后的诸决策必构成最优子策略。动态规划应用举例动态规划应用举例例例1 最短路线问题最短路线问题AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第31页，讲稿共82张，创作于星期日32逆序递推方程：逆序递推方程：（1）k=5 时，状态时，状态它们到它们到F 点的距离即为点的距离即为最短路。最短路。AB1B2C1C2C3C4D1D2D3E1E2F4523687

29、75845348435623143第32页，讲稿共82张，创作于星期日33AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（2）k=4 时，状态时，状态它们到它们到F 点需经过中途点需经过中途点点E，需一一分析从，需一一分析从E 到到 F的最短路：先说从的最短路：先说从D1到到F 的最短路的最短路有两种选择：经过有两种选择：经过 E1,E2,比较最短。比较最短。第33页，讲稿共82张，创作于星期日34AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143这说明由这说明由 D1 到到F 的最短距离为的最短距

30、离为7，其路径为，其路径为相应的决策为：相应的决策为：第34页，讲稿共82张，创作于星期日35这说明由这说明由 D2 到到F 的最短距离为的最短距离为5，其路径为，其路径为相应的决策为：相应的决策为：AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第35页，讲稿共82张，创作于星期日36AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143即即 D3 到到F 的最短距离为的最短距离为5，其路径为，其路径为相应的决策为：相应的决策为：第36页，讲稿共82张，创作于星期日37（3）k=3 时，状态时，状态这说

31、明由这说明由 C1 到到F 的最短距离为的最短距离为12，相应的决策为，相应的决策为AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第37页，讲稿共82张，创作于星期日38AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143即由即由 C2 到到F 的最短距离为的最短距离为10，相应的决策为，相应的决策为第38页，讲稿共82张，创作于星期日39即由即由 C3 到到F 的最短距离为的最短距离为8，相应的决策为，相应的决策为即由即由 C4 到到F 的最短距离为的最短距离为9，相应的决策为，相应的决策为AB1B

32、2C1C2C3C4D1D2D3E1E2F452368775845348435623143第39页，讲稿共82张，创作于星期日40AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（4）k=2时，状态时，状态这说明由这说明由 B1 到到F 的最短距离为的最短距离为13，相应的决策为，相应的决策为第40页，讲稿共82张，创作于星期日41即由即由 B2到到F 的最短距离为的最短距离为15，相应的决策为，相应的决策为AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第41页，讲稿共82张，创作于星期日42AB1

33、B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（5）k=1 时，只有一个状态点时，只有一个状态点A,则则即由即由 A到到F 的最短距离为的最短距离为17，相应的决策为，相应的决策为第42页，讲稿共82张，创作于星期日43所以最优路线为：所以最优路线为：AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143再按计算顺序反推可得最优决策序列：再按计算顺序反推可得最优决策序列：第43页，讲稿共82张，创作于星期日44顺序递推方程：顺序递推方程：AB1B2C1C2C3C4D1D2D3E1E2F452368775845

34、348435623143例例1：1阶段2阶段3阶段4阶段5阶段行走方向行走方向第第k阶段阶段第44页，讲稿共82张，创作于星期日45AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143K=1 时时注意到：注意到：所以所以第45页，讲稿共82张，创作于星期日46K=2 时时AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第46页，讲稿共82张，创作于星期日47K=3 时时AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第47页，讲稿共82张，创作于星期日48

35、AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143或或类似地，可算出：类似地，可算出：第48页，讲稿共82张，创作于星期日49最优策略：最优策略：AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143或第49页，讲稿共82张，创作于星期日50最短路径：最短路径：最短路长：最短路长：注注：顺序解法与逆序解法无本质区别，一般来说，当初始状：顺序解法与逆序解法无本质区别，一般来说，当初始状态给定时用逆序解法，当终止状态给定时用顺序解法。若问态给定时用逆序解法，当终止状态给定时用顺序解法。若问题给定了一个初始状态与

36、一个终止状态，则两种方法均可使题给定了一个初始状态与一个终止状态，则两种方法均可使用。用。第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页，讲稿共82张，创作于星期日529.3 9.3 背背 包包 问问 题题 一般的提法为：一旅行者携带背包去登山。已知他所能承受一般的提

37、法为：一旅行者携带背包去登山。已知他所能承受 的背包重量的极限为的背包重量的极限为a(千克千克)，现有，现有n种物品可供他选择装入种物品可供他选择装入背包。第背包。第i种物品的单位重量为种物品的单位重量为 (千克千克)，其价值（可以是表，其价值（可以是表明本物品对登山者的重要性指标）是携带数量明本物品对登山者的重要性指标）是携带数量 的函数的函数 （i=1 1，2 2，n）.问旅行者应如何选择携带物品的件问旅行者应如何选择携带物品的件数，以使总价值最大？数，以使总价值最大？此模型解决的是运输工具包括卫星的最优装载问题。此模型解决的是运输工具包括卫星的最优装载问题。其数学模型为：其数学模型为：第

38、52页，讲稿共82张，创作于星期日53设设 为第为第 i 种物品装入的件数，则背包问题可归结为如种物品装入的件数，则背包问题可归结为如下下 形式的整数规划模型：形式的整数规划模型：下面从一个例子来分析动态规划建模。下面从一个例子来分析动态规划建模。例例 有一辆最大货运量为有一辆最大货运量为10 t 的卡车，用以装载的卡车，用以装载3种种货物，每种货物的单位重量及相应单位价值如表货物，每种货物的单位重量及相应单位价值如表4 所示。所示。应如何装载可使总价值最大？应如何装载可使总价值最大？第53页，讲稿共82张，创作于星期日54货物编号i 1 2 3单位重量（t）3 4 5单位价值 ci 4 5

39、6表 4 设第设第 种货物装载的件数为种货物装载的件数为 则问题可表为：则问题可表为：阶段阶段k:将可装入物品按将可装入物品按1，2，3的顺序排序，每段装入一的顺序排序，每段装入一种物品，共划分种物品，共划分3个阶段，即个阶段，即k=1,2,3.第54页，讲稿共82张，创作于星期日55状态变量状态变量 ：在第在第k段开始时，背包中允许装入前段开始时，背包中允许装入前k种种物品的总重量。物品的总重量。决策变量决策变量 ：装入第装入第k种物品的件数。种物品的件数。状态转移方程：状态转移方程：最优指标函数最优指标函数 ：在背包中允许装入物品的总重量不超在背包中允许装入物品的总重量不超过过 kg，采取

40、最优策略只装前，采取最优策略只装前k种物品时的最大使用价值种物品时的最大使用价值。货物1货物2货物3第55页，讲稿共82张，创作于星期日56由此可得动态规划的顺序递推方程为：由此可得动态规划的顺序递推方程为：货物1货物2货物3K=1 时时第56页，讲稿共82张，创作于星期日57货物1货物2货物3K=1 时时注意到：注意到：例如：例如：时，时，其它计算结果见表其它计算结果见表5：第57页，讲稿共82张，创作于星期日580 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 41 42 42 43 3000448121200011233表 5第58页，讲稿共82张，创作于星期日59货物1货物2货物3K=2 时时其中其中例如：例如：时时，第59页，讲稿共82张，创作于星期日600 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表 5第60页，讲稿共82张，创作于星期日61其它计算结果见表其它计算结果见表6：0 1 2 0 1 2 3 4 5 6 7 8 9 105 50 00

42、 0 5 50 04 4 5 51 10 0 5 50 012 512 51 18 58 52 20 0 0513011表 6第61页，讲稿共82张，创作于星期日62货物1货物2货物3K=3 时时第62页，讲稿共82张，创作于星期日63 0 1 2 0 1 2 3 4 5 6 7 8 9 105 50 00 0 5 50 04 4 5 51 10 0 5 50 012 512 51 18 58 52 20 0 0513011表 6第63页，讲稿共82张，创作于星期日64从从再由状态转移方程再由状态转移方程 0 1 2 0 1 2 3 4 5 6 7 8 9 105 50 00 0 5 50 0

43、4 4 5 51 10 0 5 50 012 512 51 18 58 52 20 0 0513011表 6货物1货物2货物3第64页，讲稿共82张，创作于星期日65再由状态转移方程再由状态转移方程0 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 3000481202400123表 5最大装载价值为最大装载价值为 第65页，讲稿共82张，创作于星期日66总结：今后解背包问题应先从总结：今后解背包问题应先从k=3入手：入手：k=3时 下面

44、应有重点地从下面应有重点地从k=2中求解三个最优函数值：中求解三个最优函数值：第66页，讲稿共82张，创作于星期日67K=2 时时第67页，讲稿共82张，创作于星期日68所以从第一阶段应有重点地求以下四个数：所以从第一阶段应有重点地求以下四个数：K=1 时时第68页，讲稿共82张，创作于星期日69由此逐一逆推代回上式：由此逐一逆推代回上式：第69页，讲稿共82张，创作于星期日70由此逐一逆推代回上式：由此逐一逆推代回上式：第70页，讲稿共82张，创作于星期日71由此逐一逆推代回上式：由此逐一逆推代回上式：第71页，讲稿共82张，创作于星期日72最后最后最优策略：最优策略：再由状态转移方程再由状

45、态转移方程再由状态转移方程再由状态转移方程最大装载价值为最大装载价值为 第72页，讲稿共82张，创作于星期日73例：用动态规划方法求解：例：用动态规划方法求解：解：我们用背包问题顺序解的思路：解：我们用背包问题顺序解的思路：人为的划分三个阶段：人为的划分三个阶段：k=1,2,3阶段指标函数及其他分配情况如下图：阶段指标函数及其他分配情况如下图：123第73页，讲稿共82张，创作于星期日74123动态规划的顺序递推方程为：动态规划的顺序递推方程为：第74页，讲稿共82张，创作于星期日75123第75页，讲稿共82张，创作于星期日76第76页，讲稿共82张，创作于星期日77123第77页，讲稿共82张，创作于星期日78第78页，讲稿共82张，创作于星期日79第79页，讲稿共82张，创作于星期日80第80页，讲稿共82张，创作于星期日81第81页，讲稿共82张，创作于星期日82最优决策为最优决策为所对应的最优值为所对应的最优值为第82页，讲稿共82张，创作于星期日