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

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

例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ù)量為s1，要求制定一個五年計劃,在每年開始時決定機器在兩種不同負荷下生產(chǎn)的數(shù)量,使五年內(nèi)產(chǎn)品的總產(chǎn)量最高。4.1多階段決策問題與動態(tài)規(guī)劃多階段決策問題和我們前面遇到的決策問題不同，它是和時間有關(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)。4.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，當決策變量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ī)律。4.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)＝04.3動態(tài)規(guī)劃的步驟（一）當k=6時按基本方程由后向前繼續(xù)遞推有:當k=5時當k=4時現(xiàn)在把動態(tài)規(guī)劃法的步驟歸納如下：(1)將所研究問題的過程劃分為n個恰當?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ī)劃模型的步驟。4.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ù)量為s1，要求制定一個五年計劃,在每年開始時決定機器在兩種不同負荷下生產(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{5sj+3xj+fk+1(sk+1)}k=5,4,3,2,1

0≤xk≤sk

f6(s6)＝0解:當k=5時f5(s5)＝max{5s5+3x5+f6(s6)}=max{5s5+3x5}=8s5(x5*=s5)0≤x5≤s50≤x5≤s5當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}=13.6s4(x4*=s4)0≤x4≤s4當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}=17.5s3(x3*=s3)0≤x3≤s3當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}=20.7s4(x2*=0)0≤x2≤s2當k=1時f1(s1)=23.7s1(x1*=0)f1(1000)=23700s1=1000,x1*=0s2=900,x2*=0s3=810,x3*=810s4=576,x4*=576s5=397,x5*=397某些靜態(tài)規(guī)劃問題可用動態(tài)規(guī)劃法來求解。例用動態(tài)規(guī)劃法求解maxz=x12.x22.x3x1+x2+x3=cxi≥0i=1,2,34.4動態(tài)規(guī)劃的應(yīng)用(一)1求解靜態(tài)規(guī)劃問題例某工業(yè)部門根據(jù)國家計劃安排，擬將五臺某種高效率的機器分配給所屬的甲、乙、丙三個工廠，各工廠得到不同數(shù)量的機器可獲得的收益如下表。問應(yīng)如何分配機器，才能使各廠的總效益最大。某單位準備在以后的n個時期內(nèi)采購一批物資。各時期的價格不是確定的，而是按照某種已知的概率分布取值。試制定采購策略，確定在哪一時期以什么價格采購，能使采購價的數(shù)學(xué)期望值最低。這類問題也適合用動態(tài)規(guī)劃法進行處理。下面通過實例加以說明。例7某廠生產(chǎn)上需要在近五周內(nèi)采購一批原料，而估計在未來五周的價格有波動，其浮動價格和概率策得如下表。試確定該廠應(yīng)在哪一周以什么價格購入，能使其采購價的數(shù)學(xué)期望值最小，并求出期望值。4.4動態(tài)規(guī)劃的應(yīng)用(三)3不確定性采購問題設(shè)有n個工件需要在機床A、B上加工，每個工件都必須先經(jīng)過A而后B兩道加工工序。以ai、bi分別表示工件i(1≤i≤n)在A、B上的加工時間。問應(yīng)如何在兩機床上安排各工件的加工順序，使在機床A上加工第一個工件開始到在機床B上加工完最后一個工件為止，所用的加工總時間最少？加工工件在機床A上有加工順序問題，在機床B上也有加工順序問題?？梢宰C明：最優(yōu)加工順序在兩臺機床上可同時實現(xiàn)。因此，最優(yōu)排序方案可以只在機床A、B上加工順序相同的排序中尋找。即使如此，所有可能的方案仍有n!個，這是一個不小的數(shù)，用窮舉法是不現(xiàn)實的。4.4動態(tài)規(guī)劃的應(yīng)用(四)4排序問題用動態(tài)規(guī)劃法可以推出，工件i應(yīng)該排在工件j之前的條件為min(ai,bj)≤min(aj,bi)。根據(jù)這個條件，構(gòu)造下列排序方法：

a1a2…a