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

1、2022-5-2212022-5-221Dynamic Programming，DP美国数学家贝尔曼美国数学家贝尔曼(Richard Bellman, 19201984)创始时间创始时间上个世纪上个世纪50年代年代创始人创始人 动态规划是运筹学的主要分支之一动态规划是运筹学的主要分支之一, , 是现代是现代企业管理中的一种重要决策方法企业管理中的一种重要决策方法, , 它是解决它是解决多阶段决策过程多阶段决策过程的一种最优化方法的一种最优化方法2022-5-222本章主要内容本章主要内容n多阶段决策过程及其问题举例多阶段决策过程及其问题举例 q最短路问题最短路问题n 动态规划的基本概念和基本方

2、程动态规划的基本概念和基本方程 n动态规划应用举例动态规划应用举例q资源分配问题资源分配问题q背包问题背包问题q生产库存问题生产库存问题q2022-5-2237.1 多阶段决策过程及其问题举例多阶段决策过程及其问题举例n动态规划研究的问题动态规划研究的问题多阶段决策问题多阶段决策问题q在时间或空间上可以划分为若干阶段，每一阶段都需要根在时间或空间上可以划分为若干阶段，每一阶段都需要根据现阶段的情况做出决策据现阶段的情况做出决策q决策者每段决策时，不仅要考虑决策者每段决策时，不仅要考虑本阶段目标最优本阶段目标最优，还应考，还应考虑虑之后各阶段之后各阶段的目标最优的目标最优，最终达到整个决策活动的

3、，最终达到整个决策活动的总体总体目标最优目标最优q当各个阶段的决策确定后，就构成了一个决策序列当各个阶段的决策确定后，就构成了一个决策序列q各阶段的决策一般与时间有关，故称各阶段的决策一般与时间有关，故称“动态动态”。但某些。但某些“静态静态”问题可通过引进问题可通过引进“时间时间”因素，用动态规划方法因素，用动态规划方法来处理来处理12状态状态状态状态状态状态n状态状态决策决策决策决策决策决策状态状态2022-5-224n动态规划分类：动态规划分类：q离散确定性离散确定性动态规划动态规划q离散随机性离散随机性动态规划动态规划q连续确定性连续确定性动态规划动态规划q连续随机性连续随机性动态规划

4、动态规划2022-5-225GD76543358109745EABCHF例例1 最短路径问题最短路径问题 第一阶段第一阶段 第二阶段第二阶段 第三阶段第三阶段 第四阶段第四阶段 求从求从 A 到到 H 的最短路径的最短路径2022-5-2262022-5-226n第一种方法第一种方法称做称做枚举法枚举法（穷举法穷举法）：基本思想是列举出所基本思想是列举出所有可能发生的方案和结果，再对它们进行比较，求出最优有可能发生的方案和结果，再对它们进行比较，求出最优方案。这里，从方案。这里，从 A A 到到 H H 的路程共有的路程共有7 7条可能的路线，分条可能的路线，分别算出各条路线的距离，最后进行比

5、较，可得最优路线别算出各条路线的距离，最后进行比较，可得最优路线 当节点很多时，用穷举法求最优路线的计算工作量将会十当节点很多时，用穷举法求最优路线的计算工作量将会十分庞大，而且其中包含着许多重复计算分庞大，而且其中包含着许多重复计算n第二种方法第二种方法熟称熟称贪心算法贪心算法，亦即，亦即“局部最优路径局部最优路径”法，只法，只选择当前最短途径，选择当前最短途径，“逢近便走逢近便走”，错误地以为局部最优，错误地以为局部最优会致整体最优。在这种想法指导下，所取决策必是会致整体最优。在这种想法指导下，所取决策必是 A C G H，距离为，距离为 4+5+8=172022-5-227d(sk, u

6、k)：第第 k 阶阶段，采取策略段，采取策略 uk 所发生的距离所发生的距离 fk(sk)：第第 k 阶段，在阶段，在 sk 状态时到终点状态时到终点 H 的最短距离的最短距离动态规划的基本思想：动态规划的基本思想：如果起点如果起点 A 经过经过 B, E 而到而到 H最优，则最优，则由由 B 出发经出发经 E 到到 H 这条子路线，必为从这条子路线，必为从 B 到到 H 的最短路线。的最短路线。所以，寻找最短路线，应该从最后一段开始找，然后往前递推所以，寻找最短路线，应该从最后一段开始找，然后往前递推假设假设 sk：第第 k 阶段初所处的节点阶段初所处的节点 uk(sk)：在在 sk 状态时

7、第状态时第 k 阶段所作的决定阶段所作的决定GD76543358109745EABCHF2022-5-228 f4(H)=0GD76543358109745EABCHF2022-5-229 f4(H)=0GD76543358109745EABCHF f3(E)=3343( )()()303( )fEd EHfHu EEH2022-5-2210 f4(H)=0GD76543358109745EABCHF f3(E)=3 f3(F)=5FHFuHfHFdFf)(505)()()(3432022-5-2211GHGuHfHGdGf)(508)()()(343 f4(H)=0GD76543358109

8、745EABCHF f3(E)=3 f3(F)=5 f3(G)=82022-5-2212 f4(H)=0GD76543358109745EABCHF f3(E)=3 f3(F)=5 f3(G)=8 f2(B)=13BEBuFfFBdEfEBdBf)(1359310min)(),()(),(min)(23322022-5-2213CECuGfGCdFfFCdEfECdCf)(10855637min)(),()(),()(),(min)(23332 f4(H)=0GD76543358109745EABCHF f3(E)=3 f3(F)=5 f3(G)=8 f2(B)=13 f2(C)=102022

9、-5-2214DFDuGfGDdFfFDdDf)(88453min)(),()(),(min)(2332 f4(H)=0GD76543358109745EABCHF f3(E)=3 f3(F)=5 f3(G)=8 f2(B)=13 f2(C)=10 f2(D)=82022-5-2215ACAuDfDAdCfCAdBfBAdAf)(1487104135min)(),()(),()(),(min)(12221 f4(H)=0GD76543358109745EABCHF f3(E)=3 f3(F)=5 f3(G)=8 f2(B)=13 f2(C)=10 f2(D)=8 f1(A)=142022-5-

10、2216 f4(H)=0GD76543358109745EABCHF f3(E)=3 f3(F)=5 f3(G)=8 f2(B)=13 f2(C)=10 f2(D)=8f1(A)=14状态状态 最优决策最优决策 状态状态 最优决策最优决策 状态状态 最优决策最优决策 状态状态 A （ AC） C （CE） E （EH） H从从A到到H的最短路径：距离为的最短路径：距离为14，路线为，路线为ACEH 2022-5-22172022-5-2217多阶段决策过程及实例：标号法多阶段决策过程及实例：标号法B1AC3F2F1E3E2E1D3D2D1C4C2C1B2G5313687668353421382

11、23335526643437597681310912131618第一阶段第一阶段第二阶段第二阶段第三阶段第三阶段第四阶段第四阶段第五阶段第五阶段第六阶段第六阶段从从G到到A的解法称为的解法称为逆序解法逆序解法注：因为从注：因为从A A到到G G的最短路与从的最短路与从G G到到A A的最短路是一样的，因此的最短路是一样的，因此也可以从也可以从A A出发来找。从出发来找。从A A到到G G的解法称为的解法称为顺序解法顺序解法2022-5-22182022-5-2218 综上可见，综上可见，全枚举法全枚举法虽可找出最优方案，但不是好算法；虽可找出最优方案，但不是好算法；局部最优法局部最优法则完全是

12、个错误方法；只有则完全是个错误方法；只有动态规划方法动态规划方法属于属于科学有效的算法。它的基本思想是，科学有效的算法。它的基本思想是，把一个比较复杂的问把一个比较复杂的问题分解为一系列同类型的更易求解的子问题题分解为一系列同类型的更易求解的子问题2022-5-22197.2 动态规划的基本概念和基本方程动态规划的基本概念和基本方程 ( (一一) ) 基本概念和基本方程基本概念和基本方程(1) 阶段：阶段：k = 1, , n(2) 状态变量状态变量 sk ：第第 k 阶段的自然状况阶段的自然状况 (3) 决策变量决策变量 uk(sk) ：第第 k 阶段的决定阶段的决定 Dk(sk) ：决策变

13、量的取值范围：决策变量的取值范围GD76543358109745EABCHF2022-5-2220(4) 状态转移方程状态转移方程 sk1 T (sk, uk)：描述第描述第 k 阶段与第阶段与第 k+1 阶段的状态变量的关系阶段的状态变量的关系(5) 指标指标 v (sk ,uk) ：第第 k 阶段在状态阶段在状态 sk 下采取决策下采取决策 uk 得到的得到的 结果（距离、得益、成本等）结果（距离、得益、成本等） 指标函数指标函数是指各阶段指标的累计。即是指各阶段指标的累计。即 V (sk,uk, , sn,un, sn+1)=vk(sk,uk)*vk+1(sk+1,uk+1)*vn(sn

14、,un) 它表示从第它表示从第 k 阶段的状态阶段的状态 sk 开始到第开始到第 n 阶段的终止状态的指标阶段的终止状态的指标累计。式中累计。式中*表示某种运算符，一般为表示某种运算符，一般为加法加法或或乘积乘积运算运算(6) 最优指标函数最优指标函数 fk (sk) ：它表示从第它表示从第 k 阶段的状态阶段的状态 sk 开始到开始到 第第 n 阶段终止的过程中，采取最优策略得到的指标函数值阶段终止的过程中，采取最优策略得到的指标函数值 ),()(1,nkknkuukksusVOPTsfnk2022-5-22212022-5-2221逆推公式逆推公式 fk(sk)OPT v(sk,uk)+

15、fk+1(sk+1) k =n, 1 fn+1(sn+1)0或或 fk(sk)OPTv(sk ,uk)+ fk+1(sk+1) k =n-1, 1 fn(sn) OPTv(sn ,un) 多阶段决策问题中，常见的目标函数形式之一是取多阶段决策问题中，常见的目标函数形式之一是取各阶段效各阶段效益之和的形式益之和的形式。有些问题，如系统可靠性问题，其目标函数。有些问题，如系统可靠性问题，其目标函数是取是取各阶段效益的连乘积形式各阶段效益的连乘积形式。总之，具体问题的目标函数。总之，具体问题的目标函数表达形式需要视具体问题而定表达形式需要视具体问题而定Max 或或 Min2022-5-2222对例对

16、例1(1) 阶段：阶段：k1,2,3(2) 状态变量状态变量 sk ：第第 k 阶段初所处的位置阶段初所处的位置, 状态集合状态集合 Sk, 如如 S2 =B , C, D(3) 决策变量决策变量 uk ：在第在第 k 段段 sk 状态时的路径选择状态时的路径选择(4) 状态转移方程状态转移方程 ：sk1 uk (sk)2022-5-2223(5) 指标：指标： vk (sk ，uk) 为第为第 k 阶段阶段采取决策采取决策 uk 时到下一状态的距离时到下一状态的距离 指标函数指标函数(6) 最优指标函数：最优指标函数： fk (sk)：第第 k 阶段，在阶段，在 sk 状态时到终点状态时到终

17、点 H 的最短距离的最短距离,( ,)nk njijj kVv s ufk(sk)min vk (sk,uk)+ fk+1(sk+1) k=3, 1f4(s4)02022-5-22242022-5-2224（二）（二）贝尔曼贝尔曼最优化原理最优化原理最优策略具有这样的性质：不论初始最优策略具有这样的性质：不论初始状态与初始策略如何，对于先前决策状态与初始策略如何，对于先前决策所造成的状态而言，余下所有决策必所造成的状态而言，余下所有决策必构成最优决策。即：构成最优决策。即：最优策略的子策最优策略的子策略也是最优的！略也是最优的！A BMII II 2022-5-2225（三）解法步骤（三）解法

18、步骤q首先将问题划分为若干个阶段，然后选择状态变量与决首先将问题划分为若干个阶段，然后选择状态变量与决策变量，并写出转移方程和指标函数，列出基本方程策变量，并写出转移方程和指标函数，列出基本方程q反向条件优化反向条件优化q正向求最优解正向求最优解fk(sk)OPT vk (sk,uk) + fk+1(sk+1) k=n, 1fn+1(sn+1)0fk(sk)OPT vk (sk,uk) fk+1(sk+1) k=n, 1fn+1(sn+1)12022-5-22267.3 应用举例应用举例例例2 资源分配问题资源分配问题()()例例3 资源分配问题资源分配问题()()例例4 背包问题背包问题例例

19、5 生产库存问题生产库存问题例例6 可靠性问题可靠性问题例例7 机器负荷分配问题机器负荷分配问题2022-5-2227例例 2 资源分配问题资源分配问题()()某公司准备将某公司准备将 5 台设备分配给所属的三个子工厂，各工厂台设备分配给所属的三个子工厂，各工厂获得设备后的可盈利情况如表所示。获得设备后的可盈利情况如表所示。问：如何分配这五台问：如何分配这五台设备，才能使公司获得的收益最大？设备，才能使公司获得的收益最大？ 工厂工厂 盈利（万元）盈利（万元）设备数设备数工厂工厂1工厂工厂2工厂工厂300001354271063101111412111251411122022-5-2228分析分

20、析(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 阶段采取最优阶段采取最优 分配策略可产生的最大收益分

21、配策略可产生的最大收益2022-5-2229 fk(sk) max gk ( uk)+ fk+1(sk+1) （k = 3,2,1） f4(s4)0逆推公式：逆推公式：其中其中()kkkuD s(): 0kkkkD sus2022-5-22302022-5-2230k=3, S3 = 0,1,2,3,4,5, f3(s3) maxg3(u3)+0g3(u3)+0max u3s3012345f3(s3)u3000010441204662304611113404611121245046111212124,5330su 2022-5-22312022-5-2231k=2, S2 = 0,1,2,3,

22、4,5, f2(s2) maxg2(u2)+ f3(s3)g2(u2)+ f3(s3)max最优最优决策决策 u2s2012345f2(s2)u200+000(0,0)10+45+051(1,0)20+65+410+0102(2,0)30+115+610+411+0142(2,1)40+125+1110+611+411+0161,2(1,3) (2,2)50+125+1210+1111+611+411+0212(2,3)S3=S2-u3220su 2022-5-22322022-5-2232g1(u1)+ f2(s2)max最优决策最优决策 u1s1012345f1(s1)u150+213+1

23、67+1410+1012+514+0210,2(0,2,3)(2,2,1)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台，工厂台，工厂2 分配分配2台，工厂台，工厂3分配分配1台台总盈利均为总盈利均为21万元万元2*2u5052s21*f3*3u3253s同理得到另一同理得到另一组最优解组最优解0*1u51s110su 2022-5-2233一般分配问题一般分配问题某种资

24、源的总量为某种资源的总量为 a，用于用于 n 种生产种生产若分配若分配 uk 于第于第 k 种生产时，收益为种生产时，收益为 gk(xk) 问：应如何分配才能使总收入最大？问：应如何分配才能使总收入最大？该问题的数学模型为该问题的数学模型为Max z = g1 (u1 )+ g2 (u2 )+ gn (un) s.t. u1 +u2 +un= a uk0 2022-5-2234分析分析 (1) 阶段：阶段：k =1，2，., n(3) 决策变量决策变量 uk ：对第对第 k 阶段的分配数阶段的分配数(2) 状态变量状态变量 sk ：第第 k 阶段初可供分配的资源数阶段初可供分配的资源数(4)

25、状态转移方程：状态转移方程： sk1 sk - uk(5) 指标函数指标函数 gk (uk) ：uk 台设备分配给第台设备分配给第 k 种生产所产生种生产所产生 的收益的收益(6) 最优指标函数最优指标函数 fk (sk) ：第第 k 至至 n 阶段采取最优分配策阶段采取最优分配策 略可产生的最大收益略可产生的最大收益2022-5-2235fk(sk) max gk ( uk)+ fk+1(sk+1) k = n,2,1 fn+1(sn+1)0逆推公式：逆推公式：kksu 02022-5-2236例例3 资源分配问题资源分配问题()() 某工厂要进行某工厂要进行A,B,C三种新产品的试制，为提

26、高三种产品三种新产品的试制，为提高三种产品研制成功的概率，决定调拨经费研制成功的概率，决定调拨经费2百万，并要求资金集中百万，并要求资金集中使用，也即以百万为单位进行分配，其增加研发费与新产使用，也即以百万为单位进行分配，其增加研发费与新产品不成功概率的关系如表所示。品不成功概率的关系如表所示。问：如何分配资金，可使问：如何分配资金，可使三种产品都研制不成功的概率最小？三种产品都研制不成功的概率最小？ 产品产品 不成功概率不成功概率费用（百万）费用（百万）ABC00.40.60.810.20.40.520.150.20.32022-5-2237分析分析(1) 阶段：阶段：k = 1，2，3(3

27、) 决策变量决策变量 uk ：对第对第 k 阶段分配金额阶段分配金额(2) 状态变量状态变量 sk ：第第 k 阶段初的可用金额阶段初的可用金额(4) 状态转移方程：状态转移方程： sk1 sk - uk(5) 最优指标函数最优指标函数 fk (sk) ：第第 k 至至 3 阶段采取最优阶段采取最优 分配策略时的最小不成功概率的值分配策略时的最小不成功概率的值2022-5-2238 fk(sk) min gk ( uk) * fk+1(sk+1) k=3,2,1 f4(s4)1逆推公式：逆推公式：其中其中 gk (uk) 是阶段函数是阶段函数kksu 02022-5-2239 u3s3g3(u

28、3)minu3=0u3=1u3=2f3(s3)u*3(s3)00.80.8010.80.50.5120.80.50.30.32k=3, S3 = 0,1,2, f3(s3) ming3(u3)*1330su 2022-5-2240220su u2s2g2(u2)* f3(s3)minu2=0u2=1u2=2f2(s2)u*2(s2)00.6*0.80.48010.6*0.50.4*0.80.3020.6*0.30.4*0.50.2*0.80.162k=2, S2 = 0,1,2, f2(s2) ming2(u2)*f3(s3)2022-5-2241g1(u1)* f2(s2)mins1 u10

29、12f1(s1)u1* (s1)20.4*0.16=0.0640.2*0.3=0.060.15*0.48=0.0720.061k=1, S1 = 2, f1(s1) max g1(u1)* f2(s2)得到方案：得到方案：u1*1，u2*0，u3*1: 产品产品 A分配分配 1百万，产百万，产品品 B分配分配0，产品，产品 C分配分配1百万，百万，f *=0.06110su 1*1u21s0*2u1122s06. 0*f1*3u0013s2022-5-2242例例4 背包问题背包问题 某卡车载重能力为某卡车载重能力为10吨，现要装三种产品，已知每件吨，现要装三种产品，已知每件产品的重量和利润如

30、表。又规定产品产品的重量和利润如表。又规定产品3至多装至多装2件。件。问：问：如何安排运输可使总利润最大？如何安排运输可使总利润最大？产品种类产品种类 k重量重量 tk (吨吨/件件)利润利润 rk (元元/件件) 1 4 150 2 3 120 3 2 802022-5-2243n阶段：阶段：k=1,2,3n状态变量状态变量 sk：第第 k 阶段初的可装载能力阶段初的可装载能力n决策变量决策变量 uk：第第 k 阶段的装载件数阶段的装载件数n状态转移方程：状态转移方程： （tk 为为 k 产品的单件重量）产品的单件重量）n最优指标函数最优指标函数 fk(sk)：第第k-3阶段采取最优策略时的

31、最大利润阶段采取最优策略时的最大利润n递推公式：递推公式： k=3,2,1 f4(s4)=0 kkkkutss1()11()max ()kkkkkkkkDkusfsr ufs动态规划方法求解动态规划方法求解2022-5-2244物品物品1物品物品2物品物品3k=1k=2k=3k=4s1=10s2s3s4阶段阶段状态变量状态变量：装载前背包装载前背包的容量的容量决策变量决策变量：装载的件数装载的件数u1u2u3决策允许集合决策允许集合：装载件数的范围装载件数的范围0u1s1/t1u1为整数为整数状态转移方程状态转移方程：背包容背包容量和装载件数的关系量和装载件数的关系阶段指标阶段指标： vk(s

32、k,uk)=rkuk 在背包中第在背包中第k种物品的价值种物品的价值最优指标最优指标： fk(sk)=maxrkuk+fk+1(sk+1)终端条件终端条件：f4(s4)=0 s2s1-t1u1 s3=s2-t2u2 s4=s3-t3u30u2s2/t2u2为整数为整数0u3mins3/t3, 2u3为整数为整数2022-5-2245nk =3 u3s3r3u3+0=80u3maxu3=0u3=1u3=2f3(s3)u3*010002308080141008016016023333333()0min,2 ,sDsuuut整0)()(max)(444433)(33333sfsfursfsDuC的单

33、件重量为的单件重量为t3=2 2022-5-2246) )=120u=120u2 2+f+f3 3(s(s2 2-3u-3u2 2) )u u2 2=2=2240+160240+160400400k=2：装载物品：装载物品B，f2(s2)B的单件重量为的单件重量为t2=32022-5-2247u u1 1=0=00+4000+400k=1：装载物品：装载物品A， f1(u1)最优解：物品最优解：物品A装装0件，物品件，物品B装装2件，物品件，物品C装装2件件 最大价值为最大价值为400元元2*2u100102s400*f2*3u43*2103s0*1u101sA的单件重量为的单件重量为t1=4

34、2022-5-2248 例例5 生产库存问题生产库存问题q某厂在年末估计，来年某厂在年末估计，来年4个季度市场对该厂某产品的需求量个季度市场对该厂某产品的需求量均为均为 dk=3 (k=1, 2, 3, 4)，而该厂每季度生产此产品的能力为，而该厂每季度生产此产品的能力为 bk=5 (k=1, 2, 3, 4)q每季度生产该产品的固定成本为每季度生产该产品的固定成本为 F=13 (不生产时则为不生产时则为 0)，该产品的单位生产成本为该产品的单位生产成本为 C=2q如果当季度产品不能售出，则需发生库存费用如果当季度产品不能售出，则需发生库存费用 g=1/件，仓件，仓库能贮存产品的最大数量库能贮

35、存产品的最大数量 Ek=4 (k=1, 2, 3, 4) q年初年末库存为年初年末库存为 0，而，而每个季度可以销售的产品是本季度初每个季度可以销售的产品是本季度初的库存及本季度的产量的库存及本季度的产量 试问：在满足市场需求的前提下，如何安排试问：在满足市场需求的前提下，如何安排 4 个季度的生个季度的生产使生产和库存的总费用最小产使生产和库存的总费用最小?2022-5-2249分析分析(1) 阶段：阶段：k = 1, 2, 3, 4(2) 状态变量状态变量 sk ：第第 k 季度初的库存量季度初的库存量(3) 决策变量决策变量 uk ：第第 k 个季度的产量个季度的产量(4) 转移方程：转

36、移方程： sk1 sk +uk - dk(5) 最优指标函数最优指标函数 fk (sk) ：第第 k 至第至第 4 个季度采取最优策略个季度采取最优策略 时的最小总费用时的最小总费用2022-5-2250fk(sk)minwk(uk,sk)+fk+1(sk+1) k=4, 3, 2, 1f5(s5)041141max(0,)min(,)0min(,(),)kkkkkkkiki kkkkiiiii kdsub EdsdssEbdd逆推公式：逆推公式：0)(0)(kkkkkkkkkudusgCuFudsgwdk=3: 需求需求 bk=5: 生产能力生产能力F=13: 固定成本固定成本 C=2: 单

37、位生产成本单位生产成本g=1: 单位库存费用单位库存费用 Ek=4: 仓库储存能力仓库储存能力()kkkuD s2022-5-22511110()3,4,5sD s2022-5-2252nk = 441141max(0,3)=max(0,)min(,)min(5,7,3)0min(,(),)min(4,6,3)kkkkkkkkikkki kkkkiiiii ksdsub EdsdssssEbdd u4s4w4+0min0123f4(s4)u4*0191931171722151513000()3,0()132(3),0kkkkkkkkkkkkkg sdsuwFCug sudusuu2022-5-

38、2253nk = 330min 4,4,64s3333max 0,3min 5,6,7suss3333333132(3),03,0usuuwsu u3s3w3+f4(s4)min012345f3(s3)u3*019+1922+1725+15383117+1920+1723+1526+0265215+1918+1721+1524+024430+1916+1719+1522+019041+1717+1520+01802022-5-2254nk = 220min 4,2,9s22227 ,9 , 5min3 , 0maxssus030),3(2132222222usuusuw u2s2w2+f3(s

39、3)min12345f2(s2)u2*019+3822+2625+24484117+3820+2623+2426+19455215+3818+2621+2424+1927+184342022-5-2255nk = 167*f u1s1w1+f2(s2)min345f1(s1)u1*019+4822+4525+43673, 40543*4*3*2*1uuuu3054*4*3*2*1uuuu1111111132(3),030usuuwsu2022-5-2256可用总费用为可用总费用为 C，总重量为总重量为 Wck 为第为第 k 个部件装配一个备用件的费用个部件装配一个备用件的费用wk 为第为第 k

40、 个部件装配一个备用件的重量个部件装配一个备用件的重量Pk 第第 k 个部件的故障概率个部件的故障概率某机器工作系统由某机器工作系统由 n 个部件组成，这些部件正常工作关系个部件组成，这些部件正常工作关系为串联。为提高系统工作的可靠性，考虑对每个部件都配为串联。为提高系统工作的可靠性，考虑对每个部件都配备备用件。备用件越多，可靠性越大，但系统的成本、重备备用件。备用件越多，可靠性越大，但系统的成本、重量、体积都会变大。已知：量、体积都会变大。已知：例例6 可靠性问题可靠性问题问：在这两个限制条件下，应如何选用部件的备用件个数，问：在这两个限制条件下，应如何选用部件的备用件个数，使得正常工作的可

41、靠性最大使得正常工作的可靠性最大？2022-5-2257设设 uk 为第为第 k 个部件装配备用件的个数，个部件装配备用件的个数， dk(sk, uk) 为第为第 k 个个部件装配部件装配 uk 个备用件时机器正常工作的概率个备用件时机器正常工作的概率(,)1 ()kukkkkds uP 111max(,). .0nkkknkkknkkkkd s ustc uCw uWu为整数2022-5-2258动态规划模型动态规划模型(1) 阶段：阶段：k = 1, 2, , n(3) 决策变量决策变量 uk ：第第 k 个部件上装的备用件个数个部件上装的备用件个数(2) 状态变量状态变量 sk ：第第

42、k 至第至第 n 个部件允许的总费用个部件允许的总费用(4) 状态转移：状态转移： sk+1 = sk - ckuk tk+1 = tk - wkuk (5) 最优指标函数最优指标函数 fk (sk , tk)：第第 k 至第至第 n 个部件，采取最个部件，采取最优策略时机器正常工作的概率优策略时机器正常工作的概率tk ：第第 k 至第至第 n 个部件允许的总重量个部件允许的总重量2022-5-2259逆推公式：逆推公式：fk (sk, tk) = maxdk (sk, uk )* fk+1 (sk+1, tk+1) fn+1 (sn+1 , tn+1)=1 k=n, ,12022-5-226

43、0 某系统由某系统由 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 三部分各应购置多少部件才能使系统的总可三部分各应购置多少部件才能使系统的总可靠率最大？（假设每部分至少购置一件）靠率最大？（假设

44、每部分至少购置一件）2022-5-2261n阶段：阶段：购置购置 A、B、C 分别为阶段分别为阶段1、2、3n状态变量状态变量 sk：第第 k 阶段初可用来购买部件的费用阶段初可用来购买部件的费用n决策变量决策变量 uk：第第 k 阶段购置的件数阶段购置的件数n状态转移方程：状态转移方程：sk+1 = sk - ckuk n指标函数：指标函数：第第 k 阶段本身的可靠率阶段本身的可靠率n最优指标函数最优指标函数 fk(sk) ：第第 k 阶段尚有资金阶段尚有资金 sk 时可能获得时可能获得 的的最高可靠率最高可靠率n递推方程递推方程 fk(sk)= max dk(sk, uk)fk+1(sk+

45、1) k=3,2,1 f4(s4)=1(,)1 ()kukkkkds uP ku2022-5-2262第第3阶段阶段此时此时 C 应至少配备应至少配备 1 个部件，故个部件，故 s2c3=3同时同时 A, B 部件已经至少配备部件已经至少配备 1个部件，故个部件，故 s210-c1-c2=7 u3s3u31u32f3(s3)=maxd3(s3,u3)u3*35670.50.51- -0.250.50.7512总费用：总费用：10 (万元万元)单价：单价：c1=1, c2=2, c3=3故障率：故障率：P1=0.4, P2=0.2, P3=0.53333443( ,)()1uds ufsP 20

46、22-5-2263第第2阶段阶段此时此时 B、C 应至少各配制应至少各配制 1 个部件，故个部件，故 s2c2+c3=2+3=5同时同时 A 部件已经至少配备部件已经至少配备 1个部件，故个部件，故 s2101=9 u2s2u21u22u23f2(s2)u2*567890.80.50.80.50.80.750.80.750.960.50.960.50.960.50.9920.50.40.480.60.61211总费用：总费用：10 (万元万元)单价：单价：c1=1, c2=2, c3=3故障率：故障率：P1=0.4, P2=0.2, P3=0.5222233233(,)()(1)()uds u

47、fsPfs2022-5-226461*283s第第1阶段阶段 u1s1u11u12u13u14u15f1(s1)u1*100.60.60.840.60.9360.480.97440.40.990.40.50422*1u101s1*2u81*2102s504. 0*f*32u 111122122( ,)()(1)()uds ufsPfs总费用：总费用：10 (万元万元)单价：单价：c1=1, c2=2, c3=3故障率：故障率：P1=0.4, P2=0.2, P3=0.52022-5-2265例例7 机器负荷分配问题机器负荷分配问题（其它情形之一）（其它情形之一） 某厂有某厂有 120 台同一规

48、格完好的机器，每台机床全年台同一规格完好的机器，每台机床全年在高负荷下工作可创利在高负荷下工作可创利 9 万元，但机器的报废率高，万元，但机器的报废率高，每年将有每年将有 的机器报废；在低负荷下工作可创利的机器报废；在低负荷下工作可创利 6 万元，每年将有万元，每年将有 的机器报废的机器报废 试拟定连续试拟定连续 3 年的分配计划，使得总利润最大年的分配计划，使得总利润最大 2022-5-2266n阶段：阶段：k1、2、3n状态变量状态变量 sk：第第 k 阶段完好的机器数量阶段完好的机器数量n决策变量决策变量 uk：第第 k 阶段用于高负荷工作的机器数量阶段用于高负荷工作的机器数量n状态转移

49、方程：状态转移方程：n指标函数：指标函数： n最优指标函数最优指标函数 fk(sk)：第第 k 阶段尚有机器数量为阶段尚有机器数量为 sk 时可能时可能获得总收益获得总收益n递推方程：递推方程：kkkkkksuusug63)(691 , 2 , 30)(44ksfkkkkkkususus25. 075. 0)(75. 05 . 011+10()max36()kkkkkkkkusfsusfs2022-5-2267采用反向动态规划法，从第采用反向动态规划法，从第3阶段算起：阶段算起：33*333333330( )max3609( )usf sussuss2222222232222200*222()

50、max36(0.750.25)max0.7512.75 13.5()ususfsusfsuussuss1111111121111100*11( )max36(0.750.25 )max16.1250.375 16.125( )0ususf susfsususus 1201s4525. 075. 0,9025. 075. 0223112ussuss*1230,90,45,1935uuuf2022-5-2268例例8 不确定采购问题不确定采购问题（其它情形之二）（其它情形之二）某厂某厂 5 周内需采购一批原料，周内需采购一批原料，价格波动见右表价格波动见右表试求：在哪周，以什么价格购试求：在哪周，

51、以什么价格购进，期望价格最低？进，期望价格最低？单价单价 P500 0.3600 0.3700 0.42022-5-2269(1) 阶段：阶段：k =1, 2, 3, 4, 5 (2) 状态变量状态变量 sk：第第 k 周的实际价格周的实际价格Sk =500，600，700(3) 决策变量决策变量 uk：1 第第 k 周采购周采购0 第第 k 周等待周等待(4) 指标函数指标函数 SkE ：第第 k 周等待，以后再采购的最低期望价格周等待，以后再采购的最低期望价格(5) 最优指标函数最优指标函数 fk( sk)：第第 k 到第到第 5 周采用最优采购策略时周采用最优采购策略时 的最低期望价格的

52、最低期望价格2022-5-2270基本方程基本方程fk( sk)= min sk, SkE k=4,3,2,1f5( s5)= s5k=5 f5( s5)= s5 u5=1 s5 500 600 700f5( s5) 500 600 700 u5 1 1 12022-5-2271k=4 f4( s4)= min s4, S4E S4E= 0.3 f5 (500)+ 0.3 f5 (600)+ 0.4 f5 (700)=610 f4 (s4)= min s4, 610=500, 当当 s4 =500600, 当当 s4 =600610, 当当 s4 =700 u4 =0 u4 =1k=3 S3E

53、 = 0.3 f4 (500)+ 0.3 f4 (600)+ 0.4 f4 (700) =0.3500+ 0.3600+ 0.4610 =5742022-5-2272 f3( s3)= min s3, S3E = min s3, 574 500, 当当 s3 =500 u3 =1574, 当当 s3 =600,700 u3 =0= f2( s2) = min s2, 551.8500, 当当 s2 =500 u2 =1551.8, 当当 s2 =600,700 u2 =0= k=2 S2E = 0.3 f3 (500)+ 0.3 f3 (600)+ 0.4 f3 (700) = 0.3500+ 0.3574+ 0.4574 = 551.82022-5-2273 f1( s1) = min s1, 536.26500, 当当 s1 =500 u1 =1536.26, 当当 s1 =600,700 u1 =0= uk500500600600700700第第1 1周周1 1 0 0 0 0 第第2 2周周1 10 00 0第第3 3周周1 10 00 0第第4 4周