【正文】 ?? 2 2212 , . . . . . . ,。為簡便起見，下面用 C 代表（ c1， c2，?? cm）。21e xp...2 1 ????? . 取似然函數(shù) L 最大來估計參數(shù) C，應(yīng)使 ? ?? ? mi n。若為正態(tài)分布的情況，則最大似然法與最小二乘法是一致的。 根據(jù)式（ 003）的要求，應(yīng)有 ? ?? ? ? ?mkCxfyc ccNi iiik , . . . ,2,10。1 ?1 2 ????? ??? ? （ 004） 解方程組（ 004），即得 m 個參數(shù)的估計值 mccc ?,...,?,? 21 ，從而得到擬合的曲線方程? ?mcccxf ?,...,?,?。 然而，對擬合的結(jié)果還應(yīng)給予合理的評價。1? （ 005） 把參數(shù)估計 ? ?mcccc ?,...,?,?? 21? 代入上式并比較式（ 003），便得到最小的 x2 值 ? ?? ??? ??Ni iii cxfyx 1222m i n ?。 由 x2 分布得知，隨機(jī)變量 2minx 的期望值為 Nm。 5 線性規(guī)劃建模方法 線性規(guī)劃建模方法 主要用于解決生活、生產(chǎn)中的資源利用、人力調(diào)配、生產(chǎn)安排等問題，它是一種重要的數(shù)學(xué)模型。 14 線性規(guī)劃的一般理論 一般的優(yōu)化問題是指用“最好”的方式，使用或分配有限的資源即勞動力、原材料、機(jī)器、資金等，使得費(fèi)用最小或利潤最大。若只有（ 1）式就是無約束優(yōu)化。 在優(yōu)化模型中，如果目標(biāo) 函數(shù) f（ x）和約束條件 gi （ x）都是線性函數(shù)，則該模型稱為線性規(guī)劃。決策變量選取得當(dāng)，不僅能順利地建立模型而且能方便地求解，否則很可能事倍功半。當(dāng)限制條件多，背景比較復(fù)雜時，可以采用圖示或表格形式列出所有的已知數(shù)據(jù)和信息，從而避免“遺漏”或“重復(fù)”所造成的錯誤。 決策變量的非負(fù)要求可以根據(jù)問題的實際意義加以確定。 2 選擇條件 有多種可供選擇的可行方案，以便從中選取最優(yōu)方案。 此外，描述問題的決策變量相互之間應(yīng)有一定的聯(lián)系，有可能建立 數(shù)學(xué)關(guān)系，即這些變量之間是內(nèi)部相關(guān)的，這一點(diǎn)自然是不言而喻的。 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 代入原問題，將自由變量替換掉。 考慮：還有沒有其他標(biāo)準(zhǔn)？可以使切割后剩余的總余料最少。問應(yīng)如何下料，才能既滿足需要又使原材料消耗最少？ 另外，還有“合理配料問題”、“食譜問題”等也可歸結(jié)為類似形式。應(yīng)該說，我們對圖論中的經(jīng)典例子或多或少還是有一些了解的，比如，哥尼斯堡七橋問題、中國郵遞員問題、四色定理等等。 17 許多難題由于歸結(jié)為圖論問題被巧妙地 解決。這里面都直接或是間接用到圖論方面的知識。 圖論的基本概念和簡單的圖論模型 首先給出圖論中的一些基本概念。 E 中每個元素 e 是連接頂點(diǎn)集 V中兩個頂點(diǎn) u 和 v 的邊 ，稱 e 與 u， v 關(guān)聯(lián) 。 2． 頂點(diǎn)集為 V，邊集為 E 的圖 G 通常記為 G=（ V， E）。 3．頂點(diǎn) v 的度 (或“次” )是指與 v 相關(guān)聯(lián)的邊的個數(shù)。 4． 若圖 G 中任意兩個頂點(diǎn) u、 v 之間都存在連接它們的路，稱 G 為連通圖。 v0 是起點(diǎn)， vk 是終點(diǎn)；各邊相異的道路叫做行跡，各頂點(diǎn)相異的道路叫做軌道；起點(diǎn)和終點(diǎn)重合的道路為回路；起點(diǎn)和終點(diǎn)重合的軌道為圈；包含圖中每條邊的回路稱為Euler 回路；含 Euler 回路的圖稱為 Euler 圖。樹是最簡單而最重要的一類圖。G 連通的充要條件是 G 有生成樹。 8． 設(shè)對圖 G=（ V， E）的每一條邊 e 賦予一個實數(shù) W（ e），稱為 e 的權(quán)， G 稱為賦權(quán)圖(加權(quán)圖 )。顯然 G*應(yīng)為 G 的一個生成樹。 18 最短軌道問題 背景：給定連接若干城市的鐵路網(wǎng)，尋求從指定城市 v0 到各城 v 去的最短道路。 這一問題可用迪克斯特拉 (Dijkstra)算法解決。實際上每一步都通過把至少一個具有 T 標(biāo)號的點(diǎn)變成 P 標(biāo)號 (即把一個不是最短距離標(biāo)號的頂點(diǎn)變成是最短距離標(biāo)號的頂點(diǎn) )，這樣最多經(jīng)過 |V(G)|1 步就可完成。 (1) l(v0)=0， l(v) = ?， (v?v0)； S0={v0}， i=0。令 S(i＋ 1)＝ Si＋ {v(i+1)}。 實例： CMCM94A－公路選址問題。設(shè)計一個線路圖，使總造價最低。顯然，權(quán)最小的連通生成子圖是一個生 成樹，即求取連通加權(quán)圖上的權(quán)最小的生成樹， 這就歸結(jié)為最小生成樹問題 。 思路：從“邊”著手選最小生成樹。 (1) 先把 G 中所有的邊按權(quán)值大小由小到大重新排列，并取權(quán)最小的一條邊為樹 T 中的邊。 (2) 從剩下的邊中按 (1)中的排列取下一條邊。若 e1， e2，?， ei 已經(jīng)選好，則從 E－ {e1， e2，?，ei}中選取 ei＋ 1，使得 G[{e1， e2，?， ei， ei+1}]中無圈，且 w(ei+1)=min。則 T 為 G 的最小生成樹。 19 模擬退火法原理 模擬退火法 (Simulated annealing, SA)是模擬熱力學(xué)中經(jīng)典粒子系統(tǒng)的降溫過程，來求解極值 問題 。 其步驟如下 (也 稱為 Metropolis 過程 )： （ 1） 給定初始溫度 T0，及初始點(diǎn)，計算該點(diǎn)的函數(shù)值 f(x)。 （ 3） 若 Δf≤0，則接受新點(diǎn)，作為下一次模擬的初始點(diǎn)； （ 4） 若 Δf0，則計算新點(diǎn)接受概率： ，產(chǎn)生 ［ 0， 1］區(qū)間上均勻分布的偽隨機(jī)數(shù) r,r∈ ［ 0,1］，如果 p(Δf)≥r，則接受新點(diǎn)作為下一次模擬的初始點(diǎn)；否則放棄新點(diǎn)，仍取原來的點(diǎn)作為下一次模擬的初始點(diǎn)。 CMCM 97A 題 97 年全國大學(xué)生數(shù)模競賽 A 題 “零件的參數(shù)設(shè)計 ”，可以歸結(jié)為非線性規(guī)劃模型，由于目標(biāo)函數(shù)很復(fù)雜，且又是一個多維函數(shù)，因此求解比較困難，為應(yīng)用模擬退火法進(jìn)行求解，將 7 個自變量的取值范圍進(jìn)行離散化，取步長為 ， 這樣 ， 所有 7 個變量取值就組成了一個極為龐大的離散空間 , 而這個問題變成組合優(yōu)化模型。 CMCM 98B 題 98 年全國大學(xué)生數(shù)學(xué)建模競賽 B 題 “水災(zāi)巡視問題 ”，是一個推銷員問題，本題有 53個點(diǎn)，所有可能性大約為 exp(53),目前沒有好 方法求出精確解，既然求不出精確解，我們使用模擬退火法求出一個較優(yōu)解 ， 將所有結(jié)點(diǎn)編號為 1 到 53， 1 到 53 的排列就是系統(tǒng)的結(jié)構(gòu) ， 結(jié)構(gòu)的變化規(guī)則是 ： 從 1 到 53 的排列中隨機(jī)選取一個子排列 ， 將其反轉(zhuǎn)或?qū)⑵湟浦亮硪惶?， 能量 E 自然是路徑總長度。 步 2：步 3 8 循環(huán) K 次 20 步 3：步 47 循環(huán) M 次 步 4：隨機(jī)選擇路線的一段 步 5：隨機(jī)確定將選定的路線反轉(zhuǎn)或移動，即兩種調(diào)整方式：反轉(zhuǎn)、移動。附錄中的圖 、 表 、 公式 、 參考文獻(xiàn) 另編排序號，與正文分開 ， 一律用阿拉伯?dāng)?shù)字編碼，但在編碼前冠以附錄序碼，如：圖 A1；表B2；式 (B3)；文獻(xiàn) [A5]等 。一念至此，竟有些恍惚，所謂白駒過隙、百代過客云云，想來便是這般惆悵了。大學(xué)四年， 雖然讀的是一所二流的大學(xué)，而且處在一個大學(xué)生泛濫的時代，我們的學(xué)歷顯得那么的微不足道，但是我依然踏踏實實的過完了這四年。我無愧于這四年的大學(xué)生活，在即將給它畫上句號的時候，我還是會帶著微笑去回憶，這四年我成長了許多，從那么的稚嫩、懵懂變得成熟穩(wěn)重。 我在這里首先要感謝的是我的學(xué)位論文指導(dǎo) 老師 —— 閆峰 老師。我很自豪有這樣一位老師，她值得我感激和尊敬。感謝數(shù)學(xué)系 的所有授課老師， 以及實習(xí)學(xué)校的指導(dǎo)老師， 你們使我終身受益。