大二下課程運籌學20172課件or04動態(tài)

決勝千運籌帷決勝千運籌帷動態(tài)規(guī)劃動態(tài)規(guī)劃里之外幄之中里之外幄之中1214C132A10649D155106E5113821211102

1214106 10

96

E4 131211

8 10

E55E22E和終點進行分析和討論分別求C1，C2，C3到D1，D2的最短路87 分析得知：如果經(jīng)過B1，則走B1-C1-D1-E；A 83592145A B2760E51822

1 1

22n

Sj:j階段初系統(tǒng)所處狀態(tài)rj(Sj,Xj):j階段在狀態(tài) S=S1,

, j=1,2,,Xj(Sj)?Dj(SjSj+1=T(Sj,Xj1,n(S1)=1(S1),X2(S2),,Xn(Snk,n(Sk)=k(Sk),Xk+1(Sk+1),,Xn(SnPk,n(Sk)=k(Sk),Xk+1(Sk+1),,Xn(Snfk(Sk)=Optrk(Sk,Xk)ˉrk+1(Sk+1,Xk+1)ˉˉrn(Sn,Xnfk(Sk)= k(Sk Xk?Dk(Skfn+1(Sn+1)=0(or)

k=n,n-Anoptimalhasthepropertythatwhatevertheinitialstateandinitialdecisionare,thenremainingdecisionsmustconstituteanoptimalwithregardtothestateresultingfromfirstdecision.4.4產(chǎn)品，其收益為gi(xi)。問應(yīng)如何分配，

有4萬元，投資A、B、C三個項目，每個項目的投資效益與投入該項目的有關(guān)。三個項目A、B、C的投資效益（萬噸）和投入（萬元）的關(guān)系見下表：

階段k：每投資一個項目作為一個階段；狀態(tài)變量投資第k個項目前的余額；決策變量xk第k個項目的投資額；k=4，f4(s4)=0;k=3，0≤x3≤s3，s4=s3-00000010101102020211203030312213040404132231400000001010110202001120303001221304040213223140v1(s1,x1)v1(s1,x1)+f2(s2)4040113223140

0￡ui￡si,i第5年第4年第3年第2年第1年

f5(s5)=max5+5(s5-x5)+f6(s60￡x5第5年=max5+5第5年0￡x5x*=

f4(s4)=max8x4+0￡x48x40￡x48x40￡x4

-x4)+第4年-第4年

+

-x4=maxx0￡x4

4=

4…4x*=s44

=max{8x3+5(s3-x3)+13.6[0.7x3+0.9(s3-x3)]}第3年第3年 x

第2年第2年…x

2(產(chǎn)量

第1年第1年 x

(產(chǎn)量

每年投入高負荷運行的機器數(shù)以及每年初完好的機器數(shù)為：

一個工廠生產(chǎn)某種產(chǎn)品，1～7月份生產(chǎn)成本和產(chǎn)品需={xk|xk?0,rk+1￡sk- 因為s8=0 x7=0，所以 f5(s5)=min{c5x5+f6(s6)}x5?D5(s5)={x5|x5?0,r6￡s5-r5+x5￡H={x5|x5?0,9-s5￡x5￡11-D5(s5)={x5|9-s5￡x5￡11-s5}=10(9-s5)-=min{-3x4-D4(s4)={x4|x4?0,r5￡s4-={x4|x4?0,r5+r4-s4￡x4￡H+r4-={x4|x4?0,5-s4￡x4￡12-由于在f4(s4)的表達式中x4的系數(shù)是-由此f4(s4)=-3(12-s4)-20s4+280=-17s4+244f3(s3)=min=min{13x3+244-=min{13x3+244-17(s3-=min{-4x3-f3(s3)=-4(14-s3)- =min{5x2-13-x2(s2)={x2|13-s2￡x2￡17-s2}由此f2(s2)=5(13-s2)-13s2+377=min{-7x1-根據(jù)題意s1=2D1(s1)={x1|k1 7 0 42 470wi，每件價值ci?，F(xiàn)有一只可裝載重量為W的背包，求各種物品應(yīng)各取多少件放入背包，使背包中物品的價值最高。這個問題可以用整數(shù)規(guī)劃模型來描述。設(shè)第i種物品取xi s.t.w1x1+w2x2+…+wnxn≤W

sk+1=

vk=ck

fk(sk)

xk=0,1,,[w/wk

=xk=0,1,,[w/wk

fn+1(sn+1)=i123i123231f3(s3)=

{c3x3+f4(s40￡x3￡s3/ 0￡x3￡s3/由題意知，s1=5f1(s1f2(s2f3(s3)*=2s2=s1-2x1=1x2*=0s33x2=1x3以看出，如果背包得容量為W=4，W=3，W=2和

P=PNmax =Ppi(zii=s.t.

NNi=NN

ciz ￡wiz ￡i=z 0,

Dk(sk,uk)={x

|0￡

￡min([sk],[uk])}sk-1

-ck

ck = -wk-

vk=pk(xk

fk(sk,uk)=max{pk(xk)?fk-1(sk-1,uk-xk?Dk(sk,uk給出具體問題，例4-8 =

-ck,x,kk-

s0= xk?Dk(sk 124523563123分析狀態(tài)空間 N-min{cij|j=1,2,3}￡sk￡10-min{ck+i,j|j=1,2,3} 2￡s1￡6,5￡s2￡9,6￡s1￡10,從狀態(tài)轉(zhuǎn)