高等教育運籌學(xué)課程動態(tài)規(guī)劃

1、動態(tài)規(guī)劃（2）應(yīng)用舉例1、建立動態(tài)規(guī)劃模型的一般步驟1 劃分階段。即按時間和空間的先后順序適當?shù)貏澐譃闈M足遞推關(guān)系的若干個階段。2 正確選擇狀態(tài)變量。（可知性和無后效性）3 根據(jù)狀態(tài)變量和決策變量的含義，正確寫出狀態(tài)轉(zhuǎn)移方程 Sk+1=Tk(sk,uk)4 明確指標函數(shù)Vk.n、最優(yōu)指標函數(shù)fk(sk)及k階段指標Vk(sk,us)的含義。5 正確列出最優(yōu)指標函數(shù)的遞推關(guān)系及邊界條件。2、資源分配問題資源分配問題 所謂分配問題，就是將數(shù)量一定的一種或若干種資源（例如原材料，資金，機器設(shè)備，勞力，食品等等），恰當?shù)胤峙浣o若干個使用者，使效益函數(shù)為最優(yōu)。資源分配離散連續(xù)(1)資源離散分配問題資源離

2、散分配問題 多元投資分配問題 設(shè)有某種原料，總數(shù)量為a，用于生產(chǎn)n種產(chǎn)品。若分配數(shù)量xi用于生產(chǎn)第i種產(chǎn)品，其收益為gi(xi),問應(yīng)如何分配，才能使生產(chǎn)n種產(chǎn)品的總收入最大？nixaxxxtsxgxgxgMaxZinnn,2, 10.212211靜態(tài)規(guī)劃建立動態(tài)規(guī)劃模型1、決策變量dk表示分配給生產(chǎn)第k種產(chǎn)品的原料數(shù)量，dk=xk；2、設(shè)狀態(tài)變量sk表示為分配給用于生產(chǎn)第k種產(chǎn)品至第n種產(chǎn)品的原料數(shù)量；3、狀態(tài)轉(zhuǎn)移方程： sk+1=sk-uk=sk-xk4、決策集合：Dk(sk)=uk|0uk=xksk5、最優(yōu)值函數(shù)fk(sk)表示以數(shù)量為sk的原料分配給第k種產(chǎn)品至第n種產(chǎn)品所得到的最大總

3、收益，動態(tài)規(guī)劃的遞推關(guān)系為：)(max)(1 , 1)()(max)(10nnsxnnkkkkksxkkxgsfnkxsfxgsfnnkk 例1：某公司有資金10萬元，若投資于項目i（i=1，2，3）的投資額為xi時，其效益分別為 23332221112)(,9)(,4)(xxgxxgxxg問如何分配投資數(shù)額才能使總效益最大解：可列出靜態(tài)規(guī)劃問題的模型如下)3,2,1(,010.294max3212321ixxxxtsxxxZi應(yīng)用動態(tài)規(guī)劃求解： 1、分階段：考慮效益函數(shù)的形式，分為三個階段，即k=1，2，3。2、確定決策變量dk：通常可以取靜態(tài)規(guī)劃中的變量為決策變量，即決 定給第 k個項目投

4、資的資金數(shù)。 確定狀態(tài)變量S k：狀態(tài)變量與決策變量有密切關(guān)系，狀態(tài)變量一般為累計量或隨遞推過程變化的量。既第k階段可以投資于第k項到第3項目的資金數(shù)量。應(yīng)用動態(tài)規(guī)劃求解： 1、分階段：考慮效益函數(shù)的形式，分為三個階段，k=1，2，32、確定決策變量dk：通常可以取靜態(tài)規(guī)劃中的變量為決策變量，即決定給第 k個項目投資的資金數(shù)。3、 確定狀態(tài)變量sk：狀態(tài)變量與決策變量有密切關(guān)系，狀態(tài)變量一般為累計量或隨遞推過程變化的量。既第k階段可以投資于第k項到最后項（第3項目）的資金數(shù)量。4、狀態(tài)轉(zhuǎn)移方程：Sk+1=sk-xk33221122311210,0,0,10sxsxsxxssxsss5、 指標函

5、數(shù)33,)(kiiikxgV6、最優(yōu)指標函數(shù)fk(sk)：當可投資金額為sk時，投資第k項到第3項所得的最大收益數(shù)?；痉匠虨椋?)(1 , 2 , 3)()(max)(44110sfksfxgsfkkkksxkkkk解算：1、當階段k=3時，有23333*3230332)(,2max)(33ssfsxxsfsx最優(yōu)決策為：最優(yōu)目標函數(shù)：當階段k=2時，有)(29max29max)(9max)(222202320332022222222xsxsxsfxsfsxsxsx是凹函數(shù)，最大值點只能在0，s2端點上取得，即2*22222*222222222222222)()0(290),()0(29)(

6、)0(299)(;2)0(sxsffsxsffssffsssfsf當當當時，時，時，此時此時2階導(dǎo)數(shù)大于0當階段k=1時，有)(4max)(22101111sfxsfsx2910, 0959max994max)10(112*1111100111100111xssxsxsxsxfxx040)10(10200)10(0)(24max)10(*11111211110011xfxfxxsxfx2229)(ssf22222)(ssf當當時時矛盾，舍去。是凹函數(shù)，故比較0,10的端點（最優(yōu)決策）2階導(dǎo)數(shù)0S29/21010,029103*3*223*2*112sxxssxxss因為所以最優(yōu)投資方案是全部資

7、金投于第3個項目，可得最大收益200萬元。 例2 某大型公司擬將某種高效率的設(shè)備5臺分配給所屬的甲、乙、丙三個工廠，各工廠若獲得這種設(shè)備之后，可以為公司提供的盈利如表。問這五臺設(shè)備如何分配給各工廠，才能使公司得到的盈利最大。 工 廠 盈 利設(shè) 備 臺 數(shù)甲 乙丙 0 1 2 3 4 5037912130510111111046111212解：將問題按工廠分為三個階段，甲、乙、丙分別編號為1，2，3。用k表示，即階段變量決策變量dk表示分配給第k個工廠的設(shè)備臺數(shù)，即dk=xk；設(shè)狀態(tài)變量sk表示為分配給第k個工廠至第3工廠的設(shè)備臺數(shù)；狀態(tài)轉(zhuǎn)移方程： sk+1=sk-uk=sk-xk決策集合：Dk

8、(sk)=dk|0dk=xksk最優(yōu)值函數(shù)fk(sk)表示以數(shù)量為sk的設(shè)備臺數(shù)分配給第k個工廠至第n個工廠所得到的最大總收益，動態(tài)規(guī)劃的遞推關(guān)系為：0)(1 , 2 , 3)()(max)(4410sfkxsfxgsfkkkkksxkkkk當階段k=3時，0s35， 0 x3s3，有0)(4433033max33sfxgsfsx0) 0(0) 0()()(max) 0(0*33443303333xgsfxgfssx1) 1 (4) 1 ()0(max)()(max) 1 (1*3331 ,04433033333xggsfxgfsxsxx3(s3)2)2(6)2() 1 ()0(max)()(

9、max)2(2*33332, 1 ,04433033333xgggsfxgfsxsx3)3(11)3()2() 1 ()0(max)()(max)3(3*333333 ,2, 1 ,04433033333xggggsfxgfsxsx4)4(12)4()3()2() 1 ()0(max)()(max)4(4*3333334, 3 ,2, 1 ,04433033333xgggggsfxgfsxsx5)5(12)5()4()3()2() 1 ()0(max)()(max)5(5*33333335 ,4, 3 ,2, 1 ,04433033333xggggggsfxgfsxsxg3(x3) x3s30

10、12345f3(s3)x*3012345046111212046111212012345結(jié)果列于下表：當階段k=2時， s3=s2-x2， 0s25， 0 x2s2，有0) 0(0) 0()()(max) 0(0*22332202222xgsfxgfssx1) 1 (50540max)0() 1 () 1 ()0(max)()(max) 1 (1*21 ,032321 ,033220222222xfgfgsfxgfsxxsx2)2(100104560max)0()2() 1 () 1 ()2()0(max)()(max)2(2*22 , 1 , 03232322 , 1 , 033220222

11、222xfgfgfgsfxgfsxxsx2)3(1401141065110max)0()3() 1 ()2()2() 1 ()3()0(max)()(max)3(3*23 , 2, 1 , 0323232323 , 2, 1 , 033220222222xfgfgfgfgsfxgfsxxsx2 , 1)4(16011411610115120max)0()4() 1 ()3()2()2()3() 1 ()4()0(max)()(max)4(4*24, 3 , 2, 1 , 032323232324, 3 , 2, 1 , 033220222222xfgfgfgfgfgsfxgfsxxsx2)5(

12、210114116111110125120max) 1 ()4() 1 ()4()2()3()3()2()4() 1 ()5()0(max)()(max)5(5*25 ,4, 3 ,2, 1 ,03232323232325 ,4, 3 ,2, 1 ,033220222222xfgfgfgfgfgfgsfxgfsxxsxg2(x2)+f3(s2-x2) x2s2012345f2(s2) x*201234500+40+60+110+120+125+05+45+65+115+1210+010+410+610+1111+011+411+611+011+4 11+0051014162101221,22結(jié)

13、果列于下表：當階段k=1時， s2=s1-x1， s1=5， 0 x1s1，有2 , 0)5(,21013512109147163210max)0()5() 1 ()4()2()3()3()2()4() 1 ()5()0(max)()(max)()(max)(5*1212121212121112115 ,4, 3 ,2, 1 ,0,22110111111xfgfgfgfgfgfgxsfxgsfxgsfsxsxg1(x1)+f2(s1-x1) x1s1012345f1(s1) x*150+213+167+149+1012+5 13+0210,2結(jié)果可寫成表格的形式 然后按計算表格的順序反推，可知

14、最優(yōu)分配方案有兩個： 由于x1*=0，根據(jù)s2=s1-x1*=5-0=5，查表知x2*=2，由s3=s2-x2*=5-2=3，故x3*=s3=3。即得甲工廠分配0臺，乙工廠分配2臺，丙工廠分配3臺。 由于x1*=2，根據(jù)s2=s1-x1*=5-2=3，查表知x2*=2，由s3=s2-x2*=3-2=1，故x3*=s3=1。即得甲工廠分配2臺，乙工廠分配2臺，丙工廠分配1臺。 以上兩個分配方案所得到的總盈利均為21萬元。問題：如果原設(shè)備臺數(shù)是4臺，求最優(yōu)分配方案？ 如果原設(shè)備臺數(shù)是3臺，求最優(yōu)分配方案？（2）資源連續(xù)分配問題一般問題的提法是：資源數(shù)量s1 A種生產(chǎn)數(shù)量u1投入收益g(u1)年終資

15、源回收率a B種生產(chǎn)數(shù)量s1-u1收益h(s1-u1)年終資源回收率b第一年資源數(shù)量s2=au1+b(s1-u1)第二年 A種生產(chǎn)數(shù)量u2投入;收益g(u2);年終資源回收率a B種生產(chǎn)數(shù)量s2-u2;收益h(s2-u2);年終資源回收率b到n年如此進行n年，如何確定投入A的資源量u1、un，使總收入最大？此問題的靜態(tài)規(guī)劃問題模型為：nisuusbaususbaususbaustsushugZiinnnnniiii,2, 1,0)()()(.)()(max1222311121。 設(shè)sk為狀態(tài)變量，它表示在第k階段（第k年）可投入A、B兩種生產(chǎn)的資源量；uk為決策變量，它表示在第k階段（第k年）

16、用于A生產(chǎn)的資源量，則sk-uk表示用于B生產(chǎn)的資源量；狀態(tài)轉(zhuǎn)移方程為：sk+1=auk+b(sk-uk)最優(yōu)值函數(shù)fk(sk)表示有資源量sk從第 k階段至第n階段采取最優(yōu)分配方案進行生產(chǎn)后所得到的最大總收入。動態(tài)規(guī)劃的逆推關(guān)系方程為：1 , 2 , 1)()()(max)()()(max)(100nkusbaufushugsfushugsfkkkkkkksukknnnsunnnnnn最后求得的f1(s1)即為所求問題的最大收入例3 機器負荷分配問題 某種機器可在高低兩種不同負荷下進行生產(chǎn)，設(shè)機器在高負荷情況下的產(chǎn)量函數(shù)為g=8u1，其中u1是投入生產(chǎn)的機器數(shù)量，年完好率為 a=0.7，在低

17、負荷情況下的產(chǎn)量函數(shù)為h=5y，其中y是投入生產(chǎn)的機器數(shù)量，年完好率為b=0.9。假定開始生產(chǎn)時完好機器的數(shù)量為1000臺，試問每年如何安排機器在高低兩種負荷下的生產(chǎn)，可使5年內(nèi)生產(chǎn)的產(chǎn)品總產(chǎn)量最高。 5 , 2 , 1),( 9 . 07 . 0)(1kusuusbauskkkkkkk 允許決策集合0uksk解： 設(shè)階段階段數(shù)k表示年度。 狀態(tài)變量狀態(tài)變量sk為第k年度初擁有的完好機器臺數(shù)。 決策變量決策變量uk為第k年度中分配高負荷下生產(chǎn)的機器臺數(shù)。故低負荷下生產(chǎn)的機器臺數(shù)是sk-uk。 狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程 第k年度產(chǎn)量為)(58),(kkkkkkusuusv 指標函數(shù)為515 ,

18、1),(kkkkusvV 遞推方程為1 , 2 , 5)( 9 . 07 . 0()( 58max)(0)(1066kusufususfsfkkkkkkksukkkk5555*5550665550558)(,)53max)()(58max)(55555ssfsususfususfksusu當時4444*4440444044454440446 .13)(,2 .124 . 1max)(2 .126 .13max)(9 . 07 . 0()( 58max)(4444444ssfsusuusuusufususfksususu當時依次類推可得，111*1222*23333*37 .23)(08 .20

19、)(05 .17)(ssfussfussfsu相應(yīng)的相應(yīng)的相應(yīng)的 因為S1=1000，所以f1(s1)=23700因此最優(yōu)策略為5*54*43*3*2*1, 0, 0sususuuu即前兩年應(yīng)在年初把全部完好的機器投入低負荷生產(chǎn)，后三年應(yīng)在年初把全部完好的機器投入高負荷生產(chǎn)。最高產(chǎn)量為23700（臺）。每年年初的機器狀態(tài)：S1=1000S2=0.7u1+0.9(s1-u1)=0.9s1=900S3= 0.7u2+0.9(s2-u2)=0.9s2=810S4= 0.7u3+0.9(s3-u3)=0.7s3=567S5= 0.7u4+0.9(s4-u4)=0.7s4=397S6= 0.7u5+0.

20、9(s5-u5)=0.7s5=278練習(xí)：每年年初的完好機器數(shù)。作業(yè)：如規(guī)定在第五年結(jié)束時完好機器數(shù)為500臺，該如何安排生產(chǎn)？3、生產(chǎn)與存貯問題、生產(chǎn)與存貯問題 所謂生產(chǎn)與庫存問題就是一個生產(chǎn)部門，如何在已知生產(chǎn)成本、庫存費用和各階段市場需求條件下，決定各階段產(chǎn)量，使計劃內(nèi)的費用總和為最小的問題。很多問題可以化成此類問題來解決。 生產(chǎn)與庫存問題本身就是一個多階段決策過程。設(shè)某一生產(chǎn)部門，生產(chǎn)周期分為n個階段，已知最初庫存量為x1，階段市場的需求為dk，生產(chǎn)的固定成本為K，單位產(chǎn)品的消耗費用為L，單位產(chǎn)品的階段庫存費用為h，倉庫容量為M，階段最大生產(chǎn)能力為B。問如何安排各階段產(chǎn)量，使計劃周期內(nèi)

21、的費用總和最小。狀態(tài)變量xk選為階段k的初始庫存量，x1已知，xn+1=0。 階段k的庫存量即不能超過庫存容量M，也不能超過階段k至階段n的需求總量(因為n+1階段的庫存量為0），即nkdddMxnkkk, 2 , 1,min01 決策變量uk選為階段k的產(chǎn)量。階段產(chǎn)量必須不超過生產(chǎn)能力和第k階段到第n階段的總需求減去第k階段初的庫存量，同時要大于該階段的需求和庫存量之差，即,min1knkkkkkxdddBuxd 狀態(tài)轉(zhuǎn)移方程為kkkkduxx1 階段效益為階段生產(chǎn)費用和庫存費用之和，即)(),(kkkkkkkduxhLuKuxg階段k的生產(chǎn)費用k階段末的庫存費用 動態(tài)規(guī)劃基本方程)()(m

22、in)(11)(kkkkkkxDukkxfduxhLuKxfkkk 例 已知n=3，K=8，L=2，h=2，x1=1，M=4，x4=0（計劃周期末期的庫存量為0），B=6，d1=3，d2=4，d3=3，求解生產(chǎn)與庫存問題。 解：利用上述的遞推方程得0) 3 (, 8) 3 (31) 2(,10) 2(22) 1 (,12) 1 (13) 0(,14) 0(03,min,min0214)3 ( 2828min)(3*333*333*333*33333333 , 6min33333ufxufxufxufxdMdMxxxuxfknkiikxuxk若若若若則則則則當時x4=x3+u3-d3=0 u3

23、x30123f3(x3)u*3(x3)01414311212221010138807 , 6min,min44,min022232223222223xxddBuxMddMxduxxk當時3) 1 (288620104181221614014min)3()3(228min) 1 (14)0(30104201221814016min)4()4(228min)0(047 ,min,min0)4()4(228min)()(228min)(*223226, 5 ,4, 322*223226, 5 ,4223222232227,6min43322227,6min42222222222uufuufxuufu

24、ufxMdMxuxfuxuxfduxuxfuuiixuxxux若若則則1) 3(248616104141221214010min)1() 1(228min) 3(32)2(268618104161221414012min)2()2(228min)2(2*223224 , 3 , 2 , 122*223225 , 4 , 3 , 22222uufuufxuufuufxuu0) 4(22861410412122101408min)(2)28(min) 4(4*223223 , 2 , 1 , 0222uufuufxu u2 x20123456f2(x2) u*2(x2)016+0+14 18+2+

25、12 20+4+10304114+0+14 16+2+12 18+4+10 20+6+8283212+0+14 14+2+12 16+4+10 18+6+8262310+0+14 12+2+12 14+4+10 16+6+824148+0+14 10+2+12 12+4+10 14+6+8220結(jié)果見下表：2) 1 (422282024618264162821430012min)2()2(228min)()(228min) 1 (62, 211*112116 , 5 , 4 , 3 , 22211116 , 5 , 4 , 3 , 21112111uufuuxfduxufuuxxkuu時是唯一

26、確定的，因此 u1 x123456f1(x1) u*1(x1)112+0+30 14+2+28 16+4+26 18+6+24 20+8+22422最優(yōu)決策為最優(yōu)路線為 1，0，0，0最優(yōu)目標函數(shù)值為42。3)0(, 4)0(, 2) 1 (*3*2*1uuux2=u1-2=0 x3=x2+u2-d2=0+4-4=04、設(shè)備更新問題設(shè)備更新問題 個人、單位等隨時均有設(shè)備更新問題。自行車、彩電、設(shè)備隨著使用年限的增加而設(shè)備陳舊，處理價格愈低，因此需要維修和更新的費用增加。處于各種階段的設(shè)備總是面臨保留還是更新問題。保留還是更新，應(yīng)該從整個計劃期間的總回收額來考慮，而不能從局部的某個階段的回收額來

27、考慮，是一個多階段的決策問題。設(shè)備更新問題提法如下（以一臺機器為例）： n為計劃設(shè)備使用年數(shù)。 Ik(t) 為第k年（階段）已經(jīng)使用過t年的機器再使用一年所得的收入。 Ok(t) 為第k年已經(jīng)使用過t年的機器再使用一年的維修費用 。 Ck(t) 為第k年賣掉一臺已經(jīng)使用過t年的機器，買進一臺新設(shè)備的更新凈費用。為折扣因子，表示一年以后收入是上一年的單位。要求在n年內(nèi)的每年年初作出決策，是繼續(xù)使用舊設(shè)備還是更換一臺新的，使n年內(nèi)總效益最大？建立動態(tài)規(guī)劃模型如下：階段k（k=1，2，n）表示計劃使用該設(shè)備的年限數(shù)。狀態(tài)變量sk：第k年初，設(shè)備已使用過的年數(shù)。決策變量xk：是第k年初更新（Repla

28、cement），還是保留使用（Keep）舊設(shè)備，分別用K，R表示。狀態(tài)轉(zhuǎn)移方程為： RxKxsskkkk111 階段效益為：RxKxscOIsOsIxsvkkkjjjkjkjkkj)() 0() 0()()(),(最優(yōu)指標函數(shù)fk(sk)：表示第k年初，使用一臺已用了sk年的設(shè)備，到第n年末的最大收益，動態(tài)規(guī)劃的基本方程為0)()(),(max)(1111nnkkkkjRorKxkksfsfxsvsfk實際上RxKxfscOIsfsOsIsfkkkkkkkkkkkkkkk) 1 ()() 0 () 0 () 1()()(max)(11 役齡項目012345效益 Ik(t)54.543.7532

29、.5運行費Ok(t)0.511.522.53更新費ck(t)0.51.52.22.533.5（單位：萬元）例：設(shè)某臺新設(shè)備的年效益及年均維修費用、更新凈費用如下表，試確定今后五年內(nèi)的更新策略，使總效益最大。（設(shè)=1）解：n=5RxKxscOIsOsIsfk555555555555)() 0() 0()()(max)(5狀態(tài)變量s5可取1，2，3，4KxRxKxcOIOIf) 1 (5 . 35 . 15 . 0515 . 4max) 1 () 0() 0() 1 () 1 (max) 1 (555555555KxRxKxcOIOIf) 2(5 . 22 . 25 . 055 . 10 . 4m

30、ax) 2() 0() 0() 2() 2(max) 2(555555555RxRxKxcOIOIf) 3(25 . 25 . 05275. 3max) 3()0()0() 3() 3(max) 3(555555555賣掉役齡2年的設(shè)備，買入新設(shè)備的更新費用RxRxKxcOIOIf)4(5 . 135 . 055 . 23max)4()0()0()4()4(max)4(555555555RxKxfscOIsfsOsIsfk445444445444444) 1 ()() 0() 0() 1()()(max)(4狀態(tài)變量s4可取1，2，3RxRxKxfscOIsfsOsIfs) 1 (5 . 65

31、 . 35 . 15 . 055 . 215 . 4max) 1 ()() 0() 0() 1()()(max) 1 (44454444454444144RxRxKxfscOIsfsOsIfs) 2(8 . 55 . 32 . 25 . 0525 . 14max) 1 ()() 0() 0() 1()()(max) 2(44454444454444244RxRxKxfscOIsfsOsIfs) 3 (5 . 55 . 35 . 25 . 055 . 1275. 3max) 1 ()() 0() 0() 1()()(max) 3 (44454444454444344RxKxfscOIsfsOsI

32、sfk334333334333333) 1 ()() 0() 0() 1()()(max)(3此時s3可取1或2RxRxKxfscOIsfsOsIfs) 1 (5 . 95 . 65 . 15 . 058 . 515 . 4max) 1 ()() 0() 0() 1()()(max) 1 (33343333343333133RxRxKxfscOIsfsOsIfs) 2(8 . 85 . 62 . 25 . 055 . 55 . 14max) 1 ()() 0() 0() 1()()(max) 2(33343333343333233RxKxfscOIsfsOsIsfk22322222322222

33、2) 1 ()() 0() 0() 1()()(max)(2由于狀態(tài)s2只能取1，所以有RxRxKxfscOIsfsOsIfs) 1 (5 .125 . 95 . 15 . 058 . 815 . 4max) 1 ()() 0() 0() 1()()(max) 1 (22232222232222122RxKxfscOIsfsOsIsfk112111112111111) 1 ()() 0() 0() 1()()(max)(1由于狀態(tài)s1只能取0，所以有KxRxKxfscOIsfsOsIfs) 0(175 .125 . 05 . 055 .125 . 05max) 1 ()() 0() 0() 1

34、()()(max) 0(11121111121111011上述過程遞推回去，當x*1(0)=K，由狀態(tài)轉(zhuǎn)移方程本例的最優(yōu)策略是K，R，R，R，K，即第一年初購買的設(shè)備到第二、三、四年初各更換一次，用到第五年年末，總效益為17萬元。RxKxss111211s2=1，查f2(1)得x*2=Rs3=1，查f3(1)得x*3=Rs4=1，查f4(1)得x*4=Rs5=1，查f5(1)得x*5=KRxKxss222311 5、動態(tài)規(guī)劃總結(jié) 一、動態(tài)規(guī)劃基本概念： 1 階段：將所給問題的過程，按時間或空間特征分 解成若干互相聯(lián)系的階段，用k表示， 2 狀態(tài)：各階段開始時的客觀條件。 狀態(tài)變量用sk表示。

35、狀態(tài)變量集合用Sk表示。 狀態(tài)性質(zhì)：當某階段狀態(tài)給定以后，在這階段以 后的過成的發(fā)展不受這段以前各狀態(tài) 的影響。3 決策：當各階段的狀態(tài)確定以后，可以作出不同的選擇，從 而確定下一階段的狀態(tài)。這個選擇稱為決策。 決策變量:dk(sk) 允許決策集合：決策變量的取值范圍，用DK(SK)表示4 策略：各階段決策確定后，整個問題的決策序列就構(gòu)成一 個策略。P1.nd1(s1),d2(s2),dn(sn). 允許策略集合：可供選擇的策略范圍。P1.n5 狀態(tài)轉(zhuǎn)移方程：由k階段到k+1段的狀態(tài)轉(zhuǎn)移規(guī)律。 Sk+1=Tk(sk,uk) 6 指標函數(shù)：用于衡量所選定策略優(yōu)劣的數(shù)量指標。 V1.n(s1,p1

36、.n)表示初始狀態(tài)為S1，采用策略p1.n 時原過程的指標函數(shù)值。7 最優(yōu)指標函數(shù)：從第k階段狀態(tài)Sk，采用最優(yōu)策略pk.n 到過 程終止時的最佳效益值。 fk(sk)=Vk.n(sk,pk.n ) =opt Vk.n(sk,pk.n ) 二、動態(tài)規(guī)劃基本原理Bellmen 最優(yōu)化原理：一個過程的最優(yōu)策略具有這樣的性質(zhì)：無論初始狀態(tài)及初始決策如何，對于先前決策所形成的狀態(tài)而言，其以后的所有決策應(yīng)構(gòu)成最優(yōu)決策，三、動態(tài)規(guī)劃的基本思想 （1）劃分階段，選取變量，定義最優(yōu)指標函數(shù)。 （2）從邊界條件開始，逆過成行進方向逐段遞推尋優(yōu)。 （3）把當前效益和未來各段分開，又把當前效益與未來效 益結(jié)合起來考

37、慮。 四、動態(tài)規(guī)劃的 基本解法 1 逆序解法：適用于初始狀態(tài)給定的情況。 2 順序解法：適用于終止狀態(tài)給定的情況。五、動態(tài)規(guī)劃基本方程0)(1 , 2, 1,)(),()(1111nnkkkkkkksfnnksfsvoptsf六、動態(tài)規(guī)劃模型的建立要點1 劃分滿足遞推關(guān)系的若干階段2 正確選擇狀態(tài)變量、決策變量（可知性和無后效性）3 正確寫出狀態(tài)轉(zhuǎn)移方程 Sk+1=Tk(sk,uk)4 確定指標函數(shù)Vk n,5 列出基本方程最優(yōu)指標函數(shù)fk(sk)，確定邊界條件。 七、幾個典型示例動態(tài)規(guī)劃模型的建立最短路問題階段k：整體路線上的段數(shù)狀態(tài)變量sk：每一段上的中轉(zhuǎn)站決策變量uk：從某一段上某一狀態(tài)

38、到下一階段各中轉(zhuǎn)站的決定狀態(tài)轉(zhuǎn)移方程：Sk+1=uk(sk)指標函數(shù)：V k.n是第k階段到終點的距離基本方程： 0)() 1 , 2 , 1,)(),(min)(1111nnkkkkkkksfnnksfusdsf資源分配問題階段k：投資項目數(shù)狀態(tài)變量sk：第k段可以投資于第k項到第n個項目的資金數(shù)決策變量xk：決定給第k個項目投資的資金數(shù)狀態(tài)轉(zhuǎn)移方程：sk+1=sk-xk指標函數(shù)：最優(yōu)值函數(shù)fk(sk):表示以數(shù)量為sk的原料分配給第k種產(chǎn)品至第n種產(chǎn)品所得到的最大總收益?；痉匠蹋?)(max)(1 , 1)()(max)(10nnsxnnkkkkksxkkxgsfnkxsfxgsfnnkk)(nkiiinkxgV生產(chǎn)與存儲問題階段k：每個月為一個階段狀態(tài)變量xk：第k個月初的庫存量決策變量uk：第k個月的生產(chǎn)量狀態(tài)轉(zhuǎn)移方程：階段效益為階段生產(chǎn)費用和庫存費用之和，即 kkkkduxx1)(),(kkkkkkkduxhLuKuxg基本方程：)()(min)(11)(kkkkkk