全國大學(xué)生數(shù)學(xué)建模競賽常用建模方法總結(jié)概要

1、邯鄲學(xué)院本科畢業(yè)論文 題 目 全國大學(xué)生數(shù)學(xué)建模競賽常用建模方法探討 學(xué) 生 柴云飛 指導(dǎo)教師 閆峰教授 年 級 2009級本科 專 業(yè) 數(shù)學(xué)與應(yīng)用數(shù)學(xué) 二級學(xué)院 數(shù)學(xué)系 （系、部） 邯鄲學(xué)院數(shù)學(xué)系 2013年6月 鄭重聲明 本人的畢業(yè)論文是在指導(dǎo)教師閆峰的指導(dǎo)下獨(dú)立撰寫完成的.如有剽竊、 抄襲、造假等違反學(xué)術(shù)道德、學(xué)術(shù)規(guī)范和侵權(quán)的行為，本人愿意承擔(dān)由此產(chǎn) 生的各種后果，直至法律責(zé)任，并愿意通過網(wǎng)絡(luò)接受公眾的監(jiān)督.特此鄭重 聲明. 論文經(jīng)“中國知網(wǎng)”論文檢測系統(tǒng)檢測，總相似比為 5.80%. 畢業(yè)論文作者（簽名）： 年 月I 全國大學(xué)生數(shù)學(xué)建模競賽常用建模方法探討 摘要 全國大學(xué)生數(shù)學(xué)建模競賽

2、作為全國高校規(guī)模最大的基礎(chǔ)性學(xué)科競賽，越來越受到人們 的重視，所以建模競賽的方法也就變得尤為重要隨著競賽的不斷發(fā)展，賽題的開放性逐 步增大，一道賽題可用多種解法，各種求解的算法有時(shí)會相互融合，同時(shí)也在向大規(guī)模數(shù) 據(jù)處理方向發(fā)展，這就對選手的能力提出了更高的要求由于建模方法種類眾多，無法一 一介紹，所以本文主要介紹了四種比較常用的數(shù)學(xué)建模競賽方法，包括微分與差分方程建 模方法、數(shù)學(xué)規(guī)劃建模方法、統(tǒng)計(jì)學(xué)建模方法、圖論方法，并結(jié)合歷年賽題加以說明. 關(guān)鍵詞：數(shù)學(xué)建模競賽統(tǒng)計(jì)學(xué)方法數(shù)學(xué)規(guī)劃圖論II Commonly Used Modeling Method of China Undergraduate

3、 Mathematical Contest in Modeling Chai yunfei Directed by Professor Yan feng ABSTRACT The Chi na un dergraduate mathematical con test in modeli ng has bee n atte nti on by more and more people as a basic subject of the largest national college competition. The method of modeli ng competiti on has be

4、come more and more importa nt. Ope n questio ns gradually in creased 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 player

5、s. The modeling methods is too numerous to mention, so this article mainly four kinds Commonly used modeling method are introduced that differential and differenee equations modeling method, Mathematical programming modeling method, Statistics modeling method, graph theory and interprets with calend

6、ar years test questi ons. KEY WORDS : Mathematical con test in modeli ng Statistics method Mathematical program ming Graph theory1 摘要 . . 英文摘要 . II 刖 言 . 1. 1微分方程與差分方程建模 . 2. 1.1微分方程建模 . 2. 1.1.1微分方程建模的原理和方法 . 2 1.1.2微分方程建模應(yīng)用實(shí)例 . .3 1.2差分方程建模 . .4. 1.2.1差分方程建模的原理和方法 . 4 1.2.2差分方程建模應(yīng)用實(shí)例 . .5. 2數(shù)學(xué)規(guī)劃建模

7、 . 5. 2.1線性規(guī)劃建模的一般理論 . 6. 2.2線性規(guī)劃建模應(yīng)用實(shí)例 . 1. 3統(tǒng)計(jì)學(xué)建模方法 . 8. 3.1聚類分析 . 8. 3.1.1聚類分析的原理和方法 . .8. 3.1.2聚類分析應(yīng)用實(shí)例 . 9. 3.2回歸分析 . 9. 3.2.1回歸分析的原理與方法 . .9. 3.2.2回歸分析應(yīng)用實(shí)例 . 10 4圖論建模方法 . 10 4.1兩種常見圖論方法介紹 . 11 4.1.1模擬退火法的基本原理 . 1.1 4.1.2最短路問題 . 1.1 4.2圖論建模應(yīng)用實(shí)例 . 1.2 5小結(jié) . 1.3. 參考文獻(xiàn) . 1.4 2 致謝 . 1.5.1 全國大學(xué)生數(shù)學(xué)建模

8、競賽創(chuàng)辦于 1992年，每年一屆，目前已成為全國高校規(guī)模最 大的基礎(chǔ)性學(xué)科競賽，也是世界上規(guī)模最大的數(shù)學(xué)建模競賽.參賽者需要根據(jù)題目要求, 在三天時(shí)間內(nèi)完成一篇包括模型假設(shè)、模型建立和求解、計(jì)算方法的設(shè)計(jì)和實(shí)現(xiàn)、模型 結(jié)果的分析和檢驗(yàn)、模型的改進(jìn)等方面的論文通過參加競賽的訓(xùn)練和比賽，可以提高 學(xué)生用數(shù)學(xué)方法解決實(shí)際問題的意識和能力，而且在培養(yǎng)團(tuán)隊(duì)精神和撰寫科技論文等方 面都會得到十分有益的鍛煉. 競賽題目的涉及面比較寬，有工業(yè)、農(nóng)業(yè)、工程設(shè)計(jì)、交通運(yùn)輸、經(jīng)濟(jì)管理、生物 醫(yī)學(xué)和社會事業(yè)等競賽選手不一定預(yù)先掌握深入的專業(yè)知識，而只需要學(xué)過高等數(shù)學(xué) 的相關(guān)課程即可，并且題目具有較大的靈活性，便于參賽

9、者發(fā)揮其創(chuàng)造能力近年來， 競賽題目包含的數(shù)據(jù)較多，手工計(jì)算一般不能實(shí)現(xiàn)，所以就對參賽者的計(jì)算機(jī)能力提出 了更高的要求，如2003年B題，某些問題的解決需要使用計(jì)算機(jī)軟件； 2001年A題, 問題的數(shù)據(jù)讀取需要計(jì)算機(jī)技術(shù)，并且對于給出的圖像，需要用圖像處理的方法獲得； 再如2004年A題則需要利用數(shù)據(jù)庫數(shù)據(jù)，數(shù)據(jù)庫方法，統(tǒng)計(jì)軟件包等等. 競賽題目的總體特點(diǎn)可大致歸納如下：（1）實(shí)用性不斷加強(qiáng)，問題和數(shù)據(jù)來自于實(shí) 際，解決方法需要切合實(shí)際，模型和結(jié)果可以應(yīng)用于實(shí)際； （2）綜合性不斷加強(qiáng)，解法 多樣，方法融合，學(xué)科交叉；（3）數(shù)據(jù)結(jié)構(gòu)越來越復(fù)雜，包括數(shù)據(jù)的真實(shí)性，數(shù)據(jù)的海 量性，數(shù)據(jù)的不完備性，數(shù)

10、據(jù)的冗余性等；（4）開放性也越來越突出，題意的開放性， 思路的開放性，方法多樣，結(jié)果不唯一等總體來說，賽題向大規(guī)模數(shù)據(jù)處理方向發(fā)展， 求解算法和各類現(xiàn)代算法相互融合. 縱觀歷年的賽題，主要用到的建模方法有：初等數(shù)學(xué)模型、微分與差分方程建模、 組合概率、數(shù)據(jù)處理、統(tǒng)計(jì)學(xué)建模、計(jì)算方法建模、數(shù)學(xué)規(guī)劃、圖論方法、層次分析、 插值與擬合、排隊(duì)論、模糊數(shù)學(xué)、隨機(jī)決策、多目標(biāo)決策、隨機(jī)模擬、計(jì)算機(jī)模擬法、 灰色系統(tǒng)理論、時(shí)間序列等. 本文不一一列舉競賽題目中涉及的所有方法， 只是重點(diǎn)討論其中一些比較常用的方 法，包括微分與差分方程建模方法、數(shù)學(xué)規(guī)劃建模方法、統(tǒng)計(jì)學(xué)建模方法、圖論建模方 法，并結(jié)合案例說明建

11、模方法的原理及應(yīng)用.2 1微分方程與差分方程建模 在很多競賽題目中，常常會涉及很多變量之間的關(guān)系，找出它們之間的函數(shù)關(guān)系式 具有重要意義可在許多實(shí)際問題中，我們常常不能直接給出所需要的函數(shù)關(guān)系，但可 以得到含有所求函數(shù)的導(dǎo)數(shù)（或微分）或差分（即增量）的方程，這樣的方程稱為微分 方程或差分方程建立微分方程或差分方程的數(shù)學(xué)模型是一種重要的建模方法 女口 1996年A題“最優(yōu)捕魚策略” ，1997年A題“零件參數(shù)設(shè)計(jì)” ，2003年A題“SARS 的傳播”，2007年A題“中國人口增長預(yù)測”，2009年A題“最優(yōu)捕魚策略”等賽題中， 都用到了這種方法. 1.1微分方程建模 1.1.1微分方程建模的原

12、理和方法 一般來說，任何時(shí)變問題中隨時(shí)間變化而發(fā)生變化的量與其它一些量之間的關(guān)系經(jīng) 常以微分方程的形式來表現(xiàn). 例1.1有一容器裝有某種濃度的溶液，以流量 V1注入該容器濃度為 5 的同樣溶液， 假定溶液立即被攪拌均勻，并以 V2的流量流出混合后的溶液，試建立反映容器內(nèi)濃度變 化的數(shù)學(xué)模型. 溶液質(zhì)量 解注意到溶液濃度=溶液質(zhì)量，因此，容器中溶液濃度會隨溶質(zhì)質(zhì)量和溶液體積 溶液體積 變化而發(fā)生變化. 不妨設(shè)t時(shí)刻容器中溶質(zhì)質(zhì)量為 st，初始值為 S0,t時(shí)刻容器中溶液體積為 vt，初 始值為 V。，則這段時(shí)間 t,t ：t 內(nèi)有 & = 5 心_32 少 （） 其中 G 表示單位時(shí)間內(nèi)

13、注入溶液的濃度，C2 表示單位時(shí)間內(nèi)流出溶液的濃度，當(dāng)肥很小 時(shí)，在 t,t rt 內(nèi)有 C 弋 s(t) _ s(t) (2) 3 2 V(t) Vo+(V1V2)t 對式(1)兩端同除以-1，令0，則有 ds =c1v1 c2v2 dt dV_ ( 3) * Vi v? . (3) dt s(O) = So,V(O)=V。 即所求問題的微分方程模型雖然它是針對液體溶液變化建立的，但對氣體和固體 濃度變化同樣適用. 實(shí)際應(yīng)用中，許多時(shí)變問題都可取微小的時(shí)間段 .：t去考察某些量之間的變化規(guī)律， 從而建立問題的數(shù)學(xué)模型，這是數(shù)學(xué)建模中微分方程建模常用手段之一. 常用微分方程建模的方法主要有：

14、(1) 按實(shí)驗(yàn)定律或規(guī)律建立微分方程模型. 此種建模方法充分依賴于各個(gè)學(xué)科領(lǐng)域中有關(guān)實(shí)驗(yàn)定律或規(guī)律以及某些重要的已 知定理，這種方法要求建模者有寬廣的知識視野，這樣才能對具體問題采用某些熟知的 實(shí)驗(yàn)定律. (2) 分析微元變化規(guī)律建立微分方程模型. 求解某些實(shí)際問題時(shí)，尋求一些微元之間的關(guān)系可以建立問題的數(shù)學(xué)模型. 如例1.1 中考察時(shí)間微元t，從而建立起反應(yīng)溶液濃度隨時(shí)間變化的模型. 此建模方法的出發(fā)點(diǎn) 是考察某一變量的微小變化，即微元分析，找出其他一些變量與該微元間的關(guān)系式，從 微分定義出發(fā)建立問題的數(shù)學(xué)模型. (3) 近似模擬法. 在許多實(shí)際問題中，有些現(xiàn)象的規(guī)律性并非一目了然，或有所了

15、解亦是復(fù)雜的，這 類問題常用近似模擬方法來建立問題的數(shù)學(xué)模型.一般通過一定的模型假設(shè)近似模擬實(shí) 際現(xiàn)象，將問題做某些規(guī)范化處理后建立微分方程模型，然后分析、求解，并與實(shí)際問 題作比較，觀察模型能否近似刻畫實(shí)際現(xiàn)象近似模擬法的建模思路就是建立能夠近似 刻畫或反映實(shí)際現(xiàn)象的數(shù)學(xué)模型，因此在建模過程中經(jīng)常做一些較合理的模型假設(shè)使問 題簡化，然后通過簡化建立近似反映實(shí)際問題的數(shù)學(xué)模型. 1.1.2微分方程建模應(yīng)用實(shí)例 例1.2 (2003年高教社杯全國大學(xué)生數(shù)學(xué)建模競賽 A題)SARS傳播的預(yù)測. 2003年爆發(fā)的“SARS疾病得到了許多重要的經(jīng)驗(yàn)和教訓(xùn)， 使人們認(rèn)識到研究傳染4 病的傳播規(guī)律的重要性

16、題目給出了感病情況的三個(gè)附件，要求對 SARS的傳播建立數(shù) 學(xué)模型：（1）對SARS勺傳播建立一個(gè)自己的模型，并說明模型的優(yōu)缺點(diǎn)；（2）收集SARS 對經(jīng)濟(jì)某個(gè)方面影響的數(shù)據(jù)，建立相應(yīng)的數(shù)學(xué)模型并進(jìn)行預(yù)測. 問題求解過程分析 由于題目具有開放性，故選擇文獻(xiàn)1中的求解思路分析 傳染病的傳播模式可近似分為自由傳播階段和控后階段，然后將人群分為易感者 S，感病者I，移出者R三類由三者之間的關(guān)系可得到下列微分方程： dt dt S I R 二 N 利用附件中給出的數(shù)據(jù)，可以將上述方程變形為 -J I =kNI hl dt 其中一 kN h，其解為 I(t) = loe. 其中 Io為初始值. 但此模型

17、只適用于病例數(shù)與總?cè)丝跀?shù)具有可比性的情況， 當(dāng)病例數(shù)遠(yuǎn)小于總?cè)丝跀?shù) 時(shí)，感病人數(shù)將隨時(shí)間以指數(shù)增長這是按實(shí)驗(yàn)定律或規(guī)律建立的微分方程模型 為進(jìn)一步改進(jìn)模型，用計(jì)算機(jī)跟蹤病毒的個(gè)體傳播情況，又建立計(jì)算機(jī)模擬模型.然 后用計(jì)算機(jī)模擬北京5月10日之前SARS勺傳播情況， 并對5月10日以后的傳播情況 進(jìn)行預(yù)測但是得到的有效接觸率與實(shí)際統(tǒng)計(jì)數(shù)據(jù)有所偏差，所以統(tǒng)計(jì)數(shù)據(jù)，為參數(shù)的 確定尋求醫(yī)學(xué)上的支持，并以隨機(jī)模擬取代完全確定性的模擬，對原模型進(jìn)行改進(jìn)，建 立隨機(jī)模擬模型通過計(jì)算機(jī)編程，產(chǎn)生正態(tài)分布的隨機(jī)數(shù)，并對傳染情況進(jìn)行 500次 模擬，即可進(jìn)行預(yù)測，并可得出對 SARSS情控制提出的相應(yīng)建議. d

18、SkiS dt pl I d 二 kIS-hl 5 1.2差分方程建模 1.2.1差分方程建模的原理和方法 差分方程在數(shù)學(xué)建模競賽中應(yīng)用的頻率極高， 所以要對這種方法引起足夠的重 視它針對要解決的目標(biāo)，引入系統(tǒng)或過程中的離散變量具體方法是：根據(jù)實(shí)際的規(guī) 律性質(zhì)、平衡關(guān)系等，建立離散變量所滿足的關(guān)系式，從而建立差分方程模型. 差分方程可以分為不同的類型，如一階和高階差分方程，常系數(shù)和變系數(shù)差分方程， 線性和非線性差分方程等等. 建立差分方程模型一般要注意以下問題： （1） 注意題中的離散變化量，對過程進(jìn)行分析，尤其要注意形成變化運(yùn)動過程的 時(shí)間或距離的分化而得到離散變量； （2） 通過對具體變化

19、過程的分析，列出滿足題意的差分方程，其中入手點(diǎn)是找出 變量所能滿足的平衡關(guān)系、增量或減量關(guān)系及規(guī)律，從而得到差分方程. 1.2.2差分方程建模應(yīng)用實(shí)例 例1.3 （2007年高教社杯全國大學(xué)生數(shù)學(xué)建模競賽 A題） 中國人口增長預(yù)測. 題目要求從中國的實(shí)際情況和人口增長的特點(diǎn)出發(fā)，參考附錄中的相關(guān)數(shù)據(jù)（也可 以搜索相關(guān)文獻(xiàn)和補(bǔ)充新的數(shù)據(jù)），建立中國人口增長的數(shù)學(xué)模型，并由此對中國人口 增長的中短期和長期趨勢做出預(yù)測，特別要指出模型中的優(yōu)點(diǎn)與不足之處 問題求解過程分析 由于題目具有開放性，故選擇文獻(xiàn)2中的求解思路分析. 通過分析題中相關(guān)的數(shù)據(jù)， 考慮到我國近年來人口發(fā)展的總趨勢， 因?yàn)樯婕暗饺丝?

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

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

22、劃、參數(shù)規(guī) 劃、組合優(yōu)化、隨機(jī)規(guī)劃、模糊規(guī)劃、多層規(guī)劃問題等. 在1993年A題“非線性交調(diào)的頻率設(shè)計(jì)” ，1993年B題“足球隊(duì)排名”，1995年A 題“飛行管理問題” ，1996年B題“節(jié)水洗衣機(jī)” ，1997年A題“零件的參數(shù)設(shè)計(jì)”，1998 年A題“一類投資組合問題”，1999年B題“鉆井布局” ，2001年B題“公交車調(diào)度問 題”，2002年A題“車燈線光源的優(yōu)化” ，2006年A題“出版社書號問題” ，2007年B 題“城市公交線路選擇問題”等賽題中，都用到了規(guī)劃的方法在此以線性規(guī)劃為例， 對規(guī)劃的方法進(jìn)行探討. 2.1線性規(guī)劃建模的一般理論 線性規(guī)劃建模方法主要用于解決生產(chǎn)實(shí)際中

23、的資源利用、人力調(diào)配、生產(chǎn)安排等問 題，它是一種重要的數(shù)學(xué)模型線性規(guī)劃是運(yùn)籌學(xué)中研究較早、發(fā)展較快、應(yīng)用廣泛、 方法較成熟的一個(gè)重要分支，它是研究線性約束條件下線性目標(biāo)函數(shù)的極值問題的數(shù)學(xué) 理論和方法. 一般的優(yōu)化問題是指用“最好”的方式，使用或分配有限的資源即勞動力、原材料、 機(jī)器、資金等，使得費(fèi)用最小或利潤最大. 優(yōu)化模型的一般形式為： min 或 max z 二 f x (4) s.t.g x -0. i h,2, ,m (5) f T (x=(為，X2，Xn ). 由(4)、(5)組成的模型屬于約束優(yōu)化若只有(4)式就是無約束優(yōu)化.f(x)稱 為目標(biāo)函數(shù)，g x空0稱為約束條件. 在優(yōu)

24、化模型中，如果目標(biāo)函數(shù) f x 和約束條件中的g x都是線性函數(shù)，則該模型 稱為線性規(guī)劃. 建立實(shí)際問題線性規(guī)劃模型的步驟如下： (1) 設(shè)置要求解的決策變量.決策變量選取得當(dāng)，不僅能順利地建立模型而且能 方便地求解，7 否則很可能事倍功半. (2) 找出所有的限制，即約束條件，并用決策變量的線性方程或線性不等式來表 示.當(dāng)限制條件多，背景比較復(fù)雜時(shí)，可以采用圖示或表格形式列出所有的已知數(shù)據(jù)和 信息，從而避免“遺漏”或“重復(fù)”所造成的錯(cuò)誤. （3）明確目標(biāo)要求，并用決策變量的線性函數(shù)來表示，標(biāo)出對函數(shù)是取極大還是 取極小的要求. 需要特別說明的是，要使用線性規(guī)劃方法來處理一個(gè)實(shí)際問題，必須具備

25、下面的條 件： （1） 優(yōu)化條件：問題的目標(biāo)有極大化或極小化的要求，而且能用決策變量的線性函 數(shù)來表示. （2） 選擇條件：有多種可供選擇的可行方案，以便從中選取最優(yōu)方案. （3） 限制條件：達(dá)到目標(biāo)的條件是有一定限制的（比如，資源的供應(yīng)量有限度等） 而且這些限制可以用決策變量的線性等式或線性不等式表示出來. 此外，描述問題的決策變量相互之間應(yīng)有一定的聯(lián)系，才有可能建立數(shù)學(xué)關(guān)系，這 一點(diǎn)自然是不言而喻的. 線性規(guī)劃模型的求解可用圖解法或單純形法. 隨著計(jì)算機(jī)的普及和大量數(shù)學(xué)軟件的 出現(xiàn)，可以利用現(xiàn)成的軟件 MATLA或LINGO等求解，在此不再敘述. 2.2線性規(guī)劃建模應(yīng)用實(shí)例 例2.1 （2

26、006年高教社杯全國大學(xué)生數(shù)學(xué)建模競賽 B題）艾滋病療法的評價(jià)及療 效的預(yù)測. 題目給出了美國某艾滋病醫(yī)療試驗(yàn)機(jī)構(gòu)公布的兩組數(shù)據(jù)， 數(shù)據(jù)涉及到了病人CD4和 HIV的濃度含量的測試結(jié)果.根據(jù)所給的資料需要參賽者完成以下問題：（1）利用附件1 的數(shù)據(jù)，預(yù)測繼續(xù)治療的效果，或者確定最佳治療終止時(shí)間； （2）利用附件2的數(shù)據(jù)， 評價(jià)4種療法的優(yōu)劣（僅以 CD4 為標(biāo)準(zhǔn)），并對較優(yōu)的療法預(yù)測繼續(xù)治療的效果，或者 確定最佳治療終止時(shí)間；（3）如果病人需要考慮4種療法的費(fèi)用，對評價(jià)和預(yù)測有什么 影響 問題求解過程分析 由于題目具有開放性，故選擇文獻(xiàn)3中的求解思路進(jìn)行分析 首先對題目所給數(shù)據(jù)進(jìn)行分析，考慮到

27、治療的效果與患者的年齡有關(guān)，將患者按年 齡分組，如1425趴2535歲，3545歲及 45 歲以上4組.每組中按照4種療法和4個(gè) 治療階段（如010周，1020周，2030周，3040周），構(gòu)造 16 個(gè)決策單元.取4 種藥品量為輸入，治療各個(gè)階段末患者的 CD4 值與開始治療時(shí) CD4 值的比值為輸出. 然后建立相應(yīng)的數(shù)學(xué)模型，利用相對有效性評價(jià)方法，建立分式規(guī)劃模型并經(jīng)過變 換，轉(zhuǎn)化為線性規(guī)劃模型求解，對各年齡組患者在各階段的治療效率進(jìn)行評價(jià).計(jì)算結(jié) 果：對第1年齡組療法2和4在整個(gè)治療中效率較高，在第4階段仍然有效；對第2年齡 組療法1在第1，2階段有效；對第3年齡組療法1，2，3在第1

28、階段有效； 對第4年齡 組療法1，2在第1，2階段有效.表明只有1425歲的年4種輕患者，才能在治療的最 8 后階段仍然有有效的療法. 隨后， 由線性規(guī)劃模型的對偶形式建立預(yù)測模型， 對各年齡組各種療法下一階段的 療效進(jìn)行預(yù)測.若由某決策單元得到的實(shí)際輸出大于預(yù)測輸出，則該決策單元相對有效； 反之，說明該種療法對該組患者在治療的未來階段不再有效，應(yīng)該轉(zhuǎn)換療法. 3統(tǒng)計(jì)學(xué)建模方法 在數(shù)學(xué)建模競賽中，常常會涉及到大量的數(shù)據(jù)，因此，我們就需要用統(tǒng)計(jì)學(xué)建模方 法對這些數(shù)據(jù)進(jìn)行處理此類方法主要包括統(tǒng)計(jì)分析、計(jì)算機(jī)模擬、回歸分析、聚類分 析、數(shù)據(jù)分類、判別分析、主成分分析、因子分析、殘差分析、典型相關(guān)分析

29、、時(shí)間序 列等. 如2004年A題“奧運(yùn)會臨時(shí)超市網(wǎng)點(diǎn)設(shè)計(jì)問題” ，2004年B題“電力市場的輸電阻 塞管理問題” ，2007年A題“人口增長預(yù)測問題” ，2008年B題“大學(xué)學(xué)費(fèi)問題” ，2012 年A題“葡萄酒的評價(jià)”等都用到了這種建模方法在此選取其中兩類方法進(jìn)行闡述. 3.1聚類分析 3.1.1聚類分析的原理和方法 該方法說的通俗一點(diǎn)就是，將n個(gè)樣本，通過適當(dāng)?shù)姆椒ㄟx取 m聚類中心，通過研 究各樣本和各個(gè)聚類中心的距離，選擇適當(dāng)?shù)木垲悩?biāo)準(zhǔn)，通常利用最小距離法來聚類， 從而可以得到聚類結(jié)果利用sas軟件或者spss軟件來做聚類分析， 就可以得到相應(yīng) 的動態(tài)聚類圖這種模型的的特點(diǎn)是直觀，容易

30、理解. 聚類分析的類型可分為：Q 型聚類(即對樣本聚類)和 R型聚類(即對變量聚類) 通常聚類中有相似系數(shù)法和距離法兩種衡量標(biāo)準(zhǔn) 聚類方法種類多樣，有可變類平 均法、中間距離法、最長距離法、利差平均和法等.在應(yīng)用時(shí)要注意，在樣本量比較大時(shí), 要得到聚類結(jié)果就顯得不是很容易，這時(shí)需要根據(jù)背景知識和相關(guān)的其他方法輔助處 理主要的方法步驟大致如下： (1) 首先把每個(gè)樣本自成一類； (2) 選取適當(dāng)?shù)暮饬繕?biāo)準(zhǔn)，得到衡量矩陣； (3) 重新計(jì)算類間距離，得到衡量矩陣； (4) 重復(fù)第2步，直到只剩下一個(gè)類. 3.1.2聚類分析應(yīng)用實(shí)例 9 例3.1 （2012年高教社杯全國大學(xué)生數(shù)學(xué)建模競賽 A題）

31、葡萄酒的評價(jià) 題目的附件中給出了某一年份一些葡萄酒的評價(jià)結(jié)果， 和該年份這些葡萄酒的和釀 酒葡萄的成分?jǐn)?shù)據(jù)要求參賽者建立數(shù)學(xué)模型解決以下問題：（1）分析附件1中兩組評 酒員的評價(jià)結(jié)果有無顯著性差異，哪一組結(jié)果更可信； （2）根據(jù)釀酒葡萄的理化指標(biāo)和 葡萄酒的質(zhì)量對這些釀酒葡萄進(jìn)行分級；（3）分析釀酒葡萄與葡萄酒的理化指標(biāo)之間的 聯(lián)系；（4）分析釀酒葡萄和葡萄酒的理化指標(biāo)對葡萄酒質(zhì)量的影響，并論證能否用葡萄 和葡萄酒的理化指標(biāo)來評價(jià)葡萄酒的質(zhì)量. 問題求解過程分析 由于題目具有開放性，故選擇文獻(xiàn)4中的求解思路分析. 由于給定了釀酒葡萄的理化指標(biāo)，首先可將附錄2和附錄3中的一些數(shù)據(jù)進(jìn)行處理. 并可

32、以據(jù)此對各種釀酒葡萄進(jìn)行聚類分析，但是，由于題目中所給的數(shù)據(jù)龐大，所以可 通過主成分分析法，簡化并提取大部分有效信息，再用聚類分析對釀酒葡萄進(jìn)行分級.最 后根據(jù)釀酒葡萄對應(yīng)葡萄酒質(zhì)量的平均值大小進(jìn)行比較，排序分級接下來針對問題中 分析釀酒葡萄與葡萄酒理化指標(biāo)之間的聯(lián)系， 及上面整理好的數(shù)據(jù)，采用回歸分析原理， 在SPSS中得到釀酒葡萄與葡萄酒的理化指標(biāo)之間的聯(lián)系再通過相關(guān)分析，得出相應(yīng) 的相關(guān)系數(shù)，從而得到相應(yīng)的判斷結(jié)論在分析釀酒葡萄與葡萄酒的理化指標(biāo)之間的聯(lián) 系時(shí)，還用到了多元線性回歸分析. 該模型用于生活實(shí)踐中，也可以解決很多實(shí)際問題. 3.2回歸分析 回歸分析是利用數(shù)據(jù)統(tǒng)計(jì)原理，對大量數(shù)

33、據(jù)進(jìn)行數(shù)學(xué)處理，并確定因變量與某些自 變量的相關(guān)關(guān)系，建立一個(gè)相關(guān)性較好的回歸方程，并加以外推，用于預(yù)測今后的因變 量的變化的分析方法. 3.2.1回歸分析的原理與方法 回歸分析是在一組數(shù)據(jù)的基礎(chǔ)上研究這樣幾個(gè)問題： 建立因變量與自變量之間的回 歸模型；對回歸模型的可信度進(jìn)行檢驗(yàn)；判斷每個(gè)自變量對因變量的影響是否顯著；判 斷回歸模型是否適合這組數(shù)據(jù)；利用回歸模型對進(jìn)行預(yù)報(bào)或控制回歸分析主要包括一 元線性回歸、多元線性回歸、非線性回歸. 回歸分析的主要步驟為： （1）根據(jù)自變量和因變量的關(guān)系，建立回歸方程. (2) 解出回歸系數(shù). (3) 對其進(jìn)行相關(guān)性檢驗(yàn)，確定相關(guān)系數(shù). (4) 當(dāng)符合相關(guān)性

34、要求后，便可與具體條件結(jié)合，確定預(yù)測值的置信區(qū)間 . 需要注意的是，要盡可能定性判斷自變量的可能種類和個(gè)數(shù)，并定性判斷回歸方程 的可能類型10 另外，最好應(yīng)用高質(zhì)量的統(tǒng)計(jì)數(shù)據(jù)，再運(yùn)用數(shù)學(xué)工具和相關(guān)軟件定量定性 判斷. 3.2.2回歸分析應(yīng)用實(shí)例 例3.2 (2006年高教社杯全國大學(xué)生數(shù)學(xué)建模競賽 B題)艾滋病療法的評價(jià)及療 效的預(yù)測. 題目同例2.1 . 問題求解過程分析 由于題目具有開放性，故選擇文獻(xiàn)3中的求解思路進(jìn)行分析 問題2的解決就用到回歸模型.首先分析數(shù)據(jù)知，應(yīng)建立時(shí)間的一次與二次函數(shù)模 型，并經(jīng)過統(tǒng)計(jì)分析比較，確定哪種較好所以可建立一個(gè)統(tǒng)一的回歸模型，也可對每 種療法分別建立一個(gè)

35、模型. 以總體回歸模型為例，分別用一次與二次時(shí)間函數(shù)模型進(jìn)行比較，可知療法13用 一次模型較優(yōu)，且一次項(xiàng)系數(shù)為負(fù)，即 CD 4 在減少，從數(shù)值看療法3優(yōu)于療法2和1 ; 療法4用二次模型較優(yōu)，即 CD4 先增后減，在 t=20 左右達(dá)到最大可以通過4條回歸 曲線進(jìn)行比較，顯示療法4在 30 周之前明顯優(yōu)于其它最后再用檢驗(yàn)法作比較，結(jié)果是 療法1與2無顯著性差異，而療法1與3，2與3，3與4均有顯著性差異. 4圖論建模方法 圖論建模方法在建模競賽中也經(jīng)常涉及，應(yīng)用十分廣泛，并且解法巧妙，方法靈活 多變.如1990年B題“掃雪問題”，1991年B題“尋找最優(yōu)Ste in er樹”，1992年B題

36、“緊急修復(fù)系統(tǒng)的研制”，1993年B題“足球隊(duì)排名”，1994年A題“逢山開路問題”， 1994年B題“鎖具裝箱問題”，1995年B題“天車與冶煉爐的作業(yè)調(diào)度” ，1997年B題 “截?cái)嗲懈畹淖顑?yōu)排列”，1998年B題“災(zāi)情巡視最佳路線”，1999年B題“鉆井布局”， 2007年B題“城市公交線路選擇問題”等都應(yīng)用到了圖論的方法. 圖論近幾年來發(fā)展十分迅速，在物理、化學(xué)、生物學(xué)、地理學(xué)、計(jì)算機(jī)科學(xué)、信息 論、控制論、社會科學(xué)、軍事科學(xué)以及計(jì)算機(jī)管理等方面都有著廣泛的應(yīng)用.因此圖論 越來越受到了全世界數(shù)學(xué)界和工程技術(shù)界乃至經(jīng)營決策管理者的重視. 同時(shí)也成為了數(shù) 學(xué)建模中一種十分重要的方法.圖論問

37、題算法很多， 包括最短路、 最大流、 最小生成樹、 二分匹配、floyd、frim 等. 4.1兩種常見圖論方法介紹 圖論中的圖是由平面上的一些點(diǎn)及這些點(diǎn)之間的連線(稱為邊)構(gòu)成的.圖中的點(diǎn) 表示要研究的離散對象，邊表示對象之間的關(guān)系用這些點(diǎn)和邊建立的離散對象來建立 模型，通過這種辦法許多難題都可以被巧妙地解決.所以圖論方法成為研究離散問題的 一種重要手段.由于圖論方法所包含的概念和定義較多，無法全部列舉.在這里只就其 中的兩種方法作介紹. 11 4.1.1模擬退火法的基本原理 模擬退火法是模擬熱力學(xué)中系統(tǒng)的降溫過程， 當(dāng)孤立粒子系統(tǒng)的溫度以足夠慢的速 度下降時(shí)，系統(tǒng)近似處于熱力學(xué)平衡狀態(tài)，最

38、后系統(tǒng)將達(dá)到本身的最低能量狀態(tài)，即基 態(tài)，這相當(dāng)于能量函數(shù)的全局極小點(diǎn).其步驟如下 (也稱為Metropolis過程)： (1) 給定初始溫度 To，及初始點(diǎn)，計(jì)算該點(diǎn)的函數(shù)值 f x ; (2) 隨機(jī)產(chǎn)生擾動 x，得到新點(diǎn) 八x 泳計(jì)算新點(diǎn)函數(shù)值 f x ,及函數(shù)值差 f = f xj f x ； (3) 若-：f 0，則接受新點(diǎn)，作為下一次模擬的初始點(diǎn)； (4) 若：f 0，則計(jì)算新點(diǎn)接受概率： 也 f、 p(f )=exp - I， I K T 丿 產(chǎn)生 0,1 區(qū)間上均勻分布的偽隨機(jī)數(shù) r , R 0,11，如果 p f - r，則接受新點(diǎn)作為下一 次模擬的初始點(diǎn)；否則放棄新點(diǎn)，仍取原

39、來的點(diǎn)作為下一次模擬的初始點(diǎn). 4.1.2最短路問題 最短路問題是一個(gè)有著廣泛應(yīng)用價(jià)值的問題，例如各種管道的鋪設(shè)，線路的安排， 輸送網(wǎng)絡(luò)費(fèi)用等問題，都可以用到最短路求法. 在解決實(shí)際問題時(shí)，我們問題中的“邊權(quán)”可以有著各種不同的解釋.例如在運(yùn)輸 網(wǎng)絡(luò)中，從v運(yùn)送一批貨物到u，若“邊權(quán)”視為通常意義下的路程，則最短路問題就是 使運(yùn)輸總路程最短的路線，若“邊權(quán)”表示運(yùn)輸時(shí)間，則最短路就是運(yùn)輸總時(shí)間最短的 路線，“邊權(quán)”也可以代表費(fèi)用，這時(shí)相應(yīng)的就是總費(fèi)用最省的的路線. 4.2圖論建模應(yīng)用實(shí)例 例4.2 （ 2007年高教社杯全國大學(xué)生數(shù)學(xué)建模競賽 B題） 城市公交線路選擇問題. 在2007年B題中

40、， 涉及到了北京公交車的換乘問題， 為了使乘客利益最大化， 需 要設(shè)計(jì)一個(gè)“公交線路選擇自主查詢系統(tǒng)”，其核心是線路選擇的模型，該模型必須考 慮實(shí)際情況，滿足查詢者的各種不同需求要求解決如下問題： （1）僅考慮公汽線路， 給出任意兩公汽站點(diǎn)之間線路選擇問題的一般數(shù)學(xué)模型與算法. （2）同時(shí)考慮公汽與地 12 鐵線路，解決以上問題.（3）假設(shè)又知道所有站點(diǎn)之間的步行時(shí)間，請你給出任意兩站 點(diǎn)之間線路選擇問題的數(shù)學(xué)模型. 問題求解過程分析 由于題目具有開放性，故選擇文獻(xiàn)中的求解思路進(jìn)行分析. 由于在現(xiàn)實(shí)情況下，乘客一般不能乘坐一輛公交車就到達(dá)終點(diǎn)，可能會換乘，但要 是頻繁倒車，會給乘客造成不便，也

41、會增加車費(fèi)所以可針對城市公交線路選擇問題建 立模型.為了使問題簡單化，我們分別以乘車時(shí)間、乘車費(fèi)用以及換乘次數(shù)為目標(biāo)函數(shù)， 得到各自的較優(yōu)線路，再通過對比，有效地處理這些線路，最終得出查詢系統(tǒng)給出的結(jié) 果. 首先固定換乘次數(shù)n，通過集合論的相關(guān)知識把確定換乘點(diǎn)的具體位置，轉(zhuǎn)化成確 定一些集合間的交集，從而建立集合尋線算法，再根據(jù)集合相關(guān)公式，得到所有可行線 路；進(jìn)一步考慮時(shí)間和費(fèi)用等因素，對可行線路進(jìn)行處理比較，得出最佳線路. 圖論模型中，通過圖論的知識將整個(gè)北京市交通線路構(gòu)建出一個(gè)有向圖，每個(gè)站點(diǎn) 與有向圖的頂點(diǎn)一一對應(yīng)，同一線路上的相鄰站點(diǎn)對應(yīng)為有向邊， 通過不同目標(biāo)（時(shí)間、 費(fèi)用）給有向圖進(jìn)行不同的賦權(quán)，分別將不同目標(biāo)轉(zhuǎn)化為賦權(quán)有向圖尋找最短有向路， 根據(jù)最短路徑算法，得到最佳線路最后綜合評價(jià)了兩個(gè)模型的優(yōu)缺點(diǎn). 以每個(gè)站點(diǎn)為頂點(diǎn)，若站點(diǎn) A到站點(diǎn)B有公交線路并且A與B為相鄰站點(diǎn)，則連一 條A到B有向邊， 根據(jù)所給的站點(diǎn)與線路我們建立一個(gè)得到一個(gè)有重邊的有向圖 DV,E 條公交線路就是DV,E的一條有向路則任意兩公汽站點(diǎn)之間線路最少時(shí)間 選擇問題就轉(zhuǎn)化為求DV,E,W的對應(yīng)兩頂點(diǎn)的最短有向路問題. 由圖論模型所得的查詢系統(tǒng)，是以圖論知識中的最短路有向圖為基礎(chǔ)，對不同線路 經(jīng)過同一站點(diǎn)時(shí)，假設(shè)多個(gè)假想點(diǎn)，并將各不同