【正文】 求最小生成樹 ...............................................18 模擬退火法原理 .............................................19 應(yīng)用舉例 ...................................................19 參考文獻(xiàn) ...........................................................20 附 錄 .............................................................22 致 謝 .............................................................23 1 前 言 全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽創(chuàng)辦于 1992 年，每年一屆， 目前已成為全國(guó)高校規(guī)模最大的基礎(chǔ)性學(xué)科競(jìng)賽，也是世界上規(guī)模最大的數(shù)學(xué)建模競(jìng)賽。 賽題一般 涉及面寬 有社會(huì)，經(jīng)濟(jì)，管理，生活，環(huán)境，自然現(xiàn)象，工程技術(shù)，現(xiàn)代科學(xué)中出現(xiàn)的新問(wèn)題等。對(duì)于一些機(jī)理簡(jiǎn)單的問(wèn)題，常常應(yīng)用靜態(tài)、線性或邏輯的方法即可建立模型，使用初等數(shù)學(xué)方法或簡(jiǎn)單的微積分知識(shí)即可求解，此類模型稱之為初等數(shù)學(xué)模型。試在此基礎(chǔ)上，建立數(shù)學(xué)模型并對(duì)所得結(jié)果進(jìn)行評(píng)價(jià) 。22lv =6n mv2 = xmv63 于是單位 時(shí)間行人行走所作的功為 P= E勢(shì) + E動(dòng) = lMgxv8 + xmv63 這是一個(gè)數(shù)學(xué)模型，問(wèn)題轉(zhuǎn)化為欲求： x 為多大時(shí)， P最小。 n= xv2m3 , 其中 P= lMgxv8 + xv2m3 , 同上解得 n=Mgml34≈ 。（ 1+6001 ） 4 x3 =100+100（ 1+6001 ） 1?n 五年末養(yǎng)老金為 x60 =10060)60011(1)60011(1???? =60000? 60)60011( ? 1? 元≈ 元 ②當(dāng)復(fù)利和存款按日計(jì)算時(shí)，記 yk 為第 k天的養(yǎng)老金數(shù)，則每天的存款額為 a= 3651200 ,每天的利率為 r=365002 .第 k+1 天的養(yǎng)老金數(shù)量與第 k天的養(yǎng)老金數(shù)量的關(guān)系為 y 1?k = 3651200+ yk 當(dāng) m 分別取 12 和 365 時(shí)，就是前兩種情況下的計(jì)算公式。 微分方程建模原理和方法 一般來(lái)說(shuō)，任何事變問(wèn)題中隨時(shí)間變化發(fā)生變化的量與其它一些量之間的關(guān)系經(jīng)常以微分方程的形式來(lái)表現(xiàn)。它是針對(duì)液體溶液變化建立的，但它對(duì)氣體和固體濃度變化同樣適用。 刺激按摩充分依賴于各個(gè)學(xué)科領(lǐng)域中有關(guān)實(shí)驗(yàn)定律或規(guī)律以及某些重要的已知定理。如上述問(wèn)題中考察時(shí)間微元 t? ，從 而建立的反應(yīng)溶液濃度隨時(shí)間變化的模型。一般通過(guò)一定的模型假設(shè)近似模擬實(shí)際現(xiàn)象，將問(wèn)題做某些規(guī)范化處理后建立微分方程模型，然后分析，求解再與實(shí)際問(wèn)題作比較，觀察模型能否近似刻畫實(shí)際現(xiàn)象。描述離散型變量之間的關(guān)系的數(shù)學(xué)模型為離散型模型。假設(shè)出生數(shù)及死亡數(shù)與 )(tp 及 dt 均成正比，而且以矩形取代了曲邊梯形的面積。 Malthus 人口模型所說(shuō)的人口并不一定限于人，可以是認(rèn)可一個(gè)生物群體，只要滿足類似的性質(zhì)即可。 顯然，如果能求出（ 3）的根，則可以得到（ 2）的解。 4 數(shù)據(jù)差值與擬合方法 在生產(chǎn)實(shí)踐和科學(xué)研究中，常常有這樣的問(wèn)題：由實(shí)驗(yàn)或測(cè)量得到變量間的一批離散樣點(diǎn)，要求由此建立變量之間的函數(shù)關(guān)系或得到樣點(diǎn)之外的數(shù)據(jù)。我們可以利用拉格朗日插值求方程，根據(jù)它的程序求原方程的圖像。均為 1 次多項(xiàng)式且滿足 0l （ x） =1 且 1l (x)=0。 最小二乘法 在兩個(gè)觀測(cè)量中，往往總有一個(gè)量精度比另一個(gè)高得多，為簡(jiǎn)單起見把精度較高的觀測(cè)量看作沒(méi)有誤差，并把這個(gè)觀測(cè)量選作 x，而把所有的誤差只認(rèn)為是 y 的誤差。若不存在測(cè)量誤差，則這些數(shù)據(jù)點(diǎn)都準(zhǔn)確落在理論曲線上。設(shè)測(cè)量中不存 在著系統(tǒng)誤差，或者說(shuō)已經(jīng)修正，則 y 的觀測(cè)值 yi 圍繞著期望值 f（ x； c1， c2，?? cm） 擺動(dòng)，其分布為正態(tài)分布，則yi 的概率密度為 ? ? ? ?? ? ?????????? ??? 2 2212 , . . . . . . ,。21e xp...2 1 ????? . 取似然函數(shù) L 最大來(lái)估計(jì)參數(shù) C，應(yīng)使 ? ?? ? mi n。 根據(jù)式（ 003）的要求，應(yīng)有 ? ?? ? ? ?mkCxfyc ccNi iiik , . . . ,2,10。 然而，對(duì)擬合的結(jié)果還應(yīng)給予合理的評(píng)價(jià)。 由 x2 分布得知，隨機(jī)變量 2minx 的期望值為 Nm。 14 線性規(guī)劃的一般理論 一般的優(yōu)化問(wèn)題是指用“最好”的方式，使用或分配有限的資源即勞動(dòng)力、原材料、機(jī)器、資金等，使得費(fèi)用最小或利潤(rùn)最大。 在優(yōu)化模型中，如果目標(biāo) 函數(shù) f（ x）和約束條件 gi （ x）都是線性函數(shù)，則該模型稱為線性規(guī)劃。當(dāng)限制條件多，背景比較復(fù)雜時(shí)，可以采用圖示或表格形式列出所有的已知數(shù)據(jù)和信息，從而避免“遺漏”或“重復(fù)”所造成的錯(cuò)誤。 2 選擇條件 有多種可供選擇的可行方案，以便從中選取最優(yōu)方案。 15 n 個(gè)變量的線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式為： Max ?s ??nj jjxc1 (1) ..ts ?? ?nj ijij bxa1 mi ?,3,2,1? (2) jx ≥0 ( ib 是 0? 的常數(shù) ) （ 3） 線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式：簡(jiǎn)記“ LP”問(wèn)題 可通過(guò)以下手段將線性規(guī)劃問(wèn)題的一般形式轉(zhuǎn)化為標(biāo)準(zhǔn)形式： 目標(biāo)函數(shù)轉(zhuǎn)化 若問(wèn)題的目標(biāo)函數(shù)是求其極小值，即求： Min z=c1 x1 +c2 x2 +? + xn 則可轉(zhuǎn)化為求極大值問(wèn)題，即求： max z? =z=( c1 x1 +c2 x2 +? + xn ) 約束條件轉(zhuǎn)換 如果某一約束條件是線性不等式 ?? ?nj ijij bxa1 或（ ?? ?nj ijij bxa1 ）， 則通過(guò)引入松弛變量 x 1?i ? 0，將它轉(zhuǎn)化為 ?? ? ??nj iinjij bxxa1 （或 ?? ? ??nj iinjij bxxa1 ，其中的 x 1?i 也稱為剩余變量） x 1?i ? 0 反之，若有必要，也可等式約束 ?? ?nj ijij bxa1 等價(jià)的轉(zhuǎn)化為兩個(gè)不等式約束，即 ?? ?nj ijij bxa1 或 ?? ?nj ijij bxa1 變量的轉(zhuǎn)換 若某個(gè)變 量的約束條件為 x i ? 1l （或 x i ? 1l ）則可令 jy jx? jl? （或 jy jj xl ?? ）， j y 變?yōu)榉秦?fù)變量 若某個(gè)變量 ix 無(wú)非負(fù)限制（稱為自由變量），則可令 ????????????0, jjjjjxxxxx 代入原問(wèn)題，將自由變量替換掉。問(wèn)應(yīng)如何下料，才能既滿足需要又使原材料消耗最少？ 另外，還有“合理配料問(wèn)題”、“食譜問(wèn)題”等也可歸結(jié)為類似形式。 17 許多難題由于歸結(jié)為圖論問(wèn)題被巧妙地 解決。 圖論的基本概念和簡(jiǎn)單的圖論模型 首先給出圖論中的一些基本概念。 2． 頂點(diǎn)集為 V，邊集為 E 的圖 G 通常記為 G=（ V， E）。 4． 若圖 G 中任意兩個(gè)頂點(diǎn) u、 v 之間都存在連接它們的路，稱 G 為連通圖。樹是最簡(jiǎn)單而最重要的一類圖。 8． 設(shè)對(duì)圖 G=（ V， E）的每一條邊 e 賦予一個(gè)實(shí)數(shù) W（ e），稱為 e 的權(quán)， G 稱為賦權(quán)圖(加權(quán)圖 )。 18 最短軌道問(wèn)題 背景：給定連接若干城市的鐵路網(wǎng)，尋求從指定城市 v0 到各城 v 去的最短道路。實(shí)際上每一步都通過(guò)把至少一個(gè)具有 T 標(biāo)號(hào)的點(diǎn)變成 P 標(biāo)號(hào) (即把一個(gè)不是最短距離標(biāo)號(hào)的頂點(diǎn)變成是最短距離標(biāo)號(hào)的頂點(diǎn) )，這樣最多經(jīng)過(guò) |V(G)|1 步就可完成。令 S(i＋ 1)＝ Si＋ {v(i+1)}。設(shè)計(jì)一個(gè)線路圖，使總造價(jià)最低。 思路：從“邊”著手選最小生成樹。 (2) 從剩下的邊中按 (1)中的排列取下一條邊。則 T 為 G 的最小生成樹。 其步驟如下 (也 稱為 Metropolis 過(guò)程 )： （ 1） 給定初始溫度 T0，及初始點(diǎn)，計(jì)算該點(diǎn)的函數(shù)值 f(x)。 CMCM 97A 題 97 年全國(guó)大學(xué)生數(shù)模競(jìng)賽 A 題 “零件的參數(shù)設(shè)計(jì) ”，可以歸結(jié)為非線性規(guī)劃模型，由于目標(biāo)函數(shù)很復(fù)雜，且又是一個(gè)多維函數(shù)，因此求解比較困難，為應(yīng)用模擬退火法進(jìn)行求解，將 7 個(gè)自變量的取值范圍進(jìn)行離散化，取步長(zhǎng)為 ， 這樣 ， 所有 7 個(gè)變量取值就組成了一個(gè)極為龐大的離散空間 , 而這個(gè)問(wèn)題變成組合優(yōu)化模型。 步 2：步 3 8 循環(huán) K 次 20 步 3：步 47 循環(huán) M 次 步 4：隨機(jī)選擇路線的一段 步 5：隨機(jī)確定將選定的路線反轉(zhuǎn)或移動(dòng)，即兩種調(diào)整方式：反轉(zhuǎn)、移動(dòng)。一念至此，竟有些恍惚，所謂白駒過(guò)隙、百代過(guò)客云云，想來(lái)便是這般惆悵了。我無(wú)愧于這四年的大學(xué)生活，在即將給它畫上句號(hào)的時(shí)候，我還是會(huì)帶著微笑去回憶，這四年我成長(zhǎng)了許多，從那么的稚嫩、懵懂變得成熟穩(wěn)重。我很自豪有這樣一位老師，她值得我感激和尊敬。