第8章动态规划第1,2节学习教案

1、会计学1第第8章动态章动态(dngti)规划第规划第1,2节节第一页，共78页。2设备更新问题、复合系统可靠性问题及生产过程最优控制等，并且取得了显著的效果。第1页/共78页第二页，共78页。3 动态规划是用来解决多阶段决策过程最优化的一动态规划是用来解决多阶段决策过程最优化的一种数量方法。其特点在于，它可以种数量方法。其特点在于，它可以(ky)把一个把一个n 维维决策问题变换为几个一维最优化问题，从而一个一个决策问题变换为几个一维最优化问题，从而一个一个地去解决。地去解决。 需指出：动态规划是求解某类问题的一种方法，需指出：动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种算

2、法。必须对具是考察问题的一种途径，而不是一种算法。必须对具体问题进行具体分析，运用动态规划的原理和方法，体问题进行具体分析，运用动态规划的原理和方法，建立相应的模型，然后再用动态规划方法去求解。建立相应的模型，然后再用动态规划方法去求解。第2页/共78页第三页，共78页。412n状态状态决策决策状态状态决策决策状态状态状态状态决策决策第3页/共78页第四页，共78页。5第4页/共78页第五页，共78页。6所以多阶段决策问题也称为序贯决策问题。第5页/共78页第六页，共78页。7C4AB2B1C3C2C1D3D2D1E3E2E1F1F2G53136387668522552233333663441

3、8第6页/共78页第七页，共78页。8第7页/共78页第八页，共78页。9第8页/共78页第九页，共78页。10C4AB2B1C3C2C1D3D2D1E3E2E1F1F2G5313638766852255223333366344181阶段2阶段5阶段3阶段4阶段6阶段第9页/共78页第十页，共78页。11n穷举法2*3*2*2*2*1=48第10页/共78页第十一页，共78页。12第11页/共78页第十二页，共78页。13第12页/共78页第十三页，共78页。14n如D2（B1）C1,C2,C3，若从B1出发选取C2，则C2是状态B1在决策u2(B1)作用下的一个新的状态，记为u2(B1)=C

4、2 第13页/共78页第十四页，共78页。15第14页/共78页第十五页，共78页。16的难点之一。第15页/共78页第十六页，共78页。17211132112211122( , )( , , , )( , , , , , )kkkksT s usT s u s usT s u s us u 图示如下图示如下(rxi)：状态转移方程是确定过状态转移方程是确定过程程(guchng)(guchng)由一个由一个状态到另一个状态的演状态到另一个状态的演变过程变过程(guchng)(guchng)。如果第如果第k k阶段状态变量阶段状态变量sksk的值、该阶段的决策变的值、该阶段的决策变量一经确定，第

5、量一经确定，第k+1k+1阶段阶段状态变量状态变量sk+1sk+1的值也就的值也就确定。确定。其状态转移方程其状态转移方程(fngchng)如下（一般形式）如下（一般形式）12ks1u1s2u2s3skuksk+1 能用动态规划方法求解的多阶段决策过程是一类特殊的多阶段决策过程，即能用动态规划方法求解的多阶段决策过程是一类特殊的多阶段决策过程，即具有无后效性具有无后效性的多阶段决策过程。的多阶段决策过程。第16页/共78页第十七页，共78页。18如果如果(rgu)(rgu)状态变量不能满足无后效性的要求，应适当地改变状态的定义或规定方法。状态变量不能满足无后效性的要求，应适当地改变状态的定义或

6、规定方法。),(),(),(122231112kkkkusTsusTsusTs 动态规划中能动态规划中能处理的状态转移处理的状态转移方程方程(fngchng)(fngchng)的形式。的形式。状态具有无后效性的多阶段决策状态具有无后效性的多阶段决策(juc)(juc)过程的状态转移方程如下过程的状态转移方程如下无后效性无后效性( (马尔可夫性马尔可夫性) )如果某阶段状态给定后，则在这个阶段以后过程的发展不受这个阶段以前各段状态的影响；如果某阶段状态给定后，则在这个阶段以后过程的发展不受这个阶段以前各段状态的影响；过程的过去历史只能通过当前的状态去影响它未来的发展；过程的过去历史只能通过当前的

7、状态去影响它未来的发展；构造动态规划模型时，要充分注意是否满足无后效性的要求；即构造动态规划模型时，要充分注意是否满足无后效性的要求；即状态变量要满足无后效性的要求状态变量要满足无后效性的要求；第17页/共78页第十八页，共78页。19推关系，即：nVk，n（sk，uk，sk+1，uk+1 ,，sn+1）=ksk，uk，Vk+1，n（sk+1， uk+1 ,，sn+1） 第18页/共78页第十九页，共78页。20(,)njjjj kv s u(,)njjjj kv s u第19页/共78页第二十页，共78页。21,1,()(,)knkkk nkknuufsopt Vs us第20页/共78页第

8、二十一页，共78页。22小结小结(xioji):(xioji):),()(1,susVoptsfnkknkkkuunk),(,111,1nkknkkkksusVus方程方程 : :状态转移方程状态转移方程),(1kkkkusTs概念概念 : : 阶段变量阶段变量k k状态变量状态变量s sk k决策变量决策变量u uk k; ;指标指标: : ),(111,nkkkknknksususVV动态规划本质上是多阶段决策过程动态规划本质上是多阶段决策过程; ; 效益效益指标函数指标函数(hnsh)(hnsh)形式形式: : 和、和、积积无后效性无后效性),(111,nkkkknksususV可递推可

9、递推第21页/共78页第二十二页，共78页。23第22页/共78页第二十三页，共78页。24始点到终点的最短路线。ABC第23页/共78页第二十四页，共78页。25第24页/共78页第二十五页，共78页。26511615151151262521615252252262531615353262(,)()34()minmin7,()(,)()53(,)()54()minmin5,()(,)()23(,)()()min(,)()dEFfFfEuEFdEFfFdEFfFfEuEFdEFfFdEFfFfEdEFfF53264min9,()63uEF1阶段2阶段3阶段4阶段5阶段6阶段C4AB2B1C3C

10、2C1D3D2D1E3E2E1F1F2G531363876685225522333336634418第25页/共78页第二十六页，共78页。27411514141251252422524242252353432524353353(,)()2 7()minmin7,()(,)()2 5(,)()1 5()minmin6,()(,)()2 9(,)()()min(,)()d D Ef Ef Du DEd D Ef Ed D Ef Ef Du DEd D Ef Ed D Ef Ef Dd D Ef E4323 5min8,()3 9u DE1阶段2阶段3阶段4阶段5阶段6阶段C4AB2B1C3C2C

11、1D3D2D1E3E2E1F1F2G531363876685225522333336634418第26页/共78页第二十七页，共78页。283131151413251141221321425221214222211334322333243234343()13()()7()7()10()()()13()()6()5()()18()()16()()9()8()()()()12()fCuCDfEfDfCuEFuDEfBuCDfDfEuBCfAuDEfBuABfCufDuBCuCDuDEfCuCD6161522625362532()4()()()3()9()()fFuFGEFfFfEuFGuEF1阶段

12、2阶段3阶段4阶段5阶段6阶段C4AB2B1C3C2C1D3D2D1E3E2E1F1F2G531363876685225522333336634418第27页/共78页第二十八页，共78页。29C4AB2B1C3C2C1D3D2D1E3E2E1F1F2G5313638766852255223333366344180第28页/共78页第二十九页，共78页。30C4AB2B1C3C2C1D3D2D1E3E2E1F1F2G5313638766852255223333366344181813131216109768759403第29页/共78页第三十页，共78页。31C4AB2B1C3C2C1D3D2

13、D1E3E2E1F1F2G5313638766852255223333366344180第30页/共78页第三十一页，共78页。32C4AB2B1C3C2C1D3D2D1E3E2E1F1F2G53136387668522552233333663441805693810111313131315161815第31页/共78页第三十二页，共78页。33第32页/共78页第三十三页，共78页。34均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题所得的最优解，就是整个问题的最优解。第33页/共78页第三十四页，共78页。35第34页/共78页第三十五页，共78页。36第35页/共78页第三十

14、六页，共78页。37ksku)(kkxD),(1kkkuxTx),(kkkuxv,kVk),(,),(11111nnkkkkkknnkkkkkuxuxVuxuxuxuxV),(1kkkkVux1,knV第36页/共78页第三十七页，共78页。38n8、设备更新问题第37页/共78页第三十八页，共78页。39第38页/共78页第三十九页，共78页。401v1(s1,u1)x1s1s22x2s3skkxksk+1snnxnsn+1输输入入输出输出v2(s2,u2)vk(sk,uk)vn(sn,un)1(,)kkkksT sx解得最优解x1=x1(s1)和最优值f1(s1) 。11()1()()(,

15、)*() (,)*(,),1,1kkkkkkkkkkkkkxDskkkkkkkxDsfsoptv sxfsoptv sxfT sxkn n于是s2=T1(s1,x1)和f2(s2),顺序推算确定每阶段决策(juc)和效益。第39页/共78页第四十页，共78页。411(,)rkkkksTsx解得最优解xn=xn(sn+1)和最优值fn(sn+1) 。11()11()()(,)*() (,)*(,),1,2,kkkkkkkkkkkkkxDsrkkkkkkkxDsfsoptv sxfsoptv sxfTsxkn于是sn=Trn(sn+1,xn)和fn-1(sn),逆序推算(tu sun)确定每阶段决

16、策和效益。k=1f1(s2)x1s1s2k=2f2(s3)x2s3skk=kfk(sk+1)xksk+1snk=nfn(sn+1)xnsn+1输输入入输出输出第40页/共78页第四十一页，共78页。42Max Z=x1.(x2)2.x3x1+x2+x3=c ( 0 )xi0 i=1,2,30 i=1,2,3第41页/共78页第四十二页，共78页。4333123122334s1 | 2 | 3 | 4 ss ss ss xcxxx 阶段 223112ss xsxsc 按问题的变量个数划分阶段，把它看作按问题的变量个数划分阶段，把它看作(kn zu)一个一个三阶段决策问题，三阶段决策问题，k=1，

17、2，3第42页/共78页第四十三页，共78页。44v3（x3）=x3 ，各指标函，各指标函数数(hnsh)以乘积方式结合以乘积方式结合第43页/共78页第四十四页，共78页。45第44页/共78页第四十五页，共78页。46状态转移方程为状态转移方程为：s3=x3s3+x2=s2s2+x1=s1=c指标指标(zhbio)函函数为：数为：v1（x1）=x1v2（x2）=x22v3（x3）=x322222222223302232202222032*22(2) f ()m ax ()() = m ax () = m ax () = 4/ 27 x2/ 3xsxsxssvxfsxfsxxsxss3333

18、33334433*33(1) f ()max()() = max(1) xxsxssvxfsxss11111111220121031104*1(3) f ()m ax()() = m ax () = m ax (4()/ 27 ) =/ 64 x/ 4xscxcxcsvxfsxfcxxcxcc2223222222222222223232(032620 xsxsxxsxxsxsxs222222222令 hd h由d x得 舍 去 ）dh又d xdh而 故 是 极 大 值 点d x第45页/共78页第四十六页，共78页。47*411111*3321122222*32233333*112111 x

19、f ( )446432141x x f ()s4322716111x x f ( )s444112xx443scscscsscscscsscscscsc所以最优解为： *233*411 x 24164scsczc第46页/共78页第四十七页，共78页。4821322123122334ss1 | 2 | 3 | 4 = c ss ss ss xxsxxx 阶段 433s xsc 第47页/共78页第四十八页，共78页。49第48页/共78页第四十九页，共78页。50第49页/共78页第五十页，共78页。51由后向前(xin qin)逐段递推，f1（a）即为所求问题的最大收益。 第50页/共78页

20、第五十一页，共78页。52第51页/共78页第五十二页，共78页。53 工厂工厂 赢利赢利设备台数设备台数甲甲(1) 乙乙(2) 丙丙(3)012345037912130510111111046111212第52页/共78页第五十三页，共78页。54fk(sk)= M a x Pk (xk) +fk+1(sk+1) ，k=3,2,1;f4(s4)= 0 （边界条件）（边界条件）0 xxk kssk k第53页/共78页第五十四页，共78页。55 x3s3P3(x3)f3(s3) x*30123450000114126623111134121245121253333333( )max()0,1,

21、2,3,4,5xf sP xss其中第54页/共78页第五十五页，共78页。56 x2S2P2(x2)+f3(s2-x2)f2(s2) x*201234500+00010+4 5+05120+6 5+4 10+010230+115+6 10+4 11+014240+125+1110+6 11+411+0161,250+125+1210+11 11+611+4 11+0 21222222232202()max()()0,1,2,3,4,5xsfsP xf sx其中s =第55页/共78页第五十六页，共78页。57 x1S1P1(x1)+f2(5-x1)f1(5) x*101234550+213+

22、167+14 9+1012+5 13+0 210,211111112101( )(5)max()(5)5xsf sfP xfx其中s =按计算表格的顺序反推算(tu sun)，可得两个最优方案方案(fng n)(1) x*1=0, s2=s1-x*1=5x*2=2, s3=s2-x*2=3x*3=s3=3方案(fng n)(2) x*1=2, s2=s1-x*1=3x*2=2, s3=s2-x*2=1x*3=s3=1第56页/共78页第五十七页，共78页。58第57页/共78页第五十八页，共78页。59第58页/共78页第五十九页，共78页。60kkk0 x0()3 1* x1,2,.,6 x

23、6()0.5()()kkkkkkkxxkvvvkxvkkkk当第k期生产成本 c当当第 期末库存量为 时的存储费用 h第 期总成本为ch状态状态(zhungti)转移方程为：转移方程为： vk-1+ xk- dk= vk第59页/共78页第六十页，共78页。61每期生产量每期生产量x k ：每期生产量不超过生产能力每期生产量不超过生产能力6（用（用m表示）；表示）；又因为又因为(yn wi) v k-1 +x k -d k = v k, 所以所以v k-1 = v k+ d k-x k 0,即即 x k v k+ d k; 0 x kMin v k+ d k,6 = k 每期期末库存量每期期末

24、库存量v k：不大于今后各期需求量之和不大于今后各期需求量之和不大于不大于m- d k 。410min(,6)kjkj kvdd 第60页/共78页第六十一页，共78页。62指标函数循序递推关系为（指标函数循序递推关系为（顺推法顺推法) ： f k (vk )= M i n c k(xk)+0.5vk + f k-1 (vk-1 ) = M i n c k(xk)+0.5 vk + f k-1 (vk + dk - xk) 其中其中 k = min(vk+ dk, 6 ) ;k=2,3,4 f 0(v0 )=0 （边界条件）（边界条件）k=1,2,3,4.0 xxk k 0 xxk k 第61

25、页/共78页第六十二页，共78页。63f 1(v1 )= M i n c 1(x1)+0.5 v1 + f 0(v0)x x1 = min(v1+ d1, 6 )41120min(,6)min(9,62)4jjvdd1111120(0)min(30.5*0)5,2xvfxx时，1111131(1)min(30.5*1)6.5,3xvfxx时，1111142(2)min(30.5*2)8,4xvfxx时，1111153(3)min(30.5*3)9.5,5xvfxx时，1111164(4)min(30.5*6)11,6xvfxx时，第62页/共78页第六十三页，共78页。642222222212

26、2022224223()min ()()(3)min(,6)min(3,6) 0vmin(,6)min(6,3)3xjjf vc xh vf vxvdvdd 其中：2222212032212212221221(0)min()(0)(3)c (0)(0)(3)09.5c (1)(0)(2)48 =minmin9.5,0c (2)(0)(1)56.565c (3)(0)(0)xfc xhfxhfhfxhfhf所以2222212204(1)min()(1)(4)=11.5,0 xfc xhfxx所以2222212205(2)min()(2)(5)=14,5xfc xhfxx所以2222212206(

27、3)min()(3)(6)=15.5,6xfc xhfxx所以第63页/共78页第六十四页，共78页。653333333323303333343()min ()()(2)min(,6)min(2,6) 0vmin(,6)min(4,4)4xf vc xh vf vxvdvdd其中：3333333333(0)14,0(1)16,03(2)17.5,4(3)19,5(4)20.5,6fxfxfxfxfx所以所以或所以所以所以第64页/共78页第六十五页，共78页。664444443404434343443430(0)min ( )(0)(4)c (0)(4)0 20.5c (1)(3)4 19 =min c (2)(2)min 5 17.520.5,06 16c (3)(1)7 14c (4)(0)xvfc xhfxfffxff所以第65页/共78页第六十六页，共78页。67k-1kkkv = v + d -x 阶段需求量di库存量vi生产量xi440032462300123