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