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

第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ò)程就是在所有允許策略集合中。確定一個(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è)決策序列，從而形成了整個(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)題。圖11-1所示是一個(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得最短路線是A—B]—C2—D2—E（記作1），那么當(dāng)尋求L中的任何一點(diǎn)（如C2）到E得最短路時(shí)，它必然是L子路線C2—D2—E（記作L]）。否則，如D2到E的最短路是另一條路線L2，則把A—B1—C2與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)在某一階段所處的位置。描述過(guò)程狀態(tài)的變量稱為狀態(tài)變量，第k階段的狀態(tài)變量常用sk表示，狀態(tài)變量的集合用Sk表示。如在例1中，第一階段有一個(gè)狀態(tài)就是初始位置A，第三階段有3個(gè)狀態(tài)，即集合S3={C1,C2,C3}.（3）決策：當(dāng)系統(tǒng)處于某一階段的某個(gè)狀態(tài)時(shí)，可以作出不同的決定（或選擇），從而確定下一階段的狀態(tài)，這種決定稱為決策。如在例1第二階段中，從狀態(tài)B2出發(fā)，其允許決

策集合為D2（B2）=（4）策略：由系統(tǒng)各階段確定的決策所形成的決策序列稱為策略。從初始狀態(tài)si出發(fā)，由系統(tǒng)的所有n個(gè)階段的決策所形成的策略成為全過(guò)程策略，從允許策略集合中找出達(dá)到最有效果的策略稱為最優(yōu)策略。（5）狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程是確定過(guò)程有一個(gè)狀態(tài)到另一個(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)的過(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)圖11—2.當(dāng)k=4時(shí)，有D1到終點(diǎn)E只有一條路線，故f4（D1）=4，同理，f4（D2）=3.r(C,D)+f(D1)

3 11 4r(Cr(C,D)+f(D1)

3 11 4r(C,D)+f(D)

312 42F3(C1)=min<=min{5+4}=7.（C1）（C1）=D］，表示由D1,至終點(diǎn)E的最短距離為7,其最短距離路線是C1—D1—E.同理，從C2和C3出發(fā)，則有{r(C,D)+f(D)[ .{4+41f(C)=〈3 2 1 4 1 .=min〈 .=6。3 2 ，(C,D)+f(D)J [3+3Jv5 2 2 4 2其相應(yīng)的決策為d3(C2)=D2。f3(C3)=min<\r(C,D)+f(D)I.{6+4]f3(C3)=min<3 3 1 4 1 \=min5 \=10,r(C,D)+f(D)J [9+3Jv3 3 2 4 2且d3（C3）=D3。類似地。可計(jì)算當(dāng)k=2時(shí)，有f2（B1）=12, d2（B1）=C2.

f2(B2)=H, d2IB?)=C2,f2(B3)=9, d2(B3)=C3當(dāng)k=1時(shí)，出發(fā)點(diǎn)只有一個(gè)點(diǎn)A,貝0I J3+12、>=min<5+11>=15Ih+9|'[,I J3+12、>=min<5+11>=15Ih+9|'TOC\o"1-5"\h\z1 2 1f1(A)=min"(A,B)+f(B)2 2 2r(A,B)+f(B)13 2 3且d1(A)=B1，于是獲得從始點(diǎn)A至終點(diǎn)E的最短距離為15,為便于找出最短路線，在按計(jì)算的順序推之，可求出最優(yōu)決策函數(shù)序列{dk},即由d1(A)=B],d2(B)=C2，d3(C2)=D2,d4(D2)=E組成一個(gè)最優(yōu)策略。那么最短路線為A—B]—C2—D2—E.§11.2中學(xué)生數(shù)學(xué)知識(shí)應(yīng)用競(jìng)賽題舉例例2今年盛夏酷暑，能源緊張，某工廠從能源部門(mén)獲得5個(gè)單位某種能源，該工廠有3個(gè)部門(mén)需要這種能源，由于各部門(mén)所使用設(shè)備條件不同，生產(chǎn)的產(chǎn)品也不同，這樣導(dǎo)致是用能源所產(chǎn)生的收益情況也不同，所用的能源為整數(shù)單位，各部門(mén)具體產(chǎn)生的收益(萬(wàn)元)如表11-1所示，為能有效地利用這種能源，工廠將如何分配能源給各部門(mén)使工廠受益最大？表11—1、'收益(萬(wàn)元)部門(mén)0能源51234102455620134683034556解設(shè)3個(gè)部門(mén)分配到的能源分別為x1，x2,x3單位，相應(yīng)每個(gè)單位所產(chǎn)生的收益設(shè)為c1(x1),c2(x2),c3(x3),a那么模型為Max{c1(x1)+c2(x2)+c3(x3)};s.t. x1+x2+x3W5x1,x2,x330為整數(shù)。使用遞推方法來(lái)求解。按k=1,2,3為3階段，用fk(z)表示在第k階段所用能源為z單位時(shí)，獲得最大收益，即有f(5)=max{c(x)+0,(^)+^(^)}；3 1V12、2,3、3'S.t. x】+x2+x3v5.x1,x2,x330為整數(shù)。于是f3(5)=max{f2(5-x3)+c3(x3)}(x3=1,1,2,3..5)=max{f(5),f(4)+3,f(3)+4,f(2)+5,f(1)+5,f(0)+6};LO'' f2(5)=max{f1(5-x2)+c2(x2)}(x2=0,1,2,....5)=max{f1(5),f1(4)+1f2(5)=maxf2(4)=max{f1(4-x2)+c2(x2)}(x2=0,1,2,.4)=max{f1(4),f1(3)+1,f1(2)+3,f1(1)+4,f1(0)+6};f2(3)=max{f1(3-x2)+c2(x2)}(x2=0,1,3)max{f1(3),f1(2)+1,f1(1)+3,f1(0)+4};f2(2)=max{f](2),f(1)+1,f](0)+3}；f(1)=max{f(1),f(0)+1}.將f1(0)=0,f1(1)=2,f1(2)=4,f1(3)=5,f1(4)=5,f1(5)=6回代得f2(1)=2

f2（2）=max{4,2+1,3}=4,f2（3）=max{5,4+1,2+3,4}=5,f2（4）=max{5,5+1,4+3,2+4,6}=7,f2（5）=max{6,5+2,5+3,4+4,2+6,8}=8.f2（5）=max{8,7+3,5+4,4+5,2+5,6}=10于是解為x3*=1,x2*=2,x1*=2，最大收益為10（萬(wàn)元），即分配給3個(gè)部門(mén)的分別為：部門(mén)1，部門(mén)2都為2單位，而部門(mén)3為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）o例3某個(gè)廠設(shè)計(jì)一種電子設(shè)備，，由3種元件D1,D2,D3組成，已知這3中元件的價(jià)格和可靠性如11—2所示。要求在設(shè)計(jì)中所使用元件的費(fèi)用不超過(guò)105元，試問(wèn)：應(yīng)如何設(shè)計(jì)室設(shè)備的可靠性達(dá)到最大（不考慮重量的限制）？表11—2元件單價(jià)（元）可靠性D1300.9D2150.8D3200.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)=max[1-f3(s3)=f2(s2)=f1(s2)=f(s-15x)};3 2 2f(s-30f(s-15x)};3 2 2f(s-30x)}21 1max{1-(0.2)x21<x2<[s2/15]〈maxf1—(0.1)氣1<氣<[s1/30] '由于s1=105，故解此問(wèn)題只要求出f1(105)即可，而imax{1-(0.1)氣]f2(105-30xp=max{fo.9f(75),0.99f(45),0.999f(15)]},22 2但f1(105)=f(75)=max缶-(0.2)x]f(75-15x)}2f1<X2<4 2 3 2 )=max{0.8f(60),0.96f(45),0.992f(30),0.998f(15)}33 3 3且f(60)=max[1-(1.5)x3]=max{0.5,0.75,0.873}=0.875,3 1<x3<3f3(30)=0.5,f3(15)=0,所以f2(75)=max{0.8X0.875,0.96X0.75,0.992X.5,0.9984X0}=max{0.7,0.72,0.496}=0.72.同理f2(45)=max{0.8f3(30),0.96f3(30)}=max{0.4,0}=0.4,f2(15)=0.故f2(105)=max{0.9X.72,0.99X0.4,0.999X0}=max{0.648,0.396}=0.648.從而求得x1*=1,x2*=2,x3*=2為最優(yōu)方案，即D1元件用2個(gè)，D3元件用2個(gè)，其總費(fèi)用為100元，可靠性為0.648?！?1.4不確定性的采購(gòu)問(wèn)題本節(jié)敘述在生產(chǎn)和經(jīng)營(yíng)管理中，經(jīng)常遇到在價(jià)格有波動(dòng)時(shí)如何合理購(gòu)買(mǎi)的問(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à)格和概率(可能性)如表11—3所示。試求各周中處在什么價(jià)位時(shí)應(yīng)購(gòu)入，使采購(gòu)價(jià)格最為合理？費(fèi)用數(shù)學(xué)期望值最??？單價(jià)(千元/噸)概率180.4160.3140.3解這里價(jià)格是一個(gè)隨機(jī)變量，是按某種已知的概率分布取值的。用動(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)=min{yk,ykE}，ykGSk,f5(yk)=y5, y5eS5其中Sk={18，16，14}，k=1，2，3,4，5.由ykE和fk(yk)的定義可知y.=ef,(yJ=0.4f,(18)+0.3f,(16)+0.3f,(14). (11—3)JVT7 V_i_1V_i_1/ V_i_1、 / V_i_1、 / V_i_1、 / 、 /kE k+1 k+1 k+1 k+1 k+1并且得出最優(yōu)決策為[1(采購(gòu))，當(dāng)/(y)=y;kkk廣〔0(等待)，當(dāng)^(y)=y.七 kkkE從最后一周開(kāi)始；逐步向前遞推計(jì)算，具體計(jì)算過(guò)程如下：當(dāng)k=5是，因f5(y5)=y5,y5S5,故有f5(18)=18;f5(16)=16;f5(14)=14,即在第5周時(shí)，若所需的原料尚未買(mǎi)入，則無(wú)論市場(chǎng)價(jià)格如何，都必須采購(gòu)，不能再等。當(dāng)k=5時(shí)，由y“=0.4fii(18)+0.3fii(16)+0.3fii(14)可知kEk+1 k+1 k+1y4E=0.4X18+0.3X16+0.3X14=16.2.于是，由（11—3）式，得y(y)=min{y,y}=min{y,