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

1、運(yùn)籌學(xué)運(yùn)籌學(xué) 第八、九章第八、九章 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃第八章 動(dòng)態(tài)規(guī)劃1建立動(dòng)態(tài)規(guī)劃模型的步驟建立動(dòng)態(tài)規(guī)劃模型的步驟 1 1、劃分階段、劃分階段劃分階段是運(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 2、正確選擇狀態(tài)變量、正確選擇狀態(tài)變量Sk選擇變量既要能確切描述過程演變又要滿足無后效性，選擇變量既要能

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

3、據(jù)根據(jù)k 階段狀態(tài)變量和決策變量，寫出階段狀態(tài)變量和決策變量，寫出k+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)系。 5 5、正確寫出指標(biāo)函數(shù)、正確寫出指標(biāo)函數(shù)V Vk,n的關(guān)系，它應(yīng)滿足下面三個(gè)的關(guān)系，它應(yīng)滿足下面三個(gè)性質(zhì)：性質(zhì)：V Vk,n是定義在全過程和所有后部子過程上的數(shù)量函數(shù)是定義在全過程和所有后部子過程上的數(shù)量函數(shù)具有可分離性，并滿足遞推關(guān)系，即具有可分離性，并滿足遞推關(guān)系，即Vk,n(Sk,Uk ,Sk1,Sn+1)=k(Sk,Uk ,Vk1,n(Sk1,Uk1,Sn+1)函數(shù)函數(shù)k（Sk，Uk ，Vk1,n）對(duì)于變量對(duì)于變量Vk1,n

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

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

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

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

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

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

10、：設(shè)將設(shè)將S2臺(tái)設(shè)備（臺(tái)設(shè)備（S20,1,2,3,4,5）分配給乙廠和）分配給乙廠和丙廠時(shí)，對(duì)每一個(gè)丙廠時(shí)，對(duì)每一個(gè)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第一階段第一階段：設(shè)將S1臺(tái)設(shè)備（S15）分配給甲廠、乙廠

11、和丙廠時(shí)，則最大盈利值為：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按計(jì)算表格的順序反推，可知最優(yōu)分配方案有兩個(gè)：按計(jì)算表格的順序反推，可知最優(yōu)分配方案有兩個(gè)：1）由）由X1*0，S2S1X1*505。再由。再由表表92，可知，可知X2*2。S3S2X2*523，故，故X3*S33。即得甲。即得甲廠分得廠分得0臺(tái)，乙廠分得臺(tái)，乙廠分得2臺(tái)，丙廠分得臺(tái)，丙廠分得3臺(tái)。臺(tái)。2）由）由X1*2，S2S1X1*523。再由表。再由表92

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

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

14、 s1 1 =1000=1000; ;決策變量決策變量u uk k 表示表示第第k k年投入高負(fù)荷生產(chǎn)的機(jī)器數(shù)年投入高負(fù)荷生產(chǎn)的機(jī)器數(shù) ， 允許決策集合允許決策集合U Uk k ( (s sk k)= )= u uk k 00 u uk k s sk k; skuk表示為第表示為第k年初分配在低負(fù)荷下生產(chǎn)的機(jī)器數(shù)量。年初分配在低負(fù)荷下生產(chǎn)的機(jī)器數(shù)量。狀態(tài)轉(zhuǎn)移方程為狀態(tài)轉(zhuǎn)移方程為 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; ;階段指標(biāo)階段指標(biāo)v vk k( (s sk k, , x xk k) ) 表示表示第第k k年的產(chǎn)量年的產(chǎn)量 ：v vk k( (s sk k, ,u uk k) = ) = 8u8uk k + +5 5( (s sk ku uk k ) )= =5s5sk k + +3u3uk k ; ;最優(yōu)指數(shù)函數(shù)最優(yōu)指數(shù)函數(shù)f fk k( (s sk k) )表示第表示第k k階段從階段從s sk k 開始到最后階段采用最優(yōu)開始到最后階段采用最優(yōu)分配策略實(shí)現(xiàn)的最大產(chǎn)量分配策略實(shí)現(xiàn)的最大產(chǎn)量; ;0)(5 , 4 , 3 , 2 , 1)2 . 09 . 0(35)(),()(6610

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

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

18、22222222ususussussfusvsfsusususuf2(s2)是關(guān)于是關(guān)于u2 的的單調(diào)減函數(shù)單調(diào)減函數(shù)，故，故u*2 =0 時(shí)，時(shí)， f2(s2)=20.8 s2依次類推，可求得：u1*0，f1(s1)23.7 s1 最優(yōu)生產(chǎn)策略：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即前兩年應(yīng)把年初全部完好的機(jī)器投入低負(fù)荷下即前兩年應(yīng)把年初全部完好的機(jī)器投入低負(fù)荷下生產(chǎn)，后三年應(yīng)把年初全部完好的機(jī)器投入高負(fù)荷生產(chǎn)，后三年應(yīng)把年初全部完好的機(jī)器投入高負(fù)荷下生產(chǎn)。這樣最高產(chǎn)量為下生產(chǎn)。這樣最高產(chǎn)量為23700臺(tái)。臺(tái)。 企業(yè)一年中的產(chǎn)品生產(chǎn)往往是分期分批生產(chǎn)的。企業(yè)一年中的產(chǎn)品生產(chǎn)往往是分期分批生產(chǎn)的。 組織每批產(chǎn)品的生產(chǎn)，都要花費(fèi)一些生產(chǎn)準(zhǔn)備組織每批產(chǎn)品的生產(chǎn)，都要花費(fèi)一些生產(chǎn)準(zhǔn)備費(fèi)和存貯費(fèi)用。費(fèi)和存貯費(fèi)用。 若某一時(shí)期增

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

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

22、庫存量也為，第四個(gè)時(shí)期之末的庫存量也為0。試問：該廠應(yīng)如。試問：該廠應(yīng)如何安排各個(gè)時(shí)期的生產(chǎn)與庫存，才能在滿足市場(chǎng)需求何安排各個(gè)時(shí)期的生產(chǎn)與庫存，才能在滿足市場(chǎng)需求的條件下，總成本最小。的條件下，總成本最小。 動(dòng)態(tài)規(guī)劃的數(shù)學(xué)模型動(dòng)態(tài)規(guī)劃的數(shù)學(xué)模型該問題分成四個(gè)階段，該問題分成四個(gè)階段，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年的生產(chǎn)量，年的生產(chǎn)量，d dk k表示為第表示為第k k年的年的需求量。需求

23、量。 允許決策集合允許決策集合D Dk k( (s sk k)= )= u uk k 00 u uk k 66 狀態(tài)轉(zhuǎn)移方程為狀態(tài)轉(zhuǎn)移方程為 s sk k = =s sk-1k-1+ +u uk kdk; ;s s0 00; s40 第第k k年的生產(chǎn)成本為：年的生產(chǎn)成本為：66211300)(kkkkkkuuuuuc當(dāng)，當(dāng)當(dāng)解：解：第第k期末庫存量為期末庫存量為sk的存貯費(fèi)用為的存貯費(fèi)用為: 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寫出寫出順序遞推關(guān)系式順序遞推關(guān)系式：由于由于庫存量必須非負(fù)庫存量必須非負(fù), sk-1 skdkuk , ukskdkuk6 , 所以所以u(píng)kmin skdk，6sk 即使以后各期不再生產(chǎn)，須滿足最后的庫存即使以后各期不再生產(chǎn)，須滿足最后的庫存為為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對(duì)s1 9 之間的值分別進(jìn)行計(jì)算。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對(duì)對(duì)s2 6 之間的值分別進(jìn)行計(jì)算。之間的值分別進(jìn)行計(jì)算。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：某車間需要按月在月底供應(yīng)一定數(shù)量的某種部件給總裝：某車間需要按月在月底供應(yīng)一定數(shù)量的某種部件給總裝車間，由于生產(chǎn)條件的變化，該車間在各月份中生產(chǎn)每單位這種車間，由于生產(chǎn)條件的變化，該車間在各月份中生產(chǎn)每單位這種部件所需耗費(fèi)的工時(shí)不同，各月份的生產(chǎn)量于當(dāng)月的月底前，全部件所需耗費(fèi)的工時(shí)不同，各月份的生產(chǎn)量于當(dāng)月的月底前，全部要存入倉庫以備后用。已知總裝車間的各個(gè)月份的需求量以及部要存入倉庫以備后用。已知總裝車間的各個(gè)月份的需求量以及在加工車間生產(chǎn)該部件每單位數(shù)量所需工時(shí)數(shù)如下表所示。在加工車間生產(chǎn)該部件每單位數(shù)量所需工時(shí)數(shù)如下表所示。設(shè)倉庫容量限制為設(shè)倉庫容量限制為H=9，

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

31、轉(zhuǎn)移方程：sk+1skukdk ; dkskH 允許決策集合：允許決策集合：D k(sk) uk : uk 0, dk+1skukdkH s12 s70 fk(Sk)表示在第k月的庫存為sk時(shí)，從第k月到第6月所生產(chǎn)部件的最小累計(jì)工時(shí)數(shù)。寫出遞推關(guān)系式：遞推關(guān)系式：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 最小工時(shí)數(shù)為最小工時(shí)數(shù)為357。3 3 動(dòng)態(tài)規(guī)劃和靜態(tài)規(guī)劃關(guān)系動(dòng)態(tài)規(guī)劃和靜態(tài)規(guī)劃關(guān)系 對(duì)于某些靜態(tài)規(guī)劃問題對(duì)于某些靜態(tài)規(guī)劃問題, ,可以人為引入時(shí)間因素可以人

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

36、skxks1=a（1）逆推解法：）逆推解法： 設(shè)已知初始狀態(tài)為s1，并假定最優(yōu)值函數(shù)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)(和可確定 按遞推過程的相反順序推算可得所要求結(jié)果例例5 用動(dòng)態(tài)規(guī)劃逆推解法求解用動(dòng)態(tài)規(guī)劃逆推解法求解csxssxsxsxxxcxssxcxsscs1122233332122311121,或設(shè)3,2, 1,0)0(max3213221ixccxxxxxxzi 按變量個(gè)數(shù)劃分為3個(gè)階段，設(shè)狀態(tài)變量為s1, s2 s3, s4 ，s1c。取x1,x2,x3為決策變量；指標(biāo)函數(shù)按乘積方式結(jié)合。最優(yōu)值函數(shù)fk(sk)

38、表示為第k階段的初始狀態(tài)為sk，從k階段到3階段所得的最大值。csxsxsx1122330 ,0 ,則有解：解：33333333maxsxs)(x)(sfsx及最優(yōu)解為極大值點(diǎn)，而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）順推解法：）順推解法： 設(shè)已知終止?fàn)顟B(tài)為設(shè)已知終止?fàn)顟B(tài)為sn+1，并假定最優(yōu)值函數(shù)，并假定最優(yōu)值函數(shù)fk(s)為表示第為表示第k階段的結(jié)束狀態(tài)為階段的結(jié)束狀態(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)轉(zhuǎn)移方程為：狀態(tài)轉(zhuǎn)移方程為：),(1kkkkxsTs12ks1u1s2u2s3skuksk+1;1),x(sTsnnnn)(sfsxxnnnnn11),(最優(yōu)值最優(yōu)解 在第在第k階段階段max11)(sf),x(sv)(sfnnnnn)(sDxnnnnn 由于終止?fàn)顟B(tài)由于終止?fàn)顟B(tài)sn+1已知，已知，)(sfsxxnnnnn11)(和可確定 按計(jì)算過程的相反順序推算可得所要求結(jié)果按計(jì)

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

42、2210 ,0 ,則有用順推解法求解用順推解法求解解：解：21212121maxsxs)(x)(sfsx及最優(yōu)解為極大值點(diǎn)，而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 用動(dòng)態(tài)規(guī)劃方法解下面問題9,2,333222111sxssxssx設(shè)3 , 2 , 1, 09231224max321232221ixxxxxxxFi 按變量個(gè)數(shù)劃分為按變量個(gè)數(shù)劃分為3個(gè)階段，設(shè)狀態(tài)變量為個(gè)階段，設(shè)狀態(tài)變量為s0, s1 s2, s3 ，記，記s39。取。取x1,x2,x3為決策

44、變量；指標(biāo)函數(shù)按加為決策變量；指標(biāo)函數(shù)按加法方式結(jié)合。最優(yōu)值函數(shù)法方式結(jié)合。最優(yōu)值函數(shù)fk(sk)表示為第表示為第k階段末的階段末的結(jié)束狀態(tài)為結(jié)束狀態(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īng)的最優(yōu)解 該點(diǎn)不在允許決策集合內(nèi)，因而最大值必在兩端上選取該點(diǎn)不在允許決策集合內(nèi)，因而最大值必在兩端上選取),(max)(94122max122max33302332022203333333333xshxsx)(sfx)(sfsxsxsx122,129402332233s)(shs)(h174max,9;0;0321Fxxx最優(yōu)解為：最優(yōu)解為：233333112098944sxsxdxdh得由，該點(diǎn)為極小值點(diǎn)09442332dxhd332333122sxs)(sf及相應(yīng)的最優(yōu)解 由于s3未知，須對(duì)s3求極值122maxmax239033034s)(sfscs 當(dāng)s39時(shí)，

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

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

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

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

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

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

52、max)25(max)25(max)25(5max)5(xxxxxxxaxfffxfxxfxxfxf，整數(shù)整數(shù)整數(shù)整數(shù) )0()0(0max)20(max)20(max)20(5max)0(1)0(121202122002120022222222ffxfxxfxxfxfxxxxxax 5 5 整數(shù)整數(shù)整數(shù)整數(shù))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 種零件經(jīng)過不同設(shè)備加工是的順序問題。種零件經(jīng)過不同設(shè)備加工是的順序問題。其目的是使加工周期為最短。其目的是使加工周期為最短。 1、n 1 排序問題排序問題 即即n 種零件經(jīng)過種零件經(jīng)過1 種設(shè)備進(jìn)行加工，如何安排？種設(shè)備進(jìn)行加工，如何安排？14682023交貨日期（交貨日期（d）451

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

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