运筹学教程课件五动态规划

1、1第五章第五章 动态规划动态规划不要过河拆桥不要过河拆桥2动态规划动态规划 Dynamic programming 五十年代贝尔曼五十年代贝尔曼(B. E. Bellman)为代表的研究成果为代表的研究成果 属于现代控制理论的一部分属于现代控制理论的一部分 以长远利益为目标的一系列决策以长远利益为目标的一系列决策 最优化原理，可归结为一个递推公式最优化原理，可归结为一个递推公式5.1 动态规划的最优化原理及其算法5.1.1 求解多阶段决策过程的方法求解多阶段决策过程的方法例例5.1.1 最短路问题最短路问题HLOBIECAFJDGKNPM4352352344771134222548123 决策

2、树法决策树法ACEHIIFJIFDGJJK可以枚举出可以枚举出20条路径，其中最短的路径长度为条路径，其中最短的路径长度为164 例例5.1.1 最短路问题最短路问题表现为明显的阶段性表现为明显的阶段性一条从一条从A 到到B 的最短路径的最短路径中的任何一段都是最短的中的任何一段都是最短的HLOBIECAFJDGKNPM435235234477113422254812161214021457108671189213456阶阶段段HLOBIECAFJDGKNPM435235234477113422254812161214021457108671189213456阶阶段段 每步的决策只与相邻阶段状

3、态有关，每步的决策只与相邻阶段状态有关，而与如何达到这一状态无关而与如何达到这一状态无关 DADCACAiSdSdSBiSmin则则有有径径的的长长度度点点的的最最短短路路点点到到表表示示由由设设因此我们可以从因此我们可以从B向回搜索最短路向回搜索最短路标记法标记法如何找出最短路径如何找出最短路径5 5.1.2 动态规划的基本概念及递推公式动态规划的基本概念及递推公式1、基本概念、基本概念1）阶段）阶段；把多阶段决策问题分为若干个相互联系的阶段，常用；把多阶段决策问题分为若干个相互联系的阶段，常用k表示表示 2）状态：）状态：每一阶段开始时所处的状态。某一阶段某一状态用状态变量每一阶段开始时所

4、处的状态。某一阶段某一状态用状态变量s k表示，第表示，第k阶段的所有状态集合用阶段的所有状态集合用S k表示，各阶段所有状态集合用表示，各阶段所有状态集合用S表示，则表示，则 s k S k S， 动态规划中的状态必须满足无后效性。动态规划中的状态必须满足无后效性。 3）决策：）决策：某一阶段某一阶段k某一状态某一状态s k所作出的决策用决策变量所作出的决策用决策变量x k（s k）表示，）表示，第第k阶段状态阶段状态s k的允许决策集合用的允许决策集合用D k（s k）表示，第）表示，第k阶段各状态的允许决阶段各状态的允许决策集合用策集合用D k表示，所有各阶段各状态的允许决策集合用表示，

5、所有各阶段各状态的允许决策集合用D 表示。则有表示。则有 x k（s k） D k（s k） D k D4）策略：）策略：指某一阶段某一状态到终点的顺序排列的决策组合的集合。用指某一阶段某一状态到终点的顺序排列的决策组合的集合。用 Pk（s k）= x k（s k），），x k-1（s k-1），），x 1（s 1） 表示从第表示从第k阶段状态阶段状态s k出发到终点的一个子策略。从第出发到终点的一个子策略。从第k阶段状态阶段状态s k出发出发到终点的允许策略集合为到终点的允许策略集合为P。则。则Pk（s k） P。5）状态转移方程：）状态转移方程：反映相邻两个阶段的状态和决策变量之间的相互关

6、系反映相邻两个阶段的状态和决策变量之间的相互关系 s k-1=Tks k，x k（s k） = g(sk, xk) 65.1.2 动态规划的基本概念及递推公式动态规划的基本概念及递推公式6）直接效果函数：）直接效果函数：它是状态变量它是状态变量s k和决策变量和决策变量x k（s k）的函数，记为：）的函数，记为： d ks k，x k（s k）。7）总效果函数：）总效果函数：从第从第k阶段状态阶段状态s k出发到终点的子策略出发到终点的子策略 Pk（s k）的函数。记为：）的函数。记为：Vk= Vk Pk（s k）8）最优效果函数：）最优效果函数：表示在某一阶段某一状态下，采取最优策略后到终

7、点的最优效表示在某一阶段某一状态下，采取最优策略后到终点的最优效果值。记为果值。记为)(|)( )(PsPsPVOptsfkkkkkkk2、最优化原理和动态规划递推关系、最优化原理和动态规划递推关系1、最优化原理：、最优化原理：最优策略的子策略也是最优的。最优策略的子策略也是最优的。2、递推关系：、递推关系： ,.2 , 1 )(),( )(11KksfxsdxOptsfkkkkkkkk ,.2 , 1 )(),( )(11KksfxsdxOptsfkkkkkkkk ,.2, 1 )(),( )(11KksfxsdxOptsfkkkkkkkk7 3、动态规划的步骤、动态规划的步骤1)划分阶段划

8、分阶段 将所研究的问题划分为将所研究的问题划分为K个阶段，并对阶个阶段，并对阶段进行编号。一般按逆向编号；段进行编号。一般按逆向编号；2)确定状态变量确定状态变量s k 正确确定状态变量正确确定状态变量s k ，使它既能描，使它既能描述过程的演变又能满足无后效性；述过程的演变又能满足无后效性；3)确定决策变量确定决策变量x k（s k）及其允许的决策集合）及其允许的决策集合 D k（s k）；）；4)写出状态转移方程写出状态转移方程 s k-1 = g (s k ,x k)；5)确定直接效果函数确定直接效果函数6)列出最优指标函数的递推关系式列出最优指标函数的递推关系式7)确定边界条件确定边界

9、条件 85.2 动态规划模型举例动态规划模型举例5.2.1 资源分配问题资源分配问题例例 5.2.1某公司有某公司有4个推销员在北京、上海和广州三个市场推个推销员在北京、上海和广州三个市场推销货物，这三个市场里推销人员数与收益的关系如表销货物，这三个市场里推销人员数与收益的关系如表5.2.1所示，试作出使总收益最大的分配方案。所示，试作出使总收益最大的分配方案。 表表5.2.1推销人员数与收益推销人员数与收益 推销员推销员市场市场01234北京北京2032475766上海上海4050607182广州广州506172 8483解解 1、划分阶段、划分阶段 分成分成3个阶段，即个阶段，即K=3，并

10、按逆向编号，广，并按逆向编号，广州州k=1，上海，上海k=2，北京，北京k=3，分配推销员的优先顺序为北京，分配推销员的优先顺序为北京上海上海广州；广州；2、确定状态变量、确定状态变量s k 状态变量状态变量s k 表示第表示第k阶段初尚未分配的阶段初尚未分配的推销员数。显然有推销员数。显然有 s3= 4，s2和和s1的可能取值范围为的可能取值范围为0 4。93、确定决策变量、确定决策变量x k 决策变量决策变量x k 表示分配给第表示分配给第k阶段市场阶段市场的推销员数。显然有，的推销员数。显然有，x k s k ；4、确定状态转移方程、确定状态转移方程 根据前面定义的状态变量根据前面定义的

11、状态变量s k和决策和决策变量变量x k的意义，可得其状态转移方程为的意义，可得其状态转移方程为s k-1 =s k - x k ；5、确定直接效果函数、确定直接效果函数 d k (s k，x k) 它表示第它表示第k阶段初有推阶段初有推销员数销员数s k，分配给第，分配给第k市场市场x k个推销员时所产生的直接效个推销员时所产生的直接效益。这些效益指标由表益。这些效益指标由表5.2.1给出；给出；6、最优指标函数、最优指标函数 由于三个市场的总效益等于三个市场的由于三个市场的总效益等于三个市场的效益之和，即其指标函数为累加形式。所以最优指标函效益之和，即其指标函数为累加形式。所以最优指标函数

12、为数为7、边界条件、边界条件 f0 (s 0) = 0 。各阶段计算过程见教材各阶段计算过程见教材P（138139）10 5.2.2项目选择问题项目选择问题 某工厂预计明年有某工厂预计明年有A,B,C,D四个新四个新建项目，每个项目的投资额建项目，每个项目的投资额 wk及其投及其投资后的收益资后的收益 vk如右表所示。投资总额如右表所示。投资总额为为30万元，问如何选择项目才能使总万元，问如何选择项目才能使总收益最大。收益最大。 上述问题的静态规划模型如下：上述问题的静态规划模型如下：项目项目wkvkA1512B108C129D85 这是一类这是一类0-1规划问题规划问题 该问题是经典的该问题

13、是经典的旅行背包问题旅行背包问题 (Knapsack) 该问题是该问题是 NP-complete项入选项未入选 1 030)(maxkkxxwxvxfkkkkkkk11解解：设项目选择的顺序为：设项目选择的顺序为A, B, C, D;1、阶段、阶段 k=1, 2, 3, 4 分别对应分别对应 D, C, B, A项目的选择过程项目的选择过程2、第、第 k 阶段的状态阶段的状态 sk，代表第，代表第 k 阶段初尚未分配的投资额阶段初尚未分配的投资额3、第、第 k 阶段的决策变量阶段的决策变量 xk,，代表第，代表第 k 阶段项目是否入选阶段项目是否入选4、状态转移方程为、状态转移方程为 sk1=

14、 sk wk xk5、直接效益、直接效益 dk(sk ,xk)= vk 或或 06、总效益递推公式、总效益递推公式 ),(),(max),(111 kkkkkkxkkkxsfxsdxsfk 该问题的难点在于各阶段的状态的确定，当阶段增加时，状该问题的难点在于各阶段的状态的确定，当阶段增加时，状态数成指数增长。下面利用决策树来确定各阶段的可能状态。态数成指数增长。下面利用决策树来确定各阶段的可能状态。12x2=02253037150812201018531582018302051530301530 x1=0 x1=1x1=0 x2=1x3=1x3=0 x4=0 x4=1x1=0 x1=1x1=1

15、x1=1x1=1x1=0 x1=0 x1=0 x1=0 x2=0 x2=0 x2=0 x2=1x2=1x3=0k=4w4=15 v4=12k=3w3=10 v3=8k=2w2=12 v2=9k=1 w1=8v1=522225141455550990 x3=1135.2.3 生产和库存控制问题生产和库存控制问题 某工厂生产某种产品的月生产能力为某工厂生产某种产品的月生产能力为10件，已知今后件，已知今后四个月的产品成本及销售量如表所示。如果本月产量四个月的产品成本及销售量如表所示。如果本月产量超过销售量时，可以存储起来备以后各月销售，一件超过销售量时，可以存储起来备以后各月销售，一件产品的月存储

16、费为产品的月存储费为2元，试安排月生产计划并做到：元，试安排月生产计划并做到： 1、保证满足每月的销售量，并规定计划期初和期末、保证满足每月的销售量，并规定计划期初和期末库存为零；库存为零； 2、在生产能力允许范围内，安排每月生产量计划使、在生产能力允许范围内，安排每月生产量计划使产品总成本产品总成本(即生产费用加存储费即生产费用加存储费)最低。最低。月月份份阶阶段段k产产品品成成本本ck/件件月月销销售售量量yk月月初初库库存存sk月月末末库库存存sk-114706s4=0s323727s3s2328012s2s141766s1s0=014 例例1 产品生产计划安排产品生产计划安排设设xk为

17、第为第k阶段生产量，则有直接成本阶段生产量，则有直接成本 dk(sk, xk)= ck xk+2sk状态转移公式为状态转移公式为 sk-1= sk+ xk- yk总成本递推公式总成本递推公式 ),(),(min),(111 kkkkkkxkkkxsfxsdxsfk第一阶段第一阶段：(即第即第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,515

18、5.2.4 目标函数为乘积形式的动态规划目标函数为乘积形式的动态规划 有有 A, B, C 三部机器串联生产某种产品，由于工艺技术问题，产品常三部机器串联生产某种产品，由于工艺技术问题，产品常出现次品。统计结果表明，机器出现次品。统计结果表明，机器 A, B, C 产生次品的概率分别为产生次品的概率分别为 pA=30%, PB=40%, PC=20%, 而产品必须经过三部机器顺序加工才能而产品必须经过三部机器顺序加工才能完成。为了降低产品的次品率，决定拨款完成。为了降低产品的次品率，决定拨款 5 万元进行技术改造，以万元进行技术改造，以便最大限度地提高产品的成品率指标。现提出如下四种改进方案：

19、便最大限度地提高产品的成品率指标。现提出如下四种改进方案：方案方案1: 不拨款，机器保持原状；不拨款，机器保持原状；方案方案2: 加装监视设备，每部机器需款加装监视设备，每部机器需款 1 万元；万元；方案方案3: 加装设备，每部机器需款加装设备，每部机器需款 2 万元；万元；方案方案4: 同时加装监视及控制设备，每部机器需款同时加装监视及控制设备，每部机器需款 3 万元；万元；采用各方案后，各部机器的次品率如下表。采用各方案后，各部机器的次品率如下表。ABC不不拨拨款款30%40%20%拨拨款款 1 万万元元20%30%10%拨拨款款 2 万万元元10%20%10%拨拨款款 3 万万元元5%1

20、0%6%165.2.5 连续性变量动态规划问题解法连续性变量动态规划问题解法 设某厂计划全年生产某种产品设某厂计划全年生产某种产品A。其四个季度的订货量分别为。其四个季度的订货量分别为600公斤，公斤，700公斤，公斤，500公斤和公斤和1200公斤。已知生产产品公斤。已知生产产品A的生产费的生产费用与产品的平方成正比，系数为用与产品的平方成正比，系数为0.005。厂内有仓库可存放产品，。厂内有仓库可存放产品，存储费为每公斤每季度存储费为每公斤每季度1元。求最佳的生产安排使年总成本最小。元。求最佳的生产安排使年总成本最小。解解：四个季度为四个阶段，采用阶段编号与季度顺序一致。：四个季度为四个阶

21、段，采用阶段编号与季度顺序一致。 设设 sk 为第为第k季初的库存量，则边界条件为季初的库存量，则边界条件为 s1=s5=0 设设 xk 为第为第k季的季的生产生产量，量，设设 yk 为第为第k季的订货量；季的订货量； sk ，xk ，yk 都取实数，状态转移方程为都取实数，状态转移方程为 sk+1=sk+xk - yk 仍采用反向递推，但注意阶段编号是正向的仍采用反向递推，但注意阶段编号是正向的 目标函数为目标函数为 412,1)005. 0(min)(4321iiixxxxsxxf17生产生产库存管理问题库存管理问题(连续变量连续变量)第一步第一步：(第四季度第四季度) 总效果总效果 f4

22、(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) 得：得：233333333333333332333323233333233330025. 077550)(),(,5 . 0

23、80001601. 002. 0),(1395015005. 01601. 001. 0)500(005. 0)500(117200005. 0),(sssfxsfsxsxxxsfssxsxxsxsxsxxsf 得得代代入入解解得得18 生产生产库存管理问题库存管理问题(连续变量连续变量)第三步第三步：(第二、三、四季度第二、三、四季度) 总效果总效果 f2(s2,x2)=0.005 x22+s2+ f3*(s3) 将将 s3= s2 + x2 700 代入代入 f2(s2,x2) 得：得：222222222222222222222222222)3005. 0(610000)(),(,)31(

24、70007)700(005. 0015. 0),()700(0025. 0)700(77550005. 0),(sssfxsfsxsxxxsfsxsxsxxsf 得得代代入入解解得得 注意注意：阶段最优总效果仅是当前状态的函数，与其后的决：阶段最优总效果仅是当前状态的函数，与其后的决策无关策无关19 生产生产库存管理问题库存管理问题(连续变量连续变量)第四步第四步：(第一、二、三、四季度第一、二、三、四季度) 总效果总效果 f1(s1,x1)=0.005 x12+s1+ f2*(s2) 将将 s2= s1 + x1 600= x1 600 代入代入 f1(s1,x1) 得：得：11800)()

25、,(,60008)304. 0(),()600)(3005. 0()600(610000005. 0),(21111111111211121111 sfxsfxxxxsfxxsxxsf得得代代入入解解得得由此由此回溯回溯：得最优生产：得最优生产库存方案库存方案 x1*=600，s2*=0； x2*=700，s3*=0； x3*=800，s4*=300； x4*=900。205.2.6动态规划方法求解非线性规划动态规划方法求解非线性规划解解: 这是一个资源分配问题。设分配次序为这是一个资源分配问题。设分配次序为x1, x2, x3，阶段正向，阶段正向编号，但逆向递推，由约束条件可得边界条件编号，但逆向递推，由约束条件可得边界条件 s1=27, s4=0。第三阶段：（给第三阶段：（给 x3分配）分配） 0,27)(max321321321xxxxxxxxxxf333)(xxf 由边界条件和状态转移方程有：由边界条件和状态转移方程有：s4=s3 x3=0，即，即 x3*= s3；因此有，因此有，33*3)(ssf 第二阶段：（给第二阶段：（给 x2分配）分配）)(),(3*32222sfxxsf 由状态转移方程有：由状态转移方程有：s3=s2 x2，代