运筹学第05章北邮.ppt

* 例6 用动态规划解非线性规划 解: 这是一个资源分配问题。设分配次序为x1, x2, x3，阶段正向编号，但逆向递推，由约束条件可得边界条件 s1=27, s4=0。 第三阶段：（给 x3分配） 由边界条件和状态转移方程有：s4=s3?x3=0，即 x3*= s3；因此有， 第二阶段：（给 x2分配） 由状态转移方程有：s3=s2?x2，代入上式得， * 例6 用动态规划解非线性规划 第一阶段：（给 x1分配） 由状态转移方程有：s2=s1?x1=27 ?x1 ，代入上式得， * 动态规划总结 二大类：生产-库存问题；资源分配问题 第五章 动态规划 不要过河拆桥 * 动态规划 Dynamic programming 五十年代贝尔曼(B. E. Bellman)为代表的研究成果 属于现代控制理论的一部分 以长远利益为目标的一系列决策 最优化原理，可归结为一个递推公式 5.1 动态规划的最优化原理及其算法 5.1.1 求解多阶段决策过程的方法 例5.1.1 最短路问题 * 决策树法 可以枚举出20条路径，其中最短的路径长度为16 * 例5.1.1 最短路问题 表现为明显的阶段性 一条从A 到B 的最短路径中的任何一段都是最短的 最优性原理 “最优策略的一部分也是最优的” 每步的决策只与相邻阶段状态有关，而与如何达到这一状态无关 因此我们可以从B向回有哪些信誉好的足球投注网站最短路 标记法 如何找出最短路径 * 5.1.2 动态规划的基本概念及递推公式 状态(每阶段初始的出发点) 最短路问题中，各个节点就是状态 生产库存问题中，库存量是状态 物资分配问题中，剩余的物资量是状态 控制变量(决策变量) 最短路问题中，走哪条路 生产库存问题中，各阶段的产品生产量 物资分配问题中，分配给每个地区的物资量 阶段的编号与递推的方向 一般采用反向递推，所以阶段的编号也是逆向的 当然也可以正向递推 * 动态规划的步骤 1、确定问题的阶段和编号 2、确定状态变量 用 Sk 表示第 k 阶段的状态变量及其值 3、确定决策变量 用 xk 表示第 k 阶段的决策变量，并以 xk*表示该阶段的最优决策 4、状态转移方程 sk-1= g(sk, xk) 反向编号 sk+1= g(sk, xk) 正向编号 5、直接效果 直接一步转移的效果 dk(sk, xk) 6、总效果函数 指某阶段某状态下到终端状态的总效果，它是一个递推公式 * 动态规划的步骤 hk 是一般表达形式，求当前阶段当前状态下的阶段最优总效果 (1) 如最短路问题，是累加形式，此时有 终端的边际效果一般为 f0(s0, x0)=0 (2)如串联系统可靠性问题，是连乘形式，此时有 终端的边际效果一般为 f0(s0,x0)=1 从第1阶段开始，利用边际效果和边界条件，可以递推到最后阶段 * 5.2 动态规划模型举例 5.2.1 产品生产计划安排问题 例1 某工厂生产某种产品的月生产能力为10件，已知今后四个月的产品成本及销售量如表所示。如果本月产量超过销售量时，可以存储起来备以后各月销售，一件产品的月存储费为2元，试安排月生产计划并做到： 1、保证满足每月的销售量，并规定计划期初和期末库存为零； 2、在生产能力允许范围内，安排每月生产量计划使产品总成本(即生产费用加存储费)最低。 * 例1 产品生产计划安排 设xk为第k阶段生产量，则有直接成本 dk(sk, xk)= ck xk+2sk 状态转移公式为 sk-1= sk+ xk- yk 总成本递推公式 第一阶段：(即第4月份) 由边界条件和状态转移方程 s0=s1+x1?y1= s1+x1?6=0 得 s1+x1= 6 或 x1= 6?s1?0 估计第一阶段，即第4月份初库存的可能状态： 0? s1 ? 30?6?7?12=5，所以， s1 ?[0,5] * 第一阶段最优决策表 第二阶段：最大可能库存量 7 件 由状态转移方程： s1=s2+x2?12?0 及 x2?10，可知 s2?[2,7]，min x2=5 由阶段效果递推公式有：f2(2,10)=d2(2,10)+f1*(0,6) =2?2+80?10+456=1260 得第二阶段最优决策表，如下 * 第二阶段最优决策表 第三阶段：最大可能库存量 4 件 由状态转移方程： s2=s3+x3?7?2 及 x3?10，可知 s3?[0,4]，min x3=5 由阶段效果递推公式有：f3(1,10)=d3(1,1