第13講 確定型動態(tài)規(guī)劃

1、運籌學運籌學 第八、九章第八、九章 動態(tài)規(guī)劃動態(tài)規(guī)劃第八章 動態(tài)規(guī)劃1建立動態(tài)規(guī)劃模型的步驟建立動態(tài)規(guī)劃模型的步驟 1 1、劃分階段、劃分階段劃分階段是運用動態(tài)規(guī)劃求解多階段決策問題的第一劃分階段是運用動態(tài)規(guī)劃求解多階段決策問題的第一步，在確定多階段特性后，按時間或空間先后順序，步，在確定多階段特性后，按時間或空間先后順序，將過程劃分為若干相互聯系的階段。對于靜態(tài)問題要將過程劃分為若干相互聯系的階段。對于靜態(tài)問題要人為地賦予人為地賦予“時間時間”概念，以便劃分階段。概念，以便劃分階段。 2 2、正確選擇狀態(tài)變量、正確選擇狀態(tài)變量Sk選擇變量既要能確切描述過程演變又要滿足無后效性，選擇變量既要能

2、確切描述過程演變又要滿足無后效性，而且各階段狀態(tài)變量的取值能夠確定。一般地，狀態(tài)而且各階段狀態(tài)變量的取值能夠確定。一般地，狀態(tài)變量的選擇是從過程演變的特點中尋找。變量的選擇是從過程演變的特點中尋找。 3 3、確定決策變量、確定決策變量Uk及允許決策集合及允許決策集合Dk通常選擇所求解問題的關鍵變量作為決策變量，同時通常選擇所求解問題的關鍵變量作為決策變量，同時要給出決策變量的取值范圍，即確定允許決策集合。要給出決策變量的取值范圍，即確定允許決策集合。運籌學運籌學 第八、九章第八、九章 動態(tài)規(guī)劃動態(tài)規(guī)劃第八章 動態(tài)規(guī)劃2 4 4、確定狀態(tài)轉移方程、確定狀態(tài)轉移方程Sk+1=Tk(Sk,Uk) 根

3、據根據k 階段狀態(tài)變量和決策變量，寫出階段狀態(tài)變量和決策變量，寫出k+1階段狀態(tài)變量，階段狀態(tài)變量，狀態(tài)轉移方程應當具有遞推關系。狀態(tài)轉移方程應當具有遞推關系。 5 5、正確寫出指標函數、正確寫出指標函數V Vk,n的關系，它應滿足下面三個的關系，它應滿足下面三個性質：性質：V Vk,n是定義在全過程和所有后部子過程上的數量函數是定義在全過程和所有后部子過程上的數量函數具有可分離性，并滿足遞推關系，即具有可分離性，并滿足遞推關系，即Vk,n(Sk,Uk ,Sk1,Sn+1)=k(Sk,Uk ,Vk1,n(Sk1,Uk1,Sn+1)函數函數k（Sk，Uk ，Vk1,n）對于變量對于變量Vk1,n

4、要嚴格單調。要嚴格單調。6 6、恰當地定義最優(yōu)指標函數、恰當地定義最優(yōu)指標函數 階段指標函數是指第階段指標函數是指第k 階段的收益，最優(yōu)指標函數是階段的收益，最優(yōu)指標函數是指從第指從第k 階段狀態(tài)出發(fā)到第階段狀態(tài)出發(fā)到第n 階段末所獲得收益的最優(yōu)值。階段末所獲得收益的最優(yōu)值。 運籌學運籌學 第八、九章第八、九章 動態(tài)規(guī)劃動態(tài)規(guī)劃第八章 動態(tài)規(guī)劃3 動態(tài)規(guī)劃模型分類 過程過程變量變量確定確定隨機隨機離散離散連續(xù)連續(xù)離散確定型離散確定型離散隨機型離散隨機型連續(xù)確定型連續(xù)確定型連續(xù)隨機型連續(xù)隨機型7、寫出恰當的邊界條件、寫出恰當的邊界條件 ，從邊界條件開始，逐段遞推尋優(yōu)，在每一個子問題的求解中，均用

5、了它前面的子問題的最優(yōu)化結果，依次進行，最后一個子問題所得的最優(yōu)結果，就是這個問題的最優(yōu)解，并找到相應的最優(yōu)策略最優(yōu)策略。第第6章章 動態(tài)規(guī)劃動態(tài)規(guī)劃動態(tài)規(guī)劃的基本理論動態(tài)規(guī)劃的基本理論 （2學時）學時）確定型動態(tài)規(guī)劃確定型動態(tài)規(guī)劃 （2學時）學時）隨機型動態(tài)規(guī)劃隨機型動態(tài)規(guī)劃 （1學時）學時） 動態(tài)規(guī)劃的軟件計算動態(tài)規(guī)劃的軟件計算 （1學時）學時）第14講 確定型性動態(tài)規(guī)劃 (6.2)最短路問題最短路問題資源分配問題資源分配問題生產與存儲問題生產與存儲問題動態(tài)規(guī)劃和靜態(tài)規(guī)劃的關系動態(tài)規(guī)劃和靜態(tài)規(guī)劃的關系自學背包問題、排序問題、貨郎擔問題自學背包問題、排序問題、貨郎擔問題 資源分配問題：資源分

6、配問題：把有限的資源把有限的資源( (如資金、材料、設備、人力等如資金、材料、設備、人力等) )分分配給若干使用者，而使某一指標為最優(yōu)的問題即配給若干使用者，而使某一指標為最優(yōu)的問題即為資源分配問題。為資源分配問題。資源可以有一種或若干種，資源可以有一種或若干種，只有一種資源可供分配的問題稱之為一維資源分只有一種資源可供分配的問題稱之為一維資源分配問題。配問題。資源分配問題 (6.2.2)例例1：某工業(yè)部門按國家計劃的安排，擬將某高效率某工業(yè)部門按國家計劃的安排，擬將某高效率的設備五臺，分配給所屬的甲、乙、丙三個工廠，各工的設備五臺，分配給所屬的甲、乙、丙三個工廠，各工廠若獲得這種設備之后，可

7、以為國家提供的盈利如下表廠若獲得這種設備之后，可以為國家提供的盈利如下表所示。問：這五臺設備如何分配給各工廠，才能使國家所示。問：這五臺設備如何分配給各工廠，才能使國家得到的盈利最大。得到的盈利最大。1、一維資源分配問題、一維資源分配問題 動態(tài)規(guī)劃的數學模型動態(tài)規(guī)劃的數學模型將三個分廠看作是三個階段，即階段變量將三個分廠看作是三個階段，即階段變量 k=1,2,3k=1,2,3; ;狀態(tài)變量狀態(tài)變量s sk k 表示表示第第k k 階段初可分配的設備臺數階段初可分配的設備臺數, ,0s0sk k 55; ;決策變量決策變量x xk k 表示表示第第k k 階段分配給分廠階段分配給分廠k k 的設

8、備臺數，的設備臺數， 允許決策集合允許決策集合X Xk k ( (s sk k)= )= x xk k 00 x xk k ssk k;狀態(tài)轉移方程為狀態(tài)轉移方程為 s sk+1k+1 = = s sk k - - x xk k ; ;階段指標階段指標P Pk k( (s sk k, , x xk k) ) 表示第表示第k k 階段從階段從s sk k臺設備中分配給臺設備中分配給k k 分廠分廠x xk k 臺設備的階段效益臺設備的階段效益; ; 最優(yōu)指數函數最優(yōu)指數函數f fk k( (s sk k) )表示第表示第k k階段從階段從s sk k 開始到最后階段采開始到最后階段采用最優(yōu)分配策

9、略取得的最大的效益值用最優(yōu)分配策略取得的最大的效益值; ;遞推方程函數式遞推方程函數式 0)()(),()(4411)(maxsfsfxsPsfkkkkkSXxkkkkk邊界條件：基本方程：第三階段第三階段：設將S3臺設備（S30,1,2,3,4,5）全部分配給丙廠時，最大盈利值為： f3(S3)maxP3(X3) 其中X3S30,1,2,3,4,5 X3*表示使得表示使得f3(S3)為最大值時的最優(yōu)決策。為最大值時的最優(yōu)決策。X3S3 P3(X3) f3(S3) X3* 01234500 0014 4126 62311 113412 124512125逆序求解逆序求解表表91第二階段第二階段

10、：設將設將S2臺設備（臺設備（S20,1,2,3,4,5）分配給乙廠和）分配給乙廠和丙廠時，對每一個丙廠時，對每一個S2值，都有一種最優(yōu)分配方案，使得最大盈值，都有一種最優(yōu)分配方案，使得最大盈利值為：利值為：f2(S2)max P2(X2)+ f3(S2X2) ，X20,1,2,3,4,5X2S2P2(X2)f3(S2X2) f2(S2) X2* 01234500 0010450 5120654100 102301156104110 1424012511106114110 161,250125121011116114110212表表92第一階段第一階段：設將S1臺設備（S15）分配給甲廠、乙廠

11、和丙廠時，則最大盈利值為：f1(S1)max P1(X1)+ f2(5X1) 其中，X10,1,2,3,4,5X1S1P1(X1)f2(5X1) f1(5) X1* 0123455021 316 714 910 125 130210,2按計算表格的順序反推，可知最優(yōu)分配方案有兩個：按計算表格的順序反推，可知最優(yōu)分配方案有兩個：1）由）由X1*0，S2S1X1*505。再由。再由表表92，可知，可知X2*2。S3S2X2*523，故，故X3*S33。即得甲。即得甲廠分得廠分得0臺，乙廠分得臺，乙廠分得2臺，丙廠分得臺，丙廠分得3臺。臺。2）由）由X1*2，S2S1X1*523。再由表。再由表92

12、，可知，可知X2*2。S3S2X2*321，故，故X3*S31。即得甲。即得甲廠分得廠分得2臺，乙廠分得臺，乙廠分得2臺，丙廠分得臺，丙廠分得1臺。臺。以上兩種最優(yōu)方案的總盈利均為以上兩種最優(yōu)方案的總盈利均為21萬元。萬元。 例例2 2 機器負荷問題機器負荷問題某種機器可在高低兩種不同的某種機器可在高低兩種不同的負荷下進行生產，設機器在高負荷下生產的產量函數為負荷下進行生產，設機器在高負荷下生產的產量函數為g=8u1，其中，其中u u1 1為投入生產的機器數量，年完好率為為投入生產的機器數量，年完好率為a=0.7=0.7；在低負荷下生產的產量函數為在低負荷下生產的產量函數為h=5y，其中，其中

13、y y為投入生產的為投入生產的機器數量，年完好率為機器數量，年完好率為b=0.9。假定開始生產時完好的機。假定開始生產時完好的機器數量器數量S S1 110001000臺，試問每年如何安排機器在高低負荷下臺，試問每年如何安排機器在高低負荷下的生產，使在五年內生產的產品總產量最高。的生產，使在五年內生產的產品總產量最高。2、資源連續(xù)分配問題、資源連續(xù)分配問題 動態(tài)規(guī)劃的數學模型動態(tài)規(guī)劃的數學模型每年為一個階段，每年為一個階段，即階段變量即階段變量 k=1,2,3,4,k=1,2,3,4,5;5;狀態(tài)變量狀態(tài)變量s sk k 表示表示第第k k年初所擁有的完好機器臺數，年初所擁有的完好機器臺數，s

14、 s1 1 =1000=1000; ;決策變量決策變量u uk k 表示表示第第k k年投入高負荷生產的機器數年投入高負荷生產的機器數 ， 允許決策集合允許決策集合U Uk k ( (s sk k)= )= u uk k 00 u uk k s sk k; skuk表示為第表示為第k年初分配在低負荷下生產的機器數量。年初分配在低負荷下生產的機器數量。狀態(tài)轉移方程為狀態(tài)轉移方程為 s sk+1k+1 = =au uk k + +b b( (s sk ku uk k ) =) =0.7u0.7uk k+ +0.90.9( (s sk ku uk k) ) = =0.9s0.9sk k 0.2 0.

15、2u uk k; ;階段指標階段指標v vk k( (s sk k, , x xk k) ) 表示表示第第k k年的產量年的產量 ：v vk k( (s sk k, ,u uk k) = ) = 8u8uk k + +5 5( (s sk ku uk k ) )= =5s5sk k + +3u3uk k ; ;最優(yōu)指數函數最優(yōu)指數函數f fk k( (s sk k) )表示第表示第k k階段從階段從s sk k 開始到最后階段采用最優(yōu)開始到最后階段采用最優(yōu)分配策略實現的最大產量分配策略實現的最大產量; ;0)(5 , 4 , 3 , 2 , 1)2 . 09 . 0(35)(),()(6610

16、11)(maxmaxsfkusfussfusvsfkkkkkSukkkkkSUukkkkkkk邊界條件：基本方程：解：解： K=5從第5階段開始，向前逆推計算55)(),()(35maxmax5555066555055usSuSusfusvsff5(s5)是關于是關于u5 的單增函數，故的單增函數，故u*5 =s5 時，時，f5(s5)最大，最大， f5(s5)=8 s5 K=4440444405440554440444.12.12)2.09.0(835835)(),()(maxmaxmaxmax44444444ususussussfusvsfsusususuf4(s4)是關于是關于u4 的單

17、增函數，故的單增函數，故u*4 =s4 時，時， f4(s4)=13.6 s4 K=33303333043304433303328. 024.17)2 . 09 . 0(6 .13356 .1335)(),()(maxmaxmaxmax33333333ususussussfusvsfsusususuf f3 3( (s s3 3) )是關于是關于u u3 3 的單增函數，故的單增函數，故u*3 =s3 時，時， f3(s3)=17.52 s3 K=222022220322033222022504.08 .20)2 .09 .0(52.173552.1735)(),()(maxmaxmaxmax

18、22222222ususussussfusvsfsusususuf2(s2)是關于是關于u2 的的單調減函數單調減函數，故，故u*2 =0 時，時， f2(s2)=20.8 s2依次類推，可求得：u1*0，f1(s1)23.7 s1 最優(yōu)生產策略：u*1 =0 ， u*2 =0 ， u*3 =s3 ，u*4 =s4 ，u*5 =s5 各階段狀態(tài)： s1 =1000， u*1 =0， s2 = 0.9s1 0.2u1 = 0.9s1 =900， u*2=0， s3 = 0.9s2 0.2u2 = 0.9s2 =810， u*3= s3 ， s4 = 0.9s3 0.2u3 = 0.7s3 =57

19、6， u*4= s4 s5 = 0.9s4 0.2u4 = 0.7s4=397 ， u*5= s5 s6 = 0.9s5 0.2u5 = 0.7s5=278即前兩年應把年初全部完好的機器投入低負荷下即前兩年應把年初全部完好的機器投入低負荷下生產，后三年應把年初全部完好的機器投入高負荷生產，后三年應把年初全部完好的機器投入高負荷下生產。這樣最高產量為下生產。這樣最高產量為23700臺。臺。 企業(yè)一年中的產品生產往往是分期分批生產的。企業(yè)一年中的產品生產往往是分期分批生產的。 組織每批產品的生產，都要花費一些生產準備組織每批產品的生產，都要花費一些生產準備費和存貯費用。費和存貯費用。 若某一時期增

20、大生產批量則可減少生產批次，若某一時期增大生產批量則可減少生產批次，從而降低生產成本。從而降低生產成本。 與此同時，批量大了，必然增加庫存而使存與此同時，批量大了，必然增加庫存而使存貯費用增加。貯費用增加。 在企業(yè)產品的生產成本、存貯費用、市場需求在企業(yè)產品的生產成本、存貯費用、市場需求量確定的情況下，正確計劃各時期的生產量，量確定的情況下，正確計劃各時期的生產量，既滿足市場需求，又使總支出最少，這是一個既滿足市場需求，又使總支出最少，這是一個多階段決策問題。多階段決策問題。生產存儲問題 (6.2.3)1、生產計劃問題：、生產計劃問題：例例3 某工廠要對一種產品制訂今后四個時期的生產某工廠要對

21、一種產品制訂今后四個時期的生產計劃，據估計在今后四個時期內，市場對于該產品的計劃，據估計在今后四個時期內，市場對于該產品的需求量如下表所示。假定該廠生產每批產品的固定成需求量如下表所示。假定該廠生產每批產品的固定成本為本為3千元，若不生產就為千元，若不生產就為0，每單位產品成本為，每單位產品成本為1千千元，每個時期生產能力所允許的最大生產批量為不超元，每個時期生產能力所允許的最大生產批量為不超過過6個單位，每個時期末未售出的產品，每單位需付個單位，每個時期末未售出的產品，每單位需付存貨費存貨費0.5千元。還假定在第一個時期的初始庫存量為千元。還假定在第一個時期的初始庫存量為0，第四個時期之末的

22、庫存量也為，第四個時期之末的庫存量也為0。試問：該廠應如。試問：該廠應如何安排各個時期的生產與庫存，才能在滿足市場需求何安排各個時期的生產與庫存，才能在滿足市場需求的條件下，總成本最小。的條件下，總成本最小。 動態(tài)規(guī)劃的數學模型動態(tài)規(guī)劃的數學模型該問題分成四個階段，該問題分成四個階段，k k表示年度，表示年度，k k1 1，2 2，3 3，4 4; ;狀態(tài)變量狀態(tài)變量s sk-1k-1表示為第表示為第k年初的庫存量，第年初的庫存量，第k1年末的年末的庫存量。庫存量。決策變量決策變量u uk k 表示表示為第為第k k年的生產量，年的生產量，d dk k表示為第表示為第k k年的年的需求量。需求

23、量。 允許決策集合允許決策集合D Dk k( (s sk k)= )= u uk k 00 u uk k 66 狀態(tài)轉移方程為狀態(tài)轉移方程為 s sk k = =s sk-1k-1+ +u uk kdk; ;s s0 00; s40 第第k k年的生產成本為：年的生產成本為：66211300)(kkkkkkuuuuuc當，當當解：解：第第k期末庫存量為期末庫存量為sk的存貯費用為的存貯費用為: hk(sk)=0.5 sk總成本為總成本為:ck(uk)hk(sk)fk(sk)表示由第表示由第1年的初始庫存為年的初始庫存為0到第到第k年末的庫存為年末的庫存為Sk的最小總的最小總成本。成本。fk(s

24、k)min ck(uk)hk(sk)fk-1(sk-1) min ck(uk)hk(sk)fk-1(skdkuk) k=1,2,3,4邊界條件邊界條件f0(s0)0寫出寫出順序遞推關系式順序遞推關系式：由于由于庫存量必須非負庫存量必須非負, sk-1 skdkuk , ukskdkuk6 , 所以所以ukmin skdk，6sk 即使以后各期不再生產，須滿足最后的庫存即使以后各期不再生產，須滿足最后的庫存為為0。在。在0和和min ，6- dk 之間取值之間取值nkjjd1nkjjd1f1(s1)min c1(u1)h1(s1) f0(s0)s1 s0 +u1d1 d1=2s10，u12，f1

25、(0)5s11，u13，f1(1)6.5s12，u14，f1(2)842jjd對s1 9 之間的值分別進行計算。k1s13，u15，f1(3)9.5s14，u16，f1(4)11f2(s2)min c2(u2)h2(s2)f1(s2d2u2)k2其中，u2min s23，6s21，f2(1)min c2(u2)h2(1)f1(4u2)5 . 9565 . 65845 . 90min(0)f0(3)C(1)f0(2)C(2)f0(1)C(3)f0(0)Cmin121212125 .1155 . 075 . 65 . 0685 . 055 . 95 . 04115 . 00min(0)f5 . 0

26、(4)C(1)f5 . 0(3)C(2)f5 . 0(2)C(3)f5 . 0(1)C(4)f5 . 0(0)Cmin121212121243jjd對對s2 6 之間的值分別進行計算。之間的值分別進行計算。s20，f2(0)min c2(u2)h2(0)f1(3u2)u2=0 f2(0)9.5 u2=0u2=0f2(1)11.5，u2=0s22，f2(2)min c2(u2)h2(2)f1(5u2) 14，u2=5s23，f2(3)min c2(u2)h2(3)f1(6u2) 15.5，u2=6s24，f2(4)min c2(u2)h2(4)f1(7u2) 17.5，u2=6s25，f2(5)

27、min c2(u2)h2(5)f1(8u2) 19.5，u2=6s26，f2(6)min c2(u2)h2(6)f1(9u2) 21.5，u2=6145 . 955 .114140min(0)f0(2)C(1)f0(1)C(2)f0(0)Cmin232323f3(s3)min c3(u3)h3(s3)f2(s3d3u3)其中，其中，u3min s32，6 s3在在0至至d44之間之間k3s30，f3(0)minc3(u3)h3(0)f2(2u3)u3=0s31，f3(1)min c3(u3)h3(1)f2(3u3) 16 u3=0,3s32，f3(2)min c3(u3)h3(2)f2(4u3

28、) 17.5 u3=4f3(0)14 u3=0； f3(1) 16 u3=0,3； f3(2)17.5 u3=4f3(3)19 u3=55 .20140716065 .170519045 .2000min(0)f0(4)C(1)f0(3)C(2)f0(2)C(3)f0(1)C(4)f0(0)Cmin3434343434所以，所以，u4=0，u3=6，u2=0，u1=5, 最小總成本為最小總成本為20.5千元千元f4(s4)min c4(u4)h4(s4)f3(s4d4u4)其中，其中，u4min s44，6 s40k4f4(0)min c4(u4)h4(0)f3(4u4)u4=0f3(4)20

29、.5 u3=6例例4：某車間需要按月在月底供應一定數量的某種部件給總裝：某車間需要按月在月底供應一定數量的某種部件給總裝車間，由于生產條件的變化，該車間在各月份中生產每單位這種車間，由于生產條件的變化，該車間在各月份中生產每單位這種部件所需耗費的工時不同，各月份的生產量于當月的月底前，全部件所需耗費的工時不同，各月份的生產量于當月的月底前，全部要存入倉庫以備后用。已知總裝車間的各個月份的需求量以及部要存入倉庫以備后用。已知總裝車間的各個月份的需求量以及在加工車間生產該部件每單位數量所需工時數如下表所示。在加工車間生產該部件每單位數量所需工時數如下表所示。設倉庫容量限制為設倉庫容量限制為H=9，

30、開始庫存量為，開始庫存量為2，期終庫存量為，期終庫存量為0，要，要求制定一個半年的逐月生產計劃，既使得滿足需要和庫容量的限求制定一個半年的逐月生產計劃，既使得滿足需要和庫容量的限制，又使得生產這種部件的總耗費工時數為最少。制，又使得生產這種部件的總耗費工時數為最少。月份月份(k)6需求量需求量(dk)0單位工時單位工時(ak)201011181317458532740123動態(tài)規(guī)劃的數學模型動態(tài)規(guī)劃的數學模型 該問題分成六個階段階段，k表示月份，k1,2,3,4,5,6 設sk表示為第k月初的庫存量，第k1月末的庫存量。 uk表示為第k月的生產量，dk表示為第k月的需求量。 狀態(tài)轉移方程：狀態(tài)

31、轉移方程：sk+1skukdk ; dkskH 允許決策集合：允許決策集合：D k(sk) uk : uk 0, dk+1skukdkH s12 s70 fk(Sk)表示在第k月的庫存為sk時，從第k月到第6月所生產部件的最小累計工時數。寫出遞推關系式：遞推關系式：fk(Sk)minak(uk)fk+1(sk1) min ak(uk)fk+1(skukdk) k=0,1,2,3,4,5,6邊界條件邊界條件: f7(S7)0解：解：s7s6u6d6s70，u60 s6d64 f6(s6)0k6s6s5u5d5 s5u511f5(s5)mina5(u5)f6(s6) 10(11s5)11010s5

32、 u5*11 s5k5f4(s4)mina4(u4)f5(s5)min20 u4+11010 (s4u42) = min10 u410 s4130dk+1skukdkH ，dk+1dkskukHdk sk 9s4 u411s4又又uk0 ;max0, 9S4 u411s4f4(s4)10(9s4) 10 s4130=22020 s4 ; u4*9s4k4s5s4u4d4 s4u42s5s4s3u3d3 s3u33s4k3f2(s2)mina2(u2)f3(s3)min13 u2+24417 (s2u25) = min4u217 s23298s2 u214s2又又uk0 max0, 8s2 u2

33、14s2f2(s2)4(14s2) 17 s2329=27313 s2 u2*14s25s3 u312s3;又又uk0 max0, 5s3 u312s3f3(s3)3(12s3) 20 s3280=24417 S3 u3*12s3f3(s3)mina3(u3)f4(s4)min17 u3+22020 (s3 u33) = min3u320 s3280k2s3s2u2d2 ,s2u25s3f1(s1)mina1(u1)f2(s2)min18u1+27313(s1u18) =min5u113 s137713s1 u117s1;又又uk0 max0, 13s1 u117s1f1(S1)5(13s1)

34、 13s1377=44218s1 U1*13s1k1f0(s0)mina0(u0)f1(s1)min11u0+44218u018 s0= min7u018s04428s0 u09s0又又uk0 max0, 8s0 u09S0f0(s0)7(9s0) 18s0442 s0=2，f0(s0)357 u0*9s07k0s2s1u1d1 s1u18s2s1s0u0d0 , s0u0s1u0*7, u1*4，u2*9，u3*3，u4*0，u5*4 最小工時數為最小工時數為357。3 3 動態(tài)規(guī)劃和靜態(tài)規(guī)劃關系動態(tài)規(guī)劃和靜態(tài)規(guī)劃關系 對于某些靜態(tài)規(guī)劃問題對于某些靜態(tài)規(guī)劃問題, ,可以人為引入時間因素可以人

35、為引入時間因素, ,適當引入階段變量、狀態(tài)、決策變量可把它看作適當引入階段變量、狀態(tài)、決策變量可把它看作是按階段進行的動態(tài)規(guī)劃問題。是按階段進行的動態(tài)規(guī)劃問題。線性規(guī)劃和非線性規(guī)劃所研究的問題，通常都線性規(guī)劃和非線性規(guī)劃所研究的問題，通常都是與時間無關的，故又可以稱為靜態(tài)規(guī)劃。是與時間無關的，故又可以稱為靜態(tài)規(guī)劃。 靜態(tài)規(guī)劃模型靜態(tài)規(guī)劃模型njxaxxxxgxgxgzjnnn, 2 , 1 0 )()()( max212211其動態(tài)規(guī)劃方程：其動態(tài)規(guī)劃方程：0)(1 , 1, )()(max)(1111)(nnkkkksDxkksfnnksfxgsfkkk狀態(tài)轉移方程為狀態(tài)轉移方程為sk+1=

36、skxks1=a（1）逆推解法：）逆推解法： 設已知初始狀態(tài)為s1，并假定最優(yōu)值函數fk(sk)為表示第k階段的初始狀態(tài)為sk，從k階段到n階段得到最大效益。),x(sv)(sfnnn)(sDxnnnnn max 在第n階段;111),x(sTsnnnn)(sfsxxnnnnn最優(yōu)值最優(yōu)解),( 在第n-1階段max11111111)(sf),x(sv)(sfnnnnn)(sDxnnnnn)(sfsxxnnnnn11111),(最優(yōu)值得最優(yōu)解;1),x(sTskkkkmax2211111111)(sf),x(sv)(sf)(sDx;1112),x(sTs 在第1階段)(sfsxxkkkkk最優(yōu)

37、值最優(yōu)解),( 在第k階段max11)(sf),x(sv)(sfkkkkk)(sDxkkkkk)(sfsxx11111),(最優(yōu)值得最優(yōu)解 由于初始狀態(tài)s1已知，)(sfsxx11111)(和可確定 按遞推過程的相反順序推算可得所要求結果例例5 用動態(tài)規(guī)劃逆推解法求解用動態(tài)規(guī)劃逆推解法求解csxssxsxsxxxcxssxcxsscs1122233332122311121,或設3,2, 1,0)0(max3213221ixccxxxxxxzi 按變量個數劃分為3個階段，設狀態(tài)變量為s1, s2 s3, s4 ，s1c。取x1,x2,x3為決策變量；指標函數按乘積方式結合。最優(yōu)值函數fk(sk)

38、表示為第k階段的初始狀態(tài)為sk，從k階段到3階段所得的最大值。csxsxsx1122330 ,0 ,則有解：解：33333333maxsxs)(x)(sfsx及最優(yōu)解為極大值點，而22232222222222232,026222sxsdxhdxsdxhdsx22322232274sxs)(sf及最優(yōu)解)(032032222222222舍去和得由xsxxsxdxdh),(max)(maxmax2220222203322022222222xshxsx)(sfx)(sfsxsxsx),(max)(274maxmax111031110221011111111xshxsx)(sfx)(sfsxsxsx4

39、1641maxc(c)fzcs 1c)(sfcx41;4133332222161;2132c)(sfcsxcccxss4341112cxcxcx41;21;41321411641;41c(c)fcxcccxss412143223411111641;41s)(sfsx最優(yōu)解為：最優(yōu)解為：（2）順推解法：）順推解法： 設已知終止狀態(tài)為設已知終止狀態(tài)為sn+1，并假定最優(yōu)值函數，并假定最優(yōu)值函數fk(s)為表示第為表示第k階段的結束狀態(tài)為階段的結束狀態(tài)為s，從，從1階段到階段到k階階段得到最大效益。段得到最大效益。),(,max121111121111xsTs),x(sv)(sf)(sDx其中 在第

40、在第1階段階段;2322),x(sTs)(sfsxx21211),(最優(yōu)值最優(yōu)解 在第在第2階段階段max2122232222)(sf),x(sv)(sf)(sDx )(sfsxx32322),(最優(yōu)值得最優(yōu)解 狀態(tài)轉移方程為：狀態(tài)轉移方程為：),(1kkkkxsTs12ks1u1s2u2s3skuksk+1;1),x(sTsnnnn)(sfsxxnnnnn11),(最優(yōu)值最優(yōu)解 在第在第k階段階段max11)(sf),x(sv)(sfnnnnn)(sDxnnnnn 由于終止狀態(tài)由于終止狀態(tài)sn+1已知，已知，)(sfsxxnnnnn11)(和可確定 按計算過程的相反順序推算可得所要求結果按計

41、算過程的相反順序推算可得所要求結果例例6csxssxsxsxxxcxxsxssxcxsscs 4333221212323423233434,或或設設3,2, 1,0)0(max3213221ixccxxxxxxzi 按變量個數劃分為按變量個數劃分為3個階段，設狀態(tài)變量為個階段，設狀態(tài)變量為s1, s2 s3, s4 ，s4c。取。取x1,x2,x3為決策變量；指標函為決策變量；指標函數按乘積方式結合。最優(yōu)值函數數按乘積方式結合。最優(yōu)值函數fk(sk+1)表示為第表示為第k階段末的結束狀態(tài)為階段末的結束狀態(tài)為sk+1，從，從1階段到階段到k階段所階段所得的最大值。得的最大值。csxsxsx433

42、2210 ,0 ,則有用順推解法求解用順推解法求解解：解：21212121maxsxs)(x)(sfsx及最優(yōu)解為極大值點，而32332222223222232,026232sxsdxhdxsdxhdsx32332232274sxs)(sf及最優(yōu)解)(032032232223222舍去和得由xsxxsxdxdh),(max)(maxmaxmax2320232202220212203232323232xshxsxsx)(sfx)(sfsxsxsxsx ),(max)(274max274maxmax343033430333032304343434343xshxsxsx)(sfx)(sfsxsxsx

43、sx443641maxc)(sfzcs 4c)(sfcx41;4121133232161;2132c)(sfcsxcccxss4341343cxcxcx41;21;413214433641;41c)(sfcxcccxss412143232444343641;41s)(sfsx最優(yōu)解為：最優(yōu)解為：例7 用動態(tài)規(guī)劃方法解下面問題9,2,333222111sxssxssx設3 , 2 , 1, 09231224max321232221ixxxxxxxFi 按變量個數劃分為按變量個數劃分為3個階段，設狀態(tài)變量為個階段，設狀態(tài)變量為s0, s1 s2, s3 ，記，記s39。取。取x1,x2,x3為決策

44、變量；指標函數按加為決策變量；指標函數按加法方式結合。最優(yōu)值函數法方式結合。最優(yōu)值函數fk(sk)表示為第表示為第k階段末的階段末的結束狀態(tài)為結束狀態(tài)為sk，從，從1階段到階段到k階段所得的最大值。階段所得的最大值。3322110,20,3sxsxsx則有解：解：3944max11223111111sxs)x()(sfsx及最優(yōu)解42,9402222222s)s(hs)(h222222780916914sxsxdxdh得由),(max)2(94max94maxmax2322022222202222011222022222212222xshxsxsx)(sfx)(sfsxsxsxsx094222

45、22xs)(sf及相應的最優(yōu)解 該點不在允許決策集合內，因而最大值必在兩端上選取該點不在允許決策集合內，因而最大值必在兩端上選取),(max)(94122max122max33302332022203333333333xshxsx)(sfx)(sfsxsxsx122,129402332233s)(shs)(h174max,9;0;0321Fxxx最優(yōu)解為：最優(yōu)解為：233333112098944sxsxdxdh得由，該點為極小值點09442332dxhd332333122sxs)(sf及相應的最優(yōu)解 由于s3未知，須對s3求極值122maxmax239033034s)(sfscs 當s39時，

46、 f3(s3)取最大。 f3(s3)292+12174 按計算過程的相反順序推算可得所要求結果判斷題判斷題 1.1.動態(tài)規(guī)劃模型中動態(tài)規(guī)劃模型中, ,問題的階段數目等于問題中子問問題的階段數目等于問題中子問題的數目題的數目; ; 2.2.動態(tài)規(guī)劃中動態(tài)規(guī)劃中, ,定義狀態(tài)時應保證在各個階段中所做定義狀態(tài)時應保證在各個階段中所做決策的相互獨立性決策的相互獨立性; ; 3.3.動態(tài)規(guī)劃的最優(yōu)性原理保證了從某一狀態(tài)開始的動態(tài)規(guī)劃的最優(yōu)性原理保證了從某一狀態(tài)開始的未來決策獨立于先前已作出的決策未來決策獨立于先前已作出的決策; ; 4.4.對于一個動態(tài)規(guī)劃問題對于一個動態(tài)規(guī)劃問題, ,應用順推或逆推解法

47、可能應用順推或逆推解法可能會得到不同的結果；會得到不同的結果； 5.5.假如一個線性規(guī)劃問題含有假如一個線性規(guī)劃問題含有5 5個變量和個變量和3 3個約束條個約束條件，則用動態(tài)規(guī)劃求解時將劃分為件，則用動態(tài)規(guī)劃求解時將劃分為3 3個階段，每個階個階段，每個階段的狀態(tài)將由一個五維的向量組成；段的狀態(tài)將由一個五維的向量組成； 6.6.動態(tài)規(guī)劃問題的基本方程是將一個多階段的決策動態(tài)規(guī)劃問題的基本方程是將一個多階段的決策問題轉化為一系列具有遞推關系的單階段的決策問問題轉化為一系列具有遞推關系的單階段的決策問題。題。作業(yè)：習題6 1，2，4 有一個徒步旅行者，其可攜帶物品重量的限度為有一個徒步旅行者，其

48、可攜帶物品重量的限度為a 公公斤，設有斤，設有n 種物品可供他選擇裝入包中。已知每種物品種物品可供他選擇裝入包中。已知每種物品的重量及使用價值（作用），問此人應如何選擇攜帶的重量及使用價值（作用），問此人應如何選擇攜帶的物品（各幾件），使所起作用（使用價值）最大？的物品（各幾件），使所起作用（使用價值）最大？物品物品 1 2 j n重量（公斤重量（公斤/ /件）件） a1 a2 aj an每件使用價值每件使用價值 c1 c2 cj cn 這就是背包問題。類似的還有工廠里的下料問題、運這就是背包問題。類似的還有工廠里的下料問題、運輸中的貨物裝載問題、人造衛(wèi)星內的物品裝載問題等。輸中的貨物裝載問題

49、、人造衛(wèi)星內的物品裝載問題等。背包問題 (選學)設設xj 為第為第j 種物品的裝件數（非負整數）則問題的數學種物品的裝件數（非負整數）則問題的數學模型如下：模型如下： ). 2 . 1(0max1njxaxaxcZjnijjjnjjj 且且為為整整數數動態(tài)規(guī)劃的數學模型動態(tài)規(guī)劃的數學模型 按照裝入物品的種類劃分階段，按照裝入物品的種類劃分階段，k=1，2，n； 狀態(tài)變量狀態(tài)變量sk表示裝入第表示裝入第k種至第種至第n種物品的總重量種物品的總重量 決策變量決策變量xk表示裝入第表示裝入第k種物品的件數；。種物品的件數；。 狀態(tài)轉移方程為：狀態(tài)轉移方程為：sk+1=skakxk 允許決策集合為：允

50、許決策集合為： 階段指標函數階段指標函數ck（xk）表示第表示第k階段裝入第階段裝入第k種商品種商品xk件時件時的價值的價值 fk(sk)表示第表示第k階段裝入物品總重量為階段裝入物品總重量為sk時的最大價值時的最大價值為整數kkkkkkkxasxxsD,0)(kkaskkas其中 表示不超過 的最大整數；動態(tài)規(guī)劃基本方程為：動態(tài)規(guī)劃基本方程為：nkxasfxcsfkkkkkkasxkkkkk2 )(max)(10其中當當 k=1 時，有：時，有：的最大整數表示不超過其中1111111 , )(asasasxascsfkkkkk例題：求下面背包問題的最優(yōu)解例題：求下面背包問題的最優(yōu)解且為整數0

51、,55231258max321321321xxxxxxxxxZ物品物品 1 2 3重量（公斤）重量（公斤） 3 2 5使用價值使用價值 8 5 12解：解：a5 ，問題是求，問題是求 f3(5) )55(12max)5(323503333xfxfxax 整整數數 )1()0(223231032355032350333333333)0(12),5(0max)55(12max)55(12max)55(12max)5(xxxxxxaxffxfxxfxxfxf ，整整數數整整數數 5 5 )( 2)1()0(1112122, 10212250212502222222222)1(10),3(5),5(0

52、max)25(max)25(max)25(5max)5(xxxxxxxaxfffxfxxfxxfxf，整數整數整數整數 )0()0(0max)20(max)20(max)20(5max)0(1)0(121202122002120022222222ffxfxxfxxfxfxxxxxax 5 5 整數整數整數整數)0(0308)0()0(0318)1()1(8338)3()1(8358)5(1111111111111111 xxcfxxcfxxcfxxcf ) 1, 1(1310, 85, 8max) 1 (10),3(5),5(0max)5(212)1()0(1112222 xxffffxxx

53、)( )0, 0(0)0()0(0max)0(211)0(122 xxfffx )0,1,1(13012,130max)0(12),5(0max)5(321)1()0(22333 xxxfffxx所以，最優(yōu)解為所以，最優(yōu)解為 X（1 . 1 . 0），），最優(yōu)值為最優(yōu)值為 Z = 13。 排序問題指排序問題指n 種零件經過不同設備加工是的順序問題。種零件經過不同設備加工是的順序問題。其目的是使加工周期為最短。其目的是使加工周期為最短。 1、n 1 排序問題排序問題 即即n 種零件經過種零件經過1 種設備進行加工，如何安排？種設備進行加工，如何安排？14682023交貨日期（交貨日期（d）451

54、73加工時間（加工時間（t）零件代號零件代號2j1j3j4j5j例、例、排序問題 (選學) （1）平均通過設備的時間最?。┢骄ㄟ^設備的時間最小 按零件加工時間非負次序排列順序，其時間最小。（即按零件加工時間非負次序排列順序，其時間最小。（即將加工時間由小到大排列即可）將加工時間由小到大排列即可）1j2j3j4j5j零件加工順序零件加工順序 工序時間工序時間13457 實際通過時間實際通過時間1481320 交貨時間交貨時間82314620 平均通過時間平均通過時間2 .9)1481320(51 x延遲時間延遲時間 = 13 6 = 7 （2）按時交貨排列順序）按時交貨排列順序1j2j3j4j

55、5j零件加工順序零件加工順序 工序時間工序時間13457 實際通過時間實際通過時間56101720 交貨時間交貨時間82314620 平均通過時間平均通過時間6 .11)56101720(51 x延遲時間延遲時間 = 0 （3）既滿足交貨時間，又使平均通過時間最?。┘葷M足交貨時間，又使平均通過時間最小1j2j3j4j5j零件加工順序零件加工順序 工序時間工序時間13457 實際通過時間實際通過時間1691320 交貨時間交貨時間82314620延遲時間延遲時間 = 0 平均通過時間平均通過時間8 .9)1691320(51 x 2、n 2 排序問題排序問題 即即n 種零件經過種零件經過2 種設備進行加工，如何安