全國大學(xué)生數(shù)學(xué)建模競賽常用建模方法探討畢業(yè)論文

1、邯鄲學(xué)院本科畢業(yè)論文邯鄲學(xué)院本科畢業(yè)論文 題題 目目 全國大學(xué)生數(shù)學(xué)建模競賽常用建模方法探討 學(xué)學(xué) 生生 柴云飛 指導(dǎo)教師指導(dǎo)教師 閆峰 教授 年年 級級 2009 級級 專專 業(yè)業(yè) 數(shù)學(xué)與應(yīng)用數(shù)學(xué) 二級學(xué)院二級學(xué)院 數(shù)學(xué)系 （系、部）（系、部） 邯鄲學(xué)院數(shù)學(xué)系學(xué)院（系、部） 2013 年 5 月 鄭重聲明鄭重聲明 本人的畢業(yè)論文（設(shè)計(jì)）是在指導(dǎo)教師 閆峰 的指導(dǎo)下獨(dú)立撰寫完 成的。如有剽竊、抄襲、造假等違反學(xué)術(shù)道德、學(xué)術(shù)規(guī)范和侵權(quán)的行為，本 人愿意承擔(dān)由此產(chǎn)生的各種后果，直至法律責(zé)任，并愿意通過網(wǎng)絡(luò)接受公眾 的監(jiān)督。特此鄭重聲明。 畢業(yè)論文（設(shè)計(jì)）作者（簽名）： 年 月 日 全國大學(xué)生數(shù)學(xué)建

2、模競賽常用建模方法探討全國大學(xué)生數(shù)學(xué)建模競賽常用建模方法探討 摘要 請單擊此處，然后輸入中文摘要內(nèi)容 關(guān)鍵詞：關(guān)鍵詞：數(shù)學(xué)建模競賽 初等方法 建模方法 微分方程 圖論 線性規(guī)劃 commonly used modeling method of the national mathematical contest in modeling chai yunfei directed by professor yanfeng abstract 在此處輸入英文摘要內(nèi)容 key words：mathematical contest elementary method modeling method diff

3、erential equations graph theory linear programming 目目 錄錄 全國大學(xué)生數(shù)學(xué)建模競賽常用建模方法探討.i 前言.1 1 初等數(shù)學(xué)建模方法.2 1.1 走路問題 .2 1.2 銀行復(fù)利問題 .3 2 微分方程建模方法.5 2.1 微分方程建模原理和方法 .5 2.2 人才分配問題模型 .7 3 差分和代數(shù)建模方法.8 3.1 malthus 人口模型.8 3.2 線性差分方程的解法 .9 4 數(shù)據(jù)差值與擬合方法.10 4.1 拉格朗日插值法 .11 4.2 最小二乘法 .12 5 線性規(guī)劃建模方法.14 5.1 線性規(guī)劃的一般理論 .14 5.

4、2 合理下料問題 .16 6 圖論建模方法.17 6.1 圖論的基本概念和簡單的圖論模型 .17 6.2 最短軌道問題 .18 6.3 求最小生成樹 .18 6.4 模擬退火法原理 .19 6.5 應(yīng)用舉例 .19 參考文獻(xiàn).21 附錄.22 致謝.23 前前言言 全國大學(xué)生數(shù)學(xué)建模競賽創(chuàng)辦于 1992 年，每年一屆，目前已成為全國高校規(guī)模最大 的基礎(chǔ)性學(xué)科競賽，也是世界上規(guī)模最大的數(shù)學(xué)建模競賽。競賽題目一般來源于工程技 術(shù)和管理科學(xué)等方面經(jīng)過適當(dāng)簡化加工的實(shí)際問題，不要求參賽者預(yù)先掌握深入的專門 知識，只需要學(xué)過高等學(xué)校的數(shù)學(xué)課程。題目有較大的靈活性供參賽者發(fā)揮其創(chuàng)造能力。 參賽者應(yīng)根據(jù)題目

5、要求，完成一篇包括模型的假設(shè)、建立和求解、計(jì)算方法的設(shè)計(jì)和計(jì) 算機(jī)實(shí)現(xiàn)、結(jié)果的分析和檢驗(yàn)、模型的改進(jìn)等方面的論文。賽題一般涉及面寬-有社會， 經(jīng)濟(jì)，管理，生活，環(huán)境，自然現(xiàn)象，工程技術(shù)，現(xiàn)代科學(xué)中出現(xiàn)的新問題等。一般都 有一個(gè)比較確切的現(xiàn)實(shí)問題。本文將主要介紹一些常用的數(shù)學(xué)建模方法，包括初等數(shù)學(xué) 建模方法、微分方程建模方法、差分和代數(shù)建模方法、數(shù)據(jù)差值與擬合方法、線性規(guī)劃 建模方法、圖論建模方法等。 1 初等數(shù)學(xué)建模方法 在數(shù)學(xué)建模競賽中，常會涉及到初等數(shù)學(xué)建模方法。對于一些機(jī)理簡單的問題，常 常應(yīng)用靜態(tài)、線性或邏輯的方法即可建立模型，使用初等數(shù)學(xué)方法或簡單的微積分知識 即可求解，此類模型稱之

6、為初等數(shù)學(xué)模型。初等數(shù)學(xué)建模方法很多，有比例關(guān)系、狀態(tài) 轉(zhuǎn)移、量綱分析、類比建模等。本章主要列舉了走路問題與銀行復(fù)利問題，問題中涉及 到了一些方法，通過這些知識方法的巧妙應(yīng)用，可以開拓思路，提高分析解決實(shí)際問題 的能力。 1.1 走路問題 人在勻速行走時(shí)，步行多大最省勁？把人行走時(shí)做的功看作是人體重心的勢能和兩 腳運(yùn)動(dòng)的動(dòng)能之和。試在此基礎(chǔ)上，建立數(shù)學(xué)模型并對所得結(jié)果進(jìn)行評價(jià)。 設(shè)人體重 m，腿重為,腿長為 ,步長為，速度為 ，單位時(shí)間內(nèi)步數(shù)為 n. 則mlxv nxv 由已知，人行走時(shí)所作的功是抬高人體重心所需勢能與兩腿運(yùn)動(dòng)所需動(dòng)能之和。 計(jì)算人體重心升高的勢能 將人的行走簡化，設(shè)重心升高為

7、 h,則 lllhcos 2 sin1ll 2 2 4 1 l x 當(dāng)較小時(shí)，取泰勒公式展開式前兩項(xiàng)，得 l x 2 1 ( llh 2 2 8l x ) l x 8 2 于是單位時(shí)間內(nèi)重心升高所需勢能為 e 勢 nmgmghn l x 8 2 l mgxv 8 計(jì)算腿運(yùn)動(dòng)的動(dòng)能 如果將行走視為腿（均為直徑）繞腰部的轉(zhuǎn)動(dòng)，則單位時(shí)間的動(dòng)能為 e=in 動(dòng) 2 1 2 其中 i 為轉(zhuǎn)動(dòng)慣量，i=l =l 1 0 2 r dm 1 0 2 rdr 3 1 3 3 m 2 為角速度，=，ml .所以 l v e=l =mv = 動(dòng) 2 n 3 m 2 2 2 l v 6 n 2 x mv 6 3 于

8、是單位時(shí)間行人行走所作的功為 p= e+ e=+ 勢動(dòng) l mgxv 8x mv 6 3 這是一個(gè)數(shù)學(xué)模型，問題轉(zhuǎn)化為欲求：x 為多大時(shí)，p 最小。 在中，求 p 的駐點(diǎn)，令=0，解得 x=v。由 nx=v,得 dx dp mg ml 3 4 n= mg ml 3 4 若取 m:m=4:1,代入且近似取 l=1(米)，可得 n5,即每秒 5 步，顯然太快了， 模型修改：是腿重集中在腳上，人行走所需動(dòng)能為腳的直線運(yùn)動(dòng)的動(dòng)能，則有 =mv n=,e 動(dòng)能 2 1 2 x v 2 m 3 其中 =+,p l mgxv 8x v 2 m 3 同上解得 =3.這比較符合實(shí)際。n mg ml 3 4 1.

9、2 銀行復(fù)利問題 一個(gè)人為了積累養(yǎng)老金，他每月按時(shí)到銀行存 100 元，銀行的年利率 2，且可以任 意分段按復(fù)利計(jì)算。試問此人 5 年后共積累了多少養(yǎng)老金？如果存款和復(fù)利按日計(jì)算， 則他又有多少養(yǎng)老金？如果復(fù)利和存款連續(xù)計(jì)算呢？試建立數(shù)學(xué)模型并求解。 按月存款和利息時(shí)，每月的利息為= 12 1 100 2 600 1 記 x 為第 k 月末時(shí)的養(yǎng)老金數(shù)，則由題意得 k x =100 1 x =100+100（1+） 2 600 1 x =100+100（1+）+100（1+） 3 600 1 600 1 2 x 100+100（1+）+100（1+） n 600 1 600 1 1n 五年末養(yǎng)

10、老金為 x=100=60000-1元6629.9 元 60 60 ) 600 1 1 (1 ) 600 1 1 (1 60 ) 600 1 1 ( 當(dāng)復(fù)利和存款按日計(jì)算時(shí)，記 y 為第 k 天的養(yǎng)老金數(shù)，則每天的存款額為 a= k ,每天的利率為 r=.第 k+1 天的養(yǎng)老金數(shù)量與第 k 天的養(yǎng)老金數(shù)量的關(guān)系為 365 1200 36500 2 y=+ y (1+r)= + y (1+) 1k 365 1200 k 365 1200 k 36500 2 從第一天開始遞推為 y =a 1 y =a+a(1+r) 2 y = a+a(1+r) +a(1+r) 3 2 y = a+a(1+r) +a

11、(1+r) + a(1+r)=a=-1 n 21n n r r )1 (1 )1 (1 r a n r)1 ( 在 5 年末時(shí)的養(yǎng)老金數(shù)為： （5 年=5365=1825） y=-1=-16614.68 元 1825 r a 1825 )1 (r 365 1200 2 36500 1825 ) 36500 2 1 ( 當(dāng)存款和復(fù)利連續(xù)計(jì)算時(shí)，將 1 年分成 m 個(gè)相等的時(shí)間區(qū)間，則在每個(gè)時(shí)間區(qū)間 中，存款為，每個(gè)區(qū)間的利息為,記第 k 個(gè)區(qū)間養(yǎng)老金的數(shù)目為 z ,類似與前 m 1200 m100 2 k 面分析，5 年后養(yǎng)老金為 z= m5 m 1200 m m m 5 ) 100 2 1 (

12、1 ) 100 2 1 (1 m 1200 1) 100 2 1 ( 2 100 5 m m m =60000（元）=600001) 100 2 1 ( 5 m m 1) 50 1 1 ( 5 m m 令 m,即得連續(xù)存款和利息時(shí)，5 年后的養(yǎng)老金為： z=60000=60000(e-1)元6642.08 元 lim m 1) 100 2 1 ( 5m m 10 1 觀察這三種不同情況下復(fù)利的計(jì)算問題，可以看出，將 1 年份為 m 等份，得出的計(jì) 算公式具有一般性。當(dāng) m 分別取 12 和 365 時(shí)，就是前兩種情況下的計(jì)算公式。另外， 是 m 的單調(diào)函數(shù)，所以計(jì)算間隔越小，5 年后的養(yǎng)老金數(shù)

13、就越多，但不會超過 m m 5 ) 50 1 1 ( 連續(xù)存款和計(jì)息的極限值。 由于存款和計(jì)息的間隔越小時(shí)，收益越大，且不需要一次到銀行存較多的現(xiàn)金而是分 批逐漸存入，對投資者的資金周轉(zhuǎn)有利，所以在銀行按復(fù)利計(jì)算時(shí)，建議存款者盡量采 用小間隔的策略。 2 微分方程建模方法 在大多賽題中，要直接找出某些量之間的關(guān)系往往比較困難，但有時(shí)考慮其微小增 量或變化率與這些變量之間的關(guān)系確是容易的，這種情形下我們常常采用微分關(guān)系式去 描述其關(guān)系。 2.1 微分方程建模原理和方法 一般來說，任何事變問題中隨時(shí)間變化發(fā)生變化的量與其它一些量之間的關(guān)系經(jīng)常 以微分方程的形式來表現(xiàn)?？催@樣一個(gè)問題：有一容器裝有某

14、種濃度的溶液，以流量 v 1注入該容器濃度為 c1的同樣溶液，假定溶液立即被攪拌均勻，并以 v2的流量流出混合 后的溶液，試建立反映容器內(nèi)濃度變化的數(shù)學(xué)模型。 注意到 溶液濃度=溶液體積 溶質(zhì)質(zhì)量 因此，容器中溶液濃度會隨溶質(zhì)質(zhì)量和溶液體積變化而發(fā)生變化。不妨設(shè) t 時(shí)刻容器 中溶質(zhì)質(zhì)量為 s(t)，初始值為 s ,t 時(shí)刻容器中溶液體積為 v（t） ，初始值為 v ，則這段時(shí) 00 間內(nèi)有 （1）ttt, tvtvv tvctvcs 21 2211 其中，c 表示單位時(shí)間內(nèi)注入溶液的濃度，c 表示單位時(shí)間內(nèi)流出溶液的濃度，當(dāng) 12 t 很小時(shí)，在內(nèi)ttt, c = （2） 2 )( )( t

15、v ts tvvv ts )( )( 210 對式（1）兩端同除以，令0，則有tt （3） 00 21 2211 )0(,)0(vvss vv dt dv vcvc dt ds 此即問題的數(shù)學(xué)模型。它是針對液體溶液變化建立的，但它對氣體和固體濃度變化 同樣適用。實(shí)際中，對面許多時(shí)變問題都可取微小的時(shí)間段 t 去考察某些量之間的變化 規(guī)律，從而建立問題的數(shù)學(xué)模型，這是數(shù)學(xué)建模中微分建模常用手段之一。 通過對上述例子的了解，下面介紹幾種常用微分方程建模方法。 （1）按實(shí)驗(yàn)定律或規(guī)律建立的微分方程模型。 刺激按摩充分依賴于各個(gè)學(xué)科領(lǐng)域中有關(guān)實(shí)驗(yàn)定律或規(guī)律以及某些重要的已知定理。 此法建模要求建模者有

16、寬廣的知識視野才能對耨寫具體問題采用某些熟知的實(shí)驗(yàn)定律。 （2）分析微元變化規(guī)律建立微分方程模型。 求解某些實(shí)際問題時(shí)，尋求一些微元之間的關(guān)系可以建立問題的數(shù)學(xué)模型。如上述 問題中考察時(shí)間微元 t ，從而建立的反應(yīng)溶液濃度隨時(shí)間變化的模型。此建模方法的出 發(fā)點(diǎn)是考察某一變量的微小變化，即微元分析，找出其他一些變量與該微元間的關(guān)系式， 從微分定義出發(fā)建立問題的數(shù)學(xué)模型。 （3）近似模擬法。 在許多實(shí)際問題中，有些現(xiàn)象的規(guī)律性并非一目了然，或有所了解亦是復(fù)雜的，這 類問題常用近似模擬方法來建立問題的數(shù)學(xué)模型。一般通過一定的模型假設(shè)近似模擬實(shí) 際現(xiàn)象，將問題做某些規(guī)范化處理后建立微分方程模型，然后分

17、析，求解再與實(shí)際問題 作比較， ，觀察模型能否近似刻畫實(shí)際現(xiàn)象。近似模擬法建模思路是建立能夠近似刻畫或 反映實(shí)際現(xiàn)象的數(shù)學(xué)模型，因此在建模過程中經(jīng)常做一些較合理的模型假設(shè)使問題簡化， 然后通過簡化建立近似反映實(shí)際問題的數(shù)學(xué)模型 2.2 人才分配問題模型 每年大學(xué)畢業(yè)生中都要有一定比例的人員留在學(xué)校充實(shí)教師隊(duì)伍, 其余人員將分配到 國民經(jīng)濟(jì)其他部門從事經(jīng)濟(jì)和管理工作. 設(shè) t 年教師人數(shù)為 ),( 1 tx 科學(xué)技術(shù)和管理人員數(shù)目 為 ),( 2 tx 又設(shè) 1 外教員每年平均培養(yǎng)個(gè)畢業(yè)生, 每年人教育、科技和經(jīng)濟(jì)管理崗位 退休、死亡或調(diào)出人員的比率為 ),10( 表示每年大學(xué)生畢業(yè)生中從事教師

18、職業(yè)所 占比率 ),10( 于是有方程 11 1 xx dt dx (1) 21 2 )1 (xx dt dx (2) 方程(1)有通解 t ecx )( 11 (3) 若設(shè) ,)0( 1 01 xx 則 , 1 01 xc 于是得特解 t exx )(1 01 (4) 將(4)代入(2)方程變?yōu)?t exx dt dx )(1 02 2 )1 ( (5) 求解方程(5)得通解 tt e x ecx )( 1 0 22 )1 ( (6) 若設(shè) ,)0( 2 02 xx 則 , 1 1 0 2 02 xxc 于是得特解 tt exexxx )(1 0 1 0 2 02 11 (7) (4)式和(

19、7)式分別表示在初始人數(shù)分別為 )0(),0( 21 xx 情況, 對應(yīng)于 的取值, 在 t 年教 師隊(duì)伍的人數(shù)和科技經(jīng)濟(jì)管理人員人數(shù). 從結(jié)果看出, 如果取 , 1 即畢業(yè)生全部留在教 育界, 則當(dāng) t 時(shí), 由于 , 必有 )( 1 tx 而 , 0)( 2 tx 說明教師隊(duì)伍將迅速增加. 而科技和經(jīng)濟(jì)管理隊(duì)伍不斷萎縮, 勢必要影響經(jīng)濟(jì)發(fā)展, 反過來也會影響教育的發(fā)展. 如 果將 接近于零. 則 , 0)( 1 tx 同時(shí)也導(dǎo)致 , 0)( 2 tx 說明如果不保證適當(dāng)比例的畢業(yè)生充 實(shí)教師選擇好比率 , 將關(guān)系到兩支隊(duì)伍的建設(shè), 以及整個(gè)國民經(jīng)濟(jì)建設(shè)的大局. 3 差分和代數(shù)建模方法 在一

20、些問題中，許多數(shù)據(jù)都是以等間隔時(shí)間周期統(tǒng)計(jì)的。例如，銀行中的定期存款 是按設(shè)定的時(shí)間等間隔計(jì)息，外貿(mào)出口額按月統(tǒng)計(jì)，國民收入按年統(tǒng)計(jì)，產(chǎn)品的產(chǎn)量按 月統(tǒng)計(jì)，等等。這些量是變量，通常這些變量為離散型變量。描述離散型變量之間的關(guān) 系的數(shù)學(xué)模型為離散型模型。對取值是離散化的經(jīng)濟(jì)變量，差分方程是研究他們之間變 化規(guī)律的有效方法。 3.1 malthus 人口模型 1798 年英國人口學(xué)家和政治經(jīng)濟(jì)學(xué)家馬爾薩斯以兩個(gè)假設(shè)為前提：第一，食物為 人類生存所必須；第二，人的性本能幾乎無法限制，提出了聞名于世的人口指數(shù)增長模 型，即 malthus 人口模型： 人口總數(shù)為 )(tp ,人口的出生率為 b，死亡率

21、為 d。任取時(shí)段【t,t+dt】 ，在此時(shí)段中 的出生人數(shù)為 b )(tp dt，死亡人數(shù)為 d )(tp dt。假設(shè)出生數(shù)及死亡數(shù)與 )(tp 及dt均成正 比，而且以矩形取代了曲邊梯形的面積。在時(shí)段【t,t+dt】中，人口增加量為 )(dttp - )(tp d )(tp ，它應(yīng)等于此時(shí)段中的出生人數(shù)與死亡人數(shù)之差，即 d )(tp =b )(tp dtd )(tp dt=a )(tp dt, 其中a=bd 稱為人口的凈增長率。于是 )(tp 滿足微分方程 dt tdp )( =a )(tp . (1) 若已知初始時(shí)刻t=t0 時(shí)的人口總數(shù)為 p0，那么 )(tp 還滿足初始條件 t=t0

22、 時(shí)， )(tp =p0. (2) 可以求得微分方程(1)滿足初始條件(2)的解為（設(shè)a是常數(shù)） )(tp =p0e )0(tta , (3) 即人口總數(shù)按指數(shù)增長。 模型參數(shù)的意義和作用：t0 為初始時(shí)刻（初始年度） ，p0 為初始年度t0 的人口總數(shù)， a為每年的人口凈增長率，b 為人口出生率，d 為人口死亡率。malthus 人口模型所說的人 口并不一定限于人，可以是認(rèn)可一個(gè)生物群體，只要滿足類似的性質(zhì)即可。 3.2 線性差分方程的解法 方程 )(. 110 nbxaxaxa nkknkn （ 1） 其中 k aaa,., 10 為常數(shù)，稱方程（1）為常系數(shù)線性方程。 又稱方程 0. 1

23、10 nkknkn xaxaxa （2） 為方程（1）對應(yīng)的齊次方程。 如果（2）有形如 n n x 的解，帶入方程中可得： 0. 1 1 10 kk kk aaaa （3） 稱方程（3）為方程（1） 、 （2）的特征方程。 顯然，如果能求出（3）的根，則可以得到（2）的解。 基本結(jié)果如下： 若（3）有 k 個(gè)不同的實(shí)根，則（2）有通解： n kk nn n cccx. 2211 ， 若（3）有 m 重根，則通解中有構(gòu)成項(xiàng)： n m mn cncc).( 1 21 若（3）有一對單復(fù)根 i ，令： i e ， arctan, 22 ， 則（2）的通解中有構(gòu)成項(xiàng)： ncnc nn sincos

24、21 若有 m 重復(fù)根： i ， i e ，則（2）的通項(xiàng)中有成項(xiàng)： nncnccnncncc nm mmm nm m sin).(cos).( 1 221 1 21 綜上所述，由于方程（3）恰有 k 個(gè)根，從而構(gòu)成方程 （9）的通解中必有 k 個(gè)獨(dú)立的任意常數(shù)。通解可記為： n x 如果能得到方程（1）的一個(gè)特解： * n x ，則（1）必有通解： n x n x + * n x （11） （1） 的特解可通過待定系數(shù)法來確定。 例如：如果 )(),()(npnpbnb mm n 為 n 的多項(xiàng)式，則當(dāng) b 不是特征根時(shí)，可設(shè)成 形如 )(nqb m n 形式的特解，其中 )(nqm 為 m

25、 次多項(xiàng)式；如果 b 是 r 重根時(shí)，可設(shè)特解： rnn b )(nqm ，將其代入（8）中確定出系數(shù)即可。 4 數(shù)據(jù)差值與擬合方法 在生產(chǎn)實(shí)踐和科學(xué)研究中，常常有這樣的問題：由實(shí)驗(yàn)或測量得到變量間的一批離 散樣點(diǎn)，要求由此建立變量之間的函數(shù)關(guān)系或得到樣點(diǎn)之外的數(shù)據(jù)。與此有關(guān)的一類問 題是當(dāng)原始數(shù)據(jù) ),( ,),(),( 1100nn yxyxyx 精度較高，要求確定一個(gè)初等函數(shù) )(xpy （一般用多項(xiàng)式或分段多項(xiàng)式函數(shù)）通過已知各數(shù)據(jù)點(diǎn)（節(jié)點(diǎn)） ，即 nixpy ii , 1 , 0, )( ，或要求得函數(shù)在另外一些點(diǎn)（插值點(diǎn)）處的數(shù)值，這便是插值問 題。 4.1 拉格朗日插值法 數(shù)據(jù)建

26、模有兩大方法：一類是插值方法，另一類是擬合函數(shù)一般的說，插值法比較 適合數(shù)據(jù)準(zhǔn)確或數(shù)據(jù)量小的情形。然而 lagrange 插值有很多種，1 階，2 階,n 階。我們 可以利用拉格朗日插值求方程，根據(jù)它的程序求原方程的圖像。下面我具體介紹分析一 下拉格朗日插值的算法設(shè)計(jì)及應(yīng)用。 已知函數(shù) y=f(x)在若干點(diǎn) i x 的函數(shù)值 i y = i xf （i=0,1, ,n）一個(gè)差值問題就是求一 “簡單”的函數(shù) p(x)：p( i x )= i y ,i=0,1, ,n, (1) 則 p(x)為 f(x)的插值函數(shù)，而 f(x)為被插值函數(shù)會插值原函數(shù)， 0 x ， 1 x ， 2 x ，., n

27、x 為 插值節(jié)點(diǎn)，式（1）為插值條件，如果對固定點(diǎn) x求 f( x)數(shù)值解，我們稱 x為一個(gè)插值節(jié) 點(diǎn)，f( x)p( x)稱為 x點(diǎn)的插值，當(dāng) xmin(0 x ， 1 x ， 2 x ，., n x )，max( 0 x ， 1 x ， 2 x ，., n x )時(shí)，稱為內(nèi)插，否則稱為外插式外推，特別地，當(dāng) p(x)為不超過 n 次多項(xiàng)式時(shí)稱為 n 階 lagrange 插值。 線性插值公式 ) 1 ( 1 l ：設(shè)已知 0 x ， 1 x 及 0 y =f( 0 x ) , 1 y =f( 1 x ), )( 1 xl 為不超過一次 多項(xiàng)式且滿足 )( 01 xl = 0 y , )(

28、11 xl = 1 y ,幾何上， )( 1 xl 為過（ 0 x ， 0 y ） ， （ 1 x ， 1 y ）的直線， 從而得到 )( 1 xl = 0 y + 01 01 xx yy （x- 0 x ）. （2） 為了推廣到高階問題，我們將式（2）變成對稱式 )( 1 xl = 0 l （x） 0 y + 1 l (x) 1 y . 其中， 0 l （x）= 10 1 xx xx , 1 l (x)= 01 0 xx xx 。均為 1 次多項(xiàng)式且滿足 0 l （x）=1 且 1 l (x)=0。或 0 l （x）=0 且 1 l (x)=1。 兩關(guān)系式可統(tǒng)一寫成 )( ii xl = j

29、i ji 0 1 。 （3） n 階 lagrange 插值公式 )(xln ：設(shè)已知 0 x ， 1 x ， 2 x ，., n x 及 i y =f( i x )(i=0,1,.,n), )(xln 為不超過 n 次多項(xiàng)式且滿足 iin yxl)( （i=0,1,.n）. 易知 )(xln = 0 l （x） 0 y +.+ )(xln n y . 其中， )(xli 均為 n 次多項(xiàng)式且滿足式（3） （i,j=0,1,.,n）,再由 j x （ji）為 n 次多項(xiàng) 式 )(xli 的 n 個(gè)根知 )(xli =c n ii j j xx 0 .最后，由 1)()( 0 n ij j ji

30、ji xxcxl c= n ij j ji xx 0 )( 1 ,i=0,1,.,n. 總之， )(xln = i n i i yxl 0 )( ， )(xli = . 0 n ij j ji j xx xx 式為 n 階 lagrange 插值公式，其中， )(xli （i=0,1,.n）稱為 n 階 lagrange 插值的基函數(shù)。 4.2 最小二乘法 在兩個(gè)觀測量中，往往總有一個(gè)量精度比另一個(gè)高得多，為簡單起見把精度較高的 觀測量看作沒有誤差，并把這個(gè)觀測量選作 x，而把所有的誤差只認(rèn)為是 y 的誤差。設(shè) x 和 y 的函數(shù)關(guān)系由理論公式 yf（x；c1，c2，cm） （0-0-1） 給

31、出，其中 c1，c2，cm 是 m 個(gè)要通過實(shí)驗(yàn)確定的參數(shù)。對于每組觀測數(shù)據(jù) （xi，yi）i1，2，n。都對應(yīng)于 xy 平面上一個(gè)點(diǎn)。若不存在測量誤差，則這些 數(shù)據(jù)點(diǎn)都準(zhǔn)確落在理論曲線上。只要選取 m 組測量值代入式（0-0-1） ，便得到方程組 yif（x；c1，c2，cm） （0-0-2） 式中 i1，2，m.求 m 個(gè)方程的聯(lián)立解即得 m 個(gè)參數(shù)的數(shù)值。顯然 nm 的情況下，式（0-0-2）成為矛盾方程組，不能直接用解方程的方法求得 m 個(gè)參數(shù)值，只能用曲線擬合的方法來處理。設(shè)測量中不存在著系統(tǒng)誤差，或者說已經(jīng)修 正，則 y 的觀測值 yi 圍繞著期望值 擺動(dòng)，其分布為正態(tài)分 布，則

32、yi 的概率密度為 2 2 21 2 ,.,; exp 2 1 i mii i i cccxfy yp , 式中 i 是分布的標(biāo)準(zhǔn)誤差。為簡便起見，下面用 c 代表（c1，c2，cm） ?？紤]各 次測量是相互獨(dú)立的，故觀測值（y1，y2，cn）的似然函數(shù) n i i i n n cxfy l 1 2 2 21 ; 2 1 exp .2 1 . 取似然函數(shù) l 最大來估計(jì)參數(shù) c，應(yīng)使 min; 1 1 2 2 n i ii i cxfy （0-0-3） 取最小值：對于 y 的分布不限于正態(tài)分布來說，式（0-0-3）稱為最小二乘法準(zhǔn)則。 若為正態(tài)分布的情況，則最大似然法與最小二乘法是一致的。因權(quán)

33、重因子 2 /1 ii ，故 式（0-0-3）表明，用最小二乘法來估計(jì)參數(shù)，要求各測量值 yi 的偏差的加權(quán)平方和為最 小。 根據(jù)式（0-0-3）的要求，應(yīng)有 mkcxfy c cc n i ii ik ,.,2 , 10; 1 1 2 2 從而得到方程組 mk c cxf cxfy cc n i k ii i ,.,2 , 10 ; ; 1 1 2 （0-0-4） 解方程組（0-0-4） ，即得 m 個(gè)參數(shù)的估計(jì)值 m ccc,., 21 ，從而得到擬合的曲線方程 m cccxf,.,; 21 。 然而，對擬合的結(jié)果還應(yīng)給予合理的評價(jià)。若 yi 服從正態(tài)分布，可引入擬合的 x2 量， n i

34、 ii i cxfyx 1 2 2 2 ; 1 （0-0-5） 把參數(shù)估計(jì) m cccc,., 21 代入上式并比較式（0-0-3） ，便得到最小的 x2 值 n i ii i cxfyx 1 2 2 2 min ; 1 （0-0-6） 可以證明， 2 min x 服從自由度 vn-m 的 x2 分布，由此可對擬合結(jié)果作 x2 檢驗(yàn)。 由 x2 分布得知，隨機(jī)變量 2 min x 的期望值為 n-m。如果由式（0-0-6）計(jì)算出 2 min x 接近 n-m（例如 mnx 2 min ） ，則認(rèn)為擬合結(jié)果是可接受的；如果 2 2 min mnx ，則認(rèn) 為擬合結(jié)果與觀測值有顯著的矛盾。 5 線

35、性規(guī)劃建模方法 線性規(guī)劃建模方法主要用于解決生活、生產(chǎn)中的資源利用、人力調(diào)配、生產(chǎn)安排等 問題，它是一種重要的數(shù)學(xué)模型。線性規(guī)劃是運(yùn)籌學(xué)中研究較早、發(fā)展較快、應(yīng)用廣泛、 方法較成熟的一個(gè)重要分支，它是輔助人們進(jìn)行科學(xué)管理的一種數(shù)學(xué)方法，研究線性約 束條件下線性目標(biāo)函數(shù)的極值問題的數(shù)學(xué)理論和方法。 5.1 線性規(guī)劃的一般理論 一般的優(yōu)化問題是指用“最好”的方式，使用或分配有限的資源即勞動(dòng)力、原材料、 機(jī)器、資金等，使得費(fèi)用最小或利潤最大。 優(yōu)化模型的一般形式為: min(或 max) z=f（x） （1） st g（x）0.（i=1,2，m） （2） （x=（x1，x2，xn） t ） 由（1）

36、 、 （2）組成的模型屬于約束優(yōu)化。若只有（1）式就是無約束優(yōu)化。f（x）稱 為目標(biāo)函數(shù)，gi（x）0 稱為約束條件。 在優(yōu)化模型中，如果目標(biāo)函數(shù) f（x）和約束條件 gi（x）都是線性函數(shù)，則該模型稱 為線性規(guī)劃。 實(shí)際問題的線性規(guī)劃模型的步驟： 第一步：設(shè)置要求解的決策變量。決策變量選取得當(dāng)，不僅能順利地建立模型而且 能方便地求解，否則很可能事倍功半。 第二步：找出所有的限制，即約束條件，并用決策變量的線性方程或線性不等式來 表示。當(dāng)限制條件多，背景比較復(fù)雜時(shí)，可以采用圖示或表格形式列出所有的已知數(shù)據(jù) 和信息，從而避免“遺漏”或“重復(fù)”所造成的錯(cuò)誤。 第三步：明確目標(biāo)要求，并用決策變量的線

37、性函數(shù)來表示，標(biāo)出對函數(shù)是取極大還 是取極小的要求。 決策變量的非負(fù)要求可以根據(jù)問題的實(shí)際意義加以確定。 需要特別說明的是： 要使用線性規(guī)劃方法來處理一個(gè)實(shí)際問題，必須具備下面的條件： 1.優(yōu)化條件-問題的目標(biāo)有極大化或極小化的要求,而且能用決策變量的線性函數(shù)來 表示。 2 選擇條件-有多種可供選擇的可行方案，以便從中選取最優(yōu)方案。 3 限制條件-達(dá)到目標(biāo)的條件是有一定限制的（比如，資源的供應(yīng)量有限度等） ，而 且這些限制可以用決策變量的線性等式或線性不等式表示出來。 此外，描述問題的決策變量相互之間應(yīng)有一定的聯(lián)系，有可能建立數(shù)學(xué)關(guān)系，即這 些變量之間是內(nèi)部相關(guān)的，這一點(diǎn)自然是不言而喻的。 為

38、了便于研究線性規(guī)劃問題的理論與一般解法，人們需要將任意一個(gè)線性規(guī)劃問題 化為標(biāo)準(zhǔn)形式。 n 個(gè)變量的線性規(guī)劃問題的標(biāo)準(zhǔn)形式為： max s n j jjx c 1 (1) . .ts n j ijij bxa 1 mi, 3 , 2 , 1 (2) j x 0 ( i b 是 0 的常數(shù)) （3） 線性規(guī)劃問題的標(biāo)準(zhǔn)形式：簡記“l(fā)p”問題 可通過以下手段將線性規(guī)劃問題的一般形式轉(zhuǎn)化為標(biāo)準(zhǔn)形式： 1、目標(biāo)函數(shù)轉(zhuǎn)化 若問題的目標(biāo)函數(shù)是求其極小值，即求： min z=c1x1+c2x2+cnxn 則可轉(zhuǎn)化為求極大值問題，即求： max z =-z=-( c1x1+c2x2+cnxn) 2、約束條件轉(zhuǎn)

39、換 如果某一約束條件是線性不等式 n j ijij bxa 1 或（ n j ijij bxa 1 ） ， 則通過引入松弛變量 x 1i0，將它轉(zhuǎn)化為 n j iinjij bxxa 1 （或 n j iinjij bxxa 1 ，其中的x 1i 也稱為剩余變量） x1i0 反之，若有必要，也可等式約束 n j ijij bxa 1 等價(jià)的轉(zhuǎn)化為兩個(gè)不等式約束，即 n j ijij bxa 1 或 n j ijij bxa 1 3、變量的轉(zhuǎn)換 若某個(gè)變量的約束條件為x i 1 l （或x i 1 l ）則可令 j y j x j l （或 j y jj xl ） ， j y 變?yōu)榉秦?fù)變量 若某

40、個(gè)變量 i x 無非負(fù)限制（稱為自由變量） ，則可令 0, jj jjj xx xxx 代入原問題，將自由變量替換掉。 5.2 合理下料問題 假定有一批某種型號的圓鋼長 8 厘米，需要截成 2.5 厘米的毛坯 100 根，長 1.3 厘米 的毛坯 200 根，問應(yīng)該怎樣選擇下料方式才能既滿足需要又使總用料最少？ 根據(jù)經(jīng)驗(yàn)，可將各種可能的方案列出來， 解 設(shè)決策變量 j x （ 4 , 3 , 2 , 1j ）表示第 j 種方式所用的原材料根數(shù)，則問題的數(shù) 學(xué)模型可歸結(jié)為：求 j x （ 4 , 3 , 2 , 1j ） ，使得 min 4321 xxxxz ).4 , 3 , 2 , 1(0

41、200642 10023 . . 432 321 jx xxx xxx ts j 結(jié)果為： . 0 , 3 100 , 3 100 , 0, 3 200 4321 xxxxz 注：此問題結(jié)果不唯一，即可有多種方案，將結(jié)果應(yīng)用到實(shí)際，由實(shí)際情況所限 （根數(shù)為整數(shù)）也有多種選擇，但最少用 67 根。 考慮：還有沒有其他標(biāo)準(zhǔn)？可以使切割后剩余的總余料最少。此時(shí)，相應(yīng)的模型應(yīng) 為什么？ 這類問題的一般提法是：設(shè)某種原材料截取零件為 n aaa, 21 的毛坯，由以往的經(jīng) 驗(yàn)，在一件原材料上可以有 n bbb, 21 種不同的下料方式，每種下料方式可截得各種毛 坯的個(gè)數(shù)以及每種零件的需要量已經(jīng)給出。問應(yīng)

42、如何下料，才能既滿足需要又使原材料 消耗最少？ 另外，還有“合理配料問題” 、 “食譜問題”等也可歸結(jié)為類似形式。 6 圖論建模方法 圖論作為離散數(shù)學(xué)的一個(gè)重要分支，在工程技術(shù)、自然科學(xué)和經(jīng)濟(jì)管理中的許多方 面都能提供有力的數(shù)學(xué)模型來解決實(shí)際問題，所以吸引了很多研究人員去研究圖論中的 方法和算法。應(yīng)該說，我們對圖論中的經(jīng)典例子或多或少還是有一些了解的，比如，哥 尼斯堡七橋問題、中國郵遞員問題、四色定理等等。圖論方法已經(jīng)成為數(shù)學(xué)模型中的重 要方法。許多難題由于歸結(jié)為圖論問題被巧妙地解決。而且，從歷年的數(shù)學(xué)建模競賽看， 出現(xiàn)圖論模型的頻率極大，比如： amcm90b掃雪問題； amcm91b尋找最

43、優(yōu) steiner 樹； amcm92b緊急修復(fù)系統(tǒng)的研制(最小生成樹) amcm94b計(jì)算機(jī)傳輸數(shù)據(jù)的最小時(shí)間(邊染色問題) cmcm93b足球隊(duì)排名(特征向量法) cmcm94b鎖具裝箱問題(最大獨(dú)立頂點(diǎn)集、最小覆蓋等用來證明最優(yōu)性) cmcm98b災(zāi)情巡視路線(最優(yōu)回路) 等等。這里面都直接或是間接用到圖論方面的知識。要說明的是，這里圖論只是解 決問題的一種方法，而不是唯一的方法。 6.1 圖論的基本概念和簡單的圖論模型 首先給出圖論中的一些基本概念。 1一個(gè)圖 g 由一個(gè)頂點(diǎn)集 v 和一個(gè)邊的集 e 組成。e 中每個(gè)元素 e 是連接頂點(diǎn)集 v 中兩個(gè)頂點(diǎn) u 和 v 的邊，稱 e 與

44、u，v 關(guān)聯(lián)。我們規(guī)定連接兩個(gè)頂點(diǎn) u、v 至多有一條邊， 且一條邊的兩個(gè)頂點(diǎn)不重合，這種圖稱為簡單圖。 2頂點(diǎn)集為 v，邊集為 e 的圖 g 通常記為 g=（v，e） 。圖 g1=（v1，e1）稱為 g 的子圖，如果 v1v， e1e。 3頂點(diǎn) v 的度(或“次”)是指與 v 相關(guān)聯(lián)的邊的個(gè)數(shù)。圖 g 的度數(shù)之和為邊數(shù)的兩 倍。 4若圖 g 中任意兩個(gè)頂點(diǎn) u、v 之間都存在連接它們的路，稱 g 為連通圖。 5w=v0e1v1e2ekvk，其中 eie，vjv，ei 與 vi-1，vi 關(guān)聯(lián)，稱 w 是圖 g 的一 條道路。v0 是起點(diǎn)，vk 是終點(diǎn)；各邊相異的道路叫做行跡，各頂點(diǎn)相異的道路

45、叫做軌道； 起點(diǎn)和終點(diǎn)重合的道路為回路；起點(diǎn)和終點(diǎn)重合的軌道為圈；包含圖中每條邊的回路稱 為 euler 回路；含 euler 回路的圖稱為 euler 圖。 6一個(gè)無圈的連通圖稱為樹。樹是最簡單而最重要的一類圖。樹有下列重要性質(zhì)： 7如果圖 g=（v，e）的子圖 gt=（vt，et）是一個(gè)樹，且 vt=v，稱 g t 是 g 的生成 樹。g 連通的充要條件是 g 有生成樹。生成樹一般而言數(shù)量很大。 8設(shè)對圖 g=（v，e）的每一條邊 e 賦予一個(gè)實(shí)數(shù) w（e） ，稱為 e 的權(quán)，g 稱為賦權(quán) 圖(加權(quán)圖)。假設(shè) g 是連通的賦權(quán)圖，要找 g 的連通子圖 g *=（v，e*） ，使得 w（g*

46、）= ee ew)( 為最小。顯然 g*應(yīng)為 g 的一個(gè)生成樹。g 的權(quán)最小的生成樹稱為 g 的最小生成樹。 6.2 最短軌道問題 背景：給定連接若干城市的鐵路網(wǎng)，尋求從指定城市 v0 到各城 v 去的最短道路。 數(shù)學(xué)模型：圖 g 為一賦權(quán)圖，對任給的 vv(g)，尋求軌道 p(v0,v)，使得 w(p(v0,v)=minw(p),p 取自所有 v0 到 v 的軌道集合 其中 w(p)是軌道 p 上各邊權(quán)之和。 這一問題可用迪克斯特拉(dijkstra)算法解決。 基本思想：從起點(diǎn) v0 開始，逐步尋找到達(dá)各點(diǎn)的最短路，在每一步都對頂點(diǎn)記錄一 個(gè)數(shù)，稱之為該點(diǎn)的標(biāo)號，它表示 v0 到該點(diǎn)的最短

47、距離的上界，或就是 v0 到該點(diǎn)的最 短距離。實(shí)際上每一步都通過把至少一個(gè)具有 t 標(biāo)號的點(diǎn)變成 p 標(biāo)號(即把一個(gè)不是最短 距離標(biāo)號的頂點(diǎn)變成是最短距離標(biāo)號的頂點(diǎn))，這樣最多經(jīng)過|v(g)|-1 步就可完成。 步驟：記 l(v)為 v0 到 v 的距離。 (1) l(v0)=0，l(v) = ，(vv0)；s0=v0，i=0。 (2) 對 vsi，minl(v)，l(vi)+w(viv)代替 l(v)；這樣找到點(diǎn) vi1 使得 l(v)取最小值， v(i1)(si 的余集)。令 s(i1)siv(i+1)。 (3) i=|v(g)|-1 時(shí)停止，否則，i+1，轉(zhuǎn)到(2)。 實(shí)例：cmcm94

48、a公路選址問題。 6.3 求最小生成樹 背景：筑路選線問題 欲修筑連接 n 個(gè)城市的鐵路，已知 i 城與 j 城之間的鐵路造 價(jià)為 cij。設(shè)計(jì)一個(gè)線路圖，使總造價(jià)最低。 分析：選線問題的數(shù)學(xué)模型是在連通加權(quán)圖上求權(quán)最小的連通生成子圖。顯然，權(quán) 最小的連通生成子圖是一個(gè)生成樹，即求取連通加權(quán)圖上的權(quán)最小的生成樹，這就歸結(jié) 為最小生成樹問題。這個(gè)問題可由克羅斯克爾(kruskal)算法解決。 思路：從“邊”著手選最小生成樹。 步驟：設(shè) g 為由 m 個(gè)節(jié)點(diǎn)組成的連通賦權(quán)圖。 (1) 先把 g 中所有的邊按權(quán)值大小由小到大重新排列，并取權(quán)最小的一條邊為樹 t 中的邊。即選 e1e，使得 w(e1)

49、min。 (2) 從剩下的邊中按(1)中的排列取下一條邊。若該邊與前面已取進(jìn) t 中的邊構(gòu)成一個(gè) 回路，則舍棄該邊，否則也把它取進(jìn) t 中。若 e1，e2，ei 已經(jīng)選好，則從 ee1，e2，ei中選取 ei1，使得 ge1，e2，ei，ei+1中無圈，且 w(ei+1) =min。 (3) 重復(fù)步驟(2)，直到 t 中有 m1 條邊為止。則 t 為 g 的最小生成樹。 該算法的復(fù)雜度為 o(eloge)，其中 e 是圖 g 中的邊數(shù)。 6.4 模擬退火法原理 模擬退火法(simulated annealing, sa)是模擬熱力學(xué)中經(jīng)典粒子系統(tǒng)的降溫過程，來求 解極值問題。當(dāng)孤立粒子系統(tǒng)的溫

50、度以足夠慢的速度下降時(shí)，系統(tǒng)近似處于熱力學(xué)平衡 狀態(tài)，最后系統(tǒng)將達(dá)到本身的最低能量狀態(tài)，即基態(tài)，這相當(dāng)于能量函數(shù)的全局極小點(diǎn)。 其步驟如下(也稱為 metropolis 過程)： （1） 給定初始溫度 t0，及初始點(diǎn)，計(jì)算該點(diǎn)的函數(shù)值 f(x)。 （2） 隨機(jī)產(chǎn)生擾動(dòng) x，得到新點(diǎn) x=x+x，計(jì)算新點(diǎn)函數(shù)值 f(x),及函數(shù)值差 f=f(x)-f(x)。 （3） 若 f0，則接受新點(diǎn)，作為下一次模擬的初始點(diǎn)； （4） 若 f0，則計(jì)算新點(diǎn)接受概率：，產(chǎn)生 0，1區(qū) 間上均勻分布的偽隨機(jī)數(shù) r,r0,1 ，如果 p(f)r，則接受新點(diǎn)作為下一次模擬的初始 點(diǎn)；否則放棄新點(diǎn)，仍取原來的點(diǎn)作為下一次模擬的初始點(diǎn)。 6.5 應(yīng)用舉例 1、cmcm91b(通訊網(wǎng)絡(luò)中的極小生成樹)是一個(gè)求 steiner 生成樹問題。 2、cmcm 97a 題 97 年全國大學(xué)生數(shù)模競賽 a 題“零件的參數(shù)設(shè)計(jì)”，可以歸結(jié)為非線性規(guī)劃模型，由 于目標(biāo)函數(shù)很復(fù)雜，且又是一個(gè)多維函數(shù)，因此求解比較困難，為應(yīng)用模擬退火法進(jìn)行 求解，將 7 個(gè)自