运筹学与最优化方法修改动态规划学习教案

《运筹学与最优化方法修改动态规划学习教案》由会员分享，可在线阅读，更多相关《运筹学与最优化方法修改动态规划学习教案（122页珍藏版）》请在装配图网上搜索。

1、会计学1第一页，共122页。2多阶段决策过程(Multi-Stagedecision process)： 前一个阶段的决策要影响到后一个阶段的决策，从而影响整个(zhngg)过程。各个阶段所确定的决策就构成了一个决策序列，称为一个策略。一般来说，由于每一阶段可供选择的决策往往不止一个，因此，对于整个(zhngg)过程，就会有许多可供选择的策略。第1页/共122页第二页，共122页。3最优策略： 若对应于一个策略，可以由一个量化的指标来确定这个策略所对应的活动过程的效果，那么不同(b tn)的策略就有各自的效果。在所有可供选择的策略中，对应效果最好的策略称为最优策略。把一个问题划分成若干个相互联

2、系的阶段选取其最优策略，这类问题就是多阶段决策问题。第2页/共122页第三页，共122页。4第3页/共122页第四页，共122页。5 属于多阶段(jidun)决策类的问题很多，例如：第4页/共122页第五页，共122页。6如果卖去旧的买新的，还需要如果卖去旧的买新的，还需要付出更新费因此就需要综合付出更新费因此就需要综合权衡决定设备的使用年限，使权衡决定设备的使用年限，使总的经济效益总的经济效益(jn j xio (jn j xio y)y)最好。最好。第5页/共122页第六页，共122页。7第6页/共122页第七页，共122页。8多阶段决策问题，应用动态规划方法加以解决。第7页/共122页第

3、八页，共122页。9面我们将详细讨论这个问题面我们将详细讨论这个问题) )。第8页/共122页第九页，共122页。10究。究。第9页/共122页第十页，共122页。11图11 运输网络图示第10页/共122页第十一页，共122页。12第11页/共122页第十二页，共122页。13多阶段决策(juc)过程特点:要点：阶段(jidun)，状态，决策，状态转移方程，k-后部子过程状态 x1阶段1T1决策u1状态 x2决策u2阶段2T2状态 x3.状态 xk决策uk阶段kTk状态 xk+1.状态 xn决策un阶段nTn状态 xn+1第12页/共122页第十三页，共122页。14第13页/共122页第十

4、四页，共122页。15v10 ，全程长度是20；显然，这种方法的结果常是错误的第14页/共122页第十五页，共122页。16动态规划方法总是从过程的最后阶段开始考虑，然后逆着实际过程发展的顺序，逐段向前递推计算直至始点。第15页/共122页第十六页，共122页。17第16页/共122页第十七页，共122页。18第17页/共122页第十八页，共122页。19用以描述阶段的变量叫作阶段用以描述阶段的变量叫作阶段变 量 ， 一 般 以变 量 ， 一 般 以 k k 表 示 阶 段 变表 示 阶 段 变量阶段数等于多段决策过程量阶段数等于多段决策过程从开始到结束所需作出决策的从开始到结束所需作出决策的

5、数目。数目。第18页/共122页第十九页，共122页。20态，或称输入状态和输出状态，态，或称输入状态和输出状态，阶段阶段k k的初始状态记作的初始状态记作sksk，终止，终止状态记为状态记为sk+1sk+1。但为了清楚起见，。但为了清楚起见，通常定义阶段的状态即指其初始通常定义阶段的状态即指其初始状态。状态。第19页/共122页第二十页，共122页。21第20页/共122页第二十一页，共122页。22第21页/共122页第二十二页，共122页。23第22页/共122页第二十三页，共122页。24)(,(1kkkkksusTs(1)第23页/共122页第二十四页，共122页。25指标函数可以是

6、诸如费用、成本、产值、利润、产量、耗量、距离、时间、效用(xioyng)，等等。第24页/共122页第二十五页，共122页。26关(yugun)，还跟该子过程策略pk(sk)有关(yugun)，因此它是sk和pk(sk)的函数，严格说来，应表示为:)(,(kkkkspsR第25页/共122页第二十六页，共122页。27),(),(),(),(11111,nnnkkkkkknnkkkknknkusgusgusgusususRR (2)第26页/共122页第二十七页，共122页。28nkiiiikusgR),(nkiiiikusgR),(第27页/共122页第二十八页，共122页。29nkspsR

7、optsfkkkksPpkkkKk, 2 , 1),(,()()()(,(kkkkspsR)(,),(),(11nnkkkksususunksusususpnnkkkkkk, 2 , 1),(,),(),()(11nkuuupnkkk, 2 , 1,1第28页/共122页第二十九页，共122页。30,109731vvvvp)()(11111011ssfsfoptfSs,),()(211111nuusussp第29页/共122页第三十页，共122页。31), 2 , 1(nkuknkUuSsusTstsusususRRoptfkkkkkkkknnuun, 2, 1),(. .),(122111（

8、5）第30页/共122页第三十一页，共122页。32,21nuuu,121nnssss第31页/共122页第三十二页，共122页。33)(),(,),(),()(221111nnkksususususp 则对上述策略中所隐含的任一状态而言， 第k子过程上对应(duyng)于该状态的最优策略必然 包含在上述全过程最优策略p1*中，即为)(,),(),()(11nnkkkkkksusususp第32页/共122页第三十三页，共122页。34第33页/共122页第三十四页，共122页。35第34页/共122页第三十五页，共122页。36第35页/共122页第三十六页，共122页。37),(,),(1

9、11111,nkkkkknkkkknkssRussususR),(,111nkkkkkssRus第36页/共122页第三十七页，共122页。38nkiiiikkusgsR),()(),(iiiusg),(),(111nkkkkkkssRusgR第37页/共122页第三十八页，共122页。39 学习方法建议： 第一步 先看问题，充分理解问题的条件、情况及求解目标。 第二步 结合前面讲到的理论和解题过程，考虑如何着手进行求解该问题的工作。分析针对该动态规划问题的“四大要素、一个方程”这一步在开始时会感到困难，但是一定要下决心去思考，在思考过程中深入(shnr)理解前文讲到的概念和理论。4.动态规划

10、方法应用(yngyng)举例第38页/共122页第三十九页，共122页。40 第三步 动手把求解思路整理出来，或者说，把该问题作为习题独立的来做。 第四步 把自己的求解放到一边，看书中的求解方法，要充分(chngfn)理解教材中的论述。 第五步 对照自己 的求解，分析成败。 4.动态(dngti)规划方法应用举例第39页/共122页第四十页，共122页。414.动态规划(guhu)方法应用举例第40页/共122页第四十一页，共122页。42 2. 动态(dngti)规划基本方程 fn+1(xn+1) = 0 (边界条件) fk(xk) = opt urk ( xk , uk ) + fk+1(

11、xk+1) k = n,1（递推方程）4.动态规划方法应用(yngyng)举例第41页/共122页第四十二页，共122页。43第42页/共122页第四十三页，共122页。44BACBDBCDEC212312312511214106104131211396581052 阶段 1 阶段 2 阶段 3 阶段 4 阶段 5 求 最 短 路 径例5.5第43页/共122页第四十四页，共122页。45求 最 短 路 径第44页/共122页第四十五页，共122页。46fxvxdfxdDx4444455444()min (,)()()从 f5(x5)到 f4(x4)的递推过程用下表表示： x4D4(x4) x

12、5v4(x4,d4) v4(x4,d4)+f5(x5) f4(x4) 最优决策 d4*D1D1E E55+0=5*5D1ED2D2E E22+0=2*2D2E求 最 短 路 径第45页/共122页第四十六页，共122页。47f4(x4) 的表达式 x4 f4(x4) 最优决策 d4* D1 5 D1E D2 2 D2E 求 最 短 路 径第46页/共122页第四十七页，共122页。48从 f4(x4)到 f3(x3)的递推过程用表格表示如下： x3 D3(x3) x4 v3(x3,d3) v3(x3,d3)+f4(x4) f3(x3) 最优决策d3* C1 C1D1 C1D2 D1 D2 3

13、9 3+5=8* 9+2=11 8 C1D1 C2 C2D1 C2D2 D1 D2 6 5 6+5=11 5+2=7* 7 C2D2 C3 C3D1 C3D2 D1 D2 8 10 8+5=13 10+2=12* 12 C3D2 )(),(min)(44333)(33333xfdxvxfxDd 求 最 短 路 径第47页/共122页第四十八页，共122页。49x3 f3(x3) 最优决策d3* C1 8 C1D1 C2 7 C2D2 C3 12 C3D2 第二阶段的递推方程为： )(),(min)(33222)(22222xfdxvxfxDd从f3(x3)到f2(x2)的递推过程用表格表示如下

14、： 求 最 短 路 径第48页/共122页第四十九页，共122页。50 x2 D2(x2) x3 v2(x2,d2) v2(x2,d2)+f3(x3) f2(x2) 最优决策 d2* B1 B1C1 B1C2 B1C3 C1 C2 C3 12 14 10 12+8=20* 14+7=21 10+12=22 20 B1C1 B2 B2C1 B2C2 B2C3 C1 C2 C3 6 10 4 6+8=14* 10+7=17 4+12=16 14 B2C1 B3 B3C1 B3C2 B3C3 C1 C2 C3 13 12 11 13+8=21 12+7=19* 11+12=23 19 B3C2 求

15、最 短 路 径第49页/共122页第五十页，共122页。51x2 f2(x2) 最优决策 d2* B1 20 B1C1 B2 14 B2C1 B3 19 B3C2 求 最 短 路 径第50页/共122页第五十一页，共122页。52)(),(min)(22111)(11111xfdxvxfxDd 从f2(x2)到f1(x1)的递推过程用表格表示如下： x1 D1(x1) x2 v1(x1,d1) v1(x1,d1)+f2(x2) f1(x1) 最优决策 d1* A A B1 A B2 AB3 B1 B2 B3 2 5 1 2+20=22 5+14=19* 1+19=20 19 A B 2 求 最

16、 短 路 径第51页/共122页第五十二页，共122页。53x1 f1(x1) 最优决策 d1* A 19 A B2 从表达式f1(x1)可以看出，从A到E 的最短路径长度为 19。由f1(x1)向 f4(x4)回朔，得到最短路径为： A B2 C1 D1 E求 最 短 路 径第52页/共122页第五十三页，共122页。54 AB1B2C1C2C3C4D1D2D3E1E2 E3F1F2G531368766835338422123335526643第53页/共122页第五十四页，共122页。55此问题的基本方程为 fk(sk) Min dk(uk)+fk+1(sk+1) ukDk(sk) k6,

17、5,4,3,2,1 f7(s7)0按基本(jbn)方程由后向前递推有:第54页/共122页第五十五页，共122页。56AB1B2C1C2C3C4D1D2D3E1E2 E3F1F2G531368766835338422123335526643当k=6时S6U6D(U6)+F7(S7)F6(S6)F1F1G 4+0=4* 4F2F2G 3+0=3* 3第55页/共122页第五十六页，共122页。57当k=5时S5 U5 D(U5)+F6(S6) F5(S5) E1 E1F1 E1F2 3+4=7* 5+3=8 7 E2 E2F1 E2F2 5+4=9 2+3=5* 5 E3 E3F1 E3F2 6

18、+4=10 6+3=9* 9 AB1B2C1C2C3C4D1D2D3E1E2 E3F1F2G531368766835338422123335526643第56页/共122页第五十七页，共122页。58当k=4时S4U4D(U4)+F5(S5)F4(S4)D1D1E1D1E2 2+7=9 2+5=7* 7D2D2E2D2E3 1+5=6* 2+9=11 6D3D3E2D3E3 3+5=8* 3+9=12 8AB1B2C1C2C3C4D1D2D3E1E2 E3F1F2G531368766835338422123335526643第57页/共122页第五十八页，共122页。59当k=3时S3U3D(

19、U3)+F4(S4)F4(S4)C1C1D1C1D2 6+7=13* 8+6=14 13C2C2D1C2D2 3+7=10* 5+6=11 10C3C3D2C3D3 3+6=9* 3+8=11 9C4C4D2C4D3 8+6=14 4+8=12*12AB1B2C1C2C3C4D1D2D3E1E2 E3F1F2G531368766835338422123335526643第58页/共122页第五十九页，共122页。60当k=2时S4U4D(U4)+F5(S5)F4(S4)B1B1C1B1C2B1C3 1+13=14 3+10=13* 6+9=15 13B2B2C2B2C3B2C4 8+9=17

20、7+9=16* 6+12=18 16AB1B2C1C2C3C4D1D2D3E1E2 E3F1F2G531368766835338422123335526643第59页/共122页第六十页，共122页。61当k=1时S5U5D(U5)+F6(S6)F5(S5)AAB1AB2 5+13=18* 3+16=19 18AB1B2C1C2C3C4D1D2D3E1E2 E3F1F2G531368766835338422123335526643 由此可以看出，A到G的最短路(dunl)长为18，路径为： AB1C2D1E2F2G第60页/共122页第六十一页，共122页。62 (7) 按照基本方程递推求解。

21、按照基本方程递推求解。以上步骤是动态规划法处理问题的基本以上步骤是动态规划法处理问题的基本步骤，其中的前六步是建立动态规划模步骤，其中的前六步是建立动态规划模型的步骤。型的步骤。第61页/共122页第六十二页，共122页。63第62页/共122页第六十三页，共122页。64 项目投入资金ABC1 万元15 万吨13 万吨11 万吨2 万元28 万吨29 万吨30 万吨3 万元40 万吨43 万吨45 万吨4 万元51 万吨55 万吨58 万吨求对三个项目的最优投资(tu z)分配，使总投资(tu z)效益最大。资 源 分 配 问 题第63页/共122页第六十四页，共122页。65fk(xk)=

22、maxvk(xk ,dk)+fk+1(xk+1)8.终端条件：f4(x4)=0资 源 分 配 问 题第64页/共122页第六十五页，共122页。66x3D3(x3)x4v3(x3,d3)v3(x3,d3)+f4(x4)f3(x3)d3*00000+0=0000100+0=01101111+0=11*1110200+0=0111111+0=112203030+0=30*3020300+0=0121111+0=11213030+0=303304545+0=45*4530400+0=0131111+0=11223030+0=30314545+0=454405858+0=58*584资 源 分 配 问

23、 题第65页/共122页第六十六页，共122页。67x2D2(x2)x3v2(x2,d2)v2(x2,d2)+f3(x3)f2(x2)d2*00000+0=0000100+11=111101313+0=13*1310200+30=30*111313+11=242202929+0=293000300+45=45*121313+30=43212929+11=403304343+0=434500400+58=58131313+45=58222929+30=59*314343+11=544405555+0=55592资 源 分 配 问 题第66页/共122页第六十七页，共122页。68x1D1(x1)

24、x2v1(x1,d1)v1(x1,d1)+f2(x2)f1(x1)d1*0400+59=59131515+45=60*222828+30=58314040+13=534405151+0=51601最优解为 x1=4, d1*=1, x2=x1-d1=3, d2*=0, x3=x2-d2*=3, d3=3, x4=x3-d3=0， 即项目 A 投资 1 万元，项目 B 投资 0 万元，项目 C 投资 3 万元，最大效益为 60 万吨。 资 源 分 配 问 题第67页/共122页第六十八页，共122页。69第68页/共122页第六十九页，共122页。70 设有n种物品，每一种物品数量无限。 第i种

25、物品每件重量为wi， 每件价值ci。现有一只可装载重量为 W 的背包，求各种物品应各取多少件放入背包， 使背包中物品的价值最高。 这个问题可以用整数规划模型来描述。 设第i种物品取xi件 （i=1,2,n，xi为非负整数） ，背包中物品的价值为z，则 背 包 问 题第69页/共122页第七十页，共122页。71背 包 问 题第70页/共122页第七十一页，共122页。72wkdk)wkdk)8. 8. 终端条件：终端条件：fn+1(xn+1)=0fn+1(xn+1)=0背 包 问 题第71页/共122页第七十二页，共122页。7330max)(max)(3/04433/033333333dxf

26、dcxfwxdwxd列出f3(x3)的数值表 背 包 问 题第72页/共122页第七十三页，共122页。74x3 D3(x3) x4 30d3+f4(x4) f3(x3) d3* 0 0 0 0+0=0 0 0 1 0 1 1 0 0+0=0 30+0=30* 30 1 2 0 1 2 2 1 0 0+0=0 30+0=30 60+0=60* 60 2 3 0 1 2 3 3 2 1 0 0+0=0 30+0=30 60+0=60 90+0=90* 90 3 4 0 1 2 3 4 4 3 2 1 0 0+0=0 30+0=30 60+0=60 90+0=90 120+0=120* 120 4

27、 5 0 1 2 3 4 5 5 4 3 2 1 0 0+0=0 30+0=30 60+0=60 90+0=90 120+0=120 150+0=150* 150 5 第73页/共122页第七十四页，共122页。75对于k=2 )3(80max)(max)(22323/03322/02222222dxfdxfdcxfxdwxd 列出 f2(x2)的数值表 x2 D2(x2) x3 80d2+f3(x3) f2(x2) d2* 0 0 0 0+f3(0)=0+0=0* 0 0 1 0 1 0+f3(1)=0+30=30* 30 0 2 0 2 0+f2(2)=0+60=60* 60 0 3 0

28、1 3 0 0+f3(3)=0+90=90* 80+f3(0)=80+0=80 90 0 4 0 1 4 1 0+f3(4)=0+120=120* 80+f3(1)=80+30=110 120 0 5 0 1 5 2 0+f3(5)=0+150=150* 80+f3(2)=80+60=140 150 0 第74页/共122页第七十五页，共122页。76对于对于k k=1=1 )2(65max)(max)(11212/02211/01111111dxfdxfdcxfxdwxd 列出列出f f1 1( (x x1 1) )的数值的数值 x x1 1 D D1 1( (x x1 1) ) x x2

29、2 6565d d1 1+ +f f2 2( (x x2 2) ) f f1 1( (x x1 1) ) d d1 1* * 0 0 0 0 0 0 0+0+f f2 2(0)=0+0=0*(0)=0+0=0* 0 0 0 0 1 1 0 0 1 1 0+0+f f2 2(1)=0+30=30*(1)=0+30=30* 3030 0 0 2 2 0 0 1 1 2 2 0 0 0+0+f f2 2(2)=0+60=60(2)=0+60=60 65+65+f f2 2(0)=65+0=65*(0)=65+0=65* 6565 1 1 3 3 0 0 1 1 3 3 1 1 0+0+f f2 2(

30、3)=0+90=90(3)=0+90=90 65+65+f f2 2(1)=65+30=95*(1)=65+30=95* 9595 1 1 4 4 0 0 1 1 2 2 4 4 2 2 0 0 0+0+f f2 2(4)=(4)=0+120=1200+120=120 65+65+f f2 2(2)=65+60=125(2)=65+60=125 130+130+f f2 2(0)=130+0=130*(0)=130+0=130* 130130 2 2 5 5 0 0 1 1 2 2 5 5 3 3 1 1 0+0+f f2 2(5)=0+150=150(5)=0+150=150 65+65+f

31、 f2 2(3)=65+90=155(3)=65+90=155 130+130+f f2(1)=130+30=160*2(1)=130+30=160* 160160 2 2 第75页/共122页第七十六页，共122页。77由题意知，x1=5，由表f1(x1)、f2(x2)、f3(x3)，经回朔可得： d1*=2，x2=x1-2d1=1，d2*=0，x3=x2-3d2=1，d3*=1，x4=x3-d3=0 即应取第一种物品 2 件,第三种物品 1 件,最高价值为 160 元,背包没有余量。由f1(x1)得列表可以看出，如果背包得容量为W=4，W=3，W=2 和W=1 时，相应的最优解立即可以得到

32、。 第76页/共122页第七十七页，共122页。78第77页/共122页第七十八页，共122页。79 最短路径问题和背包问题的状态变量和决策变量都只能取离散的整数值。 当状态变量和决策变量的取值范围很大， 或者这些变量是连续的， 用列举的方法就比较困难或者根本不可能了。 这就需要用连续变量的处理方法。 例 5.8:某种机器可以在高、低两种负荷下生产。高负荷生产条件下机器完好率为 0.7，即如果年初有u台完好机器投入生产，则年末完好的机器数量为0.7u台。系数 0.7 称为完好率。年初投入高负荷运行的u台机器的年产量为 8u吨。系数 8 称为单台产量。低负荷运行时，机器完好率为 0.9，单台产量

33、为5 吨。设开始时有 1000 台完好机器，要制订五年计划，每年年初将完好的机器一部分分配到高负荷生产， 剩下的机器分配到低负荷生产， 使五年的总产量为最高。 第78页/共122页第七十九页，共122页。80 机器负荷分配(fnpi)问题第79页/共122页第八十页，共122页。81 根据题意， 本题的决策允许集合应该是一个整数集合， 但由于决策允许集合中可取的决策数量很大， 一一列举计算量很大， 不妨认为状态变量和决策变量都是连续的， 得到最优解后，再作取整处理。 机器(j q)负荷分配问题第80页/共122页第八十一页，共122页。82 机器负荷分配(fnpi)问题第81页/共122页第八

34、十二页，共122页。83 机器负荷分配(fnpi)问题第82页/共122页第八十三页，共122页。84 机器负荷(fh)分配问题第83页/共122页第八十四页，共122页。85 机器(j q)负荷分配问题第84页/共122页第八十五页，共122页。86 机器(j q)负荷分配问题第85页/共122页第八十六页，共122页。87d4*=x4=567, x5=0.7d4+0.9(x4-d4)=397d5*=x5=397, x6=0.7d5+0.9(x5-d5)=278 机器负荷分配(fnpi)问题第86页/共122页第八十七页，共122页。88 机器负荷分配(fnpi)问题第87页/共122页第八

35、十八页，共122页。89tniitniikkkpppk0112121)1(01)( 机器负荷分配(fnpi)问题第88页/共122页第八十九页，共122页。90第89页/共122页第九十页，共122页。91月份月份(k) 1 2 3 4 5 6 7 生产成本生产成本(ck) 11 18 13 17 20 10 15 需求量需求量(rk) 0 8 5 3 2 7 4 为了调节生产生产和需求， 工厂建为了调节生产生产和需求， 工厂建设有一个产品仓库，库容量设有一个产品仓库，库容量H H=9=9。已知。已知期初库存量为期初库存量为 2 2，要求期末（七月底），要求期末（七月底）库存量为库存量为 0

36、0。 每个月生产的产品在月末。 每个月生产的产品在月末入库，月初根据当月需求发货。求七入库，月初根据当月需求发货。求七个月的生产量，能满足各月的需求，个月的生产量，能满足各月的需求，并使生产成本最低。并使生产成本最低。 生 产 库 存 问 题第90页/共122页第九十一页，共122页。92；n阶段指标：vk(xk ,dk)=ckdk；n终端条件：f8(x8)=0,x8=0；生 产 库 存 问 题第91页/共122页第九十二页，共122页。93生 产 库 存 问 题第92页/共122页第九十三页，共122页。94生 产 库 存 问 题第93页/共122页第九十四页，共122页。95生 产 库 存

37、 问 题第94页/共122页第九十五页，共122页。96生 产 库 存 问 题第95页/共122页第九十六页，共122页。97生 产 库 存 问 题第96页/共122页第九十七页，共122页。98 由于(yuy) 在f4(x4)的表达式中d4的系数是-3， 因此d4在决策允许集合中应取集合中的最大值，即d4=12-x4由此 f4(x4)=-3(12-x4)-20 x4+280 =-17x4+244生 产 库 存 问 题第97页/共122页第九十八页，共122页。99生 产 库 存 问 题第98页/共122页第九十九页，共122页。100生 产 库 存 问 题第99页/共122页第一百页，共12

38、2页。101生 产 库 存 问 题第100页/共122页第一百零一页，共122页。102生 产 库 存 问 题第101页/共122页第一百零二页，共122页。103k 1 2 3 4 5 6 7 ck 11 18 13 17 20 10 15 rk 0 8 5 3 2 7 4 xk 2 9 5 9 9 7 4 dk 7 13-x2=4 14-x3=9 12-x4=3 9-x5=0 11-x6=4 0 生 产 库 存 问 题第102页/共122页第一百零三页，共122页。104第103页/共122页第一百零四页，共122页。105设 备 更 新 问 题第104页/共122页第一百零五页，共122

39、页。106阶段k：运行年份； 状态变量xk：设备的役龄t； 决策变量dk： 继续使用更新)()(ReKeepKplaceRdk 状态转移方程： KdxRdxkkkk111 阶段指标： KdtCRdtSCPKdxCRdxSCPvkkkkkkk)()()0()()()0( 第105页/共122页第一百零六页，共122页。107递推方程： KdtftCRdftSCPKdxfxCRdxfxSCPxfkkkkkkkkkkkkkk) 1()() 1 ()()0(min)()()()()0(min)(111111 终端条件： fn(t)=-R(t) 设 备 更 新 问 题第106页/共122页第一百零七页，

40、共122页。108T 0 1 2 3 4 5 6 7 C(t) 10 13 20 40 70 100 100 - S(t) - 32 21 11 5 0 0 0 R(t) - 25 17 8 0 0 0 0 且 n=5，T=2，P=50 由上表开始，终端条件为： f6(1)=-25，f6(2)=-17，f6(3)=-8 f6(4)=f6(5)=f6(6)=f6(7)=0 设 备 更 新 问 题第107页/共122页第一百零八页，共122页。109 对于k=5: KdRdtftCftSCPtf55665) 1()() 1 ()() 0(min)( KdfCfSCPf*5665, 443min)1

41、7(13)25(321050min) 2() 1 () 1 () 1 () 0(min) 1 ( KdfCfSCPf*5665,121214min) 8(20)25(211050min) 3 () 2() 1 () 2() 0(min) 2( 第108页/共122页第一百零九页，共122页。110RdfCfSCPf*5665,244024min040)25(111050min)4() 3 () 1 () 3 ()0(min) 3 ( RdfCfSCPf*5665,307030min070)25(51050min)5()4() 1 ()4()0(min)4(RdfCfSCPf*5665,3510

42、035min0100)25(01050min) 6() 5 () 1 () 5 () 0(min) 5 (第109页/共122页第一百一十页，共122页。111RdfCfSCPf*5665,3510035min0100)25(01050min)7() 6() 1 () 6() 0(min) 6( KdRdtftCftSCPtf44554) 1()() 1 ()() 0 (min)( RdfCfSCPf*4554,242524min1213) 4(321050min) 2() 1 () 1 () 1 () 0(min) 1 ( 对于k=4: 第110页/共122页第一百一十一页，共122页。11

43、2RdfCfSCPf*4554,354435min2420)4(211050min)3()2()1 ()2()0(min)2( RdfCfSCPf*4554,457045min3040)4(111050min)4()3() 1 ()3()0(min)3( 第111页/共122页第一百一十二页，共122页。113 RdfCfSCPf*4554,5110551min3570) 4(51050min) 5() 4() 1 () 4() 0(min) 4( RdfCfSCPf*5554,5613556min35100) 4(01050min) 6() 5 () 1 () 5 () 0(min) 5 (

44、 第112页/共122页第一百一十三页，共122页。114 对于k=3: KdRdtftCftSCPtf33443) 1()() 1 ()() 0 (min)( KdfCfSCPf*3443,484852min351324321050min)2() 1 () 1 () 1 ()0(min) 1 ( 第113页/共122页第一百一十四页，共122页。115 RdfCfSCPf*3443,739173min514024111050min)4()3() 1 ()3()0(min)3( RdfCfSCPf*3443,7912679min56702451050min)5()4() 1 ()4()0(mi

45、n)4( RdfCfSCPf*3443,636563min452024211050min) 3()2() 1 ()2()0(min)2(第114页/共122页第一百一十五页，共122页。116 KdRdtftCftSCPtf22332) 1()() 1 ()()0(min)( RdKdfCfSCPf*2*2332,767676min631348321050min)2()1 ()1 ()1 ()0(min)1 (或者 RdfCfSCPf*2332,879387min732048211050min)3()2() 1 ()2()0(min)2( 对于k=2: 第115页/共122页第一百一十六页，共

46、122页。117 对于k=1: KdRdtftCftSCPtf11221) 1()() 1 ()()0(min)(RdfCfSCPf*1221,115117115min972076211050min) 3()2() 1 ()2()0(min)2(RdfCfSCPf*2332,7311997min794048111050min)4() 3() 1 () 3()0(min) 3(97第116页/共122页第一百一十七页，共122页。118年份年份 1 1 2 2 3 3 4 4 5 5 决策决策 1 1 更新更新 更新更新 继续继续 更新更新 继续继续 决策决策 2 2 更新更新 继续继续 更新更

47、新 更新更新 继续继续 这两个(lin )决策是 设 备 更 新 问 题第117页/共122页第一百一十八页，共122页。119Zxxxxxxt sxxxxxxz321321321232221,4. .5342minM=4, N=312111)(uuug2222232)(uuug3233354)(uuug 余下的解法过程和资源分配问题类似。不过这里是连续(linx)情形，详细过程见下例。第118页/共122页第一百一十九页，共122页。120例 用动态规划法求解如下几何规划（一种特殊的非线性规划）问题。. 0, 6. .max32132133221xxxxxxtsxxxz令 ， ， ，则目标函

48、数为21)(xxgxxg)(233)(xxg)()()(332211xgxgxgz对非负实数u，令则原问题等价于求解 f3(6) , 3 , 2 , 1,0| )(max)(11kuxxgufkiikiiik递推方程. 3 , 2),()(max)(111011kxgxufufkkkkuxkk第119页/共122页第一百二十页，共122页。121边界条件为 11122111100( )max()max|xuxuxuf ugxxu2222212222200341273( )max()()max()|xuxuxuf uf ux gxuxxu333334323333327006114322( )max()()max()|xuxuxuf ufuxgxuxxu状态转移方程 1kkxux第120页/共122页第一百二十一页，共122页。1221086)6(643113* fz*3*23*1321321()13()2xuxuxxuxx第121页/共122页第一百二十二页，共122页。