运筹帷幄之中决胜千里之外运筹学课件

第1页运筹帷幄之中决胜千里之外运筹学课件动态规划DynamicProgramming第2页动态规划综述最优化原理确定性的定期多阶段决策问题确定性的不定期多阶段决策问题第3页综述动态规划所研究的对象是多阶段决策问题。所谓多阶段决策问题是指一类活动过程，它可以分为若干个相互联系的阶段，在每个阶段都需要作出决策。这个决策不仅决定这一阶段的效益，而且决定下一阶段的初始状态。每个阶段的决策确定以后，就得到一个决策序列，称为策略。多阶段决策问题就是求一个策略，使各阶段的效益的总和达到最优。第4页最优化原理多阶段决策问题及实例例1例2例3多阶段决策问题最优化原理性质用最优化原理求解例2第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个阶段后的最大总收入。第6页例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(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）第8页例2生产和存储控制问题某工厂生产某种季节性商品，需要作下一年度的生产计划，假定这种商品的生产周期需要两个月，全年共有6个生产周期，需要作出各个周期中的生产计划。第9页设已知各周期对该商品的需要量如下表所示：周期123456需求量551030508例2续（1）第10页例2续（2）假设这个工厂根据需要可以日夜两班生产或只是日班生产，当开足日班时，每一个生产周期能生产商品15个单位，每生产一个单位商品的成本为100元。当开足夜班时，每一生产周期能生产的商品也是15个，但是由于增加了辅助性生产设备和生产辅助费用，每生产一单位商品的成本为120元。由于生产能力的限制，可以在需求淡季多生产一些商品储存起来以备需求旺季使用，但存储商品是需要存储费用的，假设每单位商品存储一周期需要16元，已知开始时存储为零，年终也不存储商品备下年使用，问应该如何作生产和存储计划，才能使总的生产和存储费用最小？第11页例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==为最小，其中tjjiiuxf16116)()1852345(16)(5432161xxxxxxfii第12页3015,300120150,100)(iiiiixxxxxf例2续（4）第13页例3.机金矿问题两个金矿A,B分别有存储量x，y，现有一部开矿机器，如果开采金矿A，则以概率p1得储量x的r1倍（0r11），并且机器没有损坏，可以继续再去开采金矿A或B。同时又以概率1-p1宣告失败，机器报废，也得不到金子；如果把这部开矿机器用以开采金矿B，则以概率p2得到储量y的r2倍（0r21），并且机器没有损坏，可以继续再去开采金矿A或B，同时又以概率1-p2宣告失败，机器报废，也得不到金子。把机器用于开采金矿A或者B，如果机器没有损坏，将继续把机器用于开采金矿A或者B，直到机器损坏，问应该如何选择开矿的序列使获得金子的期望值最大。第14页多阶段决策问题有一个系统，可以分成若干个阶段，任意一个阶段k，系统的状态可以用xk表示（可以是数量、向量、集合等）。在每一阶段k的每一状态都有一个决策集合Qk(xk)，在Qk(xk)中选定一个决策qkQk(xk)，状态xk就转移到新的状态xk+1=Tk(xk,qk)，并且得到效益Rk(xk,qk)。我们的目的就是在每一个阶段都在它的决策集合中选择一个决策，使所有阶段的总效益达到最大。这样的多阶段问题称为动态规划。第15页最优化原理动态规划最优化原理：一个过程的最优策略具有这样的性质，即无论其初始状态及其初始决策如何，其以后诸决策对以第一个决策所形成的状态作为初始状态而言，必须构成最优策略。第16页最优化原理的性质对于多阶段决策问题的最优策略，如果用它的前步策略产生的情况（加上原有的约束条件）来形成一个前步问题，那么所给最优策略的前阶段的策略构成这前步问题的一个最优策略。第17页用最优化原理求解例2如果一开始的存储量u0已经给定，要求最后一个周期结束时有存储量un，那么最优生产和存储费用就完全由u0，un决定。对某一个周期k，如果这个周期开始时有库存量uk-1，要求结束时有库存量uk，那么它的生产数量xk=sk+uk-uk-1，sk是这个周期的商品需求量，所以它的生产和存储费为f(xk)+16uk-1，其中3015,300120150,100)(xxxxxf第18页续(1)用Fk(u0,uk)表示开始的存储量为u0，第k个周期结束时存储量为uk的满足前k个周期需要的前k个周期的最优生产和存储费用，由最优化原理xk=sk+uk-uk-1,k=2,3,…,6x1=s1+u1-u0,让k=2,3,…,6，求出F6(u0,u6)，就得到问题的解}16)(),({min),(1101001kkkkukkuxfuuFuuFk0110116)(),(uxfuuF第19页确定性的定期多阶段决策问题旅行售货员问题多阶段资源分配问题用最优化原理解某些非线性规划问题排序最优排序法第20页旅行售货员问题旅行售货员问题是图论中一个著名问题，就是在网络N上找一条从v0点出发，经过v1,v2,…,vn各一次最后返回v0的最短路线和最短路程。现把它看成一个多阶段决策问题。从v0出发，经过n个阶段，每个阶段的决策是选择下一个点。如果用所在的位置来表示状态，那么状态与阶段数就不能完全决定决策集合了，因为走过的点不需要再走，所以决策集合与以前选的决策有关。用（vi,V）表示状态，vi是所处的点，V是还没有经过的点集合。在状态（vi,V）的决策集合中，取决策vjV，获得的效益是vi到vj的距离dij，转入下一个状态（vj,V\{vj}），现在用最优化原理来找递推公式。第21页续(1)用fk(vi,V)表示从vi点出发，经过V中的点各一次，最后回到v0点的最短路程，V是一个顶点集合，|V|=k，dij是vi到vj的弧长，则001),(,,2,1})},{\,({min),(iijjkijVvikdvfnkvVvfdVvfj第22页多阶段资源分配问题下面讨论有限资源分配问题，它的递推公式是：一般情况下，g(y)，g(y)是很复杂的函数时，这个问题的解不容易找。当g(y)，g(y)为凸函数，且h(0)=g(0)=0时，可以证明在每个阶段上y的最优决策总是取其端点的值。)}()({max)(2))},(()()({max)(0110yxhygxfkyxbayfyxhygxfxykxyk第23页续(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(X)}也是x的凸函数。第24页续(2)定理5.2.1设g(y)，g(y)是凸函数，且h(0)=g(0)=0，则n阶段资源分配问题的最优策略y在每个阶段总取0yx的短点的值，并且)}(),(max{)()}()(),()(max{)(111xgxhxfaxfxgbxfxhxfkkk第25页用最优化原理解某些非线性规划问题假设有数量x0的物资可用于n种生产，若以xi投入第i种生产时可得收益gi(xi)，问应如何选取xi，使得x0用于n种生产时得到的总收益最大。这个问题可以写成数学规划问题：nixxxxxtsxgxgxgFinnn,,2,1,0..)()()(max0212211第26页续(1)假设每个gi(xi)在内连续，显然F的极大值存在，这是一个特殊类型的非线性规划问题，由于这类问题的特殊结构，可以把它看成一个多阶段决策问题，并利用动态规划的递推关系求解。把数量为x0的物资投入n种生产方式，可以看成是n阶段决策问题每阶段投入一定数量物资与某种生产。第i阶段初还有资源y，用y表示状态，投入i中生产的资源为xi，(0xiy)，还剩下资源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上的加工时间,由于工序的不同,所用的时间也是不同的,因此,加工完这个工件的总时间是排列顺序的函数,现在的问题是怎样安排加工顺序才使总时间最少?用(X,t)来描述状态,X表示在机床A上等待加工的工件集合,就是说,这是A已经把X以外的工件全加工完了,准备选择X中某个工件加工,t表示B还需时刻t才能把X以外的工件加工完.第29页续(1)在状态(X,t),决策集合是工件集合X,选定决策{i}属于X,就转入新的状态(X\{i},zi(t)),并获得效益.用最优化原理得到这是一个递推公式,有{X}=0开始,直到X=n.{}(,)min{(\{},())}(,)iiiXfXtafXiztftt第30页最优排序法1:找出a1,a2,…,an,b1,b2,…,bn中的最小数.2:若最小者为ai,则将工件i排在第一位,并从工件集合中去掉这个工件.3:若最小者为bj,则将工件j排在最后一位,并从工件集合中去掉这个工件.4:对剩下的工件重复上述手续,直到工件集合为空集合时停止.第31页给定5个工件,在A,B上的加工时间如下表所示.用上述方法,很容易得到最优化顺序是13542例n12345A37457B62734第32页确定性的不定期多阶段决策问题有的多阶段决策过程,给定一个状态集合XT,当状态xXT时,过程停止,这是阶段不确定的多阶段决策过程,如果经过有限阶段,状态x一定能进入XT,就是阶段数有限的,否则就是阶段数无限的.这类问题通常利用最优化原理得到一个函数方程来求解.主要有:1:最优线路问题.2:有限资源分配问题.不作详细讲述.