插值與數(shù)據(jù)擬合模型

1、5)6)5)6)第二講插值與數(shù)據(jù)擬合模型函數(shù)插值與曲線擬合都是要根據(jù)一組數(shù)據(jù)構(gòu)造一個函數(shù)作為近似，由于近似的要求不同，二者的數(shù)學方法上是完全不同的。而面對一個實際問題，究竟用插值還是擬合，有時容易確定，有時則并不明顯。在數(shù)學建模過程中，常常需要確定一個變量依存于另一個或更多的變量的關(guān)系，即函數(shù)。但實際上確定函數(shù)的形式(線性形式、乘法形式、冪指形式或其它形式)時往往沒有先驗的依據(jù)。只能在收集的實際數(shù)據(jù)的基礎(chǔ)上對若干合乎理論的形式進行試驗，從中選擇一個最能擬合有關(guān)數(shù)據(jù)，即最有可能反映實際問題的函數(shù)形式，這就是數(shù)據(jù)擬合問題。一、插值方法簡介插值問題的提法是，已知n+1個節(jié)點(x,y),j二0,1,2

2、,n,其中x互不相同，不妨設(shè)a二xxx二b，求任一插值點x*(鼻x)處的插值y*。(x,y)可以看成是由某個函數(shù)01njjjy=g(x)產(chǎn)生的，g的解析表達式可能十分復雜，或不存在封閉形式。也可以未知。求解的基本思路是，構(gòu)造一個相對簡單的函數(shù)y二f(x)，使f通過全部節(jié)點，即f(x.)二y.(j二0，1，2,n)，再由f(x)計算插值，即y*二f(x*)。1拉格朗日多項式插值插值多項式從理論和計算的角度看，多項式是最簡單的函數(shù)，設(shè)f(x)是n次多項式，記作1)L(x)=axn+axn-1hfax+annn-110對于節(jié)點(x,y)應(yīng)有.L(x)=y,j=0,1,2,nnjj為了確定插值多項式L

3、(x)中的系數(shù)a,a，,a,a，將(1)代入(2)，有2)方程組(3)簡寫成nn-110axn+axnhfax+an0n-1010(axn+axnhfax+an1n-11110=y00=y13)axn+annn-1nxnhhaxha1n0 xnxn-100 xnxn-111jxnxn-1nn,A=(a,ann-1,a0)T,Y=(y0,y1，,yn)T注意detX是Vandermonde行列式，XA=Y利用行列式性質(zhì)可得detX二H(xk0jkn4)因x互不相同，故detX豐0，于是方程(4)中A有唯一解，即根據(jù)n+1個節(jié)點可以確定唯一的n次插值多項式。拉格朗日插值多項式實際上比較方便的做法不

4、是解方程(4)求A,而是先構(gòu)造一組基函數(shù)：、(x-x)(x-x)(x-x)(x-x)l(x)=01i+4n-il(x)是n次多項式，滿足i:i-i+:n,i=0,1,2,n(x-x)(x-x)(x-x)(x-x)i0ii-1iih1inl(x)=ri=ji,j=0,1,2,nij|0,心j1/14 /14 /147)L(x)=y1(x)niii=o顯然L(x)是滿足(2)的n次多項式，由方程(4)解的唯一性，(7)式表示的L(x)的解與(1)式相nn同。(5)、(7)稱拉格朗日插值多項式，用L(x)計算插值稱拉格朗日多項式插值。n誤差估計插值的誤差通過插值多項式L(x)與產(chǎn)生節(jié)點(x,y)的g

5、(x)之差來估計，記作R(x)。雖然我們可njjn能不知道g(x)的解析表達式，但不妨設(shè)g(x)充分光滑，具有n+1階導數(shù)。利用泰勒展開可以推出，對于任意xea,b。(n+1)!R(x)二g(x)-L(x)二-肝(x-x覧w(a,b)nn(n+1)!j若可以估計j=oIg(n+1)(g)|Mn+1實際上因為MIR(x)I減少；nn+1例將區(qū)間o,MnIR(x)I=+nIxxI,ge(a,b)n(n+1)!jj=o常難以確定，所以(10)式并不能給出精確的誤差估計。但是可能看出，n增加,10)g越光滑，M越小，IR(x)I越??；x越接近x，IR(x)I越小。n+1njnn等分，用y=g(x)=c

6、osx產(chǎn)生n+1個節(jié)點，然后作拉格朗日插值多項式。用兀L(x)計算cosn6(取4位有效數(shù)字)。估計IR(x)I(取n=1,2)。n兀c),0。由(5)、(7)式丿兀x二+ox0=12x0-1t-0兀22則(%,yo)=(0,1),(x1，y1)=L1(x)=yo1o+”廣1-2，則(x,y)=(0,1)，(x,y)=-,0.7071,(x,y)=-,00011v4丿22v2丿=0.6667若n二，由(5)、(7)式。1l6丿兀cos=L6L2(x)=yo1o+y111+y212=1(兀x4八兀Vo4、丫兀x2丿o八2丿(xo)x+o.7o71-兀、2丿兀兀42丿兀(x0)(x)4兀兀24丿兀

7、0丫12人(兀)(1)16(1)xX0.7071xxV4丿V2丿12V2丿1cos=L=0.8508。62V6丿=8兀2估計IRn(x)I:對于g(x)=C0Sx可設(shè)Mn+1=】，記節(jié)點間隔h=2。當xxj+1hh2IxxIIxxI-jj+14肝丨xx丨-2h-3hnhj4j=0于是(10)式給出1h2hn+1兀n+1丨R(x)|-2h-3h-nhn(n+1)!44(n+1)4(n+1)(2n)n+1可以算出n1234丨R(x)|n0.30.044.7x10-34.7x10-4,L16J216丿的誤差在IR(x)l范圍內(nèi)。n兀cos的精確值是0.8660(4位有效數(shù)字)L61插值多項式的振蕩用

8、拉格朗日插值多項式L(x)近似g(x)(axb)雖然隨著節(jié)點個數(shù)的增加，L(x)的次數(shù)變大，nn多數(shù)情況下誤差I(lǐng)R(x)I會變小，但n增加時，L(x)的光滑性變壞，有時會出現(xiàn)很大的振蕩。理論上,nn當nTa時，在a,b內(nèi)并不能保證L(x)處處收斂于g(x)。Runge給出了一個有名的例子：n1g(x)二,xg5,51+x2取x.=5+10j,j二0,1,2,n。對于n二2,4,6,作L(x)，會得到如下圖所示的結(jié)果?？梢钥闯?jnn對于較大的|x|，隨著n的增加，L(x)的振蕩越來越大，事實上可以證明，僅當|x|3.63時，才有nlimL(x)二g(x)，而在此區(qū)間外,L(x)是發(fā)散的。nnn

9、Ta高次插值多項式的這些缺陷，促使人們轉(zhuǎn)而尋求簡單的低次數(shù)多項式插值。2.分段線性插值簡單地說，將每兩個相鄰的節(jié)點用直線連起來，如此形成的一條折線就是分段線性插值函數(shù)，記作I(x)，它滿足I(x)二y，且I(x)在每個小區(qū)間x,x上是線性函數(shù)(j二0,1,n)。nnjjnjj+1I(x)可以表示為n12)I(x)=Yyl(x)njjj=0 xxd,xxx(j=0時舍去)xxj1jxx亠，xxjj+10,xxx(j=n時舍去)jj+1其它13)jj1I(x)有良好的收斂性，即對于xga,b有，limI(x)=g(x)。nnnTa用I(x)計算x點的插值時，只用到x左右的兩個節(jié)點，計算量與節(jié)點個數(shù)

10、n無關(guān)。但n越大，分段n越多，插值誤差越小。實際上用函數(shù)表作插值計算時，分段線性插值就足夠了，如數(shù)學、物理中用的特殊函數(shù)表，數(shù)理統(tǒng)計中用的概率分布表等。3.三次樣條插值樣條函數(shù)的由來分段線性插值雖然簡單，n足夠大時精度也相當高。但是折線在節(jié)點處顯然不光滑，即I(x)在節(jié)點n處導數(shù)不連續(xù)。這影響了它在諸如機械加工等領(lǐng)域(希望插值曲線光滑)中的應(yīng)用。所謂樣條(Spline),來源于船舶、飛機等設(shè)計中描繪光滑外形曲線用的繪圖工具。一根有彈性的細長木條用壓鐵固定在節(jié)點上，其它地方讓它自然彎曲，如此畫出的曲線稱為樣條曲線。因為這種曲線的曲率是處處連續(xù)的,所以要求樣條函數(shù)的二階導數(shù)連續(xù)。人們普遍使用的樣條

11、函數(shù)是分段三次多項式。三次樣條函數(shù)三次樣條函數(shù)記作S(x),axb。要求它滿足以下條件：在每個小區(qū)間x,x(i二1,.,n)上是3次多項式；i-1i在axb上二階導數(shù)連續(xù)；TOC o 1-5 h zS(x)二y,i=0,1,n。(14)ii由條件a,不妨將S(x)記為S(x)二(x),xex,x,i二1,.,n)ii-1iS(x)二ax3+bx2+cx+d(15)iiiii其中a,b,c,d為待定系數(shù)，共4n個。由條件b,iiiiS(x)二S(x)iii+1iS(x)二S(x)i二1,2,n一1(16)iii+1iS(x)二S(x)iii+1i容易看出，(14)、(16)式共含有4n-2個方程

12、，為確定S(x)的4n個待定參數(shù)，尚需再給出2個條件。最常用的是所謂自然邊界條件：S(x)=S(x)=0(17)0n可以證明，4n階線性方程組(14)、(16)、(17)有唯一解，即S(x)被唯一確定。但是，這種解法的工作量太大，方程組又常呈病態(tài)，所以實際上要設(shè)計簡便的解法。另外，像分段線性函數(shù)I(x)一樣，三次樣條函數(shù)S(x)也有良好的收斂性，即在相當一般的條件下，nlimS(x)=g(x)。4.用MATLAB作插值計算拉格朗日插值需先按照(5)、(7)式編寫一個程序。設(shè)n個節(jié)點以數(shù)組x0,y0輸入(注意：程序中用n個節(jié)點，而不是(5)、(7)式中的n+1個節(jié)點)，m個插值點以數(shù)組x輸入。輸

13、出數(shù)組y為m個插值。比如可以寫一個名為lagr1.m的M文件。分段線性插值有現(xiàn)成的程序y=interp1(x0,y0,x)其中輸入x0,y0,x和輸出y的意義同上，數(shù)組長度自定義(x0,y0同長度，x,y同長度)。三次樣條插值也有現(xiàn)成的程序y=interp1(x0,y0,x,spline)或y=spline(x0,y0,x)其中輸入x0,y0,x和輸出y的意義同上，數(shù)組長度自定義(x0,y0同長度，x,y同長度)。例對y二八I、,-5x5，用n(=11)個節(jié)點(等分)作上述三種插值，用m(=21)個插值點(等分)(1+x2)作圖，比較結(jié)果。插值方法小結(jié)拉格朗日插值是高次多項式插值(n+1個節(jié)點

14、上用不超過n次的多項式)，插值曲線光滑，誤差估計有表達式。但有振蕩現(xiàn)象，收斂性不能保證。這種插值主要用于理論分析，實際意義不大。分段線性和三次樣條插值是低次多項式插值，簡單實用，收斂性有保證，但不光滑，三次樣條插值的整體光滑性已大有提高，應(yīng)用廣泛，唯誤差估計較困難。二、最小二乘法簡介下面先看一個例子。例1“人口問題”是我國最大社會問題之一，估計人口數(shù)量和發(fā)展趨勢是我們制定一系列相關(guān)政策的基礎(chǔ)。有人口統(tǒng)計年鑒，可查的我國從1949年至1994年人口數(shù)據(jù)智料如下：年份1949195419591964196919741979198419891994人口數(shù)（百萬）541.67602.66672.097

15、04.99806.71908.59975.421034.751106.761176.74分析：（1）在直角坐標系上作出人口數(shù)的圖象。（2）估計出這圖象近似地可看做一條直線。（3）用以下幾種方法（之一）確定直線方程，并算出1999年人口數(shù)。方法一：先選擇能反映直線變化的兩個點，如（1949，541.67），（1984，1034.75）二點確定一條直線，方程為：N=14.088t-26915.842,代入t=1999,得N-12.46億。方法二：可以多取幾組點對，確定幾條直線方程，將t=1999代入，分別求出人口數(shù)，再取其算數(shù)平值。方法三：可采用“最小二乘法”求出直線方程。最小二乘法簡介設(shè)（x,y

16、）,（x,y），,（x,y）是直角平面坐標系下給出的一組數(shù)據(jù)，設(shè)xxx，我們可1122nn12n以把這組數(shù)據(jù)看作是一個離散的函數(shù)。根據(jù)觀察，如果這組數(shù)據(jù)圖象“很象”一條直線（不是直線），我們的問題是確定一條直線y=ax+b，使得它能最好的反映出這組數(shù)據(jù)的變化。對個別觀察值來說，用直線y二ax+b的值來近似代替其觀察值時，所產(chǎn)生的誤差可能是正的，也可能是負的。為了不使它們相加彼此抵消，可用Iy-（ax+b）Iiii=1來表示用直線y=ax+b來近似代原來實驗數(shù)據(jù)時所產(chǎn)生的誤差。為了在數(shù)學上處理方便，又把上式改成d=y-（ax+b）2iii=1也就是說，我們選取常數(shù)a,b，使得總誤差d達到最小。這

17、就是所謂的最小二乘法。用微分法不難求出上面最小值問題的駐點，這里不列出其結(jié)果。事實上，在MATLAB中已有現(xiàn)成的求最小二乘問題的函數(shù)polyfit，稱為多項式擬合函數(shù)，并且這個函數(shù)允許多項式的次數(shù)可以是任意次的。除外，還可以用解線性方程組中的除法運算（矩陣除法）來求解。這兩個方法的區(qū)別在于：用polyfit函數(shù)求擬合問題時，多項式的次數(shù)必須從0次到最高次數(shù)n之間每個次數(shù)都要出現(xiàn)。而如果需要選擇一些次數(shù)進行擬合時，就可用矩陣除法運算來進行。矩陣除法還可以求一般的線性擬合問題，例如擬合函數(shù)不是多項式的線性擬合問題。上面例1中的問題就可以用polyfit來求解。例2用最小二乘法求一個形如y=a+bx

18、2的經(jīng)驗公式，數(shù)據(jù)如下：x1925313844y19.032.349.073.398.8解用求矩陣除法（因為要擬合的多項式缺了1次幕項，所以不能用polyfit函數(shù)）。代碼如下。x=1925313844;y=19.032.349.073.398.8;x1=x.A2;x1=ones（5,1）,x1ab=x1yx0=19:0.2:44;y0=ab（1）+ab（2）*x0.A2;clfplot（x,y,o,x0,y0,-r）多項式擬合是線性擬合問題（注意：無論擬合的多項式次是多少，多項式擬合都是線性擬合!）。但在實際應(yīng)用中，有時還需要作非線性擬合問題。所謂線性擬合問題是指：需要擬合的函數(shù)中的未知常數(shù)

19、都線性的。如函數(shù)y=a+bx2中,常數(shù)a,b是線性的。但y=ax+ebx、y=aebx中的常數(shù)a,b都是非線性。這種函數(shù)的擬合問題稱為非線性擬合問題。有的非線性擬合問題可以化為線性擬合問題。例如在函數(shù)y=aebx中，兩邊取對數(shù)，得lny=lna+bx，再令a=lna，z=lny，則要擬合的函數(shù)就成z=a+bx，這樣就變成線性擬合問題了。但也有不能化成線性擬合問題的情況，如函數(shù)y二ax+ebx就是這樣。在MATLAB5.3中求非線性擬合問題的函數(shù)是lsqcurvefit。例3在區(qū)間-1,3內(nèi)擬合函數(shù)y二ax+ebx。解用非線性擬合函數(shù)lsqcurvefit來擬合。先建立擬合函數(shù)。%建立擬合函數(shù)，

20、文件名是nxxyhhx.m，必須與函數(shù)名相同。%要擬合的函數(shù)中參數(shù)用x表示，即x(1)=ax(2)=b；%而擬合函數(shù)中x的值則用xdata表示。functionv=nxxyhhx(x,xdata)v=x(1)*xdata+exp(x(2)*xdata);以下指令在命令窗中進行。clf;x=linspace(-1,3,10);y1=2*x+exp(-0.1*x);%原型函數(shù)plot(x,y1,-k)holdony=y1+1.2*(rand(size(x)-0.5);%將原型函數(shù)加一些擾動plot(x,y,*g)x0=2.5,-0.5;a=lsqcurvefit(nxxyhhx,xO,x,y)%用

21、原始實驗數(shù)據(jù)擬合函數(shù)nxxyhhx(x),vpa(a(1),a(2),8)%nxxyhhx(t)表達式中各項的系數(shù)。y2=nxxyhhx(a,x);plot(x,y2,-r)legend(原型函數(shù)，原始數(shù)據(jù),用原始數(shù)據(jù)擬合的結(jié)果,4);三、血液流量問題小哺乳動物與小鳥的心跳速度比大哺乳動物與大鳥的快。如果動物的進化為每種動物確定了最佳心跳速度，為什么各種動物的最佳心跳速度不一樣呢？由于熱血動物的熱量通過身體表面散失，所以它們要用大量的能量維持體溫，而冷血動物在休息時只需要極少的能量，所以正在休息的熱血動物似乎在維持體溫?？梢哉J為，熱血動物可用的能量與通過肺部的血液流量成正比。試建立一個模型，將

22、體重與通過心臟的基礎(chǔ)(即休息時的)血液流量聯(lián)系起來，用下面的數(shù)據(jù)檢驗你的模型。有許多可得到脈搏數(shù)據(jù)但沒有血液流量數(shù)據(jù)的動物，建立一個模型將體重與基礎(chǔ)脈搏聯(lián)系起來，用下面的數(shù)據(jù)檢驗你的模型。在檢驗你在(1)和(2)中的模型時會出現(xiàn)不一致，試進行分析。表一關(guān)于某些哺乳動物的數(shù)據(jù)哺乳動物名稱兔山羊狗狗狗體重(千克)4.12416126.4基礎(chǔ)血液流量(分升/分)5.331221211表二關(guān)于人類的數(shù)據(jù)年齡5101625334760體重(千克)18316668707270基礎(chǔ)血液流量(分升/分)23335251434046脈搏(次/分)96906065687280表三關(guān)于小鳥類的數(shù)據(jù)表四關(guān)于大鳥類的數(shù)

23、據(jù)鳥類體重(克)脈搏(次/分)鳥類體重(克)脈搏(次/分)蜂鳥4615海鷗388401鷦鷯11450雞1980312金絲雀16514禿鷹8310199麻雀28350火雞875093鴿子130135駝鳥8000065表五關(guān)于哺乳動物的數(shù)據(jù)哺乳動物名稱體重(千克)脈搏(次/分)哺乳動物名稱體重(千克)脈搏(次/分)小蝙蝠0.006588海豹2025100小家鼠0.017500山羊3381倉鼠0.103347綿羊507080小貓0.117300豬1006080大家鼠0.252352馬3804503455天竺鼠0.437269牛5004653兔1.34251象200030002550這里只對該問題作一

24、些擬合方面的練習。其它問題讀者可自己進行討論。符號用w表示動物的體重，單位：千克用v表示動物的基礎(chǔ)血液流量，單位：公升/分用t表示動物的年齡，單位：歲用n表示動物的脈搏，單位：次/分假設(shè)動物的基礎(chǔ)血液流量與動物的體重之間存在一定的函數(shù)關(guān)系V=f(w)，可以用表一中的數(shù)據(jù)來擬合這個函數(shù)。函數(shù)f(w)是一個什么樣的函數(shù)呢？由于我們對“動物的基礎(chǔ)血液流量與動物的體重”之間的關(guān)系并不清楚，所以只有根據(jù)表一中的數(shù)據(jù)得出函數(shù)f(w)一些性質(zhì)。先將表一中的數(shù)據(jù)用MATLAB軟件作出圖形。從圖上可以看出，這個函數(shù)關(guān)系V二f(w)應(yīng)當是一個單調(diào)增加的函數(shù)。因此，擬合的函數(shù)如果不具有這一性質(zhì)的話，就不能作為是好的

25、選擇。一般地，可以假設(shè)函數(shù)f(w)是一個多項式，通常，這個多項式的次數(shù)不要超過3、4次，具體可根據(jù)擬合的效果來定。當然也可以用其它函數(shù)來擬合。為了提高擬合的效果，函數(shù)f(w)還可以用分段函數(shù)來擬合。以下是用分段函數(shù)擬合的結(jié)果：0.0033w4+0.1706w3-2.9727w2+21.3418w-43.0649,v=f(w)=we4.1,16-0.204756w2+9.31526w-74.6265,we16,24擬合函數(shù)圖形是：問題1寫出擬合函數(shù)v二f(w)和作出上面圖形的MATLAB指令。同樣可以擬合人的基礎(chǔ)血液流量與體重之間的函數(shù)關(guān)系v=g(w)，可以用表二中的數(shù)據(jù)來擬合這個函數(shù)。這里用4

26、次多項式來擬合，擬合的結(jié)果是：v=0.000025w4+0.00351W30.1728w2+4.340w16.98,we18,72擬合函數(shù)圖形是：問題2：寫出擬合函數(shù)v=g(w)和作出上面圖形的MATLAB指令。將上面擬合出來的函數(shù)v二f(w)和v二g(w)在它們的公共定義域18,24上的圖形畫出來，如下圖所示。從圖形上可以看出人類與動物之間的差異。人和動物在體重的公共區(qū)間上關(guān)于基礎(chǔ)血液流量函數(shù)的圖形sG=.-._tIk(xlr問題3：寫出作出上面圖形的MATLAB指令。下面考慮動物、人類的體重與基礎(chǔ)脈搏的函數(shù)關(guān)系。假設(shè)人類的體重與基礎(chǔ)脈搏之間的函數(shù)關(guān)系是w=H1(n)，利用表二中的數(shù)據(jù)來擬合

27、這個函數(shù)。這里用3次多項式擬合。擬合的結(jié)果是：w二H(n)二0.0002566n30.143347n2+16.2450n450.216,ne60,961其圖形是：人的基礎(chǔ)脈搏與體重之間的函數(shù)尸片恤;和原始數(shù)據(jù)圖形1jUIIIIIII滯60-2040*riFC1*ifl/3-i-c2*w2+c3*w+c4+原始數(shù)據(jù)0IIIII=_11160657075808590951D0w問題4寫出擬合函數(shù)w=H1(n)和作出上面圖形的MATLAB指令。假設(shè)哺乳動物的體重與基礎(chǔ)脈搏之間的函數(shù)關(guān)系是w=H(n)，利用表五中的數(shù)據(jù)來擬合這個函數(shù)。2這里用分段函數(shù)來擬合。由于當n100w=H2(n)彳7.56493

28、x1012“八2,n4000100.100.30300.150.45500.200.60建立模型的目的選擇拖船的船型和船速，使冰山到達目的地后，可得到的每立方米淡水所花的費用最低，并與海水淡化的費用相比較。根據(jù)建模的目的和搜集到的有限的資料，需要對問題作如下的簡化和假設(shè)：模型假設(shè)拖船航行過程中船速不變，航行不考慮天氣等任何因素的影響，總航行距離為9600千米。山形狀為球形，球面各點融化速率相同。冰山到達目的地后，每立方米冰可融化成0.85立方米水。模型構(gòu)成首先需要知道冰山體積在運輸過程中的變化情況;然后是計算航行過程中的燃料消耗；由此可以算出到達目的地后的冰山體積和運費。在計算過程中需要根據(jù)收

29、集到的數(shù)據(jù)擬合出經(jīng)驗公式。問題：1.理解建模過程中每一步的作用；用MATLAB軟件求解這個模型，寫出相應(yīng)的MATLAB指令。五、水塔流量估計某居民區(qū)有一供居民用水的圓柱形水塔，一般可以通過測量其水位來估計水的流量。但面臨的困難是，當水塔水位下降到設(shè)定的最低水位時，水泵自動啟動向水塔供水，到設(shè)定的最高水位時停止供水，這段時間無法測量水塔的水位和水泵的供水量。通常水泵每天供水一兩次，每次約兩個小時。水塔是一個高12.2米、直徑17.4米的正圓柱。按照設(shè)計，水塔水位降至約8.2米時，水泵自動啟動，水位升到約10.8米時水泵停止工作。下表是某一天的水位測量記錄、試估計任何時刻（包括水泵正供水時）從水塔

30、流出的水流量，及一天的總用水量。時刻（h）00.921.842.953.874.985.907.017.938.97水位（cm）968948931913898881869852839822時刻（h）9.9810.9210.9512.0312.9513.8814.9815.9016.8317.93水位（cm）/108210501021994965941918892時刻（h）19.0419.9620.8422.0122.9623.8824.9925.91水位（cm）866843822/105910351018六、加工工序的問題設(shè)有14件工件等待在一臺機床上加工，某些工件的加工必須安排在另一些工件加

31、工完后才能進行第j件工件工件號j12345678910111213142028251642123210242040243616前期工件號i3，45，7，85，910，113，8，943，5，744，76，7，145，121，2，6（1）.若給出一個加工順序，則確定了每個工件完工的時間（包括等待與加工兩個階段），試設(shè)計一個滿足條件的加工順序，使各個工件完工的時間之和最小。（2）.若第j號工件緊接著第i號工件完工后開工，機床需要準備時間是Ji+j9ij試設(shè)計一個滿足條件的加工順序，使機床花費的總時間最小。（3）.若工件完工時間超過一定時限u，則需支付一定的補嘗費，其數(shù)額等于超過的時間與費用率卩.之i12/14 /14i /14積:工件號j1234567891011121314費用121015161011108541010812對于u=100,t