川大版运筹学课件2套-key第七章动态

第七第七…决策…决策决策 决策 决策决策3…，决策n｝2005-2- 1951年，R.Bellman等人,根据某类多阶段决策问题的 2005-2- 资源分配背包问2005-2- S2=｛B1,B2,B3｝

=｛C

,C2

6 4

3C3s，s，s，{

SS

阶段

阶段

阶段

阶段2005-2- B={B,B,B12253163Du3(s3)=D21E412{1{{阶段阶段阶段阶段决策决策(行为)u1(s1

决策集D1(s1D2(s2),D3(s32005-2-

A25A25196585E{1{2阶段阶段阶段阶段

阶段p14(s1)={p14

EE}}2005-2-7 略p24(s2)=｛s2u2(s2)

u4(s4)p1n(s1)=

…

}pkn pkn 2005-2-

}8A25645E12{1{{阶段阶段阶段阶段状态转移方程sk+1=Tksk,uk(sk))如s3C1u3(s3D2,s4T3(C1,D22005-2- VVk,n(pk,n(sk))k(sk,uk,sk1,uk1,pk,n(sk)sk,uk,uk1,uk2,,un,sn,un加加法形Vk,n(pk,n)nj vj(sj,uj(sj乘法形Vk,n(pk,n)jnvj(sj,uj(sjvvj(sj,uj(sj j1,2,L,2005-2- fk(sk)optVk,nsk,uk,L,sn1f1(s1)optV1,ns1,u1,s2,u2,L,n,n,2005-2- 25A564E12求从A到E的最短路2005-2- BB BB12005-2- 2265A5E412f4(D1)d(D1E)f5(E)502005-2- 22A6455E12f4(D2)d(D2E)f5(E)202005-2- BB1265A5E421f

)min(C1,D1)f4(D1) (C,D)f(D) min3 9

min8

最优决策

2005-2- BB1265A5E421f

)min(C2,D1)f4(D1) (C,D)f(D) min65min11 最优决策 52

7 2005-2- BB1265A5E421f

)min(C3,D1)f4(D1) (C,D)f(D) min85min

最优决策C3D 2005-2- BB1265A5E421f(B)

(B1,C1)f3(C1)

128

min(B1,C2)f3(C2)min147min21(B,C)f(C 最优决策B1

2005-2- 2A9655E5182f(B)

(B2,C1)f3(C1)

68

min(B2,C2)f3(C2)min107min17(B,C)f(C 4 最优决策B2

2005-2- 2A9655E5182f2(B3)

(B3,C1)f3(C1) min(B3,C2)f3(C (B,C)f(C

138 min12

最优决策B3

2005-2- 2A9655E5182f(A)

(A,B1)f2(B1)

2

min(A,B2)f2(B2)min514min19(A,B)f(B 最优决策A2005-2- 2A9655E5182状态最优决策状态最优决策状态最优决策状态最优决策 （A，B2）2005-2- 2A9655E5182状态最优决策状态最优决策状态最优决策状态最优决策 （A，B2） （B2，C1）2005-2- 2A9655E5182状态最优决策状态最优决策状态最优决策状态最优决策 （A，B2） （B2，C1）C1（C1，D1）2005-2- 2A9655E5182状态最优决策状态最优决策状态最优决策状态最优决策状态 （A，B2）B2 （B2，C1）C1（C1，D1）D1（D1，E） 从A到E的最短路径为19，路线为A→B2→C1→D1→E2005-2- 练1写出下例的阶段,状态变量,状态集, 点,A点看成终点,再重做一次,并且要求保持练1中 2005-2- 675124633A52E43533D241532005-2- 练习2 5 3 4

4633

3E 阶段阶段阶段

阶段阶段阶段2005-2-阶段阶段阶段7.37.3 已知已知阶段阶段阶段2005-2- Tn1(sn1,xn1),LL,sk1Tk(sk,xkKK,s2T1(s1,fn1(sn1)fn(sn) xnDn(snfn1(sn1)

vn(sn,xn [vn1(sn1,xn1)fn(snMMMMfk(sk)MMMMf1(s1)

xn1Dn1(sn1 [vk(sk,xk)fk1(sk1xkDk(sk [v1(s1,x1)f2(s22005-2-

xn=unsn-已知阶段 阶段 阶段 阶段2005-2- s1T1(s2,x1),LL,skKK,sn Tn(sn1,xnf0(s1)

Tk(sk1,xkf1(s2)f2(s3)MMM

v1(s2,x1x1D1(s2 [v2(s3,x2) f1(s2x2D2(s3fk(sk1) xkDk(sk1

[vk(sk1,xk) fk1(skMMMfn(sn1)

[vn(sn1,xn) fn1(snxnDn(sn12005-2- 4 4

部门共有12支巡逻队,负责4个要害部位A,B,C,D的 巡逻。对每个部位可分别派出2～4支巡逻队，并由于派出巡逻队数的不同，各部位预期在一段时期内可能造成的损失有差别，具体数字见表8—1。问该部门应往 分别派出多少支巡逻队，使总的损失最342005-2- skk4个部位的巡逻队数(状态变量)，xkk个部位的巡逻队数(决策变量), skDk（sk）=｛xk︱2xk≤4,xksk,整数f5(s5)fk(sk) [pk(sk,xk)fk1(sk12005-2-

S4

2005-2- S3

7, P3(x3)+

f（s）x 24+ 24+ 22+

24+ 24+

22+22+

21+ 21+ 2005-2- 2～4，至少是2P2(x2)+23482938+338+35+31+42005-2- P1(x1)+2344顺定:x1*=4,s2*=s1－x1*=12－4=8,3s3*=s2*－x2* x34s4*=s3*－x3* x4逆推法:逆推,2005-2- sk1k－1个部位的巡逻队数(状态变量xkk个部位的巡逻队数(决策变量),状态转移方程为：sk=sk+1 s5=12，s1=0，k=1,2,sk+1Dk（sk+1）=｛xk︱2xk≤4,整数f0(s1)fk(sk1) [pk(sk1,xk)fk1(skxkDk(sk12005-2- 2～4，至少是2S2

4 2005-2- 2～4，至少是2S3=｛4，5，6,7,P2(x2)+23442526273,842005-2- 2～4，至少是2P3(x3)+234829222005-2- P4(x1)+2344顺定:x4*=4,s4*=s5－x4*=12－4=8,2s3*=s4*－x3* x21s2*=s3*－x2* x1顺推法:顺推,2005-2- (项目投资问题 134

4051

4355

3045582005-2- x1,A项 x2,B项 04004000303011122244 万万万万万万万万2020

112万万万万万万222005-

1313040477.5例1: z4x19 2x22x14x23

12x13x24x3

0,i

顺推法: 2005-2- ss

s

1,x

D3=｛x3∣0≤x3≤s4/3D2=｛x2∣0≤x2≤s3/4 D1=｛x1∣0≤x1≤s2/2fk(sk1)

(vk

,sk1fk1(skxkDk

f1(s2)

4x12s2 xs221240x1s24f2(s3)

(9x2f1(s2))9/4s3 x

s320x2s32005-2- f3(s4) (2x2 f2(s3))9/4s30x

s44 (2x2 (s43x340x

s494s4

(2x

274 0x

s33hx3)2x3

274x

,hx

)因h(x3 0,h(x3

2s2/9 sx3

x3s4/ 3因为s 10,将s 10代入, h(x3)0,x 3f3(s4)45/2,x 0,x 5/2,x 2005-2- 例2: zx1x22x1x2

c0 0,ix1x2x3s { {{逆推法: 2005-2-

s

T

s ,x

D1=｛x1∣0≤x1≤s1｝fk(sk)

(vkxk,skfk1(sk1xkDkskf3(s3) x3s3 x30x32005-2- f2(s2) (x2f3(s3)) 20x2s2

0x2s2 h2s2,x220x22

2x2s23x20,得x2

2s2,

2d22又2dx2

6x2

d2dx2xd2dx23

2s2

故x22s2所以，x2 , s4s3 2005-f1(s1) (x1f2(s2))

x1 s1x130x1 0x1

0x2s2 由

4s1x13x134s1x1 4s1x12s1x13x14s1x12s14x1得x11s1x1s142005-d2又 s1x1s1

4故x11s1为