規(guī)劃數(shù)學(xué) 確定型動態(tài)規(guī)劃.ppt

1、第八章 動態(tài)規(guī)劃,1,建立動態(tài)規(guī)劃模型的步驟 1、劃分階段 劃分階段是運(yùn)用動態(tài)規(guī)劃求解多階段決策問題的第一步，在確定多階段特性后，按時(shí)間或空間先后順序，將過程劃分為若干相互聯(lián)系的階段。對于靜態(tài)問題要人為地賦予“時(shí)間”概念，以便劃分階段。 2、正確選擇狀態(tài)變量Sk 選擇變量既要能確切描述過程演變又要滿足無后效性，而且各階段狀態(tài)變量的取值能夠確定。一般地，狀態(tài)變量的選擇是從過程演變的特點(diǎn)中尋找。 3、確定決策變量Uk及允許決策集合Dk 通常選擇所求解問題的關(guān)鍵變量作為決策變量，同時(shí)要給出決策變量的取值范圍，即確定允許決策集合。,第八章 動態(tài)規(guī)劃,2,4、確定狀態(tài)轉(zhuǎn)移方程Sk+1=Tk(Sk,Uk)

2、 根據(jù)k 階段狀態(tài)變量和決策變量，寫出k+1階段狀態(tài)變量，狀態(tài)轉(zhuǎn)移方程應(yīng)當(dāng)具有遞推關(guān)系。 5、正確寫出指標(biāo)函數(shù)Vk,n的關(guān)系，它應(yīng)滿足下面三個(gè)性質(zhì)： Vk,n是定義在全過程和所有后部子過程上的數(shù)量函數(shù) 具有可分離性，并滿足遞推關(guān)系，即Vk,n(Sk,Uk ,Sk1,Sn+1)=k(Sk,Uk ,Vk1,n(Sk1,Uk1,Sn+1) 函數(shù)k（Sk，Uk ，Vk1,n）對于變量Vk1,n要嚴(yán)格單調(diào)。 6、恰當(dāng)?shù)囟x最優(yōu)指標(biāo)函數(shù) 階段指標(biāo)函數(shù)是指第k 階段的收益，最優(yōu)指標(biāo)函數(shù)是指從第k 階段狀態(tài)出發(fā)到第n 階段末所獲得收益的最優(yōu)值。,第八章 動態(tài)規(guī)劃,3,動態(tài)規(guī)劃模型分類,7、寫出恰當(dāng)?shù)倪吔鐥l件

3、，從邊界條件開始，逐段遞推尋優(yōu)，在每一個(gè)子問題的求解中，均用了它前面的子問題的最優(yōu)化結(jié)果，依次進(jìn)行，最后一個(gè)子問題所得的最優(yōu)結(jié)果，就是這個(gè)問題的最優(yōu)解，并找到相應(yīng)的最優(yōu)策略。,第6章 動態(tài)規(guī)劃,動態(tài)規(guī)劃的基本理論 （2學(xué)時(shí)） 確定型動態(tài)規(guī)劃 （2學(xué)時(shí)） 隨機(jī)型動態(tài)規(guī)劃 （1學(xué)時(shí)） 動態(tài)規(guī)劃的軟件計(jì)算 （1學(xué)時(shí)）,第14講 確定型性動態(tài)規(guī)劃 (6.2),最短路問題 資源分配問題 生產(chǎn)與存儲問題 動態(tài)規(guī)劃和靜態(tài)規(guī)劃的關(guān)系 自學(xué)背包問題、排序問題、貨郎擔(dān)問題,資源分配問題： 把有限的資源(如資金、材料、設(shè)備、人力等)分配給若干使用者，而使某一指標(biāo)為最優(yōu)的問題即為資源分配問題。 資源可以有一種或若干種

4、， 只有一種資源可供分配的問題稱之為一維資源分配問題。,資源分配問題 (6.2.2),例1：某工業(yè)部門按國家計(jì)劃的安排，擬將某高效率的設(shè)備五臺，分配給所屬的甲、乙、丙三個(gè)工廠，各工廠若獲得這種設(shè)備之后，可以為國家提供的盈利如下表所示。問：這五臺設(shè)備如何分配給各工廠，才能使國家得到的盈利最大。,1、一維資源分配問題,動態(tài)規(guī)劃的數(shù)學(xué)模型 將三個(gè)分廠看作是三個(gè)階段，即階段變量 k=1,2,3; 狀態(tài)變量sk 表示第k 階段初可分配的設(shè)備臺數(shù),0sk 5; 決策變量xk 表示第k 階段分配給分廠k 的設(shè)備臺數(shù)， 允許決策集合Xk (sk)= xk 0 xk sk; 狀態(tài)轉(zhuǎn)移方程為 sk+1 = sk

5、- xk ; 階段指標(biāo)Pk(sk, xk) 表示第k 階段從sk臺設(shè)備中分配給k 分廠xk 臺設(shè)備的階段效益; 最優(yōu)指數(shù)函數(shù)fk(sk)表示第k階段從sk 開始到最后階段采用最優(yōu)分配策略取得的最大的效益值; 遞推方程函數(shù)式,第三階段：設(shè)將S3臺設(shè)備（S30,1,2,3,4,5）全部分配給丙廠時(shí)，最大盈利值為： f3(S3)maxP3(X3) 其中X3S30,1,2,3,4,5 X3*表示使得f3(S3)為最大值時(shí)的最優(yōu)決策。,逆序求解,表91,第二階段：設(shè)將S2臺設(shè)備（S20,1,2,3,4,5）分配給乙廠和丙廠時(shí)，對每一個(gè)S2值，都有一種最優(yōu)分配方案，使得最大盈利值為：f2(S2)max P

6、2(X2)+ f3(S2X2) ，X20,1,2,3,4,5,表92,第一階段：設(shè)將S1臺設(shè)備（S15）分配給甲廠、乙廠和丙廠時(shí)，則最大盈利值為：f1(S1)max P1(X1)+ f2(5X1) 其中，X10,1,2,3,4,5,按計(jì)算表格的順序反推，可知最優(yōu)分配方案有兩個(gè)： 1）由X1*0，S2S1X1*505。再由表92，可知X2*2。S3S2X2*523，故X3*S33。即得甲廠分得0臺，乙廠分得2臺，丙廠分得3臺。 2）由X1*2，S2S1X1*523。再由表92，可知X2*2。S3S2X2*321，故X3*S31。即得甲廠分得2臺，乙廠分得2臺，丙廠分得1臺。 以上兩種最優(yōu)方案的總

7、盈利均為21萬元。,例2 機(jī)器負(fù)荷問題某種機(jī)器可在高低兩種不同的負(fù)荷下進(jìn)行生產(chǎn)，設(shè)機(jī)器在高負(fù)荷下生產(chǎn)的產(chǎn)量函數(shù)為g=8u1，其中u1為投入生產(chǎn)的機(jī)器數(shù)量，年完好率為a=0.7；在低負(fù)荷下生產(chǎn)的產(chǎn)量函數(shù)為h=5y，其中y為投入生產(chǎn)的機(jī)器數(shù)量，年完好率為b=0.9。假定開始生產(chǎn)時(shí)完好的機(jī)器數(shù)量S11000臺，試問每年如何安排機(jī)器在高低負(fù)荷下的生產(chǎn)，使在五年內(nèi)生產(chǎn)的產(chǎn)品總產(chǎn)量最高。,2、資源連續(xù)分配問題,動態(tài)規(guī)劃的數(shù)學(xué)模型 每年為一個(gè)階段，即階段變量 k=1,2,3,4,5; 狀態(tài)變量sk 表示第k年初所擁有的完好機(jī)器臺數(shù)，s1 =1000; 決策變量uk 表示第k年投入高負(fù)荷生產(chǎn)的機(jī)器數(shù) ， 允許

8、決策集合Uk (sk)= uk 0 uk sk; skuk表示為第k年初分配在低負(fù)荷下生產(chǎn)的機(jī)器數(shù)量。 狀態(tài)轉(zhuǎn)移方程為 sk+1 =auk +b(skuk ) =0.7uk+0.9(skuk) =0.9sk 0.2uk; 階段指標(biāo)vk(sk, xk) 表示第k年的產(chǎn)量 ：vk(sk,uk) = 8uk +5(skuk )=5sk +3uk ; 最優(yōu)指數(shù)函數(shù)fk(sk)表示第k階段從sk 開始到最后階段采用最優(yōu)分配策略實(shí)現(xiàn)的最大產(chǎn)量;,解：,K=5,從第5階段開始，向前逆推計(jì)算,f5(s5)是關(guān)于u5 的單增函數(shù)，故u*5 =s5 時(shí)，f5(s5)最大， f5(s5)=8 s5,K=4,f4(s

9、4)是關(guān)于u4 的單增函數(shù)，故u*4 =s4 時(shí)， f4(s4)=13.6 s4,K=3,f3(s3)是關(guān)于u3 的單增函數(shù)，故u*3 =s3 時(shí)， f3(s3)=17.52 s3,K=2,f2(s2)是關(guān)于u2 的單調(diào)減函數(shù)，故u*2 =0 時(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

10、= 0.9s2 =810， u*3= s3 ， s4 = 0.9s3 0.2u3 = 0.7s3 =576， 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ù)荷下生產(chǎn)，后三年應(yīng)把年初全部完好的機(jī)器投入高負(fù)荷下生產(chǎn)。這樣最高產(chǎn)量為23700臺。,企業(yè)一年中的產(chǎn)品生產(chǎn)往往是分期分批生產(chǎn)的。 組織每批產(chǎn)品的生產(chǎn)，都要花費(fèi)一些生產(chǎn)準(zhǔn)備費(fèi)和存貯費(fèi)用。 若某一時(shí)期增大生產(chǎn)批量則可減少生產(chǎn)批次，從而降低生產(chǎn)成本。 與此同時(shí)，批量大了，必然增加庫存而使存貯費(fèi)用增加。 在

11、企業(yè)產(chǎn)品的生產(chǎn)成本、存貯費(fèi)用、市場需求量確定的情況下，正確計(jì)劃各時(shí)期的生產(chǎn)量，既滿足市場需求，又使總支出最少，這是一個(gè)多階段決策問題。,生產(chǎn)存儲問題 (6.2.3),1、生產(chǎn)計(jì)劃問題： 例3 某工廠要對一種產(chǎn)品制訂今后四個(gè)時(shí)期的生產(chǎn)計(jì)劃，據(jù)估計(jì)在今后四個(gè)時(shí)期內(nèi)，市場對于該產(chǎn)品的需求量如下表所示。假定該廠生產(chǎn)每批產(chǎn)品的固定成本為3千元，若不生產(chǎn)就為0，每單位產(chǎn)品成本為1千元，每個(gè)時(shí)期生產(chǎn)能力所允許的最大生產(chǎn)批量為不超過6個(gè)單位，每個(gè)時(shí)期末未售出的產(chǎn)品，每單位需付存貨費(fèi)0.5千元。還假定在第一個(gè)時(shí)期的初始庫存量為0，第四個(gè)時(shí)期之末的庫存量也為0。試問：該廠應(yīng)如何安排各個(gè)時(shí)期的生產(chǎn)與庫存，才能在滿足

12、市場需求的條件下，總成本最小。,動態(tài)規(guī)劃的數(shù)學(xué)模型 該問題分成四個(gè)階段，k表示年度，k1，2，3，4; 狀態(tài)變量sk-1表示為第k年初的庫存量，第k1年末的庫存量。 決策變量uk 表示為第k年的生產(chǎn)量，dk表示為第k年的需求量。 允許決策集合Dk(sk)= uk 0 uk 6 狀態(tài)轉(zhuǎn)移方程為 sk =sk-1+ukdk;s00; s40 第k年的生產(chǎn)成本為：,解：,第k期末庫存量為sk的存貯費(fèi)用為: hk(sk)=0.5 sk 總成本為:ck(uk)hk(sk) fk(sk)表示由第1年的初始庫存為0到第k年末的庫存為Sk的最小總成本。,fk(sk)min ck(uk)hk(sk)fk-1(s

13、k-1) min ck(uk)hk(sk)fk-1(skdkuk) k=1,2,3,4 邊界條件f0(s0)0,寫出順序遞推關(guān)系式：,由于庫存量必須非負(fù), sk-1 skdkuk , ukskdk uk6 , 所以ukmin skdk，6,f1(s1)min c1(u1)h1(s1) f0(s0),s1 s0 +u1d1 d1=2 s10，u12，f1(0)5 s11，u13，f1(1)6.5 s12，u14，f1(2)8,對s1 9 之間的值分別進(jìn)行計(jì)算。,k1,s13，u15，f1(3)9.5 s14，u16，f1(4)11,f2(s2)min c2(u2)h2(s2)f1(s2d2u2)

14、,k2,其中，u2min s23，6,s21，f2(1)min c2(u2)h2(1)f1(4u2),對s2 6 之間的值分別進(jìn)行計(jì)算。,s20，f2(0)min c2(u2)h2(0)f1(3u2),u2=0,f2(0)9.5 u2=0,u2=0,f2(1)11.5，u2=0,s22，f2(2)min c2(u2)h2(2)f1(5u2) 14，u2=5 s23，f2(3)min c2(u2)h2(3)f1(6u2) 15.5，u2=6 s24，f2(4)min c2(u2)h2(4)f1(7u2) 17.5，u2=6 s25，f2(5)min c2(u2)h2(5)f1(8u2) 19.5

15、，u2=6 s26，f2(6)min c2(u2)h2(6)f1(9u2) 21.5，u2=6,f3(s3)min c3(u3)h3(s3)f2(s3d3u3) 其中，u3min s32，6 s3在0至d44之間,k3,s30，f3(0)minc3(u3)h3(0)f2(2u3),u3=0,s31，f3(1)min c3(u3)h3(1)f2(3u3) 16 u3=0,3 s32，f3(2)min c3(u3)h3(2)f2(4u3) 17.5 u3=4 f3(0)14 u3=0； f3(1) 16 u3=0,3； f3(2)17.5 u3=4 f3(3)19 u3=5,所以，u4=0，u3=

16、6，u2=0，u1=5, 最小總成本為20.5千元,f4(s4)min c4(u4)h4(s4)f3(s4d4u4) 其中，u4min s44，6 s40,k4,f4(0)min c4(u4)h4(0)f3(4u4),u4=0,f3(4)20.5 u3=6,例4：某車間需要按月在月底供應(yīng)一定數(shù)量的某種部件給總裝車間，由于生產(chǎn)條件的變化，該車間在各月份中生產(chǎn)每單位這種部件所需耗費(fèi)的工時(shí)不同，各月份的生產(chǎn)量于當(dāng)月的月底前，全部要存入倉庫以備后用。已知總裝車間的各個(gè)月份的需求量以及在加工車間生產(chǎn)該部件每單位數(shù)量所需工時(shí)數(shù)如下表所示。 設(shè)倉庫容量限制為H=9，開始庫存量為2，期終庫存量為0，要求制定一

17、個(gè)半年的逐月生產(chǎn)計(jì)劃，既使得滿足需要和庫容量的限制，又使得生產(chǎn)這種部件的總耗費(fèi)工時(shí)數(shù)為最少。,動態(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)移方程：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)系式： fk(Sk)minak(uk)fk+1(sk1) min ak(uk)fk

18、+1(skukdk) k=0,1,2,3,4,5,6 邊界條件: f7(S7)0,解：,s7s6u6d6 s70，u60 s6d64 f6(s6)0,k6,s6s5u5d5 s5u511 f5(s5)mina5(u5)f6(s6) 10(11s5) 11010s5 u5*11 s5,k5,f4(s4)mina4(u4)f5(s5)min20 u4+11010 (s4u42) = min10 u410 s4130 dk+1skukdkH ，dk+1dkskukHdk sk 9s4 u411s4 又uk0 ;max0, 9S4 u411s4 f4(s4)10(9s4) 10 s4130 =2202

19、0 s4 ; u4*9s4,k4,s5s4u4d4 s4u42s5,s4s3u3d3 s3u33s4,k3,f2(s2)mina2(u2)f3(s3)min13 u2+24417 (s2u25) = min4u217 s2329 8s2 u214s2 又uk0 max0, 8s2 u214s2 f2(s2)4(14s2) 17 s2329 =27313 s2 u2*14s2,5s3 u312s3;又uk0 max0, 5s3 u312s3 f3(s3)3(12s3) 20 s3280=24417 S3 u3*12s3,f3(s3)mina3(u3)f4(s4)min17 u3+22020 (s

20、3 u33) = min3u320 s3280,k2,s3s2u2d2 ,s2u25s3,f1(s1)mina1(u1)f2(s2) min18u1+27313(s1u18) =min5u113 s1377 13s1 u117s1;又uk0 max0, 13s1 u117s1 f1(S1)5(13s1) 13s1377=44218s1 U1*13s1,k1,f0(s0)mina0(u0)f1(s1) min11u0+44218u018 s0= min7u018s0442 8s0 u09s0 又uk0 max0, 8s0 u09S0 f0(s0)7(9s0) 18s0442 s0=2，f0(s0

21、)357 u0*9s07,k0,s2s1u1d1 s1u18s2,s1s0u0d0 , s0u0s1,u0*7, u1*4，u2*9，u3*3，u4*0，u5*4 最小工時(shí)數(shù)為357。,3 動態(tài)規(guī)劃和靜態(tài)規(guī)劃關(guān)系,對于某些靜態(tài)規(guī)劃問題,可以人為引入時(shí)間因素,適當(dāng)引入階段變量、狀態(tài)、決策變量可把它看作是按階段進(jìn)行的動態(tài)規(guī)劃問題。,線性規(guī)劃和非線性規(guī)劃所研究的問題，通常都是與時(shí)間無關(guān)的，故又可以稱為靜態(tài)規(guī)劃。,靜態(tài)規(guī)劃模型,其動態(tài)規(guī)劃方程：,狀態(tài)轉(zhuǎn)移方程為sk+1=skxks1=a,（1）逆推解法：,設(shè)已知初始狀態(tài)為s1，并假定最優(yōu)值函數(shù)fk(sk)為表示第k階段的初始狀態(tài)為sk，從k階段到n階段

22、得到最大效益。,在第n階段,在第n-1階段,在第1階段,在第k階段,由于初始狀態(tài)s1已知，,按遞推過程的相反順序推算可得所要求結(jié)果,例5 用動態(tài)規(guī)劃逆推解法求解,按變量個(gè)數(shù)劃分為3個(gè)階段，設(shè)狀態(tài)變量為s1, s2 s3, s4 ，s1c。取x1,x2,x3為決策變量；指標(biāo)函數(shù)按乘積方式結(jié)合。最優(yōu)值函數(shù)fk(sk)表示為第k階段的初始狀態(tài)為sk，從k階段到3階段所得的最大值。,解：,最優(yōu)解為：,（2）順推解法：,設(shè)已知終止?fàn)顟B(tài)為sn+1，并假定最優(yōu)值函數(shù)fk(s)為表示第k階段的結(jié)束狀態(tài)為s，從1階段到k階段得到最大效益。,在第1階段,在第2階段,狀態(tài)轉(zhuǎn)移方程為：,在第k階段,由于終止?fàn)顟B(tài)sn+

23、1已知，,按計(jì)算過程的相反順序推算可得所要求結(jié)果,例6,按變量個(gè)數(shù)劃分為3個(gè)階段，設(shè)狀態(tài)變量為s1, s2 s3, s4 ，s4c。取x1,x2,x3為決策變量；指標(biāo)函數(shù)按乘積方式結(jié)合。最優(yōu)值函數(shù)fk(sk+1)表示為第k階段末的結(jié)束狀態(tài)為sk+1，從1階段到k階段所得的最大值。,用順推解法求解,解：,最優(yōu)解為：,例7 用動態(tài)規(guī)劃方法解下面問題,按變量個(gè)數(shù)劃分為3個(gè)階段，設(shè)狀態(tài)變量為s0, s1 s2, s3 ，記s39。取x1,x2,x3為決策變量；指標(biāo)函數(shù)按加法方式結(jié)合。最優(yōu)值函數(shù)fk(sk)表示為第k階段末的結(jié)束狀態(tài)為sk，從1階段到k階段所得的最大值。,解：,該點(diǎn)不在允許決策集合內(nèi)，因

24、而最大值必在兩端上選取,最優(yōu)解為：,由于s3未知，須對s3求極值,當(dāng)s39時(shí)， f3(s3)取最大。 f3(s3)292+12174,按計(jì)算過程的相反順序推算可得所要求結(jié)果,判斷題,1.動態(tài)規(guī)劃模型中,問題的階段數(shù)目等于問題中子問題的數(shù)目; 2.動態(tài)規(guī)劃中,定義狀態(tài)時(shí)應(yīng)保證在各個(gè)階段中所做決策的相互獨(dú)立性; 3.動態(tài)規(guī)劃的最優(yōu)性原理保證了從某一狀態(tài)開始的未來決策獨(dú)立于先前已作出的決策; 4.對于一個(gè)動態(tài)規(guī)劃問題,應(yīng)用順推或逆推解法可能會得到不同的結(jié)果； 5.假如一個(gè)線性規(guī)劃問題含有5個(gè)變量和3個(gè)約束條件，則用動態(tài)規(guī)劃求解時(shí)將劃分為3個(gè)階段，每個(gè)階段的狀態(tài)將由一個(gè)五維的向量組成； 6.動態(tài)規(guī)劃問

25、題的基本方程是將一個(gè)多階段的決策問題轉(zhuǎn)化為一系列具有遞推關(guān)系的單階段的決策問題。,作業(yè)：習(xí)題6 1，2，4,有一個(gè)徒步旅行者，其可攜帶物品重量的限度為a 公斤，設(shè)有n 種物品可供他選擇裝入包中。已知每種物品的重量及使用價(jià)值（作用），問此人應(yīng)如何選擇攜帶的物品（各幾件），使所起作用（使用價(jià)值）最大？,這就是背包問題。類似的還有工廠里的下料問題、運(yùn)輸中的貨物裝載問題、人造衛(wèi)星內(nèi)的物品裝載問題等。,背包問題 (選學(xué)),設(shè)xj 為第j 種物品的裝件數(shù)（非負(fù)整數(shù)）則問題的數(shù)學(xué)模型如下：,動態(tài)規(guī)劃的數(shù)學(xué)模型 按照裝入物品的種類劃分階段，k=1，2，n； 狀態(tài)變量sk表示裝入第k種至第n種物品的總重量 決策

26、變量xk表示裝入第k種物品的件數(shù)；。 狀態(tài)轉(zhuǎn)移方程為：sk+1=skakxk 允許決策集合為： 階段指標(biāo)函數(shù)ck（xk）表示第k階段裝入第k種商品xk件時(shí)的價(jià)值 fk(sk)表示第k階段裝入物品總重量為sk時(shí)的最大價(jià)值,其中 表示不超過 的最大整數(shù)；,動態(tài)規(guī)劃基本方程為：,當(dāng) k=1 時(shí)，有：,例題：求下面背包問題的最優(yōu)解,解：a5 ，問題是求 f3(5),所以，最優(yōu)解為 X（1 . 1 . 0），最優(yōu)值為 Z = 13。,排序問題指n 種零件經(jīng)過不同設(shè)備加工是的順序問題。其目的是使加工周期為最短。,1、n 1 排序問題 即n 種零件經(jīng)過1 種設(shè)備進(jìn)行加工，如何安排？,例、,排序問題 (選學(xué))

27、,（1）平均通過設(shè)備的時(shí)間最小,按零件加工時(shí)間非負(fù)次序排列順序，其時(shí)間最小。（即將加工時(shí)間由小到大排列即可）,零件加工順序,平均通過時(shí)間,延遲時(shí)間 = 13 6 = 7,（2）按時(shí)交貨排列順序,零件加工順序,平均通過時(shí)間,延遲時(shí)間 = 0,（3）既滿足交貨時(shí)間，又使平均通過時(shí)間最小,零件加工順序,延遲時(shí)間 = 0,平均通過時(shí)間,2、n 2 排序問題 即n 種零件經(jīng)過2 種設(shè)備進(jìn)行加工，如何安排？,例、,經(jīng)變換為,加工順序圖如下：,A,B,T,3,7,5,6,8,9,5,4,3,2,+2,+2,-5,加工周期 T = 3+7+5+6+8+2 = 31,3、n 3 排序問題 即n 種零件經(jīng)過 3

28、種設(shè)備進(jìn)行加工，如何安排？,例、,A,B,C,T,變換,排序,復(fù)原,計(jì)算,T = 6+10+8+7+6+4+3 = 44,計(jì)算依據(jù)：,一個(gè)著名的命題：一個(gè)串村走戶的賣貨郎，他從某個(gè)村莊出發(fā)，通過若干個(gè)村莊一次且僅一次，最后仍回到原出發(fā)的村莊，問：應(yīng)如何選擇行走路線，能使得總的行程最短。 設(shè)有n個(gè)城市，1,2,n。Dij表示從i城到j(luò)城的距離。 規(guī)定推銷員是從城市1開始的，設(shè)推銷員走到i城，記Ni2,3,i-1,i+1,n 表示由1城到i城的中間城市集合。 S表示到達(dá)i城中途所經(jīng)過的城市的集合，則有S Ni 1）選取（i,S）作為狀態(tài)變量，表示推銷員從城市1開始走到i城，經(jīng)過若干個(gè)城市，構(gòu)成集合S。 2）最優(yōu)值函數(shù)fk(i,S)為從城市