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

第11章動態(tài)規(guī)劃一個隨事件或階段推移的系統(tǒng)叫做動態(tài)系統(tǒng)，動態(tài)規(guī)劃是解決多階段決策過程最優(yōu)化的一種數(shù)學(xué)方法。一個系統(tǒng)依據(jù)某種方式分為許多個不同的階段，這些階段不僅有著次序推移性，而且相互間有著依賴和影響。這樣，在多階段決策過程中，每個階段決策的選擇，不僅要依據(jù)次序來考查某階段的效果，而且要顧及此決策對以后各階段決策的影響。一般情況下，為得到整個系統(tǒng)的最優(yōu)選擇，必須放棄對某個階段來說最佳的決策。對各個階段所做的決策形成確定整個系統(tǒng)的決策序列，稱這樣的決策序列為系統(tǒng)的一個策略。對應(yīng)某一確定的策略，整個系統(tǒng)依據(jù)某種數(shù)量指標(biāo)衡量其決策的優(yōu)劣。多階段決策過程就是在所有允許策略集合中。確定一個達(dá)到最有指標(biāo)的最優(yōu)策略。這種衡量系統(tǒng)的指標(biāo)一般取最大值或最小值的策略。因此，多階段決策過程也是一個可以構(gòu)成多個變量的最優(yōu)化問題。動態(tài)規(guī)劃就是解決此類多階段決策過程的最優(yōu)化方法。雖然動態(tài)規(guī)劃主要解決多階段決策的動態(tài)系統(tǒng)，但是可分階段的靜態(tài)系統(tǒng)問題也能作為特例用它有效地求解。§11.1動態(tài)規(guī)劃的基本原理本章通過構(gòu)造數(shù)學(xué)模型，形成具有特殊的動態(tài)系統(tǒng)過程，將基于某種方式把整個過程分成若干個互相聯(lián)系的階段，在其每個階段都需要作出決策，從而使整個過程達(dá)到最佳效果。同時，各個階段決策的選擇依賴于該階段的狀態(tài)以及前階段或后階段的變化。各個階段決策確定后，組成一個決策序列，從而形成了整個過程具有前后關(guān)聯(lián)的鏈狀結(jié)構(gòu)的多階段決策過程，稱為序貫決策過程。先用下面的最短路問題（問題可分成階段性）來說明動態(tài)規(guī)劃的基本思想。例1，最短路問題。圖11-1所示是一個路線網(wǎng)絡(luò)圖，連線上的數(shù)字表示兩點之間的距離（或費用），要求尋找一條由A到E的路線，使距離最短（或費用最?。τ谶@樣的一個比較簡單的問題，可直接使用枚舉法例舉所有從A到E得路線，確定出所應(yīng)走的路線是距離最短或費用最少，用動態(tài)規(guī)劃的思想，如果已找到由A到E得最短路線是A—B]—C2—D2—E（記作1），那么當(dāng)尋求L中的任何一點（如C2）到E得最短路時，它必然是L子路線C2—D2—E（記作L]）。否則，如D2到E的最短路是另一條路線L2，則把A—B1—C2與L2連接起來，就會得到一條不同于L的從A到E得最短路，根據(jù)最短路的這一特性，可以從最后一'段開始，用逐步向前遞推的方法，一次求出路段上各點到E的最短路，最后得到A到E得最短路。上述這種由系統(tǒng)的最后階段逐段向初始階段求最優(yōu)的過程稱為動態(tài)規(guī)劃的解法。該過程揭示了動態(tài)規(guī)劃的基礎(chǔ)思想，為便于對動態(tài)規(guī)劃的思想和方法進(jìn)行數(shù)學(xué)描述，下面先引入動態(tài)規(guī)劃的基本概念并建立最優(yōu)目標(biāo)函數(shù)。（1）分階段：適當(dāng)?shù)匾罁?jù)具體情況將系統(tǒng)分成若干個相互聯(lián)系的階段，并將各個段按順序或逆序加以編號（常用K），描述階段的變量稱為階段變量。如例1可分為5個階段，k=1，2，3，4，5.（2）狀態(tài)：狀態(tài)表示系統(tǒng)在某一階段所處的位置。描述過程狀態(tài)的變量稱為狀態(tài)變量，第k階段的狀態(tài)變量常用sk表示，狀態(tài)變量的集合用Sk表示。如在例1中，第一階段有一個狀態(tài)就是初始位置A，第三階段有3個狀態(tài)，即集合S3={C1,C2,C3}.（3）決策：當(dāng)系統(tǒng)處于某一階段的某個狀態(tài)時，可以作出不同的決定（或選擇），從而確定下一階段的狀態(tài)，這種決定稱為決策。如在例1第二階段中，從狀態(tài)B2出發(fā)，其允許決

策集合為D2（B2）=（4）策略：由系統(tǒng)各階段確定的決策所形成的決策序列稱為策略。從初始狀態(tài)si出發(fā)，由系統(tǒng)的所有n個階段的決策所形成的策略成為全過程策略，從允許策略集合中找出達(dá)到最有效果的策略稱為最優(yōu)策略。（5）狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程是確定過程有一個狀態(tài)到另一個狀態(tài)的演變過程。若給定第k階段狀態(tài)的演變過程，并且若該階段的決策變量dk一經(jīng)確定，第k+1階段的狀態(tài)變量sk+1也就完全確定。如例1中，狀態(tài)轉(zhuǎn)移方程為sk+1=dk（sk）-（6） 階段收益：若確定某一階段的系統(tǒng)狀態(tài)，執(zhí)行某一階段決策所得的效益稱為階段效益，他是整個系統(tǒng)總收益的一部分。階段效益是階段狀態(tài)和決策變量的函數(shù)。如在例1中階段效益為走完一段路程所走過的距離。（7） 指標(biāo)函數(shù)和最優(yōu)值函數(shù)：系統(tǒng)執(zhí)行某策略所產(chǎn)生效果的優(yōu)劣可用數(shù)學(xué)指標(biāo)來衡量，它是各個階段狀態(tài)和決策的函數(shù)，稱為指數(shù)函數(shù)。（8） 邊值條件：在系統(tǒng)決策的狀態(tài)推移進(jìn)程中最初的條件稱為邊值條件。由系統(tǒng)的最后階段逐段向初始階段求最優(yōu)的過程稱為速推解法，由系統(tǒng)的最前階段逐段向終結(jié)階段求最優(yōu)的過程稱為順序推解法。如例1顯然有邊值條件：fn+1（sn+1）=0.根據(jù)上述確定的階段編號。狀態(tài)變量、決策變量、狀態(tài)轉(zhuǎn)移方程、邊值條件及指標(biāo)函數(shù)。確定例1的最短路線，計算步驟如下：根據(jù)最短路線特性，尋找最短路線的方法，將從最后一段開始，用后向前逐步地推的方法，求出各點到點E的最短路線，最后求得由點A到點E的最短線，所以，動態(tài)規(guī)劃的方向是從各點逐段向始點方向?qū)ふ易疃搪肪€的一種方法，見圖11—2.當(dāng)k=4時，有D1到終點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,至終點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。類似地?？捎嬎惝?dāng)k=2時，有f2（B1）=12, d2（B1）=C2.

f2(B2)=H, d2IB?)=C2,f2(B3)=9, d2(B3)=C3當(dāng)k=1時，出發(fā)點只有一個點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，于是獲得從始點A至終點E的最短距離為15,為便于找出最短路線，在按計算的順序推之，可求出最優(yōu)決策函數(shù)序列{dk},即由d1(A)=B],d2(B)=C2，d3(C2)=D2,d4(D2)=E組成一個最優(yōu)策略。那么最短路線為A—B]—C2—D2—E.§11.2中學(xué)生數(shù)學(xué)知識應(yīng)用競賽題舉例例2今年盛夏酷暑，能源緊張，某工廠從能源部門獲得5個單位某種能源，該工廠有3個部門需要這種能源，由于各部門所使用設(shè)備條件不同，生產(chǎn)的產(chǎn)品也不同，這樣導(dǎo)致是用能源所產(chǎn)生的收益情況也不同，所用的能源為整數(shù)單位，各部門具體產(chǎn)生的收益(萬元)如表11-1所示，為能有效地利用這種能源，工廠將如何分配能源給各部門使工廠受益最大？表11—1、'收益(萬元)部門0能源51234102455620134683034556解設(shè)3個部門分配到的能源分別為x1，x2,x3單位，相應(yīng)每個單位所產(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ù)。使用遞推方法來求解。按k=1,2,3為3階段，用fk(z)表示在第k階段所用能源為z單位時，獲得最大收益，即有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（萬元），即分配給3個部門的分別為：部門1，部門2都為2單位，而部門3為1單位，最大收益為10萬元。.§11.3復(fù)合系統(tǒng)工作可靠性問題若某種機(jī)器的工作系統(tǒng)有n個部件串聯(lián)組成，只要有一個部件失靈，整個系統(tǒng)就不能工作，為提高系統(tǒng)工作的可靠性，在每一個部件上均配有主要元件的備用件，并且設(shè)計了備用元件自動投入裝置。顯然，備用元件越多，整個系統(tǒng)正常工作的可靠性越大，但備用元件多了，整個系統(tǒng)的成本、重量、體積均相應(yīng)增大，工作精度也降低，因此，最優(yōu)化問題是在考慮上述限制條件下，應(yīng)如何選擇個部件的備用元件數(shù)，使整個系統(tǒng)的工作可靠性最大。設(shè)部件i（i=1，2,???..n）上裝有ui個備用件時，它正常工作的概率為pi（ui）o例3某個廠設(shè)計一種電子設(shè)備，，由3種元件D1,D2,D3組成，已知這3中元件的價格和可靠性如11—2所示。要求在設(shè)計中所使用元件的費用不超過105元，試問：應(yīng)如何設(shè)計室設(shè)備的可靠性達(dá)到最大（不考慮重量的限制）？表11—2元件單價（元）可靠性D1300.9D2150.8D3200.5解按元件種類劃分為3各階段，設(shè)狀態(tài)變量sk表示能容許用在Dk元件至D3元件的總費用；決策變量xk表示在Dk元件上的并聯(lián)個數(shù)；Pk表示一個Dk元件正常工作的概率，則為xk個Dk元件不正常工作的概率，另最優(yōu)值函數(shù)fk（sk）表示由狀態(tài)sk開始從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，故解此問題只要求出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個，D3元件用2個，其總費用為100元，可靠性為0.648。§11.4不確定性的采購問題本節(jié)敘述在生產(chǎn)和經(jīng)營管理中，經(jīng)常遇到在價格有波動時如何合理購買的問題，不確定性的采購問題的最優(yōu)化目標(biāo)為制定采購策略，對不同時期的浮動借個和概率，確定采購量以使總的采購費用(數(shù)學(xué)期望值)最小。例4某公司在近5周內(nèi)必須一次性采購原料一批，估計在未來5周內(nèi)價格有波動，期浮動價格和概率(可能性)如表11—3所示。試求各周中處在什么價位時應(yīng)購入，使采購價格最為合理？費用數(shù)學(xué)期望值最??？單價(千元/噸)概率180.4160.3140.3解這里價格是一個隨機(jī)變量，是按某種已知的概率分布取值的。用動態(tài)規(guī)劃方法處理，按采購期限將5周分為5個階段，將每周的價格看做該階段的狀態(tài)，設(shè)yk為狀態(tài)變量，表示第k周的實際價格；xk為決策變量。當(dāng)x=1，表示第k周決定采購；當(dāng)xk=0，表示第k周決定等待。用ykE表示第k周決定等待，而在以后采取最優(yōu)決策時采購價格的期望值；用fk(yk)表示第k周實際價格為yk時，從第k周至第5周采取最優(yōu)策略所得的最小期望值。因而可寫出逆序遞推關(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(采購)，當(dāng)/(y)=y;kkk廣〔0(等待)，當(dāng)^(y)=y.七 kkkE從最后一周開始；逐步向前遞推計算，具體計算過程如下：當(dāng)k=5是，因f5(y5)=y5,y5S5,故有f5(18)=18;f5(16)=16;f5(14)=14,即在第5周時，若所需的原料尚未買入，則無論市場價格如何，都必須采購，不能再等。當(dāng)k=5時，由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,