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

《动态规划的基本原理和基本应用课件.ppt》由会员分享，可在线阅读，更多相关《动态规划的基本原理和基本应用课件.ppt（83页珍藏版）》请在三一办公上搜索。

1、1,第9章 动态规划的基本原理和基本应用,1第9章,2,动态规划是解决多阶段决策过程最优化问题的一种方法。由美国数学家贝尔曼（Bellman）等人在20世纪50年代提出。他们针对多阶段决策问题的特点，提出了解决这类问题的“最优化原理”，并成功地解决了生产管理、工程技术等方面的许多实际问题。,2 动态规划是解决多阶段决策过程最优,3,动态规划是现代企业管理中的一种重要决策方法，可用于最优路径问题、资源分配问题、生产计划和库存问题、投资问题、装载问题、排序问题及生产过程的最优控制等。,3 动态规划是现代企业管理中的一种重要决策方法,4,9.1多阶段决策过程最优化问题举例多阶段决策过程最优化 多阶段

2、决策过程是指这样一类特殊的活动过程，他们可以按时间顺序分解成若干相互联系的阶段，在每个阶段都要做出决策，全部过程的决策是一个决策序列，所以多阶段决策问题也称为序贯决策问题。,4 9.1多阶段决策过程最优化问题举例,5,例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 多阶段资源分配问题 设有数量为

3、x,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,6 若以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)

4、xn-1=ayn-2+b(xn-2-yn-2)yi与xi均非负,i=1,2,n-1,例1,7 因此，我们的问题就变成：求y,y1,y2,yn-,8,例2 生产和存储控制问题,某工厂生产某种季节性商品，需要作下一年度的生产计划，假定这种商品的生产周期需要两个月，全年共有6个生产周期，需要作出各个周期中的生产计划。,设已知各周期对该商品的需要量如下表所示：,8例2 生产和存储控制问题 某工厂生产某种季节,9,例2,假设这个工厂根据需要可以日夜两班生产或只是日班生产，当开足日班时，每一个生产周期能生产商品15个单位，每生产一个单位商品的成本为100元。当开足夜班时，每一生产周期能生产的商品也是15个

5、，但是由于增加了辅助性生产设备和生产辅助费用，每生产一单位商品的成本为120元。由于生产能力的限制，可以在需求淡季多生产一些商品储存起来以备需求旺季使用，但存储商品是需要存储费用的，假设每单位商品存储一周期需要16元，已知开始时存储为零，年终也不存储商品备下年使用，问应该如何作生产和存储计划，才能使总的生产和存储费用最小？,9例2 假设这个工厂根据需要可以日夜两班生产或只是日班生,10,例2,设第i个周期的生产量为xi，周期末的存储量为ui，那么这个问题用式子写出来就是：求x1,x2,x6，满足条件：x1=5+u1 x2+u1=5+u2 x3+u2=10+u3 x4+u3=30+u4 x5+u

6、4=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 运输网络问题：如图1所示的运输网络，点间连线上的数字表示两地距离(也可是运费、时间等)，要求从v1至v10的最短路线。这种运输网络问题也是静态决策问题。但是，按照网络中点的分布，可以把它分为4个阶段，而作为多阶段决策问题来研究。,11 例3 运输网络问题：如图1所示的运输网络，点间,12,图1 运输网络图示,121234图1 运输网络图示,13,动态规划方法导引 为了说明动态规划的基本思想方法和特点，下面以图1所示为例讨论求最

7、短路问题的方法。第一种方法称做全枚举法或穷举法，它的基本思想是列举出所有可能发生的方案和结果，再对它们一一进行比较，求出最优方案。这里从v1到v10的路程可以分为4个阶段。第一二段的走法有三种，第三段的走法有两种，第四段的走法仅一种，因此共有332118条可能的路线，54次加法算出各条路线的距离，最后进行17次两两比较，可知最优路线是v1 v2 v5 v8 v10,最短距离是27,13动态规划方法导引,14,显然，当组成交通网络的节点很多时，用穷举法求最优路线的计算工作量将会十分庞大，而且其中包含着许多重复计算 第二种方法即所谓“局部最优路径”法，是说某人从k出发，他并不顾及全线是否最短，只是

8、选择当前最短途径，“逢近便走”，错误地以为局部最优会致整体最优，在这种想法指导下，所取决策必是v1 v2 v5 v9 v10，全程长度是30；显然，这种方法的结果常是错误的,14 显然，当组成交通网络的节点很多时，用穷举法求最优,15,第三种方法是动态规划方法，动态规划方法寻求该最短路问题的基本思想是，首先将问题划分为4个阶段，每次的选择总是综合后继过程的一并最优进行考虑，在各段所有可能状态的最优后继过程都已求得的情况下，全程的最优路线便也随之得到。为了找出所有可能状态的最优后继过程，动态规划方法是从过程的最后阶段开始考虑，然后逆着实际过程发展的顺序，逐段向前递推计算直至始点。,15 第三种方

9、法是动态规划方法，动态规划方法寻求该最短,16,具体说，此问题先从v10开始，因为v10是终点。再无后继过程，故可以接着考虑第4阶段上所有可能状态v8,v9的最优后续过程因为从v8,v9 到v10的路线是唯一的，所以v8,v9 的最优决策和最优后继过程就是到v10，它们的最短距离分别是10和14。接着考虑阶段3上可能的状态v5,v6,v7 到v10的最优决策和最优后继过程在状态V5上，虽然到v8是6，到v9是5，但是,（10）,（14）,16具体说，此问题先从v10开始，因为v10是终点。再无后继,17,综合考虑后继过程整体最优，取最优决策是到v8,最优后继过程是v5v8 v10，最短距离是1

10、6同理，状态v6的最优决策是至v8；v7的最优决策是到v9。同样，当阶段3上所有可能状态的最优后继过程都已求得后，便可以开始考虑阶段2上所有可能状态的最优决策和最优后继过程，如v2的最优决策是到v5,最优路线是,（10）,（14）,（16）,（15）,（17）,17综合考虑后继过程整体最优，取最优决策是到v8,最优后继过,18,v2v5v8v10，最短距离是22依此类推，最后可以得到从初始状态v1的最优决策是到v2最优路线是v1v2v5v8v10，全程的最短距离是27。图1中红线表示最优路线，每点上圆括号内的数字表示该点到终点的最短路距离。,（10）,（14）,（16）,（15）,（17）,（

11、22）,（22）,（21）,（27）,18v2v5v8v10，最短距离是22依此类推，最,19,综上所述可见，全枚举法虽可找出最优方案，但不是个好算法，局部最优法则完全是个错误方法，只有动态规划方法属较科学有效的算法。它的基本思想是，把一个比较复杂的问题分解为一系列同类型的更易求解的子问题，便于应用计算机。整个求解过程分为两个阶段，先按整体最优的思想逆序地求出各个子问题中所有可能状态的最优决策与最优路线值，然后再顺序地求出整个问题的最优策略和最优路线。计算过程中，系统地删去了所有中间非最优的方案组合，从而使计算工作量比穷举法大为减少。,19综上所述可见，全枚举法虽可找出最优方案，但不是个好算法

12、，,20,拾火柴游戏:桌子上放30根火柴,每人一次可拾起13根,谁拾起最后一根火柴谁输,如果你先选择,如何保证你能赢得游戏？2925211713951,动态规划与倒推求解:,20拾火柴游戏:桌子上放30根火柴,每人一次可拾起1,21,动态规划是解决多阶段决策问题的一种方法。所谓多阶段,决策问题是指这样的决策问题：其过程可分为若干个相互联,系的阶段，每一阶段都对应着一组可供选择的决策，每一决,策的选定即依赖于当前面临的状态，又影响以后总体的效果。,A,B,C,D,E,状态A,状态B,状态C,状态D,状态E,状态F,决策A,决策D,决策E,当每一阶段的决策选定以后，就构成一个决策序列，称为一个,决

13、策B,决策C,策略，它对应着一个确定的效果。多阶段决策问题就是寻找使,此效果最好的策略。,21动态规划是解决多阶段决策问题的一种方法。所谓多阶段决策问,22,动态规划问题实例,例 给定一个线路网络，,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,要从A向F铺设一条输油管道，,各点间连线上的数字表示距离，问应选择什么路线，可使总,距离最短？,22动态规划问题实例例 给定一个线路网络，AB1B2C,23,9.2 动态规划的基本概念和基本原理,一、基本概念,阶段：是指问题需要做

14、出决策的步数。阶段总数常记为n，相应的是n个阶段的决策问题。阶段的序号常记为k，称为阶段变量，k=1,2,n.k即可以是顺序编号也可以是逆序编号，常用顺序编号。全过程；后部子过程。,状态：各阶段开始时的客观条件，第k阶段的状态常用状态变量 表示，状态变量取值的集合称为状态集合，用表示。,例如，例中，,239.2 动态规划的基本概念和基本原理一、基本,24,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,第1阶段,第2阶段,第3阶段,第4阶段,第5阶段,状态1,状态2,状态3

15、,状态4,状态5,状态6,24AB1B2C1C2C3C4D1D2D3E1E2F4523,25,决策：是指从某阶段的某个状态出发，在若干个不同方案中,做出的选择。表示决策的变量，称为决策变量，用 表示,例如：表示走到3阶段,当处于C2 路口时，下一步奔D1.,时的允许决策集合记为，例如：策略:全过程策略 p1n；子策略pkn；最优策略。,状态转移方程：是从上一阶段的某一状态值转变为下一阶段某一状态值的转移规律，用,表示。,决策变量允许的取值范围称为允许决策集合，第k阶段状态为,25决策：是指从某阶段的某个状态出发，在若干个不同方案中做出,26,A,B1,B2,C1,C2,C3,C4,D1,D2,

16、D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,第1阶段,第2阶段,第3阶段,第4阶段,第5阶段,状态1,状态2,状态3,状态4,状态5,状态6,26AB1B2C1C2C3C4D1D2D3E1E2F4523,27,指标函数：分阶段指标函数和过程指标函数。阶段指标函数,是指第k阶段从状态 出发，采取决策 时的效益，用,表示。而过程指标函数指从第k阶段的某状态出发，,采取子策略,时所得到的阶段效益之和：,最优指标函数：表示从第k阶段状态为 时采用最佳策略,到过程终止时的最佳效益。记为,27指标函数：分阶段指标函数和过程指标函数。

17、阶段指标函数是指,28,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,第1阶段,第2阶段,第3阶段,第4阶段,第5阶段,状态1,状态2,状态3,状态4,状态5,状态6,28AB1B2C1C2C3C4D1D2D3E1E2F4523,29,其中 opt 可根据具体情况取max 或min。,基本方程：此为逐段递推求和的依据，一般为：,式中opt 可根据题意取 max 或 min.,例如，例的基本方程为：,29其中 opt 可根据具体情况取max 或min。基本方程,30,即确定

18、各个变量及方程函数1、阶段变量2、状态变量：选择时要满足两个条件：能正确描述受控过程的演变特性要满足无后效性无后效性：给定了某阶段状态，在这阶段以后过程的发展不受这阶段以前各阶段状态的影响。3、决策变量4、列出状态转移方程5、指标函数,二、模型的构成（因素）,30即确定各个变量及方程函数二、模型的构成（因素）,31,三、最优化原理：最优策略的任一后部子策略都是最优的。,无论以前状态决策如何，从眼下直到最后的诸决策必构成最优子策略。,动态规划应用举例,例1 最短路线问题,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,

19、4,8,4,3,5,6,2,3,1,4,3,31三、最优化原理：最优策略的任一后部子策略都是最优的。无论,32,逆序递推方程：,（1）k=5 时，状态,它们到F 点的距离即为,最短路。,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,32逆序递推方程：（1）k=5 时，状态它们到F 点的距离即,33,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,（2）

20、k=4 时，状态,它们到F 点需经过中途,点E，需一一分析从E 到 F的最短路：先说从D1到F 的最短路,有两种选择：经过 E1,E2,比较最短。,33AB1B2C1C2C3C4D1D2D3E1E2F4523,34,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,这说明由 D1 到F 的最短距离为7，其路径为,相应的决策为：,34AB1B2C1C2C3C4D1D2D3E1E2F4523,35,这说明由 D2 到F 的最短距离为5，其路径为,相应的决策为：,A,B1,B2,C

21、1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,35这说明由 D2 到F 的最短距离为5，其路径为相应的决策,36,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,即 D3 到F 的最短距离为5，其路径为,相应的决策为：,36AB1B2C1C2C3C4D1D2D3E1E2F4523,37,（3）k=3 时，状态,这说明由 C1 到F 的最短距离为12，相应的决策为,A,B

22、1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,37（3）k=3 时，状态这说明由 C1 到F 的最短距离为,38,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,即由 C2 到F 的最短距离为10，相应的决策为,38AB1B2C1C2C3C4D1D2D3E1E2F4523,39,即由 C3 到F 的最短距离为8，相应的决策为,即由 C4 到F 的最短距离为9

23、，相应的决策为,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,39即由 C3 到F 的最短距离为8，相应的决策为即由 C4,40,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,（4）k=2时，状态,这说明由 B1 到F 的最短距离为13，相应的决策为,40AB1B2C1C2C3C4D1D2D3E1E2F4523,41,即由 B2到F 的最短距离为15

24、，相应的决策为,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,41即由 B2到F 的最短距离为15，相应的决策为AB1B2,42,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,（5）k=1 时，只有一个状态点A,则,即由 A到F 的最短距离为17，相应的决策为,42AB1B2C1C2C3C4D1D2D3E1E2F4523,43,所以最优路线为：,A,

25、B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,再按计算顺序反推可得最优决策序列：,43所以最优路线为：AB1B2C1C2C3C4D1D2D3E,44,顺序递推方程：,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,例1：,1阶段,2阶段,3阶段,4阶段,5阶段,行走方向,第k阶段,44顺序递推方程：AB1B2C1C2C3C4D1D2D3E1,45,A,B1

26、,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,K=1 时,注意到：,所以,45AB1B2C1C2C3C4D1D2D3E1E2F4523,46,K=2 时,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,46K=2 时AB1B2C1C2C3C4D1D2D3E1E2,47,K=3 时,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5

27、,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,47K=3 时AB1B2C1C2C3C4D1D2D3E1E2,48,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,或,类似地，可算出：,48AB1B2C1C2C3C4D1D2D3E1E2F4523,49,最优策略：,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,

28、或,49最优策略：AB1B2C1C2C3C4D1D2D3E1E2,50,最短路径：,最短路长：,注：顺序解法与逆序解法无本质区别，一般来说，当初始状态给定时用逆序解法，当终止状态给定时用顺序解法。若问题给定了一个初始状态与一个终止状态，则两种方法均可使用。,50最短路径：最短路长：注：顺序解法与逆序解法无本质区别，一,51,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,（4，F）,（3，F）,（5，E1）,（5，E2）,（7，E1）,（12，D1）,（10，D2）,（8，

29、D2）,（9，D3）,（13，C2）,（15，C3）,（17，B1）,作业：P235 5.2（双标号法，顺序逆序选一）,51AB1B2C1C2C3C4D1D2D3E1E2F4523,52,9.3 背 包 问 题,一般的提法为：一旅行者携带背包去登山。已知他所能承受 的背包重量的极限为a(千克)，现有n种物品可供他选择装入背包。第i种物品的单位重量为(千克)，其价值（可以是表明本物品对登山者的重要性指标）是携带数量 的函数（i=1，2，n）.问旅行者应如何选择携带物品的件数，以使总价值最大？,此模型解决的是运输工具包括卫星的最优装载问题。,其数学模型为：,529.3 背 包 问 题 一般的提法为

30、：一旅行者携带背包,53,设 为第 i 种物品装入的件数，则背包问题可归结为如下,形式的整数规划模型：,下面从一个例子来分析动态规划建模。,例 有一辆最大货运量为10 t 的卡车，用以装载3种货物，每种货物的单位重量及相应单位价值如表4 所示。,应如何装载可使总价值最大？,53设 为第 i 种物品装入的件数，则背包问题可归结为,54,表 4,阶段k:将可装入物品按1，2，3的顺序排序，每段装入一种物品，共划分3个阶段，即k=1,2,3.,54货物编号i 1 2,55,状态变量：在第k段开始时，背包中允许装入前k种物品的总重量。,决策变量：装入第k种物品的件数。,状态转移方程：,最优指标函数：在

31、背包中允许装入物品的总重量不超过 kg，采取最优策略只装前k种物品时的最大使用价值。,货物1,货物2,货物3,55状态变量：在第k段开始时，背包中允,56,由此可得动态规划的顺序递推方程为：,货物1,货物2,货物3,K=1 时,56由此可得动态规划的顺序递推方程为：货物1货物2货物3K=,57,货物1,货物2,货物3,K=1 时,注意到：,例如：,时，,其它计算结果见表5：,57货物1货物2货物3K=1 时注意到：例如：时，其它计算结,58,表 5,580 1,59,货物1,货物2,货物3,K=2 时,其中,例如：,时，,59货物1货物2货物3K=2 时其中例如：时，,60,表 5,600 1

32、,61,其它计算结果见表6：,表 6,61其它计算结果见表6：0,62,货物1,货物2,货物3,K=3 时,62货物1货物2货物3K=3 时,63,表 6,63 0 1,64,从,再由状态转移方程,表 6,货物1,货物2,货物3,64从再由状态转移方程 0,65,再由状态转移方程,表 5,最大装载价值为,65再由状态转移方程0 1,66,总结：今后解背包问题应先从k=3入手：,k=3时,下面应有重点地从k=2中求解三个最优函数值：,66总结：今后解背包问题应先从k=3入手：k=3时 下面应有,67,K=2 时,67K=2 时,68,所以从第一阶段应有重点地求以下四个数：,K=1 时,68所以从

33、第一阶段应有重点地求以下四个数：K=1 时,69,由此逐一逆推代回上式：,69由此逐一逆推代回上式：,70,由此逐一逆推代回上式：,70由此逐一逆推代回上式：,71,由此逐一逆推代回上式：,71由此逐一逆推代回上式：,72,最后,最优策略：,再由状态转移方程,再由状态转移方程,最大装载价值为,72最后最优策略：再由状态转移方程再由状态转移方程最大装载价,73,例：用动态规划方法求解：,解：我们用背包问题顺序解的思路：人为的划分三个阶段：k=1,2,3阶段指标函数及其他分配情况如下图：,73例：用动态规划方法求解：解：我们用背包问题顺序解的思路：,74,动态规划的顺序递推方程为：,74123动态规划的顺序递推方程为：,75,75123,76,76,77,77123,78,78,79,79,80,80,81,81,82,最优决策为,所对应的最优值为,82最优决策为所对应的最优值为,83,作业：P235 5.8,83作业：,