第四章 动态规划模型08-6.ppt

第四章 动态规划 动态规划 Dynamic programming 五十年代贝尔曼(B. E. Bellman)为代表的研究成果 属于现代控制理论的一部分 主要用于解决多阶段决策问题 最优性原理，可归结为一个递推公式 决策树法 分析决策过程： 动态规划方法：反向找出各点到终点的最短路径 计算量：2 乘9+6=24次加，9次比较. 4. 2 动态规划模型的基本结构 4. 2. 1 动态规划的基本概念 阶段(用k表示) 状态(每阶段初始的出发点)与状态变量（用sk表示） 最短路问题中，各个节点就是状态 生产库存问题中，库存量是状态 物资分配问题中，剩余的物资量是状态 决策与决策变量(用dk(sk)表示) 最短路问题中，走哪条路 生产库存问题中，各阶段的产品生产量 物资分配问题中，分配给每个地区的物资量 阶段的编号与递推的方向 一般采用反向递推，而阶段的编号为正向 当然也可以正向递推 状态转移与状态转移方程 系统由这一阶段的一个状态转变到下一阶段的另一个状态称为状态转移 状态转移方程用于描述状态转移关系，它与状态、决策均有关 策略与（后部）子策略 阶段指标 对过程中某一个阶段的决策效果衡量其优劣的数量指标。记为vk(sk,dk(sk)) 指标函数与最优指标函数 4. 2. 2 最优性原理和基本递推公式 1. 最优性原理 最优策略的一部分也是最优的. 每步的决策只与相邻阶段状态有关，而与如何达到这一状态无关. 无后效性 2. 基本递推公式 正向编号 状态转移方程 sk+1= g(sk, xk) 指标函数 :表示从第 k 阶段的状态变量sk开始，在决策序 列 xk， xk+1，….， xn 之下，得到的指标函数值. 在最优决策序列 xk* ，xk+1*，……， xn*之下， 反向编号 状态转移方程 sk-1= g(sk, xk) 指标函数 基本递推公式 4.3 动态规划的步骤 1、确定问题的阶段和编号 2、确定状态变量和取值范围 用 Sk 表示第 k 阶段的状态变量及其值 3、确定决策变量和取值范围 用 xk 表示第 k 阶段的决策变量，并以 xk*表示该阶段的最优决策 4、状态转移方程 sk+1= g(sk, xk) 正向编号 sk-1= g(sk, xk) 反向编号 5、阶段指标函数（直接效果） 直接一步转移的效果 vk(sk, xk) 6、总效果函数 - 基本递推公式 指某阶段某状态下到终端状态的总效果，它是一个递推公式 4.3 动态规划的步骤 hk 是一般表达形式，求当前阶段当前状态下的阶段最优总效果 (1) 如最短路问题，是累加形式，此时有 4.4 动态规划模型举例 4.4.1 产品生产计划安排问题 例4.4.1 某工厂生产某种产品的月生产能力为10件，已知今后四个月的产品成本及销售量如表所示。如果本月产量超过销售量时，可以存储起来备以后各月销售，一件产品的月存储费为2元，试安排月生产计划并做到： 1、保证满足每月的销售量，并规定计划期初和期末库存为零； 2、在生产能力允许范围内，安排每月生产量计划使产品总成本(即生产费用加存储费)最低。 例4.4.1 产品生产计划安排 设xk为第k阶段生产量，则有直接成本 vk(sk, xk)= ck xk+2sk 状态转移公式为 sk+1= sk+ xk- yk 总成本递推公式 第4阶段最优决策表 第3阶段：最大可能库存量 7 件 由状态转移方程： s4=s3+x3?12?0 及 x3?10，可知 s3?[2,7]，min x3=5 由阶段效果递推公式有：f3(2,10)=v3(2,10)+f4*(0,6) =2?2+80?10+456=1260 得第3阶段最优决策表，如下 第3阶段最优决策表 第2阶段：最大可能库存量 4 件 由s3=s2+x2?7?2 , s3 ?7 及 x2?10，可知 s2?[0,4]，min x2=5 由阶段效果递推公式有：f2(1,10)=v2(1,10)+f3*(4,8) =2?1+72?10+1104=1826 得第2阶段最优决策表，如下 第