ANPのソースを表示

'''【えいえぬぴー (ANP (analytic network process))】'''
=== 概要 ===
AHPの階層構造をネットワーク構造に拡張したもの. AHPの評価構造は評価基準が代替案を評価するというように, 評価者と被評価者の区別が固定しているが, ANPでは, 被評価者自身が, 評価者の評価の重要度あるいは評価能力を評価するという問題をも取り扱う. サーティ (T.L. Saaty) はこの評価構造の関連を超行列という一種の確率行列で表現し, その累乗の極限によって分析する方法を示した.
=== 詳説 ===

　AHPの特徴は, 一対比較の情報に基づいて固有ベクトル法を用いて各対象の評価値を推定するという面と, いくつかの評価基準の下での評価値を総合化するという階層構造にあった. T. L. Saatyの提案したANPというのは, 簡単に言うと, その階層構造をネットワーク構造に拡張したものである. Saatyはこのネットワーク構造の解析の基本として, 超行列とよばれる行列を導入し, その行列としての性質, 既約性や原始性を利用して解析法を確立した. 

[超行列]

　はじめに簡単な例を通して, ANPの特徴をつかもう. たとえば食品産業の3社<math>A_1, A_2, A_3\, </math>を代替案とみて, これらを2つの評価基準<math>C_1\, </math>(広告), <math>C_2\, </math>(サービス)で評価するという問題を考えよう. <math>A_i\, </math>の<math>C_j\, </math>による評価値が<math>u_{ij}\, </math>であるとしてこれらを列挙すると表1のようになる. <math>A_j\, </math>の企業戦略として広告とサービスにそれぞれ<math>w_{1j}\, </math>, <math>w_{2j}\, </math>の重要度を考えているとすると<math>(j=1,2,3)\, </math>, <math>C_1\, </math>, <math>C_2\, </math>の重要度の評価は, AHPのように一組だけでなく, <math>A_j\, </math>によって変化して表2のようになる. 


<center><table><tr><td align=center>表1: <math>A_i\, </math>の<math>C_j\, </math>による評価<br></td></tr>
<tr><td align=center>[[画像:sk-0231-a-h-08-1.png]]</td></tr>
<td align=center><br></td></table></center>

<!--
\begin{table} \caption{$A_i$の$C_j$による評価} \label{A-H-08+tab:1st} \begin{center} \begin{tabular}{c|cc|} \multicolumn{1}{c}{} &\multicolumn{1}{c}{$C_1$} &\multicolumn{1}{c}{$C_2$} \\ \cline{2-3} $A_1$ & $u_{11}$ & $u_{12}$ \\ $A_2$ & $u_{21}$ & $u_{22}$ \\ $A_3$ & $u_{31}$ & $u_{32}$ \\ \cline{2-3} \end{tabular} \end{center} \end{table} 
-->


<center><table><tr><td align=center>表2: <math>C_i\, </math>の<math>A_j\, </math>による評価<br></td></tr>
<tr><td align=center>[[画像:sk-0231-a-h-08-2.png]]</td></tr>
<td align=center><br></td></table></center>

<!--
\begin{table} \caption{$C_i$の$A_j$による評価}\label{A-H-08+tab:2nd} \begin{center} \begin{tabular}{c|ccc|} \multicolumn{1}{c}{} &\multicolumn{1}{c}{$A_1$} &\multicolumn{1}{c}{$A_2$} &\multicolumn{1}{c}{$A_3$} \\ \cline{2-4} $C_1$ & $w_{11}$ & $w_{12}$ & $w_{13}$ \\ $C_2$ & $w_{21}$ & $w_{22}$ & $w_{23}$ \\ \cline{2-4} \end{tabular} \end{center} \end{table}
-->


　これは<math>C_i\, </math>が<math>A_j\, </math>を評価するだけでなく, <math>A_j\, </math>自身が<math>C_i\, </math>の重要度を評価することを示している. つまりANPでは, 評価者と被評価者の区別が固定したものでなく, 互いに他を評価するという一種の相互評価の構造がある. 

　対象<math>i\, </math>の<math>j\, </math>による評価値(評価がない場合は0)を<math>i\, </math>行<math>j\, </math>列として得られる行列が超行列(super matrix)と呼ばれるものである. 上の例の超行列は

<center><table><tr><td align=center>[[画像:sk-0231-a-h-08-3.png]]　　　　　<math> (1) \, </math></td></tr>
<td align=center><br></td></table></center>

<!--
\begin{equation} S= \begin{array}{c|cccccc|} \multicolumn{1}{c}{} &\multicolumn{1}{c}{C_1} &\multicolumn{1}{c}{C_2} &\multicolumn{1}{c}{} &\multicolumn{1}{c}{A_1} &\multicolumn{1}{c}{A_2} &\multicolumn{1}{c}{A_3}\\ \cline{2-7} C_1 &0 &0 & &w_{11} &w_{12} &w_{13} \\ C_2 &0 &0 & &w_{21} &w_{22} &w_{23} \\ A_1 &u_{11} &u_{12} & &0 &0 &0 \\ A_2 &u_{21} &u_{22} & &0 &0 &0 \\ A_3 &u_{31} &u_{32} & &0 &0 &0 \\ \cline{2-7} \end{array} \label{A-H-08+eq:1st} \end{equation} 
-->


　ANPの解析の目的はこの超行列が与えられたとき, 各対象(上例では<math>C_1, C_2, A_1, A_2, A_3\, </math>)の総合評価値を求めることである. またANPでは与えられる評価値はすべて正であり, 一つの対象が与える評価値の総和は1であるという規約がある. つまり超行列の各列の要素の和は1である. このことは超行列が(列)確率行列であることを示している. 

[ネットワーク構造]

　対象<math>i\, </math>が<math>j\, </math>を評価するとき(つまり超行列の<math>(i,j)\, </math>要素が非ゼロのとき)そしてそのときに限り, 点<math>i\, </math>から点<math>j\, </math>への矢線をもつ有向グラフが得られるが, これをこのANPのネットワーク構造と呼ぶ. 上例に対するネットワークは図1のようになる. このグラフ構造の特徴が超行列<math>S\, </math>の行列としての性質に密接に関連していて, それがANPの解析を特徴づける. 

　すでにAHPの中に外部従属法という解析法があるが, これはANPの特殊なもので, そのネットワーク構造が図1のように2部グラフの形をしたものである. ANPの新しさは, このネットワーク構造がどんなものであっても, 超行列を基本として一貫した解析法で総合評価値を求めることができることにある. 


<center><table><tr><td align=center>[[画像:sk-0231-a-h-08-4.png]]</td></tr>
<td align=center>図1: ネットワーク構造<br></td></table></center>

<!--
\begin{figure}[htbp] \begin{center} %\includegraphics[8.2cm,3.5cm]{Fig1.bmp} %WinTpicVersion2.15 \unitlength 0.1in \begin{picture}(26.25,8.00)(1.75,-11.15) % STR 2 0 3 0 % 3 1000 700 1000 800 5 0 % $C_1$ \put(10.0000,-4.0000){\makebox(0,0){$C_1$}}% % STR 2 0 3 0 % 3 2200 700 2200 800 5 0 % $C_2$ \put(22.0000,-4.0000){\makebox(0,0){$C_2$}}% % STR 2 0 3 0 % 3 400 1500 400 1600 5 0 % $A_1$ \put(4.0000,-12.0000){\makebox(0,0){$A_1$}}% % STR 2 0 3 0 % 3 1600 1500 1600 1600 5 0 % $A_2$ \put(16.0000,-12.0000){\makebox(0,0){$A_2$}}% % STR 2 0 3 0 % 3 2800 1500 2800 1600 5 0 % $A_3$ \put(28.0000,-12.0000){\makebox(0,0){$A_3$}}% % VECTOR 2 0 3 0 % 14 1000 900 400 1500 400 1500 1000 900 1000 900 1600 1500 1600 1500 2200 900 %2200 900 2800 1500 2800 1500 2200 900 2200 900 1600 1500 % \special{pn 8}% \special{pa 1000 500}% \special{pa 400 1100}% \special{fp}% \special{sh 1}% \special{pa 400 1100}% \special{pa 461 1067}% \special{pa 438 1062}% \special{pa 433 1039}% \special{pa 400 1100}% \special{fp}% \special{pa 400 1100}% \special{pa 1000 500}% \special{fp}% \special{sh 1}% \special{pa 1000 500}% \special{pa 939 533}% \special{pa 962 538}% \special{pa 967 561}% \special{pa 1000 500}% \special{fp}% \special{pa 1000 500}% \special{pa 1600 1100}% \special{fp}% \special{sh 1}% \special{pa 1600 1100}% \special{pa 1567 1039}% \special{pa 1562 1062}% \special{pa 1539 1067}% \special{pa 1600 1100}% \special{fp}% \special{pa 1600 1100}% \special{pa 2200 500}% \special{fp}% \special{sh 1}% \special{pa 2200 500}% \special{pa 2139 533}% \special{pa 2162 538}% \special{pa 2167 561}% \special{pa 2200 500}% \special{fp}% \special{pa 2200 500}% \special{pa 2800 1100}% \special{fp}% \special{sh 1}% \special{pa 2800 1100}% \special{pa 2767 1039}% \special{pa 2762 1062}% \special{pa 2739 1067}% \special{pa 2800 1100}% \special{fp}% \special{pa 2800 1100}% \special{pa 2200 500}% \special{fp}% \special{sh 1}% \special{pa 2200 500}% \special{pa 2233 561}% \special{pa 2238 538}% \special{pa 2261 533}% \special{pa 2200 500}% \special{fp}% \special{pa 2200 500}% \special{pa 1600 1100}% \special{fp}% \special{sh 1}% \special{pa 1600 1100}% \special{pa 1661 1067}% \special{pa 1638 1062}% \special{pa 1633 1039}% \special{pa 1600 1100}% \special{fp}% % VECTOR 2 0 3 0 % 4 1000 900 2800 1500 2800 1500 1000 900 % \special{pn 8}% \special{pa 1000 500}% \special{pa 2800 1100}% \special{fp}% \special{sh 1}% \special{pa 2800 1100}% \special{pa 2743 1060}% \special{pa 2749 1083}% \special{pa 2730 1098}% \special{pa 2800 1100}% \special{fp}% \special{pa 2800 1100}% \special{pa 1000 500}% \special{fp}% \special{sh 1}% \special{pa 1000 500}% \special{pa 1057 540}% \special{pa 1051 517}% \special{pa 1070 502}% \special{pa 1000 500}% \special{fp}% % VECTOR 2 0 3 0 % 4 2200 900 400 1500 400 1500 2200 900 % \special{pn 8}% \special{pa 2200 500}% \special{pa 400 1100}% \special{fp}% \special{sh 1}% \special{pa 400 1100}% \special{pa 470 1098}% \special{pa 451 1083}% \special{pa 457 1060}% \special{pa 400 1100}% \special{fp}% \special{pa 400 1100}% \special{pa 2200 500}% \special{fp}% \special{sh 1}% \special{pa 2200 500}% \special{pa 2130 502}% \special{pa 2149 517}% \special{pa 2143 540}% \special{pa 2200 500}% \special{fp}% \end{picture}% \caption{ネットワーク構造} \label{A-H-08+fig:1st} \end{center} \end{figure} 
-->


[ANPの解法]

　SaatyのANPの解法は, 超行列の累乗<math>S^t\, </math>の<math>t\to\infty\, </math> での極限を利用するものであるが, <math>S\, </math>の行列としての性質によって, その収束状態が異なってくる. 

　一般に行列の性質はそれに対応する有向グラフの特性と密接に関連する. 行列論でいう行列の既約性 (irreducibility)は, 対応する有向グラフが強連結であることと同値である. (有向グラフの任意の2点<math>i,j\, </math>に対して<math>i\, </math>から<math>j\, </math>への有向パスがあれば, このグラフを強連結という). 

　また非負の既約行列<math>X\, </math>が原始(primitive)であるとは, 適当な自然数<math>n\, </math>に対して<math>X^n\, </math>の要素がすべて正となることであるが, これはこの行列に対応する有向グラフの周期が1であることと同値である [1]. 周期とはすべての有向サイクル(ある点からその点にはじめて戻る有向パス)の長さの最大公約数<math>d\, </math>である. 図1での有向サイクルの長さは, <math>2,4,6,\cdots\, </math> であるので周期は<math>d=2\, </math>である. 

　超行列<math>S\, </math>に対応する有向グラフの周期<math>d\, </math>がANPの解法に重要な役割を果たす. SaatyによるANP解法の基本はつぎの定理に要約される [1]：

'''定理'''　<math>m\times n\, </math>超行列<math>S\, </math>が既約であってかつ原始(<math>S\, </math>に対応する有向グラフの周期が1)であれば, <math>t\to\infty\, </math>で<math>S^t\, </math>は収束しその極限値<math>S^{\infty}\, </math>はすべての列が同一ベクトル <math>\mathbf{x}\, </math>となる. つまり


<center><math>lim_{t\to\infty}S^t=S^{\infty}=[ \mathbf{x} \mathbf{x} \cdots \mathbf{x} \mathbf{x}]\, </math>　　　　　<math>(2)\,</math></center> 


そしてこの <math>\mathbf{x}=[x_1x_2\cdots x_n]^{\top}\, </math>の要素<math>x_i\, </math>を対象<math>i\, </math>の総合評価値とみることができる.

'''定理'''　超行列<math>S\, </math>が既約であって, 対応する有向グラフの周期を<math>d\, </math>とするとき<math>t\to\infty\, </math>で<math>(S^d)^t\, </math>が収束し, その極限値で行と列を適当に並べかえたものを<math>S^{\infty}\, </math>とすると, これは<math>d\, </math>位のブロック対角行列となり, 各ブロック内ではすべての列が同一ベクトルとなる. 

たとえば<math>d=2\, </math>なら


<center><math>
\begin{array}{ccc}
S^{\infty}=
\left[
\begin{array}{cc}
S_1 & O  \\
O   &S_2 \\
\end{array}
\right]
& , &
\begin{array}{c}
S_1=[ \mathbf{x}_1 \mathbf{x}_1\cdots \mathbf{x}_1] \\
S_2=[ \mathbf{x}_2 \mathbf{x}_2\cdots \mathbf{x}_2] \\
\end{array}
\end{array}\, </math>　　　　　<math>(3)\,</math></center> 


となり,  <math>\mathbf{x}_i\, </math>の各成分が対象の総合評価値を与える. 

[超行列の固有ベクトル]

　最近, 高橋, 関谷 [2], [3] は, <math>S\, </math>が既約ならば, <math>S\, </math>の主固有ベクトルが(2)等の収束ベクトル <math>\mathbf{x}\, </math>に一致することを示している. <math>S\, </math>が確率行列であるから, その主固有値は1であり, <math>S\, </math>の主固有ベクトル <math>\mathbf{x}\, </math>は


<center><math>S \mathbf{x}= \mathbf{x}\, </math>　　　　　<math>(4)\,</math></center>


の解であるが, これが(2)の <math>\mathbf{x}\, </math>と(定数倍を除いて)一致することが示されたのである. <math>S\, </math>が原始でない場合でも(4)の解はたとえば(3)の <math>\mathbf{x}_1, \mathbf{x}_2\, </math>をそのまま縦に並べたものと一致する. 

　これによるとANPの解法は極めて簡単で超行列の主固有ベクトルを求めればよいということになる. また「非負の既約行列の主固有ベクトルは(定数倍を除いて)一意であり, その成分はすべて正である」 [4] というフロベニウスの定理から, (4)の解の一意性とその値がすべて正となることが保証される. 

　以上の解法はいずれも超行列が既約であること, つまりネットワーク構造が強連結であることを前提としている. しかし [2] には必ずしも強連結でない場合についてもその解法が提案されている. 



----

'''参考文献'''

[1] T. L. Saaty, ''The Analytic Network Process'', RWS Publication, 1996. 

[2] K. Sekitani and I. Takahashi, " Unified Model and Analysis for AHP and ANP," ''Journal of the Operations Research Society of Japan'', '''44''' (2001), 67-89.

[3] 高橋磐郎, 『AHPからANPへの諸問題』, オペレーションズ・リサーチ, '''43''' (1998), 289-293.

[4] 古屋茂, 『行列と行列式』, 培風館, 1957.

[[category:AHP(階層的意思決定法)|えいえぬぴい]]