运筹与决策5动态规划.ppt

《运筹与决策5动态规划.ppt》由会员分享，可在线阅读，更多相关《运筹与决策5动态规划.ppt（56页珍藏版）》请在装配图网上搜索。

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

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

3、表示该阶段的最优决策 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.

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

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

6、 由阶段效果递推公式有：f3(1,10)=d3(1,10)+f2*(4,8) =21+7210+1104=1826 得第三阶段最优决策表，如下,第三阶段最优决策表,第四阶段：初始库存量 s4=0 由状态转移方程： s3=s4+x460 可知 x46，由阶段效果递推公式有：f4(0,6)=d4(0,6)+f3*(0,10) =706+1902=2322 得第四阶段最优决策表，如下,回 溯 得 此 表,例2 生产库存管理问题(连续变量),设某厂计划全年生产某种产品A。其四个季度的订货量分别为600公斤，700公斤，500公斤和1200公斤。已知生产产品A的生产费用与产品的平方成正比，系数为0.00

7、5。厂内有仓库可存放产品，存储费为每公斤每季度1元。求最佳的生产安排使年总成本最小。 解：四个季度为四个阶段，采用阶段编号与季度顺序一致。 设 sk 为第k季初的库存量，则边界条件为 s1=s5=0 设 xk 为第k季的生产量，设 yk 为第k季的订货量； sk ，xk ，yk 都取实数，状态转移方程为 sk+1=sk+xk - yk 仍采用反向递推，但注意阶段编号是正向的 目标函数为,例2 生产库存管理问题(连续变量),第一步：(第四季度) 总效果 f4(s4,x4)=0.005 x42+s4 由边界条件有： s5= s4 + x4 y4=0，解得：x4*=1200 s4 将x4*代入 f4

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

9、、三、四季度) 总效果 f1(s1,x1)=0.005 x12+s1+ f2*(s2) 将 s2= s1 + x1 600= x1 600 代入 f1(s1,x1) 得：,由此回溯：得最优生产库存方案 x1*=600，s2*=0； x2*=700，s3*=0； x3*=800，s4*=300； x4*=900。,5.2.2 资源分配问题,例3 某公司有9个推销员在全国三个不同市场推销货物，这三个市场里推销人员数与收益的关系如下表，试作出使总收益最大的分配方案。,解：设分配人员的顺序为市场1, 2, 3，采用反向阶段编号。 设 sk 为第k阶段尚未分配的人员数，边界条件为 s3=9 设 xk 为

10、第k阶段分配的推销人员数；仍采用反向递推， 状态转移方程为 sk1=sk xk 目标函数为,例3 第一阶段：给第三市场分配,s1 有09种可能，第一阶段最优决策表如下：,为什么与例1 的第一阶段的表有差别？,因为不存在边界条件 s0=0,例3 第二阶段：给第二市场分配,s2 有09种可能，第二阶段最优决策表如下：,例3 第三阶段：给第一市场分配,由边界条件 s3=9，第三阶段最优决策表如下：,得决策过程：x3*=2, x2*=0, x1*=7, f3*=218 即 市场1 分配 2人，市场2 不分配 ，市场3 分配 7人 最优解与分配的顺序有关吗？,5.2.2 资源分配问题,例4 项目选择问题

11、 某工厂预计明年有A,B,C,D四个新建项目，每个项目的投资额 wk及其投资后的收益 vk如右表所示。投资总额为30万元，问如何选择项目才能使总收益最大。 上述问题的静态规划模型如下：,这是一类0-1规划问题 该问题是经典的旅行背包问题 (Knapsack) 该问题是 NP-complete,例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

12、= sk wk xk 5、直接效益 dk(sk ,xk)= vk 或 0 6、总效益递推公式,该问题的难点在于各阶段的状态的确定，当阶段增加时，状态数成指数增长。下面利用决策树来确定各阶段的可能状态。,例4 第一阶段(项目D)的选择过程,s18 时，x1只能取0；w1=8, v1=5,例4 第二阶段(项目C)的选择过程,例4 第三阶段(项目B)的选择过程,第四阶段(项目A)的选择过程,5.2.3 串联系统可靠性问题,例5 有 A, B, C 三部机器串联生产某种产品，由于工艺技术问题，产品常出现次品。统计结果表明，机器 A, B, C 产生次品的概率分别为 pA=30%, PB=40%, PC

13、=20%, 而产品必须经过三部机器顺序加工才能完成。为了降低产品的次品率，决定拨款 5 万元进行技术改造，以便最大限度地提高产品的成品率指标。现提出如下四种改进方案： 方案1: 不拨款，机器保持原状； 方案2: 加装监视设备，每部机器需款 1 万元； 方案3: 加装设备，每部机器需款 2 万元； 方案4: 同时加装监视及控制设备，每部机器需款 3 万元； 采用各方案后，各部机器的次品率如下表。,例5 串联机器可靠性问题,解：为三台机器分配改造拨款，设拨款顺序为A, B, C，阶段序号反向编号为 k，即第一阶段计算给机器 C 拨款的效果。 设 sk 为第 k 阶段剩余款，则边界条件为 s3=5；

14、 设 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),第二阶段最优决策表,第二阶段 ：对机器 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 得第二阶段最优决策表,第二阶段最优决策表,第三阶段 ：对

15、机器 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=0.648 II：x3=2, x2=2, x1=1, R3= 0.90.80.9=0.648 III: x3=2, x2=3, x1=0, R3= 0.90.90.8 =0.648,例6 用动态规划解非线性规划,解: 这是一个资源分配问题。设分配次序为x1,

16、x2, x3，阶段正向编号，但逆向递推，由约束条件可得边界条件 s1=27, s4=0。 第三阶段：（给 x3分配）,由边界条件和状态转移方程有：s4=s3x3=0，即 x3*= s3；因此有，,第二阶段：（给 x2分配）,由状态转移方程有：s3=s2x2，代入上式得，,例6 用动态规划解非线性规划,第一阶段：（给 x1分配）,由状态转移方程有：s2=s1x1=27 x1 ，代入上式得，,动态规划总结,二大类：生产-库存问题；资源分配问题,动态规划（二）,最短路径问题 资源分配问题,hk 是一般表达形式，求当前阶段当前状态下的阶段最优总效果 (1) 如最短路问题，是累加形式，此时有,终端的边际

17、效果一般为 f0(s0, x0)=0 (2)如串联系统可靠性问题，是连乘形式，此时有,终端的边际效果一般为 f0(s0,x0)=1 从第1阶段开始，利用边际效果和边界条件，可以递推到最后阶段,一、最短路径问题,求从A到E的最短路径,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f5(E)=0,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D1)=5,f5(E)=0,2,5,1,1

18、2,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f4(D1)=5,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C1)=8,f4(D1)=5,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f

19、3(C2)=7,f4(D1)=5,f3(C1)=8,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f3(C1)=8,f3(C2)=7,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B1)=20,f3(C2)=7,f3(C1)=8,2,5,

20、1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B2)=14,f3(C2)=7,f3(C1)=8,f2(B1)=21,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f2(B1)=21,f2(B

21、2)=14,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=21,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(

22、C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=21,状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态,A （ A，B2） B2,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=21,状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态,A （

23、A，B2） B2 （B2，C1） C1,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=21,状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态,A （ A，B2） B2 （B2，C1） C1 （C1，D1） D1,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,

24、10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=21,状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态,A （ A，B2） B2 （B2，C1） C1 （C1，D1） D1 （D1，E） E 从A到E的最短路径为19，路线为AB 2C1 D1 E,例. 有资金4万元，投资A、B、C三个项目，每个项目的投资效益与投入该项目的资金有关。三个项目A、B、C的投资效益（万吨）和投入资

25、金（万元）关系见下表：,求对三个项目的最优投资分配，使总投资效益最大。,二、资源分配问题,4万元,2万元,1万元,0万元,4万元,2万元,1万元,0万元,4万元,2万元,1万元,0万元,4万元,x1A项目 x2B项目 x3C项目 x4,3万元,3万元,3万元,0,f,阶段k：每投资一个项目作为一个阶段； 状态变量xk：投资第k个项目前的资金数； 决策变量dk：第k个项目的投资； 决策允许集合：0dkxk 状态转移方程：xk+1=xk-dk 阶段指标：vk(xk,dk)见表中所示； 递推方程：fk(xk)=maxvk(xk,dk)+fk+1(xk+1) 终端条件：f4(x4)=0,k=4，f4(x4)=0k=3，0d3x3，x4=x3-d3,k=2，0d2x2，x3=x2-d2,k=1，0d1x1，x2=x1-d1,