2022 美國大學生數學建模競賽（MCM/ICM）常見模型分析

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

01層次分析法（AHP）——評價(jia) /決(jue) 策問題

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

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

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

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

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

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

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

第二步：構造成對比較陣

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

最終成對比較矩陣A=（），如下圖示例：

第三步：一致性檢驗

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

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

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

3、計算一致性比例CR

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

步驟四：計算權重向量

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

注意以下2點：

1、層次分析法隻能從(cong) 現有的方案中選擇出較優(you) 的一個(ge) ，並不能提供出一個(ge) 新的或是更好的方案來；

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

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

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

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

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

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

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

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

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

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

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

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

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

04灰色預測——預測模型

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

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

步驟一：生成數列

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

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

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

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

步驟二：建立模型

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

以上就是美賽中常見的數學模型，大家可以注意到，有些模型涵蓋了多個(ge) 問題，比如層次分析法既可以解決(jue) 決(jue) 策問題，也可以解決(jue) 評價(jia) 問題，這啟發我們(men) 競賽時既要根據問題選擇合適的模型，又要靈活運用模型做出合理的優(you) 化。希望同學們(men) 可以熟練掌握以上模型，並且在此基礎上不斷學習(xi) ，一方麵探索經典模型的優(you) 化方法，學會(hui) “舊瓶裝新酒”，另一方麵學習(xi) 新的方法，不斷擴充自己的知識體(ti) 係。