数学建模动态规划课件.ppt

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

2、是多阶段决策问题。图1 运输网络图示多阶段决策过程特点多阶段决策过程特点:要点：要点：阶段，状态，决策，状态转阶段，状态，决策，状态转移方程，移方程，k k-后部子过程后部子过程状态状态 x x1 1阶段阶段1 1T T1 1决策决策u u1 1状态状态 x x2 2决策决策u u2 2阶段阶段2 2T T2 2状态状态 x x3 3.状态状态 x xk k决策决策u uk k阶段阶段k kT Tk k状态状态 x xk k+1+1.状态状态 x xn n决策决策u un n阶段阶段n nTnTn状态状态 x xn n+1+1)(,(1kkkkksusTs(1)(,(kkkkspsR),(),

3、(),(),(11111,nnnkkkkkknnkkkknknkusgusgusgusususRR(2)nkiiiikusgR),(nkiiiikusgR),()(,(kkkkspsRnkspsRoptsfkkkksPpkkkKk,2,1),(,()()()(,),(),(11nnkkkksususunksusususpnnkkkkkk,2,1),(,),(),()(11nkuuupnkkk,2,1,1,109731vvvvp)()(11111011ssfsfoptfSs,),()(211111nuusussp),2,1(nkuknkUuSsusTstsusususRRoptfkkkkkkkk

4、nnuun,2,1),(.),(122111（5）,21nuuu,121nnssss)(),(,),(),()(221111nnkksususususp 则对上述策略中所隐含的任一状态而言，第k子过程上对应于该状态的最优策略必然 包含在上述全过程最优策略p1*中，即为)(,),(),()(11nnkkkkkksusususp),(,),(111111,nkkkkknkkkknkssRussususR),(,111nkkkkkssRusnkiiiikkusgsR),()(),(iiiusg),(),(111nkkkkkkssRusgR4.4.动态规划方法应用举例动态规划方法应用举例 2.动态规划

5、基本方程 fn+1(xn+1)=0 (边界条件)fk(xk)=opt urk(xk,uk)+fk+1(xk+1)k=n,14.4.动态规划方法应用举例动态规划方法应用举例BACBDBCDEC212312312511214106104131211396581052 阶段1 阶段2 阶段3 阶段4 阶段5 fxvxdfxdDx4444455444()min(,)()()从 f5(x5)到 f4(x4)的 递 推 过 程 用 下 表 表 示：x4D4(x4)x5v4(x4,d4)v4(x4,d4)+f5(x5)f4(x4)最优决策 d4*D1D1E E55+0=5*5D1ED2D2E E22+0=2

6、*2D2Ef4(x4)的表达式 x4 f4(x4)最优决策 d4*D1 5 D1E D2 2 D2E 从 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 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 x3

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

8、1 B3 B3C1 B3C2 B3C3 C1 C2 C3 13 12 11 13+8=21 12+7=19*11+12=23 19 B3C2 x2 f2(x2)最优决策d2*B1 20 B1C1 B2 14 B2C1 B3 19 B3C2 )(),(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 x1 f1

9、(x1)最优决策 d1*A 19 A B2 从表达式f1(x1)可以看出，从A到E 的最短路径长度为 19。由f1(x1)向 f4(x4)回朔，得到最短路径为：A B2 C1 D1 E 项目投入资金ABC1 万元15 万吨13 万吨11 万吨2 万元28 万吨29 万吨30 万吨3 万元40 万吨43 万吨45 万吨4 万元51 万吨55 万吨58 万吨求对三个项目的最优投资分配，使总投资效益最大。x3D3(x3)x4v3(x3,d3)v3(x3,d3)+f4(x4)f3(x3)d3*00000+0=0000100+0=01101111+0=11*1110200+0=0111111+0=112

10、203030+0=30*3020300+0=0121111+0=11213030+0=303304545+0=45*4530400+0=0131111+0=11223030+0=30314545+0=454405858+0=58*584x2D2(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=58131

11、313+45=58222929+30=59*314343+11=544405555+0=55592x1D1(x1)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 万吨。设有n种物品，每一种物品数量无限。第i种物品每件重量为wi，每件

12、价值ci。现有一只可装载重量为 W 的背包，求各种物品应各取多少件放入背包，使背包中物品的价值最高。这个问题可以用整数规划模型来描述。设第i种物品取xi件（i=1,2,n，xi为非负整数），背包中物品的价值为z，则 3333333333440/30/()max()max 30dswdswf sc df sd 最短路径问题和背包问题的状态变量和决策变量都只能取离散的整数值。当状态变量和决策变量的取值范围很大，或者这些变量是连续的，用列举的方法就比较困难或者根本不可能了。这就需要用连续变量的处理方法。例例 5 5.8 8:某种机器可以在高、低两种负荷下生产。高负荷生产条件下机器完好率为 0.7，即

13、如果年初有u台完好机器投入生产，则年末完好的机器数量为0.7u台。系数 0.7 称为完好率。年初投入高负荷运行的u台机器的年产量为 8u吨。系数 8 称为单台产量。低负荷运行时，机器完好率为 0.9，单台产量为5 吨。设开始时有 1000 台完好机器，要制订五年计划，每年年初将完好的机器一部分分配到高负荷生产，剩下的机器分配到低负荷生产，使五年的总产量为最高。根据题意，本题的决策允许集合应该是一个整数集合，但由于决策允许集合中可取的决策数量很大，一一列举计算量很大，不妨认为状态变量和决策变量都是连续的，得到最优解后，再作取整处理。tniitniikkkpppk0112121)1(01)(月份(

14、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=9。已 知 期初 库 存 量 为 2，要 求 期 末（七 月 低）库存 量 为 0。每 个 月 生 产 的 产 品 在 月 末 入库，月 初 根 据 当 月 需 求 发 货。求 七 个月 的 生 产 量，能 满 足 各 月 的 需 求，并使 生 产 成 本 最 低。由于 在f4(x4)的表达式中d4的系数是-3，因此d4在决策允许集合中应取集合中的最大值，即d4=12-

15、x4由此 f4(x4)=-3(12-x4)-20 x4+280=-17x4+244k 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 阶段k：运行年份；状态变量xk：设备的役龄t；决策变量dk：继续使用更新)()(ReKeepKplaceRdk 状态转移方程：KdxRdxkkkk111 阶段指标：KdtCRdtSCPKdxCRdxSCPvkkkkkkk)()()0()()()0(递推方程：KdtftCRdft

16、SCPKdxfxCRdxfxSCPxfkkkkkkkkkkkkkk)1()()1()()0(min)()()()()0(min)(111111 终端条件：fn(t)=-R(t)T 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 对于k=5:KdRdtftCftSCPtf55665)1()()1()()0(min

17、)(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()0(min)2(RdfCfSCPf*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(

18、)0(min)5(RdfCfSCPf*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:RdfCfSCPf*4554,354435min2420)4(211050min)3()2()1()2()0(min)2(RdfCfSCPf*4554,457045min3040)4(111050min)4()3()1()3()0(min)3(Rd

19、fCfSCPf*4554,5110551min3570)4(51050min)5()4()1()4()0(min)4(RdfCfSCPf*5554,5613556min35100)4(01050min)6()5()1()5()0(min)5(对于k=3:KdRdtftCftSCPtf33443)1()()1()()0(min)(KdfCfSCPf*3443,484852min351324321050min)2()1()1()1()0(min)1(RdfCfSCPf*3443,739173min514024111050min)4()3()1()3()0(min)3(RdfCfSCPf*3443,

20、7912679min56702451050min)5()4()1()4()0(min)4(RdfCfSCPf*3443,636563min452024211050min)3()2()1()2()0(min)2(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:RdfCfSCPf*2332,7311997min794048111050min)4()3()1()3()0(min)3(对于k=1:KdRdtftCftSCPtf11221)1()()1()()0(min)(RdfCfSCPf*1221,115117115min972076211050min)3()2()1()2()0(min)2(9797年年 份份 1 1 2 2 3 3 4 4 5 5 决决 策策 1 1 更更 新新 更更 新新 继继 续续 更更 新新 继继 续续 决决 策策 2 2 更更 新新 继继 续续 更更 新新 更更 新新 继继 续续 这两个决策是