运筹学-第七章-动态规划

1、2020/9/5,1,2020/9/5,1,第七章 动态规划Dynamic Programming，DP,美国数学家贝尔曼 (Richard Bellman, 19201984),创始时间,上个世纪50年代,创始人,动态规划是运筹学的主要分支之一, 是现代企业管理中的一种重要决策方法, 它是解决多阶段决策过程的一种最优化方法,2020/9/5,2,本章主要内容,多阶段决策过程及其问题举例 最短路问题 动态规划的基本概念和基本方程 动态规划应用举例 资源分配问题 背包问题 生产库存问题 ,2020/9/5,3,7.1 多阶段决策过程及其问题举例,动态规划研究的问题多阶段决策问题 在时间或空间上可

2、以划分为若干阶段，每一阶段都需要根据现阶段的情况做出决策 决策者每段决策时，不仅要考虑本阶段目标最优，还应考虑之后各阶段的目标最优，最终达到整个决策活动的总体目标最优 当各个阶段的决策确定后，就构成了一个决策序列 各阶段的决策一般与时间有关，故称“动态”。但某些“静态”问题可通过引进“时间”因素，用动态规划方法来处理,2020/9/5,4,动态规划分类： 离散确定性动态规划 离散随机性动态规划 连续确定性动态规划 连续随机性动态规划,2020/9/5,5,例1 最短路径问题,第一阶段 第二阶段 第三阶段 第四阶段 求从 A 到 H 的最短路径,2020/9/5,6,2020/9/5,6,第一种

3、方法称做枚举法（穷举法）：基本思想是列举出所有可能发生的方案和结果，再对它们进行比较，求出最优方案。这里，从 A 到 H 的路程共有7条可能的路线，分别算出各条路线的距离，最后进行比较，可得最优路线 当节点很多时，用穷举法求最优路线的计算工作量将会十分庞大，而且其中包含着许多重复计算 第二种方法熟称贪心算法，亦即“局部最优路径”法，只选择当前最短途径，“逢近便走”，错误地以为局部最优会致整体最优。在这种想法指导下，所取决策必是 A C G H，距离为 4+5+8=17,2020/9/5,7,d(sk, uk)：第 k 阶段，采取策略 uk 所发生的距离 fk(sk)：第 k 阶段，在 sk 状

4、态时到终点 H 的最短距离,动态规划的基本思想：如果起点 A 经过 B, E 而到 H最优，则由 B 出发经 E 到 H 这条子路线，必为从 B 到 H 的最短路线。所以，寻找最短路线，应该从最后一段开始找，然后往前递推 假设 sk：第 k 阶段初所处的节点,uk(sk)：在 sk 状态时第 k 阶段所作的决定,2020/9/5,8,2020/9/5,9,f3(E)=3,2020/9/5,10,f3(F)=5,2020/9/5,11,f3(G)=8,2020/9/5,12,f2(B)=13,2020/9/5,13,f2(C)=10,2020/9/5,14,f2(D)=8,2020/9/5,15

5、,f1(A)=14,2020/9/5,16,状态 最优决策 状态 最优决策 状态 最优决策 状态,A （ AC） C （CE） E （EH） H 从A到H的最短路径：距离为14，路线为ACEH,2020/9/5,17,2020/9/5,17,多阶段决策过程及实例：标号法,4,3,7,5,9,7,6,8,13,10,9,12,13,16,18,从G到A的解法称为逆序解法,注：因为从A到G的最短路与从G到A的最短路是一样的，因此也可以从A出发来找。从A到G的解法称为顺序解法,2020/9/5,18,2020/9/5,18,综上可见，全枚举法虽可找出最优方案，但不是好算法；局部最优法则完全是个错误方

6、法；只有动态规划方法属于科学有效的算法。它的基本思想是，把一个比较复杂的问题分解为一系列同类型的更易求解的子问题,2020/9/5,19,7.2 动态规划的基本概念和基本方程,(一) 基本概念和基本方程,(1) 阶段：k = 1, , n,(2) 状态变量 sk ：第 k 阶段的自然状况,(3) 决策变量 uk(sk) ：第 k 阶段的决定 Dk(sk) ：决策变量的取值范围,2020/9/5,20,(4) 状态转移方程 sk1 T (sk, uk)：描述第 k 阶段与第 k+1 阶段的状态变量的关系,(5) 指标 v (sk ,uk) ：第 k 阶段在状态 sk 下采取决策 uk 得到的 结

7、果（距离、得益、成本等） 指标函数是指各阶段指标的累计。即 V (sk,uk, , sn,un, sn+1)=vk(sk,uk)*vk+1(sk+1,uk+1)*vn(sn,un) 它表示从第 k 阶段的状态 sk 开始到第 n 阶段的终止状态的指标累计。式中*表示某种运算符，一般为加法或乘积运算,(6) 最优指标函数 fk (sk) ：它表示从第 k 阶段的状态 sk 开始到 第 n 阶段终止的过程中，采取最优策略得到的指标函数值,2020/9/5,21,2020/9/5,21,逆推公式,或,多阶段决策问题中，常见的目标函数形式之一是取各阶段效益之和的形式。有些问题，如系统可靠性问题，其目标

8、函数是取各阶段效益的连乘积形式。总之，具体问题的目标函数表达形式需要视具体问题而定,Max 或 Min,2020/9/5,22,对例1,(1) 阶段：k1,2,3,(2) 状态变量 sk ：第 k 阶段初所处的位置, 状态集合 Sk, 如 S2 =B , C, D,(3) 决策变量 uk ：在第 k 段 sk 状态时的路径选择,(4) 状态转移方程 ：sk1 uk (sk),2020/9/5,23,(5) 指标： vk (sk ，uk) 为第 k 阶段采取决策 uk 时到下一状态的距离 指标函数,(6) 最优指标函数： fk (sk)：第 k 阶段，在 sk 状态时到终点 H 的最短距离,20

9、20/9/5,24,2020/9/5,24,（二）贝尔曼最优化原理 最优策略具有这样的性质：不论初始状态与初始策略如何，对于先前决策所造成的状态而言，余下所有决策必构成最优决策。即：最优策略的子策略也是最优的！,2020/9/5,25,（三）解法步骤 首先将问题划分为若干个阶段，然后选择状态变量与决策变量，并写出转移方程和指标函数，列出基本方程 反向条件优化 正向求最优解,2020/9/5,26,7.3 应用举例,例2 资源分配问题() 例3 资源分配问题() 例4 背包问题 例5 生产库存问题 例6 可靠性问题 例7 机器负荷分配问题 ,2020/9/5,27,例 2 资源分配问题(),某公

10、司准备将 5 台设备分配给所属的三个子工厂，各工厂获得设备后的可盈利情况如表所示。问：如何分配这五台设备，才能使公司获得的收益最大？,2020/9/5,28,分析,(1) 阶段：k =1，2，3,(3) 决策变量 uk ：对第 k 阶段的分配数,(2) 状态变量 sk ：可分配给第 k 个至第 3 个企业的 设备数（亦即第 k 阶段初可供分配的设备数）,(4) 状态转移方程： sk1 sk - uk,(5) 指标函数 gk (uk) ：分配 uk 台设备给第 k 个工厂所产生 的收益 (6) 最优指标函数 fk (sk) ：第 k 至 第 3 阶段采取最优 分配策略可产生的最大收益,2020/

11、9/5,29,逆推公式：,其中,2020/9/5,30,2020/9/5,30,k=3, S3 = 0,1,2,3,4,5, f3(s3) maxg3(u3)+0,2020/9/5,31,2020/9/5,31,k=2, S2 = 0,1,2,3,4,5, f2(s2) maxg2(u2)+ f3(s3),S3=S2-u3,2020/9/5,32,2020/9/5,32,k=1, S1 = 5, f1(s1) max g1(u1)+ f2(s2),得到两种方案： u1*0，u2*2，u3*3: 工厂1分配0台，工厂2 分配2台，工厂3分配3台 u1*2，u2*2，u3*1: 工厂1分配2台，工

12、厂2 分配2台，工厂3分配1台 总盈利均为21万元,同理得到另一组最优解,2020/9/5,33,一般分配问题,某种资源的总量为 a，用于 n 种生产 若分配 uk 于第 k 种生产时，收益为 gk(xk),问：应如何分配才能使总收入最大？ 该问题的数学模型为,Max z = g1 (u1 )+ g2 (u2 )+ gn (un),s.t. u1 +u2 +un= a uk0,2020/9/5,34,分析,(1) 阶段：k =1，2，., n,(3) 决策变量 uk ：对第 k 阶段的分配数,(2) 状态变量 sk ：第 k 阶段初可供分配的资源数,(4) 状态转移方程： sk1 sk - u

13、k,(5) 指标函数 gk (uk) ：uk 台设备分配给第 k 种生产所产生 的收益 (6) 最优指标函数 fk (sk) ：第 k 至 n 阶段采取最优分配策 略可产生的最大收益,2020/9/5,35,逆推公式：,2020/9/5,36,例3 资源分配问题(),某工厂要进行A,B,C三种新产品的试制，为提高三种产品研制成功的概率，决定调拨经费2百万，并要求资金集中使用，也即以百万为单位进行分配，其增加研发费与新产品不成功概率的关系如表所示。问：如何分配资金，可使三种产品都研制不成功的概率最小？,2020/9/5,37,分析,(1) 阶段：k = 1，2，3,(3) 决策变量 uk ：对第

14、 k 阶段分配金额,(2) 状态变量 sk ：第 k 阶段初的可用金额,(4) 状态转移方程： sk1 sk - uk,(5) 最优指标函数 fk (sk) ：第 k 至 3 阶段采取最优 分配策略时的最小不成功概率的值,2020/9/5,38,逆推公式：,其中 gk (uk) 是阶段函数,2020/9/5,39,k=3, S3 = 0,1,2, f3(s3) ming3(u3)*1,2020/9/5,40,k=2, S2 = 0,1,2, f2(s2) ming2(u2)*f3(s3),2020/9/5,41,k=1, S1 = 2, f1(s1) max g1(u1)* f2(s2),得到

15、方案：u1*1，u2*0，u3*1: 产品 A分配 1百万，产品 B分配0，产品 C分配1百万，f *=0.06,2020/9/5,42,例4 背包问题 某卡车载重能力为10吨，现要装三种产品，已知每件产品的重量和利润如表。又规定产品3至多装2件。问：如何安排运输可使总利润最大？,2020/9/5,43,阶段：k=1,2,3 状态变量 sk：第 k 阶段初的可装载能力 决策变量 uk：第 k 阶段的装载件数 状态转移方程： （tk 为 k 产品的单件重量） 最优指标函数 fk(sk)：第k-3阶段采取最优策略时的最大利润 递推公式： k=3,2,1 f4(s4)=0,动态规划方法求解,2020

16、/9/5,44,物品1,物品2,物品3,k=1,k=2,k=3,k=4,s1=10,s2,s3,s4,阶段,状态变量： 装载前背包的容量,决策变量： 装载的件数,u1,u2,u3,决策允许集合： 装载件数的范围,0u1s1/t1 u1为整数,状态转移方程：背包容量和装载件数的关系,阶段指标： vk(sk,uk)=rkuk 在背包中第k种物品的价值,最优指标： fk(sk)=maxrkuk+fk+1(sk+1),终端条件：,f4(s4)=0,s2s1-t1u1,s3=s2-t2u2,s4=s3-t3u3,0u2s2/t2 u2为整数,0u3mins3/t3, 2 u3为整数,2020/9/5,4

17、5,k =3,C的单件重量为t3=2,2020/9/5,46,k=2：装载物品B，f2(s2),B的单件重量为t2=3,2020/9/5,47,k=1：装载物品A， f1(u1),最优解：物品A装0件，物品B装2件，物品C装2件 最大价值为400元,A的单件重量为t1=4,2020/9/5,48,例5 生产库存问题 某厂在年末估计，来年4个季度市场对该厂某产品的需求量均为 dk=3 (k=1, 2, 3, 4)，而该厂每季度生产此产品的能力为 bk=5 (k=1, 2, 3, 4) 每季度生产该产品的固定成本为 F=13 (不生产时则为 0)，该产品的单位生产成本为 C=2 如果当季度产品不能

18、售出，则需发生库存费用 g=1/件，仓库能贮存产品的最大数量 Ek=4 (k=1, 2, 3, 4) 年初年末库存为 0，而每个季度可以销售的产品是本季度初的库存及本季度的产量 试问：在满足市场需求的前提下，如何安排 4 个季度的生产使生产和库存的总费用最小?,2020/9/5,49,分析,(1) 阶段：k = 1, 2, 3, 4,(2) 状态变量 sk ：第 k 季度初的库存量,(3) 决策变量 uk ：第 k 个季度的产量,(4) 转移方程： sk1 sk +uk - dk,(5) 最优指标函数 fk (sk) ：第 k 至第 4 个季度采取最优策略 时的最小总费用,2020/9/5,5

19、0,逆推公式：,dk=3: 需求 bk=5: 生产能力 F=13: 固定成本 C=2: 单位生产成本 g=1: 单位库存费用 Ek=4: 仓库储存能力,2020/9/5,51,2020/9/5,52,k = 4,2020/9/5,53,k = 3,2020/9/5,54,k = 2,2020/9/5,55,k = 1,2020/9/5,56,可用总费用为 C，总重量为 W ck 为第 k 个部件装配一个备用件的费用,wk 为第 k 个部件装配一个备用件的重量,Pk 第 k 个部件的故障概率,某机器工作系统由 n 个部件组成，这些部件正常工作关系为串联。为提高系统工作的可靠性，考虑对每个部件都配

20、备备用件。备用件越多，可靠性越大，但系统的成本、重量、体积都会变大。已知：,例6 可靠性问题,问：在这两个限制条件下，应如何选用部件的备用件个数，使得正常工作的可靠性最大？,2020/9/5,57,设 uk 为第 k 个部件装配备用件的个数， dk(sk, uk) 为第 k 个部件装配 uk 个备用件时机器正常工作的概率,2020/9/5,58,动态规划模型,(1) 阶段：k = 1, 2, , n,(3) 决策变量 uk ：第 k 个部件上装的备用件个数,(4) 状态转移： sk+1 = sk - ckuk tk+1 = tk - wkuk,(5) 最优指标函数 fk (sk , tk)：第

21、 k 至第 n 个部件，采取最优策略时机器正常工作的概率,tk ：第 k 至第 n 个部件允许的总重量,2020/9/5,59,2020/9/5,60,某系统由 A, B, C 三个部分串联而成，已知： A、B、C 相互独立 各部分的单件故障率分别为 P1=0.4， P2=0.2， P3=0.5 每个部分的单件价格为：A 部分单价 c1=1 万元； B 部分单价 c2=2 万元；C 部分单价 c3=3 万元 可投资购置部件的金额为10万元 问：A, B, C 三部分各应购置多少部件才能使系统的总可靠率最大？（假设每部分至少购置一件）,2020/9/5,61,阶段：购置 A、B、C 分别为阶段1

22、、2、3 状态变量 sk：第 k 阶段初可用来购买部件的费用 决策变量 uk：第 k 阶段购置的件数 状态转移方程：sk+1 = sk - ckuk 指标函数：第 k 阶段本身的可靠率 最优指标函数 fk(sk) ：第 k 阶段尚有资金 sk 时可能获得 的最高可靠率 递推方程 fk(sk)= max dk(sk, uk)fk+1(sk+1) k=3,2,1 f4(s4)=1,2020/9/5,62,第3阶段 此时 C 应至少配备 1 个部件，故 s2c3=3 同时 A, B 部件已经至少配备 1个部件，故 s210-c1-c2=7,总费用：10 (万元) 单价：c1=1, c2=2, c3=

23、3 故障率：P1=0.4, P2=0.2, P3=0.5,2020/9/5,63,第2阶段 此时 B、C 应至少各配制 1 个部件，故 s2c2+c3=2+3=5 同时 A 部件已经至少配备 1个部件，故 s2101=9,总费用：10 (万元) 单价：c1=1, c2=2, c3=3 故障率：P1=0.4, P2=0.2, P3=0.5,2020/9/5,64,第1阶段,总费用：10 (万元) 单价：c1=1, c2=2, c3=3 故障率：P1=0.4, P2=0.2, P3=0.5,2020/9/5,65,例7 机器负荷分配问题（其它情形之一）,某厂有 120 台同一规格完好的机器，每台机

24、床全年在高负荷下工作可创利 9 万元，但机器的报废率高，每年将有 的机器报废；在低负荷下工作可创利 6 万元，每年将有 的机器报废 试拟定连续 3 年的分配计划，使得总利润最大,2020/9/5,66,阶段：k1、2、3 状态变量 sk：第 k 阶段完好的机器数量 决策变量 uk：第 k 阶段用于高负荷工作的机器数量 状态转移方程： 指标函数： 最优指标函数 fk(sk)：第 k 阶段尚有机器数量为 sk 时可能获得总收益 递推方程：,2020/9/5,67,采用反向动态规划法，从第3阶段算起：,2020/9/5,68,例8 不确定采购问题（其它情形之二）,某厂 5 周内需采购一批原料，价格波

25、动见右表 试求：在哪周，以什么价格购进，期望价格最低？,2020/9/5,69,(1) 阶段：k =1, 2, 3, 4, 5,(5) 最优指标函数 fk( sk)：第 k 到第 5 周采用最优采购策略时 的最低期望价格,2020/9/5,70,2020/9/5,71,k=4 f4( s4)= min s4, S4E,k=3 S3E = 0.3 f4 (500)+ 0.3 f4 (600)+ 0.4 f4 (700) =0.3500+ 0.3600+ 0.4610 =574,2020/9/5,72,k=2 S2E = 0.3 f3 (500)+ 0.3 f3 (600)+ 0.4 f3 (700) = 0.3500+ 0.3574+ 0.4574 = 551.8,2020/9/5,73,k=1 S1E = 0.3 f2 (500)+ 0.3 f2 (600)+ 0.4 f2 (700) = 0.3500+ 0.3551.8+ 0.4551.8 = 536.26,2020/9/5,74,最优策略：第 1- 3周，价格为500