华东理工大学工商经济学院：《运筹学》 动态规划

动 安水利水业步木经院 态 筹 i 规 划 学

Page:1QSC 华东理工大学 工商经济学院 运筹学 运筹学动态规划

生产一库存问题 月份()1234567 生产成本(c)11181317201015 需求量)085327 产品仓库容量H=9。期初库存量为2,要求 期末(七月底)库存量为0。每个月生产的 产品在月末入库。求最优生产计划x

Page:2 QSC 华东理工大学 工商经济学院 运筹学 生产－库存问题 月份(k) 1 2 3 4 5 6 7 生产成本(ck ) 11 18 13 17 20 10 15 需求量(rk ) 0 8 5 3 2 7 4 产品仓库容量H=9。期初库存量为2，要求 期末（七月底）库存量为0。每个月生产的 产品在月末入库。求最优生产计划xk

分析处理方法 ■静态处理——线性(整数)规划 ■动态处理—动态规划

Page:3 QSC 华东理工大学 工商经济学院 运筹学 分析处理方法 静态处理 —— 线性(整数)规划 动态处理 —— 动态规划

生产一库存问题的动态结构 生产量 生产量 生产量x 1月初库彳量 2月初库量 3月初库量 7月初库量 7月底量 SIO 生产立 生 S3 S8=0 系统 系统 系统 决策側 决策側刂 决策側 生产成本cx最小 生产成本cx最小 生产成本cx最小

Page:4 QSC 华东理工大学 工商经济学院 运筹学 生产－库存问题的动态结构 生产 系统 1月初库存量: s1=0 生产量x1 决策准则: 生产成本c1x1最小 生产 系统 2月初库存量: s2 生产量x2 3月初库存量: s3 决策准则: 生产成本c2x2最小 生产 系统 生产量x7 7月底库存量: s8＝0 决策准则: 生产成本c7x7最小 7月初库存量: s7

阶段最优与总体最优之间的非一致性 秦每一阶段的最优决策未必能保证总体最优 秦总体最优并不能保证每一阶段最优 能否通过阶段决策达到总体最优目标? 在什么条件下总体最优包含了阶段最优?

Page:5 QSC 华东理工大学 工商经济学院 运筹学 阶段最优与总体最优之间的非一致性 每一阶段的最优决策未必能保证总体最优 总体最优并不能保证每一阶段最优 能否通过阶段决策达到总体最优目标？ 在什么条件下总体最优包含了阶段最优？

般多阶段决策问题的结构 决策Ⅹ 决策X 决策X 阶段s2阶段S sn阶段|S 2 n 指值 指标值 指值 r(S,) r2S X2) rs Xn S:j阶段初系统所处状态 X1:阶段所作决策 r(S,X:阶段在状态S下作决策X得到的收益(成本

Page:6 QSC 华东理工大学 工商经济学院 运筹学 一般多阶段决策问题的结构 阶段 1 S1 决策X1 指标值 r1(S1, X1) 阶段 2 S2 决策X2 S3 阶段 n 决策Xn Sn-1 Sn 指标值 r2(S2, X2) 指标值 rn(Sn, Xn) Sj : j阶段初系统所处状态 Xj：j阶段所作决策 rj(Sj, Xj): j阶段在状态Sj下作决策Xj得到的收益(成本)

允许状态集合 每一阶段可能初始状态的全体 S S

Page:7 QSC 华东理工大学 工商经济学院 运筹学 允许状态集合 —— 每一阶段可能初始状态的全体 Sj Sj S  , j = 1, 2, , n 1 j 2  , ,  

决策空间 —每一阶段决策变量的允许取值空间 X;(S;)∈D,(S,)

Page:8 QSC 华东理工大学 工商经济学院 运筹学 决策空间 —— 每一阶段决策变量的允许取值空间 X j S j ( )  D ( S ) j j

眷状态变换 每一阶段的初始状态经决策变量的 作用产生下一阶段的初始状态 S1=7(S;,X;)

Page:9 QSC 华东理工大学 工商经济学院 运筹学 状态变换 —— 每一阶段的初始状态经决策变量的 作用产生下一阶段的初始状态 Sj+1  T(Sj Xj , )

壽策略 从初始阶段到最终阶段,每一阶段的 决策所形成的序列 Pn(S1)={X(S1,X2(S2),……,Xn(Sn

Page:10 QSC 华东理工大学 工商经济学院 运筹学 策略 —— 从初始阶段到最终阶段，每一阶段的 决策所形成的序列 P1,n (S1 )  X1 (S1 ), X2 (S2 ), , Xn (Sn )