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

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 多阶段资源分配问题 设有数量为x6 若以y与

3、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个阶段的总收入最大。 例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=a

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

5、生产的商品也是15个，但是由于增加了辅助性生产设备和生产辅助费用，每生产一单位商品的成本为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

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

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

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

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

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

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

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

13、略，它对应着一个确定的效果。多阶段决策问题就是寻找使此效果最好的策略。21动态规划是解决多阶段决策问题的一种方法。所谓多阶段决策问22动态规划问题实例例 给定一个线路网络，AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143要从A向F铺设一条输油管道，各点间连线上的数字表示距离，问应选择什么路线，可使总距离最短？22动态规划问题实例例 给定一个线路网络，AB1B2C239.2 动态规划的基本概念和基本原理一、基本概念阶段：是指问题需要做出决策的步数。阶段总数常记为n，相应的是n个阶段的决策问题。阶段的序号常记为k，称为阶段变量，k=1,2, ,n.

14、k即可以是顺序编号也可以是逆序编号，常用顺序编号。全过程；后部子过程。状态：各阶段开始时的客观条件，第k阶段的状态常用状态变量 表示，状态变量取值的集合称为状态集合，用表示。例如，例中，239.2 动态规划的基本概念和基本原理一、基本24AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第1阶段第2阶段第3阶段第4阶段第5阶段状态1状态2状态3状态4状态5状态624AB1B2C1C2C3C4D1D2D3E1E2F452325决策：是指从某阶段的某个状态出发，在若干个不同方案中做出的选择。表示决策的变量，称为决策变量，用 表示例如： 表示走到3阶段,

15、当处于C2 路口时，下一步奔D1. 时的允许决策集合记为 ，例如：策略:全过程策略 p1n；子策略pkn；最优策略。状态转移方程：是从上一阶段的某一状态值转变为下一阶段某一状态值的转移规律，用 表示。决策变量允许的取值范围称为允许决策集合，第k阶段状态为 25决策：是指从某阶段的某个状态出发，在若干个不同方案中做出26AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第1阶段第2阶段第3阶段第4阶段第5阶段状态1状态2状态3状态4状态5状态626AB1B2C1C2C3C4D1D2D3E1E2F452327指标函数：分阶段指标函数和过程指标函数。阶段

16、指标函数是指第k阶段从状态 出发，采取决策 时的效益，用表示。而过程指标函数指从第k阶段的某状态出发，采取子策略时所得到的阶段效益之和：最优指标函数：表示从第k阶段状态为 时采用最佳策略到过程终止时的最佳效益。记为27指标函数：分阶段指标函数和过程指标函数。阶段指标函数是指28AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143第1阶段第2阶段第3阶段第4阶段第5阶段状态1状态2状态3状态4状态5状态628AB1B2C1C2C3C4D1D2D3E1E2F452329其中 opt 可根据具体情况取max 或min。基本方程：此为逐段递推求和的依据，一般

17、为：式中opt 可根据题意取 max 或 min.例如，例的基本方程为：29其中 opt 可根据具体情况取max 或min。基本方程30即确定各个变量及方程函数1、阶段变量2、状态变量：选择时要满足两个条件：能正确描述受控过程的演变特性要满足无后效性无后效性：给定了某阶段状态，在这阶段以后过程的发展不受这阶段以前各阶段状态的影响。3、决策变量4、列出状态转移方程5、指标函数二、模型的构成（因素）30即确定各个变量及方程函数二、模型的构成（因素）31三、最优化原理：最优策略的任一后部子策略都是最优的。无论以前状态决策如何，从眼下直到最后的诸决策必构成最优子策略。动态规划应用举例例1 最短路线问题

18、AB1B2C1C2C3C4D1D2D3E1E2F45236877584534843562314331三、最优化原理：最优策略的任一后部子策略都是最优的。无论32逆序递推方程：（1）k=5 时，状态它们到F 点的距离即为最短路。AB1B2C1C2C3C4D1D2D3E1E2F45236877584534843562314332逆序递推方程：（1）k=5 时，状态它们到F 点的距离即33AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（2）k=4 时，状态它们到F 点需经过中途点E，需一一分析从E 到 F的最短路：先说从D1到F 的最短路有两种选择：

19、经过 E1, E2, 比较最短。33AB1B2C1C2C3C4D1D2D3E1E2F452334AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143这说明由 D1 到F 的最短距离为7，其路径为相应的决策为：34AB1B2C1C2C3C4D1D2D3E1E2F452335这说明由 D2 到F 的最短距离为5，其路径为相应的决策为：AB1B2C1C2C3C4D1D2D3E1E2F45236877584534843562314335这说明由 D2 到F 的最短距离为5，其路径为相应的决策36AB1B2C1C2C3C4D1D2D3E1E2F45236877

20、5845348435623143即 D3 到F 的最短距离为5，其路径为相应的决策为：36AB1B2C1C2C3C4D1D2D3E1E2F452337（3）k=3 时，状态这说明由 C1 到F 的最短距离为12，相应的决策为AB1B2C1C2C3C4D1D2D3E1E2F45236877584534843562314337（3）k=3 时，状态这说明由 C1 到F 的最短距离为38AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143即由 C2 到F 的最短距离为10，相应的决策为38AB1B2C1C2C3C4D1D2D3E1E2F452339即由 C

21、3 到F 的最短距离为8，相应的决策为即由 C4 到F 的最短距离为9，相应的决策为AB1B2C1C2C3C4D1D2D3E1E2F45236877584534843562314339即由 C3 到F 的最短距离为8，相应的决策为即由 C440AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（4）k=2时，状态这说明由 B1 到F 的最短距离为13，相应的决策为40AB1B2C1C2C3C4D1D2D3E1E2F452341即由 B2到F 的最短距离为15，相应的决策为AB1B2C1C2C3C4D1D2D3E1E2F452368775845348

22、43562314341即由 B2到F 的最短距离为15，相应的决策为AB1B242AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143（5）k=1 时，只有一个状态点A, 则即由 A到F 的最短距离为17，相应的决策为42AB1B2C1C2C3C4D1D2D3E1E2F452343所以最优路线为：AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143再按计算顺序反推可得最优决策序列：43所以最优路线为：AB1B2C1C2C3C4D1D2D3E44顺序递推方程：AB1B2C1C2C3C4D1D2D3E1E2F4

23、52368775845348435623143例1：1阶段2阶段3阶段4阶段5阶段行走方向第k阶段44顺序递推方程：AB1B2C1C2C3C4D1D2D3E145AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143K=1 时注意到：所以45AB1B2C1C2C3C4D1D2D3E1E2F452346K=2 时AB1B2C1C2C3C4D1D2D3E1E2F45236877584534843562314346K=2 时AB1B2C1C2C3C4D1D2D3E1E247K=3 时AB1B2C1C2C3C4D1D2D3E1E2F45236877584534

24、843562314347K=3 时AB1B2C1C2C3C4D1D2D3E1E248AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143或类似地，可算出：48AB1B2C1C2C3C4D1D2D3E1E2F452349最优策略：AB1B2C1C2C3C4D1D2D3E1E2F452368775845348435623143或49最优策略：AB1B2C1C2C3C4D1D2D3E1E250最短路径：最短路长：注：顺序解法与逆序解法无本质区别，一般来说，当初始状态给定时用逆序解法，当终止状态给定时用顺序解法。若问题给定了一个初始状态与一个终止状态，则两种

25、方法均可使用。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）作业：P235 5.2（双标号法，顺序逆序选一）51AB1B2C1C2C3C4D1D2D3E1E2F4523529.3 背 包 问 题 一般的提法为：一旅行者携带背包去登山。已知他所能承受 的背包重量的极限为a (千克)，现有n种物品可供他选择装入背包。第i种物品的单

26、位重量为 (千克)，其价值（可以是表明本物品对登山者的重要性指标）是携带数量 的函数 （i=1，2，n）.问旅行者应如何选择携带物品的件数，以使总价值最大？此模型解决的是运输工具包括卫星的最优装载问题。其数学模型为：529.3 背 包 问 题 一般的提法为：一旅行者携带背包53设 为第 i 种物品装入的件数，则背包问题可归结为如下 形式的整数规划模型：下面从一个例子来分析动态规划建模。例 有一辆最大货运量为10 t 的卡车，用以装载3种货物，每种货物的单位重量及相应单位价值如表4 所示。应如何装载可使总价值最大？53设 为第 i 种物品装入的件数，则背包问题可归结为54货物编号i 1 2 3单

27、位重量（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 104040 40 40 41 40 41 4240 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 104040 40 40 41 40 41 4240 41 42 430004812