1、邯鄲學院本科畢業論文題 目 全國大學生數學建模競賽常用建模方法探討學 生 柴云飛指導教師 閆 峰 教授年 級 2009級本科專 業 數學與應用數學二級學院 數學系（系、部）邯鄲學院數學系2013年6月 鄭重聲明本人的畢業論文是在指導教師閆峰的指導下獨立撰寫完成的如有剽竊、抄襲、造假等違反學術道德、學術規范和侵權的行為，本人愿意承擔由此產生的各種后果，直至法律責任，并愿意通過網絡接受公眾的監督特此鄭重聲明論文經“中國知網”論文檢測系統檢測，總相似比為5.80% 畢業論文作者（簽名）： 年 月 日全國大學生數學建模競賽常用建模方法探討摘要全國大學生數學建模競賽作為全國高校規模最大的基礎性學科競賽，

2、越來越受到人們的重視，所以建模競賽的方法也就變得尤為重要隨著競賽的不斷發展，賽題的開放性逐步增大，一道賽題可用多種解法，各種求解的算法有時會相互融合，同時也在向大規模數據處理方向發展，這就對選手的能力提出了更高的要求由于建模方法種類眾多，無法一一介紹，所以本文主要介紹了四種比較常用的數學建模競賽方法，包括微分與差分方程建模方法、數學規劃建模方法、統計學建模方法、圖論方法，并結合歷年賽題加以說明關鍵詞：數學建模競賽 統計學方法 數學規劃 圖論Commonly Used Modeling Method of China Undergraduate Mathematical Contest in M

3、odeling Chai yunfei Directed by Professor Yan fengABSTRACTThe China undergraduate mathematical contest in modeling has been attention by more and more people as a basic subject of the largest national college competition. The method of modeling competition has become more and more important. Op

4、en questions gradually increased with the development of competition. Most of the games can be solved by lots of solutions. Sometimes these methods can be used together. And there is also a lot of data which puts forward higher requirement on the ability of players. The modeling methods is too numer

5、ous to mention, so this article mainly four kinds Commonly used modeling method are introduced that differential and difference equations modeling method, Mathematical programming modeling method, Statistics modeling method, graph theory and interprets with calendar years test questions.KEY WORDS：Ma

6、thematical contest in modeling Statistics method Mathematical programming Graph theory目 錄摘 要I英文摘要II 前言11 微分方程與差分方程建模21.1 微分方程建模2 微分方程建模的原理和方法2 微分方程建模應用實例31.2 差分方程建模4 差分方程建模的原理和方法4 差分方程建模應用實例52 數學規劃建模52.1 線性規劃建模的一般理論62.2 線性規劃建模應用實例73 統計學建模方法83.1 聚類分析8 聚類分析的原理和方法8 聚類分析應用實例83.2 回歸分析9 回歸分析的原理與方法9 回歸分析應用

7、實例104 圖論建模方法104.1 兩種常見圖論方法介紹11 模擬退火法的基本原理11 最短路問題114.2 圖論建模應用實例125 小結13參考文獻14致謝15前言全國大學生數學建模競賽創辦于1992年，每年一屆，目前已成為全國高校規模最大的基礎性學科競賽，也是世界上規模最大的數學建模競賽參賽者需要根據題目要求，在三天時間內完成一篇包括模型假設、模型建立和求解、計算方法的設計和實現、模型結果的分析和檢驗、模型的改進等方面的論文通過參加競賽的訓練和比賽，可以提高學生用數學方法解決實際問題的意識和能力，而且在培養團隊精神和撰寫科技論文等方面都會得到十分有益的鍛煉競賽題目的涉及面比較寬，有工業、農

8、業、工程設計、交通運輸、經濟管理、生物醫學和社會事業等競賽選手不一定預先掌握深入的專業知識，而只需要學過高等數學的相關課程即可，并且題目具有較大的靈活性，便于參賽者發揮其創造能力近年來，競賽題目包含的數據較多，手工計算一般不能實現，所以就對參賽者的計算機能力提出了更高的要求，如2003年B題，某些問題的解決需要使用計算機軟件；2001年A題，問題的數據讀取需要計算機技術，并且對于給出的圖像，需要用圖像處理的方法獲得；再如2004年A題則需要利用數據庫數據，數據庫方法，統計軟件包等等競賽題目的總體特點可大致歸納如下：（1）實用性不斷加強，問題和數據來自于實際，解決方法需要切合實際，模型和結果可以

9、應用于實際；（2）綜合性不斷加強，解法多樣，方法融合，學科交叉；（3）數據結構越來越復雜，包括數據的真實性，數據的海量性，數據的不完備性，數據的冗余性等；（4）開放性也越來越突出，題意的開放性，思路的開放性，方法多樣，結果不唯一等總體來說，賽題向大規模數據處理方向發展，求解算法和各類現代算法相互融合縱觀歷年的賽題，主要用到的建模方法有：初等數學模型、微分與差分方程建模、組合概率、數據處理、統計學建模、計算方法建模、數學規劃、圖論方法、層次分析、插值與擬合、排隊論、模糊數學、隨機決策、多目標決策、隨機模擬、計算機模擬法、灰色系統理論、時間序列等本文不一一列舉競賽題目中涉及的所有方法，只是重點討論

10、其中一些比較常用的方法，包括微分與差分方程建模方法、數學規劃建模方法、統計學建模方法、圖論建模方法，并結合案例說明建模方法的原理及應用1 微分方程與差分方程建模在很多競賽題目中，常常會涉及很多變量之間的關系，找出它們之間的函數關系式具有重要意義可在許多實際問題中，我們常常不能直接給出所需要的函數關系，但可以得到含有所求函數的導數（或微分）或差分（即增量）的方程，這樣的方程稱為微分方程或差分方程. 建立微分方程或差分方程的數學模型是一種重要的建模方法.如1996年A題“最優捕魚策略”，1997年A題“零件參數設計”，2003年A題“SARS的傳播”，2007年A題“中國人口增長預測”，2009年

11、A題“最優捕魚策略”等賽題中，都用到了這種方法1.1 微分方程建模1.1.1 微分方程建模的原理和方法一般來說，任何時變問題中隨時間變化而發生變化的量與其它一些量之間的關系經常以微分方程的形式來表現例1.1 有一容器裝有某種濃度的溶液，以流量注入該容器濃度為的同樣溶液，假定溶液立即被攪拌均勻，并以的流量流出混合后的溶液，試建立反映容器內濃度變化的數學模型解 注意到溶液濃度=，因此，容器中溶液濃度會隨溶質質量和溶液體積變化而發生變化不妨設t時刻容器中溶質質量為，初始值為,時刻容器中溶液體積為，初始值為，則這段時間內有， （1）其中表示單位時間內注入溶液的濃度，表示單位時間內流出溶液的濃度，當很小

12、時，在內有. （2）對式（1）兩端同除以，令，則有. （3）即所求問題的微分方程模型雖然它是針對液體溶液變化建立的，但對氣體和固體濃度變化同樣適用實際應用中，許多時變問題都可取微小的時間段去考察某些量之間的變化規律，從而建立問題的數學模型，這是數學建模中微分方程建模常用手段之一常用微分方程建模的方法主要有：（1）按實驗定律或規律建立微分方程模型此種建模方法充分依賴于各個學科領域中有關實驗定律或規律以及某些重要的已知定理，這種方法要求建模者有寬廣的知識視野,這樣才能對具體問題采用某些熟知的實驗定律（2）分析微元變化規律建立微分方程模型求解某些實際問題時，尋求一些微元之間的關系可以建立問題的數學模

13、型如例1.1中考察時間微元，從而建立起反應溶液濃度隨時間變化的模型此建模方法的出發點是考察某一變量的微小變化，即微元分析，找出其他一些變量與該微元間的關系式，從微分定義出發建立問題的數學模型（3）近似模擬法在許多實際問題中，有些現象的規律性并非一目了然，或有所了解亦是復雜的，這類問題常用近似模擬方法來建立問題的數學模型一般通過一定的模型假設近似模擬實際現象，將問題做某些規范化處理后建立微分方程模型，然后分析、求解，并與實際問題作比較，觀察模型能否近似刻畫實際現象近似模擬法的建模思路就是建立能夠近似刻畫或反映實際現象的數學模型，因此在建模過程中經常做一些較合理的模型假設使問題簡化，然后通過簡化建

14、立近似反映實際問題的數學模型1.1.2 微分方程建模應用實例例1.2（2003年高教社杯全國大學生數學建模競賽A題） SARS傳播的預測2003年爆發的“SARS”疾病得到了許多重要的經驗和教訓，使人們認識到研究傳染病的傳播規律的重要性題目給出了感病情況的三個附件，要求對SARS的傳播建立數學模型：（1）對SARS的傳播建立一個自己的模型，并說明模型的優缺點；（2）收集SARS對經濟某個方面影響的數據，建立相應的數學模型并進行預測問題求解過程分析 由于題目具有開放性，故選擇文獻1中的求解思路分析.傳染病的傳播模式可近似分為自由傳播階段和控后階段，然后將人群分為易感者，感病者，移出者三類由三者之

15、間的關系可得到下列微分方程：，利用附件中給出的數據，可以將上述方程變形為， 其中，其解為.其中為初始值但此模型只適用于病例數與總人口數具有可比性的情況，當病例數遠小于總人口數時，感病人數將隨時間以指數增長.這是按實驗定律或規律建立的微分方程模型.為進一步改進模型，用計算機跟蹤病毒的個體傳播情況，又建立計算機模擬模型然后用計算機模擬北京5月10日之前SARS的傳播情況，并對5月10日以后的傳播情況進行預測但是得到的有效接觸率與實際統計數據有所偏差，所以統計數據，為參數的確定尋求醫學上的支持，并以隨機模擬取代完全確定性的模擬，對原模型進行改進，建立隨機模擬模型通過計算機編程，產生正態分布的隨機數，

16、并對傳染情況進行500次模擬，即可進行預測，并可得出對SARS疫情控制提出的相應建議1.2 差分方程建模1.2.1 差分方程建模的原理和方法差分方程在數學建模競賽中應用的頻率極高，所以要對這種方法引起足夠的重視它針對要解決的目標，引入系統或過程中的離散變量具體方法是：根據實際的規律性質、平衡關系等，建立離" 2 L* n9 G4 v4 T散變量所滿足的關系式，從而建立差分方程模型差分方程可以分為不同的類型，如一階和高階差分方程，常系數和變系數差分方程，線性和非線性差分方程等等建立差分方程模型一般要注意以下問題：（1）注意題中的離散變化量，對過程進行分析，尤其要注意形成變化運動過程的時

17、間或距離的分化而得到離散變量；（2）通過對具體變化過程的分析，列出滿足題意的差分方程，其中入手點是找出變量所能滿足的平衡關系、增量或減量關系及規律，從而得到差分方程1.2.2 差分方程建模應用實例例1.3（2007年高教社杯全國大學生數學建模競賽A題） 中國人口增長預測.題目要求從中國的實際情況和人口增長的特點出發，參考附錄中的相關數據（也可以搜索相關文獻和補充新的數據），建立中國人口增長的數學模型，并由此對中國人口增長的中短期和長期趨勢做出預測，特別要指出模型中的優點與不足之處.問題求解過程分析 由于題目具有開放性，故選擇文獻2中的求解思路分析.通過分析題中相關的數據，考慮到我國近年來人口發

18、展的總趨勢，因為涉及到人口的增長和變換，所以可以先用微分方程來建立模型，并對我國人口增長的中短期和長期趨勢做出預測首先，根據灰色系統理論，使用灰色關聯分析模型法對人口系統結構進行關聯分析，找出影響人口增長的主要因素；其次使用年齡推算法進行短期預測.在建立和求解長期預測模型時，根據人口阻滯增長模型（Logistic模型），可以考慮對中國人口老齡化進程加速、出生人口性別比例持續升高以及鄉村人口城鎮化等因素建立新的人口增長的差分方程模型.但是它僅給出了人口總數的變化規律，反映不出各類人口的詳細信息，所以我們需要建立離散化的模型，并進一步可以得到全面系統地反應一個時期內人口數量狀況的差分方程，可以用微

19、分和差分方程理論來表現和模擬人口數量的變化規律從而對人口分布的狀況、變化趨勢、總體特征等有更加詳細和科學的了解在模型的求解過程中，用到了MATLAB軟件，并做參數估計，利用所得結果和題目給出的近五年來的人口數據，對我國人口發展趨勢進行了預測，得到了在老齡化進程加速、出生人口性別比例持續升高以及鄉村人口城鎮化等因素影響下，未來我國人口發展預測情況.2 數學規劃建模數學規劃是指在一系列條件限制下，尋求最優方案，使得目標達到最優的數學模型，它是運籌學的一個重要分支數學規劃的內容十分豐富，包括許多研究分支，如：線性規劃、非線性規劃、整數規劃、二次規劃、0-1規劃、多目標規劃、動態規劃、參數規劃、組合優

20、化、隨機規劃、模糊規劃、多層規劃問題等在1993年A題“非線性交調的頻率設計”，1993年B題“足球隊排名”，1995年A題“飛行管理問題”，1996年B題“節水洗衣機”，1997年A題“零件的參數設計”，1998年A題“一類投資組合問題”，1999年B題“鉆井布局”，2001年B題“公交車調度問題”，2002年A題“車燈線光源的優化”，2006年A題“出版社書號問題”，2007年B題“城市公交線路選擇問題”等賽題中，都用到了規劃的方法在此以線性規劃為例，對規劃的方法進行探討2.1 線性規劃建模的一般理論線性規劃建模方法主要用于解決生產實際中的資源利用、人力調配、生產安排等問題，它是一種重要的

21、數學模型線性規劃是運籌學中研究較早、發展較快、應用廣泛、方法較成熟的一個重要分支，它是研究線性約束條件下線性目標函數的極值問題的數學理論和方法一般的優化問題是指用“最好”的方式，使用或分配有限的資源即勞動力、原材料、機器、資金等，使得費用最小或利潤最大優化模型的一般形式為: (4) (5).由（4）、（5）組成的模型屬于約束優化若只有（4）式就是無約束優化稱為目標函數，稱為約束條件在優化模型中，如果目標函數和約束條件中的都是線性函數，則該模型稱為線性規劃建立實際問題線性規劃模型的步驟如下：（1）設置要求解的決策變量決策變量選取得當，不僅能順利地建立模型而且能方便地求解，否則很可能事倍功半（2）

22、找出所有的限制，即約束條件，并用決策變量的線性方程或線性不等式來表示當限制條件多，背景比較復雜時，可以采用圖示或表格形式列出所有的已知數據和信息，從而避免“遺漏”或“重復”所造成的錯誤（3）明確目標要求，并用決策變量的線性函數來表示，標出對函數是取極大還是取極小的要求需要特別說明的是，要使用線性規劃方法來處理一個實際問題，必須具備下面的條件：（1）優化條件：問題的目標有極大化或極小化的要求,而且能用決策變量的線性函數來表示（2）選擇條件：有多種可供選擇的可行方案，以便從中選取最優方案（3）限制條件：達到目標的條件是有一定限制的（比如，資源的供應量有限度等），而且這些限制可以用決策變量的線性等式

23、或線性不等式表示出來此外，描述問題的決策變量相互之間應有一定的聯系，才有可能建立數學關系，這一點自然是不言而喻的 線性規劃模型的求解可用圖解法或單純形法隨著計算機的普及和大量數學軟件的出現，可以利用現成的軟件MATLAB或LINGO等求解，在此不再敘述2.2 線性規劃建模應用實例例2.1（2006年高教社杯全國大學生數學建模競賽B題） 艾滋病療法的評價及療效的預測.題目給出了美國某艾滋病醫療試驗機構公布的兩組數據，數據涉及到了病人CD4和HIV的濃度含量的測試結果.根據所給的資料需要參賽者完成以下問題：（1）利用附件1的數據，預測繼續治療的效果，或者確定最佳治療終止時間；（2）利用附件2的數據

24、，評價4種療法的優劣（僅以為標準），并對較優的療法預測繼續治療的效果，或者確定最佳治療終止時間；（3）如果病人需要考慮4種療法的費用，對評價和預測有什么影響.問題求解過程分析 由于題目具有開放性，故選擇文獻3中的求解思路進行分析. 首先對題目所給數據進行分析,考慮到治療的效果與患者的年齡有關，將患者按年齡分組，如歲,歲,歲及歲以上組每組中按照種療法和個治療階段（如周，周，周，周），構造個決策單元取種藥品量為輸入，治療各個階段末患者的值與開始治療時值的比值為輸出.然后建立相應的數學模型,利用相對有效性評價方法，建立分式規劃模型并經過變換，轉化為線性規劃模型求解，對各年齡組患者在各階段的治療效率進

25、行評價計算結果：對第年齡組療法和在整個治療中效率較高，在第階段仍然有效；對第年齡組療法在第，階段有效；對第年齡組療法，在第階段有效；對第年齡組療法，在第，階段有效表明只有歲的年種輕患者，才能在治療的最后階段仍然有有效的療法隨后，由線性規劃模型的對偶形式建立預測模型，對各年齡組各種療法下一階段的療效進行預測若由某決策單元得到的實際輸出大于預測輸出，則該決策單元相對有效；反之，說明該種療法對該組患者在治療的未來階段不再有效，應該轉換療法3 統計學建模方法在數學建模競賽中，常常會涉及到大量的數據，因此，我們就需要用統計學建模方法對這些數據進行處理此類方法主要包括統計分析、計算機模擬、回歸分析、聚類分

26、析、數據分類、判別分析、主成分分析、因子分析、殘差分析、典型相關分析、時間序列等如2004年A題“奧運會臨時超市網點設計問題”，2004年B題“電力市場的輸電阻塞管理問題”，2007年A題“人口增長預測問題”，2008年B題“大學學費問題”，2012年A題“葡萄酒的評價”等都用到了這種建模方法在此選取其中兩類方法進行闡述3.1 聚類分析3.1.1 聚類分析的原理和方法該方法說的通俗一點就是，將個樣本，通過適當的方法選取聚類中心，通過研究8 d( $ M1 S9 u, f, r各樣本和各個聚類中心的距離，選擇適當的聚類標準，通常利用最小距離法來聚類，從而可以得到聚類9 c. - % "

27、 s: y, d, 9 e$ 結果利用sas 軟件或者spss 軟件來做聚類分析，就可以得到相應的動態聚類圖這種模型的的特點是直觀，容易理解聚類分析的類型可分為：型聚類（即對樣本聚類）和型聚類（即對變量聚類）& / r  T: C. B, C: D- z' n7 X+ h+ _: B( f  M% ( x7 O9 u% S通常聚類中有相似系數法和距離法兩種衡量標準.# . n. + E& G: d% h- s- X聚類方法種類多樣，有可變類平均法、中間距離法、最長距離法、利差平均和法等.在應用時要9 |! B. K" C

28、2 r" Q, S7 注意,在樣本量比較大時，要得到聚類結果就顯得不是很容易,這時需要根據背景知識和相關的其他方法輔助處理主要的( B3 1 U4 h( |/ B; I方法步驟大致如下：（1） 首先把每個樣本自成一類；（2）選取適當的衡量標準，得到衡量矩陣；（3）重新計算類間距離，得到衡量矩陣；（4）重復第2步，直到只剩下一個類.3.1.2 聚類分析應用實例例3.1（2012年高教社杯全國大學生數學建模競賽A題） 葡萄酒的評價.題目的附件中給出了某一年份一些葡萄酒的評價結果，和該年份這些葡萄酒的和釀酒葡萄的成分數據.要求參賽者建立數學模型解決以下問題：（1）分析附件1中兩組評酒員的評

29、價結果有無顯著性差異，哪一組結果更可信；（2）根據釀酒葡萄的理化指標和葡萄酒的質量對這些釀酒葡萄進行分級；（3）分析釀酒葡萄與葡萄酒的理化指標之間的聯系；（4）分析釀酒葡萄和葡萄酒的理化指標對葡萄酒質量的影響，并論證能否用葡萄和葡萄酒的理化指標來評價葡萄酒的質量.問題求解過程分析 由于題目具有開放性，故選擇文獻4中的求解思路分析. 由于給定了釀酒葡萄的理化指標，首先可將附錄2和附錄3中的一些數據進行處理.并可以據此對各種釀酒葡萄進行聚類分析，但是，由于題目中所給的數據龐大，所以可通過主成分分析法，簡化并提取大部分有效信息，再用聚類分析對釀酒葡萄進行分級最后根據釀酒葡萄對應葡萄酒質量的平均值大小

30、進行比較，排序分級接下來針對問題中分析釀酒葡萄與葡萄酒理化指標之間的聯系，及上面整理好的數據，采用回歸分析原理，在SPSS中得到釀酒葡萄與葡萄酒的理化指標之間的聯系再通過相關分析，得出相應的相關系數，從而得到相應的判斷結論在分析釀酒葡萄與葡萄酒的理化指標之間的聯系時，還用到了多元線性回歸分析該模型用于生活實踐中，也可以解決很多實際問題3.2 回歸分析 回歸分析是利用數據統計原理，對大量數據進行數學處理，并確定因變量與某些自變量的相關關系，建立一個相關性較好的回歸方程，并加以外推，用于預測今后的因變量的變化的分析方法3.2.1 回歸分析的原理與方法回歸分析是在一組數據的基礎上研究這樣幾個問題：建

31、立因變量與自變量之間的回歸模型；對回歸模型的可信度進行檢驗；判斷每個自變量對因變量的影響是否顯著；判斷回歸模型是否適合這組數據；利用回歸模型對進行預報或控制回歸分析主要包括一元線性回歸、多元線性回歸、非線性回歸回歸分析的主要步驟為：（1）根據自變量和因變量的關系，建立回歸方程（2）解出回歸系數（3）對其進行相關性檢驗，確定相關系數（4）當符合相關性要求后，便可與具體條件結合，確定預測值的置信區間.需要注意的是，要盡可能定性判斷自變量的可能種類和個數，并定性判斷回歸方程的可能類型另外，最好應用高質量的統計數據，再運用數學工具和相關軟件定量定性判斷3.2.2 回歸分析應用實例例3.2（2006年高

32、教社杯全國大學生數學建模競賽B題） 艾滋病療法的評價及療效的預測.題目同例2.1問題求解過程分析 由于題目具有開放性，故選擇文獻3中的求解思路進行分析. 問題2的解決就用到回歸模型.首先分析數據知，應建立時間的一次與二次函數模型，并經過統計分析比較，確定哪種較好所以可建立一個統一的回歸模型，也可對每種療法分別建立一個模型以總體回歸模型為例，分別用一次與二次時間函數模型進行比較，可知療法用一次模型較優，且一次項系數為負，即在減少，從數值看療法優于療法和；療法用二次模型較優，即先增后減，在左右達到最大可以通過條回歸曲線進行比較，顯示療法在周之前明顯優于其它最后再用檢驗法作比較，結果是療法與無顯著性

33、差異，而療法與，與，與均有顯著性差異4 圖論建模方法圖論建模方法在建模競賽中也經常涉及，應用十分廣泛，并且解法巧妙，方法靈活多變如1990年B題“掃雪問題”，1991年B題“尋找最優Steiner樹”，1992年B題“緊急修復系統的研制”，1993年B題“足球隊排名”，1994年A題“逢山開路問題”，1994年B題“鎖具裝箱問題”，1995年B題“天車與冶煉爐的作業調度”，1997年B題“截斷切割的最優排列”，1998年B題“災情巡視最佳路線”，1999年B題“鉆井布局”，2007年B題“城市公交線路選擇問題”等都應用到了圖論的方法圖論近幾年來發展十分迅速，在物理、化學、生物學、地理學、計算機

34、科學、信息論、控制論、社會科學、軍事科學以及計算機管理等方面都有著廣泛的應用因此圖論越來越受到了全世界數學界和工程技術界乃至經營決策管理者的重視同時也成為了數學建模中一種十分重要的方法圖論問題算法很多，包括最短路、最大流、最小生成樹、二分匹配、floyd、frim等 4.1 兩種常見圖論方法介紹圖論中的圖是由平面上的一些點及這些點之間的連線（稱為邊）構成的圖中的點表示要研究的離散對象，邊表示對象之間的關系用這些點和邊建立的離散對象來建立模型，通過這種辦法許多難題都可以被巧妙地解決所以圖論方法成為研究離散問題的一種重要手段由于圖論方法所包含的概念和定義較多，無法全部列舉在這里只就其中的兩種方法作

35、介紹4.1.1 模擬退火法的基本原理模擬退火法是模擬熱力學中系統的降溫過程，當孤立粒子系統的溫度以足夠慢的速度下降時，系統近似處于熱力學平衡狀態，最后系統將達到本身的最低能量狀態，即基態，這相當于能量函數的全局極小點其步驟如下(也稱為Metropolis過程)：（1）給定初始溫度，及初始點，計算該點的函數值；（2）隨機產生擾動，得到新點計算新點函數值,及函數值差；（3）若，則接受新點，作為下一次模擬的初始點；（4）若，則計算新點接受概率：，產生區間上均勻分布的偽隨機數,，如果，則接受新點作為下一次模擬的初始點；否則放棄新點，仍取原來的點作為下一次模擬的初始點4.1.2 最短路問題最短路問題是一

36、個有著廣泛應用價值的問題，例如各種管道的鋪設，線路的安排，輸送網絡費用等問題，都可以用到最短路求法在解決實際問題時，我們問題中的“邊權”可以有著各種不同的解釋例如在運輸網絡中，從運送一批貨物到，若“邊權”視為通常意義下的路程，則最短路問題就是使運輸總路程最短的路線，若“邊權”表示運輸時間，則最短路就是運輸總時間最短的路線，“邊權”也可以代表費用，這時相應的就是總費用最省的的路線4.2 圖論建模應用實例例4.2（2007年高教社杯全國大學生數學建模競賽B題） 城市公交線路選擇問題.在2007年B題中，涉及到了北京公交車的換乘問題，為了使乘客利益最大化，需要設計一個“公交線路選擇自主查詢系統”，其

37、核心是線路選擇的模型，該模型必須考慮實際情況，滿足查詢者的各種不同需求要求解決如下問題：(1)僅考慮公汽線路，給出任意兩公汽站點之間線路選擇問題的一般數學模型與算法 (2)同時考慮公汽與地鐵線路，解決以上問題(3)假設又知道所有站點之間的步行時間，請你給出任意兩站點之間線路選擇問題的數學模型問題求解過程分析 由于題目具有開放性，故選擇文獻5中的求解思路進行分析. 由于在現實情況下，乘客一般不能乘坐一輛公交車就到達終點，可能會換乘，但要是頻繁倒車，會給乘客造成不便，也會增加車費所以可針對城市公交線路選擇問題建立模型為了使問題簡單化，我們分別以乘車時間、乘車費用以及換乘次數為目標函數，得到各自的較

38、優線路，再通過對比，有效地處理這些線路，最終得出查詢系統給出的結果首先固定換乘次數，通過集合論的相關知識把確定換乘點的具體位置, 轉化成確定一些集合間的交集，從而建立集合尋線算法，再根據集合相關公式，得到所有可行線路；進一步考慮時間和費用等因素，對可行線路進行處理比較，得出最佳線路圖論模型中，通過圖論的知識將整個北京市交通線路構建出一個有向圖，每個站點與有向圖的頂點一一對應，同一線路上的相鄰站點對應為有向邊，通過不同目標（時間、費用）給有向圖進行不同的賦權，分別將不同目標轉化為賦權有向圖尋找最短有向路，根據最短路徑算法，得到最佳線路最后綜合評價了兩個模型的優缺點以每個站點為頂點，若站點到站點有公交線路并且與為相鄰站點，則連一條到有向邊，根據所給的站點與線路我們建立一個得到一個有重邊的有向圖一條公交線路就是的一條有向路則任意兩公汽站點之間線路最少時間選擇問題就轉化為求的對應兩頂點的最短有向路問題由圖論模型所得的查詢系統，是以圖論知識中的最短路有向圖為基礎，對不同線路經過同一站點時，假設多個假想點，并將各不同站點之間所需時間作為權，對各線路站點賦權，分別確定以時間、費用、