运筹帷幄之中决胜千里之外运筹学课件动态规划

1、第第1页页运运 筹筹 帷帷 幄幄 之之 中中决决 胜胜 千千 里里 之之 外外运运 筹筹 学学 课课 件件动动 态态 规规 划划Dynamic ProgrammingDynamic Programming第第2页页动动 态态 规规 划划n综述综述n最优化原理最优化原理n确定性的定期多阶段决策问题确定性的定期多阶段决策问题n确定性的不定期多阶段决策问题确定性的不定期多阶段决策问题 第第3页页综综 述述 动态规划所研究的对象是多阶段决策问题。动态规划所研究的对象是多阶段决策问题。 所谓所谓多阶段决策问题是多阶段决策问题是指一类活动过程，它指一类活动过程，它可以分为若干个相互联系的阶段，在每个阶段都

2、可以分为若干个相互联系的阶段，在每个阶段都需要作出决策。这个决策不仅决定这一阶段的效需要作出决策。这个决策不仅决定这一阶段的效益，而且决定下一阶段的初始状态。益，而且决定下一阶段的初始状态。 每个阶段的决策确定以后，就得到一个决策每个阶段的决策确定以后，就得到一个决策序列，称为策略。多阶段决策问题就是求一个策序列，称为策略。多阶段决策问题就是求一个策略，使各阶段的效益的总和达到最优。略，使各阶段的效益的总和达到最优。第第4页页最优化原理最优化原理 多阶段决策问题及实例多阶段决策问题及实例 例1 例2 例3 多阶段决策问题 最优化原理最优化原理 性质 用最优化原理求解例2第第5页页例例1 1 多

3、阶段资源分配问题多阶段资源分配问题 设有数量为设有数量为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个阶段后的最大总收入。个阶段后的最大总收入。 第第6页页例例1 1 续

4、（续（1 1） 若以若以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个阶段的总收入最大。个阶段的总收入最大。 第第7页页 因此，我们的问题就变成：求因此，我们的问题就变成：求y,y1,y2,yn-1，以，以使使g(

5、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 续（续（2 2）第第8页页例例2 2 生产和存储控制问题生产和存储控制问题 某工厂生产某种季节性商品，需要作下一某工厂生产某种季节性商品，需要作下一年度的生产计划，假定这种商品的生产周期需年度的生产计划，假定这种商品的生产周期需要两个月，全年共有要两个月，全年共有6个生产周期，需要作出个生产

6、周期，需要作出各个周期中的生产计划。各个周期中的生产计划。第第9页页设已知各周期对该商品的需要量如下表所示设已知各周期对该商品的需要量如下表所示：周期周期123456需求量需求量551030508例例2 2 续（续（1 1）第第10页页例例2 2 续（续（2 2） 假设这个工厂根据需要可以日夜两班生产或只是日假设这个工厂根据需要可以日夜两班生产或只是日班生产，当开足日班时，每一个生产周期能生产商品班生产，当开足日班时，每一个生产周期能生产商品1515个单位，每生产一个单位商品的成本为个单位，每生产一个单位商品的成本为100100元。当开足元。当开足夜班时，每一生产周期能生产的商品也是夜班时，每

7、一生产周期能生产的商品也是1515个，但是由个，但是由于增加了辅助性生产设备和生产辅助费用，每生产一单于增加了辅助性生产设备和生产辅助费用，每生产一单位商品的成本为位商品的成本为120120元。由于生产能力的限制，可以在元。由于生产能力的限制，可以在需求淡季多生产一些商品储存起来以备需求旺季使用，需求淡季多生产一些商品储存起来以备需求旺季使用，但存储商品是需要存储但存储商品是需要存储费用的，假设每单位商品存储一费用的，假设每单位商品存储一周期需要周期需要16元，已知开始时存储为零，年终也不存储商元，已知开始时存储为零，年终也不存储商品备下年使用，问应该如何作生产和存储计划，才能使品备下年使用，

8、问应该如何作生产和存储计划，才能使总的生产和存储费用最小？总的生产和存储费用最小？第第11页页例例2 2 续（续（3 3） 设第设第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= = 为最小，其中为最小，其中 tjjiiuxf16116)()1852345(16

9、)(5432161xxxxxxfii第第12页页3015,300120150 ,100)(iiiiixxxxxf例例2 2 续（续（4 4）第第13页页例3.机金矿问题 两个金矿两个金矿A,B分别有存储量分别有存储量x，y，现有一部开矿机，现有一部开矿机器，如果开采金矿器，如果开采金矿A，则以概率，则以概率p1得储量得储量x的的r1倍（倍（0 r11），并且机器没有损坏，可以继续再去开采金矿），并且机器没有损坏，可以继续再去开采金矿A或或B。同时又以概率。同时又以概率1- p1宣告失败，机器报废，也宣告失败，机器报废，也得不到金子；如果把这部开矿机器用以开采金矿得不到金子；如果把这部开矿机器用

10、以开采金矿B，则以概率则以概率p2得到储量得到储量y的的r2倍（倍（0r21），并且机器没），并且机器没有损坏，可以继续再去开采金矿有损坏，可以继续再去开采金矿A或或B，同时又以概，同时又以概率率1- p2宣告失败，机器报废，也得不到金子。宣告失败，机器报废，也得不到金子。 把机器用于开采金矿把机器用于开采金矿A或者或者B，如果机器没有损坏，如果机器没有损坏，将继续把机器用于开采金矿，将继续把机器用于开采金矿A或者或者B，直到机器损，直到机器损坏，问应该如何选择开矿的序列使获得金子的期望值坏，问应该如何选择开矿的序列使获得金子的期望值最大。最大。第第14页页多阶段决策问题多阶段决策问题 有一个

11、系统，可以分成若干个阶段，任意有一个系统，可以分成若干个阶段，任意一个阶段一个阶段k，系统的状态可以用，系统的状态可以用xk表示（可以是表示（可以是数量、向量、集合等）。在每一阶段数量、向量、集合等）。在每一阶段k的每一状的每一状态都有一个决策集合态都有一个决策集合Qk(xk)，在，在Qk(xk)中选定一中选定一个决策个决策qkQk(xk)，状态，状态xk就转移到新的状态就转移到新的状态xk+1=Tk(xk,qk)，并且得到效益，并且得到效益Rk(xk,qk)。我们的。我们的目的就是在每一个阶段都在它的决策集合中选目的就是在每一个阶段都在它的决策集合中选择一个决策，使所有阶段的总效益达到最大。

12、择一个决策，使所有阶段的总效益达到最大。 这样的多阶段问题称为这样的多阶段问题称为动态规划动态规划。第第15页页最优化原理最优化原理动态规划最优化原理动态规划最优化原理：一个过程的最优策：一个过程的最优策略具有这样的性质，即无论其初始状态及略具有这样的性质，即无论其初始状态及其初始决策如何，其以后诸决策对以第一其初始决策如何，其以后诸决策对以第一个决策所形成的状态作为初始状态而言，个决策所形成的状态作为初始状态而言，必须构成最优策略。必须构成最优策略。第第16页页最优化原理的性质最优化原理的性质 对于多阶段决策问题的最优策略，对于多阶段决策问题的最优策略，如果用它的前步策略产生的情况（加上如果

13、用它的前步策略产生的情况（加上原有的约束条件）来形成一个前步问题，原有的约束条件）来形成一个前步问题，那么所给最优策略的前阶段的策略构成那么所给最优策略的前阶段的策略构成这前步问题的一个最优策略。这前步问题的一个最优策略。第第17页页用最优化原理求解例用最优化原理求解例2 如果一开始的存储量如果一开始的存储量u0已经给定，要求最后一个已经给定，要求最后一个周期结束时有存储量周期结束时有存储量un，那么最优生产和存储费用就，那么最优生产和存储费用就完全由完全由u0，un决定。对某一个周期决定。对某一个周期k，如果这个周期，如果这个周期开始时有库存量开始时有库存量uk-1，要求结束时有库存量，要求

14、结束时有库存量uk，那么，那么它的生产数量它的生产数量xk=sk+uk-uk-1，sk是这个周期的商品需求是这个周期的商品需求量，所以它的生产和存储量，所以它的生产和存储费为费为f(xk)+16 uk-1，其中，其中3015,300120150 ,100)(xxxxxf第第18页页续续 (1) 用用Fk(u0,uk)表示开始的存储量为表示开始的存储量为u0，第，第k个周期结束个周期结束时存储量为时存储量为uk的满足前的满足前k个周期需要的前个周期需要的前k个周期的最优个周期的最优生产和存储费用，由最优化原理生产和存储费用，由最优化原理 xk=sk+uk-uk-1, k=2,3,6 x1=s1+

15、u1-u0, 让让k=2,3,6，求出，求出F6(u0,u6)，就得到问题的解，就得到问题的解16)(),(min),(1101001kkkkukkuxfuuFuuFk0110116)(),(uxfuuF第第19页页确定性的定期多阶段决策问题确定性的定期多阶段决策问题q旅行售货员问题旅行售货员问题 q多阶段资源分配问题多阶段资源分配问题q用最优化原理解某些非线性规划问题用最优化原理解某些非线性规划问题 q排序排序q最优排序法最优排序法第第20页页旅行售货员问题旅行售货员问题 旅行售货员问题是图论中一个著名问题，就是在网络旅行售货员问题是图论中一个著名问题，就是在网络N上找一条从上找一条从v0点

16、出发，经过点出发，经过v1,v2,vn各一次最后返回各一次最后返回v0的最短路线和最短路程。现把它看成一个多阶段决策的最短路线和最短路程。现把它看成一个多阶段决策问题。从问题。从v0出发，经过出发，经过n个阶段，每个阶段的决策是选择个阶段，每个阶段的决策是选择下一个点。如果用所在的位置来表示状态，那么状态与下一个点。如果用所在的位置来表示状态，那么状态与阶段数就不能完全决定决策集合了，因为走过的点不需阶段数就不能完全决定决策集合了，因为走过的点不需要再走，所以决策集合与以前选的决策有关。用（要再走，所以决策集合与以前选的决策有关。用（vi,V）表示状态，表示状态，vi是所处的点，是所处的点，V

17、是还没有经过的点集合。在是还没有经过的点集合。在状态（状态（vi,V）的决策集合中，取决策）的决策集合中，取决策vjV，获得的效益是，获得的效益是vi到到vj的距离的距离dij，转入下一个状态，转入下一个状态（vj,Vvj），现在用），现在用最优化原理来找递推公式。最优化原理来找递推公式。第第21页页续续 (1) 用用fk(vi,V)表示从表示从vi点出发，经过点出发，经过V中的点各一次，中的点各一次，最后回到最后回到v0点的最短路程，点的最短路程，V是一个顶点集合，是一个顶点集合，|V|=k，dij是是vi到到vj的弧长，则的弧长，则001),(, 2 , 1),(min),(iijjkij

18、VvikdvfnkvVvfdVvfj第第22页页多阶段资源分配问题多阶段资源分配问题下面讨论有限资源分配问题，它的递推公式是：下面讨论有限资源分配问题，它的递推公式是： 一般情况下，一般情况下，g(y)，g(y)是很复杂的函数时，这个问题的是很复杂的函数时，这个问题的解不容易找。当解不容易找。当g(y)，g(y)为凸函数，且为凸函数，且h(0)=g(0)=0时，可以证明在每个阶段上时，可以证明在每个阶段上y的最优决策总是取其端的最优决策总是取其端点的值。点的值。 )()(max)(2),()()(max)(0110yxhygxfkyxbayfyxhygxfxykxyk第第23页页续续 (1)引

19、理引理5.2.1 设设g(x)，g(y)是凸函数，则对任何固定是凸函数，则对任何固定 的的x，F(y)=g(y)+h(x-y)是是y的凸函数。的凸函数。 引理引理5.2.2 设设F1(x),F2(X)是是x的凸函数，则的凸函数，则 F(x)=max F1(x),F2(X) 也是也是x的凸函数。的凸函数。第第24页页续续 (2)定理定理5.2.1 设设g(y)，g(y)是凸函数，且是凸函数，且h(0)=g(0)=0，则，则n阶阶段资源分配问题的最优策略段资源分配问题的最优策略y在每个阶段总取在每个阶段总取0yx的短的短点的值，并且点的值，并且)(),(max)()()(),()(max)(111

20、xgxhxfaxfxgbxfxhxfkkk第第25页页用最优化原理解某些非线性规划问题用最优化原理解某些非线性规划问题 假设有数量假设有数量x0的物资可用于的物资可用于n种生产，若以种生产，若以xi投入第投入第i种生产时可得收益种生产时可得收益gi(xi)，问应如何选取，问应如何选取xi，使得，使得x0用用于于n种生产时得到的总收益最大。这个问题可以写成种生产时得到的总收益最大。这个问题可以写成数学规划问题：数学规划问题：nixxxxxtsxgxgxgFinnn, 2 , 1, 0. .)()()(max0212211第第26页页续续 (1) 假设每个假设每个gi(xi)在内连续，显然在内连续

21、，显然F的极大值存的极大值存在，这是一个特殊类型的非线性规划问题，由在，这是一个特殊类型的非线性规划问题，由于这类问题的特殊结构，可以把它看成一个多于这类问题的特殊结构，可以把它看成一个多阶段决策问题，并利用动态规划的递推关系求阶段决策问题，并利用动态规划的递推关系求解。解。 把数量为把数量为x0的物资投入的物资投入n种生产方式，可以种生产方式，可以看成是看成是n阶段决策问题每阶段投入一定数量物资阶段决策问题每阶段投入一定数量物资与某种生产。第与某种生产。第i阶段初还有资源阶段初还有资源y，用，用y表示状表示状态，投入态，投入i中生产的资源为中生产的资源为xi，(0 xi y)，还剩下资，还剩

22、下资源源y- xi，并获得效益，并获得效益gi(xi)。第第27页页续续 (2) 用用fk(y)表示有资源表示有资源y投入于前投入于前k种生产方种生产方式所得到的最大收入。由最优化原理式所得到的最大收入。由最优化原理)(max)()()(max)(110101xgyfxyfxgyfyxkkkkyxkk第第28页页排排 序序 问问 题题 设有设有n个工件需要在机床个工件需要在机床A,B上加工上加工,每个工件都必每个工件都必须经过先须经过先A后后B的两道加工工序的两道加工工序,我们一号码我们一号码i(1in)表表示第示第i个工件个工件,以以Ai,Bi分别表示工件分别表示工件i在在A,B上的加工时上

23、的加工时间间,由于工序的不同由于工序的不同,所用的时间也是不同的所用的时间也是不同的,因此因此,加工加工完这完这 个工件的总时间是排列顺序的函数个工件的总时间是排列顺序的函数,现在的问题现在的问题是怎样安排加工顺序才使总时间最少是怎样安排加工顺序才使总时间最少? 用用(X,t)来描述状态来描述状态,X表示在机床表示在机床A上等待加工的工上等待加工的工件集合件集合,就是说就是说,这是这是A已经把已经把X以外的工件全加工完了以外的工件全加工完了,准备选择准备选择X中某个工件加工中某个工件加工,t表示表示B还需时刻还需时刻t才能把才能把X以外的工件加工完以外的工件加工完.第第29页页续续 (1) 在状态在状态(X,t),决策集合是工件集合决策集合是工件集合X,选定决策选定决策i属属于于X,就转入新的状态就转