动态规划运筹学基础及其应用胡运权第五版14718.pptx

《动态规划运筹学基础及其应用胡运权第五版14718.pptx》由会员分享，可在线阅读，更多相关《动态规划运筹学基础及其应用胡运权第五版14718.pptx（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第五章 动态规划1动态规划 Dynamic programming 五十年代贝尔曼(B.E.Bellman)为代表的研究成果 属于现代控制理论的一部分 以长远利益为目标的一系列决策 最优化原理，可归结为一个递推公式5.1 动态规划的最优化原理及其算法5.1.1 求解多阶段决策过程的方法例5.1.1 最短路问题2 决策树法可以枚举出20条路径，其中最短的路径长度为163 例5.1.1 最短路问题 表现为明显的阶段性 一条从A 到B 的最短路径中的任何一段都是最短的 最优性原理“最优策略的一部分也是最优的”每步的决策只与相邻阶段状态有关，而与如何达到这一状态无关因此我们可以从B向回搜索最短路标记法

2、如何找出最短路径4 5.1.2 动态规划的基本概念及递推公式 状态(每阶段初始的出发点)最短路问题中，各个节点就是状态 生产库存问题中，库存量是状态 物资分配问题中，剩余的物资量是状态 控制变量(决策变量)最短路问题中，走哪条路 生产库存问题中，各阶段的产品生产量 物资分配问题中，分配给每个地区的物资量 阶段的编号与递推的方向 一般采用反向递推，所以阶段的编号也是逆向的 当然也可以正向递推5 动态规划的步骤1、确定问题的阶段和编号2、确定状态变量 用 Sk 表示第 k 阶段的状态变量及其值3、确定决策变量 用 xk 表示第 k 阶段的决策变量，并以 xk*表示该阶段的最优决策4、状态转移方程

3、sk-1=g(sk,xk)反向编号 sk+1=g(sk,xk)正向编号 5、直接效果 直接一步转移的效果 dk(sk,xk)6、总效果函数 指某阶段某状态下到终端状态的总效果，它是一个递推公式6 动态规划的步骤 hk 是一般表达形式，求当前阶段当前状态下的阶段最优总效果(1)如最短路问题，是累加形式，此时有终端的边际效果一般为 f0(s0,x0)=0(2)如串联系统可靠性问题，是连乘形式，此时有终端的边际效果一般为 f0(s0,x0)=1从第1阶段开始，利用边际效果和边界条件，可以递推到最后阶段 75.2 动态规划模型举例 5.2.1 产品生产计划安排问题 例1 某工厂生产某种产品的月生产能力

4、为10件，已知今后四个月的产品成本及销售量如表所示。如果本月产量超过销售量时，可以存储起来备以后各月销售，一件产品的月存储费为2元，试安排月生产计划并做到：1、保证满足每月的销售量，并规定计划期初和期末库存为零；2、在生产能力允许范围内，安排每月生产量计划使产品总成本(即生产费用加存储费)最低。8 例1 产品生产计划安排 设xk为第k阶段生产量，则有直接成本 dk(sk,xk)=ck xk+2sk 状态转移公式为 sk-1=sk+xk-yk 总成本递推公式第一阶段：(即第4月份)由边界条件和状态转移方程 s0=s1+x1y1=s1+x16=0 得 s1+x1=6 或 x1=6 s10估计第一阶

5、段，即第4月份初库存的可能状态：0 s1 306712=5，所以，s1 0,59第一阶段最优决策表第二阶段：最大可能库存量 7 件由状态转移方程：s1=s2+x2120 及 x210，可知 s22,7，min x2=5由阶段效果递推公式有：f2(2,10)=d2(2,10)+f1*(0,6)=2 2+80 10+456=1260得第二阶段最优决策表，如下10第二阶段最优决策表第三阶段：最大可能库存量 4 件由状态转移方程：s2=s3+x372 及 x310，可知 s30,4，min x3=5由阶段效果递推公式有：f3(1,10)=d3(1,10)+f2*(4,8)=2 1+7210+1104=

6、1826得第三阶段最优决策表，如下11第三阶段最优决策表第四阶段：初始库存量 s4=0由状态转移方程：s3=s4+x460 可知 x46，由阶段效果递推公式有：f4(0,6)=d4(0,6)+f3*(0,10)=706+1902=2322得第四阶段最优决策表，如下回溯得此表12 例2 生产库存管理问题(连续变量)设某厂计划全年生产某种产品A。其四个季度的订货量分别为600公斤，700公斤，500公斤和1200公斤。已知生产产品A的生产费用与产品的平方成正比，系数为0.005。厂内有仓库可存放产品，存储费为每公斤每季度1元。求最佳的生产安排使年总成本最小。解：四个季度为四个阶段，采用阶段编号与季

7、度顺序一致。设 sk 为第k季初的库存量，则边界条件为 s1=s5=0 设 xk 为第k季的生产量，设 yk 为第k季的订货量；sk，xk，yk 都取实数，状态转移方程为 sk+1=sk+xk-yk 仍采用反向递推，但注意阶段编号是正向的 目标函数为13例2 生产库存管理问题(连续变量)第一步：(第四季度)总效果 f4(s4,x4)=0.005 x42+s4 由边界条件有：s5=s4+x4 y4=0，解得：x4*=1200 s4 将x4*代入 f4(s4,x4)得：f4*(s4)=0.005(1200 s4)2+s4=7200 11 s4+0.005 s42第二步：(第三、四季度)总效果 f3

8、(s3,x3)=0.005 x32+s3+f4*(s4)将 s4=s3+x3 500 代入 f3(s3,x3)得：14 例2 生产库存管理问题(连续变量)第三步：(第二、三、四季度)总效果 f2(s2,x2)=0.005 x22+s2+f3*(s3)将 s3=s2+x2 700 代入 f2(s2,x2)得：注意：阶段最优总效果仅是当前状态的函数，与其后的决策无关15 例2 生产库存管理问题(连续变量)第四步：(第一、二、三、四季度)总效果 f1(s1,x1)=0.005 x12+s1+f2*(s2)将 s2=s1+x1 600=x1 600 代入 f1(s1,x1)得：由此回溯：得最优生产库存

9、方案 x1*=600，s2*=0；x2*=700，s3*=0；x3*=800，s4*=300；x4*=900。16 5.2.2 资源分配问题例3 某公司有9个推销员在全国三个不同市场推销货物，这三个市场里推销人员数与收益的关系如下表，试作出使总收益最大的分配方案。解：设分配人员的顺序为市场1,2,3，采用反向阶段编号。设 sk 为第k阶段尚未分配的人员数，边界条件为 s3=9 设 xk 为第k阶段分配的推销人员数；仍采用反向递推，状态转移方程为 sk1=sk xk 目标函数为17 例3 第一阶段：给第三市场分配 s1 有09种可能，第一阶段最优决策表如下：为什么与例1 的第一阶段的表有差别？因

10、为不存在边界条件 s0=018 例3 第二阶段：给第二市场分配 s2 有09种可能，第二阶段最优决策表如下：19 例3 第三阶段：给第一市场分配 由边界条件 s3=9，第三阶段最优决策表如下：得决策过程：x3*=2,x2*=0,x1*=7,f3*=218 即 市场1 分配 2人，市场2 不分配，市场3 分配 7人最优解与分配的顺序有关吗？20 5.2.2 资源分配问题例4 项目选择问题 某工厂预计明年有A,B,C,D四个新建项目，每个项目的投资额 wk及其投资后的收益 vk如右表所示。投资总额为30万元，问如何选择项目才能使总收益最大。上述问题的静态规划模型如下：这是一类0-1规划问题 该问题

11、是经典的旅行背包问题(Knapsack)该问题是 NP-complete21 例4 项目选择问题解：设项目选择的顺序为A,B,C,D;1、阶段 k=1,2,3,4 分别对应 D,C,B,A项目的选择过程2、第 k 阶段的状态 sk，代表第 k 阶段初尚未分配的投资额3、第 k 阶段的决策变量 xk,，代表第 k 阶段分配的投资额4、状态转移方程为 sk1=sk wk xk5、直接效益 dk(sk,xk)=vk 或 06、总效益递推公式 该问题的难点在于各阶段的状态的确定，当阶段增加时，状态数成指数增长。下面利用决策树来确定各阶段的可能状态。2223 例4 第一阶段(项目D)的选择过程 s18

12、时，x1只能取0；w1=8,v1=524例4 第二阶段(项目C)的选择过程25 例4 第三阶段(项目B)的选择过程第四阶段(项目A)的选择过程26 5.2.3 串联系统可靠性问题例5 有 A,B,C 三部机器串联生产某种产品，由于工艺技术问题，产品常出现次品。统计结果表明，机器 A,B,C 产生次品的概率分别为 pA=30%,PB=40%,PC=20%,而产品必须经过三部机器顺序加工才能完成。为了降低产品的次品率，决定拨款 5 万元进行技术改造，以便最大限度地提高产品的成品率指标。现提出如下四种改进方案：方案1:不拨款，机器保持原状；方案2:加装监视设备，每部机器需款 1 万元；方案3:加装设

13、备，每部机器需款 2 万元；方案4:同时加装监视及控制设备，每部机器需款 3 万元；采用各方案后，各部机器的次品率如下表。27 例5 串联机器可靠性问题解：为三台机器分配改造拨款，设拨款顺序为A,B,C，阶段序号反向编号为 k，即第一阶段计算给机器 C 拨款的效果。设 sk 为第 k 阶段剩余款，则边界条件为 s3=5；设 xk 为第 k 阶段的拨款额；状态转移方程为 sk-1=sk-xk；目标函数为 max R=(1-PA)(1-PB)(1-PC)仍采用反向递推第一阶段：对机器 C 拨款的效果 R1(s1,x1)=d1(s1,x1)R0(s0,x0)=d1(s1,x1)28第二阶段最优决策表

14、第二阶段：对机器 B,C 拨款的效果 由于机器 A 最多只需 3 万元，故 s2 2 递推公式：R2(s2,x2)=d2(s2,x2)R1(s1,x1*)例：R2(3,2)=d2(3,2)R1(1,1)=(1-0.2)0.9=0.72 得第二阶段最优决策表29第二阶段最优决策表第三阶段：对机器 A,B,C 拨款的效果 边界条件：s3=5 递推公式：R3(s3,x3)=d3(s3,x3)R2(s2,x2*)例：R3(5,3)=d3(5,3)R2(2,2)=(1-0.05)0.64=0.608 得第三阶段最优决策表回溯：有多组最优解。I：x3=1,x2=3,x1=1,R3=0.8 0.9 0.9=

15、0.648 II：x3=2,x2=2,x1=1,R3=0.90.80.9=0.648III:x3=2,x2=3,x1=0,R3=0.90.90.8=0.64830 例6 用动态规划解非线性规划解:这是一个资源分配问题。设分配次序为x1,x2,x3，阶段正向编号，但逆向递推，由约束条件可得边界条件 s1=27,s4=0。第三阶段：（给 x3分配）由边界条件和状态转移方程有：s4=s3x3=0，即 x3*=s3；因此有，第二阶段：（给 x2分配）由状态转移方程有：s3=s2x2，代入上式得，31 例6 用动态规划解非线性规划第一阶段：（给 x1分配）由状态转移方程有：s2=s1x1=27 x1，代入上式得，32动态规划总结 二大类：生产-库存问题；资源分配问题33谢谢观看/欢迎下载BY FAITH I MEAN A VISION OF GOOD ONE CHERISHES AND THE ENTHUSIASM THAT PUSHES ONE TO SEEK ITS FULFILLMENT REGARDLESS OF OBSTACLES.BY FAITH I BY FAITH