美賽常用模型-數學建模美賽常用模型介紹

數學建模競賽發展到今天已經有幾十年的歷史，所誕生出的模型也百花齊放，各有各的特點，短時間內掌握全部模型是不可能的，但我們可以學習經典模型，吃透這些經典模型，其它方法也能觸類旁通。今天我們介紹美賽中常見的幾類問題（評價、決策、預測、聚類和最短路）求解方法。

1.層次分析法（AHP）——評價/決策問題

層次分析法是將定性問題定量化處理的一種有效手段，因此它可以廣泛用于評價問題和決策問題。面臨各種各樣的方案，要進行比較、判斷、評價、最后作出決策，例如去某地旅游要考慮景色、費用、居住、飲食和旅途等費用，不同地區在這些方面各有特點，如果只是憑借經驗處理這些問題，主觀性較強，不能使人信服。

第一步：建立層次結構模型

一般分為三層，最上面為目標層，最下面為方案層，中間是準則層或指標層。

在層次劃分及因素選取時，我們要注意三點：

1. 上層對下層有支配作用；

2. 同一層因素不存在支配關系（相互獨立）；

3. 每層因素一般不要超過9個。

第二步：構造成對比較陣

面對的決策問題：要比較n個因素對目標的影響。我們要確定它們在目標層中所占的比重（權重），可以用兩兩比較的方法將各因素的重要性量化（兩個東西進行比較，最能比較出它們的優劣及優劣程度）。

第三步：一致性檢驗

我們發現，在給出成對比較矩陣的時候存在一定主觀性，因此需要通過一致性檢驗判斷成對比較矩陣的合理性。

1、計算一致性指標CI用來衡量成對比較矩陣的不一致程度。

2、查找相應的平均隨機一致性指標RI

3、計算一致性比例CR

當CR<0.1時，認為矩陣A的不一致性是可以接受的，反之，應該修改成對比較矩陣。

步驟四：計算權重向量

求矩陣A的最大特征值所對應的向量，并歸一化，即可作為權向量。權向量的各個權重就是決策層對目標層的影響大小。把每一層對上一層的權重依次乘起來，即可得到最終的權向量，有大到小排列即可得到評價標準或者決策方案。

注意以下2點：

1、層次分析法只能從現有的方案中選擇出較優的一個，并不能提供出一個新的或是更好的方案來；

2、建立層次結構及成對比較矩陣，主觀因素起很大作用，這是一個無法克服的缺點，因此我們建議比賽時如果要用這種方法，可以在網上查找充足的資料，再由小組共同打分或者單獨打分取平均值，以此規避主觀性，此外，一致性檢驗必不可少。

2.狄克斯特拉（Dijkstra）算法——最短路問題

最短路問題是圖論應用的基本問題，很多實際問題，如線路的布設、運輸安排、運輸網絡最小費用流等問題,都可通過建立最短路問題模型來求解。

Dijkstra算法采用的是一種貪心的策略，為了在計算機上描述圖與網絡，我們采用鄰接矩陣表示法，其中鄰接矩陣是表示頂點之間相鄰關系的矩陣，記為

聲明一個數組dis來保存源點到各個頂點的最短距離和一個保存已經找到了最短路徑的頂點的集合：T。初始時，原點 s 的路徑權重被賦為0（dis[s] = 0）。若對于頂點 s 存在能直接到達的邊（s,m），則把dis[m]設為w（s, m）,同時把所有其他（s不能直接到達的）頂點的路徑長度設為無窮大。即根據距離給W賦權：

初始時，集合T只有頂點s。然后從dis數組選擇最小值，則該值就是源點s到該值對應的頂點的最短路徑，并且把該點加入到T中，此時完成一個頂點。然后我們需要查看新加入的頂點是否可以到達其他頂點，并且查看通過該頂點到達其他點的路徑長度是否比原點直接到達短？如果是，那么就替換這些頂點在dis中的值，然后又從dis中找出最小值，重復上述動作，直到T中包含了圖的所有頂點。

3.k-近鄰算法（KNN）——聚類問題

聚類問題常見于數據處理，聚類算法通過感知樣本間的相似度，進行歸類歸納，對新的輸入進行輸出預測，輸出變量取有限個離散值。KNN是一種基于實例的監督學習算法，選擇合適的參數k就可以進行應用。

k近鄰法的特殊情況是k=1的情形，稱為最近鄰算法。

優點：精度高、對異常值不敏感、無數據輸入假定；缺點：計算復雜度高、空間復雜高。

算法三要素：k值的選擇、距離度量、分類決策規則。如果選擇較小的值，分類結果會對近鄰的實例點非常敏感，如果鄰近的實例點恰巧是噪聲，分類就會出錯；如果選擇較大的值，與輸入實例較遠的(不相似的點)也會對分類產生影響，使分類發生錯誤。關于如何選擇合適的k，沒有固定的計算方法，而是依賴經驗。

距離的度量一般采用歐氏距離，優點在于計算量小，容易解釋且足夠準確。

分類決策規則采用"投票法" ，即選擇這k個樣本中出現最多的類別標記作為預測結果或者采用"平均法" ，即將k個樣本的實值輸出標記平均值作為預測結果；還可基于距離遠近進行加權平均或加權投票，距離越近的樣本權重越大

4.灰色預測——預測模型

對于一些預測問題，如氣象預報、地震預報、病蟲害預報等可以用灰色預測模型解決。

灰色預測是一種對含有不確定因素的系統進行預測的方法?；疑A測通過鑒別系統因素之間發展趨勢的相異程度，即進行關聯分析，并對原始數據進行生成處理來尋找系統變動的規律，生成有較強規律性的數據序列，然后建立相應的微分方程模型，從而預測事物未來發展趨勢的狀況。其用等時距觀測到的反應預測對象特征的一系列數量值構造灰色預測模型，預測未來某一時刻的特征量，或達到某一特征量的時間。

步驟一：生成數列

通過對原始數據的整理尋找數的規律，分為三類：

1. 累加生成：通過數列間各時刻數據的依個累加得到新的數據與數列。累加前數列為原始數列，累加后為生成數列。

2. 累減生成：前后兩個數據之差，累加生成的逆運算。累減生成可將累加生成還原成非生成數列。

3. 映射生成：累加、累減以外的生成方式。

步驟二：建立模型

把原始數據加工成生成數，對殘差（模型計算值與實際值之差）修訂后，建立差分微分方程模型，基于關聯度收斂分析。GM模型所得數據須經過逆生成還原后才能用。

以上就是美賽中常見的數學模型，大家可以注意到，有些模型涵蓋了多個問題，比如層次分析法既可以解決決策問題，也可以解決評價問題，這啟發我們競賽時既要根據問題選擇合適的模型，又要靈活運用模型做出合理的優化。

希望同學們可以熟練掌握以上模型，并且在此基礎上不斷學習，一方面探索經典模型的優化方法，學會“舊瓶裝新酒”，另一方面學習新的方法，不斷擴充自己的知識體系。