安檄水水业的查木经院 动态规划 筹 学
Page : 1 QSC 华东理工大学 工商经济学院 运筹学 运筹学 动态规划
生产一库存问题 月份()1234567 生产成本(c)1l181317201015 需求量(n)085327 产品仓库容量H-9。期初库存量为2,要求 期末(七月底)库存量为0。每个月生产的 产品在月末入库。求最优生产计划
Page:2 QSC 华东理工大学 工商经济学院 运筹学 生产-库存问题 月 份(k) 1 2 3 4 5 6 7 生产成本(ck ) 1 1 1 8 1 3 1 7 2 0 1 0 1 5 需求量(rk ) 0 8 5 3 2 7 4 产品仓库容量H=9。期初库存量为2,要求 期末(七月底)库存量为0。每个月生产的 产品在月末入库。求最优生产计划xk
分析处理方法 静态处理——线性(整数)规划 ■动态处理—动态规划
Page:3 QSC 华东理工大学 工商经济学院 运筹学 分析处理方法 静态处理 —— 线性(整数)规划 动态处理 —— 动态规划
生产一库存问题的动态结构 生产量x1 生产量x2 生产量x7 1月初库存量: 2月初库存量 3月初库存量 7月初库存量 7月底库存量 s1=0 生产 生产 S3 生产s=0 系统 系统 系统 决策准则 决策准则 决策准则 生产成本cx1最小 生产成本c2x2最小 生产成本cx7最小
Page:4 QSC 华东理工大学 工商经济学院 运筹学 生产-库存问题的动态结构 生产 系统 1 月初库存量: s1=0 生产量 x1 决策准则: 生产成本 c1x1最小 生产 系统 2 月初库存量: s2 生产量 x2 3 月初库存量: s3 决策准则: 生产成本 c2x2最小 生产 系统 生产量 x7 7 月底库存量: s8= 0 决策准则: 生产成本 c7x7最小 7 月初库存量: s7
阶段最优与总体最优之间的非一致性 秦每一阶段的最优决策未必能保证总体最优 秦总体最优并不能保证每一阶段最优 能否通过阶段决策达到总体最优目标? 在什么条件下总体最优包含了阶段最优?
Page:5 QSC 华东理工大学 工商经济学院 运筹学 阶段最优与总体最优之间的非一致性 每一阶段的最优决策未必能保证总体最优 总体最优并不能保证每一阶段最优 能否通过阶段决策达到总体最优目标? 在什么条件下总体最优包含了阶段最优?
一般多阶段决策问题的结构 决策X1 决策X2 决策Xn S1阶段 阶段 S阶段S 指标值 指标值 指标值 r(S1,X1) 「Sn2Xx) S1:j阶段初系统所处状态 X:j阶段所作决策 r(S,X小阶段在状态S下作决策X得到的收益(成本
Page:6 QSC 华东理工大学 工商经济学院 运筹学 一般多阶段决策问题的结构 阶段 1 S1 决策 X1 指标值 r1 (S1, X1 ) 阶段 2 S2 决策 X2 S3 阶段 n 决策 Xn Sn Sn-1 指标值 r2 (S2, X2 ) 指标值 rn (Sn, Xn ) Sj : j阶段初系统所处状态 Xj:j阶段所作决策 rj (Sj , Xj ): j阶段在状态Sj下作决策Xj得到的收益(成本)
訾允许状态集合 —每一阶段可能初始状态的全体 S:=S . S
Page:7 QSC 华东理工大学 工商经济学院 运筹学 允许状态集合 —— 每一阶段可能初始状态的全体 Sj Sj S , j =1, 2, , n 1 j 2 = , ,
决策空间 每一阶段决策变量的允许取值空间 ;(S;)∈D(S)
Page:8 QSC 华东理工大学 工商经济学院 运筹学 决策空间 —— 每一阶段决策变量的允许取值空间 Xj Sj ( ) D (S ) j j
訾状态变换 每一阶段的初始状态经决策变量的 作用产生下一阶段的初始状态 S#=7(S;,×)
Page:9 QSC 华东理工大学 工商经济学院 运筹学 状态变换 —— 每一阶段的初始状态经决策变量的 作用产生下一阶段的初始状态 Sj+1 = T(Sj Xj , )
策略 从初始阶段到最终阶段,每一阶段的 决策所形成的序列 Pn(S1)=(X,(),X2(S2),.,X,(Sm)
Page:10 QSC 华东理工大学 工商经济学院 运筹学 策略 —— 从初始阶段到最终阶段,每一阶段的 决策所形成的序列 P1,n (S1 ) = X1 (S1 ), X2 (S2 ), , Xn (Sn )