第六章(上課)運(yùn)籌學(xué)動(dòng)態(tài)規(guī)劃04修改

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

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

3、整個(gè)過程的最優(yōu)策略。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)過程中，由于需求是隨時(shí)間變化的，因此企業(yè)為了獲得全年的最需求是隨時(shí)間變化的，因此企業(yè)為了獲得全年的最佳生產(chǎn)效益，就要在整個(gè)生產(chǎn)過程中逐月或逐季度佳生產(chǎn)效益，就要在整個(gè)生產(chǎn)過程中逐月或逐季度地根據(jù)地根據(jù)庫存和需求庫存和需求決定決定生產(chǎn)計(jì)劃生產(chǎn)計(jì)劃。 2. 2. 機(jī)器負(fù)荷分配問題機(jī)器負(fù)荷分配問題：某種機(jī)器可以在高低兩：某種機(jī)器可以在高低兩種不同的

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

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

6、態(tài)轉(zhuǎn)移規(guī)律。態(tài)的演變過程，描述了狀態(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)移方程是確定過程由一個(gè)狀態(tài)到另過程由一個(gè)狀態(tài)到另一個(gè)狀態(tài)的演變過程。一個(gè)狀態(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 能用動(dòng)態(tài)規(guī)劃

7、方法求解的多階段決策過程是一類能用動(dòng)態(tài)規(guī)劃方法求解的多階段決策過程是一類特殊的多階段決策過程，即特殊的多階段決策過程，即具有無后效性具有無后效性的多階段的多階段決策過程。決策過程。19),(),(),(122231112kkkkusTsusTsusTs 動(dòng)態(tài)規(guī)劃中能動(dòng)態(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)給定后，則在這個(gè)階段以后過程的發(fā)展不受這個(gè)階段以如果某階段狀態(tài)給定后，則在這個(gè)階段以后過程的發(fā)展不受這個(gè)階段以前各段狀態(tài)的影響；前各段狀態(tài)的影響； 過程

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

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

10、的狀態(tài)階段的狀態(tài)s sk k開始到第開始到第n n階段的終止?fàn)顟B(tài)的過程，階段的終止?fàn)顟B(tài)的過程，采取最優(yōu)策略所得到的指標(biāo)函數(shù)值。記為采取最優(yōu)策略所得到的指標(biāo)函數(shù)值。記為l“opt” optimization, min , maxopt” optimization, min , max25),()(1,fsusVoptsnkknkkkuunk小結(jié)小結(jié): :方程方程 : :狀態(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)策略; ;動(dòng)態(tài)

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

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

13、2113121212321121333( ,)()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 12

14、719,11()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)解（標(biāo)號(hào)法）最優(yōu)解（標(biāo)號(hào)法）BACBDBCDEC212312312511214106104131211396581052052871220141819動(dòng)態(tài)規(guī)劃的基本方程K階段與階段與k+1階段遞推關(guān)系階段遞推關(guān)系邊界條件邊界條件動(dòng)態(tài)規(guī)劃基本思想： 2、在多階段決策過程中，動(dòng)

15、態(tài)規(guī)劃方法是既把當(dāng)、在多階段決策過程中，動(dòng)態(tài)規(guī)劃方法是既把當(dāng)前一段和未來一段分開，又把當(dāng)前效益和未來效前一段和未來一段分開，又把當(dāng)前效益和未來效益結(jié)合起來考慮的一種最優(yōu)化方法。因此，每段益結(jié)合起來考慮的一種最優(yōu)化方法。因此，每段決策的選取是從全局來考慮的，與該段的最優(yōu)選決策的選取是從全局來考慮的，與該段的最優(yōu)選擇答案一般是不同的。擇答案一般是不同的。 3、在求整個(gè)問題的最優(yōu)策略時(shí)，由于初始狀態(tài)是、在求整個(gè)問題的最優(yōu)策略時(shí)，由于初始狀態(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四、動(dòng)態(tài)規(guī)劃遞推求解方法建立動(dòng)態(tài)規(guī)劃模型步驟建立動(dòng)態(tài)規(guī)劃模型步驟靜態(tài)規(guī)劃與動(dòng)態(tài)規(guī)劃的關(guān)系靜態(tài)規(guī)劃與動(dòng)態(tài)規(guī)劃的關(guān)系求解方法求解方法逆推解法逆推解法順推解法順推解法381 1、劃分階段、劃分階段k k劃分階段是運(yùn)用動(dòng)態(tài)規(guī)劃求解多階段決策問題的第劃分階段是運(yùn)用動(dòng)態(tài)規(guī)劃求解多階段決策問題的第一步，在確定多階段特性后，按時(shí)間或空間先后順一步，在確定多階段特性后，按時(shí)間或空間先后順序，將過程劃分為若干相互聯(lián)系的階段。對(duì)于靜態(tài)序，將過程劃分為若干相互聯(lián)系的階段。對(duì)于靜態(tài)問題要人為地賦予問題要人為地賦予“時(shí)間時(shí)間”概念，以便劃分階段。概念，以便劃分階段。 2

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

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)移方程應(yīng)當(dāng)具有遞推關(guān)系。變量，狀態(tài)轉(zhuǎn)移方程應(yīng)當(dāng)具有遞推關(guān)系。 s sk+1k+1=T=Tk k(s(sk k,u,uk k) T) Tk k 函數(shù)關(guān)系函數(shù)關(guān)系405 5、確定階段指標(biāo)函數(shù)和最優(yōu)指標(biāo)函數(shù)，建立動(dòng)態(tài)規(guī)劃、確定階段指標(biāo)函數(shù)和最優(yōu)指標(biāo)函數(shù)，建立動(dòng)態(tài)規(guī)劃基本方程基本方程 階段指標(biāo)函數(shù)是指第階段指標(biāo)函數(shù)是指第k 階段的收益，最優(yōu)指標(biāo)函數(shù)是階段的收益，最優(yōu)指標(biāo)函數(shù)是指從第指從第k 階段狀態(tài)出

19、發(fā)到第階段狀態(tài)出發(fā)到第n 階段末所獲得收益的最優(yōu)階段末所獲得收益的最優(yōu)值，最后寫出動(dòng)態(tài)規(guī)劃基本方程。值，最后寫出動(dòng)態(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 以上五步是建立動(dòng)態(tài)規(guī)劃數(shù)學(xué)模型的一般步驟。以上五步是建立動(dòng)態(tài)規(guī)劃數(shù)學(xué)模型的一般步驟。由于動(dòng)態(tài)規(guī)劃模型與線性規(guī)劃模型不同，動(dòng)態(tài)規(guī)由于動(dòng)態(tài)規(guī)劃模型與線性規(guī)劃模型不同，動(dòng)態(tài)規(guī)劃模型沒有統(tǒng)一的模式，建模時(shí)必須根據(jù)具體問劃模型沒有統(tǒng)一的模式，建模時(shí)必須根據(jù)具體問題具體分析，只有通過不斷實(shí)踐總結(jié)，才能較好題具

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

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

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

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

24、點(diǎn)D 。 AB1B2C1C2C3D24333321114DC1C2C3顯然有顯然有 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(最短路線為最短路線為B

25、1C1 D)53 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 = m

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

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

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

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

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

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

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

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

34、=3時(shí)，時(shí)，數(shù)值計(jì)算如下表數(shù)值計(jì)算如下表6-56-5表表6-5 6-5 )(max)(333333xgsfsx 67k=2k=2時(shí)，時(shí)，計(jì)算結(jié)果見下表計(jì)算結(jié)果見下表7-67-6表表7-67-6 )()(max)(2232202222xsfxgsfsx68表表66k=1k=1時(shí)，時(shí)，k=1k=1時(shí)，只有時(shí)，只有s s1 1=4=4的情況。的情況。計(jì)算結(jié)果如表計(jì)算結(jié)果如表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個(gè)個(gè)地區(qū)設(shè)置地區(qū)設(shè)置2 2個(gè)銷售點(diǎn)，第

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

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

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

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

39、sxsfxsxsfsxsxsxsx72 x x3 3* *= =s s3 3k=2時(shí)，時(shí)， x2*=0 k=1時(shí)，時(shí)， x1*=022202222220322203322202222 )9822(max )(10932350)(710max 350)(710max )()(710max)(22222222sxsxsxxsxsxsxsfxsxsfsxsxsxsx1110111111021110221110115134 )15325134(max )(1093222)(710max 22)(710max )()(710max)(11111111sxsxsxxsxsxsxsfxsxsfsxsxsxs

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

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