運(yùn)籌學(xué)第10章動(dòng)態(tài)規(guī)劃

第十章動(dòng)態(tài)規(guī)劃§1動(dòng)態(tài)規(guī)劃的基本概念與基本思路§2多階段決策過(guò)程最優(yōu)化問(wèn)題舉例§3動(dòng)態(tài)規(guī)劃的應(yīng)用(1)§4動(dòng)態(tài)規(guī)劃的應(yīng)用(2)1動(dòng)態(tài)規(guī)劃是一種研究多階段決策問(wèn)題的理論和方法，在決策中將問(wèn)題分成若干階段，對(duì)不同階段采取不同的決策，使全過(guò)程達(dá)到整體最優(yōu)。所謂多階段決策問(wèn)題是指這樣一類決策過(guò)程，當(dāng)每個(gè)階段的決策選定以后，過(guò)程也就隨之確定。把各個(gè)階段的決策綜合起來(lái)，構(gòu)成一個(gè)決策序列，稱為一個(gè)策略。顯然由于各個(gè)階段選取的決策不同，對(duì)應(yīng)整個(gè)過(guò)程就可以有一系列不同的策略。當(dāng)對(duì)過(guò)程采取某一策略時(shí)，可以得到一個(gè)確定的（或期望的）效果，采取不同的策略，就會(huì)得到不同的效果。多階段的決策問(wèn)題，就是要在所有可能采取的策略中間選取一個(gè)最優(yōu)的策略，使在預(yù)定的標(biāo)準(zhǔn)下得到最好的效果。2與線性規(guī)劃相比，動(dòng)態(tài)規(guī)劃問(wèn)題沒(méi)有一個(gè)標(biāo)準(zhǔn)的數(shù)學(xué)模型。然而，動(dòng)態(tài)規(guī)劃是一類很普遍的問(wèn)題解決方法，需要建立特定的方程以適應(yīng)各種情況。在多階段決策問(wèn)題中,各個(gè)階段采取的決策,一般來(lái)說(shuō)是與時(shí)間有關(guān)的,決策依賴于當(dāng)前的狀態(tài),又隨即引起狀態(tài)的轉(zhuǎn)移,一個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出來(lái)的,故有“動(dòng)態(tài)”的含義。因此,把處理它的方法稱為動(dòng)態(tài)規(guī)劃方法。但是,一些與時(shí)間沒(méi)有關(guān)系的靜態(tài)規(guī)劃(如線性規(guī)劃、非線性規(guī)劃等)問(wèn)題,只要人為地引進(jìn)“時(shí)間”因素,也可把它視為多階段決策問(wèn)題,用動(dòng)態(tài)規(guī)劃方法去處理。動(dòng)態(tài)規(guī)劃問(wèn)題的復(fù)雜性在于各階段決策之間的相互聯(lián)系。根據(jù)實(shí)際問(wèn)題構(gòu)造動(dòng)態(tài)規(guī)劃模型往往需要掌握更多的技巧。34最短路徑問(wèn)題：引例。如圖

,給定一個(gè)線路網(wǎng)絡(luò),兩點(diǎn)之間連線上的數(shù)字表示兩點(diǎn)間的距離(或費(fèi)用),試求一條由A到G的鋪管線路,使總距離為最短(或總費(fèi)用最小)?！?動(dòng)態(tài)規(guī)劃的基本概念5由圖可知,從A點(diǎn)到G點(diǎn)可以分為6個(gè)階段。從A到B為第一階段,從B到C為第二階段?從F到G為第六階段。在第一階段,A為起點(diǎn),終點(diǎn)有B1、B2兩個(gè),因而這時(shí)走的路線有兩個(gè)選擇,一是走到B1;一是走到B2,若選擇走到B2的決策,則B2就是第一階段在我們決策之下的結(jié)果。它既是第一階段路線的終點(diǎn),又是第二階段路線的始點(diǎn)。在第二階段,再?gòu)腂2點(diǎn)出發(fā),對(duì)應(yīng)于B2點(diǎn)就有一個(gè)可供選擇的終點(diǎn)集合{C2,C3,C4};若選擇由B2走至C2為第二階段的決策,則C2就是第二階段的終點(diǎn),同時(shí)又是第三階段的始點(diǎn)。同理遞推下去,可看到:各個(gè)階段的決策不同,鋪管路線就不同。很明顯,當(dāng)某階段的始點(diǎn)給定時(shí),它直接影響著后面各階段的行進(jìn)路線和整個(gè)路線的長(zhǎng)短,而后面各階段的路線的發(fā)展不受這點(diǎn)以前各階段路線的影響。故此問(wèn)題的要求是:在各個(gè)階段選取一個(gè)恰當(dāng)?shù)臎Q策,使由這些決策組成的一個(gè)決策序列所決定的一條路線,其總路程最短。61、動(dòng)態(tài)規(guī)劃的基本概念1.階段把所給問(wèn)題的過(guò)程,恰當(dāng)?shù)胤譃槿舾蓚€(gè)相互聯(lián)系的階段,以便能按一定的次序去求解。描述階段的變量稱為階段變量,常用k表示。階段的劃分,一般是根據(jù)時(shí)間和空間的自然特征來(lái)劃分,但要便于把問(wèn)題的過(guò)程能轉(zhuǎn)化為多階段決策的過(guò)程。如引例可分為6個(gè)階段來(lái)求解,k分別等于1、2、3、4、5、6。72.狀態(tài)狀態(tài)表示每個(gè)階段開(kāi)始所處的自然狀況或客觀條件,它描述了研究問(wèn)題過(guò)程的狀況,又稱不可控因素。在引例中,狀態(tài)就是某階段的出發(fā)位置。它既是該階段某支路的起點(diǎn),又是前一階段某支路的終點(diǎn)。通常一個(gè)階段有若干個(gè)狀態(tài),第一階段有一個(gè)狀態(tài)就是點(diǎn)A,第二階段有兩個(gè)狀態(tài),即點(diǎn)集合{B1,B2},一般第k階段的狀態(tài)就是第k階段所有始點(diǎn)的集合。8描述過(guò)程狀態(tài)的變量稱為狀態(tài)變量。常用sk

表示第k階段的狀態(tài)變量。如在引例中第三階段有四個(gè)狀態(tài),則狀態(tài)變量sk

可取四個(gè)值,即C1、C2、C3、C4。點(diǎn)集合{C1,C2,C3,C4}就稱為第三階段的可達(dá)狀態(tài)集合。記為S3={C1,C2,C3,C4}。有時(shí)為了方便起見(jiàn),將該階段的狀態(tài)編上號(hào)碼1,2?這時(shí)也可記S3={1,2,3,4}。第k階段的可達(dá)狀態(tài)集合就記為Sk

。9這里所說(shuō)的狀態(tài)應(yīng)具有下面的性質(zhì):如果某階段狀態(tài)給定后,則在這階段以后過(guò)程的發(fā)展不受這階段以前各段狀態(tài)的影響。換句話說(shuō),過(guò)程的過(guò)去歷史只能通過(guò)當(dāng)前的狀態(tài)去影響它未來(lái)的發(fā)展,當(dāng)前的狀態(tài)是以往歷史的一個(gè)總結(jié)。這個(gè)性質(zhì)稱為無(wú)后效性(即馬爾科夫性)。如果狀態(tài)僅僅描述過(guò)程的具體特征,則并不是任何實(shí)際過(guò)程都能滿足無(wú)后效性的要求。所以,在構(gòu)造決策過(guò)程的動(dòng)態(tài)規(guī)劃模型時(shí),不能僅由描述過(guò)程的具體特征這點(diǎn)著眼去規(guī)定狀態(tài)變量,而要充分注意是否滿足無(wú)后效性的要求。103.決策決策表示當(dāng)過(guò)程處于某一階段的某個(gè)狀態(tài)時(shí),可以作出不同的決定(或選擇),從而確定下一階段的狀態(tài),這種決定稱為決策。描述決策的變量,稱為決策變量。常用xk

(sk

)或uk

(sk

)表示第k階段當(dāng)狀態(tài)處于sk

時(shí)的決策變量。它是狀態(tài)變量的函數(shù)。在實(shí)際問(wèn)題中,決策變量的取值往往限制在某一范圍之內(nèi),此范圍稱為允許決策集合。常用Dk

(sk

)表示第k階段從狀態(tài)sk

出發(fā)的允許決策集合,顯然有xk

(sk

)∈Dk

(sk

)。11如在引例

第二階段中,若從狀態(tài)B1出發(fā),就可作出三種不同的決策,其允許決策集合D2(B1)={C1,C2,C3},若選取的點(diǎn)為C2,則C2是狀態(tài)B1在決策x2(B1)作用下的一個(gè)新的狀態(tài),記作x2(B1)=C2。124.策略策略是一個(gè)按順序排列的決策組成的集合。由過(guò)程的第k階段開(kāi)始到終止?fàn)顟B(tài)為止的過(guò)程,稱為問(wèn)題的后部子過(guò)程(或稱為k子過(guò)程)。由每段的決策按順序排列組成的決策函數(shù)序列{xk

(sk

),?,xn

(sn

)}稱為k子過(guò)程策略,簡(jiǎn)稱子策略,記為pk,

n

(sk

)。即13145.狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程用來(lái)表示過(guò)程由一個(gè)狀態(tài)到另一個(gè)狀態(tài)的演變。若給定第k階段狀態(tài)變量sk

的值,如果該段的決策變量uk

一經(jīng)確定,第k+1階段的狀態(tài)變量sk

+1

的值也就完全確定。即sk

+1

的值隨sk

和uk

的值變化而變化。這種確定的對(duì)應(yīng)關(guān)系,記為上式描述了由k階段到k+1階段的狀態(tài)轉(zhuǎn)移規(guī)律,稱為狀態(tài)轉(zhuǎn)移方程。Tk

稱為狀態(tài)轉(zhuǎn)移函數(shù)。156.指標(biāo)函數(shù)和最優(yōu)值函數(shù)指標(biāo)函數(shù)是衡量所選策略優(yōu)劣的數(shù)量指標(biāo)，具體可以是收益、成本、距離等指標(biāo)。分為k階段指標(biāo)函數(shù)、k子過(guò)程指標(biāo)函數(shù)及最優(yōu)指標(biāo)函數(shù)。

k階段指標(biāo)函數(shù)從k階段狀態(tài)sk出發(fā)，選擇決策xk所產(chǎn)生的第k階段指標(biāo)，稱為k階段指標(biāo)函數(shù),記為rk(sk,xk)。16從k階段狀態(tài)sk出發(fā)，選擇決策xk,xk+1,…,xn所產(chǎn)生的過(guò)程指標(biāo)，稱為k子過(guò)程指標(biāo)函數(shù)或簡(jiǎn)稱過(guò)程指標(biāo)函數(shù)，記為Vk(sk,xk,xk+1,…,xn)或Vk，n為階段數(shù)。過(guò)程指標(biāo)函數(shù)最優(yōu)指標(biāo)函數(shù)從k階段狀態(tài)sk出發(fā)，對(duì)所有的子策略，最優(yōu)的過(guò)程指標(biāo)函數(shù)稱為最優(yōu)指標(biāo)函數(shù)，記為fk(sk)，通常取Vk的最大值或最小值。17動(dòng)態(tài)規(guī)劃要求過(guò)程指標(biāo)滿足遞推關(guān)系

，即連和形式：最優(yōu)指標(biāo)函數(shù)是18動(dòng)態(tài)規(guī)劃數(shù)學(xué)模型、邊界條件及狀態(tài)轉(zhuǎn)移方程構(gòu)成。如連和形式的數(shù)學(xué)模型連乘形式(vj≠0)：最優(yōu)指標(biāo)函數(shù)是19對(duì)于可加性指標(biāo)函數(shù)，上式可以寫為上式中“opt”表示“max”或“min”。對(duì)于可乘性指標(biāo)函數(shù)，上式可以寫為上式稱為動(dòng)態(tài)規(guī)劃最優(yōu)指標(biāo)的遞推方程，是動(dòng)態(tài)規(guī)劃的基本方程。終端條件：為了使以上的遞推方程有遞推的起點(diǎn)，必須要設(shè)定最優(yōu)指標(biāo)的終端條件，即確定最后一個(gè)初始狀態(tài)n+1下最優(yōu)指標(biāo)fn+1(sn+1)的值。nksfxsvsfkkkkksDxkkoptkkk,,2,1)}(},({)(11)(L=+=++?20動(dòng)態(tài)規(guī)劃方法的基本思想結(jié)合解決最短路線問(wèn)題來(lái)介紹動(dòng)態(tài)規(guī)劃方法的基本思想。生活中的常識(shí)告訴我們,最短路線有一個(gè)重要特性:如果由起點(diǎn)A經(jīng)過(guò)P點(diǎn)和H點(diǎn)而到達(dá)終點(diǎn)G是一條最短路線,則由點(diǎn)P出發(fā)經(jīng)過(guò)H點(diǎn)到達(dá)終點(diǎn)G的這條子路線,對(duì)于從點(diǎn)P出發(fā)到達(dá)終點(diǎn)的所有可能選擇的不同路線來(lái)說(shuō),必定也是最短路線。此特性用反證法易證。因?yàn)槿绻皇沁@樣,則從點(diǎn)P到G點(diǎn)有另一條距離更短的路線存在,把它和原來(lái)最短路線由A點(diǎn)到達(dá)P點(diǎn)的那部分連接起來(lái),就會(huì)得到一條由A點(diǎn)到G點(diǎn)的新路線,它比原來(lái)那條最短路線的距離還要短些。這與假設(shè)矛盾,是不可能的。21例如,在最短路線問(wèn)題中,若找到了A→B4→C3→D1→E是由A到E的最短路線,則B4→C3→D1→E應(yīng)該是由B4出發(fā)到E點(diǎn)的所有可能選擇的不同路線中的最短路線。最優(yōu)化原理作為整個(gè)過(guò)程的最優(yōu)策略具有如下性質(zhì)：不管在此最優(yōu)策略上的某個(gè)狀態(tài)以前的狀態(tài)和決策如何，對(duì)該狀態(tài)來(lái)說(shuō)，以后的所有決策必定構(gòu)成最優(yōu)子策略。就是說(shuō)，最優(yōu)策略的任意子策略都是最優(yōu)的。22根據(jù)最短路線這一特性,尋找最短路線的方法,就是從最后一段開(kāi)始,用由后向前逐步遞推的方法,求出各點(diǎn)到E點(diǎn)的最短路線,最后求得由A點(diǎn)到E點(diǎn)的最短路線。所以,動(dòng)態(tài)規(guī)劃的方法是從終點(diǎn)逐段向始點(diǎn)方向?qū)ふ易疃搪肪€的一種方法。23動(dòng)態(tài)規(guī)劃求解思路（1）將多階段決策問(wèn)題按照空間或時(shí)間順序劃分成相互聯(lián)系的階段，從而把問(wèn)題化成一族同類型的子問(wèn)題，恰當(dāng)?shù)剡x取狀態(tài)變量和決策變量，寫出狀態(tài)轉(zhuǎn)移方程，定義最優(yōu)指標(biāo)函數(shù)，寫出遞推關(guān)系式和邊界條件。（2）求解從邊界條件開(kāi)始，由后向前逐段遞推尋找最優(yōu)。在每一個(gè)階段的計(jì)算中都要用到前一階段的子問(wèn)題的最優(yōu)結(jié)果，最后一個(gè)子問(wèn)題的最優(yōu)解就是整個(gè)問(wèn)題的最優(yōu)解。（3）在多階段決策過(guò)程中，確定階段k的最優(yōu)決策時(shí)，不僅要考慮本階段最優(yōu)，而且要考慮本階段及其所有后部子過(guò)程的整體最優(yōu)。

24§2多階段決策過(guò)程最優(yōu)化問(wèn)題舉例例1最短路徑問(wèn)題

下圖表示從起點(diǎn)A到終點(diǎn)E之間各點(diǎn)的距離。求A到E的最短路徑。BACBDBCDEC41231231232216472483867561106375125§2多階段決策過(guò)程最優(yōu)化問(wèn)題舉例如何解決這個(gè)問(wèn)題呢?可以采取窮舉法。即把由A到E所有可能的每一條路線的距離都算出來(lái)，然后互相比較找出最短者，相應(yīng)地得出了最短路線。這樣，由A到E的4個(gè)階段中,一共有4×3×2×1=24條不同的路線，比較24條不同的路線的距離值,才找出最短路線為A→B4→C3→D1→E

，相應(yīng)最短距離為14。顯然,這樣作計(jì)算是相當(dāng)繁雜的。如果當(dāng)段數(shù)很多,各段的不同選擇也很多時(shí),這種解法的計(jì)算將變得極其繁雜,甚至在電子計(jì)算機(jī)上計(jì)算都是不現(xiàn)實(shí)的。因此,為了減少計(jì)算工作量,需要尋求更好的算法,這就是要介紹的動(dòng)態(tài)規(guī)劃的方法。26第一步建模階段k：劃分為四個(gè)階段，k=1,2,3,4決策變量xk：第k階段要到達(dá)的位置狀態(tài)變量sk：第k階段出發(fā)的位置Sk：第k階段狀態(tài)集合，即狀態(tài)變量的取值范圍Dk（sk）：第k階段從狀態(tài)sk出發(fā)允許的決策集合sk+1=Tk(sk,xk)：狀態(tài)轉(zhuǎn)移方程rk(sk,xk)：第k階段從狀態(tài)sk出發(fā)，采取決策xk到達(dá)第k+1階段的狀態(tài)sk+1時(shí)兩點(diǎn)間的距離fk(sk)表示從第k階段的狀態(tài)sk出發(fā)，到終點(diǎn)的最短距離，f1(s1)即為所求。27基本方程：fk(sk)=min{rk(sk,xk)+fk+1(sk+1)},k=4,3,2,1終點(diǎn)條件：fn+1(sn+1)=0即f5(E)=0由于E是終點(diǎn)，所以不再移動(dòng)了。一般情況下，終點(diǎn)（邊界）條件或者取0（遞推方程連加的形式下）或者取1（遞推方程連乘的形式下）28第二步逆推求解求解要做的是在給定狀態(tài)下做決策。本題中是站在始點(diǎn)選終點(diǎn)。第四階段，狀態(tài)s4可取兩個(gè)值D1和D2，根據(jù)到最終終點(diǎn)E的距離最短來(lái)決策。最優(yōu)值函數(shù)計(jì)算的也就是各狀態(tài)點(diǎn)到E的最短距離。在狀態(tài)D1下，到E的路徑只有一條，故只能選擇這一條，這也是最優(yōu)的，f4(D1)=min{r4(D1,E)+f5(E)}=10在狀態(tài)D2下，同理f4(D2)=min{r4(D2,E)+f5(E)}=6第三階段，狀態(tài)s3可取三個(gè)值C1、C2和C3在狀態(tài)C1下，D3(C1)={D1,D2}。有兩個(gè)地點(diǎn)可選擇，根據(jù)到E距離最短來(lái)選擇。f3(C1)=min{r3(C1,D1)+f4(D1);r3(C1,D2)+f4(D2)}=min{8+10;6+6}=12。選擇C1經(jīng)D2到E29第二步逆推求解-表格形式

1、以上求從A到E的最短路徑問(wèn)題，可以轉(zhuǎn)化為四個(gè)性質(zhì)完全相同，但規(guī)模較小的子問(wèn)題，即分別從Di

、Ci、Bi、A到E的最短路徑問(wèn)題。第四階段：兩個(gè)始點(diǎn)（初始狀態(tài)變量）D1和D2，終點(diǎn)（決策變量）只有一個(gè)；

表10-1分析得知：從D1和D2到E的最短路徑唯一。階段4本階段始點(diǎn)（狀態(tài)）本階段各終點(diǎn)（決策）到E的最短距離本階段最優(yōu)終點(diǎn)（最優(yōu)決策)

ED1D2

106

106

EE30第三階段：有三個(gè)始點(diǎn)C1，C2，C3，終點(diǎn)有D1，D2，對(duì)始點(diǎn)和終點(diǎn)進(jìn)行分析和討論分別求C1，C2，C3到D1，D2

的最短路徑問(wèn)題：

表10-2分析得知：如果經(jīng)過(guò)C1，則最短路為C1-D2-E；如果經(jīng)過(guò)C2，則最短路為C2-D2-E；如果經(jīng)過(guò)C3，則最短路為C3-D1-E。

§2多階段決策過(guò)程最優(yōu)化問(wèn)題舉例階段3本階段始點(diǎn)（狀態(tài)）本階段各終點(diǎn)（決策）到E的最短距離本階段最優(yōu)終點(diǎn)（最優(yōu)決策)D1D2C1C2C38+10=187+10=171+10=116+6=125+6=116+6=12

121111

D2D2D131第二階段：有4個(gè)始點(diǎn)B1,B2,B3,B4，終點(diǎn)有C1,C2,C3。對(duì)始點(diǎn)和終點(diǎn)進(jìn)行分析和討論分別求B1,B2,B3,B4到C1,C2,C3

的最短路徑問(wèn)題：

表10-3

分析得知：如果經(jīng)過(guò)B1，則走B1-C2-D2-E；如果經(jīng)過(guò)B2，則走B2-C3-D1-E；如果經(jīng)過(guò)B3，則走B3-C3-D1-E；如果經(jīng)過(guò)B4，則走B4-C3-D1-E。

§2多階段決策過(guò)程最優(yōu)化問(wèn)題舉例階段2本階段始點(diǎn)（狀態(tài)）本階段各終點(diǎn)（決策）到E的最短距離本階段最優(yōu)終點(diǎn)（最優(yōu)決策)C1C2C3B1B2B3B42+12=144+12=164+12=167+12=191+11=127+11=188+11=195+11=166+11=172+11=133+11=141+11=12

12131412

C2C3C3C332第一階段：只有1個(gè)始點(diǎn)A，終點(diǎn)有B1,B2,B3,B4

。對(duì)始點(diǎn)和終點(diǎn)進(jìn)行分析和討論分別求A到B1,B2,B3,B4的最短路徑問(wèn)題：

表10-4最后，可以得到：從A到E的最短路徑為AB4C3D1E§2多階段決策過(guò)程最優(yōu)化問(wèn)題舉例階段1本階段始點(diǎn)(狀態(tài))本階段各終點(diǎn)（決策）到E的最短距離本階段最優(yōu)終點(diǎn)(最優(yōu)決策)B1B2B3B4A4+12=163+13=163+14=172+12=14

12

C233

以上計(jì)算過(guò)程及結(jié)果，可用圖2表示，可以看到，以上方法不僅得到了從A到D的最短路徑，同時(shí)，也得到了從圖中任一點(diǎn)到E的最短路徑。

以上過(guò)程，僅用了22次加法，計(jì)算效率遠(yuǎn)高于窮舉法。BACBDBCDEC41231231233216472483867516106010612111112131414127512§1多階段決策過(guò)程最優(yōu)化問(wèn)題舉例34動(dòng)態(tài)規(guī)劃小結(jié)問(wèn)題可以被分解為幾個(gè)階段，每個(gè)階段要求進(jìn)行決策。每個(gè)階段都有大量與其相關(guān)的狀態(tài)。任意階段所選定的決策描述了當(dāng)前階段的狀態(tài)如何轉(zhuǎn)移為下一階段的狀態(tài)。已知當(dāng)前狀態(tài)，其他各個(gè)階段的決策不能依賴于先前到達(dá)的狀態(tài)或先前選定的決策。存在遞推表達(dá)式，將階段t，t+1，…，T期間的成本和收益與階段t+1，…，T期間的成本和收益聯(lián)系起來(lái)。要使用動(dòng)態(tài)規(guī)劃解決問(wèn)題，需要確定合適的狀態(tài)、階段和決策。35決策目標(biāo)是在各個(gè)階段的每一種狀態(tài)下，選擇合適的決策變量來(lái)最優(yōu)化成本或收益的累積表達(dá)式。可通過(guò)羅列來(lái)找出（在離散決策變量時(shí)），也可通過(guò)決策變量的給定區(qū)間，求解出最優(yōu)值及取最優(yōu)值時(shí)決策變量的取值。要正確表達(dá)遞推公式，需要確定３個(gè)重要方面：對(duì)于給定狀態(tài)和階段而言，容許或可行的決策集（決策變量的取值范圍）；必須指出階段k的值、當(dāng)前狀態(tài)和在階段k所選擇的決策如何影響當(dāng)前階段的費(fèi)用；必須指出階段k的值、當(dāng)前狀態(tài)和在階段k所選擇的決策如何影響階段k+1的狀態(tài)。36動(dòng)態(tài)規(guī)劃的步驟第一劃分階段。第二設(shè)定決策變量。第三設(shè)定狀態(tài)變量。根據(jù)決策變量，尋找能夠影響決策變量的因素作為狀態(tài)，狀態(tài)不是只有一個(gè)確定的狀態(tài)，而是有多個(gè)狀態(tài)，在每個(gè)狀態(tài)下需進(jìn)行最優(yōu)決策。第四，確定每一狀態(tài)下決策變量的取值范圍。第五，寫出狀態(tài)轉(zhuǎn)移方程。第六，寫出階段指標(biāo)表達(dá)式。第七，寫出終端條件。第八，寫出遞推方程。37狀態(tài)變量的設(shè)定：當(dāng)前還有多少可用庫(kù)存，還有多少可用分配的資源，還有多少可供利用的空間。當(dāng)前產(chǎn)品存儲(chǔ)量是多少。3839一、資源分配問(wèn)題

例2.某公司擬將某種設(shè)備5臺(tái)，分配給所屬的甲、乙、丙三個(gè)工廠。各工廠獲得此設(shè)備后，預(yù)測(cè)可創(chuàng)造的利潤(rùn)如表10-5所示，問(wèn)這5臺(tái)設(shè)備應(yīng)如何分配給這3個(gè)工廠，使得所創(chuàng)造的總利潤(rùn)為最大？

表10-5盈利工廠設(shè)備臺(tái)數(shù)甲廠乙廠丙廠0

0

0

0

1

3

5

4

2

7

10

6

3

9

11

11

4

12

11

12

5

13

11

12§3動(dòng)態(tài)規(guī)劃的應(yīng)用(1)40解：階段k：將問(wèn)題按工廠分為三個(gè)階段，甲、乙、丙三個(gè)廠分別編號(hào)為1、2、3廠。設(shè)狀態(tài)變量：sk=可分配給第k個(gè)廠至第3個(gè)廠的設(shè)備臺(tái)數(shù)（k=1、2、3）。用于分配給剩余工廠的可得到的設(shè)備臺(tái)數(shù)。決策變量：xk=分配給第k個(gè)工廠的設(shè)備臺(tái)數(shù)。狀態(tài)轉(zhuǎn)移方程：sk

+1=sk

-xk

為可分配給第k+1個(gè)工廠至第3

個(gè)工廠的設(shè)備臺(tái)數(shù)。階段指標(biāo)函數(shù)：rk

(sk,xk

)表示為xk

臺(tái)設(shè)備分配到第k個(gè)工廠所得的盈利值。具體如上表。最優(yōu)指標(biāo)函數(shù)：fk

(sk

)表示為sk

臺(tái)設(shè)備分配給第k個(gè)工廠至第3個(gè)工廠時(shí)所得到的最大盈利值。因而可寫出遞推關(guān)系式為§3動(dòng)態(tài)規(guī)劃的應(yīng)用(1)下面從最后一個(gè)階段開(kāi)始向前逆推計(jì)算。fk

(sk

)=max[rk(sk,xk)+fk+1(sk-xk)],k=1,2,3

0≤xk≤skf4(s4)=041

第三階段:

由于第3階段是最后的階段，故有其中可取值為0,1,2,3,4,5。其數(shù)值計(jì)算見(jiàn)表10－6。

§3動(dòng)態(tài)規(guī)劃的應(yīng)用(1)42表10－6

0

1

2

3

4

5

0

0－－－－－001－4－－－－412－－6－－－623－－－11－－1134－－－－12－1245－－－－12

12124或5§3動(dòng)態(tài)規(guī)劃的應(yīng)用(1)43其中表示取3子過(guò)程上最優(yōu)指標(biāo)值時(shí)的決策，例如在表10-6中可知當(dāng)=4時(shí)，有有此時(shí)，即當(dāng)時(shí)，此時(shí)取（把4臺(tái)設(shè)備分配給第3廠）是最優(yōu)決策，此時(shí)階段指標(biāo)值（盈利）為12，最優(yōu)3子過(guò)程最優(yōu)指標(biāo)值也為12。第二階段：

當(dāng)把臺(tái)設(shè)備分配給第2工廠和第3工廠時(shí)，則對(duì)每個(gè)值，有一種最優(yōu)分配方案，使最大盈利即最優(yōu)2子過(guò)程最優(yōu)指標(biāo)函數(shù)值為

§3動(dòng)態(tài)規(guī)劃的應(yīng)用(1)44因?yàn)樯鲜揭部蓪懗善鋽?shù)值計(jì)算如表10－7所示。

表10－7

0

1

2

3

4

5

0－－－－－0010＋4

－－－－5120＋6

5＋4－－－10230＋11

5＋6

11＋0－－14240＋12

11＋4

11＋0－161,250＋12

5＋12

11＋6

11＋4

11＋0

212§3動(dòng)態(tài)規(guī)劃的應(yīng)用(1)45其中在的這一行里，當(dāng)時(shí)，這里從表10－5中可知，把1臺(tái)設(shè)備交給乙廠所得盈利數(shù)即可，知，這里從表10－6查即可知=11。同樣可知當(dāng)時(shí)，可知

;當(dāng)時(shí)，；當(dāng)時(shí)，；當(dāng)時(shí)，

；由于，不可能分2廠5臺(tái)設(shè)備，故時(shí)，欄空著不填。從這些數(shù)值中取得最大即得，即有=16。在此行中我們?cè)谌∽畲笾档纳厦婕右粰M以示區(qū)別，也可知這時(shí)的最優(yōu)決策為1或2?！?動(dòng)態(tài)規(guī)劃的應(yīng)用(1)46

第一階段：把臺(tái)設(shè)備分配給第1，第2，第3廠時(shí)，最大盈利為其中可取值0,1,2,3,4,5.數(shù)值計(jì)算見(jiàn)表10－8

表10-8

然后按計(jì)算表格的順序推算，可知最優(yōu)分配方案有兩個(gè)：

1.由于，根據(jù)，查表10－7可知，再由，求得。即分配給甲廠0臺(tái)，乙廠2臺(tái)，丙廠3臺(tái)。

2.由于，根據(jù)，查表10－7可

0

1

2

3

4

55

3＋169+1012+513+0210,2§3動(dòng)態(tài)規(guī)劃的應(yīng)用(1)47知，再由,求得，即分配給甲廠2臺(tái)，乙廠2臺(tái)，丙廠1臺(tái)。這兩種分配方案都能得到最高的總盈利21萬(wàn)元。

§3動(dòng)態(tài)規(guī)劃的應(yīng)用(1)小結(jié)：第一步，建立動(dòng)態(tài)規(guī)劃模型劃分階段，設(shè)決策變量，設(shè)狀態(tài)變量，確定決策變量的取值范圍，寫狀態(tài)轉(zhuǎn)移方程，寫階段指標(biāo)函數(shù)，寫遞推（基本）方程。第二步，求解動(dòng)態(tài)規(guī)劃模型從后往前逐段累計(jì)求解48現(xiàn)有資金4萬(wàn)元，擬分給A、B、C三個(gè)項(xiàng)目，每項(xiàng)目獲得不同的資金后可能創(chuàng)造的利潤(rùn)如下表所示，問(wèn)應(yīng)如何分配這4萬(wàn)元資金，使三個(gè)項(xiàng)目創(chuàng)造的總利潤(rùn)最大？資金（萬(wàn)元）ABC0123403810120581111046111449現(xiàn)有某種設(shè)備4臺(tái)，擬分給甲、乙、丙三個(gè)工廠，個(gè)工廠獲得此設(shè)備后可能創(chuàng)造的利潤(rùn)如下表所示，問(wèn)應(yīng)如何分配這4臺(tái)設(shè)備，使所創(chuàng)造的總利潤(rùn)最大？設(shè)備臺(tái)數(shù)甲乙丙0123403791205101111046111250二、背包問(wèn)題設(shè)有n種物品，每一種物品數(shù)量無(wú)限。第i種物品每件重量為wi公斤，每件價(jià)值ci元。現(xiàn)有一只可裝載重量為W公斤的背包，求各種物品應(yīng)各取多少件放入背包，使背包中物品的價(jià)值最高。這個(gè)問(wèn)題可以用整數(shù)規(guī)劃模型來(lái)描述。設(shè)xi為第i種物品裝入背包的件數(shù)（i=1,2,…,n），背包中物品的總價(jià)值為z，則

Maxz=c1x1+c2x2+…+cnxns.t.w1x1+w2x2+…+wnxn≤Wx1,x2,…,xn0

且為整數(shù)?！?動(dòng)態(tài)規(guī)劃的應(yīng)用(1)51下面用動(dòng)態(tài)規(guī)劃逆序解法求解它。設(shè)階段變量k：第k次裝載第k種物品（k=1,2,…,n）狀態(tài)變量sk：第k次裝載時(shí)背包還可以裝載的重量；決策變量uk

=xk：第k次裝載第k種物品的件數(shù)；決策允許集合：Dk(sk)={xk

|0

xksk/wk，xk為整數(shù)}；狀態(tài)轉(zhuǎn)移方程：sk+1=sk

wkxk；階段指標(biāo)：vk

=ckxk；最優(yōu)過(guò)程指標(biāo)函數(shù)fk(sk)：第k到n階段容許裝入物品的最大使用價(jià)值；遞推方程： fk(sk)=max{ckxk+fk+1(sk+1)}=max{ckxk+fk+1(sk

wkxk)}；

xDk(sk)終端條件：fn+1(sn+1)=0。§3動(dòng)態(tài)規(guī)劃的應(yīng)用(1)52

例3.某咨詢公司有10個(gè)工作日可以去處理四種類型的咨詢項(xiàng)目，每種類型的咨詢項(xiàng)目中待處理的客戶數(shù)量、處理每個(gè)客戶所需工作日數(shù)以及所獲得的利潤(rùn)如表10－9所示。顯然該公司在10天內(nèi)不能處理完所有的客戶，它可以自己挑選一些客戶，其余的請(qǐng)其他咨詢公司去做，應(yīng)如何選擇客戶使得在這10個(gè)工作日中獲利最大？表10－9

咨詢項(xiàng)目類型待處理客戶數(shù)處理每個(gè)客戶所需工作日數(shù)處理每個(gè)客戶所獲利潤(rùn)1234

4

3

2

2

1

3

4

7

2

8

11

20§3動(dòng)態(tài)規(guī)劃的應(yīng)用(1)53

解：用動(dòng)態(tài)規(guī)劃來(lái)求解此題。我們把此問(wèn)題分成四個(gè)階段，第一階段我們決策將處理多少個(gè)第一種咨詢項(xiàng)目類型中的客戶，第二階段決策將處理多少個(gè)第二種咨詢項(xiàng)目類型中的客戶，第三階段、第四階段我們也將作出類似的決策。我們?cè)O(shè)＝分配給第k種咨詢項(xiàng)目到第四種咨詢項(xiàng)目的所有客戶的總工作日（第k階段的狀態(tài)變量）。

=在第k種咨詢項(xiàng)目中處理客戶的數(shù)量（第k階段的決策變量）。已知＝10并有

§3動(dòng)態(tài)規(guī)劃的應(yīng)用(1)54

并從與的定義可知從第四階段開(kāi)始計(jì)算：顯然將個(gè)工作日盡可能分配給第四類咨詢項(xiàng)目，即時(shí)，第四階段的指標(biāo)值為最大，其中，表示取不大于的最大整數(shù)，符號(hào)為取整符號(hào)，故有由于第四階段是最后的階段，故有§3動(dòng)態(tài)規(guī)劃的應(yīng)用(1)55

因?yàn)橹炼酁?0，其數(shù)值計(jì)算見(jiàn)表10－10。

表10－10

0

1

0

－

0

0

1－

0

0

2－

0

0

3－

0

0

4－

0

0

5

－

0

0

6－

0

0

7

0

20

1

8

0

20

1

9

0

20

1

10

0

1

1§3動(dòng)態(tài)規(guī)劃的應(yīng)用(1)56

第三階段：當(dāng)把個(gè)工作日分配給第四類和第三類咨詢項(xiàng)目時(shí)，則對(duì)每個(gè)值，都有一種最優(yōu)分配方案，使其最大盈利即最優(yōu)3子過(guò)程最優(yōu)指標(biāo)函數(shù)值為

因?yàn)橐驗(yàn)橹炼酁?0，所以的取值可為0,1,2。其數(shù)值計(jì)算見(jiàn)表10－11?！?動(dòng)態(tài)規(guī)劃的應(yīng)用(1)57

表10－11

0120－－

0

0

1－－

0

0

2－－

0

0

3－－

0

0

4

0＋0－

11

1

5

0＋0－

11

1

6

0＋0－

11

1

7

11+0－

20

0

8

0＋20

11+0

22

2

9

0＋20

11+0

22

2

10

0＋20

11+0

22

2§3動(dòng)態(tài)規(guī)劃的應(yīng)用(1)58

第二階段：同樣以每個(gè)值都有一種最優(yōu)分配方案，使其最大盈利即最優(yōu)2子過(guò)程最優(yōu)指標(biāo)函數(shù)值為：因?yàn)?，故有因?yàn)橹炼酁?0，所以的取值為0,1,2,3。其數(shù)值計(jì)算見(jiàn)表10－12。§3動(dòng)態(tài)規(guī)劃的應(yīng)用(1)59§3動(dòng)態(tài)規(guī)劃的應(yīng)用(1)

表10-1260

第一階段：我們已知，又因?yàn)?，同樣?/p>

因?yàn)?故可取值為0,1,2,…,10。其數(shù)值計(jì)算見(jiàn)表10－13。表10－13§3動(dòng)態(tài)規(guī)劃的應(yīng)用(1)

61從表10－13可知，從而得＝10－0＝10，在表10－12的的這一行可知，由，查表10－11的的這一行可知，最后由，查表10-10的的這一行得，綜上所述得最優(yōu)解為：此時(shí)最大盈利為28?，F(xiàn)在我們不妨假設(shè)該咨詢公司的工作計(jì)劃有所改變，只有8個(gè)工作日來(lái)處理這四類咨詢項(xiàng)目，那么該咨詢公司如何選擇客戶使得獲利最大呢？我們不必從頭開(kāi)始重做這個(gè)問(wèn)題，而只要在第一階段上把改成8，重新計(jì)算就可得到結(jié)果，如表10－14所示，這是動(dòng)態(tài)規(guī)劃的一個(gè)好處。

§3動(dòng)態(tài)規(guī)劃的應(yīng)用(1)

62

表10－14

如上一樣可從表10－14,10－12,10－11,10－10得到兩組最優(yōu)解如下：

它們的最優(yōu)解（即最大盈利）都為22。一旦咨詢的工作日不是減少而是增加，那么我們不僅要重新計(jì)算第一階段，而且要在第二、第三、第四階段的計(jì)算表上補(bǔ)上增加的工作日的新的信息，也可得到新的結(jié)果?！?動(dòng)態(tài)規(guī)劃的應(yīng)用(1)

63

實(shí)際上，背包問(wèn)題我們也可以用整數(shù)規(guī)劃來(lái)求解，如果背包攜帶物品重量的限制為W公斤，這N種物品中第i種物品的重量為，價(jià)值為，第i種物品的總數(shù)量的，我們可以設(shè)表示攜帶第i種物品的數(shù)量，則其數(shù)學(xué)模型為：

S.T.

且為整數(shù)。

我們不妨用此模型去求解例3，也一定得出同樣的結(jié)果?！?動(dòng)態(tài)規(guī)劃的應(yīng)用(1)

64三、生產(chǎn)與存貯問(wèn)題例4.某公司為主要電力公司生產(chǎn)大型變壓器，由于電力采取預(yù)訂方式購(gòu)買，所以該公司可以預(yù)測(cè)未來(lái)幾個(gè)月的需求量。為確保需求，該公司為新的一年前四個(gè)月制定一項(xiàng)生產(chǎn)計(jì)劃，這四個(gè)月的需求如表10－15所示。生產(chǎn)成本隨著生產(chǎn)數(shù)量而變化。調(diào)試費(fèi)為4，除了調(diào)度費(fèi)用外，每月生產(chǎn)的頭兩臺(tái)各花費(fèi)為2，后兩臺(tái)花費(fèi)為1。最大生產(chǎn)能力每月為4臺(tái)，生產(chǎn)成本如表10－16所示。

表10－15

§3動(dòng)態(tài)規(guī)劃的應(yīng)用(1)

65

表10－16

每臺(tái)變壓器在倉(cāng)庫(kù)中由這個(gè)月存到下個(gè)月的儲(chǔ)存費(fèi)為1，倉(cāng)庫(kù)的最大儲(chǔ)存能力為3臺(tái)，另外，知道在1月1日時(shí)倉(cāng)庫(kù)里存有一臺(tái)變壓器，要求在4月30日倉(cāng)庫(kù)的庫(kù)存量為零。試問(wèn)該公司應(yīng)如何制定生產(chǎn)計(jì)劃，使得四個(gè)月的生產(chǎn)成本和儲(chǔ)存總費(fèi)用最少？解：我們按月份來(lái)劃分階段，第i個(gè)月為第i階段：（i=1,2,3,4).

設(shè)為第k階段期初庫(kù)存量；k=1,2,3,4

§3動(dòng)態(tài)規(guī)劃的應(yīng)用(1)

66

為第k階段生產(chǎn)量；k=1,2,3,4為第k階段需求量；k=1,2,3,4，這已在表10-15中告訴我們。因?yàn)橄聜€(gè)月的庫(kù)存量等于上個(gè)月的庫(kù)存量加上上個(gè)月的產(chǎn)量減去上個(gè)月的需求量，我們就得到了如下?tīng)顟B(tài)轉(zhuǎn)移方程：因?yàn)椋视?/p>

因?yàn)?，故?/p>

§3動(dòng)態(tài)規(guī)劃的應(yīng)用(1)

67

由于必須要滿足需求，則有

通過(guò)移項(xiàng)得到

另一方面，第k階段的生產(chǎn)量必不大于同期的生產(chǎn)能力（4臺(tái)），也不大于第k階段至第四階段的需求之和與第k階段期初庫(kù)存量之差，否則第k階段的生產(chǎn)量就要超過(guò)從第k階段至第四階段的總需求，故有

以下我們從第四階段開(kāi)始計(jì)算：從以上的狀態(tài)轉(zhuǎn)移方程可知這樣就有

§3動(dòng)態(tài)規(guī)劃的應(yīng)用(1)

68

這里的階段指標(biāo)可以分成兩部分，即生產(chǎn)成本與儲(chǔ)存費(fèi)，即為由于第四階段末要求庫(kù)存為零，即有，這樣可得對(duì)于每個(gè)的可行值，的值列于表10－17。

表10－17§3動(dòng)態(tài)規(guī)劃的應(yīng)用(1)

69

表中當(dāng)時(shí)，可知第四階段要生產(chǎn)臺(tái)，從表10－16可知總成本為9，同樣可以算出當(dāng)為1,2,3時(shí)的情況，結(jié)果已列于表10－17中。第三階段：此時(shí)有：因?yàn)?/p>

以及

所以有例如，當(dāng)?shù)谌A段初庫(kù)存量時(shí)，生產(chǎn)量為2時(shí)，則所以生產(chǎn)成本為8，第三階段末庫(kù)存為2時(shí)，儲(chǔ)存費(fèi)為，而§3動(dòng)態(tài)規(guī)劃的應(yīng)用(1)

70查10－17表可知，這樣可知，填入表10－18中的欄內(nèi)，其他結(jié)果如表10－18所示：表10－18

第二階段：因?yàn)樗杂小?動(dòng)態(tài)規(guī)劃的應(yīng)用(1)

71計(jì)算結(jié)果如表10－19所示。

表10－19

§3動(dòng)態(tài)規(guī)劃的應(yīng)用(1)

72

第一階段：因?yàn)楣视?/p>

計(jì)算結(jié)果見(jiàn)表10－20。

表10－20§3動(dòng)態(tài)規(guī)劃的應(yīng)用(1)

73

利用遞推關(guān)系可以從表10－20，表10－19，表10－18和表10－17得到兩組最優(yōu)解：這時(shí)有最低總成本29?！?動(dòng)態(tài)規(guī)劃的應(yīng)用(1)

74§3動(dòng)態(tài)規(guī)劃的應(yīng)用(1)

四、系統(tǒng)可靠性問(wèn)題

例5.某科研項(xiàng)目組由三個(gè)小組用不同的手段分別研究，它們失敗的概率各為0.40，0.60，0.80。為了減少三個(gè)小組都失敗的可能性，現(xiàn)決定給三個(gè)小組中增派兩名高級(jí)科學(xué)家，到各小組后，各小組科研項(xiàng)目失敗概率如下表：?jiǎn)柸绾畏峙煽茖W(xué)家才能使三個(gè)小組都失敗的概率（即科研項(xiàng)目最終失敗的概率）最?。扛呒?jí)科學(xué)家小組12300.400.600.8010.200.400.5020.150.200.3075§3動(dòng)態(tài)規(guī)劃的應(yīng)用(1)

解：用逆序算法。設(shè)階段：每個(gè)研究小組為一個(gè)階段，且階段123小組12376§3動(dòng)態(tài)規(guī)劃的應(yīng)用(1)

計(jì)算當(dāng)n=3時(shí)，當(dāng)n=2時(shí)，s3f3*(s3)x3*00．80010．50120．302

x2s2f2(s2,x2)=P2(x2)·f3*(s2-x2)f2*(s2)x2*01200．480．48010．300．320．30020．180．200．160．16277§3動(dòng)態(tài)規(guī)劃的應(yīng)用(1)

當(dāng)n=1時(shí)，最優(yōu)解為x1*=1，x2*=0，x3*=1；科研項(xiàng)目最終失敗的概率為0.060。x1s1f1(s1,x1)=P1(x1)·f2*(s1-x1)f2*(s2)x2*01220．0640．0600．0720．060178§4動(dòng)態(tài)規(guī)劃的應(yīng)用(2)*一、連續(xù)確定性動(dòng)態(tài)規(guī)劃

對(duì)于狀態(tài)變量和決策變量只取連續(xù)值，過(guò)程的演變方式為確定性時(shí)，這種動(dòng)態(tài)規(guī)劃問(wèn)題就稱為連續(xù)確定性動(dòng)態(tài)規(guī)劃問(wèn)題。79§4動(dòng)態(tài)規(guī)劃的應(yīng)用(2)*機(jī)器負(fù)荷分配問(wèn)題例1一種機(jī)器能在高低兩種不同的負(fù)荷狀態(tài)下工作。設(shè)機(jī)器在高負(fù)荷下生產(chǎn)時(shí)，產(chǎn)量函數(shù)為P1=8u1，其中u1為在高負(fù)荷狀態(tài)下生產(chǎn)的機(jī)器數(shù)目，年完好率為a=0.7，即到年底有70％的機(jī)器保持完好。在低負(fù)荷下生產(chǎn)時(shí)，產(chǎn)量函數(shù)為P2=5u2，其中u2為在低負(fù)荷狀態(tài)下生產(chǎn)的機(jī)器數(shù)目，年完好率為b=0.9。設(shè)開(kāi)始生產(chǎn)時(shí)共有1000臺(tái)完好的機(jī)器，請(qǐng)問(wèn)每年應(yīng)該如何把完好機(jī)器分配給高、低兩種負(fù)荷下生產(chǎn)，才能使得5年內(nèi)生產(chǎn)的產(chǎn)品總產(chǎn)量最高。80§4動(dòng)態(tài)規(guī)劃的應(yīng)用(2)*解建立動(dòng)態(tài)規(guī)劃模型：分為5個(gè)階段，每個(gè)階段為1年。設(shè)狀態(tài)變量sk表示在第k階段初擁有的完好機(jī)器數(shù)目；k=1,2,3,4,5。決策變量xk表示第k階段中分配給高負(fù)荷狀態(tài)下生產(chǎn)的機(jī)器數(shù)目；k=1,2,3,4,5。顯然sk-xk為分配給低負(fù)荷狀態(tài)下生產(chǎn)的機(jī)器數(shù)目。狀態(tài)轉(zhuǎn)移方程為sk+1=0.7xk+0.9(sk-xk)

階段指標(biāo)rk(sk,xk)=8xk+5(sk-xk)

最優(yōu)指標(biāo)函數(shù)，其中k=1,2,3,4,5。

f6(s6)=0。81§4動(dòng)態(tài)規(guī)劃的應(yīng)用(2)*第5階段：因?yàn)閒5(s5)是x5的線性單調(diào)增函數(shù)，故有x5*=s5，于是有f5(s5)=8s5。第4階段：

82§4動(dòng)態(tài)規(guī)劃的應(yīng)用(2)*

同樣的，f4(s4)是x4的線性單調(diào)增函數(shù)，有x4*=s4，f4(s4)=13.6s4。對(duì)前幾個(gè)階段依次類推，可得

f3(s3)=17.5s3，

f2(s2)=20.75s2，

f1(s1)=23.72s1。因?yàn)槠诔豕灿型旰脵C(jī)器1000臺(tái)，故s1=1000。有f1(s1)=23.72s1＝23720，即5年最大的產(chǎn)量為23720臺(tái)。得最優(yōu)解為，，，。這意味著前兩年應(yīng)把年初完好機(jī)器完全投入低負(fù)荷生產(chǎn)，后三年應(yīng)把年初完好機(jī)器完全投入高負(fù)荷生產(chǎn)。83§4動(dòng)態(tài)規(guī)劃的應(yīng)用(2)*

下一步工作是確定每年初的狀態(tài)，按照從前向后的順序依次計(jì)算出每年年初完好的機(jī)器數(shù)目。已知s1=1000,根據(jù)狀態(tài)轉(zhuǎn)移方程，有:84§4動(dòng)態(tài)規(guī)劃的應(yīng)用(2)*上面所討論的最優(yōu)策略過(guò)程，初始端狀態(tài)s1=1000臺(tái)是固定的，終點(diǎn)狀態(tài)s6沒(méi)有要求。這種情況下得到最優(yōu)決策稱為初始端固定終點(diǎn)自由的最優(yōu)策略。如果終點(diǎn)附加一定的條件，則問(wèn)題就稱為“終端固定問(wèn)題”。例如，規(guī)定在第5年度結(jié)束時(shí)仍要保持500臺(tái)機(jī)器完好（而不是278臺(tái)），應(yīng)如何安排生產(chǎn)才能使得總產(chǎn)量最大？下面來(lái)分析：根據(jù)終點(diǎn)條件有

可得85§4動(dòng)態(tài)規(guī)劃的應(yīng)用(2)*顯然，由于固定了終點(diǎn)的狀態(tài)，x5的取值受到了約束。因此有類似的，

容易解得，f4(s4)=21.7s4-7500。

86§4動(dòng)態(tài)規(guī)劃的應(yīng)用(2)*

依次類推，得

f3(s3)=24.5s3-7500f2(s2)=27.1s2-7500f1(s1)=29.4s1-7500

再采用順序方法遞推計(jì)算各年的狀態(tài)，有

s1=1000，

87§4動(dòng)態(tài)規(guī)劃的應(yīng)用(2)*

可見(jiàn)，為了使終點(diǎn)完好的機(jī)器數(shù)量增加到500臺(tái)，需要安排前四年中全部完好機(jī)器都要投入低負(fù)荷生產(chǎn)，且在第5年，也只能全部投入高負(fù)荷。相應(yīng)的最優(yōu)指標(biāo)為

f1(s1)=29.4s1-7500＝21900。

可以看到，因?yàn)樵黾恿烁郊訔l件，總產(chǎn)量f1(s1)要比終點(diǎn)自由情況下的產(chǎn)量要低。88二、離散隨機(jī)性動(dòng)態(tài)規(guī)劃隨機(jī)型的動(dòng)態(tài)規(guī)劃是指狀態(tài)的轉(zhuǎn)移律是不確定的，即對(duì)給定的狀態(tài)和決策，下一階段的到達(dá)狀態(tài)是具有確定概率分布的隨機(jī)變量，這個(gè)概率分布由本階段的狀態(tài)和決策完全確定。隨機(jī)型動(dòng)態(tài)規(guī)劃的基本結(jié)構(gòu)如下圖：

§4動(dòng)態(tài)規(guī)劃的應(yīng)用(2)*

sk狀態(tài)

xk決策概率k階段的收益p1p2pN….k+1階段的狀態(tài)sk+1c1c2cN

1

2N89§4動(dòng)態(tài)規(guī)劃的應(yīng)用(2)*圖中N表示第k+1階段可能的狀態(tài)數(shù)，p1、p2、…pN為給定狀態(tài)sk和決策xk的前提下，可能達(dá)到下一個(gè)狀態(tài)的概率。ci為從k階段狀態(tài)sk轉(zhuǎn)移到k+1階段狀態(tài)為i時(shí)的指標(biāo)函數(shù)值。在隨機(jī)性的動(dòng)態(tài)規(guī)劃問(wèn)題中，由于下一階段到達(dá)的狀態(tài)和階段的效益值不確定，只能根據(jù)各階段的期望效益值進(jìn)行優(yōu)化。90離散隨機(jī)性動(dòng)態(tài)規(guī)劃例2