第六章(上課) 運籌學動態(tài)規(guī)劃04修改

1、(Dynamic programming)1一、多階段決策問題一、多階段決策問題二、動態(tài)規(guī)劃的基本概念二、動態(tài)規(guī)劃的基本概念三、動態(tài)規(guī)劃的基本思想三、動態(tài)規(guī)劃的基本思想四、動態(tài)規(guī)劃遞推求解方法四、動態(tài)規(guī)劃遞推求解方法五、動態(tài)規(guī)劃的最優(yōu)性原理五、動態(tài)規(guī)劃的最優(yōu)性原理六、動態(tài)規(guī)劃問題應用舉例六、動態(tài)規(guī)劃問題應用舉例2概述1951年Bellman提出，1957動態(tài)規(guī)劃動態(tài)規(guī)劃動態(tài)規(guī)劃是解決多階段決策問題的一種數(shù)學方法。動態(tài)規(guī)劃思想動態(tài)規(guī)劃思想：把多階段決策問題變換為一系列互相聯(lián)系的單階段問題，然后逐個加以解決。即：把一個n 維決策問題變換為幾個一維最優(yōu)化問題，從而一個一個地去解決。需指出需指出：動態(tài)

2、規(guī)劃是求解某類問題的一種方法，是考察問題的一種途徑，而不是一種算法。必須對具體問題進行具體分析，運用動態(tài)規(guī)劃的原理和方法，建立相應的模型，然后再用動態(tài)規(guī)劃求解方法去求解。應用應用：最短路線、資源分配、生產(chǎn)調(diào)度問題3一、多階段決策問題多階段決策過程多階段決策過程 一類活動過程，可以按照時間進程分為狀態(tài)相互聯(lián)系而又相互區(qū)別的各個階段；每個階段都要進行決策,目的是使整個過程的決策達到最優(yōu)效果。多階段決策問題的特點多階段決策問題的特點（1）系統(tǒng)所處的狀態(tài)和時刻是進行決策的重要因素，即在系統(tǒng)發(fā)展的不同時刻（或階段）根據(jù)系統(tǒng)所處的狀態(tài)，不斷地做出決策；（2）目的是找到不同時刻的最優(yōu)決策以及整個過程的最優(yōu)策

3、略。412n狀態(tài)狀態(tài)1 1決策決策1 1狀態(tài)狀態(tài)2 2決策決策2 2狀態(tài)狀態(tài)3 3狀態(tài)狀態(tài)n n決策決策n n多階段決策問題的典型例子：多階段決策問題的典型例子： 1 . 1 . 生產(chǎn)決策問題生產(chǎn)決策問題：企業(yè)在生產(chǎn)過程中，由于：企業(yè)在生產(chǎn)過程中，由于需求是隨時間變化的，因此企業(yè)為了獲得全年的最需求是隨時間變化的，因此企業(yè)為了獲得全年的最佳生產(chǎn)效益，就要在整個生產(chǎn)過程中逐月或逐季度佳生產(chǎn)效益，就要在整個生產(chǎn)過程中逐月或逐季度地根據(jù)地根據(jù)庫存和需求庫存和需求決定決定生產(chǎn)計劃生產(chǎn)計劃。 2. 2. 機器負荷分配問題機器負荷分配問題：某種機器可以在高低兩：某種機器可以在高低兩種不同的負荷下進行生產(chǎn)。

4、在高負荷下進行生產(chǎn)時，種不同的負荷下進行生產(chǎn)。在高負荷下進行生產(chǎn)時，產(chǎn)品的年產(chǎn)量產(chǎn)品的年產(chǎn)量g和投入生產(chǎn)的機器數(shù)量和投入生產(chǎn)的機器數(shù)量u1的關系為的關系為g=g(u1)5 這時，機器的年完好率為這時，機器的年完好率為a，即如果年初完好機，即如果年初完好機器的數(shù)量為器的數(shù)量為u，到年終完好的機器就為，到年終完好的機器就為au, 0a1。 在低負荷下生產(chǎn)時，產(chǎn)品的年產(chǎn)量在低負荷下生產(chǎn)時，產(chǎn)品的年產(chǎn)量h和投入生產(chǎn)和投入生產(chǎn)的機器數(shù)量的機器數(shù)量u2的關系為的關系為 h=h(u2) 假定開始生產(chǎn)時完好的機器數(shù)量為假定開始生產(chǎn)時完好的機器數(shù)量為s s1 1。要求制。要求制定一個五年計劃，在定一個五年計劃，

5、在每年開始時，決定如何重新每年開始時，決定如何重新分配分配完好的完好的機器在兩種不同的負荷下生產(chǎn)的量機器在兩種不同的負荷下生產(chǎn)的量，使在五年內(nèi)產(chǎn)品的總產(chǎn)量達到最高。使在五年內(nèi)產(chǎn)品的總產(chǎn)量達到最高。 相應的機器年完好率相應的機器年完好率b b, 0 , 0 b b11k1）從第從第1 1階段開始到第階段開始到第n n階段結束稱為階段結束稱為全策略全策略 P P1 1, ,n n所有策略當中有最優(yōu)值的策略稱為所有策略當中有最優(yōu)值的策略稱為最優(yōu)策略最優(yōu)策略。17（5）狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程：確定過程由一個狀態(tài)到另一個狀狀態(tài)轉(zhuǎn)移方程：確定過程由一個狀態(tài)到另一個狀態(tài)的演變過程，描述了狀態(tài)轉(zhuǎn)移規(guī)律。態(tài)的

6、演變過程，描述了狀態(tài)轉(zhuǎn)移規(guī)律。18Tk為狀態(tài)轉(zhuǎn)移函數(shù)為狀態(tài)轉(zhuǎn)移函數(shù)),(),(),(221112211231112kkkkusususTsususTsusTs 圖示如下：圖示如下：狀態(tài)轉(zhuǎn)移方程是確定狀態(tài)轉(zhuǎn)移方程是確定過程由一個狀態(tài)到另過程由一個狀態(tài)到另一個狀態(tài)的演變過程。一個狀態(tài)的演變過程。如果第如果第k階段狀態(tài)變量階段狀態(tài)變量sk的值、該階段的決策的值、該階段的決策變量一經(jīng)確定，第變量一經(jīng)確定，第k+1階段狀態(tài)變量階段狀態(tài)變量sk+1的值的值也就確定。也就確定。其狀態(tài)轉(zhuǎn)移方程如下（一般形式）其狀態(tài)轉(zhuǎn)移方程如下（一般形式）12ks1u1s2u2s3skuksk+1 能用動態(tài)規(guī)劃方法求解的多階段

7、決策過程是一類能用動態(tài)規(guī)劃方法求解的多階段決策過程是一類特殊的多階段決策過程，即特殊的多階段決策過程，即具有無后效性具有無后效性的多階段的多階段決策過程。決策過程。19),(),(),(122231112kkkkusTsusTsusTs 動態(tài)規(guī)劃中能動態(tài)規(guī)劃中能處理的狀態(tài)轉(zhuǎn)移處理的狀態(tài)轉(zhuǎn)移方程的形式方程的形式。狀態(tài)具有無后效性的多階段決策過程的狀態(tài)轉(zhuǎn)移方程如下：狀態(tài)具有無后效性的多階段決策過程的狀態(tài)轉(zhuǎn)移方程如下： 如果某階段狀態(tài)給定后，則在這個階段以后過程的發(fā)展不受這個階段以如果某階段狀態(tài)給定后，則在這個階段以后過程的發(fā)展不受這個階段以前各段狀態(tài)的影響；前各段狀態(tài)的影響； 過程的過去歷史只能通

8、過當前的狀態(tài)去影響它未來的發(fā)展；過程的過去歷史只能通過當前的狀態(tài)去影響它未來的發(fā)展； 構造動態(tài)規(guī)劃模型時，要充分注意是否滿足無后效性的要求；構造動態(tài)規(guī)劃模型時，要充分注意是否滿足無后效性的要求； 如果狀態(tài)變量不能滿足無后效性的要求，應適當?shù)馗淖儬顟B(tài)的定義或規(guī)如果狀態(tài)變量不能滿足無后效性的要求，應適當?shù)馗淖儬顟B(tài)的定義或規(guī)定方法。定方法。20（6）指標函數(shù)和最優(yōu)值函數(shù)用來衡量所實現(xiàn)過程優(yōu)劣的一種數(shù)量指標，為用來衡量所實現(xiàn)過程優(yōu)劣的一種數(shù)量指標，為指標指標函數(shù)函數(shù)。v vk k(s(sk k,u,uk k) ) 表示第表示第k k階段位于階段位于s sk k狀態(tài)、決策為狀態(tài)、決策為u uk k的指的

9、指標值。標值。 21l在不同的問題中，指標函數(shù)的含義是不同的，它在不同的問題中，指標函數(shù)的含義是不同的，它可能是距離、利潤、成本、產(chǎn)量或資源消耗等。可能是距離、利潤、成本、產(chǎn)量或資源消耗等。l最短路問題中最短路問題中v vk,nk,n表示第表示第k k階段由點階段由點s sk k到終點到終點G G的最的最短距離短距離l動態(tài)規(guī)劃的指標函數(shù)應具有可分離性，并滿足遞動態(tài)規(guī)劃的指標函數(shù)應具有可分離性，并滿足遞推關系式，推關系式， 函數(shù)記為：函數(shù)記為：指標函數(shù)的形式： l和和 l積積最優(yōu)值函數(shù)l指標函數(shù)的最優(yōu)值，稱為指標函數(shù)的最優(yōu)值，稱為最優(yōu)值函數(shù)最優(yōu)值函數(shù)。表示從第。表示從第k k階段的狀態(tài)階段的狀態(tài)

10、s sk k開始到第開始到第n n階段的終止狀態(tài)的過程，階段的終止狀態(tài)的過程，采取最優(yōu)策略所得到的指標函數(shù)值。記為采取最優(yōu)策略所得到的指標函數(shù)值。記為l“opt” optimization, min , maxopt” optimization, min , max25),()(1,fsusVoptsnkknkkkuunk小結小結: :方程方程 : :狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程),(1kkkkusTs概念概念 : : 階段變量階段變量k k狀態(tài)變量狀態(tài)變量s sk k決策變量決策變量u uk k允許決策集合允許決策集合D Dk k(s(sk k) )、最優(yōu)策略、最優(yōu)策略; ;動態(tài)規(guī)劃本質(zhì)上是多階

11、段決策過程動態(tài)規(guī)劃本質(zhì)上是多階段決策過程; ;要求：無后效性要求：無后效性),()(1,susVoptsfnkknkkkuunk),(,111,1nkknkkkksusVus指標指標: : ),(111,nkkkknknksususVV 效益效益),(111,nkkkknksususV可遞推可遞推27,*2*1nuuu解多階段決策過程問題，求出解多階段決策過程問題，求出 最優(yōu)策略最優(yōu)策略，即最優(yōu)，即最優(yōu)決策序列決策序列 susvoptsfnkknkkkuunk1, f1(s1) 最優(yōu)目標函數(shù)值最優(yōu)目標函數(shù)值),(*1*1*,1*,1nnnnususVV從從 k 到終點最優(yōu)策略到終點最優(yōu)策略子策

12、略的最優(yōu)目標函數(shù)值子策略的最優(yōu)目標函數(shù)值285()0fEk=4411()5fDDE422()2fDDE三. 動態(tài)規(guī)劃的基本思想BACBDBCDEC21231231251121410610413121139658105231141311131242(,)()35()minmin8,(,)()92d C DfDf CCDd C DfD413222426()65()minmin7,5()52fDf CCDfD413332428()85()minmin12,10()102fDf CCDfDk=3BACBDBCDEC21231231251121410610413121139658105221131212

13、12321121333( ,)()12 8( )min( ,)()min 14 720,( ,)()10 12d B Cf Cf Bd B Cf CBCd B Cf C313233()8()7()12f Cf Cf Ck=2BACBDBCDEC212312312511214106104131211396581052BACBDBCDEC21231231251121410610413121139658105231223221336()68()min 10()min 10714,4()4 12f CfBf CBCf C312332323313()138()min 12()min 12719,11()

14、11 12f CfBf CBCf C313233()8()7()12f Cf Cf C211222232()220( )min 5()min 5 1419,1()1 19fBf AfBABfB212223()20()14()19fBfBfB211ABCDEk=1最優(yōu)路徑為最優(yōu)路徑為最短距離為最短距離為19最優(yōu)解（標號法）最優(yōu)解（標號法）BACBDBCDEC212312312511214106104131211396581052052871220141819動態(tài)規(guī)劃的基本方程K階段與階段與k+1階段遞推關系階段遞推關系邊界條件邊界條件動態(tài)規(guī)劃基本思想： 2、在多階段決策過程中，動態(tài)規(guī)劃方法是既把

15、當、在多階段決策過程中，動態(tài)規(guī)劃方法是既把當前一段和未來一段分開，又把當前效益和未來效前一段和未來一段分開，又把當前效益和未來效益結合起來考慮的一種最優(yōu)化方法。因此，每段益結合起來考慮的一種最優(yōu)化方法。因此，每段決策的選取是從全局來考慮的，與該段的最優(yōu)選決策的選取是從全局來考慮的，與該段的最優(yōu)選擇答案一般是不同的。擇答案一般是不同的。 3、在求整個問題的最優(yōu)策略時，由于初始狀態(tài)是、在求整個問題的最優(yōu)策略時，由于初始狀態(tài)是已知的，而每段的決策都是該段狀態(tài)的函數(shù)，故已知的，而每段的決策都是該段狀態(tài)的函數(shù)，故最優(yōu)策略所經(jīng)過的各段狀態(tài)便可逐段變換得到，最優(yōu)策略所經(jīng)過的各段狀態(tài)便可逐段變換得到，從而確定

16、了最優(yōu)路線。從而確定了最優(yōu)路線。37四、動態(tài)規(guī)劃遞推求解方法建立動態(tài)規(guī)劃模型步驟建立動態(tài)規(guī)劃模型步驟靜態(tài)規(guī)劃與動態(tài)規(guī)劃的關系靜態(tài)規(guī)劃與動態(tài)規(guī)劃的關系求解方法求解方法逆推解法逆推解法順推解法順推解法381 1、劃分階段、劃分階段k k劃分階段是運用動態(tài)規(guī)劃求解多階段決策問題的第劃分階段是運用動態(tài)規(guī)劃求解多階段決策問題的第一步，在確定多階段特性后，按時間或空間先后順一步，在確定多階段特性后，按時間或空間先后順序，將過程劃分為若干相互聯(lián)系的階段。對于靜態(tài)序，將過程劃分為若干相互聯(lián)系的階段。對于靜態(tài)問題要人為地賦予問題要人為地賦予“時間時間”概念，以便劃分階段。概念，以便劃分階段。 2 2、正確選擇狀

17、態(tài)變量、正確選擇狀態(tài)變量s sk k選擇變量既要能確切描述過程演變又要滿足選擇變量既要能確切描述過程演變又要滿足無后效無后效性性，而且各階段狀態(tài)變量的取值能夠確定。一般地，而且各階段狀態(tài)變量的取值能夠確定。一般地，狀態(tài)變量的選擇是從過程演變的特點中尋找。狀態(tài)變量的選擇是從過程演變的特點中尋找。 建立動態(tài)規(guī)劃模型的步驟 393 3、確定決策變量、確定決策變量u uk k(s(sk k) )及允許決策集合及允許決策集合D Dk k(s(sk k) )通常選擇所求解問題的關鍵變量作為決策變量，同通常選擇所求解問題的關鍵變量作為決策變量，同時要給出決策變量的取值范圍，即確定允許決策集時要給出決策變量的

18、取值范圍，即確定允許決策集合。合。 4 4、確定狀態(tài)轉(zhuǎn)移方程、確定狀態(tài)轉(zhuǎn)移方程根據(jù)根據(jù)k k階段狀態(tài)變量和決策變量，寫出階段狀態(tài)變量和決策變量，寫出k+1k+1階段狀態(tài)階段狀態(tài)變量，狀態(tài)轉(zhuǎn)移方程應當具有遞推關系。變量，狀態(tài)轉(zhuǎn)移方程應當具有遞推關系。 s sk+1k+1=T=Tk k(s(sk k,u,uk k) T) Tk k 函數(shù)關系函數(shù)關系405 5、確定階段指標函數(shù)和最優(yōu)指標函數(shù)，建立動態(tài)規(guī)劃、確定階段指標函數(shù)和最優(yōu)指標函數(shù)，建立動態(tài)規(guī)劃基本方程基本方程 階段指標函數(shù)是指第階段指標函數(shù)是指第k 階段的收益，最優(yōu)指標函數(shù)是階段的收益，最優(yōu)指標函數(shù)是指從第指從第k 階段狀態(tài)出發(fā)到第階段狀態(tài)出

19、發(fā)到第n 階段末所獲得收益的最優(yōu)階段末所獲得收益的最優(yōu)值，最后寫出動態(tài)規(guī)劃基本方程。值，最后寫出動態(tài)規(guī)劃基本方程。f k (sk ) = Opt Vk (sk ,uk ) + f k+1 (s k+1) fn+1 (s n+1 ) = 0 Opt 最優(yōu)化（最優(yōu)化（max,min）41 以上五步是建立動態(tài)規(guī)劃數(shù)學模型的一般步驟。以上五步是建立動態(tài)規(guī)劃數(shù)學模型的一般步驟。由于動態(tài)規(guī)劃模型與線性規(guī)劃模型不同，動態(tài)規(guī)由于動態(tài)規(guī)劃模型與線性規(guī)劃模型不同，動態(tài)規(guī)劃模型沒有統(tǒng)一的模式，建模時必須根據(jù)具體問劃模型沒有統(tǒng)一的模式，建模時必須根據(jù)具體問題具體分析，只有通過不斷實踐總結，才能較好題具體分析，只有通過

20、不斷實踐總結，才能較好掌握建模方法與技巧。掌握建模方法與技巧。 f1(s1) 是整個問題的最優(yōu)策略，最優(yōu)值。是整個問題的最優(yōu)策略，最優(yōu)值。f k(sk) 表示從第表示從第k階段（狀態(tài)階段（狀態(tài)sk）到終點的）到終點的最優(yōu)最優(yōu)指標值指標值。（距離、利潤、成本等。（距離、利潤、成本等） 42靜態(tài)規(guī)劃與動態(tài)規(guī)劃的關系43靜態(tài)規(guī)劃靜態(tài)規(guī)劃（與時間無關）（與時間無關）動態(tài)規(guī)劃動態(tài)規(guī)劃時間時間逆推解法與順推解法應用條件：應用條件：當初始狀態(tài)給定時，用逆推比較方便當初始狀態(tài)給定時，用逆推比較方便當終止狀態(tài)給定時，用順推比較方便當終止狀態(tài)給定時，用順推比較方便44逆序解法基本方程45思考：順序解法基本方程思考

21、：順序解法基本方程順序解法基本方程重新定義：重新定義：遞推關系：遞推關系：邊界條件：邊界條件：五、動態(tài)規(guī)劃最優(yōu)性（最優(yōu)化）原理和最優(yōu)性定理47 最優(yōu)性原理：作為整個過程的最優(yōu)策略具有這樣的性最優(yōu)性原理：作為整個過程的最優(yōu)策略具有這樣的性質(zhì)：無論過去的狀態(tài)和決策如何，相對于前面的決策質(zhì)：無論過去的狀態(tài)和決策如何，相對于前面的決策所形成的狀態(tài)而言，余下的決策序列必然構成最優(yōu)子所形成的狀態(tài)而言，余下的決策序列必然構成最優(yōu)子策略。策略?！币簿褪钦f，一個最優(yōu)策略的子策略也是最優(yōu)也就是說，一個最優(yōu)策略的子策略也是最優(yōu)的。的。 CABDEFGHJI3682371572643當前當前過去過去未來未來返回返回4

22、8最優(yōu)性定理若一個問題有最優(yōu)策略，則該問題的最優(yōu)值若一個問題有最優(yōu)策略，則該問題的最優(yōu)值函數(shù)可用動態(tài)規(guī)劃的基本方程來表示函數(shù)可用動態(tài)規(guī)劃的基本方程來表示六、動態(tài)規(guī)劃優(yōu)缺點 （1）能夠得到全局最優(yōu)解）能夠得到全局最優(yōu)解 （2）可以得到一族最優(yōu)解）可以得到一族最優(yōu)解 （3）能夠利用經(jīng)驗提高求解效率）能夠利用經(jīng)驗提高求解效率49（1）沒有統(tǒng)一的）沒有統(tǒng)一的標準模型標準模型，也沒有，也沒有構造模型的通構造模型的通用方法用方法，甚至沒有判斷一個問題能否構造動態(tài)規(guī)，甚至沒有判斷一個問題能否構造動態(tài)規(guī)劃模型的具體準則劃模型的具體準則（2）求解時存在）求解時存在維數(shù)災難維數(shù)災難缺點：缺點：優(yōu)點：優(yōu)點：七、動態(tài)

23、規(guī)劃問題應用舉例最短路徑問題資源分配問題生產(chǎn)計劃問題50例一、從例一、從A 地到地到D 地要鋪設一條煤氣管道地要鋪設一條煤氣管道,其中需經(jīng)過其中需經(jīng)過兩級中間站，兩點之間的連線上的數(shù)字表示距離，如兩級中間站，兩點之間的連線上的數(shù)字表示距離，如圖所示。問應該選擇什么路線，使總距離最短？圖所示。問應該選擇什么路線，使總距離最短？ AB1B2C1C2C3D24333321114（一）最短路徑問題（一）最短路徑問題51 解：整個計算過程分三個階段，從最后一個階段開始。解：整個計算過程分三個階段，從最后一個階段開始。 第三階段（第三階段（C D）：）： C 有三條路線到終點有三條路線到終點D 。 AB1

24、B2C1C2C3D24333321114DC1C2C3顯然有顯然有 f3 (C1 ) = 1 ； f3(C2 ) = 3 ； f3 (C3 ) = 4 52基本方程逆序解法基本方程逆序解法 d( B1,C1 ) + f3 (C1 ) 3+1 f2 ( B1 ) = min d( B1,C2 ) + f3 (C2 ) = min 3+3 d( B1,C3 ) + f3 (C3 ) 1+4 4 = min 6 = 4 5第二階段（第二階段（B C）：）： B 到到C 有六條路線。有六條路線。AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路線為最短路線為B1C1 D)53

25、 d( B2,C1 ) + f3 (C1 ) 2+1 f2 ( B2 ) = min d( B2,C2 ) + f3 (C2 ) = min 3+3 d( B2,C3 ) + f3 (C3 ) 1+4 3 = min 6 = 3 5AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路線為最短路線為B2C1 D)54第一階段（第一階段（ A B ）：）： A 到到B 有二條路線。有二條路線。 f1(A)1 = d(A, B1 ) f2 ( B1 ) 246 f1 (A)2 = d(A, B2 ) f2 ( B2 ) 437 f1 (A) = min = min6,7=6d

26、(A, B1 ) f2 ( B1 )d(A, B2 ) f2 ( B2 )(最短路線為最短路線為AB1C1 D)AB1B2C1C2C3D24333321114DC1C2C3B1B2A55AB1B2C1C2C3D24333321114DC1C2C3B1B2A最短路線為最短路線為 AB1C1 D 路長為路長為 656順序解法57AB1B2C1C2C3D24333321114Dijkstra（狄克斯拉）標號法從起點vs開始，逐步給每個結點vj標號dj，vi，其中dj為起點vs到vj的最短距離，vi為該最短路線上的前一節(jié)點。58AB1B2C1C2C3D24333321114例題：59ABDFHCEG4

27、566536813576求求A到到H的最短路徑的最短路徑?資源分配問題就是將一定數(shù)量的一種或若干種資資源分配問題就是將一定數(shù)量的一種或若干種資源（原材料、資金、設備等）合理分配給若干使用者，源（原材料、資金、設備等）合理分配給若干使用者，使得資源分配后總結果最優(yōu)。一種資源的分配問題稱使得資源分配后總結果最優(yōu)。一種資源的分配問題稱為一維資源分配問題，兩種資源的分配問題稱為二維為一維資源分配問題，兩種資源的分配問題稱為二維資源分配問題。資源分配問題。 （二）資源分配問題（二）資源分配問題60假設有一種資源，數(shù)量為假設有一種資源，數(shù)量為a a，將其分配給，將其分配給n n個使用者，個使用者，分配給第

28、分配給第i個使用者數(shù)量個使用者數(shù)量xi時，相應的收益為時，相應的收益為gi（xi），），問如何分配使得總收入最大？這就是一維資源分配問題，問如何分配使得總收入最大？這就是一維資源分配問題，該問題的數(shù)學模型為：該問題的數(shù)學模型為：這是一個靜態(tài)規(guī)劃問題，應用動態(tài)規(guī)劃方法求解時這是一個靜態(tài)規(guī)劃問題，應用動態(tài)規(guī)劃方法求解時人為賦予時間概念，將其看作是一個多階段決策問題。人為賦予時間概念，將其看作是一個多階段決策問題。 nixaxxxxgxgxgzinnn, 2 , 1 0 )()()( max21221161按變量個數(shù)劃分階段，按變量個數(shù)劃分階段，k=1，2，n；設決策變量設決策變量uk=xk，表示分

29、配給第表示分配給第k個使用者的資源數(shù)量；個使用者的資源數(shù)量；設狀態(tài)變量為設狀態(tài)變量為sk，表示分配給第表示分配給第k個至第個至第n個使用者的總個使用者的總資源數(shù)量；資源數(shù)量；狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程：sk+1=skxk，其中其中s1=a；允許決策集合：允許決策集合：Dk（sk）=xk| |0 xksk階段指標函數(shù)：階段指標函數(shù)：vk（sk，uk）=gk（xk）表示分配給第表示分配給第k個使用者數(shù)量個使用者數(shù)量xk時的收益；時的收益；62最優(yōu)指標函數(shù)最優(yōu)指標函數(shù)fk（sk）表示以數(shù)量表示以數(shù)量sk的資源分配給第的資源分配給第k個個至第至第n個使用者所得到的最大收益，則動態(tài)規(guī)劃基本方個使用者所得

30、到的最大收益，則動態(tài)規(guī)劃基本方程為：程為：由后向前逐段遞推，由后向前逐段遞推，f1（a）即為所求問題的最大收益即為所求問題的最大收益。0)(1 , )()(max)(11110nnkkkksxkksfnksfxgsfkk63按變量個數(shù)劃分階段，按變量個數(shù)劃分階段，k=1，2，n；設決策變量設決策變量uk=xk，表示分配給第表示分配給第k個使用者的資源數(shù)量；個使用者的資源數(shù)量；設狀態(tài)變量為設狀態(tài)變量為sk，表示分配給第表示分配給第k個至第個至第n個使用者的總個使用者的總資源數(shù)量；資源數(shù)量；狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程：sk+1=skxk，其中其中s1=a；允許決策集合：允許決策集合：Dk（sk）=

31、xk| |0 xksk階段指標函數(shù)：階段指標函數(shù)：vk（sk，uk）=gk（xk）表示分配給第表示分配給第k個使用者數(shù)量個使用者數(shù)量xk時的收益；時的收益；最優(yōu)指標函數(shù)最優(yōu)指標函數(shù)fk（sk）表示以數(shù)量表示以數(shù)量sk的資源分配給第的資源分配給第k個個至第至第n個使用者所得到的最大收益，則動態(tài)規(guī)劃基本方個使用者所得到的最大收益，則動態(tài)規(guī)劃基本方程為：程為：由后向前逐段遞推，由后向前逐段遞推，f1（a）即為所求問題的最大收益即為所求問題的最大收益。0)(1 , )()(max)(11110nnkkkksxkksfnksfxgsfkk64例二、某公司打算在例二、某公司打算在3 3個不同的地區(qū)設置個不

32、同的地區(qū)設置4 4個銷售點，根據(jù)個銷售點，根據(jù)市場部門估計，在不同地區(qū)設置不同數(shù)量的銷售點每月可市場部門估計，在不同地區(qū)設置不同數(shù)量的銷售點每月可得到的利潤如表得到的利潤如表6-46-4所示。試問在各地區(qū)如何設置銷售點所示。試問在各地區(qū)如何設置銷售點可使每月總利潤最大?？墒姑吭驴偫麧欁畲?。表表6-46-4 65解解 如前所述，建立動態(tài)規(guī)劃數(shù)學模型：如前所述，建立動態(tài)規(guī)劃數(shù)學模型：將問題分為將問題分為3 3個階段，個階段，k=1，2，3；決策變量決策變量xk表示分配給第表示分配給第k個地區(qū)的銷售點數(shù)；個地區(qū)的銷售點數(shù)；狀態(tài)變量為狀態(tài)變量為sk表示分配給第表示分配給第k個至第個至第3個地區(qū)的銷售點

33、總個地區(qū)的銷售點總數(shù)；數(shù)；狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程：sk+1=skxk，其中其中s1=4；允許決策集合：允許決策集合：Dk（sk）=xk| |0 xksk階段指標函數(shù)：階段指標函數(shù)：gk（xk）表示表示xk個銷售點分配給第個銷售點分配給第k個地區(qū)所獲得的利潤；個地區(qū)所獲得的利潤；最優(yōu)指標函數(shù)最優(yōu)指標函數(shù)fk（sk）表示將數(shù)量為表示將數(shù)量為sk的銷售點分的銷售點分配給第配給第k個至第個至第3個地區(qū)所得到的最大利潤，動態(tài)規(guī)劃個地區(qū)所得到的最大利潤，動態(tài)規(guī)劃基本方程為：基本方程為： 0)(1 , 2 , 3 )()(max)(4410sfkxsfxgsfkkkkksxkkkk66k=3時，時，數(shù)值

34、計算如下表數(shù)值計算如下表6-56-5表表6-5 6-5 )(max)(333333xgsfsx 67k=2k=2時，時，計算結果見下表計算結果見下表7-67-6表表7-67-6 )()(max)(2232202222xsfxgsfsx68表表66k=1k=1時，時，k=1k=1時，只有時，只有s s1 1=4=4的情況。的情況。計算結果如表計算結果如表7-77-7所示。所示。所以所以最優(yōu)解最優(yōu)解為：為：x x1 1* *=2=2，x x2 2* *=1=1，x x3 3* *=1=1，f f1 1(4)=47(4)=47，即在第即在第1 1個個地區(qū)設置地區(qū)設置2 2個銷售點，第個銷售點，第2

35、2個個地區(qū)設置地區(qū)設置1 1個銷售點，第個銷售點，第3 3個個地區(qū)設置地區(qū)設置1 1個銷售點，每月可獲利潤個銷售點，每月可獲利潤4747。表表6-76-7 )()(max)(1121101111xsfxgsfsx)4()(max)(121140111xfxgsfx69例三、機器負荷問題例三、機器負荷問題某工廠有某工廠有100100臺機器，擬分四期使用，每一期都可在高、低臺機器，擬分四期使用，每一期都可在高、低兩種不同負荷下進行生產(chǎn)。若把兩種不同負荷下進行生產(chǎn)。若把x x臺機器投入高負荷下進行生產(chǎn)，臺機器投入高負荷下進行生產(chǎn)，則在本期結束時將有則在本期結束時將有1/3x1/3x臺機器損壞報廢；余

36、下的機器全部投入臺機器損壞報廢；余下的機器全部投入低負荷下進行生產(chǎn)，則在期末有低負荷下進行生產(chǎn)，則在期末有1/101/10的機器報廢。如果高負荷下的機器報廢。如果高負荷下生產(chǎn)時每臺機器可獲利潤為生產(chǎn)時每臺機器可獲利潤為1010，低負荷下生產(chǎn)時每臺機器可獲利，低負荷下生產(chǎn)時每臺機器可獲利潤為潤為7 7，問怎樣分配機器使四期的總利潤最大？，問怎樣分配機器使四期的總利潤最大？解解 將問題按周期分為將問題按周期分為4 4個階段，個階段，k=1，2，3，4；狀態(tài)變量狀態(tài)變量sk表示第表示第k階段初完好的機器數(shù)，階段初完好的機器數(shù)，s1=100，0sk100；決策變量決策變量xk表示第表示第k階段投入高負

37、荷下生產(chǎn)的機器數(shù)，階段投入高負荷下生產(chǎn)的機器數(shù)，則則skxk表示第表示第k階段投入低負荷下生產(chǎn)的機器數(shù)；階段投入低負荷下生產(chǎn)的機器數(shù)；允許決策集合：允許決策集合：Dk（sk）=xk| |0 xksk狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程：sk+1=Tk（sk，xk），），即第即第k+1階段初擁有的完好機階段初擁有的完好機器數(shù)器數(shù)sk+1為：為： )(109321kkkkxsxs70階段指標函數(shù)：階段指標函數(shù)：vk（sk，xk）=10 xk+7（skxk）表示第表示第k階階段所獲得的利潤；段所獲得的利潤；最優(yōu)指標函數(shù)最優(yōu)指標函數(shù)f fk k（s sk k）表示從第表示從第k k階段初完好機器數(shù)為階段初完好機

38、器數(shù)為s sk k至至第第四階段的最大利潤，動態(tài)規(guī)劃基本方程為：四階段的最大利潤，動態(tài)規(guī)劃基本方程為：0)(1 , 2 , 3 , 4 )(),(max)(55110sfksfxsvsfkkkkksxkkkk444044404410)73 (max)( 710max)(4444ssxxsxsfsxsx71x x4 4* *= =s s4 4 k=4 k=4時，時， k=3k=3時，時，333033333304333044333033350 )1632(max )(1093210)(710max 10)(710max )()(710max)(33333333ssxxsxxsxsxsxsfxsxs

39、fsxsxsxsx72 x x3 3* *= =s s3 3k=2時，時， x2*=0 k=1時，時， x1*=022202222220322203322202222 )9822(max )(10932350)(710max 350)(710max )()(710max)(22222222sxsxsxxsxsxsxsfxsxsfsxsxsxsx1110111111021110221110115134 )15325134(max )(1093222)(710max 22)(710max )()(710max)(11111111sxsxsxxsxsxsxsfxsxsfsxsxsxsx73因為因為s

40、1=100，所以，所以f1（100）=2680，逆向追蹤得：，逆向追蹤得：s1=100，x1*=0 x2*=0 x3*=s3=81 x4*=s4=54即，第即，第1，2期把全部完好機器投入低負荷下生產(chǎn)，第期把全部完好機器投入低負荷下生產(chǎn)，第3，4期把全部完好機器投入高負荷下生產(chǎn)所得利潤最大。期把全部完好機器投入高負荷下生產(chǎn)所得利潤最大。 90)(10932*11*12xsxs81)(10932*22*23xsxs54)(10932*33*34xsxs74（三）生產(chǎn)計劃問題（三）生產(chǎn)計劃問題 在企業(yè)生產(chǎn)經(jīng)營活動中，經(jīng)常會遇到如何合理在企業(yè)生產(chǎn)經(jīng)營活動中，經(jīng)常會遇到如何合理安排生產(chǎn)、庫存及銷售計劃

41、，使總效益最高的問題，安排生產(chǎn)、庫存及銷售計劃，使總效益最高的問題，這一類問題統(tǒng)稱為生產(chǎn)計劃問題。這一類問題統(tǒng)稱為生產(chǎn)計劃問題。 75例例4、（庫存（庫存銷售問題）銷售問題） 設某公司計劃在設某公司計劃在1至至4月份從事某種商品經(jīng)營。已知倉月份從事某種商品經(jīng)營。已知倉庫最多可存儲庫最多可存儲600件這種商品，已知件這種商品，已知1月初存貨月初存貨200件，根件，根據(jù)預測知據(jù)預測知1至至4月份各月的單位購貨成本及銷售價格如表月份各月的單位購貨成本及銷售價格如表6-13所示，每月只能銷售本月初的庫存，當月進貨供以后各所示，每月只能銷售本月初的庫存，當月進貨供以后各月銷售，問如何安排進貨量和銷售量，使該公司四個月獲月銷售，問如何安排進貨量和銷售量，使該公司四個月獲得利潤最大（假設四月底庫存為零）。得利潤最大（假設四月底庫存為零）。表表6-13 76解 按月份劃分階段