【正文】 感謝所有關心、鼓勵、支持我的家人、親戚和朋友。 感謝和我共度四年美好大學生活的 2020 級數(shù)學系本科班的全體同學。這篇畢業(yè)論文從開題、資料查找、修改到最后定稿，如果沒有她的心血，尚不知以何等糟糕的面目出現(xiàn)。我會始終帶著感恩去銘記這里，去銘記我的恩師們，你們辛苦了。從開始的新奇，到后來的迷茫，再到后來的堅定和努力。 可是悵然之后，總要說些什么。 23 致 謝 四年的大學生活轉眼就要說再見了， 當自己終 于可以從考研、找工作、畢業(yè)論文的壓力下解脫出來，長長地吁出一口氣時，我忽然間才意識到，原來四年已經(jīng)過去，到了該告別的時候了。 步 6：計算代價 D，即調整前后的總路程的長度之差 步 7：按照如下規(guī)則確定是否做調整： 如果 D0， 則調整 如果 D0， 則按照 EXP(D/T)的概率進行調整 步 8： T*T， 降溫 參考文獻 [1] 姜啟源等編著 .數(shù)學模型［ M］ .北京：高等教育出版社， 2020 [2] 徐全智 ， 楊晉浩編 著 .數(shù)學建模入門 ［ M］ .四川： 成都電子科大出版社， 1996 [3] 劉來福，曾文藝編著 .問題解決的數(shù)學模型方法 ［ M］ .北京： 北京師范大學出版社，1999 [4] 朱道元等編著 .數(shù)學建模案例精選 [M].北京：科學出版社， 2020 [5] 齊歡編著 .數(shù)學模型方法 ［ M］ .武漢： 華中理工大學出版社， 1996 [6] 汪國強 編著 .數(shù)學建模優(yōu)秀案例選編 [M].廣州： 華南理工大學出版社， 1998 21 [7] 華羅庚，王 元編著． 數(shù)學模型選談 ［ M］ ．湖南： 湖南教育出版社 ， 1991 [8] Saaty TL. The Analytic Hierarchy Process ［ M］ .Mcgraw 2 Hill,1980 [9] 楊學楨 .數(shù)學建模方法 [M].保定：河北大學出版社， 2020 [10]王高雄，周之銘，朱思銘，王壽松 .常微分方程 [M].北京：高等教育出版社， 1983 [11]王興宇，樊愷 .數(shù)學模型方法 [M].武漢：華中理工大學出版社， 1996 22 附 錄 論文的附錄依序編排為附錄 A，附錄 B… 。具體算法描述如下： 步 1： 設定初始溫度 T，給定一個初始的巡視路線。 這個問題算法 的 狀態(tài)調整規(guī)則是：每次從 7 個自變量中隨機選取 14 個，讓選取的自變量隨機移動，考慮選取的自變量在兩個方向移動組合，從中選取最佳的作為候選者，自變量移動的距離隨著溫度的降低而減少，為避免陷入局部極小，可以 從多個隨機選取的初始值開始計算 ，算法的其它步驟同上 。 應用舉例 CMCM91B(通訊網(wǎng)絡中的極小生成樹 )是一個求 STEINER 生成樹問題 。 （ 2） 隨機產生擾動 Δx，得到新點 x′=x+Δx，計算新點函數(shù)值 f(x′),及函數(shù)值差Δf=f(x′)f(x)。當孤立粒子系統(tǒng)的溫度以足夠慢的速度下降時，系統(tǒng)近似處于熱力學平衡狀態(tài)，最后系統(tǒng)將達到本身的最低能量狀態(tài)，即基態(tài)，這相當于能量函數(shù)的全局極小點。 該算法的復雜度為 O(eloge)，其中 e 是圖 G 中的邊數(shù)。 (3) 重復步驟 (2)，直到 T 中有 m－ 1 條邊為止。若該邊與前面已取進 T 中的邊構成一個回路，則舍棄該邊，否則也把它取進 T 中。即選 e1?E，使得 w(e1)＝ min。 步驟：設 G 為由 m個節(jié)點組成的連通賦權圖。這個問題可由克羅斯克爾 (Kruskal)算法解決。 分析：選線問題的數(shù)學模型是在連通加權圖上求權最小的連通生成子圖。 求最小生成樹 背景：筑路選線問 題 欲修筑連接 n 個城市的鐵路，已知 i 城與 j 城之間的鐵路造價為 Cij。 (3) i=|V(G)|1 時停止，否則， i+1，轉到 (2)。 (2) 對 v?Si， min{l(v)， l(vi)+w(viv)}代替 l(v)；這樣找到點 vi＋ 1 使得 l(v)取最小值，v(i＋ 1)?(Si 的余集 )。 步驟：記 l(v)為 v0 到 v 的距離。 基本思想：從起點 v0 開始，逐步尋找到達各點的最短路，在每一步都對頂點記錄一個數(shù)，稱之為該點的標號，它表示 v0 到該點的最短距離的上界，或就是 v0 到該點的最短距離。 數(shù)學模型：圖 G 為一賦權圖，對任給的 v?V(G)，尋求軌道 P(v0,v)，使得 W(P(v0,v))=min{W(P),P 取自所有 v0 到 v 的軌道集合 } 其中 W(P)是軌道 P 上各邊權之和。 G 的權最小的生成樹稱為 G 的最小生成樹。 假設 G 是連通的賦權圖，要找 G 的連通子圖 G *=（ V， E*），使得 W（ G*） =??Ee eW )(為最小。生成樹一般而言數(shù)量很大。樹有下列重要性 質： 7． 如果圖 G=（ V， E）的子圖 Gt=（ Vt， Et）是一個樹，且 Vt=V，稱 G t 是 G 的生成樹。 6． 一個無圈的連通圖稱為樹。 5． W=v0e1v1e2…… ekvk，其中 ei?E， vj?V， ei 與 vi1， vi 關聯(lián)，稱 W 是圖 G 的一條道路。圖 G 的度數(shù)之和為邊數(shù)的兩倍。圖 G1=（ V1， E1）稱為 G的子圖，如果 V1 V， E1 E。我們規(guī)定連接兩個頂點 u、 v 至多有一條邊，且一條邊的兩個頂點不重合，這種圖稱為簡單圖。 1． 一個圖 G 由一個頂點集 V和一個邊的集 E 組成。要說明的是，這里圖論只是解決問題的一種方法，而不是唯一的方法。 而且，從歷年的數(shù)學建模競賽看，出現(xiàn)圖論模型的頻率極大，比如： AMCM90B－掃雪問題； AMCM91B－尋找最優(yōu) Steiner 樹； AMCM92B－緊急修復系統(tǒng)的研制 (最小生成樹 ) AMCM94B－計算機傳輸數(shù)據(jù)的最小時間 (邊染色問題 ) CMCM93B－足球隊排名 (特征向量法 ) CMCM94B－鎖具 裝箱問題 (最大獨立頂點集、最小覆蓋等用來證明最優(yōu)性 ) CMCM98B－災情巡視路線 (最優(yōu)回路 ) 等等。 圖論方法已經(jīng)成為數(shù)學模型中的重要方法。 6 圖論建模方法 圖論作為離散數(shù)學的一個重要分支，在工程技術、自然科學和經(jīng)濟管理中的許多方面都能提供有力的數(shù)學模型來解決實際問題，所以吸引了很多研究人員去研 究圖論中的方法和算法。此時，相應的模型應為什么？ 這類問題的一 般提法是：設某種原材料截取零件為 nAAA , 21 ? 的毛坯，由以往的經(jīng)驗，在一件原材料上可以有 nBBB ?, 21 種不同的下料方式，每種下料方式可截得各種毛坯的個數(shù)以及每種零件的需要量已經(jīng)給出。 16 合理下料問題 假定有一批某種型號的圓鋼長 8 厘米，需要截成 厘米的毛坯 100 根，長 厘米的毛坯 200 根，問應該怎樣選擇下料方式才能既滿足需要又使總用料最少？ 根據(jù)經(jīng)驗，可將各種可能的方案列出來， 解 設決策變量 jx （ 4,3,2,1?j ）表示第 j 種方式所用的原材料根數(shù)，則問題的數(shù)學模型可歸結為：求 jx （ 4,3,2,1?j ），使得 min 4321 xxxxz ???? ?????????????).4,3,2,1(020204210023.. 432321jxxxxxxxtsj 結果為： .0,3100,3100,0,3200 4321 ????? xxxxz 注：此問題結果不唯一，即可有多種方案，將結果應用到實際，由實際情況所限（根數(shù)為整數(shù)）也有多種選擇，但最少用 67 根。 為了便于研究線性規(guī)劃問題的理論與一般解法，人們需要將任意一個線性規(guī)劃問題化為標準形式。 3 限制條件 達到目標的條件是有一定限制的（比如，資源的供應量有限度等），而且這些限制可以用決策變量的線性等式或線性不等式表示出來。 需要特別說明的是： 要使用線性規(guī)劃方法來處理一個實際問題，必須具備下面的條件： 問題的目標有極大化或極小化的要求 ,而且能用決策變量的線性函數(shù)來表示。 第三步：明確目標要求，并用決策變量的線性函數(shù)來表示，標出對函數(shù)是取極大還是取極小的要求。 第二步：找出所有的限制，即約束條件，并用決策變量的線性 方程或線性不等式來表示。 實際問題的線性規(guī)劃模型的步驟： 第一步：設置要求解的決策變量。 f（ x）稱為目標函數(shù)， gi （ x）≤ 0 稱為約束條件。 優(yōu)化模型的一般形式為 : min(或 max) z=f（ x） （ 1） s． t g（ x）≤ 0.（ i=1,2，?， m） （ 2） （ x=（ x1 ， x2 ，?， xn ） T ） 由（ 1）、（ 2）組成的模型屬于約束優(yōu)化。線性規(guī)劃是運籌學中研究較早、發(fā)展較快、應用廣泛、方法較成熟的一個重要分支，它是輔助人們進行科學管理的一種數(shù)學方法，研究線性約束條件下線性目標函數(shù)的極值問題的數(shù)學理論和方法。如果由式（ 006）計算出 2minx 接近Nm（例如 mNx ??2min ），則認為擬合結果是可接受的；如果 22m in ??? mNx ，則認為擬合結果與觀測值有顯著的矛盾。1? （ 006） 可以證明， 2minx 服從自由度 v＝ Nm的 x2 分布，由此可對擬合結果作 x2 檢驗。若 yi 服從正態(tài)分布，可引入擬合的 x2 量， ? ?? ??? ??Ni iii Cxfyx 1222 。 21 。1 ?1 22 ???? ? ??? ? 從而得到方程組