《运筹学：第五章 动态规划》由会员分享，可在线阅读，更多相关《运筹学：第五章 动态规划（33页珍藏版）》请在金锄头文库上搜索。
1、管理与人文学院管理与人文学院 忻展红忻展红 1999，4第五章第五章 动态规划动态规划不要过河拆桥不要过河拆桥2动态规划动态规划 Dynamic programming五十年代贝尔曼五十年代贝尔曼(B. E. Bellman)为代表的研究成果为代表的研究成果属于现代控制理论的一部分属于现代控制理论的一部分以长远利益为目标的一系列决策以长远利益为目标的一系列决策最优化原理，可归结为一个递推公式最优化原理，可归结为一个递推公式5.1 动态规划的最优化原理及其算法5.1.1 求解多阶段决策过程的方法求解多阶段决策过程的方法例例5.1.1 最短路问题最短路问题3 决策树法决策树法可以枚举出可以枚举出2
2、0条路径，其中最短的路径长度为条路径，其中最短的路径长度为164 例例5.1.1 最短路问题最短路问题表现为明显的阶段性表现为明显的阶段性一条从一条从A 到到B 的最短路径的最短路径中的任何一段都是最短的中的任何一段都是最短的 最优性原理最优性原理“最优策略的一部分也是最优的最优策略的一部分也是最优的”每步的决策只与相邻阶段状态有关，每步的决策只与相邻阶段状态有关，而与如何达到这一状态无关而与如何达到这一状态无关因此我们可以从因此我们可以从B向回搜索最短路向回搜索最短路标记法标记法如何找出最短路径如何找出最短路径5 5.1.2 动态规划的基本概念及递推公式动态规划的基本概念及递推公式状态状态(
3、每阶段初始的出发点每阶段初始的出发点)最短路问题中，各个节点就是状态最短路问题中，各个节点就是状态生产库存问题中，库存量是状态生产库存问题中，库存量是状态物资分配问题中，剩余的物资量是状态物资分配问题中，剩余的物资量是状态控制变量控制变量(决策变量决策变量)最短路问题中，走哪条路最短路问题中，走哪条路生产库存问题中，各阶段的产品生产量生产库存问题中，各阶段的产品生产量物资分配问题中，分配给每个地区的物资量物资分配问题中，分配给每个地区的物资量阶段的阶段的编号编号与递推的与递推的方向方向一般采用反向递推，所以阶段的编号也是逆向的一般采用反向递推，所以阶段的编号也是逆向的当然也可以正向递推当然也可
4、以正向递推6 动态规划的步骤动态规划的步骤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、态的总效果，它是一个递推公式指某阶段某状态下到终端状态的总效果，它是一个递推公式7 动态规划的步骤动态规划的步骤hk 是一般表达形式，求当前阶段当前状态下的阶段最优是一般表达形式，求当前阶段当前状态下的阶段最优总效果总效果(1) 如最短路问题，是累加形式，此时有如最短路问题，是累加形式，此时有终端的边际效果一般为终端的边际效果一般为 f0(s0, x0)=0(2)如串联系统可靠性问题，是连乘形式，此时有如串联系统可靠性问题，是连乘形式，此时有终端的边际效果一般为终端的边际效果一般为 f0(s0,x0)=1从第从第1 1阶段开始，利用边际效果和边界条件，可以递推到最后阶段开始，利用边际效果和边界
6、条件，可以递推到最后阶段阶段85.2 动态规划模型举例动态规划模型举例 5.2.1 产品生产计划安排问题产品生产计划安排问题 例例1 某工厂生产某种产品的月生产能力为某工厂生产某种产品的月生产能力为10件，已知今后四个月件，已知今后四个月的产品成本及销售量如表所示。如果本月产量超过销售量时，可的产品成本及销售量如表所示。如果本月产量超过销售量时，可以存储起来备以后各月销售，一件产品的月存储费为以存储起来备以后各月销售，一件产品的月存储费为2元，试安排元，试安排月生产计划并做到：月生产计划并做到： 1、保证满足每月的销售量，并规定计划期初和期末库存为零；、保证满足每月的销售量，并规定计划期初和期
7、末库存为零； 2、在生产能力允许范围内，安排每月生产量计划使产品总成本、在生产能力允许范围内，安排每月生产量计划使产品总成本(即生产费用加存储费即生产费用加存储费)最低。最低。9 例例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 s
8、1 0估计估计第一阶段，即第第一阶段，即第4月份初库存的可能月份初库存的可能状态：状态： 0 s1 30 6 7 12=5，所以，所以， s1 0,510第一阶段最优决策表第一阶段最优决策表第二阶段第二阶段：最大可能库存量：最大可能库存量 7 件件由状态转移方程：由状态转移方程： s1=s2+x212 0 及及 x2 10，可知，可知 s2 2,7，min x2=5由阶段效果递推公式有：由阶段效果递推公式有：f2(2,10)=d2(2,10)+f1*(0,6) =2 2+80 10+456=1260得第二得第二阶段最优决策表，如下阶段最优决策表，如下11第二阶段最优决策表第二阶段最优决策表第三
9、阶段第三阶段：最大可能库存量：最大可能库存量 4 件件由状态转移方程：由状态转移方程： s2=s3+x37 2 及及 x3 10，可知，可知 s3 0,4，min x3=5由阶段效果递推公式有：由阶段效果递推公式有：f3(1,10)=d3(1,10)+f2*(4,8) =2 1+72 10+1104=1826得第三得第三阶段最优决策表，如下阶段最优决策表，如下12第三阶段最优决策表第三阶段最优决策表第四阶段第四阶段：初始库存量：初始库存量 s4=0由状态转移方程：由状态转移方程： s3=s4+x46 0 可知可知 x4 6，由阶段效果递推公式有：由阶段效果递推公式有：f4(0,6)=d4(0,
10、6)+f3*(0,10) =70 6+1902=2322得第四得第四阶段最优决策表，如下阶段最优决策表，如下回回溯溯得得此此表表13 例例2 生产生产库存管理问题库存管理问题(连续变量连续变量) 设某厂计划全年生产某种产品设某厂计划全年生产某种产品A。其四个季度的订货量分别为。其四个季度的订货量分别为600公斤，公斤，700公斤，公斤，500公斤和公斤和1200公斤。已知生产产品公斤。已知生产产品A的生产费用的生产费用与产品的平方成正比，系数为与产品的平方成正比，系数为0.005。厂内有仓库可存放产品，存。厂内有仓库可存放产品，存储费为每公斤每季度储费为每公斤每季度1元。求最佳的生产安排使年总
11、成本最小。元。求最佳的生产安排使年总成本最小。解解：四个季度为四个阶段，采用阶段编号与季度顺序一致。：四个季度为四个阶段，采用阶段编号与季度顺序一致。 设设 sk 为第为第k季初的库存量，则边界条件为季初的库存量，则边界条件为 s1=s5=0 设设 xk 为第为第k季的季的生产生产量，量，设设 yk 为第为第k季的订货量；季的订货量； sk ，xk ，yk 都取实数，状态转移方程为都取实数，状态转移方程为 sk+1=sk+xk - yk 仍采用反向递推，但注意阶段编号是正向的仍采用反向递推，但注意阶段编号是正向的 目标函数为目标函数为14例例2 生产生产库存管理问题库存管理问题(连续变量连续变
12、量)第一步第一步：(第四季度第四季度) 总效果总效果 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) 得：得：15 例例2 生产生产库存管理问题库存管理问题(连续变量连
13、续变量)第三步第三步：(第二、三、四季度第二、三、四季度) 总效果总效果 f2(s2,x2)=0.005 x22+s2+ f3*(s3) 将将 s3= s2 + x2 700 代入代入 f2(s2,x2) 得：得： 注意注意：阶段最优总效果仅是当前状态的函数，与其后的决：阶段最优总效果仅是当前状态的函数，与其后的决策无关策无关16 例例2 生产生产库存管理问题库存管理问题(连续变量连续变量)第四步第四步：(第一、二、三、四季度第一、二、三、四季度) 总效果总效果 f1(s1,x1)=0.005 x12+s1+ f2*(s2) 将将 s2= s1 + x1 600= x1 600 代入代入 f1
14、(s1,x1) 得：得：由此由此回溯回溯：得最优生产：得最优生产库存方案库存方案 x1*=600，s2*=0； x2*=700，s3*=0； x3*=800，s4*=300； x4*=900。17 5.2.2 资源分配问题资源分配问题例例3 某公司有某公司有9个推销员在全国三个不同市场推销货物，这三个市场个推销员在全国三个不同市场推销货物，这三个市场里推销人员数与收益的关系如下表，试作出使总收益最大的分配里推销人员数与收益的关系如下表，试作出使总收益最大的分配方案。方案。解解：设分配人员的顺序为市场：设分配人员的顺序为市场1, 2, 3，采用反向阶段编号。，采用反向阶段编号。 设设 sk 为第
15、为第k阶段尚未分配的人员数，边界条件为阶段尚未分配的人员数，边界条件为 s3=9 设设 xk 为第为第k阶段分配的推销人员数；阶段分配的推销人员数；仍采用反向递推，仍采用反向递推， 状态转移方程为状态转移方程为 sk1=sk xk 目标函数为目标函数为18 例例3 第一阶段：给第三市场分配第一阶段：给第三市场分配 s1 有有09种可能，第一阶段最优决策表如下：种可能，第一阶段最优决策表如下：为什么与为什么与例例1 的第一阶段的表有差别？的第一阶段的表有差别？因为不存在边界条件因为不存在边界条件 s0=019 例例3 第二阶段：给第二市场分配第二阶段：给第二市场分配 s2 有有09种可能，第二阶
16、段最优决策表如下：种可能，第二阶段最优决策表如下：20 例例3 第三阶段：给第一市场分配第三阶段：给第一市场分配 由边界条件由边界条件 s3=9，第三阶段最优决策表如下：，第三阶段最优决策表如下：得决策过程：得决策过程：x3*=2, x2*=0, x1*=7, f3*=218 即即 市场市场1 分配分配 2人，市场人，市场2 不分配不分配 ，市场，市场3 分配分配 7人人最优解与分配的顺序有关吗最优解与分配的顺序有关吗？21 5.2.2 资源分配问题资源分配问题例例4 项目选择问题项目选择问题 某工厂预计明年有某工厂预计明年有A,B,C,D四个新四个新建项目，每个项目的投资额建项目，每个项目的
17、投资额 wk及其投及其投资后的收益资后的收益 vk如右表所示。投资总额如右表所示。投资总额为为30万元，问如何选择项目才能使总万元，问如何选择项目才能使总收益最大。收益最大。上述问题的静态规划模型如下：上述问题的静态规划模型如下： 这是一类这是一类0-1规划问题规划问题该问题是经典的该问题是经典的旅行背包问题旅行背包问题 (Knapsack)该问题是该问题是 NP-complete22 例例4 项目选择问题项目选择问题解解：设项目选择的顺序为：设项目选择的顺序为A, B, C, D;1、阶段、阶段 k=1, 2, 3, 4 分别对应分别对应 D, C, B, A项目的选择过程项目的选择过程2、
18、第、第 k 阶段的状态阶段的状态 sk，代表第，代表第 k 阶段初尚未分配的投资额阶段初尚未分配的投资额3、第、第 k 阶段的决策变量阶段的决策变量 xk,，代表第，代表第 k 阶段分配的投资额阶段分配的投资额4、状态转移方程为、状态转移方程为 sk1= sk wk xk5、直接效益、直接效益 dk(sk ,xk)= vk 或或 06、总效益递推公式、总效益递推公式 该问题的难点在于各阶段的状态的确定，当阶段增加时，状该问题的难点在于各阶段的状态的确定，当阶段增加时，状态数成指数增长。下面利用决策树来确定各阶段的可能状态。态数成指数增长。下面利用决策树来确定各阶段的可能状态。2324 例例4
19、第一阶段第一阶段( (项目项目D) )的选择过程的选择过程s18 时时，x1只能取只能取0；w1=8, v1=525例例4 第二阶段第二阶段( (项目项目C) )的选择过程的选择过程26 例例4 第三阶段第三阶段( (项目项目B) )的选择过程的选择过程第四阶段第四阶段( (项目项目A) )的选择过程的选择过程27 5.2.3 串联系统可靠性问题串联系统可靠性问题例例5 有有 A, B, C 三部机器串联生产某种产品，由于工艺技术问题，产品三部机器串联生产某种产品，由于工艺技术问题，产品常出现次品。统计结果表明，机器常出现次品。统计结果表明，机器 A, B, C 产生次品的概率分别为产生次品的
20、概率分别为 pA=30%, PB=40%, PC=20%, 而产品必须经过三部机器顺序加工才能而产品必须经过三部机器顺序加工才能完成。为了降低产品的次品率，决定拨款完成。为了降低产品的次品率，决定拨款 5 万元进行技术改造，以便万元进行技术改造，以便最大限度地提高产品的成品率指标。现提出如下四种改进方案：最大限度地提高产品的成品率指标。现提出如下四种改进方案：方案方案1: 不拨款，机器保持原状；不拨款，机器保持原状；方案方案2: 加装监视设备，每部机器需款加装监视设备，每部机器需款 1 万元；万元；方案方案3: 加装设备，每部机器需款加装设备，每部机器需款 2 万元；万元；方案方案4: 同时加
21、装监视及控制设备，每部机器需款同时加装监视及控制设备，每部机器需款 3 万元；万元；采用各方案后，各部机器的次品率如下表。采用各方案后，各部机器的次品率如下表。28 例例5 串联机器可靠性问题串联机器可靠性问题解解：为三台机器分配改造拨款，设拨款顺序为：为三台机器分配改造拨款，设拨款顺序为A, B, C，阶段序号反，阶段序号反向编号为向编号为 k，即第一阶段计算给机器，即第一阶段计算给机器 C 拨款的效果。拨款的效果。 设设 sk 为第为第 k 阶段剩余款，则边界条件为阶段剩余款，则边界条件为 s3=5； 设设 xk 为第为第 k 阶段的阶段的拨款额拨款额； 状态转移方程为状态转移方程为 sk
22、-1=sk-xk； 目标函数为目标函数为 max R=(1-PA)(1-PB)(1-PC) 仍采用反向递推仍采用反向递推第一阶段第一阶段 ：对机器：对机器 C 拨款的效果拨款的效果 R1(s1,x1)=d1(s1,x1) R0(s0,x0)= d1(s1,x1)29第二阶段最优决策表第二阶段最优决策表第二阶段第二阶段 ：对机器：对机器 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)
23、 0.9=0.72 得得第二阶段最优决策表第二阶段最优决策表30第二阶段最优决策表第二阶段最优决策表第三阶段第三阶段 ：对机器：对机器 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
24、= 0.9 0.8 0.9=0.648III: x3=2, x2=3, x1=0, R3= 0.9 0.9 0.8 =0.64831 例例6 用动态规划解非线性规划用动态规划解非线性规划解解: 这是一个资源分配问题。设分配次序为这是一个资源分配问题。设分配次序为x1, x2, x3，阶段正向，阶段正向编号，但逆向递推，由约束条件可得边界条件编号，但逆向递推，由约束条件可得边界条件 s1=27, s4=0。第三阶段：（给第三阶段：（给 x3分配）分配）由边界条件和状态转移方程有：由边界条件和状态转移方程有：s4=s3 x3=0，即，即 x3*= s3；因此有，因此有，第二阶段：（给第二阶段：（给 x2分配）分配）由状态转移方程有：由状态转移方程有：s3=s2 x2，代入上式得，代入上式得，32 例例6 用动态规划解非线性规划用动态规划解非线性规划第一阶段：（给第一阶段：（给 x1分配）分配）由状态转移方程有：由状态转移方程有：s2=s1 x1=27 x1 ，代入上式得，代入上式得，33动态规划总结动态规划总结二大类：生产二大类：生产-库存问题；资源分配问题库存问题；资源分配问题
