动态规划2.ppt

文档介绍：生产-库存问题
产品仓库容量H=9。期初库存量为2,要求期末(七月底)库存量为0。每个月生产的产品在月末入库。求最优生产计划xk
分析处理方法
静态处理——线性(整数)规划
动态处理——动态规划
生产-库存问题的动态结构
阶段最优与总体最优之间的非一致性
每一阶段的最优决策未必能保证总体最优
总体最优并不能保证每一阶段最优
能否通过阶段决策达到总体最优目标?
在什么条件下总体最优包含了阶段最优?
一般多阶段决策问题的结构
Sj : j阶段初系统所处状态
Xj:j阶段所作决策
vj(Sj, Xj): j阶段在状态Sj下作决策Xj得到的收益(成本)
阶段和阶段变量
为了便于求解和表示决策及过程的发展顺序,而把所给问题恰当地划分为若干个相互联系又有区别的子问题,称之为多段决策问题的阶段。一个阶段,就是需要作出一个决策的子问题,通常,阶段是按决策进行的时间或空间上先后顺序划分的。用以描述阶段的变量叫作阶段变量,。
状态、状态变量
状态与状态变量。用以描述事物(或系统)在某特定的时间与空间域中所处位置及运动特征的量,称为状态。反映状态变化的量叫做状态变量。状态变量必须包含在给定的阶段上确定全部允许决策所需要的信息。按照过程进行的先后,每个阶段的状态可分为初始状态和终止状态,或称输入状态和输出状态,阶段k的初始状态记作sk,终止状态记为sk+1。但为了清楚起见,通常定义阶段的状态即指其初始状态。
允许状态集合
——每一阶段可能初始状态的全体
决策、决策变量
决策的实质是关于状态的选择,是决策者从给定阶段状态出发对下一阶段状态作出的选择。
用以描述决策变化的量称之决策变量。决策变量的值可以用数,向量、其它量,也可以是状态变量的函数,记以xk= xk(sk),表示于阶段k状态sk时的决策变量。
决策变量的取值往往也有一定的允许范围,称之允许决策集合。决策变量xk(sk)的允许决策集用Dk(sk)表示, xk(sk) ∈ Dk(sk)允许决策集合实际是决策的约束条件。
决策集合(空间)
——每一阶段决策变量的允许取值空间