ÅHPからANPへの諸問題Ⅴ
高橋 磐郎………………‖‖‖‖‖＝‖‖‖＝＝‖‖‖‖‖‖…ll………l…l…l……l…………l………ll……………lll………………l………l…………………llllll………………………………………l…………l棚‖……………llll………l…l……ll…………州l7。AN■Pの解法

この定理の証明はやはり、ここでは省略するが第1講〔卯こ詳しい。この定理は、後ほど述べるように、ANP

ここまでで、AN■Pと相互評価問題とは数学的には解析のときの超行列の主固有ベクトルをパワー法でまったく同じ構造を持つシステムであって、その超行求めるときの収束の保証を与えてくれる。

列に対するグラフ的特徴から様々なパターンがあるこ

さて既約行列に対する定理2に相当する内容はどとをみてきた。つまり既約（強連結）か否か、また同じのようになるかというと、先に述べた周期の概念が重既約であっても原始か否かの区別があり、これらによ要な役割を持つ次の定理で示される（第1講［句）。ってANPの解析法が少しずつ異なってくるのである。

そこでANPの解法を述べる前に行列の性質について

定理3 確率行列が周期cの既約行列であれば、絶対述べておこう。

値が1となる固有値は（最大固有値1を含めて）丁度c個だけ存在する。これらを入1（＝入max），入2，…，Å。と7。且 既約行列、原始行列の性質

すると

さて、既約行列や原始行列の行列としての性質がl入1l＝l入2l＝・‥＝】入。i＝1（7・2）

ANP解析に極めて重要な役割を果たす。
であって、これ以外の固有値の絶対値はすべて1より
定理且 確率行列が既約行列であれば、その最大固有小さい。

値は1であって、それは（固有方程式の）単根である。
したがって対応する固有ベクトルは（定数倍を除いて）実際に計算してみると§6例1の行列の周期は2でそ一意に決まり、かつその成分はすべて正である（ゼロの固有値は最初の2つだけが絶対値が1となる。または含まれない）。

§6例4の行列Aの周期は3であるが、Aの固有方程式
は

この定理は§2．3で述べた定理1とほぼ同様の形式で、フロベニクスの定理から証明される。原始行列は（入−1）（入2＋入＋1）＝0既約行列であるから、定理1は無論原始行列についても成り立っが、原始行列の場合はさらに次の定理が成となるので、入1＝1，入2，入3＝（−1士1乃五）／2となり、り立つ。

これらは1の3乗根である。一般に定理3の入1，…，入。
は1のc乗根となる。

定理2 確率行列が原始行列であれば、最大固有値7。2 ANP解析の基本原理

入max（＝入1）以外の固有値入2，入3ク…（一般には複素数も含まれる）の絶対値はつねに1より小さい。つまり
l袖＜1（ノ＝2，3，＝・）

まず簡単な例として、§6で述べた図3のパターン（7．1）

を例にとって解析の原理を考えてみよう。これは2つのクラスターA，βからなり、Aクラスターの要素はAl，…，Aαでβクラスターは月1，…，β♭からなり、そのたかはし いわろう 日本大学生産工学部

超行列は〒275千葉県習志野市泉町1−2−1g＝［￡：］
1998年5 月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（35）289

Tユ

机＝こ二︵U ＝−〇となり、以下同様の関係が成立し、これらをまとめるとnつ︺
γ山だlぶ2

爪孟 ご㍑

¶皿

l1

㍉．．

．．

・‖

α ¶瓜馳㈹ひ ○ 勺

勘 爪ぴ ん⁝

（7．3）

旬⊥

ァ：

αの2．′

l

仇∵ぴ

ハU

ハU

明地

鮎陀1視れ2 …らの形をしていて、これは既約であり、その周期は2で髄あ￠のとなる。この左辺の係数行列は過行列ガであるから、あることを思い起こそう。

ニ・い、・∴ ∴・・盲 、しここで嘗酢はクラスタ…濾の腰への評価行列、yは腰（7。∂）

題遠∵＝題のAへの評価行列である。このように超行列が与えられたとき、各対象の総合評価をどのように定めるかがという形になる。（7白6）式も（7由8）式の特別な場合に過ÅN㌘の解析法である。

ぎない。（7廿8）式がÅN剛こおいて超行列鳳から総合評

濾且，…，Aαの総合評価を∬19…ラ黒血、」軌，…戯のそれ

価ベクトル憲を求めるための基本方程式である。これらを凱，…，馳とすると、§2．5で述べた総合評価の基本は、超行列腰の作用によって不変となるベクトルⅢが総方程式（2。7）あるいは時刻から、合評価を与えるというのがÅNP解析の基本原理であることを示している。なお（7．8）式で、厨をマルコフ過勺エ・

疇且

イり1i〉

程の推移確率行列とみなしたとき、悪は極限分布に相∵．
lブ爪：こびことに気がつく。

また（7山8）式（あるいは（7．7）式）は∬1，…ヲ∬mに関す硯⁝甘が且且当しているので、総合評価と極限分布が対応している

・ハ・．

α引

射込小川け仔りnu汀ほじけMM許

モノ1； 一‥偏あ（7。4）る同次（定数項のない）連立一次方程式に過ぎないか
ら普通の掃出法で解くことができる。また（7。8）式ほ通がガの、固有値且に対する固有ベクトルであるというが成り立たねばならない。

見方もできるからパワー法のような固有ベクトル解、∴−． ．・…、●・i∴・J．．

法で求めることもできる。実際の計算では後者のほうがはるかに効率が良い。

としてまとめると∴ − ′・′＿・・ −・・∴・−：、（7。5）

常⑳為 義本籍曜或の解法
まず基本方程式（7。8）式は同次方程式だから、荘がそとなる。さらに悪と暫をまとめてα＋ゐ次元のベクトルの解であれば、その一定倍α淀もまたその解となる。しとして（ア匂5）を書き直サとかしこの定数倍を除いて解が一意かどうかという問

α・・ニ・・

題が重要であるが、ガが既約であればの§7，且定理1がそれを保証してくれる。これを基本方経式の解というとなる。

見方から言い換えた形で次の定理としてまとめてお§6囁2の（臥＄）式のような一般の場合の超行列に対し

こ。ても、その各対象乱，2，…，殉の総合評価をg且ヲ…，￡乃とすると、たとえば対象且は各ゴ＝2，…，開から髄1ゴの評

価を受帆二婚身の総合評価が萄であるから、やはり§2。5の（2。7）式からら、定数倍を除いて一意に定まる。
つまり劉ま最大固有値1をもち、それに対するただ一組の固有ベクトル憲が総合評価値を与える。（7p8）式

髄且慧ガ2十。・¶＋髄且陶∬隅＝∬1

を単なる連立一次方程式とみるとその解の一意性をが成り立つ。同様に鞄は示すことは容易ではないが、固有値問題として眺める

髄2且∬且＋髄23∬3＋。0。＋髄2れ￡肌＝ご2

翌恩田（36）

定理魂 基本方程式（7。8）の解霊は、題が既約行列なと、定理且より、その一意性が保証されるのである。

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズロリサーチ

（一般に単板でない固有値に対しては固有ベクトルは（7．11）

一意には定まらない。）

この定理から、超行列gが既約でないと総合評価値が一意に定まる保証がないということがわかる。このとなりC（費用）、R（修理システム）、D（耐久性）がそれぞれ0．464，0．210，0．326の重要度をもつという結論に点からも既約性の重要性がわかる。
例1さて§6．1で述べた車の評価問題の例を解いてみなる。

よう。この超行列は§6．1の（6．2）式であって既約である
表1：掃き出し法による解から、定理4でその解の一意性が保証されている（定数倍を除いてという断り書きは今後一々断らないこと

y2

封1にする）。

これを（7．7）式のまま固有値問題として解く方法は−0．198 0．628 −0．319 0

後で述べることにして、ここでは、（7．4）式の形から直−0．268 岬0．271 0．731

接方程式を解いてみよう。（7．5）式から茸を消去すると01．000 −0．766 −0．886 0

封＝ⅣⅤ臥（∫−ⅣⅤ）甘＝00．000 0．476 −0．494 0（7・9）0．000 −0．476 0．494 0となる。ここで、∫は単位行列で、Ⅳ，Ⅴは§6．1表1，表1．000 0．000 −1．681 02に示されているが、これらから

WV＝

封3

0．466 −0．357 −0．413 00．000 1．000 −1．038．637．582．105．634．250．400．105．109．637．192．250．200

0．000

0．000

00．0000．258．309．258 ．174．500．400以上のように基本方程式を同次連立一時方程式と0．534 0．357 0．413して解くこともできるが、もっと効率のよい方法としては基本方程式を固有値問題として解く方法である。
これは定理2に裏付けられたものである。

0．198 0．372 0．319
0．268 0．271 0．269
そこで（7．9）式は定理5基本方程式（7．8）の解諾は、超行列凰が原始行列であれば、gの最大固有値1に対する主固有ベクト（∫−ⅣⅤ）y0．628 −0．319

2−0．198

10．466 −0．357 −0．413

ルとして、パワー法によって求めることができる。
＝03〃﹀−0．268 −0．271 0．731〃V〃となるがこの方程式を掃出法で解くと、表1のように固有値問題は、連立一次方程式の解法より難しく計算も時間がかかるというのが、従来の常識であった。
しかし最大固有値とそれに対する主固有ベクトルをなるからここで的は任意の値がとれるのでこれをαと求めるだけならパワー法を用いればずっと簡単になおくと解は【封1的牒3】＝α【1．681，1．038，11となる。和る。連立一次方程式の解法の手間は元数の3乗に比例するが、パワー法の1回の計算は2乗のオーダーである。繰り返し計算があるとは言え、多くの場合収束はが1となるように基準化すると【yl封2的］＝【0．452，0・279，0・269】（7・10）

極めて速い。

これは車に対する総合評価値である。つまりA（アメリカ車）、E（ヨーロッパ車）、J（日本車）がそれぞれ0．452，0．279，0．269と評価されていることになる。また同じように評価基準の重要度諾も、∬＝Vyによって求められる。これを計算するとl0．634 0．250 0．400

つ︼3 エ ￡∬

1998年5月号

0．192 0．250 0．200
0．174 0．500 0．400

しかしパワー法が収束する条件は、最大固有値が単根であって、他の固有値の絶対値がその最大固有値より小さいことである。定理2は原始行列が丁度その条件をみたすことを示している。

しかし例1のように超行列が、既約であるが、原始でない場合は、定理3が示すように、絶対値が最大固有値に等しいような固有値が存在するので、パワー法による収束の保証はない。したがって直接パワー法を© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（37）291適用することはできないが、幸いにして次のようなあmりがたい定理がある。

②定理膚超行列（確率行列ノ題が既約であれば
膠皿ニα∬＋（乱仙−α）腰（のくα＜且）（′7小皿望）1 ‰‰ 町叱．L脚。U．が㌦U㌦〆けは確率行列であって、原始行列となり、」雷の主闇斎べ

図］数：漁連結でないグラフ

タトルと腰αのそれとほ仁王改する。

を図且のようなÅN脛、で考えてみよう。対応する超行
きてこの定理を用いると∴超行列慮が既約行列であり列はハしnU以上をまとめると、Å、開削こおいて超行列慮が既約行−︑︵ ︶ハ㌧しい︑館︺る。

ハ∴︵⁝U O lい﹂た行列腰αの立願有ベクトルとして求めることができ∵∵∴ ∴㌧さえすれば、基本方殿式（7け＄）の解諾を、腰を原始化し／・J列であるとき、それに対する総合評価謹を求める方法となるが、これに対する基本方綴式の解は勘＝吼

は極めて簡単で次のようになる；

霊2乙＝憲3＝］Lとなる。これは①の②と③とに対する評鳩を（7b且2）式によって原始化1してぷ7αを求める。

価び＞9と0リコしが、∬＆＝のであるため、全く無視された結ぶαの主固有べタトル憲をパワーu法で求めれば、果となって明らかに不合理である
一九般に有向グラフが強連結でない場合、それを強連それが総合評価ベクトルとなる。」（′7鼠3）

結成分に分けて考えるとき、impu七のない成分と0㍑もⅣ・
この方法を用いて、§6の例且を解いてみよう。ぶはp㍊ものない成分が出てくる。図1では、2つの強連結成（6。2）式で与えられたものだから、これをα＝＝且／2とし鮮血がなく、監芸2にはouもpuもがない。そこでこのような」，＿ 0 0 巾634。25の b4￠0場合のou．已ノpほものない成分から温叩u七のない成分への、

0 且 り ．乱92 p25の。2のの仮想的評価を考え、全体を強連結なものに変換するものとする。

㍍ C 1 ユ乱7魂。50の。40￠

軌／2＝−● ヽ − 、‥てぃ原始化すると・鳳開∵．5S2 詫（）5 且 ￠ む−

G2から隠1への評価行列としては、パラメタ∂（￠く∂く1）を用いて、［∂フ∂】とし、全体として確率行列に。乱の5 一闇媚∴思錯 仁）＋ ヨ‖ ＋Cなるように隠2内の評価行列をど（＝且−mお）倍しておく。

・− ・・

こうして変換された超行列盃は（お−一卜ど＝乱）（7d乱′7）︹Uど1ハめじハU

nU

ハU＋、＋−−● ●●ハ∴しノ〜ぶ‥

ハAU︑∴′もパワ｝法をほどこすと、わずか数ステップで収束して﹁名．Jとなる。これに（初期値を（且，且ラ且，且，19且）〉く且／6として）ビを得る。
これは全体が基準化されているが、例鼠で先に計、、・、となる。ごれに対する基本方程式の解は・・・要したものである。したがって（7。且5）を2倍したものが（7「且旦）式、（−7。1呵式の髄となり、先の計算結果と一致

罰ブコ】＝1L−一己2ラT2＝（）、ン9一十仇猛，鞘＝の。且＋の瀧（7。瑚する。となる（比だけが問題だから和が且となる基準化は行−、∴−−： ニ・っていない）。パラメタ∂（あるい古まだ）をどのようにして§6℡1の例2（図2）のように遊行列が既約でない（対応するグラフが強連結でない）場合には、基本方程式（7，8）の解が必ずL．．も妥当なヰ）のとならない。この例

讃翌夏（38）

選ぶかについては問題に応じて柔軟に考えていくのが良いと思う。

§6．，丑の例2の超行列を上と同じように変換すると、
オペレ、−一ションズ〔〉リサーチ© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

こでgの変換行列彦を

開′1 0 （1／2）∂♂
5＝＝Ⅳ21 Ⅳ20Ⅳ32（∂＋ど＝1）（7・23）

0EⅣ3として、これに対する基本方程式の解を求めればよい。ここでプは要素がすべて1である行列で1／2という係数はGlの要素の数2の逆数である。

園］Sa如y氏の提案したANPの解法は、ここで述べたものとは少し異なっている。ここで氏の方法を紹介しておこう。
図2：一般のグラフ

超行列ぶが原始行列である場合

この場合且imβγが収束し、．その極限行列の各列r→（X）

O叶⁚・⁚u録︒甜

Oはすべて同一のベクトル諾となる。つまり（∂＋ど＝1）

1imぶγ＝匝牒，＝・，諾］（7・19）

γ■→00となることを示し、この諾が総合評価となるというのがSaa七y法である。このガは我々の基本方程となる。eは要素がすべて1である1×3行列。「投」の式（7。8）の解となる。

総合評価を和、［品、広、サ］の総合評価ベクトルを諾＝［ェ1，∬2，￡3ト（M，8，W）のそれを暫＝〔封1，封2，封3Jとす（ii）超行列βが既約行列である（が原始でない）場合
この場合ぶγはγによって周期的に変動して収束しると、基本方程式はない。しかしgの周期をc（§6）とすると、ガCはその累乗が収束する。つまり1：im（題C）γを解法の根拠∂（￡1＋諾2＋∬3＋仇＋封2＋y3）＝ご0γ−→（⊃く）とする。

￡0髄＋Ey暫＝諾
ど開′諾＝即（7■20）

簡単の為2つのクラスターからなっていて互いに他を評価する場合、つまりぶが（7．3）式の形をしてとなり、その解は次のようになる。

いる場合を考えよう。この場合

諾＝∬0（す−ど2yⅣ）￣1鶴野＝ど諾0関′（才一E2y開′）■1髄

ぶ2＝㌍討（7・21）となり

図2は叫般的なパターンであるが、この場合、強連結成分Gl，G2，G3があるが、Glにはinpuもがなく、G3

1im（■打開′）γ1im（g2）γ＝r→00

γ→00

00勒︒勒侮g＝勒取︒にはouもputがない。この場合の超行列は01im（Wy）γγ→∞

において、右辺のそれぞれの成分が収束し（7．22）

1im（y開′）γ＝［憲，α，…，g］
ケ■→（：×〕1im（開′y）γ＝！野，野，…，封］
γ−→（＞〇となる。ここでⅣ1（Vy2，Ⅳ3）はGl（G2，G3）内の評価行列で、Ⅳ21（甘y32）はGlのG2（G2のG3）に対する評価行列である。
この場合のGl（G2，G3）の総合評価ベクトルを㌶1（諾2，∬3）とすると、基本方程式（7．8）の解は、諾1＝諾2＝0で∬3のみが非ゼロの解をもつことになる。そ1998年5月号となって、ベクトルガ，留がそれぞれ第一クラスタ｝、第ニクラスターの総合評価となるというのが、Saaty氏の方法である。じつはこれらが、我々の（7．5）式（あるいは（7・6）式）の解∬，討と一致する
ことも（i）の場合と同様である。

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（39）293