數學建模十大演算法之——層次分析法

09-20

數學建模十大演算法之——層次分析法

來自專欄 Eureka機器學習讀書筆記11 人贊了文章

專欄文章匯總

文章結構如下：

1：層次分析法引例

2：層次分析法概述

2.1 遞階層次的建立

2.2 構造判斷矩陣（成對比較矩陣）

2.3 層次單排序及一致性檢驗

2.4 層次總排序及一致性檢驗

3：層次分析法的應用——彩票方案的優選模型（2002年國賽B題）

3.1 問題重述

3.2 假設和符號說明

3.3 問題分析和模型建立

3.4 模型的求解

4：參考文獻

註：本文是結合參考文獻中幾篇博客和2002年國賽一等獎論文整合而來

1：層次分析法引例

層次分析法（AHP）是美國運籌學家匹茲堡大學教授薩蒂於上世紀70年代初提出。這種方法的特點是在對複雜的決策問題的本質、影響因素及其內容在關係等進行深入分析的基礎上，利用較少的定量信息使決策的思維過程數學化，從而為多目標、多準則或無結構特性的複雜決策問題提供簡便的決策方法。

決策是指在面臨多種方案時需要依據一定的標準選擇一種方案。例如，要從三個旅遊勝地選擇一個。我們一般會根據景色、費用、居住、飲食等一些準則去反覆比較這幾個景點。從中選擇符合自己需要的景點。

2：層次分析法概述

層次分析法（AHP）是將要決策的問題及其有關因素分解成目標、準則、方案等層次，進而進行定性和定量分析的決策方法。它的特徵是合理地將定性與定量決策結合起來，按照思維、心理的規律把決策過程細緻化（層次化、數量化）。

運用層次分析法建模，大體上可按下面四個步驟進行：

建立遞階層次結構模型；
構造出各層次中的所有判斷矩陣；
層次單排序及一致性檢驗；
層次總排序及一致性檢驗。

2.1 遞階層次的建立

分層：

最高層：這一層次中只有一個元素，一般它是分析問題的預定目標和理想結果。
中間層：這一層次中包含為了實現目標所涉及的中間環節，主要是一些考慮指標和一些準則。
最底層：這一層次中包含為了實現目標可供選擇的各種方案。

層次分析法要解決的問題是，求出最底層對最高層的相對權重，以此對最底層的方案、措施進行排序，選擇最優方案。

注1：為了避免兩兩比較判斷過於複雜，每層次中各元素所支配的元素一般不要超過9個，否則應劃分為若干子層；

注2：層次分析法只考慮相鄰兩個層次間自上向下的支配作用，認為同一層次的元素間相互獨立，若考慮進來需要網路分析法（ANP）。

2.2 構造判斷矩陣（成對比較矩陣）

1、比較判別矩陣的元素意義

構造好層次模型後，針對某一層來講，在比較第 $i$ 個元素與第 $j$ 個元素相對於上一層某個因素的重要性時，使用數量化的相對重要度 $a_{ij}$ 來表示，假設共有 $n$ 個元素參與比較，則矩陣: $A=egin{pmatrix} a_{11} &cdots &a_{1n} \ vdots &ddots & vdots \ a_{n1} &cdots &a_{nn} end{pmatrix}=(a_{ij})_{n imes n}$

稱為判斷矩陣（或成對比較矩陣）。

2、比較判別矩陣的定義

定義1：若矩陣 $A=(a_{ij})_{n imes n}$ 滿足

1. $a_{ij}>0$

2. $a_{ij}=frac{1}{a_{ij}}(i,j=1,2,cdots,n)$

稱之為正反矩陣。

3、關於比較判別矩陣元素的確定

使用數字1-9以及其倒數作為標度。

2.3 層次單排序及一致性檢驗

1、原理

層次單排序：判斷矩陣 $A$ 對應於最大特徵值 $lambda_{max}$ 得特徵向量 $W$ ，經歸一化即為同一層次相應元素對於上一層次元素相對重要性的排序權值。稱為層次單排序。

一致性矩陣：滿足關係式 $a_{ij}a_{jk}=a_{ik},forall i,j,k=1,2,cdots n$ 的正反矩陣稱為一致性矩陣。

註：一致性即判斷的一種傳遞性，比如 $a$ 的重要性是 $b$ 的2倍， $b$ 的重要性是 $c$ 的2倍，則 $a$ 的重要性得是 $c$ 的4倍。否則就是判斷的不一致。

判斷一致性有如下定理： $n$ 階正反矩陣 $A$ 為一致性矩陣當且僅當其最大特徵根 $lambda_{max}=n$ ，且當正反矩陣 $A$ 非一致，必有 $lambda_{max}>n$ 。

在實際操作中，由於客觀事物的複雜性以及人們對事物判斷比較時的模糊性，很難構造出完全一致的判斷矩陣。因此，Satty在構造層次分析法時，提出了一致性檢驗，所謂一致性檢驗是指判斷矩陣允許有一定不一致的範圍。

一致性檢驗步驟如下：

(1) 計算一致性指標 $CI$ ： $CI=frac{lambda_{max}-n}{n-1}$ ， $CI=0$ 表示完全一致， $CI$ 越大越不一致；

(2) 查詢平均隨機一致性指標RI，對應 $n=1$ 到10，RI值分別為（這是通過隨機的方法生成的一組標準指標。）

(3) 計算一致性比例 $CR$ ： $CR=frac{CI}{RI}$ ，當 $CR<0.1$ ，認為矩陣的一致性是可以接受的。

2.4 層次總排序及一致性檢驗

為了實現層次分析法的最終目的，需要從上而下逐層進行各層元素對目標合成權重的計算。

1、說明

(1) $A$ 為上一層次（高的層次）， $B$ 為當前層次

(2) $a_1,a_2,a_3cdots a_m$ 為 $A$ 層次的總排序權重。

(3) $b_{1j}cdots b_{nj}$ 是 $B$ 層對 $A_j$ 的單排序權重。

(4) 從最高層到最底層，現求B層中各因素關於總目標的權重，即求B層各因素的層次總排序權重 $b_1,b_2cdots b_n$ 。就按照上圖中的方法進行計算。

2、對於層次總排序也要進行一致性檢驗。

設B層中與 $A_j$ 相關的因素的成對比較判斷矩陣在單排序中經一致性檢驗，求得單排序一致性指標為 $CI(j),(j=1,2,cdots ,m)$ ，相應的平均隨機一致性指標為 $RI(j)$ ，則 $B$ 層總排序隨機一致性比例為：

$CR=frac{sum_{j=1}^mCI(j)a_j}{sum_{j=1}^mRI(j)a_j}$

當CR<0.10，認為層次總排序結果具有較滿意的一致性並接受該分析結果。

註：實際應用中，整體一致性檢驗常不予進行。主要原因是，整體考慮十分困難；其次若每個單一準則下的判斷矩陣具有滿意的一致性，而整體達不到滿意的一致性時，調整起來非常困難。另外，整體一致性的背景也不如單一準則下的背景清晰，它的必要性有待進一步研究。

3：層次分析法的應用——彩票方案的優選模型（2002年國賽B題）

3.1 問題重述

略，相關題目可百度搜索——彩票中的數學（2002年國賽B題）

傳統型：

樂透型：

29種方案：

3.2 假設和符號說明

假設

彩票形式多種多樣，在此問題中，僅討論「傳統型」和「樂透型」兩種
假定各個不同方案均是在公正公平的原則下實施，而且彩民購買和兌獎的方便程度一樣

符號說明

$G$ ：合理度，用來評價彩票發行方案合理性的目標函數

$h_j$ ：各種因素對彩票合理度 $G$ 的影響力

$w_j$ ：各種因素對彩票合理度 $G$ 的貢獻權重

$P_i$ ：各個獎項的中獎概率

$R_i$ ：各個獎項 $i$ 的設置及獎金（高項獎 $R_i$ 為比例值，低項獎 $R_i$ 為金額）

$P_{和}$ ：彩票中獎的概率和

$C_i$ ：影響合理度的每一種因素的標準值

$I$ ：彩票方案中設置的最低級獎項，也就是獎項數

$I$ ：高項獎的獎項數

$A$ ：合理度的幾個影響因素通過兩兩比較得到的判斷矩陣

$lambda_{max}$ ：判斷矩陣 $A$ 的最大特徵值

$CI$ ：判斷矩陣 $A$ 的一致性指標

3.3 問題分析和模型建立

1、各種獎項的概率計算

（略）

2、模型建立

模型1：

作者認為高項獎的獎金比例分配、低項獎的獎金金額和彩票方案的中獎概率和是影響彩票方案合理性的最直接因素，所以從根本上看，合理度G的計算和以下因素有關：

彩票方案中各個獎項$i$的設置及獎金 $R_i(i=1,cdots,I)$
彩票中獎的概率總和$P_{和}$，這和彩票方案所採用的中彩類型和獎項設置有關。

因此可以得到合理度 $G$ 和各個因素的關係模型：

$G=f(R_1,R_2,cdots ,R_I,P_{和})$

為使各因素量綱一樣，做如下考慮：每種因素除以標準值 $C_i$ ，即 $h_i=frac{R_i}{C_i}$ 。則彩票方案合理度的目標函數定義為各種因素影響力 $h_i$ 加權平均和。

此外設置各種因素對合理度 $G$ 的貢獻權重： $W=(w_1,w_2,cdots,w_I,w)$ ，由此得到評價彩票方案合理度 $G$ 目標函數：

$G=W^TH=(w_1,w_2,cdots,w_I,w)^T(h_1,h_2,cdots,h_I,h)$

其中， $w_i$ 通過層次分析法得到，各種因素的標準值 $c_j$ 可以利用題目所給的數據通過向量的標準化得到。

模型2：

為了取得最有方案，要使得合理度$G$的目標函數達到最大值，即

$max~G=max~W^TH=max~(w_1,w_2,cdots,w_I,w)^T(h_1,h_2,cdots,h_I,h)$

約束如下：

彩票方案的中獎概率總和與彩票方案的發行類型type、彩票總數碼 $n$ 、中獎基本號碼 $m$ 、特別號碼的設置以及獎項 $I$ 的設置有關。則： $P_{和}=f(n, m, type I)$
高項獎的獎金比例和為1，所以： $sum_iR_i=1quad i=1,cdots,I$
一等獎要佔高項獎總金額的大部分（吸引彩民），則： $R_1in [alpha_1, eta_1],quad 0.5<alpha_1,eta_ile 1$
除一等獎外其他高項獎也要在某一合理範圍內： $R_iin [alpha_i,eta_i],quad i=2,cdots,I$
要提高彩票方案的吸引力，就要提高彩票方案的中獎概率和，其最直接效果就是增加獎項 $I$ ，每一個低獎項的獎金金額同樣處於某一合理區間 $[c_i,d_i]$ ： $R_iin [c_i,d_i]quad i=I+1,cdots,I$
高一等獎項肯定要比低一等獎項的獎金金額高： $egin{align*}R_i&>R_{i+1},quad i=1,cdots,I-1 \R_i&>R_{i+1},quad i=I+1,cdots,I-1 end{align*}$
根據模型1： $h_i=frac{R_i}{C_i}~~frac{P}{C_i},quad 1,2,cdots,I$

綜上所述，建立最優彩票發行方案的目標規劃模型：

$egin{align*}max~G=W^TH=(w_1,w_2,cdots,w_I,w)^T(h_1,h_2,cdots,h_I,h) \s.t.left{egin{matrix} P_{和}quad f(n,m,type,I)\ sum_i R_i=1,quad i=1,cdots,I\ R_iin [alpha_i,eta_i],quad i=1,cdots,I\ R_iin [c_i,d_i],quad i=I+1,cdots,I\ R_i>R_{i+1}quad i=1,cdots,I-1\ R_i>R_{i+1}quad i=I+1,cdots,I-1\ h_i=frac{R_i}{C_i}~frac{P}{C_i}quad i=1,2,cdots,I end{matrix} ight. end{align*}$