運籌學(xué)課件：8動態(tài)規(guī)劃

8動態(tài)規(guī)劃

8.1多階段決策問題與動態(tài)規(guī)劃

8.2動態(tài)規(guī)劃的基本概念

8.3動態(tài)規(guī)劃的步驟

8.4動態(tài)規(guī)劃的應(yīng)用

1求解靜態(tài)規(guī)劃問題

2資源分配問題

3不確定性采購問題

4排序問題

例2機器負荷分配問題某種機器可以在高低兩種不同的負荷下進行生產(chǎn)．在高負荷下進行生產(chǎn)時，產(chǎn)品的年產(chǎn)量g和投入生產(chǎn)的機器數(shù)量u的關(guān)系為g＝g(u),這時機器的年完好率為a（0<a<1)．在低負荷下生產(chǎn)時，產(chǎn)品的年產(chǎn)量h和投入生產(chǎn)的機器數(shù)量v的關(guān)系為h＝h(v),這時機器的年完好率為b（a<b<1）．假定開始生產(chǎn)時完好的機器數(shù)量為s，要求制定一個五年計劃,在每年開始時決定機器在兩種不同負荷下生產(chǎn)的數(shù)量,使五年內(nèi)產(chǎn)品的總產(chǎn)量最高。8.1多階段決策問題與動態(tài)規(guī)劃例1最短路問題

多階段決策問題和我們前面遇到的決策問題不同，它是和時間有關(guān)的。與時間有關(guān)的活動過程稱為動態(tài)過程，其優(yōu)化方法稱為動態(tài)規(guī)劃。而與時間無關(guān)的活動過程稱為靜態(tài)過程，相應(yīng)的的優(yōu)化方法稱為靜態(tài)規(guī)劃。以上兩個問題都可以劃分為先后多個決策階段。這類問題就稱為多階段決策問題。多階段決策問題的過程如下圖所示：

(1)階段（stage）把所研究的決策問題，按先后順序劃分為若干相互聯(lián)系的決策步驟，以便按一定的次序進行求解。描述階段的變量稱階段變量，常用k表示。

(2)狀態(tài)（state）狀態(tài)表示每個階段開始時所處的自然狀況或客觀條件，它描述了影響決策的因素隨決策進程的變化情況，它既是前面階段所作決策的結(jié)果，又是本階段作出決策的出發(fā)點和依據(jù)。描述狀態(tài)的變量稱為狀態(tài)變量，第k階段的狀態(tài)變量常用sk表示。通常，在第一階段狀態(tài)變量s1是確定的，稱初始狀態(tài)。

(3)決策（decision）決策表示在某一階段處于某種狀態(tài)時，決策者在若干種方案中作出的選擇決定。描述決策的變量稱決策變量，第k階段的決策變量常用uk表示。決策變量的取值會受到狀態(tài)變量的制約，被限制在某一范圍之內(nèi)，稱這個范圍為允許決策集。8.2動態(tài)規(guī)劃的基本概念（一）

(4)策略（policy）把從第一階段開始到最后階段終止的整個決策過程，稱為問題的全過程；而把從第k階段開始到最后階段終止的決策過程，或稱為k子過程。在全過程上，各階段的決策按順序排列組成的決策序列p1,n＝{u1,u2,……,un}稱為全過程策略，簡稱策略；而在k子過程上的決策序列

pk,n＝{uk,uk+1,……,un

}稱為k子過程策略，也簡稱子策略。

(5)狀態(tài)轉(zhuǎn)移方程若第k階段的狀態(tài)變量值為sk，當(dāng)決策變量uk的取值決定后，下一階段狀態(tài)變量sk+1的值也就完全確定。即sk+1的值對應(yīng)于sk和uk的值。這種對應(yīng)關(guān)系記為sk+1＝Tk(sk,uk)，稱為狀態(tài)轉(zhuǎn)移方程。狀態(tài)轉(zhuǎn)移方程描述了由一個階段的狀態(tài)到下一階段的狀態(tài)的演變規(guī)律。8.2動態(tài)規(guī)劃的基本概念（二）

(6)指標函數(shù)和最優(yōu)值函數(shù)指標函數(shù)分為階段指標函數(shù)和過程指標函數(shù)。階段指標函數(shù)是對某一階段的狀態(tài)和決策產(chǎn)生的效益值的度量，用vk(sk,uk)表示。過程指標函數(shù)是指過程所包含的各階段的狀態(tài)和決策所產(chǎn)生的總的效益值，記為

Vk,n＝Vk,n(sk,uk,sk+1,uk+1,……,sn,un)

動態(tài)規(guī)劃所要求的過程指標函數(shù)應(yīng)具有可分離性，即可表達為它所包含的各階段指標函數(shù)的函數(shù)形式。常見的兩種過程指標函數(shù)形式是：①各階段指標函數(shù)的和Vk,n＝∑vj(sj,uj)；②各階段指標函數(shù)的積Vk,n＝∏vj(sj,uj)。

把過程指標函數(shù)Vk,n對k子過程策略pk,n求最優(yōu)，得到一個關(guān)于狀態(tài)sk的函數(shù)，稱為最優(yōu)值函數(shù)，記為fk(sk)。即

fk(sk)＝optVk,n(sk,uk,……,sn,un)uk,…,un式中的“opt”（optimization）可根據(jù)具體問題而取min或max。

(7)基本方程通常動態(tài)規(guī)劃問題的最優(yōu)值函數(shù)滿足遞推關(guān)系式。設(shè)過程指標函數(shù)為各階段指標函數(shù)的和的形式，即Vk,n＝∑vj(sj,uj)，則有fk(sk)＝opt{vk(sk,uk)+fk+1(sk+1)}

uk∈Dk(sk)(k＝n,n-1,…,1)

遞推方程

fn+1(sn+1)＝0邊界條件遞推方程和邊界條件一起稱為動態(tài)規(guī)劃的基本方程。可根據(jù)邊界條件，從k=n開始，由后向前逆推，逐步求得各階段的最優(yōu)決策和相應(yīng)的最優(yōu)值，最后求出f1(s1)時，就得到整個問題的最優(yōu)解。此問題的基本方程為fk(sk)＝Min{dk(uk)+fk+1(sk+1)}

uk∈Dk(sk)

k＝6,5,4,3,2,1f7(s7)＝08.3動態(tài)規(guī)劃的步驟（一）當(dāng)k=6時例最短路問題按基本方程由后向前繼續(xù)遞推有:當(dāng)k=5時當(dāng)k=4時當(dāng)k=3時當(dāng)k=2時當(dāng)k=1時

由此可以看出，A到G的最短路長為18，路徑為：A→B1→C2→D1→E2→F2→G現(xiàn)在把動態(tài)規(guī)劃法的步驟歸納如下：(1)將所研究問題的過程劃分為n個恰當(dāng)?shù)碾A段，

k＝1,2,…,n；(2)正確地選擇狀態(tài)變量Sk，并確定初始狀態(tài)S1的值；(3)確定決策變量uk以及各階段的允許決策集Dk(Sk)；(4)給出狀態(tài)轉(zhuǎn)移方程；(5)給出滿足要求的過程指標函數(shù)Vk,n及相應(yīng)的最優(yōu)值函數(shù)；(6)寫出遞推方程和邊界條件，建立基本方程；(7)按照基本方程遞推求解。以上步驟是動態(tài)規(guī)劃法處理問題的基本步驟，其中的前六步是建立動態(tài)規(guī)劃模型的步驟。8.3動態(tài)規(guī)劃的步驟（二）例：機器負荷問題某種機器可以在高低兩種不同的負荷下進行生產(chǎn)．在高負荷下進行生產(chǎn)時，產(chǎn)品的年產(chǎn)量g和投入生產(chǎn)的機器數(shù)量u的關(guān)系為g＝8u,這時機器的年完好率為a=0.7．在低負荷下生產(chǎn)時，產(chǎn)品的年產(chǎn)量h和投入生產(chǎn)的機器數(shù)量v的關(guān)系為h＝5v,這時機器的年完好率為b=0.9．假定開始生產(chǎn)時完好的機器數(shù)量為1000，要求制定一個五年計劃,在每年開始時決定機器在兩種不同負荷下生產(chǎn)的數(shù)量,使五年內(nèi)產(chǎn)品的總產(chǎn)量最高。(1)按年數(shù)劃分為5個階段，k=1,2,3,4,5(2)取第k年初完好的機器數(shù)sk為狀態(tài)變量,s1=1000(3)取第k年投入高負荷的機器數(shù)xk為決策變量,0≤xk≤sk(4)狀態(tài)轉(zhuǎn)移方程為sk+1=0.7xk+0.9(sk-xk)=0.9sk-0.2xk(5)指標函數(shù)為Vk,5=∑[8xj+5(sj-xj)]=∑(5sj+3xj)(6)基本方程為

fk(sk)＝max{5sk+3xk+fk+1(sk+1)}k=5,4,3,2,1

0≤xk≤sk

f6(s6)＝0解:當(dāng)k=5時f5(s5)＝max{5s5+3x5+f6(s6)}=max{5s5+3x5}

0≤x5≤s50≤x5≤s5=8s5(x5*=s5)當(dāng)k=4時f4(s4)＝max{5s4+3x4+8s5}=max{5s4+3x4+8(0.9s4-0.2x4)}

0≤x4≤s40≤x4≤s4=max{12.2s4+1.4x4}

0≤x4≤s4當(dāng)k=3時f3(s3)＝max{5s3+3x3+13.6s4}=max{5s3+3x3+13.6(0.9s3-0.2x3)}

0≤x3≤s30≤x3≤s3=max{17.24s3+0.28x3}

0≤x3≤s3當(dāng)k=2時f2(s2)=max{5s2+3x2+17.52s3}=max{5s2+3x2+17.52(0.9s2-0.2x2)}

0≤x2≤s20≤x2≤s2=max{20.77s2-0.504x2}

0≤x2≤s2當(dāng)k=1時f1(s1)=23.7s1(x1*=0)f1(1000)=23700s1=1000,x1*=0s2=900,x2*=0s3=810,x3*=810s4=567,x4*=567s5=397,x5*=397=13.6s4(x4*=s4)=17.52s3(x3*=s3)=20.77s2(x2*=0)

某些靜態(tài)規(guī)劃問題可用動態(tài)規(guī)劃法來求解。

例用動態(tài)規(guī)劃法求解

maxz=x1.x22.x3x1+x2+x3=cxi≥0i=1,2,38.4動態(tài)規(guī)劃的應(yīng)用(一)

1求解靜態(tài)規(guī)劃問題(1)按變量數(shù)劃分為3個階段，k=1,2,3(2)取k階段初約束條件中資源的剩余量sk為狀態(tài)變量,s1=c(3)取第k階段的變量xk為決策變量,0≤xk≤sk(4)狀態(tài)轉(zhuǎn)移方程為sk+1=sk-xk(5)指標函數(shù)為Vk,3=∏vj(xj)

其中：v1(x1)=x1,v2(x2)=x22,v3(x3)=x3(6)基本方程為

fk(sk)＝max{

vk(xk)·fk+1(sk+1)

}k=3,2,1

0≤xk≤sk

f4(s4)＝1解:當(dāng)k=3時f3(s3)＝max{v3(x3)·f4(s4)}=max{x3}

0≤x3≤s30≤x3≤s3當(dāng)k=2時f2(s2)=max{v2(x2)·f3(s3)}=max{x22·(s2-x2)}

0≤x2≤s20≤x2≤s2當(dāng)k=1時z*=f1(c)=1/64c4

s1=c,x1*=1/4cs2=3/4c,x2*=1/2cs3=1/4c,x3*=1/4c=s3(x3*=s3)設(shè)h2(s2,x2)=x22·(s2-x2),且令dh2(s2,x2)/dx2=2x2·(s2-x2)-x22=0解得:x2=0(舍去),x2=2/3s2于是f2(s2)=4/27

s23(x2*=2/3s2)f1(s1)=max{v1(x1)·f2(s2)}=max{x1·4/27(s1-x1)3}

0≤x1≤s10≤x1≤s1設(shè)h1(s1,x1)=x1·4/27(s1-x1)3,且令dh1(s1,x1)/dx1=＝4/27(s1-x1)3-12/27x1·(s1-x1)2=0解得:x1=s1(舍去),x1=1/4s1于是f1(s1)=1/64

s14(x1*=1/4s1)

資源分配問題可描述如下：設(shè)有某種原料，總數(shù)量為a，分配給n個使用者。已知第i個使用者得到數(shù)量xi的資源，可創(chuàng)造的收益為gi（xi）。問應(yīng)如何分配該資源，才能使總收益最大。8.4動態(tài)規(guī)劃的應(yīng)用(二)

用動態(tài)規(guī)劃法處理這種問題時，通常把給一個使用者分配資源的過程看成一個階段，按n個使用者分成先后n個決策階段。即先給第1個使用者分配資源，為第一階段；再給第2個使用者分配，為第2階段；依此類推，最后給第n個使用者分配，為第n階段。

2資源分配問題

例某工業(yè)部門根據(jù)國家計劃安排，擬將五臺某種高效率的機器分配給所屬的甲、乙、丙三個工廠，各工廠得到不同數(shù)量的機器可獲得的收益如下表。問應(yīng)如何分配機器，才能使各廠的總效益最大。解：（1）按工廠分成3個階段，k=1,2,3；

（2）取k階段給第k個工廠分配機器時剩余的機器數(shù)sk為狀態(tài)變量，則：s1=5；

（3）取k階段給第k個工廠分配的機器數(shù)xk為決策變量，則：0≤xk

≤sk

；

（4）狀態(tài)轉(zhuǎn)移方程為：sk+1＝sk-xk

；

（5）指標方程為：Vk,3=∑gj(xj)

；

3j=k

（6）基本方程為：

fk(sk)＝

Max{gk(xk)+fk+1(sk+1)}

k=3,2,1

0≤xk

≤sk

f4(s4)＝0當(dāng)k=3時：s3

x3

g3(x3)+f4(s4)

f3(s3)00

0+0=0*011

4+0=4*4226+0=6*63311+0=11*114412+0=12*125512+0=12*12當(dāng)k=2時：s2

x2

g2(x2)+f3(s3)

f2(s2)00

0+0=0*01010+4=45+0=5*520120+6=65+4=910+0=10*10301230+11=115+6=1110+4=14*11+0=11144012340+12=125+11=16*10+6=16*11+4=1511+0=111650123450+12=125+12=1710+11=21*11+6=1711+4=1511+0=1121當(dāng)k=1時：s1

x1

g1(x1)+f2(s2)

f1(s1)50123450+21=21*3+16=197+14=21*9+10=1912+5=1713+0=1321

某單位準備在以后的n個時期內(nèi)采購一批物資。各時期的價格不是確定的，而是按照某種已知的概率分布取值。試制定采購策略，確定在哪一時期以什么價格采購，能使采購價的數(shù)學(xué)期望值最低。這類問題也適合用動態(tài)規(guī)劃法進行處理,下面通過實例加以說明。例7某廠生產(chǎn)上需要在近五周內(nèi)采購一批原料，而估計在未來五周的價格有波動，其浮動價格和概率策得如下表。試確定該廠應(yīng)在哪一周以什么價格購入，能使其采購價的數(shù)學(xué)期望值最小，并求出期望值。8.4動態(tài)規(guī)劃的應(yīng)用(三)

3不確定性采購問題解：（1）按采購周數(shù)分成5個階段，k=1,2,…,5；

（2）取第k階段(第k周)的實際價格yk為狀態(tài)變量；

（4）用fk(yk)表示第k周狀態(tài)為yk時，從第k周到第5周按最優(yōu)策略所得到的采購價的期望值，即fk(yk)為最優(yōu)值函數(shù)；

（5）用ykE表示，從第k周到第5周按最優(yōu)策略所得到的總的采購價的期望值，顯然有

ykE=Efk(yk)=0.3fk(500)+0.3fk(600)+0.4fk(700)

（6）基本方程為：

fk(yk)＝

Min{yk,y(k+1)E}k=1,2,…,5

f5(y5)＝y(tǒng)5

1采購（3）第k階段，設(shè)xk=為決策變量；

0等待k=5時：f5(500)=500,f5(600)=600,f5(700)=700，x5*=1y5E=0.3*500+0.3*600+0.4*700=610k=4時：f4(500)=min{500,610}=500,(x4*=1),f4(600)=min{600,610}=600,(x4*=1),f4(700)=min{700,610}=610,(x4*=0),y4E=0.3*500+0.3*600+0.4*610=574k=3時：f3(500)=min{500,574}=500,(x3*=1),f3(600)=min{600,574}=574,(x3*=0),f3(700)=min{700,574}=574,(x3*=0),y3E=0.3*500+0.3*574+0.4*574=551.8k=2時：f2(500)=min{500,551.8}=500,(x2*=1),f2(600)=min{600,551.8}=551.8,(x2*=0),f2(700)=min{700,551.8}=551.8,(x2*=0),y2E=0.3*500+0.3*551.8+0.4*551.8=536.26k=1時：f1(500)=min{500,536.26}=500,(x1*=1),f1(600)=min{600,536.26}=536.26,(x1*=0),f1(700)=min{700,536.26}=536.26,(x1*=0),y1E=0.3*500+0.3*536.26+0.4*536.26=525.382

設(shè)有n個工件需要在機床A、B上加工，每個工件都必須先經(jīng)過A而后B兩道加工工序。以ai、bi分別表示工件i(1≤i≤n)在A、B上的加工時間。問應(yīng)如何在兩機床上安排各工件的加工順序，使在機床A上加工第一個工件開始到在機床B上加工完最后一個工件為止，所用的加工總時間最少？

加工工件在機床A上有加工順序問題，在機床B上也有加工順序問題。