清華大學(xué)出版《運籌學(xué)》第三版完整版課件第七章

1、1Yunchouxue 第七章 動態(tài)規(guī)劃2以最短路問題為例，來說明動態(tài)規(guī)劃的概念以最短路問題為例，來說明動態(tài)規(guī)劃的概念B1B2AC1C2C3C4D1D2D3E1E2F452358775845348435621343ABCDEF3一、動態(tài)規(guī)劃基本概念：n1、階段階段:n將所要研究的問題將所要研究的問題,按時間或空間特征分成按時間或空間特征分成若干個互相聯(lián)系的階段若干個互相聯(lián)系的階段.簡稱簡稱“階段階段”。n階段就是作出決策的若干輪次。描述階段階段就是作出決策的若干輪次。描述階段的變量叫階段變量，常用的變量叫階段變量，常用k表示階段變量表示階段變量.上例中上例中k1，2，3，4，5。42、狀態(tài)及性

2、質(zhì)n各階段開始時的客觀條件叫做狀態(tài)各階段開始時的客觀條件叫做狀態(tài).描述各階段描述各階段狀態(tài)的變量叫做狀態(tài)變量狀態(tài)的變量叫做狀態(tài)變量,常用常用sk表示第階段表示第階段的狀態(tài)變量的狀態(tài)變量, sk的取值集合稱為狀態(tài)集合的取值集合稱為狀態(tài)集合,用用Sk表示。表示。n階段的出發(fā)位置，即階段的起點階段的出發(fā)位置，即階段的起點。n上例中，第二階段有兩個狀態(tài)，即上例中，第二階段有兩個狀態(tài)，即Sk= B1,B2n動態(tài)規(guī)劃中狀態(tài)具有以下性質(zhì)動態(tài)規(guī)劃中狀態(tài)具有以下性質(zhì):某階段狀態(tài)一旦某階段狀態(tài)一旦確定確定,以后過程的狀態(tài)變化不受這個狀態(tài)以前的以后過程的狀態(tài)變化不受這個狀態(tài)以前的影響影響,也就是說某狀態(tài)以后的過程和

3、以前無關(guān)也就是說某狀態(tài)以后的過程和以前無關(guān),只只與當(dāng)前狀態(tài)有關(guān)與當(dāng)前狀態(tài)有關(guān),我們稱這種特性為我們稱這種特性為“無后效無后效性性.”(即馬爾科夫性。）即馬爾科夫性。）P19453、決策和策略n指從一個階段某狀態(tài)演變到下一階段某狀指從一個階段某狀態(tài)演變到下一階段某狀態(tài)的選擇（決定）稱為決策。態(tài)的選擇（決定）稱為決策。n表示決策的變量叫做表示決策的變量叫做決策變量決策變量,常用常用uk(sk)表示表示.第第k階段當(dāng)狀態(tài)為階段當(dāng)狀態(tài)為sk時的決策變量時的決策變量.n在實際問題中決策變量的取值往往限制在在實際問題中決策變量的取值往往限制在一定的范圍內(nèi)一定的范圍內(nèi),我們稱此范圍為允許決策集我們稱此范圍為

4、允許決策集,常用常用Dk(sk)表示第表示第k階段從狀態(tài)階段從狀態(tài)sk出發(fā)的出發(fā)的允許決策集允許決策集,因此有因此有uk(sk) Dk(sk).n在例在例1中中D2(B1)=C1,C2,C3 .6策略策略n在例在例1中中 D2(B1)=C1,C2,C3.表示什么？表示什么？n表示從第二階段的狀態(tài)表示從第二階段的狀態(tài)B1出發(fā)，可選擇下一階出發(fā)，可選擇下一階段的段的C1 ,C2,C3。即允許決策集是。即允許決策集是D2(B1).如如果我們決策選擇了果我們決策選擇了C3,則則u2(B1)=C3.n全過程中各個階段的決策組成的有序總體全過程中各個階段的決策組成的有序總體稱為策略。稱為策略。n上例中每一

5、條路線都被稱為一個策略。上例中每一條路線都被稱為一個策略。n使整個問題達(dá)到最優(yōu)效果的策略就是最優(yōu)策略使整個問題達(dá)到最優(yōu)效果的策略就是最優(yōu)策略.即上例中，路最短的策略就是最優(yōu)策略。即上例中，路最短的策略就是最優(yōu)策略。7狀態(tài)轉(zhuǎn)移方程n動態(tài)規(guī)劃中本階段的狀態(tài)是上一階段的決策動態(tài)規(guī)劃中本階段的狀態(tài)是上一階段的決策結(jié)果結(jié)果.如果給定了第如果給定了第k階段的狀態(tài)階段的狀態(tài)sk,本階段的本階段的決策就為決策就為uk(sk),則第則第k+1段的狀態(tài)段的狀態(tài)uk+1也也就完全確定了就完全確定了,它們的關(guān)系可表示它們的關(guān)系可表示為為:sk+1=Tk(sk,uk).由于它表示了由由于它表示了由k到到k1段的狀態(tài)轉(zhuǎn)移

6、規(guī)律段的狀態(tài)轉(zhuǎn)移規(guī)律,所以稱為所以稱為狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程.n即前一階段的終點（決策）是后一階段的起即前一階段的終點（決策）是后一階段的起點（狀態(tài)）。點（狀態(tài)）。n例例1的轉(zhuǎn)移方程為的轉(zhuǎn)移方程為:sk+1 =Tk(sk,uk) =uk(sk).8指標(biāo)函數(shù)n用于衡量所選定用于衡量所選定策略優(yōu)劣策略優(yōu)劣的數(shù)量指標(biāo)稱為指標(biāo)函數(shù)的數(shù)量指標(biāo)稱為指標(biāo)函數(shù).n一個一個n段決策過程段決策過程,從從1到到n叫作問題的全過程叫作問題的全過程,對于任意對于任意一個給定的一個給定的k ,從第從第k 到到n段的過程稱為全過程的一個后段的過程稱為全過程的一個后部子過程部子過程.指標(biāo)函數(shù)是定義在全過程和后部子過程上確定

7、指標(biāo)函數(shù)是定義在全過程和后部子過程上確定的數(shù)量函數(shù)。常用的數(shù)量函數(shù)。常用Vk,n表示，表示，n即即Vk,n Vk,n(sk, uk, sk+1, sn+1),k=1,2,nn 指標(biāo)函數(shù)的最優(yōu)值稱為最優(yōu)指標(biāo)函數(shù)，記為指標(biāo)函數(shù)的最優(yōu)值稱為最優(yōu)指標(biāo)函數(shù)，記為fk(sk),它表它表示從第示從第k階段狀態(tài)階段狀態(tài)sk開始到第開始到第n階段的終止?fàn)顟B(tài)的過程，階段的終止?fàn)顟B(tài)的過程，采取最優(yōu)策略所得到的指標(biāo)函數(shù)值。即采取最優(yōu)策略所得到的指標(biāo)函數(shù)值。即fk(sk)=optVk,n(sk,pk,n), fk(sk)可能是最大值，也可可能是最大值，也可能是最小值，依題意而定。能是最小值，依題意而定。n當(dāng)當(dāng)k=1時時

8、f1(s1)就是從就是從初始狀態(tài)到全過程初始狀態(tài)到全過程的整體最優(yōu)函的整體最優(yōu)函數(shù)數(shù).9指標(biāo)函數(shù)的常見形式：n（1）過程和它的任一子過程的指標(biāo)是它所包含的各階段）過程和它的任一子過程的指標(biāo)是它所包含的各階段的指標(biāo)的和。的指標(biāo)的和。（2）過程和它的任一子過程的指標(biāo)是它所包含的各階段的）過程和它的任一子過程的指標(biāo)是它所包含的各階段的指標(biāo)的乘積。指標(biāo)的乘積。n指標(biāo)函數(shù)應(yīng)具有指標(biāo)函數(shù)應(yīng)具有可分離性可分離性，并滿足，并滿足遞推關(guān)系遞推關(guān)系。vj(sj,uj)表示第表示第j階段的指標(biāo)，則階段的指標(biāo)，則1，2式分別寫為：式分別寫為：nVk,n(sk, uk, sk+1, sn+1) vk(sk,uk)+ V

9、k+1,n(sk+1, uk+1, sk+2, sn+1)nVk,n(sk, uk, sk+1, sn+1) vk(sk,uk) Vk+1,n(sk+1, uk+1, sk+2, sn+1)Vk,n(sk, uk, sk+1, sn+1)nkjjjjusv),(Vk,n(sk, uk, sk+1, sn+1)nkjjjjusv),(121210回到例1n在例在例1中中 指標(biāo)函數(shù)是距離指標(biāo)函數(shù)是距離.如第如第2階段階段,狀態(tài)狀態(tài)為為B1時時,V2,5(B1)表示從表示從B1到到F的距離的距離,而而f2(B1)則表示從則表示從B1到到 F的最短距離的最短距離.n該問題總目標(biāo)是求該問題總目標(biāo)是求f1

10、(A),即從即從A到終點到終點F的的最短距離最短距離.B1B2AC1C2C3C4D1D2D3E1E2F45235877584534843562134311n階段階段 從網(wǎng)絡(luò)圖中可看到問題可分為從網(wǎng)絡(luò)圖中可看到問題可分為k=5段段.n狀態(tài)狀態(tài) 由由A-F分為分為5段段,存在存在6種種狀態(tài)允許集狀態(tài)允許集:S1-S6 S1=A,S2=B1,B2, S3=C1,C2,C3,C4, S4=D1,D2,D3, S5=E1,E2, S6=F B1B2AC1C2C3C4D1D2D3E1E2F45235877584534843562134312n例例1中的決策允許集中的決策允許集nD1(A)=B1,B2nD2

11、(B1)=C1,C2,C3nD2(B2)=C2,C3,C4nD3(C1)=D1,D2, D3(C4)=?nD4(D1)=E1,E2,D4(D2)= E1,E2nD5(E1)=F, D5(E2)=FB1B2AC1C2C3C4D1D2D3E1E2F45235877584534843562134313n狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程 例例1中的狀態(tài)轉(zhuǎn)移方程中的狀態(tài)轉(zhuǎn)移方程sk+1=uk(sk) 如如: s3=u2(B1)=C2.n指標(biāo)函數(shù)指標(biāo)函數(shù) 例例1中的指標(biāo)函數(shù)是距離中的指標(biāo)函數(shù)是距離,(是數(shù)值是數(shù)值) V2,5(B1)=13n最優(yōu)值函數(shù)最優(yōu)值函數(shù)fk(sk), 例例1中中f5(E2)=3.B1B2A

12、C1C2C3C4D1D2D3E1E2F45235877584534843562134314二、動態(tài)規(guī)劃的基本思想和基本方程二、動態(tài)規(guī)劃的基本思想和基本方程n最短路線有一個重要特性：如果由起點最短路線有一個重要特性：如果由起點A經(jīng)經(jīng)P點和點和H點點最終到達(dá)最終到達(dá)F點是一條最短路線，則由點是一條最短路線，則由P點出發(fā)經(jīng)過點出發(fā)經(jīng)過H點點最終到達(dá)最終到達(dá)F點的這條路線必定也是從點的這條路線必定也是從P點到點到F點的最短路。點的最短路。n根據(jù)這一特性，尋找最短路的方法，就是從最后一段開根據(jù)這一特性，尋找最短路的方法，就是從最后一段開始，用由后向前逐步遞推的方法，求出各點到始，用由后向前逐步遞推的方法

13、，求出各點到F點的最點的最短路，最后求得短路，最后求得A點到點到F點的最短路。所以點的最短路。所以動態(tài)規(guī)劃的動態(tài)規(guī)劃的方法是從終點逐段向始點方向?qū)ふ易疃搪返囊环N方法方法是從終點逐段向始點方向?qū)ふ易疃搪返囊环N方法。的最短路到的最短路到FPFAFHPFHPA,.,.,.15n動態(tài)規(guī)劃的尋優(yōu)途徑：是從終點逐段向始動態(tài)規(guī)劃的尋優(yōu)途徑：是從終點逐段向始點方向?qū)ふ易疃搪肪€。點方向?qū)ふ易疃搪肪€。n解例解例1：n從例從例1得出動態(tài)規(guī)劃的基本方程。得出動態(tài)規(guī)劃的基本方程。16B1B2AC1C2C3C4D1D2D3E1E2F45235877584534843562134317B1B2AC1C2C3C4D1D2D3

14、E1E2F452358775845348435621343, 3)(, 4)(52515 EfEfk時時，時，時，4 kEDuEfEDdEfEDdDfEDuEfEDdEfEDdDfEDuEfEDdEfEDdDf134252341513434224252241512424114252141511414)(, 53341min)(),()(),(min)()(, 53246min)(),()(),(min)()(, 73543min)(),()(),(min)(18B1B2AC1C2C3C4D1D2D3E1E2F452358775845348435621343EDuDfEDuDfEDuDf1343

15、42242411414)(, 5)()(, 5)()(, 7)( DCuDfDCdDfDCdCfDCuDfDCdDfDCdCfDCuDfDCdDfDCdCfDCuDfDCdDfDCdCfk343343432424343233343332423333223242231412323113242131411313)(, 95458min)(),()(),(min)()(, 85453min)(),()(),(min)()(,105574min)(),()(),(min)()(,125875min)(),()(),(min)(3 時，時，19B1B2AC1C2C3C4D1D2D3E1E2F452358

16、775845348435621343DCuCfDCuCfDCuCfDCuCf34343233332232311313)(, 9)()(, 8)()(,10)()(,12)( .)(,17155134min)(),()(),(min)(1.)(,159787108min)(),()(),()(),(min)(.,)(,1385103122min)(),()(),()(),(min)(21122211111132243422333222322222321233312232121311212BAuBfBAdBfBAdAfCBuCfCBdCfCBdCfCBdBfCCBuCfCBdCfCBdCfCBdB

17、fkk 時時，時時，20B1B2AC1C2C3C4D1D2D3E1E2F452358775845348435621343綜上所知，該問題的綜上所知，該問題的最短距離為最短距離為17，最短路線為：，最短路線為：21動態(tài)規(guī)劃的基本方程n從上面的計算過程中可以看出，在求解的各個階從上面的計算過程中可以看出，在求解的各個階段，我們利用了段，我們利用了k階段與階段與k+1階段的遞推關(guān)系：階段的遞推關(guān)系： FsdsfsfksufsusdsfkkkkkkksDukkkkk,01 , 2 , 3 , 4 , 5,5555661min或或?qū)憣懗沙?2動態(tài)規(guī)劃的基本方程n一般情況，一般情況，k階段與階段與k+1階

18、段的遞推關(guān)系式可寫階段的遞推關(guān)系式可寫為：為：n上式稱為動態(tài)規(guī)劃的基本方程。上式稱為動態(tài)規(guī)劃的基本方程。 01 , 1,111 nnkkkkkkksDukksfnnksufsusvoptsfkkk邊邊界界條條件件為為23動態(tài)規(guī)劃方法的基本思想P197n(1)動態(tài)規(guī)劃方法的關(guān)鍵在于正確的動態(tài)規(guī)劃方法的關(guān)鍵在于正確的 寫出基本的寫出基本的遞推關(guān)系式和恰當(dāng)?shù)倪吔鐥l件遞推關(guān)系式和恰當(dāng)?shù)倪吔鐥l件(簡言之為簡言之為基本方基本方程程)。n(2)在多階段決策過程中在多階段決策過程中,動態(tài)規(guī)劃方法是既把當(dāng)動態(tài)規(guī)劃方法是既把當(dāng)前一段和未來各段分開前一段和未來各段分開,又把當(dāng)前效應(yīng)和未來效又把當(dāng)前效應(yīng)和未來效應(yīng)結(jié)合

19、起來考慮的一種最優(yōu)化方法應(yīng)結(jié)合起來考慮的一種最優(yōu)化方法.因此每段決因此每段決策的選取是從策的選取是從全局考慮全局考慮的的,與該段的最優(yōu)選擇答與該段的最優(yōu)選擇答案一般是不同的。案一般是不同的。n(3)在求整個問題的最優(yōu)策略時在求整個問題的最優(yōu)策略時,由于初始狀態(tài)是由于初始狀態(tài)是已知的已知的,而每段的決策都是該段的狀態(tài)函數(shù)而每段的決策都是該段的狀態(tài)函數(shù),故最故最優(yōu)策略所經(jīng)過的各段狀態(tài)便可逐次變換得到優(yōu)策略所經(jīng)過的各段狀態(tài)便可逐次變換得到,從從而確定了最優(yōu)路線。而確定了最優(yōu)路線。24最短路問題的圖上作業(yè)法標(biāo)號法B1B2AC1C2C3C4D1D2D3E1E2F452358775845348435621

20、343437551210891315170逆序解法25B1B2AC1C2C3C4D1D2D3E1E2F452358775845348435621343最短路問題的圖上作業(yè)法標(biāo)號法04567912111213141417順序解法26動態(tài)規(guī)劃的最優(yōu)性原理n作為整個過程的最優(yōu)策略具有如下性質(zhì)：作為整個過程的最優(yōu)策略具有如下性質(zhì)：不管在此最優(yōu)策略上的某個狀態(tài)以前的狀不管在此最優(yōu)策略上的某個狀態(tài)以前的狀態(tài)和決策如何，對該狀態(tài)來說，以后的所態(tài)和決策如何，對該狀態(tài)來說，以后的所有決策必定構(gòu)成最優(yōu)子策略，也就是說有決策必定構(gòu)成最優(yōu)子策略，也就是說最最優(yōu)策略的任一子策略都是最優(yōu)的。優(yōu)策略的任一子策略都是最優(yōu)的。

21、注意：最優(yōu)性原理不是對任何決策過程都普遍成立注意：最優(yōu)性原理不是對任何決策過程都普遍成立的；而且，最優(yōu)性原理與動態(tài)規(guī)劃基本方程，的；而且，最優(yōu)性原理與動態(tài)規(guī)劃基本方程，并不是無條件等價的，兩者之間也不存在確定的并不是無條件等價的，兩者之間也不存在確定的蘊含關(guān)系。蘊含關(guān)系。27動態(tài)規(guī)劃的最優(yōu)性定理.minoptVmaxoptVk)(nk1k),.,(,n,.21knpsusTsppppsVoptpsVoptpsVsuuup-1k11-1k-1k-1kknk-1k1n1n,kkn,k*-1k11-1k1*n11n11*n*2*1*n1knknk11-k11-k1sppspp取取是是損損失失函函數(shù)數(shù)

22、時時，；當(dāng)當(dāng)取取是是效效益益函函數(shù)數(shù)時時，段段狀狀態(tài)態(tài)。當(dāng)當(dāng)所所確確定定的的和和子子策策略略它它是是由由給給定定的的初初始始狀狀態(tài)態(tài)），（），（式式中中，（），（時時，有有），當(dāng)當(dāng)初初始始狀狀態(tài)態(tài)為為（任任一一個個為為：對對是是最最優(yōu)優(yōu)策策略略的的充充要要條條件件則則允允許許策策略略，階階段段變變量量為為的的多多階階段段決決策策過過程程，其其設(shè)設(shè)階階段段數(shù)數(shù)為為，）（，）（， 28三、動態(tài)規(guī)劃與靜態(tài)規(guī)劃的關(guān)系n將將與時間無關(guān)與時間無關(guān)的線性規(guī)劃問題或非線性規(guī)的線性規(guī)劃問題或非線性規(guī)劃問題稱為靜態(tài)規(guī)劃。而動態(tài)規(guī)劃所研究劃問題稱為靜態(tài)規(guī)劃。而動態(tài)規(guī)劃所研究的問題是的問題是與時間有關(guān)與時間有關(guān)的，它

23、是研究具有多的，它是研究具有多階段決策過程的一類問題，階段決策過程的一類問題，將問題的整體將問題的整體按時間或空間的特征而分成若干個前后銜按時間或空間的特征而分成若干個前后銜接的時空階段，從而求出了整個問題的最接的時空階段，從而求出了整個問題的最優(yōu)決策序列。優(yōu)決策序列。因此，對于某些靜態(tài)的問題，因此，對于某些靜態(tài)的問題，也可以人為的也可以人為的引入時間引入時間因素，把它看作按因素，把它看作按階段進行的一個動態(tài)規(guī)劃問題，這就使得階段進行的一個動態(tài)規(guī)劃問題，這就使得動態(tài)規(guī)劃成為求解某些線性、非線性規(guī)劃動態(tài)規(guī)劃成為求解某些線性、非線性規(guī)劃的有效方法。（的有效方法。（P203）291、動態(tài)規(guī)劃模型的建

24、立、動態(tài)規(guī)劃模型的建立n建立動態(tài)模型的建立動態(tài)模型的6個要素：個要素：n1）階段）階段kn2）狀態(tài)）狀態(tài)SKn3)決策決策uk(sk)n4）狀態(tài)轉(zhuǎn)移方程）狀態(tài)轉(zhuǎn)移方程n5）階段指標(biāo)函數(shù)）階段指標(biāo)函數(shù)n6）指標(biāo)遞推方程）指標(biāo)遞推方程30動態(tài)規(guī)劃的求解方法有兩種：動態(tài)規(guī)劃的求解方法有兩種： 逆序解法與順序解法逆序解法與順序解法2、動態(tài)規(guī)劃模型的解法、動態(tài)規(guī)劃模型的解法2、在已知終止?fàn)顟B(tài)、在已知終止?fàn)顟B(tài)Sn下，采用順序解法（正向遞歸）下，采用順序解法（正向遞歸）1、在已知初始狀態(tài)、在已知初始狀態(tài)S1下，采用逆序解法：（反向遞歸）下，采用逆序解法：（反向遞歸）31 242214242132213211

25、3132122212211212211211111221211111210101257)(),()(95745min),(),(min75843min),(),(min642),(254100BCuBfCBdCfBCuBfCBdBfCBdCfBCuBfCBdBfCBdCfBCuBfCBdCfkABuBfABuBfsfkAfsfk）（）（）（）（）（）（）（）（）（）（）（）（時時，）（）（）（）（）的的定定義義有有：（時時，按按，這這是是邊邊界界條條件件。）（）（，計計算算如如下下：順序解法解例1：B1B2AC1C2C3C4D1D2D3E1E2F452358775845348435621343

26、32FAFEDCBAFfEFuFfDEuEfDEuEfCDuDfCDuDfCCDuDfEDCBc 223122215255224241141433333322323211313.17)(17)(14)(14)(14)(12)(11)(:或或路徑為路徑為最短路長為最短路長為）（）（）（）（或或）（或或）（類似可以算出類似可以算出B1B2AC1C2C3C4D1D2D3E1E2F452358775845348435621343333、兩種解法在建模時的區(qū)別如下表所示、兩種解法在建模時的區(qū)別如下表所示34四、資源分配問題 所謂資源分配問題就是將一定數(shù)量的一種或所謂資源分配問題就是將一定數(shù)量的一種或多種

27、資源恰當(dāng)?shù)胤峙浣o若干個使用者多種資源恰當(dāng)?shù)胤峙浣o若干個使用者,而使目標(biāo)而使目標(biāo)函數(shù)為最優(yōu)。函數(shù)為最優(yōu)。如：甲流感疫苗的分配問題，優(yōu)先如：甲流感疫苗的分配問題，優(yōu)先讓幼兒園小朋友以及中小學(xué)生接種，然后才能是讓幼兒園小朋友以及中小學(xué)生接種，然后才能是成年人接種，原因是中小學(xué)生集聚在學(xué)校，容易成年人接種，原因是中小學(xué)生集聚在學(xué)校，容易傳播，另外，他們不知道回避感染者，所以，將傳播，另外，他們不知道回避感染者，所以，將有限的資源先分配給中小學(xué)生以及幼兒園。這就有限的資源先分配給中小學(xué)生以及幼兒園。這就是資源分配問題。是資源分配問題。351、一維資源分配問題n 有某種資源總量為有某種資源總量為a ，用于

28、生產(chǎn)，用于生產(chǎn)n種產(chǎn)種產(chǎn)品。設(shè)分配數(shù)量品。設(shè)分配數(shù)量Xi用于生產(chǎn)第用于生產(chǎn)第i種產(chǎn)品，第種產(chǎn)品，第i種產(chǎn)品的收益為種產(chǎn)品的收益為gi(Xi) 。問：如何分配。問：如何分配才使總收益最大？才使總收益最大？產(chǎn)品資源用量收益A1An資源限量x1xng1(x1)gn(xn)a該問題的靜態(tài)規(guī)劃模型為：Maxz=g1(x1)+ g2(x2)+ gn(xn)X1+ x2+ xn=axi0(i=1,2,n)36建立動態(tài)模型的6個要素：（提問）n1）階段階段n2）狀態(tài)變量）狀態(tài)變量n3)決策變量決策變量n4）狀態(tài)轉(zhuǎn)移方程）狀態(tài)轉(zhuǎn)移方程n5）階段指標(biāo)函數(shù)）階段指標(biāo)函數(shù)n6）指標(biāo)遞推方程）指標(biāo)遞推方程37分析：n如

29、果將生產(chǎn)如果將生產(chǎn)n種產(chǎn)品作為一個互相銜接的整體，種產(chǎn)品作為一個互相銜接的整體，對一種產(chǎn)品的資源分配作為一個階段，每個階段對一種產(chǎn)品的資源分配作為一個階段，每個階段確定對一種產(chǎn)品的資源投放量。則該問題成為一確定對一種產(chǎn)品的資源投放量。則該問題成為一個多階段決策問題。個多階段決策問題。n狀態(tài)變量狀態(tài)變量sk的選取原則是的選取原則是要能夠據(jù)此確定決策變要能夠據(jù)此確定決策變量量uk，以及滿足狀態(tài)轉(zhuǎn)移方程所要求的無后效性。以及滿足狀態(tài)轉(zhuǎn)移方程所要求的無后效性。n在資源分配問題中，決策變量選為對產(chǎn)品在資源分配問題中，決策變量選為對產(chǎn)品k的資的資源投放量，因此源投放量，因此狀態(tài)變量可以選擇為階段狀態(tài)變量可

30、以選擇為階段k初所初所擁有的資源量，即將要在第擁有的資源量，即將要在第k種到第種到第n種產(chǎn)品間種產(chǎn)品間分配的資源量。分配的資源量。該問題的靜態(tài)規(guī)劃模型為：Maxz=g1(x1)+ g2(x2)+ gn(xn)X1+ x2+ xn=axi0(i=1,2,n)38一維資源分配問題動態(tài)規(guī)劃模型為：n階段變量階段變量k1、2nn狀態(tài)變量狀態(tài)變量sk表示分配給用于生產(chǎn)第表示分配給用于生產(chǎn)第k種至第種至第n種產(chǎn)種產(chǎn)品的資源數(shù)量品的資源數(shù)量之和之和。取值范圍是。取值范圍是 0skan決策變量決策變量uk表示分配給第表示分配給第k種產(chǎn)品的資源數(shù)量。種產(chǎn)品的資源數(shù)量。取值范圍是：取值范圍是： 0uksk。 n狀

31、態(tài)轉(zhuǎn)移方程為狀態(tài)轉(zhuǎn)移方程為 sk+1=sk-uk n階段指標(biāo)函數(shù)為分配資源階段指標(biāo)函數(shù)為分配資源uk用于生產(chǎn)第用于生產(chǎn)第k種產(chǎn)品種產(chǎn)品時的收益，有時的收益，有Vk(sk, uk)=gk(uk)= gk(xk)n指標(biāo)遞推方程為：指標(biāo)遞推方程為： )()()()()(maxmax110 xgsfsfxgsfnnnnkkkkkksxsxnnkk39n例2：某有色金屬公司擬撥出某有色金屬公司擬撥出50萬元對所萬元對所屬三家冶煉廠進行技術(shù)改造。若以屬三家冶煉廠進行技術(shù)改造。若以10萬元萬元為最小分割單位，各廠收益與投資的關(guān)系為最小分割單位，各廠收益與投資的關(guān)系如下：如下：n公司經(jīng)理從定量決策的需要出發(fā)，

32、要求公公司經(jīng)理從定量決策的需要出發(fā)，要求公司的系統(tǒng)分析組求出：對三個工廠如何分司的系統(tǒng)分析組求出：對三個工廠如何分配這配這50萬元，才能使總收益達(dá)到最大？萬元，才能使總收益達(dá)到最大？投資額01234504.57910.512024.57.5111505781013技術(shù)改造后收益工廠1 工廠2 工廠340投資額01234504.57910.512024.57.5111505781013技術(shù)改造后收益工廠1 工廠2 工廠3n解：首先工廠解：首先工廠1進行分配，余進行分配，余下的工廠下的工廠2進行分配，最后余進行分配，最后余下的分配給工廠下的分配給工廠3。建立動態(tài)。建立動態(tài)規(guī)劃數(shù)學(xué)模型過程如下：規(guī)劃

33、數(shù)學(xué)模型過程如下：工廠1工廠2工廠31231）階段變量）階段變量k=1,2,32)狀態(tài)變量狀態(tài)變量sk表示分配給第表示分配給第k個工廠至第個工廠至第n個工廠的資金數(shù)。個工廠的資金數(shù)。3）決策變量）決策變量xk表示為表示為分配給第分配給第k個工廠的資金數(shù)。個工廠的資金數(shù)。4）狀態(tài)轉(zhuǎn)移方程）狀態(tài)轉(zhuǎn)移方程sk+1=sk-xk為為分配給第分配給第k+1個工廠至第個工廠至第n個個工廠的資金數(shù)。工廠的資金數(shù)。5）階段指標(biāo)函數(shù)）階段指標(biāo)函數(shù)gk(xk)表示為資金表示為資金xk分配給第分配給第k個工廠個工廠所得的收益。所得的收益。6）指標(biāo)遞推方程為：）指標(biāo)遞推方程為： 0)(11)(440) 1 , 2 ,

34、3()()(maxsfksfxgsfkkkksxkkkk41最大盈利：最大盈利：f3(s3)=g3(x3)+f4(s4).投資額01234504.57910.512024.57.5111505781013技術(shù)改造后收益工廠1 工廠2 工廠3s3x3g3(x3)+f4(s4)012345012345f3(s3)x3*0578101300517283104135K=3時，設(shè)將時，設(shè)將s3萬元全部分配給工廠萬元全部分配給工廠3計算如下：計算如下：42最大盈利為：最大盈利為：f2(s2)=投資額01234504.57910.512024.57.5111505781013技術(shù)改造后收益工廠1 工廠2 工

35、廠3)()(3322max2sfxgxs2x2g2(x2)+f3(s3)0123450123450+00+52+00+72+54.5+00+82+74.5+57.5+00+102+84.5+77.5+511+00+132+104.5+87.5+711+5 15+0 f2(s2)x2*005070,19.5212.53164 K=2時，設(shè)將時，設(shè)將s2萬元全部分配萬元全部分配給工廠給工廠2和和3；x2=0,1,2,3,4,5計算如下：43最大盈利為：最大盈利為：f1(s1)= )()(2211max1sfxgx 016164.5+12.5=177+9.5=16.57+9=1610.5+5=15.

36、512+0=12012345171g1(x1)+f2(s2)s1x1f1(s1)x1*5由此可知， s1=5,此時， x1*1，s2= s1- x1*=5-1=4,此時， x2*3s3= s2- x2*=431，此時， x3*1Z*=17,最優(yōu)策略為P*x1*， x2*， x3*1，3，1即，1，2，3工廠分別分配10萬，30萬，10萬元。投資額01234504.57910.512024.57.5111505781013技術(shù)改造后收益工廠1 工廠2 工廠3 K=1時，設(shè)將時，設(shè)將s1萬元全部分配萬元全部分配給工廠給工廠1、2和和3；x1=0，1，2，3，4，5計算如下：44例例3.某公司有資金

37、某公司有資金10萬元，若投資項目萬元，若投資項目i（i=1,2,3）的投資額為）的投資額為 時時,其效益分別為其效益分別為:問應(yīng)如何分配投資數(shù)額才能使總收益最大問應(yīng)如何分配投資數(shù)額才能使總收益最大? 可列出它的靜態(tài)模型可列出它的靜態(tài)模型: 23332221112)(,9)(,4)(xxgxxgxxg 分析分析:這是一個表面與時這是一個表面與時間沒有任何關(guān)系的問題間沒有任何關(guān)系的問題,但但要用動態(tài)規(guī)劃的方法去解要用動態(tài)規(guī)劃的方法去解則必須把它劃分為則必須把它劃分為“時時段段”.本題可劃分為本題可劃分為3個時個時段段,每段只決定對一個投資每段只決定對一個投資項目的投資額項目的投資額.這樣把問題這樣

38、把問題分解為分解為3階段決策問題階段決策問題. )3 , 2 , 1(010294max3212321ixxxxxxxzixi45kkxu :3、決策變量為、決策變量為 0321,max644110）（，）（）（）（、遞遞推推方方程程為為：sfksfxgsfkkkksxkkkk kkkkkkkkxuussxuussxususs11221121111104顯顯然然有有：、狀狀態(tài)態(tài)轉(zhuǎn)轉(zhuǎn)移移方方程程：解：1、階段變量、階段變量k1、2、32、狀態(tài)變量為、狀態(tài)變量為sk)(5xgkk、階段指標(biāo)函數(shù)：、階段指標(biāo)函數(shù)：46 ;2,2max,3233*32303333ssxxsfksx時時，函函數(shù)數(shù)取取極極

39、大大值值為為顯顯然然當(dāng)當(dāng)）（時時當(dāng)當(dāng) 47當(dāng)當(dāng)k=2k=2時時, , 222202320332022)(29max29max)(9max)(222222xsxsxsfxsfsxsxsx 這是一個函數(shù)求極值問題,利用微分方法可求得該函數(shù)有極小值.是極小值點。而4922 sx222029222220)()(222ssxsxssfsf，即：的端點取得，而極大值只能在0ss2x248要討論要討論 的具體情況的具體情況: 2s.,2222,290,2222,292*202*202)()()()(222222做做出出到到此此第第二二階階段段的的決決策策已已此此時時時時當(dāng)當(dāng)此此時時時時當(dāng)當(dāng)sxsxxsxsx

40、xssfsfsfsf 49 .,29010,29:,922:959max994max94max922)(4max)(,101122*222*221011100111100211002221011*122*11112211)()(故舍去故舍去此結(jié)論與前矛盾此結(jié)論與前矛盾而而即即時時當(dāng)當(dāng)注注時時時時當(dāng)當(dāng) xxxxxsxxsssxssxssxsxsxsxsxssxsfxsfksfsf減函數(shù)減函數(shù)50 .100291001004010,1020010,0100124max1024max20*3*22*112*11111112111100121110112222*2111到到第第三三個個項項目目最最優(yōu)優(yōu)

41、方方案案為為全全部部資資金金投投再再由由狀狀態(tài)態(tài)方方程程順順推推：）（時時當(dāng)當(dāng)）（時時當(dāng)當(dāng)?shù)牡亩硕它c點，比比較較。微微分分求求解解又又是是一一個個求求極極值值問問題題，）（）（）（）（此此時時）（，另另取取 xxsxssxfxfxsxxsxfxsxsfssfxxsx512、資源連續(xù)分配問題n將一種將一種有消耗性有消耗性的資源，多階段地在多種不的資源，多階段地在多種不同的生產(chǎn)活動中投放的問題稱為資源的多段同的生產(chǎn)活動中投放的問題稱為資源的多段分配問題，下面討論其中包含有兩個生產(chǎn)活分配問題，下面討論其中包含有兩個生產(chǎn)活動的簡單情況。動的簡單情況。52n一般提法：設(shè)有某種資源，初始的擁有量一般提法：

42、設(shè)有某種資源，初始的擁有量是是M。計劃在。計劃在A，B兩個生產(chǎn)部門連續(xù)使用兩個生產(chǎn)部門連續(xù)使用n個階段。已知在部門個階段。已知在部門A投入資源投入資源uA時的時的階段收益是階段收益是g(uA)，在部門，在部門B投入資源投入資源uB時的階段收益是時的階段收益是h(uB)。又資源在生產(chǎn)中。又資源在生產(chǎn)中將有部分消耗，已知每生產(chǎn)一個階段后部將有部分消耗，已知每生產(chǎn)一個階段后部門門A、B中的資源完好率分別為中的資源完好率分別為a和和b，0a、 b0) x1,x2,x30解：按問題變量的個數(shù)劃分階段，解：按問題變量的個數(shù)劃分階段，階段階段k1，2，3；狀態(tài)變量為；狀態(tài)變量為s1,s2,s3;且且s1c；

43、決策變量為決策變量為x1,x2,x3；狀態(tài)轉(zhuǎn)移方程為；狀態(tài)轉(zhuǎn)移方程為sk+1 xk =sk, 階段指標(biāo)函數(shù)階段指標(biāo)函數(shù)gk(xk)表示為表示為x1,x22,x3設(shè)設(shè)， s3 x3， s3 x2 s2， s2 x1 s1 c則有則有 x3 s3，0 x2 s2， 0 x1 s1 c則，遞推方程為則，遞推方程為s.t.x1x2x3 sxgsfksfxgsfsxkkkksxkkkk333)(11)()(max() 1 , 2 , 3()()(max3333059n例5：用動態(tài)規(guī)劃解下面問題P207nMaxz=4x12-x22+2x32+12 3x1+2x2+x39 xi0,(i=1,2,3)解：按問

44、題變量的個數(shù)劃分階段，階段解：按問題變量的個數(shù)劃分階段，階段k1,2,3；狀態(tài)變量為狀態(tài)變量為s1,s2,s3,s4;且且s19 ；決策變量為決策變量為x1,x2,x3；狀態(tài)轉(zhuǎn)移方程為；狀態(tài)轉(zhuǎn)移方程為sk+1 axk =sk,具體為：具體為：s3=x3,s3+2x2=s2,s2+3x1=s1則有：則有： x3 = s3,0 x2 s2/2, 0 x1 s1/3階段指標(biāo)函數(shù)階段指標(biāo)函數(shù)gk(xk)表示為表示為4x12,-x22,2x32遞推關(guān)系式：遞推關(guān)系式：x1x2x3 12)()()(max)(4411sfsfxgsfkkkkkk60五、生產(chǎn)與存貯問題n一般提法：設(shè)某公司對某種產(chǎn)品要制定一一

45、般提法：設(shè)某公司對某種產(chǎn)品要制定一項項n個階段的生產(chǎn)（或購買）計劃。已知個階段的生產(chǎn)（或購買）計劃。已知它的它的初始庫存量為零初始庫存量為零，每階段，每階段生產(chǎn)生產(chǎn)（或購（或購買）該產(chǎn)品的數(shù)量買）該產(chǎn)品的數(shù)量有上限的限制有上限的限制；每階段；每階段社會對該產(chǎn)品的社會對該產(chǎn)品的需求量是已知需求量是已知的，公司保的，公司保證供應(yīng)，在證供應(yīng)，在n階段末的階段末的終結(jié)庫存量為零終結(jié)庫存量為零。問該公司如何制定每個階段的生產(chǎn)（或采問該公司如何制定每個階段的生產(chǎn)（或采購）計劃，從而使總成本最小。購）計劃，從而使總成本最小。61模型的建立：n1、階段變量：階段變量：k=1、2、n；n2、決策變量、決策變量x

46、k，為第，為第k階段該產(chǎn)品的生產(chǎn)量階段該產(chǎn)品的生產(chǎn)量（或采購量）；（或采購量）；dk為第為第k階段對產(chǎn)品的需求量。階段對產(chǎn)品的需求量。n3、狀態(tài)變量、狀態(tài)變量vk，為第為第k階段結(jié)束時的產(chǎn)品庫存量。階段結(jié)束時的產(chǎn)品庫存量。n4、狀態(tài)轉(zhuǎn)移方程：、狀態(tài)轉(zhuǎn)移方程：vk=vk-1+xk-dkn5、階段指標(biāo)函數(shù)：、階段指標(biāo)函數(shù)：ck(xk)表示第表示第k階段生產(chǎn)產(chǎn)階段生產(chǎn)產(chǎn)品品xk時的成本費用，時的成本費用， hk(vk)表示在第表示在第k階段結(jié)階段結(jié)束時的產(chǎn)品庫存量束時的產(chǎn)品庫存量vk所需的存儲費用。所需的存儲費用。n第第k階段的成本費用階段的成本費用ck(xk)+ hk(vk)62 產(chǎn)品的上限）產(chǎn)品

47、的上限）為每階段最多能生產(chǎn)該為每階段最多能生產(chǎn)該為單位產(chǎn)品成本為單位產(chǎn)品成本m(ma,m2 , 1aK00)(xxxxxckkkkkk),mmin(0)(f0)s (f)d,s (vmin)s (fdvsdkkk1n1nkk1k1kkkkkk 其中，其中，6、指標(biāo)遞推方程：、指標(biāo)遞推方程：63 例題6：某工廠與購貨單位簽訂的供某工廠與購貨單位簽訂的供貨合同如下表。該廠每月最大產(chǎn)量為貨合同如下表。該廠每月最大產(chǎn)量為4百件，倉庫的存貨能力為百件，倉庫的存貨能力為3百件。已知百件。已知每一百件貨物的生產(chǎn)費為一萬元。在生每一百件貨物的生產(chǎn)費為一萬元。在生產(chǎn)的月份，每批產(chǎn)品的生產(chǎn)準(zhǔn)備費為產(chǎn)的月份，每批產(chǎn)

48、品的生產(chǎn)準(zhǔn)備費為4千元，倉庫保管費為每一百件貨物每月千元，倉庫保管費為每一百件貨物每月一千元。假定一千元。假定1月初開始時及月初開始時及6月底交月底交貨后倉庫中都無存貨。問該廠應(yīng)該如何貨后倉庫中都無存貨。問該廠應(yīng)該如何安排每月的生產(chǎn)與庫存，才能既滿足交安排每月的生產(chǎn)與庫存，才能既滿足交貨合同的要求，又使總費用最??？貨合同的要求，又使總費用最??？64（4）狀態(tài)轉(zhuǎn)移方程：）狀態(tài)轉(zhuǎn)移方程：cdsskkkk 1（5）第）第k月的總費用包括生產(chǎn)費和庫存費月的總費用包括生產(chǎn)費和庫存費 040,104),(dsdsddsvkkkkkkkk 0)(40)(),(min)(7711sdfsfdsvsfkkkkk

49、kkk（6）基本遞推方程）基本遞推方程解：解：1、建立動態(tài)規(guī)劃模型、建立動態(tài)規(guī)劃模型（1）階段劃分：）階段劃分：k=1，2，3，4，5，6（2）狀態(tài)變量）狀態(tài)變量sk表示第表示第k月初的庫存量，月初的庫存量，s1=0（3）決策變量）決策變量dk表示第表示第k月的計劃生產(chǎn)量月的計劃生產(chǎn)量 表示第表示第K月的合同交貨量月的合同交貨量30 sk40 dkck652、用逆序算法求解、用逆序算法求解當(dāng)當(dāng)k=6時，時，s6+d6-1=s7=0, 所以所以 s6+d6=1，f6(s6)=minv6(s6,d6) 當(dāng)當(dāng)s6=0,d6=1, f6(s6)=14，當(dāng)，當(dāng)s6=1,d6=0, f6(s6)=1當(dāng)當(dāng)k

50、=5時，時，s5+d5-2=s6, 所以所以 3255 ds 35130414204min)(),(min)(,10,32, 06655555655 sfdsvsfsds當(dāng)當(dāng) 1611042142min)(),(min)(,10,10, 26655555655 sfdsvsfsds當(dāng)當(dāng) 4130min)(),(min)(,1,0, 36655555655 sfdsvsfsds當(dāng)當(dāng) 261120414104min)(),(min)(,10,21, 16655555655 sfdsvsfsds當(dāng)當(dāng)66 692640435304min)(),(min)(,10,43, 05544444544 sfd

51、svsfsds當(dāng)當(dāng) 5042404162344262204352104min)(),(min)(,3210,4321, 25544444544 sfdsvsfsds當(dāng)當(dāng) 384330416320426310435300min)(),(min)(,3210,3210, 35544444544 sfdsvsfsds當(dāng)當(dāng) 60161404261304351204min)(),(min)(,210,432,sfdsvsfsds當(dāng)當(dāng)當(dāng)當(dāng)k=4時，時，s4+d4-3=s5, 所以所以 6344 ds67所求最優(yōu)決策結(jié)果如下表：68再生產(chǎn)點性質(zhì)p227n很多庫存問題有如下特征：n（

52、1）對于每個i，有vi-1xi=0,其中，v00.即前一階段的庫存量乘以本階段的生產(chǎn)量等于零，前提是第一階段初的庫存為0.n（2）對最優(yōu)生產(chǎn)決策來說，它被裂解為多個子問題：分別是第一至第二階段，第三至第四階段，第五至第六階段等，每個子問題的最優(yōu)生產(chǎn)決策為：它們的最小總成本之和就等于原問題的最小總成本。符合以上規(guī)律的問題可以大大減少計算。69再生產(chǎn)點n如果對每個i，都有vi-1xi=0，則稱該點的生產(chǎn)決策具有再生產(chǎn)點性質(zhì)（又稱重生性質(zhì)）。如果vi=0,則稱階段i為再生產(chǎn)點。n由假設(shè)v0=0和vn=0，故階段0和n是再生產(chǎn)點，運用再生產(chǎn)點性質(zhì)可以求庫存問題為凹函數(shù)的解。公式如下：70時時當(dāng)當(dāng)?shù)淖顑?yōu)

53、生產(chǎn)決策為：的最優(yōu)生產(chǎn)決策為：到到則從階段則從階段對應(yīng)的遞推關(guān)系式：對應(yīng)的遞推關(guān)系式：nnjnjsnnjniijcijcxdxfffdhcdcsnnjssnjjijtijsijsisttssijssj,.,2)(, 1)(0)(0,.2 , 1),()()0()(),()()(011111min 71舉例：p225 固定成本固定成本3千元，單位可變成本千元，單位可變成本1千元，每期千元，每期最大生產(chǎn)能為最大生產(chǎn)能為6個單位，每期末未售出的產(chǎn)品每個單位，每期末未售出的產(chǎn)品每單位存貯費為單位存貯費為0.5千元，第一時期初與第六時期末千元，第一時期初與第六時期末的庫存均為的庫存均為0，求總成本最小的

54、生產(chǎn)計劃。，求總成本最小的生產(chǎn)計劃。72（背包問題）某工廠生產(chǎn)三種產(chǎn)品，各種產(chǎn)（背包問題）某工廠生產(chǎn)三種產(chǎn)品，各種產(chǎn)品重量與利潤的關(guān)系下表所示?，F(xiàn)將此三種品重量與利潤的關(guān)系下表所示?，F(xiàn)將此三種產(chǎn)品運往市場出售，運輸能力總重量不超過產(chǎn)品運往市場出售，運輸能力總重量不超過6噸，問如何安排使運輸總利潤最大噸，問如何安排使運輸總利潤最大731、建立動態(tài)規(guī)劃模型（在此用的是逆序算法求解，與課、建立動態(tài)規(guī)劃模型（在此用的是逆序算法求解，與課本不同）本不同）（1）階段劃分：）階段劃分：k=1,2,3，把裝載一種產(chǎn)品看成一個階段，把裝載一種產(chǎn)品看成一個階段（2）狀態(tài)變量）狀態(tài)變量sk表示第表示第k階段初可用于裝載產(chǎn)品的總?cè)萘侩A段初可用于裝載產(chǎn)品的總?cè)萘苛?，量，s1=6（3）決策變量）決策變量dk表示第表示第k階段裝載第階段裝載第k種貨物的件數(shù)。種貨物的件數(shù)。 （4）狀態(tài)轉(zhuǎn)移方程：）狀態(tài)轉(zhuǎn)移方程： 其中其中ak表示第表示第k種貨物的單件重量種貨物的單件重量dasskkkk 1（5）指標(biāo)函數(shù)：）指標(biāo)函數(shù)：vk(sk,dk)表示裝載第表示裝載第k種貨物種貨物dk件所得的利件所得的利潤，即潤，即v1(s1,d1)=80d1,v2(s2,