第5章 动态规划

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

1、62338357(O)yuyingzhao@yahoo.com.cn运筹学千里之外决胜帷幄之中运筹主讲教师赵玉英北京林业大学理学院第5章动态规划动态规划简介最优化原理确定性的定期多阶段决策问题动态规划简介动态规划研究对象——多阶段决策问题。多阶段决策问题：一类活动过程可以分为若干个相互联系的阶段，每个阶段都要做出一个决策，这个决策即决定了本阶段的效益，也决定了下一阶段的初始状态。当每一个阶段的决策确定后，就得到一个决策序列，称为策略。多阶段决策问题就是求一个策略，使各个阶段的效益总和达到最优。§5.1最优化原理多阶段决策问题实例多阶段决策问题的基本

2、特征递推法求解最短线路问题最优化原理从A地到D地要铺设一条煤气管道,其中需经过两级中间站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线，使总距离最短？AB1B2C1C2C3D24333321114状态A决策阶段1状态B1阶段2决策状态D状态C3阶段3决策行程1行程2行程31多阶段决策问题实例（1）1多阶段决策问题实例（2）共有数量x的某种资源，投入两种生产方式A和B:以y投入生产方式A,得到收入g(y),资源的回收率a,则回收ay;以x-y投入生产方式B,得到收入h(x-y),资源的回收率为b,则回收b(x-y);第一阶段结束后，得

3、到的总收入为g(y)+h(x-y),回收的总资源为x1=ay+b(x-y);以数量y1和x1-y1分别再投入生产方式A和B,则第二阶段可得到总收入g(y1)+h(x1-y1);回收总资源x2=ay1+b(x1-y1);两阶段的总收入为g(y)+h(x-y)+g(y1)+h(x1-y1)；以上过程重复n次，希望求出合适的y,y1,…yn-1,使得n个阶段的总收入最大；问题的数学模型为：状态S1决策第一次阶段1状态S2第二次阶段2决策状态Sn-1状态S3第n次阶段n决策收益1收益2收益n1多阶段决策问题实例（2）某工厂制定某种季节性商品的生产计划，假定

4、全年共有6个生产周期，每个周期的市场需求如下表：周期123456需求551030508生产计划受到的限制：若仅日班生产,每周期生产15单位,成本100元/单位；若日夜两班,则夜班也可以生产15单位,成本120/单位；淡季要存储一些产品,以备旺季销售,存储成本16元/单位/周期，开始时存储为0,年终不再存储。如何制定生产计划，使得总的生产和存储费用最小？1多阶段决策问题实例（3）设第i个周期生产量为xi,存储量为ui,则问题的数学模型为：总生产费用总储存费用每一周期的生产量和上一周期的存储量之和等于本周期的销售量和存储量之和日夜生产的总产量限制其中：

5、某个系统可以分为若干个阶段，在阶段k，系统的状态用sk表示；在每一个状态sk都有一个决策集合；在sk的决策集合中选定一个决策,系统的状态就转移到新的阶段sk+1,并且得到效益；决策的目的就是在每一个阶段的决策集合中选取一个决策，从而形成了一个策略，使得所有阶段的总效益最优。2多阶段决策问题的基本特征3递推法求解最短线路问题AB1B2C1C2C3D24333321114几个符号：n—起点到终点的阶段数；k—某点到终点的阶段数；s—状态变量；xk(s)—决策变量；fk(s)—在s点上还有k个阶段，到终点的最短距离；d(s,xk(s))—s点到xk(s)

6、点的距离。AB1B2C1C2C3D24333321114给定决策序列（称为策略）如果是最优的，那么从最后k个阶段开始，最优策略的最后的k个决策，就是后k个阶段组成的k阶段问题的最优策略(最优策略的子策略是最优的)。3最优化原理3最优化原理ACBA到C的最短路B到C的最短路后向递推法A0A1B1A2B2C2A3D2B3C3A4B4C4A5B5A653236871668353384222133355266433最优化原理§5.2确定性的定期多阶段问题什么叫确定性定期多阶段决策问题？不含随机变量，且给定阶段数的多阶段决策问题旅行售货员问题多阶段资源分配

7、问题非线性规划问题排序问题1旅行售货员问题某网络共有4个顶点，已知各个顶点之间的路程dij如下表，求从v1出发经过v2v3v4各一次，再返回到v1的最短路程和最短线路。v1v2v3v4v10856v26085v37905v49780v4到v2的距离v2到v4的距离问题特征：由于走过的点不需要再走，所以在每一个点的决策集合和以前的决策有关；(vi,V)表示状态，其中vi表示所处的点，V是还没有经过的点的集合；当从V中选取一个决策vj,获得的收益是vi到vj的距离dij,并且转入下一个状态(vj,V{vj});fk(vi,V)表示从vi出发，经过V中

8、的点各一次，最后回到v0点的最短路程，其中V中的点的数量为k;1旅行售货员问题根据后向最优化原理：已经经过了全部的点，现在