运筹学教学课件 第5章 动态规划.ppt

《运筹学教学课件 第5章 动态规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、运筹帷幄之中决胜千里之外运筹学课件动态规划DynamicProgramming动态规划综述最优化原理确定性的定期多阶段决策问题确定性的不定期多阶段决策问题综述动态规划所研究的对象是多阶段决策问题。所谓多阶段决策问题是指一类活动过程，它可以分为若干个相互联系的阶段，在每个阶段都需要作出决策。这个决策不仅决定这一阶段的效益，而且决定下一阶段的初始状态。每个阶段的决策确定以后，就得到一个决策序列，称为策略。多阶段决策问题就是求一个策略，使各阶段的效益的总和达到最优。最优化原理多阶段决策问题及实例例1例2例3多阶段决策问题最优化原理性质用最

2、优化原理求解例2例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个阶段后的最大总收入。例1续（1）若以y与x-y分别投入生产方式A与B，在第一阶段生产后回收的总资源为x1=ay+b(x-y)，再将x1投入生产方式A和B，则可得到收入g(y1)+h(x1-y1)，继续回收资源

3、x2=ay1+b(x1-y1)，……若上面的过程进行n个阶段，我们希望选择n个变量y,y1,y2,…,yn-1，使这n个阶段的总收入最大。因此，我们的问题就变成：求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续（2）例2生产和存储控制问题某工厂生产某种季节性商品，需要作下一年度的生产

4、计划，假定这种商品的生产周期需要两个月，全年共有6个生产周期，需要作出各个周期中的生产计划。设已知各周期对该商品的需要量如下表所示：周期123456需求量551030508例2续（1）例2续（2）假设这个工厂根据需要可以日夜两班生产或只是日班生产，当开足日班时，每一个生产周期能生产商品15个单位，每生产一个单位商品的成本为100元。当开足夜班时，每一生产周期能生产的商品也是15个，但是由于增加了辅助性生产设备和生产辅助费用，每生产一单位商品的成本为120元。由于生产能力的限制，可以在需求淡季多生产一些商品储存起来以备需求旺季使用，但存储

5、商品是需要存储费用的，假设每单位商品存储一周期需要16元，已知开始时存储为零，年终也不存储商品备下年使用，问应该如何作生产和存储计划，才能使总的生产和存储费用最小？例2续（3）设第i个周期的生产量为xi，周期末的存储量为ui，那么这个问题用式子写出来就是：求x1,x2,…,x6，满足条件：x1=5+u1x2+u1=5+u2x3+u2=10+u3x4+u3=30+u4x5+u4=50+u5x6+u5=80xi30,0uj,i=1,2,…,6;j=1,2,…,5使S==为最小，其中例2续（4）例3.机金矿问题两个金矿A,B分别有存储量x，y

6、，现有一部开矿机器，如果开采金矿A，则以概率p1得储量x的r1倍（0

7、干个阶段，任意一个阶段k，系统的状态可以用xk表示（可以是数量、向量、集合等）。在每一阶段k的每一状态都有一个决策集合Qk(xk)，在Qk(xk)中选定一个决策qkQk(xk)，状态xk就转移到新的状态xk+1=Tk(xk,qk)，并且得到效益Rk(xk,qk)。我们的目的就是在每一个阶段都在它的决策集合中选择一个决策，使所有阶段的总效益达到最大。这样的多阶段问题称为动态规划。最优化原理动态规划最优化原理：一个过程的最优策略具有这样的性质，即无论其初始状态及其初始决策如何，其以后诸决策对以第一个决策所形成的状态作为初始状态而言，必须构成

8、最优策略。最优化原理的性质对于多阶段决策问题的最优策略，如果用它的前步策略产生的情况（加上原有的约束条件）来形成一个前步问题，那么所给最优策略的前阶段的策略构成这前步问题的一个最优策略。用最优化原理求解例2