运筹学 第八、九章 动态规划 建立动态规划模型的步骤 1、划分阶段 划分阶段是运用动态规划求解多阶段决策问题的第一 步,在确定多阶段特性后,按时间或空间先后顺序, 将过程划分为若干相互联系的阶段。对于静态问题要 人为地赋予“时间”概念,以便划分阶段。 2、正确选择状态变量S k 选择变量既要能确切描述过程演变又要满足无后效性 ,而且各阶段状态变量的取值能够确定。一般地,状 态变量的选择是从过程演变的特点中寻找。 3、确定决策变量U k 及允许决策集合D k 通常选择所求解问题的关键变量作为决策变量,同时 要给出决策变量的取值范围,即确定允许决策集合。 1 第八章 动态规划运筹学 第八、九章 动态规划 4、确定状态转移方程S k+1 =T k (S k ,U k ) 根据k 阶段状态变量和决策变量,写出k+1阶段状态变量 ,状态转移方程应当具有递推关系。 5、正确写出指标函数V k,n 的关系,它应满足下面三个 性质: V k,n 是定义在全过程和所有后部子过程上的数量函数 具有可分离性,并满足递推关系,即V k,n (S k ,U k ,S k 1 ,S n+1 )= k (S k ,