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

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

2、共122页5 属于多阶段决策类的问题很多，例如：第4页/共122页6此就需要综合权衡决定设备的使用年限，使总的经济效益最好。第5页/共122页7第6页/共122页8策问题，应用动态规划方法加以策问题，应用动态规划方法加以解决解决。第7页/共122页9论这个问题论这个问题) )。第8页/共122页10第9页/共122页11图11 运输网络图示第10页/共122页12程。所谓无后效性，又称马尔程。所谓无后效性，又称马尔柯夫性，是指系统从某个阶段柯夫性，是指系统从某个阶段往后的发展，仅由本阶段所处往后的发展，仅由本阶段所处的状态及其往后的决策所决定，的状态及其往后的决策所决定，与系统以前经历的状态和

3、决策与系统以前经历的状态和决策( (历史历史) )无关无关。第11页/共122页13多阶段决策过程特点:要点：阶段，状态，决策，状态转移方程，k-后部子过程状态 x1阶段1T1决策u1状态 x2决策u2阶段2T2状态 x3.状态 xk决策uk阶段kTk状态 xk+1.状态 xn决策un阶段nTn状态 xn+1第12页/共122页14第13页/共122页15v1 v3 v5 v8 v10，全程长度是20；显然，这种方法的结果常是错误的第14页/共122页16方法总是从过程的最后阶段开始考虑，然后逆着实际过程发展的顺序，逐段向前递推计算直至始点。第15页/共122页17第16页/共122页18第1

4、7页/共122页19量叫作量叫作阶段变量阶段变量，一般以，一般以k k表示表示阶段变量阶段数等于多段决阶段变量阶段数等于多段决策过程从开始到结束所需作出策过程从开始到结束所需作出决策的数目。决策的数目。第18页/共122页20称称输入状态和输出状态输入状态和输出状态，阶段，阶段k k的初始状态记作的初始状态记作s sk k，终止状态记，终止状态记为为s sk+1k+1。但为了清楚起见，。但为了清楚起见，通常通常定义阶段的状态即指其初始状态定义阶段的状态即指其初始状态。第19页/共122页21第20页/共122页22第21页/共122页23第22页/共122页24)(,(1kkkkksusTs(

5、1)第23页/共122页25指标函数可以是诸如费用、成本、产值、利润、产量、耗量、距离、时间、效用，等等。第24页/共122页26kk,kk还跟该子过程策略pk(sk)有关，因此它是sk和pk(sk)的函数，严格说来，应表示为:)(,(kkkkspsR第25页/共122页27),(),(),(),(11111,nnnkkkkkknnkkkknknkusgusgusgusususRR (2)第26页/共122页28nkiiiikusgR),(nkiiiikusgR),(第27页/共122页29nkspsRoptsfkkkksPpkkkKk, 2 , 1),(,()()()(,(kkkkspsR)

6、(,),(),(11nnkkkksususunksusususpnnkkkkkk, 2 , 1),(,),(),()(11nkuuupnkkk, 2 , 1,1第28页/共122页30,109731vvvvp)()(11111011ssfsfoptfSs,),()(211111nuusussp第29页/共122页31), 2 , 1(nkuknkUuSsusTstsusususRRoptfkkkkkkkknnuun, 2, 1),(. .),(122111（5）第30页/共122页32,21nuuu,121nnssss第31页/共122页33)(),(,),(),()(221111nnkksu

7、susususp 则对上述策略中所隐含的任一状态而言， 第k子过程上对应于该状态的最优策略必然 包含在上述全过程最优策略p1*中，即为)(,),(),()(11nnkkkkkksusususp第32页/共122页34有所不同的，动态规划中的状态变量必须具备以下三个特征：第33页/共122页35第34页/共122页36第35页/共122页37),(,),(111111,nkkkkknkkkknkssRussususR),(,111nkkkkkssRus第36页/共122页38nkiiiikkusgsR),()(),(iiiusg),(),(111nkkkkkkssRusgR第37页/共122页3

8、9 学习方法建议： 第一步 先看问题，充分理解问题的条件、情况及求解目标。 第二步 结合前面讲到的理论和解题过程，考虑如何着手进行求解该问题的工作。分析针对该动态规划问题的“四大要素、一个方程”这一步在开始时会感到困难，但是一定要下决心去思考，在思考过程中深入理解前文讲到的概念和理论。4.动态规划方法应用举例第38页/共122页40 第三步 动手把求解思路整理出来，或者说，把该问题作为习题独立的来做。 第四步 把自己的求解放到一边，看书中的求解方法，要充分理解教材中的论述。 第五步 对照自己 的求解，分析成败。 4.动态规划方法应用举例第39页/共122页414.动态规划方法应用举例第40页/

9、共122页42 2. 动态规划基本方程 fn+1(xn+1) = 0 (边界条件) fk(xk) = opt urk ( xk , uk ) + fk+1(xk+1) k = n,1（递推方程）4.动态规划方法应用举例第41页/共122页43第42页/共122页44BACBDBCDEC212312312511214106104131211396581052 阶段 1 阶段 2 阶段 3 阶段 4 阶段 5 求 最 短 路 径例5.5第43页/共122页45求 最 短 路 径第44页/共122页46fxvxdfxdDx4444455444()min (,)()()从 f5(x5)到 f4(x4)

10、的递推过程用下表表示： x4D4(x4) x5v4(x4,d4) v4(x4,d4)+f5(x5) f4(x4) 最优决策 d4*D1D1E E55+0=5*5D1ED2D2E E22+0=2*2D2E求 最 短 路 径第45页/共122页47f4(x4) 的表达式 x4 f4(x4) 最优决策 d4* D1 5 D1E D2 2 D2E 求 最 短 路 径第46页/共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 9

11、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页49x3 f3(x3) 最优决策d3* C1 8 C1D1 C2 7 C2D2 C3 12 C3D2 第二阶段的递推方程为： )(),(min)(33222)(22222xfdxvxfxDd从f3(x3)到f2(x2)的递推过程用表格表示如下： 求 最 短 路 径第48

12、页/共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 求 最 短 路 径第49页/共122页51x2 f2(x

13、2) 最优决策d2* B1 20 B1C1 B2 14 B2C1 B3 19 B3C2 求 最 短 路 径第50页/共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 求 最 短 路 径第51页/共122页53x1 f1(x1) 最优决策 d1* A 19 A B2 从表达

14、式f1(x1)可以看出，从A到E 的最短路径长度为 19。由f1(x1)向 f4(x4)回朔，得到最短路径为： A B2 C1 D1 E求 最 短 路 径第52页/共122页54 AB1B2C1C2C3C4D1D2D3E1E2 E3F1F2G531368766835338422123335526643第53页/共122页55此问题的基本方程为 fk(sk) Min dk(uk)+fk+1(sk+1) ukDk(sk) k6,5,4,3,2,1 f7(s7)0按基本方程由后向前递推有:第54页/共122页56AB1B2C1C2C3C4D1D2D3E1E2 E3F1F2G5313687668353

15、38422123335526643当k=6时S6U6D(U6)+F7(S7)F6(S6)F1F1G 4+0=4* 4F2F2G 3+0=3* 3第55页/共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+4=10 6+3=9* 9 AB1B2C1C2C3C4D1D2D3E1E2 E3F1F2G531368766835338422123335526643第56页/共122页58当k=4时S4U4D(U4)+F5(S5)F4(S4)

16、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页59当k=3时S3U3D(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*12AB1B2C1C2C3C4D

17、1D2D3E1E2 E3F1F2G531368766835338422123335526643第58页/共122页60当k=2时S4U4D(U4)+F5(S5)F4(S4)B1B1C1B1C2B1C3 1+13=14 3+10=13* 6+9=15 13B2B2C2B2C3B2C4 8+9=17 7+9=16* 6+12=18 16AB1B2C1C2C3C4D1D2D3E1E2 E3F1F2G531368766835338422123335526643第59页/共122页61当k=1时S5U5D(U5)+F6(S6)F5(S5)AAB1AB2 5+13=18* 3+16=19 18AB1B2C

18、1C2C3C4D1D2D3E1E2 E3F1F2G531368766835338422123335526643 由此可以看出，A到G的最短路长为18，路径为： AB1C2D1E2F2G第60页/共122页62第61页/共122页63第62页/共122页64 项目投入资金ABC1 万元15 万吨13 万吨11 万吨2 万元28 万吨29 万吨30 万吨3 万元40 万吨43 万吨45 万吨4 万元51 万吨55 万吨58 万吨求对三个项目的最优投资分配，使总投资效益最大。资 源 分 配 问 题第63页/共122页65kkkk ,kk+1(xk+1)8.终端条件：f4(x4)=0资 源 分 配 问

19、 题第64页/共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资 源 分 配 问 题第65页/共122页67x2D2(x2)x3v2(x2,d2)v2(x2,d2)+f3(x3)f2(x2)d2*00

20、000+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页68x1D1(x1)x2v1(x1,d1)v1(x1,d1)+f2(x2)f1(x1)d1*0400+59=59131515+45=60*222828+30=58314040+13=534

21、405151+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页69第68页/共122页70 设有n种物品，每一种物品数量无限。 第i种物品每件重量为wi， 每件价值ci。现有一只可装载重量为 W 的背包，求各种物品应各取多少件放入背包， 使背包中物品的价值最高。 这个问题可以用整数规划模型来描述。 设第i种物品取xi件 （i=1,2,n，xi为非负

22、整数） ，背包中物品的价值为z，则 背 包 问 题第69页/共122页71背 包 问 题第70页/共122页72背 包 问 题第71页/共122页7330max)(max)(3/04433/033333333dxfdcxfwxdwxd列出f3(x3)的数值表 背 包 问 题第72页/共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+

23、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 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页75对于k=2 )3(80max)(max)(22323/03322/02222222dxfdxfdcxfxdwxd 列出 f2(x2)的数值表 x2 D2(x2) x3 80d2+f3(x3) f2(x2) d2* 0

24、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 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页76对于对于k k=1=1 )2(65max)(max)(11212/02211/01111111dxfdx

25、fdcxfxdwxd 列出列出f f1 1( (x x1 1) )的数值的数值 x x1 1 D D1 1( (x x1 1) ) x x2 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+

26、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(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

27、 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 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页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 元,背包

28、没有余量。由f1(x1)得列表可以看出，如果背包得容量为W=4，W=3，W=2 和W=1 时，相应的最优解立即可以得到。 第76页/共122页78第77页/共122页79 最短路径问题和背包问题的状态变量和决策变量都只能取离散的整数值。 当状态变量和决策变量的取值范围很大， 或者这些变量是连续的， 用列举的方法就比较困难或者根本不可能了。 这就需要用连续变量的处理方法。 例 5.8:某种机器可以在高、低两种负荷下生产。高负荷生产条件下机器完好率为 0.7，即如果年初有u台完好机器投入生产，则年末完好的机器数量为0.7u台。系数 0.7 称为完好率。年初投入高负荷运行的u台机器的年产量为 8u吨

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

30、2页84 机器负荷分配问题第83页/共122页85 机器负荷分配问题第84页/共122页86 机器负荷分配问题第85页/共122页87x5=0.7d4+0.9(x4-d4)=397nd5*=x5=397, x6=0.7d5+0.9(x5-d5)=278 机器负荷分配问题第86页/共122页88 机器负荷分配问题第87页/共122页89tniitniikkkpppk0112121)1(01)( 机器负荷分配问题第88页/共122页90第89页/共122页91月份月份(k) 1 2 3 4 5 6 7 生产成本生产成本(ck) 11 18 13 17 20 10 15 需求量需求量(rk) 0 8

31、 5 3 2 7 4 为了调节生产生产和需求， 工厂建为了调节生产生产和需求， 工厂建设有一个产品仓库，库容量设有一个产品仓库，库容量H H=9=9。已知。已知期初库存量为期初库存量为 2 2，要求期末（七月底），要求期末（七月底）库存量为库存量为 0 0。 每个月生产的产品在月末。 每个月生产的产品在月末入库，月初根据当月需求发货。求七入库，月初根据当月需求发货。求七个月的生产量，能满足各月的需求，个月的生产量，能满足各月的需求，并使生产成本最低。并使生产成本最低。 生 产 库 存 问 题第90页/共122页92nvkxk ,dkckdk；n终端条件：f8(x8)=0,x8=0；生 产 库

32、存 问 题第91页/共122页93生 产 库 存 问 题第92页/共122页94生 产 库 存 问 题第93页/共122页95生 产 库 存 问 题第94页/共122页96生 产 库 存 问 题第95页/共122页97生 产 库 存 问 题第96页/共122页98 由于 在f4(x4)的表达式中d4的系数是-3， 因此d4在决策允许集合中应取集合中的最大值，即d4=12-x4由此 f4(x4)=-3(12-x4)-20 x4+280 =-17x4+244生 产 库 存 问 题第97页/共122页99生 产 库 存 问 题第98页/共122页100生 产 库 存 问 题第99页/共122页101

33、生 产 库 存 问 题第100页/共122页102生 产 库 存 问 题第101页/共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页104第103页/共122页105设 备 更 新 问 题第104页/共122页106阶段k：运行年份； 状态变量xk：设备的役龄t； 决策变量dk： 继续使用更新)()(ReKeepKplaceRdk 状态转移方程：

34、 KdxRdxkkkk111 阶段指标： KdtCRdtSCPKdxCRdxSCPvkkkkkkk)()()0()()()0( 第105页/共122页107递推方程： KdtftCRdftSCPKdxfxCRdxfxSCPxfkkkkkkkkkkkkkk) 1()() 1 ()()0(min)()()()()0(min)(111111 终端条件： fn(t)=-R(t) 设 备 更 新 问 题第106页/共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

35、 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页109 对于k=5: KdRdtftCftSCPtf55665) 1()() 1 ()() 0(min)( KdfCfSCPf*5665, 443min)17(13)25(321050min) 2() 1 () 1 () 1 () 0(min) 1 ( KdfCfSCPf*5665,121214min) 8(20)25(211050min) 3 () 2() 1 () 2(

36、) 0(min) 2( 第108页/共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,3510035min0100)25(01050min) 6() 5 () 1 () 5 () 0(min) 5 (第109页/共122页111RdfCfSCPf*5665,3510035min0100)25(01050min)7 () 6 () 1 ()

37、 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页112RdfCfSCPf*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页113 Rd

38、fCfSCPf*4554,5110551min3570) 4(51050min) 5() 4() 1 () 4() 0(min) 4( RdfCfSCPf*5554,5613556min35100) 4(01050min) 6 () 5 () 1 () 5 () 0 (min) 5 ( 第112页/共122页114 对于k=3: KdRdtftCftSCPtf33443) 1()() 1 ()() 0 (min)( KdfCfSCPf*3443,484852min351324321050min)2() 1 () 1 () 1 ()0(min) 1 ( 第113页/共122页115 RdfCfSCPf*3443,739173min514024111050min)4()3() 1 ()3()0(min)3( Rdf