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

1第第9章章 动态规划的动态规划的基本原理和基本应用基本原理和基本应用1第9章 2 动动态态规规划划是是解解决决多多阶阶段段决决策策过过程程最最优优化化问问题题的的一一种种方方法法。由由美美国国数数学学家家贝贝尔尔曼曼（Bellman）等等人人在在20世世纪纪50年年代代提提出出。他他们们针针对对多多阶阶段段决决策策问问题题的的特特点点，提提出出了了解解决决这这类类问问题题的的“最最优优化化原原理理”，并并成成功功地地解解决决了了生生产产管管理理、工工程程技技术术等等方方面面的的许许多多实实际际问题。问题。2 动态规划是解决多阶段决策过程最优3 动动态态规规划划是是现现代代企企业业管管理理中中的的一一种种重重要要决决策策方方法法，可可用用于于最最优优路路径径问问题题、资资源源分分配配问问题题、生生产产计计划划和和库库存存问问题题、投投资资问问题题、装装载载问问题题、排排序序问问题及生产过程的最优控制等。题及生产过程的最优控制等。3 动态规划是现代企业管理中的一种重要决策方法4 9.1多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例多阶段决策过程最优化多阶段决策过程最优化 多阶段决策过程是指这样一类特殊的活动多阶段决策过程是指这样一类特殊的活动过程，他们可以按时间顺序分解成若干相互联过程，他们可以按时间顺序分解成若干相互联系的阶段，在每个阶段都要做出决策，全部过系的阶段，在每个阶段都要做出决策，全部过程的决策是一个决策序列，所以多阶段决策问程的决策是一个决策序列，所以多阶段决策问题也称为序贯决策问题。题也称为序贯决策问题。4 9.1多阶段决策过程最优化问题举例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后后可可以以回回收收再再生生产产，回回收收率率分分别别为为a与与b。试求进行。试求进行n个阶段后的最大总收入。个阶段后的最大总收入。5例1 多阶段资源分配问题 设有数量为x6 若以若以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 16 若以y与x-y分别投入生产方式A与B，在第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 17 因此，我们的问题就变成：求y,y1,y2,yn-8例例2 2 生产和存储控制问题生产和存储控制问题 某工厂生产某种季节性商品，需要作下一某工厂生产某种季节性商品，需要作下一年度的生产计划，假定这种商品的生产周期需年度的生产计划，假定这种商品的生产周期需要两个月，全年共有要两个月，全年共有6个生产周期，需要作出个生产周期，需要作出各个周期中的生产计划。各个周期中的生产计划。设已知各周期对该商品的需要量如下表所示设已知各周期对该商品的需要量如下表所示：周期周期123456需求量需求量5510305088例2 生产和存储控制问题 某工厂生产某种季节9例例2 2 假设这个工厂根据需要可以日夜两班生产或只是日假设这个工厂根据需要可以日夜两班生产或只是日班生产，当开足日班时，每一个生产周期能生产商品班生产，当开足日班时，每一个生产周期能生产商品1515个单位，每生产一个单位商品的成本为个单位，每生产一个单位商品的成本为100100元。当开足元。当开足夜班时，每一生产周期能生产的商品也是夜班时，每一生产周期能生产的商品也是1515个，但是由个，但是由于增加了辅助性生产设备和生产辅助费用，每生产一单于增加了辅助性生产设备和生产辅助费用，每生产一单位商品的成本为位商品的成本为120120元。由于生产能力的限制，可以在元。由于生产能力的限制，可以在需求淡季多生产一些商品储存起来以备需求旺季使用，需求淡季多生产一些商品储存起来以备需求旺季使用，但存储商品是需要存储但存储商品是需要存储费用的，假设每单位商品存储一费用的，假设每单位商品存储一周期需要周期需要16元，已知开始时存储为零，年终也不存储商元，已知开始时存储为零，年终也不存储商品备下年使用，问应该如何作生产和存储计划，才能使品备下年使用，问应该如何作生产和存储计划，才能使总的生产和存储费用最小？总的生产和存储费用最小？9例2 假设这个工厂根据需要可以日夜两班生产或只是日班生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 使使 S=为最小，其中为最小，其中10例2 设第i个周期的生产量为xi，周期11 例例例例3 3 3 3 运运输输网网络络问问题题：如如图图1 1所所示示的的运运输输网网络络，点点间间连连线线上上的的数数字字表表示示两两地地距距离离(也也可可是是运运费费、时时间等间等)，要求从，要求从v v1 1至至v v1010的最短路线。的最短路线。这这种种运运输输网网络络问问题题也也是是静静态态决决策策问问题题。但但是是，按按照照网网络络中中点点的的分分布布，可可以以把把它它分分为为4 4个个阶阶段段，而作为多阶段决策问题来研究。而作为多阶段决策问题来研究。11 例3 运输网络问题：如图1所示的运输网络，点间121234图图1 1 运输网络图示运输网络图示121234图1 运输网络图示13动态规划方法导引动态规划方法导引 为了说明动态规划的基本思想方法和特点，下面以为了说明动态规划的基本思想方法和特点，下面以图图1 1所示为例讨论求最短路问题的方法。所示为例讨论求最短路问题的方法。第第第第一一一一种种种种方方方方法法法法称称称称做做做做全全全全枚枚枚枚举举举举法法法法或或或或穷穷穷穷举举举举法法法法，它它的的基基本本思思想想是是列列举举出出所所有有可可能能发发生生的的方方案案和和结结果果，再再对对它它们们一一一一进进行行比比较较，求求出出最最优优方方案案。这这里里从从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,最短距离是最短距离是272713动态规划方法导引14 显显然然，当当组组成成交交通通网网络络的的节节点点很很多多时时，用用穷穷举举法法求求最最优优路路线线的的计计算算工工作作量量将将会会十十分分庞庞大大，而而且且其其中包含着许多重复计算中包含着许多重复计算 第第第第二二二二种种种种方方方方法法法法即即即即所所所所谓谓谓谓“局局局局部部部部最最最最优优优优路路路路径径径径”法法法法，是是说说某某人人从从k k出出发发，他他并并不不顾顾及及全全线线是是否否最最短短，只只是是选选择择当当前前最最短短途途径径，“逢逢近近便便走走”，错错误误地地以以为为局局部部最最优优会会致致整整体体最最优优，在在这这种种想想法法指指导导下下，所所取取决决策策必必是是v v1 1 v v2 2 v v5 5 v v9 9 v v1010 ，全全程程长长度度是是3030；显显然，这种方法的结果常是错误的然，这种方法的结果常是错误的14 显然，当组成交通网络的节点很多时，用穷举法求最优15 第第第第三三三三种种种种方方方方法法法法是是是是动动动动态态态态规规规规划划划划方方方方法法法法，动动态态规规划划方方法法寻寻求求该该最最短短路路问问题题的的基基本本思思想想是是，首首先先将将问问题题划划分分为为4 4个个阶阶段段，每每次次的的选选择择总总是是综综合合后后继继过过程程的的一一并并最最优优进进行行考考虑虑，在在各各段段所所有有可可能能状状态态的的最最优优后后继继过过程程都都已已求求得得的的情情况况下下，全全程程的的最最优优路路线线便便也也随之得到。随之得到。为为了了找找出出所所有有可可能能状状态态的的最最优优后后继继过过程程，动动态态规规划划方方法法是是从从过过程程的的最最后后阶阶段段开开始始考考虑虑，然然后后逆逆着着实实际际过过程程发发展展的的顺顺序序，逐逐段段向向前前递递推推计计算算直至始点。直至始点。15 第三种方法是动态规划方法，动态规划方法寻求该最短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 的的最最优优决决策策和和最最优优后后继继过过程程就就是是到到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具体说，此问题先从v10开始，因为v10是终点。再无后继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的的最优决策是到最优决策是到v v5 5,最优路线是最优路线是1234（10）（14）（16）（15）（17）17综合考虑后继过程整体最优，取最优决策是到v8,最优后继过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）18v2v5v8v10，最短距离是22依此类推，最19综上所述可见，全枚举法虽可找出最优方案，但不是个好算综上所述可见，全枚举法虽可找出最优方案，但不是个好算法，局部最优法则完全是个错误方法，只有动态规划方法属法，局部最优法则完全是个错误方法，只有动态规划方法属较科学有效的算法。它的基本思想是，把一个比较复杂的问较科学有效的算法。它的基本思想是，把一个比较复杂的问题分解为一系列同类型的更易求解的子问题，便于应用计算题分解为一系列同类型的更易求解的子问题，便于应用计算机。整个求解过程分为两个阶段，先按整体最优的思想逆序机。整个求解过程分为两个阶段，先按整体最优的思想逆序地求出各个子问题中所有可能状态的最优决策与最优路线值，地求出各个子问题中所有可能状态的最优决策与最优路线值，然后再顺序地求出整个问题的最优策略和最优路线。计算过然后再顺序地求出整个问题的最优策略和最优路线。计算过程中，系统地删去了所有中间非最优的方案组合，从而使计程中，系统地删去了所有中间非最优的方案组合，从而使计算工作量比穷举法大为减少。算工作量比穷举法大为减少。19综上所述可见，全枚举法虽可找出最优方案，但不是个好算法，20拾火柴游戏拾火柴游戏:桌子上放桌子上放30根火柴根火柴,每人一次每人一次可拾起可拾起13根根,谁拾起最后一根火柴谁输谁拾起最后一根火柴谁输,如果你先选择如果你先选择,如何保证你能赢得游戏？如何保证你能赢得游戏？2925211713951动态规划与倒推求解动态规划与倒推求解:20 拾火柴游戏:桌子上放30根火柴,每人一次可拾起121动态规划是解决动态规划是解决多阶段决策问题多阶段决策问题的一种方法。所谓多阶段的一种方法。所谓多阶段决策问题是指这样的决策问题：其过程可分为若干个相互联决策问题是指这样的决策问题：其过程可分为若干个相互联系的阶段，每一阶段都对应着一组可供选择的决策，每一决系的阶段，每一阶段都对应着一组可供选择的决策，每一决策的选定即依赖于当前面临的状态，又影响以后总体的效果。策的选定即依赖于当前面临的状态，又影响以后总体的效果。ABCDE状态A状态B状态C状态D状态E状态F决策A决策D决策E当每一阶段的决策选定以后，就构成一个决策序列，称为一个当每一阶段的决策选定以后，就构成一个决策序列，称为一个决策B决策C策略策略，它对应着一个确定的效果。它对应着一个确定的效果。多阶段决策问题就是寻找使多阶段决策问题就是寻找使此效果最好的策略。此效果最好的策略。21动态规划是解决多阶段决策问题的一种方法。所谓多阶段决策问22动态规划问题实例动态规划问题实例例例 给定一个线路网络，给定一个线路网络，AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143要从要从A向向F铺设一条输油管道，铺设一条输油管道，各点间连线上的数字表示距离，问应选择什么路线，可使总各点间连线上的数字表示距离，问应选择什么路线，可使总距离最短？距离最短？22动态规划问题实例例 给定一个线路网络，AB1B2C239.2 动态规划的基本概念和基本原理动态规划的基本概念和基本原理一、基本概念一、基本概念阶段阶段：是指问题需要做出决策的步数。阶段总数常记为：是指问题需要做出决策的步数。阶段总数常记为n，相，相应的是应的是n个阶段的决策问题。阶段的序号常记为个阶段的决策问题。阶段的序号常记为k，称为，称为阶段阶段变量变量，k=1,2,n.k即可以是顺序编号也可以是逆序编号，即可以是顺序编号也可以是逆序编号，常用顺序编号。常用顺序编号。全过程全过程；后部子过程后部子过程。状态状态：各阶段开始时的客观条件，第：各阶段开始时的客观条件，第k阶段的状态常用阶段的状态常用状态状态变量变量 表示，状态变量取值的集合称为表示，状态变量取值的集合称为状态集合状态集合，用，用表示。表示。例如，例中，例如，例中，239.2 动态规划的基本概念和基本原理一、基本24AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第1阶段第2阶段第3阶段第4阶段第5阶段状态1状态2状态3状态4状态5状态624AB1B2C1C2C3C4D1D2D3E1E2F452325决策决策：是指从某阶段的某个状态出发，在若干个不同方案中：是指从某阶段的某个状态出发，在若干个不同方案中做出的选择。表示决策的变量，称为做出的选择。表示决策的变量，称为决策变量决策变量，用，用 表示表示例如：例如：表示走到表示走到3阶段阶段,当处于当处于C2 路口时，路口时，下一下一步奔步奔D1.时的允许决策集合记为时的允许决策集合记为 ，例如：，例如：策略策略:全过程策略全过程策略 p1n；子策略；子策略pkn；最优策略最优策略。状态转移方程状态转移方程：是从上一阶段的某一状态值转变为下一阶段：是从上一阶段的某一状态值转变为下一阶段某一状态值的转移规律，用某一状态值的转移规律，用 表示。表示。决策变量允许的取值范围称为决策变量允许的取值范围称为允许决策集合允许决策集合，第，第k阶段状态为阶段状态为 25决策：是指从某阶段的某个状态出发，在若干个不同方案中做出26AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第1阶段第2阶段第3阶段第4阶段第5阶段状态1状态2状态3状态4状态5状态626AB1B2C1C2C3C4D1D2D3E1E2F452327指标函数指标函数：分：分阶段指标函数阶段指标函数和和过程指标函数过程指标函数。阶段指标函数阶段指标函数是指第是指第k阶段从状态阶段从状态 出发，采取决策出发，采取决策 时的效益，时的效益，用用表示。而表示。而过程指标函数过程指标函数指从第指从第k阶段的某状态出发，阶段的某状态出发，采取子策略采取子策略时所得到的阶段效益之和：时所得到的阶段效益之和：最优指标函数最优指标函数：表示从第：表示从第k阶段状态为阶段状态为 时采用最佳策时采用最佳策略略到过程终止时的最佳效益。记为到过程终止时的最佳效益。记为27指标函数：分阶段指标函数和过程指标函数。阶段指标函数是指28AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第1阶段第2阶段第3阶段第4阶段第5阶段状态1状态2状态3状态4状态5状态628AB1B2C1C2C3C4D1D2D3E1E2F452329其中其中 opt 可根据具体情况取可根据具体情况取max 或或min。基本方程基本方程：此为逐段递推求和的依据，一般为：此为逐段递推求和的依据，一般为：式中式中opt 可根据题意取可根据题意取 max 或或 min.例如，例的基本方程为：例如，例的基本方程为：29其中 opt 可根据具体情况取max 或min。基本方程30v即确定各个变量及方程函数即确定各个变量及方程函数v1 1、阶段变量、阶段变量v2 2、状态变量：选择时要满足两个条件：、状态变量：选择时要满足两个条件：v能正确描述受控过程的演变特性能正确描述受控过程的演变特性v要满足无后效性要满足无后效性v无后效性无后效性：给定了某阶段状态，在这阶段以后过：给定了某阶段状态，在这阶段以后过程的发展不受这阶段以前各阶段状态的影响。程的发展不受这阶段以前各阶段状态的影响。v3 3、决策变量、决策变量v4 4、列出状态转移方程、列出状态转移方程v5 5、指标函数、指标函数二、模型的构成（因素）二、模型的构成（因素）30即确定各个变量及方程函数二、模型的构成（因素）31三、三、最优化原理最优化原理：最优策略的任一后部子策略都是最优的。：最优策略的任一后部子策略都是最优的。无论以前状态决策如何，从眼下直到最后的诸决策必构成最无论以前状态决策如何，从眼下直到最后的诸决策必构成最优子策略。优子策略。动态规划应用举例动态规划应用举例例例1 最短路线问题最短路线问题AB1B2C1C2C3C4D1D2D3E1E2F45236877584534843562314331三、最优化原理：最优策略的任一后部子策略都是最优的。无论32逆序递推方程：逆序递推方程：（1）k=5 时，状态时，状态它们到它们到F 点的距离即为点的距离即为最短路。最短路。AB1B2C1C2C3C4D1D2D3E1E2F45236877584534843562314332逆序递推方程：（1）k=5 时，状态它们到F 点的距离即33AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（2）k=4 时，状态时，状态它们到它们到F 点需经过中途点需经过中途点点E，需一一分析从，需一一分析从E 到到 F的最短路：先说从的最短路：先说从D1到到F 的最短的最短路路有两种选择：经过有两种选择：经过 E1,E2,比较最短。比较最短。33AB1B2C1C2C3C4D1D2D3E1E2F452334AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143这说明由这说明由 D1 到到F 的最短距离为的最短距离为7，其路径，其路径为为相应的决策为：相应的决策为：34AB1B2C1C2C3C4D1D2D3E1E2F452335这说明由这说明由 D2 到到F 的最短距离为的最短距离为5，其路径，其路径为为相应的决策为：相应的决策为：AB1B2C1C2C3C4D1D2D3E1E2F45236877584534843562314335这说明由 D2 到F 的最短距离为5，其路径为相应的决策36AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143即即 D3 到到F 的最短距离为的最短距离为5，其路径为，其路径为相应的决策为：相应的决策为：36AB1B2C1C2C3C4D1D2D3E1E2F452337（3）k=3 时，状态时，状态这说明由这说明由 C1 到到F 的最短距离为的最短距离为12，相应的决策为，相应的决策为AB1B2C1C2C3C4D1D2D3E1E2F45236877584534843562314337（3）k=3 时，状态这说明由 C1 到F 的最短距离为38AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143即由即由 C2 到到F 的最短距离为的最短距离为10，相应的决策为，相应的决策为38AB1B2C1C2C3C4D1D2D3E1E2F452339即由即由 C3 到到F 的最短距离为的最短距离为8，相应的决策为，相应的决策为即由即由 C4 到到F 的最短距离为的最短距离为9，相应的决策为，相应的决策为AB1B2C1C2C3C4D1D2D3E1E2F45236877584534843562314339即由 C3 到F 的最短距离为8，相应的决策为即由 C440AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（4）k=2时，状态时，状态这说明由这说明由 B1 到到F 的最短距离为的最短距离为13，相应的决策为，相应的决策为40AB1B2C1C2C3C4D1D2D3E1E2F452341即由即由 B2到到F 的最短距离为的最短距离为15，相应的决策为，相应的决策为AB1B2C1C2C3C4D1D2D3E1E2F45236877584534843562314341即由 B2到F 的最短距离为15，相应的决策为AB1B242AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（5）k=1 时，只有一个状态点时，只有一个状态点A,则则即由即由 A到到F 的最短距离为的最短距离为17，相应的决策为，相应的决策为42AB1B2C1C2C3C4D1D2D3E1E2F452343所以最优路线为：所以最优路线为：AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143再按计算顺序反推可得最优决策序列：再按计算顺序反推可得最优决策序列：43所以最优路线为：AB1B2C1C2C3C4D1D2D3E44顺序递推方程：顺序递推方程：AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143例例1：1阶段2阶段3阶段4阶段5阶段行走方向行走方向第第k阶段阶段44顺序递推方程：AB1B2C1C2C3C4D1D2D3E145AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143K=1 时时注意到：注意到：所以所以45AB1B2C1C2C3C4D1D2D3E1E2F452346K=2 时时AB1B2C1C2C3C4D1D2D3E1E2F45236877584534843562314346K=2 时AB1B2C1C2C3C4D1D2D3E1E247K=3 时时AB1B2C1C2C3C4D1D2D3E1E2F45236877584534843562314347K=3 时AB1B2C1C2C3C4D1D2D3E1E248AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143或或类似地，可算出：类似地，可算出：48AB1B2C1C2C3C4D1D2D3E1E2F452349最优策略：最优策略：AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143或49最优策略：AB1B2C1C2C3C4D1D2D3E1E250最短路径：最短路径：最短路长：最短路长：注注：顺序解法与逆序解法无本质区别，一般来说，当初始状：顺序解法与逆序解法无本质区别，一般来说，当初始状态给定时用逆序解法，当终止状态给定时用顺序解法。若问态给定时用逆序解法，当终止状态给定时用顺序解法。若问题给定了一个初始状态与一个终止状态，则两种方法均可使题给定了一个初始状态与一个终止状态，则两种方法均可使用。用。50最短路径：最短路长：注：顺序解法与逆序解法无本质区别，一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（双标号法，顺序逆序选一）（双标号法，顺序逆序选一）51AB1B2C1C2C3C4D1D2D3E1E2F4523529.3 9.3 背背 包包 问问 题题 一般的提法为：一旅行者携带背包去登山。已知他所能承受一般的提法为：一旅行者携带背包去登山。已知他所能承受 的背包重量的极限为的背包重量的极限为a(千克千克)，现有，现有n种物品可供他选择装入种物品可供他选择装入背包。第背包。第i种物品的单位重量为种物品的单位重量为 (千克千克)，其价值（可以是，其价值（可以是表表明本物品对登山者的重要性指标）是携带数量明本物品对登山者的重要性指标）是携带数量 的函数的函数 （i=1 1，2 2，n）.问旅行者应如何选择携带物品的件问旅行者应如何选择携带物品的件数，以使总价值最大？数，以使总价值最大？此模型解决的是运输工具包括卫星的最优装载问题。此模型解决的是运输工具包括卫星的最优装载问题。其数学模型为：其数学模型为：529.3 背 包 问 题 一般的提法为：一旅行者携带背包53设设 为第为第 i 种物品装入的件数，则背包问题可归结为如种物品装入的件数，则背包问题可归结为如下下 形式的整数规划模型：形式的整数规划模型：下面从一个例子来分析动态规划建模。下面从一个例子来分析动态规划建模。例例 有一辆最大货运量为有一辆最大货运量为10 t 的卡车，用以装载的卡车，用以装载3种种货物，每种货物的单位重量及相应单位价值如表货物，每种货物的单位重量及相应单位价值如表4 所示。所示。应如何装载可使总价值最大？应如何装载可使总价值最大？53设 为第 i 种物品装入的件数，则背包问题可归结为54货物编号i 1 2 3单位重量（t）3 4 5单位价值 ci 4 5 6表 4 设第设第 种货物装载的件数为种货物装载的件数为 则问题可表为：则问题可表为：阶段阶段k:将可装入物品按将可装入物品按1，2，3的顺序排序，每段装入一的顺序排序，每段装入一种物品，共划分种物品，共划分3个阶段，即个阶段，即k=1,2,3.54货物编号i 1 2 55状态变量状态变量 ：在第在第k段开始时，背包中允许装入段开始时，背包中允许装入前前k种种物品的总重量。物品的总重量。决策变量决策变量 ：装入第装入第k种物品的件数。种物品的件数。状态转移方程：状态转移方程：最优指标函数最优指标函数 ：在背包中允许装入物品的总重在背包中允许装入物品的总重量不超量不超过过 kg，采取最优策略只装前，采取最优策略只装前k种物品时的最大使用价种物品时的最大使用价值值。货物1货物2货物355状态变量 ：在第k段开始时，背包中允56由此可得动态规划的顺序递推方程为：由此可得动态规划的顺序递推方程为：货物1货物2货物3K=1 时时56由此可得动态规划的顺序递推方程为：货物1货物2货物3K=57货物1货物2货物3K=1 时时注意到：注意到：例如：例如：时，时，其它计算结果见表其它计算结果见表5：57货物1货物2货物3K=1 时注意到：例如：时，其它计算结580 1 2 3 0 1 2 3 4 5 6 7 8 9 1040404040 4040 4040 4141 40 41 4240 41 4240 41 42 4340 41 42 43000448121200011233表 5580 1 59货物1货物2货物3K=2 时时其中其中例如：例如：时时，59货物1货物2货物3K=2 时其中例如：时，600 1 2 3 0 1 2 3 4 5 6 7 8 9 1040404040 4040 4040 4141 40 41 4240 41 4240 41 42 4340 41 42 430004812000123表 5600 1 61其它计算结果见表其它计算结果见表6：0 1 2 0 1 2 3 4 5 6 7 8 9 1050500 0 50504 4 51510 0 505012 5112 518 528 520 0 0513011表 661其它计算结果见表6：0 62货物1货物2货物3K=3 时时62货物1货物2货物3K=3 时63 0 1 2 0 1 2 3 4 5 6 7 8 9 1050500 0 50504 4 51510 0 505012 5112 518 528 520 0 0513011表 663 0 1 64从从再由状态转移方程再由状态转移方程 0 1 2 0 1 2 3 4 5 6 7 8 9 1050500 0 50504 4 51510 0 505012 5112 518 528 520 0 0513011表 6货物1货物2货物364从再由状态转移方程 0 65再由状态转移方程再由状态转移方程0 1 2 3 0 1 2 3 4 5 6 7 8 9 1040404040 4040 4040 4141 40 41 4240 41 4240 41 42 4340 41 42 43000481202400123表 5最大装载价值为最大装载价值为 65再由状态转移方程0 1 66总结：今后解背包问题应先从总结：今后解背包问题应先从k=3入手：入手：k=3时 下面应有重点地从下面应有重点地从k=2中求解三个最优函数值：中求解三个最优函数值：66总结：今后解背包问题应先从k=3入手：k=3时 下面应有67K=2 时时67K=2 时68所以从第一阶段应有重点地求以下四个数：所以从第一阶段应有重点地求以下四个数：K=1 时时68所以从第一阶段应有重点地求以下四个数：K=1 时69由此逐一逆推代回上式：由此逐一逆推代回上式：69由此逐一逆推代回上式：70由此逐一逆推代回上式：由此逐一逆推代回上式：70由此逐一逆推代回上式：71由此逐一逆推代回上式：由此逐一逆推代回上式：71由此逐一逆推代回上式：72最后最后最优策略：最优策略：再由状态转移方程再由状态转移方程再由状态转移方程再由状态转移方程最大装载价值为最大装载价值为 72最后最优策略：再由状态转移方程再由状态转移方程最大装载价73例：用动态规划方法求解：例：用动态规划方法求解：解：我们用背包问题顺序解的思路：解：我们用背包问题顺序解的思路：人为的划分三个阶段：人为的划分三个阶段：k=1,2,3阶段指标函数及其他分配情况如下图：阶段指标函数及其他分配情况如下图：12373例：用动态规划方法求解：解：我们用背包问题顺序解的思路：74123动态规划的顺序递推方程为：动态规划的顺序递推方程为：74123动态规划的顺序递推方程为：751237512376767712377123787879798080818182最优决策为最优决策为所对应的最优值为所对应的最优值为82最优决策为所对应的最优值为83v作业：作业：vP235 5.883作业：