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