第11章-動(dòng)態(tài)規(guī)劃

1、精選優(yōu)質(zhì)文檔-傾情為你奉上第11章 動(dòng)態(tài)規(guī)劃一個(gè)隨事件或階段推移的系統(tǒng)叫做動(dòng)態(tài)系統(tǒng)，動(dòng)態(tài)規(guī)劃是解決多階段決策過(guò)程最優(yōu)化的一種數(shù)學(xué)方法。一個(gè)系統(tǒng)依據(jù)某種方式分為許多個(gè)不同的階段，這些階段不僅有著次序推移性，而且相互間有著依賴和影響。這樣，在多階段決策過(guò)程中，每個(gè)階段決策的選擇，不僅要依據(jù)次序來(lái)考查某階段的效果，而且要顧及此決策對(duì)以后各階段決策的影響。一般情況下，為得到整個(gè)系統(tǒng)的最優(yōu)選擇，必須放棄對(duì)某個(gè)階段來(lái)說(shuō)最佳的決策。對(duì)各個(gè)階段所做的決策形成確定整個(gè)系統(tǒng)的決策序列，稱這樣的決策序列為系統(tǒng)的一個(gè)策略。對(duì)應(yīng)某一確定的策略，整個(gè)系統(tǒng)依據(jù)某種數(shù)量指標(biāo)衡量其決策的優(yōu)劣。多階段決策過(guò)程就是在所有允許策略集

2、合中。確定一個(gè)達(dá)到最有指標(biāo)的最優(yōu)策略。這種衡量系統(tǒng)的指標(biāo)一般取最大值或最小值的策略。因此，多階段決策過(guò)程也是一個(gè)可以構(gòu)成多個(gè)變量的最優(yōu)化問(wèn)題。動(dòng)態(tài)規(guī)劃就是解決此類多階段決策過(guò)程的最優(yōu)化方法。雖然動(dòng)態(tài)規(guī)劃主要解決多階段決策的動(dòng)態(tài)系統(tǒng)，但是可分階段的靜態(tài)系統(tǒng)問(wèn)題也能作為特例用它有效地求解。§11.1 動(dòng)態(tài)規(guī)劃的基本原理 本章通過(guò)構(gòu)造數(shù)學(xué)模型，形成具有特殊的動(dòng)態(tài)系統(tǒng)過(guò)程，將基于某種方式把整個(gè)過(guò)程分成若干個(gè)互相聯(lián)系的階段，在其每個(gè)階段都需要作出決策，從而使整個(gè)過(guò)程達(dá)到最佳效果。同時(shí)，各個(gè)階段決策的選擇依賴于該階段的狀態(tài)以及前階段或后階段的變化。各個(gè)階段決策確定后，組成一個(gè)決策序列，從而形成了

3、整個(gè)過(guò)程具有前后關(guān)聯(lián)的鏈狀結(jié)構(gòu)的多階段決策過(guò)程，稱為序貫決策過(guò)程。先用下面的最短路問(wèn)題（問(wèn)題可分成階段性）來(lái)說(shuō)明動(dòng)態(tài)規(guī)劃的基本思想。例 1，最短路問(wèn)題。圖111所示是一個(gè)路線網(wǎng)絡(luò)圖，連線上的數(shù)字表示兩點(diǎn)之間的距離（或費(fèi)用），要求尋找一條由A到E的路線，使距離最短（或費(fèi)用最?。?。對(duì)于這樣的一個(gè)比較簡(jiǎn)單的問(wèn)題，可直接使用枚舉法例舉所有從A到E得路線，確定出所應(yīng)走的路線是距離最短或費(fèi)用最少，用動(dòng)態(tài)規(guī)劃的思想，如果已找到由A到E得最短路線是AB1C2D2E（記作L），那么當(dāng)尋求L中的任何一點(diǎn)（如C2）到E得最短路時(shí)，它必然是L子路線 C2D2E(記作L1)。否則，如D2到E的最短路是另一條路線L2，則

4、把AB1C2與L2連接起來(lái)，就會(huì)得到一條不同于L的從A到E得最短路，根據(jù)最短路的這一特性，可以從最后一段開(kāi)始，用逐步向前遞推的方法，一次求出路段上各點(diǎn)到E的最短路，最后得到A到E得最短路。上述這種由系統(tǒng)的最后階段逐段向初始階段求最優(yōu)的過(guò)程稱為動(dòng)態(tài)規(guī)劃的解法。該過(guò)程揭示了動(dòng)態(tài)規(guī)劃的基礎(chǔ)思想，為便于對(duì)動(dòng)態(tài)規(guī)劃的思想和方法進(jìn)行數(shù)學(xué)描述，下面先引入動(dòng)態(tài)規(guī)劃的基本概念并建立最優(yōu)目標(biāo)函數(shù)。（1）分階段：適當(dāng)?shù)匾罁?jù)具體情況將系統(tǒng)分成若干個(gè)相互聯(lián)系的階段，并將各個(gè)段按順序或逆序加以編號(hào)（常用K），描述階段的變量稱為階段變量。如例1可分為5個(gè)階段，k=1，2，3，4，5. （2）狀態(tài)：狀態(tài)表示系統(tǒng)在某一階段所處

5、的位置。描述過(guò)程狀態(tài)的變量稱為狀態(tài)變量，第k階段的狀態(tài)變量常用sk表示，狀態(tài)變量的集合用Sk表示。如在例1中，第一階段有一個(gè)狀態(tài)就是初始位置A，第三階段有3個(gè)狀態(tài)，即集合S3=.(3)決策：當(dāng)系統(tǒng)處于某一階段的某個(gè)狀態(tài)時(shí)，可以作出不同的決定（或選擇），從而確定下一階段的狀態(tài)，這種決定稱為決策。如在例1第二階段中，從狀態(tài)B2出發(fā)，其允許決策集合為D2（B2）=(4)策略：由系統(tǒng)各階段確定的決策所形成的決策序列稱為策略。從初始狀態(tài)s1出發(fā)，由系統(tǒng)的所有n個(gè)階段的決策所形成的策略成為全過(guò)程策略，從允許策略集合中找出達(dá)到最有效果的策略稱為最優(yōu)策略。（5）狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程是確定過(guò)程有一個(gè)狀態(tài)到

6、另一個(gè)狀態(tài)的演變過(guò)程。若給定第k階段狀態(tài)的演變過(guò)程，并且若該階段的決策變量dk一經(jīng)確定，第k+1階段的狀態(tài)變量sk+1也就完全確定。如例1中，狀態(tài)轉(zhuǎn)移方程為 sk+1=dk(sk).（6）階段收益：若確定某一階段的系統(tǒng)狀態(tài)，執(zhí)行某一階段決策所得的效益稱為階段效益，他是整個(gè)系統(tǒng)總收益的一部分。階段效益是階段狀態(tài)和決策變量的函數(shù)。如在例1中階段效益為走完一段路程所走過(guò)的距離。（7）指標(biāo)函數(shù)和最優(yōu)值函數(shù)：系統(tǒng)執(zhí)行某策略所產(chǎn)生效果的優(yōu)劣可用數(shù)學(xué)指標(biāo)來(lái)衡量，它是各個(gè)階段狀態(tài)和決策的函數(shù)，稱為指數(shù)函數(shù)。（8）邊值條件：在系統(tǒng)決策的狀態(tài)推移進(jìn)程中最初的條件稱為邊值條件。由系統(tǒng)的最后階段逐段向初始階段求最優(yōu)的

7、過(guò)程稱為速推解法，由系統(tǒng)的最前階段逐段向終結(jié)階段求最優(yōu)的過(guò)程稱為順序推解法。如例1顯然有邊值條件： fn+1(sn+1)=0.根據(jù)上述確定的階段編號(hào)。狀態(tài)變量、決策變量、狀態(tài)轉(zhuǎn)移方程、邊值條件及指標(biāo)函數(shù)。確定例1的最短路線，計(jì)算步驟如下：根據(jù)最短路線特性，尋找最短路線的方法，將從最后一段開(kāi)始，用后向前逐步地推的方法，求出各點(diǎn)到點(diǎn)E的最短路線，最后求得由點(diǎn)A到點(diǎn)E的最短線，所以，動(dòng)態(tài)規(guī)劃的方向是從各點(diǎn)逐段向始點(diǎn)方向?qū)ふ易疃搪肪€的一種方法，見(jiàn)圖112. 當(dāng)k=4時(shí)，有D1到終點(diǎn)E只有一條路線，故f4（D1）=4，同理，f4（D2）=3.當(dāng)k=3時(shí)，出發(fā)點(diǎn)有C1,C2,C33個(gè)，若從C1出發(fā)，則有兩

8、個(gè)選擇，一是至D1，一是至D2，則F3（C1）=min=min=7.其相應(yīng)的決策為d3（C1）=D1，表示由D1,至終點(diǎn)E的最短距離為7，其最短距離路線是C1D1E.同理，從C2和C3出發(fā)，則有 f3（C2）=。其相應(yīng)的決策為d3（C2）=D2。 f3（C3）=min且d3（C3）=D3。 類似地。可計(jì)算當(dāng)k=2時(shí)，有f2(B1)=12, d2(B1)=C2. f2(B2）=11, d2（B2）=C2， f2（B3）=9, d2（B3）=C3當(dāng)k=1時(shí)，出發(fā)點(diǎn)只有一個(gè)點(diǎn)A，則f1(A)=min,且d1(A)=B1，于是獲得從始點(diǎn)A至終點(diǎn)E的最短距離為15，為便于找出最短路線，在按計(jì)算的順序推之

9、，可求出最優(yōu)決策函數(shù)序列dk，即由d1（A）=B1,d2（B）=C2,d3（C2）=D2,d4（D2）=E組成一個(gè)最優(yōu)策略。那么最短路線為 AB1C2D2E.§11.2 中學(xué)生數(shù)學(xué)知識(shí)應(yīng)用競(jìng)賽題舉例例2今年盛夏酷暑，能源緊張，某工廠從能源部門獲得5個(gè)單位某種能源，該工廠有3個(gè)部門需要這種能源，由于各部門所使用設(shè)備條件不同，生產(chǎn)的產(chǎn)品也不同，這樣導(dǎo)致是用能源所產(chǎn)生的收益情況也不同，所用的能源為整數(shù)單位，各部門具體產(chǎn)生的收益（萬(wàn)元）如表111所示，為能有效地利用這種能源，工廠將如何分配能源給各部門,使工廠受益最大?表111收益（萬(wàn)元）部門能源0 1 2 3 4 51230 2 4 5 5

10、 60 1 3 4 6 80 3 4 5 5 6解 設(shè)3個(gè)部門分配到的能源分別為x1，x2，x3單位，相應(yīng)每個(gè)單位所產(chǎn)生的收益設(shè)為c1(x1),c2(x2),c3(x3）,a那么模型為 Maxc1(x1)+c2(x2)+c3(x3); s.t. x1+x2+x3 5 x1,x2,x3 0為整數(shù)。使用遞推方法來(lái)求解。按k=1，2，3為3階段，用fk（z）表示在第k階段所用能源為z單位時(shí)，獲得最大收益，即有 f3（5）=maxc1(x1)+c2(x2)+c3(x3); s.t. x1+x2+x3 5. x1,x2,x3 0為整數(shù)。于是 f3(5)=maxf2(5-x3)+c3(x3)(x3=1,1

11、,2,3.5) =maxf2(5),f2(4)+3,f2(3)+4,f2(2)+5,f2(1)+5,f2(0)+6; f2(5)=maxf1(5-x2)+c2(x2)(x2=0,1,2,.5) =maxf1(5)，f1(4)+1，f1(3)+3,f1(2)+4,f1(1)+6,f2(0)+8f2(4)=maxf1(4-x2)+c2(x2) (x2=0,1,2,4) =maxf1(4),f1(3)+1,f1(2)+3,f1(1)+4,f1(0)+6;f2(3)=maxf1(3-x2)+c2(x2)(x2=0,1,3) maxf1(3),f1(2)+1,f1(1)+3,f1(0)+4;f2(2)=

12、maxf1(2),f(1)+1,f1(0)+3；f2(1)=maxf1(1),f1(0)+1.將f1(0)=0，f1(1)=2,f1(2)=4,f1(3)=5,f1(4)=5，f1(5)=6回代得f2（1)=2f2（2）=max4，2+1,3=4，f2(3)=max5,4+1,2+3,4=5,f2(4)=max5,5+1,4+3,2+4,6=7,f2(5)=max6,5+2,5+3,4+4,2+6,8=8.f2(5)=max8,7+3,5+4,4+5,2+5,6=10于是解為x3*=1，x2*=2，x1*=2，最大收益為10（萬(wàn)元），即分配給3個(gè)部門的分別為：部門1，部門2都為2單位，而部門3

13、為1單位，最大收益為10萬(wàn)元。.§11.3 復(fù)合系統(tǒng)工作可靠性問(wèn)題若某種機(jī)器的工作系統(tǒng)有n個(gè)部件串聯(lián)組成，只要有一個(gè)部件失靈，整個(gè)系統(tǒng)就不能工作，為提高系統(tǒng)工作的可靠性，在每一個(gè)部件上均配有主要元件的備用件，并且設(shè)計(jì)了備用元件自動(dòng)投入裝置。顯然，備用元件越多，整個(gè)系統(tǒng)正常工作的可靠性越大，但備用元件多了，整個(gè)系統(tǒng)的成本、重量、體積均相應(yīng)增大，工作精度也降低，因此，最優(yōu)化問(wèn)題是在考慮上述限制條件下，應(yīng)如何選擇個(gè)部件的備用元件數(shù)，使整個(gè)系統(tǒng)的工作可靠性最大。設(shè)部件i（i=1，2，.n）上裝有ui個(gè)備用件時(shí)，它正常工作的概率為pi（ui）。例 3 某個(gè)廠設(shè)計(jì)一種電子設(shè)備，由3種元件D1,D

14、2,D3組成，已知這3中元件的價(jià)格和可靠性如112所示。要求在設(shè)計(jì)中所使用元件的費(fèi)用不超過(guò)105元，試問(wèn)：應(yīng)如何設(shè)計(jì)室設(shè)備的可靠性達(dá)到最大（不考慮重量的限制）？表112元件單價(jià)（元）可靠性D1D2D33015200.90.80.5解 按元件種類劃分為3各階段，設(shè)狀態(tài)變量sk表示能容許用在Dk元件至D3元件的總費(fèi)用；決策變量xk表示在Dk元件上的并聯(lián)個(gè)數(shù)；Pk表示一個(gè)Dk元件正常工作的概率，則為xk個(gè)Dk元件不正常工作的概率，另最優(yōu)值函數(shù)fk（sk）表示由狀態(tài)sk開(kāi)始從Dk元件至D3元件組成的系統(tǒng)的最大可靠性，因而有f3(s3)=f2(s2)=f1(s2)= 由于s1=105，故解此問(wèn)題只要求出

15、f1（105）即可，而 f1(105)= f3(30)=0.5, f3(15)=0,所以 f2(75)=max0.8×0.875，0.96×0.75，0.992 ×.5，0.9984×0 =max0.7,0.72,0.496 =0.72.同理 f2(45)=max0.8f3(30),0.96f3(30)=max0.4,0=0.4, f2(15)=0.故 f2(105)=max0.9 ×.72,0.99×0.4,0.999×0 =max0.648,0.396=0.648.從而求得x1*=1,x2*=2,x3*=2為最優(yōu)方案，即

16、D1元件用2個(gè)，D3元件用2個(gè)，其總費(fèi)用為100元，可靠性為0.648。§11.4 不確定性的采購(gòu)問(wèn)題本節(jié)敘述在生產(chǎn)和經(jīng)營(yíng)管理中，經(jīng)常遇到在價(jià)格有波動(dòng)時(shí)如何合理購(gòu)買的問(wèn)題，不確定性的采購(gòu)問(wèn)題的最優(yōu)化目標(biāo)為制定采購(gòu)策略，對(duì)不同時(shí)期的浮動(dòng)借個(gè)和概率，確定采購(gòu)量以使總的采購(gòu)費(fèi)用（數(shù)學(xué)期望值）最小。 例 4 某公司在近5周內(nèi)必須一次性采購(gòu)原料一批，估計(jì)在未來(lái)5周內(nèi)價(jià)格有波動(dòng)，期浮動(dòng)價(jià)格和概率（可能性）如表113所示。試求各周中處在什么價(jià)位時(shí)應(yīng)購(gòu)入，使采購(gòu)價(jià)格最為合理？費(fèi)用數(shù)學(xué)期望值最?。繂蝺r(jià)（千元/噸）概率1816140.40.30.3解 這里價(jià)格是一個(gè)隨機(jī)變量，是按某種已知的概率分布取值的

17、。用動(dòng)態(tài)規(guī)劃方法處理，按采購(gòu)期限將5周分為5個(gè)階段，將每周的價(jià)格看做該階段的狀態(tài)，設(shè)yk為狀態(tài)變量，表示第k周的實(shí)際價(jià)格；xk為決策變量。當(dāng)x=1，表示第k周決定采購(gòu)；當(dāng)xk=0，表示第k周決定等待。用ykE表示第k周決定等待，而在以后采取最優(yōu)決策時(shí)采購(gòu)價(jià)格的期望值；用fk（yk）表示第k周實(shí)際價(jià)格為yk時(shí)，從第k周至第5周采取最優(yōu)策略所得的最小期望值。因而可寫(xiě)出逆序遞推關(guān)系為 fk(yk)=minyk,ykE，ykSk, f5(yk)=y5, y5S5其中Sk=18，16，14，k=1，2，3，4，5.由ykE和fk（yk）的定義可知 ykE=efk+1(yk+1)=0.4fk+1(18)+0.3fk+1(16)+0.3fk+1(14). (113)并且得出最優(yōu)決策為 xk=從最后一周開(kāi)始；逐步向前遞推計(jì)算，具體計(jì)算過(guò)程如下： 當(dāng)k=5是，因f5(y5)=y5,y5 S5,故有 f5(18)=18;f5(16)=16;f5(14)=14,即在第5周時(shí)，若所需的原料尚未買入，則無(wú)論市場(chǎng)價(jià)格如何，都必須采購(gòu)，不能再等。當(dāng)k=5時(shí)，由ykE=0.4fk+1(18)+0.3fk+1(16)+0.3fk+1(14)可知 y4E=0.4×18+0.3&#