运筹与决策动态规划.pptx

动态规划 Dynamic programming五十年代贝尔曼(B.E.Bellman)为代表的研究成果属于现代控制理论的一部分以长远利益为目标的一系列决策最优化原理，可归结为一个递推公式5.1 动态规划的最优化原理及其算法5.1.1 求解多阶段决策过程的方法例5.1.1 最短路问题第1页/共56页 决策树法决策树法可以枚举出可以枚举出20条路径，其中最短的路径长度为条路径，其中最短的路径长度为16第2页/共56页 例例5.1.1 最短路问题最短路问题表现为明显的阶段性一条从A 到B 的最短路径中的任何一段都是最短的 最优性原理最优性原理“最优策略的一部分也是最优的最优策略的一部分也是最优的”每步的决策只与相邻阶段状态有关，每步的决策只与相邻阶段状态有关，而与如何达到这一状态无关而与如何达到这一状态无关因此我们可以从因此我们可以从B向回搜索最短路向回搜索最短路标记法标记法如何找出最短路径如何找出最短路径第3页/共56页 5.1.2 动态规划的基本概念及递推公式状态(每阶段初始的出发点)最短路问题中，各个节点就是状态生产库存问题中，库存量是状态物资分配问题中，剩余的物资量是状态控制变量(决策变量)最短路问题中，走哪条路生产库存问题中，各阶段的产品生产量物资分配问题中，分配给每个地区的物资量阶段的编号与递推的方向一般采用反向递推，所以阶段的编号也是逆向的当然也可以正向递推第4页/共56页 动态规划的步骤动态规划的步骤1、确定问题的阶段和编号2、确定状态变量用 Sk 表示第 k 阶段的状态变量及其值3、确定决策变量用 xk 表示第 k 阶段的决策变量，并以 xk*表示该阶段的最优决策4、状态转移方程 sk-1=g(sk,xk)反向编号 sk+1=g(sk,xk)正向编号 5、直接效果直接一步转移的效果 dk(sk,xk)6、总效果函数指某阶段某状态下到终端状态的总效果，它是一个递推公式第5页/共56页 动态规划的步骤动态规划的步骤hk 是一般表达形式，求当前阶段当前状态下的阶段最优总效果(1)如最短路问题，是累加形式，此时有终端的边际效果一般为终端的边际效果一般为 f0(s0,x0)=0(2)如串联系统可靠性问题，是连乘形式，此时有如串联系统可靠性问题，是连乘形式，此时有终端的边际效果一般为终端的边际效果一般为 f0(s0,x0)=1从第从第1 1阶段开始，利用边际效果和边界条件，可以递推到最后阶段开始，利用边际效果和边界条件，可以递推到最后阶段阶段第6页/共56页5.2 动态规划模型举例 5.2.1 产品生产计划安排问题 例1 某工厂生产某种产品的月生产能力为10件，已知今后四个月的产品成本及销售量如表所示。如果本月产量超过销售量时，可以存储起来备以后各月销售，一件产品的月存储费为2元，试安排月生产计划并做到：1、保证满足每月的销售量，并规定计划期初和期末库存为零；2、在生产能力允许范围内，安排每月生产量计划使产品总成本(即生产费用加存储费)最低。第7页/共56页 例例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第8页/共56页第一阶段最第一阶段最优决策表优决策表第二阶段：最大可能库存量 7 件由状态转移方程：s1=s2+x2 120 及 x210，可知 s22,7，min x2=5由阶段效果递推公式有：f2(2,10)=d2(2,10)+f1*(0,6)=22+8010+456=1260得第二阶段最优决策表，如下第9页/共56页第二阶段第二阶段最优决策最优决策表表第三阶段：最大可能库存量 4 件由状态转移方程：s2=s3+x3 72 及 x310，可知 s30,4，min x3=5由阶段效果递推公式有：f3(1,10)=d3(1,10)+f2*(4,8)=21+7210+1104=1826得第三阶段最优决策表，如下第10页/共56页第三阶段第三阶段最优决策最优决策表表第四阶段：初始库存量 s4=0由状态转移方程：s3=s4+x460 可知 x46，由阶段效果递推公式有：f4(0,6)=d4(0,6)+f3*(0,10)=706+1902=2322得第四阶段最优决策表，如下回回溯溯得得此此表表第11页/共56页 例例2 生产生产库存管理问题库存管理问题(连续变量连续变量)设某厂计划全年生产某种产品A。其四个季度的订货量分别为600公斤，700公斤，500公斤和1200公斤。已知生产产品A的生产费用与产品的平方成正比，系数为0.005。厂内有仓库可存放产品，存储费为每公斤每季度1元。求最佳的生产安排使年总成本最小。解：四个季度为四个阶段，采用阶段编号与季度顺序一致。设 sk 为第k季初的库存量，则边界条件为 s1=s5=0 设 xk 为第k季的生产量，设 yk 为第k季的订货量；sk，xk，yk 都取实数，状态转移方程为 sk+1=sk+xk-yk 仍采用反向递推，但注意阶段编号是正向的 目标函数为第12页/共56页例例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(s3,x3)=0.005 x32+s3+f4*(s4)将 s4=s3+x3 500 代入 f3(s3,x3)得：第13页/共56页 例例2 生产生产库存管理问题库存管理问题(连续变量连续变量)第三步：(第二、三、四季度)总效果 f2(s2,x2)=0.005 x22+s2+f3*(s3)将 s3=s2+x2 700 代入 f2(s2,x2)得：注意：阶段最优总效果仅是当前状态的函数，与其后的决策无关第14页/共56页 例例2 2 生产生产库存管理问题库存管理问题(连续变连续变量量)第四步：(第一、二、三、四季度)总效果 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。第15页/共56页 5.2.2 5.2.2 资源分配问题资源分配问题例3 某公司有9个推销员在全国三个不同市场推销货物，这三个市场里推销人员数与收益的关系如下表，试作出使总收益最大的分配方案。解解：设分配人员的顺序为市场：设分配人员的顺序为市场1,2,3，采用反向阶段编号。，采用反向阶段编号。设设 sk 为第为第k阶段尚未分配的人员数，边界条件为阶段尚未分配的人员数，边界条件为 s3=9 设设 xk 为第为第k阶段分配的推销人员数；仍采用反向递推，阶段分配的推销人员数；仍采用反向递推，状态转移方程为状态转移方程为 sk1=sk xk 目标函数为目标函数为第16页/共56页 例例3 第一阶段：给第三市场分配第一阶段：给第三市场分配 s1 有09种可能，第一阶段最优决策表如下：为什么与为什么与例例1 的第一阶段的表有差别？的第一阶段的表有差别？因为不存在边界条件因为不存在边界条件 s0=0第17页/共56页 例例3 第二阶段：给第二市场分配第二阶段：给第二市场分配 s2 有09种可能，第二阶段最优决策表如下：第18页/共56页 例例3 第三阶段：给第一市场分配第三阶段：给第一市场分配 由边界条件 s3=9，第三阶段最优决策表如下：得决策过程：得决策过程：x3*=2,x2*=0,x1*=7,f3*=218 即即 市场市场1 分配分配 2人，市场人，市场2 不分配不分配，市场，市场3 分配分配 7人人最优解与分配的顺序有关吗最优解与分配的顺序有关吗？第19页/共56页 5.2.2 资源分配问题例4 项目选择问题 某工厂预计明年有A,B,C,D四个新建项目，每个项目的投资额 wk及其投资后的收益 vk如右表所示。投资总额为30万元，问如何选择项目才能使总收益最大。上述问题的静态规划模型如下：这是一类这是一类0-1规划问题规划问题该问题是经典的该问题是经典的旅行背包问题旅行背包问题(Knapsack)该问题是该问题是 NP-complete第20页/共56页 例例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、总效益递推公式 该问题的难点在于各阶段的状态的确定，当阶段增加时，状该问题的难点在于各阶段的状态的确定，当阶段增加时，状态数成指数增长。下面利用决策树来确定各阶段的可能状态。态数成指数增长。下面利用决策树来确定各阶段的可能状态。第21页/共56页第22页/共56页 例例4 第一阶段第一阶段(项目项目D)的选择过程的选择过程s18 时，x1只能取0；w1=8,v1=5第23页/共56页例例4 4 第二阶段第二阶段(项目项目C)C)的选择过程的选择过程第24页/共56页 例例4 4 第三阶段第三阶段(项目项目B)B)的选择过程的选择过程第四阶段第四阶段(项目项目A)的选择过程的选择过程第25页/共56页 5.2.3 串联系统可靠性问题例5 有 A,B,C 三部机器串联生产某种产品，由于工艺技术问题，产品常出现次品。统计结果表明，机器 A,B,C 产生次品的概率分别为 pA=30%,PB=40%,PC=20%,而产品必须经过三部机器顺序加工才能完成。为了降低产品的次品率，决定拨款 5 万元进行技术改造，以便最大限度地提高产品的成品率指标。现提出如下四种改进方案：方案1:不拨款，机器保持原状；方案2:加装监视设备，每部机器需款 1 万元；方案3:加装设备，每部机器需款 2 万元；方案4:同时加装监视及控制设备，每部机器需款 3 万元；采用各方案后，各部机器的次品率如下表。第26页/共56页 例5 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)第27页/共56页第二阶段最优决策第二阶段最优决策表表第二阶段：对机器 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 得第二阶段最优决策表第28页/共56页第二阶段最优决策第二阶段最优决策表表第三阶段：对机器 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.648III:x3=2,x2=3,x1=0,R3=0.90.90.8=0.648第29页/共56页 例例6 6 用动态规划解非线性规划用动态规划解非线性规划解:这是一个资源分配问题。设分配次序为x1,x2,x3，阶段正向编号，但逆向递推，由约束条件可得边界条件 s1=27,s4=0。第三阶段：（给 x3分配）由边界条件和状态转移方程有：s4=s3x3=0，即 x3*=s3；因此有，第二阶段：（给 x2分配）由状态转移方程有：s3=s2x2，代入上式得，第30页/共56页 例例6 6 用动态规划解非线性规划用动态规划解非线性规划第一阶段：（给 x1分配）由状态转移方程有：由状态转移方程有：s2=s1 x1=27 x1，代入上式得，代入上式得，第31页/共56页动态规划总结动态规划总结二大类：生产-库存问题；资源分配问题第32页/共56页动态规划（二）最短路径问题资源分配问题第33页/共56页 hk 是一般表达形式，求当前阶段当前状态下的阶段最优总效果(1)如最短路问题，是累加形式，此时有 终端的边际效果一般为 f0(s0,x0)=0(2)如串联系统可靠性问题，是连乘形式，此时有终端的边际效果一般为 f0(s0,x0)=1从第1阶段开始，利用边际效果和边界条件，可以递推到最后阶段第34页/共56页2511214106104131112396581052C1C3D1AB1B3B2D2EC2一、最短路径问题求从A到E的最短路径第35页/共56页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=0第36页/共56页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=0第37页/共56页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=5第38页/共56页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=5第39页/共56页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=8第40页/共56页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=7第41页/共56页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B1)=20f3(C2)=7f3(C1)=8第42页/共56页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B2)=14f3(C2)=7f3(C1)=8f2(B1)=21第43页/共56页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f2(B1)=21f2(B2)=14第44页/共56页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21第45页/共56页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态A （A，B2）B2第46页/共56页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态A （A，B2）B2 （B2，C1）C1第47页/共56页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态A （A，B2）B2 （B2，C1）C1 （C1，D1）D1第48页/共56页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态A （A，B2）B2 （B2，C1）C1 （C1，D1）D1 （D1，E）E从A到E的最短路径为19，路线为AB 2C1 D1 E 第49页/共56页例.有资金4 4万元，投资A A、B B、C C三个项目，每个项目的投资效益与投入该项目的资金有关。三个项目A A、B B、C C的投资效益（万吨）和投入资金（万元）关系见下表：求对三个项目的最优投资分配，使总投资效益最大。二、资源分配问题第50页/共56页4万元2万元1万元0万元4万元2万元1万元0万元4万元2万元1万元0万元4万元 x1A项目 x2B项目 x3C项目 x43万元3万元3万元0f第51页/共56页1.阶段k：每投资一个项目作为一个阶段；2.状态变量xk：投资第k个项目前的资金数；3.决策变量dk：第k个项目的投资；4.决策允许集合：0dkxk5.状态转移方程：xk+1=xk-dk6.阶段指标：vk(xk,dk)见表中所示；7.递推方程：fk(xk)=maxvk(xk,dk)+fk+1(xk+1)8.终端条件：f4(x4)=0第52页/共56页k=4，f4(x4)=0k=3，0d3x3，x4=x3-d3第53页/共56页k=2，0d2x2，x3=x2-d2第54页/共56页k=1，0d1x1，x2=x1-d1第55页/共56页感谢您的观看！第56页/共56页