运筹学课件05动态规划

1、运 筹 帷 幄 之 中决 胜 千 里 之 外运 筹 学 课 件动 态 规 划Dynamic Programming动 态 规 划综述最优化原理确定性的定期多阶段决策问题确定性的不定期多阶段决策问题 综 述 动态规划所研究的对象是多阶段决策问题。 所谓多阶段决策问题是指一类活动过程，它可以分为若干个相互联系的阶段，在每个阶段都需要作出决策。这个决策不仅决定这一阶段的效益，而且决定下一阶段的初始状态。 每个阶段的决策确定以后，就得到一个决策序列，称为策略。多阶段决策问题就是求一个策略，使各阶段的效益的总和达到最优。最优化原理 多阶段决策问题及实例 例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)，继续回收资源x2=ay1+b(x1-y1)， 若上面的

3、过程进行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 生产和存储控制问题 某工厂生产某种季节性商品，需要作下一年度的生产计划，假定这种商品的生产周期需要两个月，全年共有6个生产周期，需要作出各个周期中的生产计划。设

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

5、产和存储费用最小？例2 续（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= = 为最小，其中例2 续（4）例3.机金矿问题 两个金矿A,B分别有存储量x，y，现有一部开矿机器，如果开采金矿A，则以概率p1得储量x的r1倍（0 r11），并且机器没有损坏，可以继续再去开采金矿A或B。同时又以概率1- p1宣告失败，机器报废，也得不到金

6、子；如果把这部开矿机器用以开采金矿B，则以概率p2得到储量y的r2倍（0r21），并且机器没有损坏，可以继续再去开采金矿A或B，同时又以概率1- p2宣告失败，机器报废，也得不到金子。 把机器用于开采金矿A或者B，如果机器没有损坏，将继续把机器用于开采金矿A或者B，直到机器损坏，问应该如何选择开矿的序列使获得金子的期望值最大。多阶段决策问题 有一个系统，可以分成若干个阶段，任意一个阶段k，系统的状态可以用xk表示（可以是数量、向量、集合等）。在每一阶段k的每一状态都有一个决策集合Qk(xk)，在Qk(xk)中选定一个决策qkQk(xk)，状态xk就转移到新的状态xk+1=Tk(xk,qk)，并

7、且得到效益Rk(xk,qk)。我们的目的就是在每一个阶段都在它的决策集合中选择一个决策，使所有阶段的总效益达到最大。 这样的多阶段问题称为动态规划。最优化原理动态规划最优化原理：一个过程的最优策略具有这样的性质，即无论其初始状态及其初始决策如何，其以后诸决策对以第一个决策所形成的状态作为初始状态而言，必须构成最优策略。最优化原理的性质 对于多阶段决策问题的最优策略，如果用它的前步策略产生的情况（加上原有的约束条件）来形成一个前步问题，那么所给最优策略的前阶段的策略构成这前步问题的一个最优策略。用最优化原理求解例2 如果一开始的存储量u0已经给定，要求最后一个周期结束时有存储量un，那么最优生产

8、和存储费用就完全由u0，un决定。对某一个周期k，如果这个周期开始时有库存量uk-1，要求结束时有库存量uk，那么它的生产数量xk=sk+uk-uk-1，sk是这个周期的商品需求量，所以它的生产和存储费为f(xk)+16 uk-1，其中续 (1) 用Fk(u0,uk)表示开始的存储量为u0，第k个周期结束时存储量为uk的满足前k个周期需要的前k个周期的最优生产和存储费用，由最优化原理 xk=sk+uk-uk-1, k=2,3,6 x1=s1+u1-u0, 让k=2,3,6，求出F6(u0,u6)，就得到问题的解确定性的定期多阶段决策问题旅行售货员问题 多阶段资源分配问题用最优化原理解某些非线性

9、规划问题 排序最优排序法旅行售货员问题 旅行售货员问题是图论中一个著名问题，就是在网络N上找一条从v0点出发，经过v1,v2,vn各一次最后返回v0的最短路线和最短路程。现把它看成一个多阶段决策问题。从v0出发，经过n个阶段，每个阶段的决策是选择下一个点。如果用所在的位置来表示状态，那么状态与阶段数就不能完全决定决策集合了，因为走过的点不需要再走，所以决策集合与以前选的决策有关。用（vi,V）表示状态，vi是所处的点，V是还没有经过的点集合。在状态（vi,V）的决策集合中，取决策vjV，获得的效益是vi到vj的距离dij，转入下一个状态（vj,Vvj），现在用最优化原理来找递推公式。续 (1)

10、 用fk(vi,V)表示从vi点出发，经过V中的点各一次，最后回到v0点的最短路程，V是一个顶点集合，|V|=k，dij是vi到vj的弧长，则多阶段资源分配问题下面讨论有限资源分配问题，它的递推公式是： 一般情况下，g(y)，g(y)是很复杂的函数时，这个问题的解不容易找。当g(y)，g(y)为凸函数，且h(0)=g(0)=0时，可以证明在每个阶段上y的最优决策总是取其端点的值。 续 (1)引理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

11、(X) 也是x的凸函数。续 (2)定理5.2.1 设g(y)，g(y)是凸函数，且h(0)=g(0)=0，则n阶段资源分配问题的最优策略y在每个阶段总取0yx的短点的值，并且用最优化原理解某些非线性规划问题 假设有数量x0的物资可用于n种生产，若以xi投入第i种生产时可得收益gi(xi)，问应如何选取xi，使得x0用于n种生产时得到的总收益最大。这个问题可以写成数学规划问题：续 (1) 假设每个gi(xi)在内连续，显然F的极大值存在，这是一个特殊类型的非线性规划问题，由于这类问题的特殊结构，可以把它看成一个多阶段决策问题，并利用动态规划的递推关系求解。 把数量为x0的物资投入n种生产方式，可

12、以看成是n阶段决策问题每阶段投入一定数量物资与某种生产。第i阶段初还有资源y，用y表示状态，投入i中生产的资源为xi，(0 xi y)，还剩下资源y- xi，并获得效益gi(xi)。续 (2) 用fk(y)表示有资源y投入于前k种生产方式所得到的最大收入。由最优化原理排 序 问 题 设有n个工件需要在机床A,B上加工,每个工件都必须经过先A后B的两道加工工序,我们一号码i(1in)表示第i个工件,以Ai,Bi分别表示工件i在A,B上的加工时间,由于工序的不同,所用的时间也是不同的,因此,加工完这 个工件的总时间是排列顺序的函数,现在的问题是怎样安排加工顺序才使总时间最少? 用(X,t)来描述状

13、态,X表示在机床A上等待加工的工件集合,就是说,这是A已经把X以外的工件全加工完了,准备选择X中某个工件加工,t表示B还需时刻t才能把X以外的工件加工完.续 (1) 在状态(X,t),决策集合是工件集合X,选定决策i属于X,就转入新的状态(Xi, zi(t),并获得效益 .用最优化原理得到 这是一个递推公式,有X=0开始,直到X=n.最优排序法 1: 找出a1,a2,an,b1,b2, ,bn中的最小数.2: 若最小者为ai ,则将工件i排在第一位,并从工件集合中去掉这个工件.3: 若最小者为bj,则将工件j排在最后一位,并从工件集合中去掉这个工件.4: 对剩下的工件重复上述手续,直到工件集合为空集合时停止.给定5个工件,在A,B上的加工时间如下表所示.用上述方法