文档介绍：62338357(O)yuyingzhao@运筹学千里之外决胜帷幄之中运筹主讲教师赵玉英北京林业大学理学院第5章动态规划多阶段决策问题最优化原理确定性的定期多阶段决策问题§,其中需经过两级中间站,两点之间的连线上的数字表示距离,如图所示。问应该选择什么路线,使总距离最短?AB1B2C1C2C3D24333321114状态x1决策阶段1状态x2阶段2决策状态x4状态x3阶段3决策行程1行程2行程31多阶段决策问题实例(1)1多阶段决策问题实例(2)今有1000台机床,要投放到两个生产部门,计划连续使用5年,已知对A部门投入uA台机器的年收益为g(uA)=uA2机器完好率a=;相应的B部门分别为h(uB)=2uA2,机器完好率b=。试建立5年间总收益最大的机器分配方案。问题的数学模型为:状态x1决策第一次阶段1状态x2第二次阶段2决策状态x5状态x3第五次阶段5决策收益1收益2收益51多阶段决策问题实例(2)某工厂制定某种季节性商品的生产计划,假定全年共有6个生产周期,每个周期的市场需求如下表:周期123456需求551030508生产计划受到的限制:若仅日班生产,每周期生产15单位,成本100元/单位;若日夜两班,则夜班也可以生产15单位,成本120/单位;淡季要存储一些产品,以备旺季销售,存储成本16元/单位/周期,开始时存储为0,年终不再存储。如何安排生产和存储计划使总费用最小?1多阶段决策问题实例(3)设第i个周期生产量为xi,存储量为ui,则问题的数学模型为:总生产费用总储存费用每一周期的生产量和上一周期的存储量之和等于本周期的销售量和存储量之和日夜生产的总产量限制其中:1多阶段决策问题实例(4)有一个系统,可以分成若干个阶段,任一个阶段k系统的状态可以用xk表示。在每一阶段k的每一状态xk都有一个决策集合Qk(xk),在决策集合Qk(xk)中选定一个决策qk∈Qk(xk),状态xk就转移到新的状态xk+1=Tk(xk,qk),并且得到收益Rk(xk,qk)阶段。我们的目的就是在每一个阶段都在它的决策集合中选择一个决策,使得所有阶段的总效益∑Rk(xk,qk)达到最优。称之为多阶段决策问题。多阶段决策问题的基本要素:阶段数、状态变量、决策变量、状态转移方程、目标函数等。