反饋問題中的網(wǎng)絡(luò)分析法anp

1saaty在網(wǎng)絡(luò)分析法中的應(yīng)用近年來，以往的層次分析法（即ahp）已在系統(tǒng)決策分析中得到廣泛應(yīng)用。AHP方法的核心是將系統(tǒng)劃分層次且只考慮上層元素對(duì)下層元素的支配作用。同一層次中的元素被認(rèn)為是彼此獨(dú)立的。這種遞階層次結(jié)構(gòu)雖然給處理系統(tǒng)問題帶來了方便,同時(shí)也限制了它在復(fù)雜決策問題中的應(yīng)用。在許多實(shí)際問題中,各層次內(nèi)部元素往往是依存的,低層元素對(duì)高層元素亦有支配作用,即存在反饋。此時(shí)系統(tǒng)的結(jié)構(gòu)更類似于網(wǎng)絡(luò)結(jié)構(gòu)。網(wǎng)絡(luò)分析法(ANP)正是適應(yīng)這種需要,由AHP延伸發(fā)展得到的系統(tǒng)決策方法。早在20世紀(jì)80年代中,Saaty就提出了反饋AHP。它就是ANP前身。1996年Saaty在ISAHP-Ⅳ上較為系統(tǒng)地提出了ANP的理論與方法。本文將對(duì)此進(jìn)行介紹和討論。并對(duì)Saaty的某些算法進(jìn)行改進(jìn)。特別對(duì)循環(huán)系統(tǒng),作者提出用帶有原點(diǎn)位移的冪法直接計(jì)算超矩陣的極限相對(duì)排序向量,改變了過去計(jì)算平均極限排序矩陣的繁瑣算法。1控制層的權(quán)重ANP首先將系統(tǒng)元素劃分為兩大部分,第一部分稱為控制因素層,包括問題目標(biāo)及決策準(zhǔn)則。所有的決策準(zhǔn)則均被認(rèn)為是彼此獨(dú)立的,且只受目標(biāo)元素支配?？刂埔蛩刂锌梢詻]有決策準(zhǔn)則,但至少有一個(gè)目標(biāo)。控制層中每個(gè)準(zhǔn)則的權(quán)重均可用傳統(tǒng)AHP方法獲得。第二部分為網(wǎng)絡(luò)層,它是由所有受控制層支配的元素組組成的,其內(nèi)部是互相影響的網(wǎng)絡(luò)結(jié)構(gòu),圖1就是一個(gè)典型的ANP結(jié)構(gòu)。2兩元素比較的方式AHP的一個(gè)重要步驟就是在一個(gè)準(zhǔn)則下,受支配元素進(jìn)行兩兩比較,由此獲得判斷矩陣。但在ANP中被比較元素之間可能不是獨(dú)立的,而是相互依存的,因而這種比較將以兩種方式進(jìn)行:1)直接優(yōu)勢(shì)度給定一個(gè)準(zhǔn)則,兩元素對(duì)于該準(zhǔn)則的重要程度進(jìn)行比較;2)間接優(yōu)勢(shì)度給出一個(gè)準(zhǔn)則,兩個(gè)元素在準(zhǔn)則下對(duì)第三個(gè)元素(稱為次準(zhǔn)則)的影響程度進(jìn)行比較。例如要比較甲、乙兩成員對(duì)商品營(yíng)銷能力的優(yōu)勢(shì)度,方法之一,可通過他們對(duì)董事長(zhǎng)所取的營(yíng)銷策略的影響力比較而間接獲得。前一種比較適用于元素間互相獨(dú)立的情形,第二種比較適用于元素間互相依存的情形。3超矩陣的生成和排序設(shè)ANP的控制層中有元素p1,\:,pn,控制層下,網(wǎng)絡(luò)層有元素組C1,\:,CN,其中Ci中有元素ei1,\:,eini,i=1,\:,N.以控制層元素Ps(s=1,\:,m)為準(zhǔn)則,以Cj中元素ejl(l=1,\:,nj)為次準(zhǔn)則,元素組Ci中元素按其對(duì)ejl的影響力大小進(jìn)行間接優(yōu)勢(shì)度比較,即構(gòu)造判斷矩陣:Ps下并由特征根法得排序向量w(jl)i1(jl)i1,\:,w(jl)ini(jl)ini)′。記Wij為Wij=[w(j1)i1w(j2)i1\:w(jnj)i1w(j1)i2w(j2)i2\:w(jnj)i2\~\:w(j1)iniw(j2)ini\:w(jnj)ini](1)Wij=????????w(j1)i1w(j1)i2w(j1)iniw(j2)i1w(j2)i2w(j2)ini\:\:\~\:\:w(jnj)i1w(jnj)i2w(jnj)ini????????(1)這里Wij的列向量就是Ci中元素ei1,\:,eini對(duì)Cj中元素eji,\:,ejnj的影響程度排序向量。若Cj中元素不受Ci中元素影響,則Wij=0。這樣最終可獲得Ps下,超矩陣W1\:n11\:n2\:1-nΝW=1\:n11\:n2\:1\:nΝ[W11W12\:W1ΝW21W22\:W2Ν\~\:WΝ1WΝ2\:WΝΝ](2)這樣的超矩陣共有m個(gè),它們都是非負(fù)矩陣,超矩陣的子塊Wij是列歸一化的,但W卻不是列歸一化的。為此以PS為準(zhǔn)則,對(duì)PS下各組元素對(duì)準(zhǔn)則Cj(j=1,\:,N)的重要性進(jìn)行比較。PS下與Cj無關(guān)的元素組對(duì)應(yīng)的排序向量分量為零,由此得加權(quán)矩陣A=[a11\:a1Ν\~\:aΝ1\:aΝΝ]對(duì)超矩陣W的元素加權(quán),得ˉW=(ˉWij),其中ˉWij=aijWiji=1,\:,Ν,j=1,\:,Ν(3)ˉW就為加權(quán)超矩陣,其列和為1,稱為列隨機(jī)矩陣。為簡(jiǎn)單起見以下的超矩陣都是加權(quán)超矩陣,并仍用符號(hào)W表示。4步優(yōu)勢(shì)度設(shè)(加權(quán))超矩陣W的元素為wij,則wij的大小反映了元素i對(duì)元素j的一步優(yōu)勢(shì)度。i對(duì)j的優(yōu)勢(shì)度還可用Ν∑k=1wikwkj得到,稱為二步優(yōu)勢(shì)度,它就是W2的元素。W2仍是列歸一化的。當(dāng)W∞=limt→∞Wt存在時(shí),W∞的第j列就是PS下網(wǎng)絡(luò)層中各元素對(duì)于元素j的極限相對(duì)排序向量。5特征向量w的存定理1設(shè)A為n階非負(fù)矩陣,λmax為其模最大特征值,則有minin∑j=1aij≤λmax≤maxin∑j=1aij證明見文獻(xiàn)。推論列隨機(jī)矩陣的模最大特征值為1。定理2設(shè)非負(fù)列隨機(jī)矩陣A的最大特征值1是單根,其它特征值的模均小于1,則A∞存在,且A∞的各列都相同,都是A的屬于1的歸一化特征向量。證明設(shè)A的特征值為λ1,λ2,\:,λn滿足1＞|λ2|≥\:≥|λn|屬于1的歸一化特征向量為v1,則必存在非奇異矩陣T=(v1,v2,\:,vn)使Τ-1AΤ=J=(1J2?Jr)其中J為A的若當(dāng)標(biāo)準(zhǔn)形,J2,\:,Jr為對(duì)角元的模小于1的若當(dāng)塊。故limk→∞Jki=0,i=2,\:,r,于是A∞=limk→∞Ak=limk→∞ΤJkΤ-1=Τ(10?0)Τ-1故A∞存在,記A=(A1,A2,\:,An)?A∞=(A∞1,A∞2,\:,A∞n)對(duì)任意X∈Pm,設(shè)T-1X=(x11,\:,xn1)′,那么A∞X=ΤJ∞Τ-1X=(v1,?,vn)(10?0)(x11\~\:xn1)=x11v1特別取X=(0,\:,0,1,0,\:,0)′i=1,\:,m時(shí)A∞X=A∞i=x11v1因?yàn)锳∞i仍是列歸一化的,故x11=1,即有A∞i=vi(i=1,\:,n),即A∞的每一列均是特征值1對(duì)應(yīng)的特征向量。由此可知,當(dāng)超矩陣W滿足定理2條件時(shí),只要用冪法求出W的特征值1對(duì)應(yīng)的特征向量v1,W∞就可求得,W∞=(v1,v1,\:,v1),即其每一列均為極限相對(duì)排序向量。定理3設(shè)W是非負(fù)不可約列隨機(jī)矩陣,則W∞=limk→∞Wk存在的充分必要條件是W是素陣。由素陣的性質(zhì)容易證明定理結(jié)論。6亞分離主結(jié)構(gòu)的各種重要組件及其相對(duì)序列向量6.1+a+nwn-2,2,2.2回射線第1列此時(shí)可把目標(biāo)層C1看作既屬于控制層又屬于網(wǎng)絡(luò)層元素(圖2)C1下超矩陣為W=[0W210W32?WΝΝ-1Τ](4)其子塊Wii-1(i=2,\:,N)都是素陣,但W非素且可約它的特征值有0和1,1的重?cái)?shù)為被擇元個(gè)數(shù)n,并且WΝ-1=C1C2\:CΝ-1CΝ[00?00\~\:00?00WΝ,Ν-1WΝ-1,Ν-2\:W21WΝΝ-1\:W32?WΝΝ-1Ι](5)且WN=WN-1,即WWN-1=WN-1,故WN-1的每一列均是1對(duì)應(yīng)的特征向量,其中第一列元素WNN-1WNN-1\:W21就是被擇元素對(duì)目標(biāo)層元素C1的排序向量。6.2系統(tǒng)元素的排序其結(jié)構(gòu)如圖3所示,控制層C1仍作為網(wǎng)絡(luò)層的一部分。其超矩陣為W=[W11W21W22W32???WΝΝ-1WΝΝ]W是非素可約陣。定理4在內(nèi)部依存的遞階層次結(jié)構(gòu)超矩陣中,若WNN是常態(tài)的,即除1外沒有其它模為1的特征值,那么W∞ΝΝ=limk→∞WkΝΝ存在,且有W∞=C1C2\:CN[00\:0\~\:00\:0D1D2\:DΝ]這里DΝ=W∞ΝΝDΝ-1=DΝWΝΝ-1(Ι-WΝ-1Ν-1)-1\~\:Di=Di+1Wi+1,i(Ι-Wii)-1\~\:D1=D2W21(Ι-W11)-1(7)D1就是系統(tǒng)元素對(duì)C1的排序向量。定理證明見文獻(xiàn)。特別當(dāng)W11=\:=WN-1N-1=0,而WNN=I時(shí),所得結(jié)果即為(1)的結(jié)果。6.3歸一化特征值1系統(tǒng)結(jié)構(gòu)如圖4所示,其超矩陣為W=[0WΝW10W2???WΝ-10](8)W是不可約非素矩陣,最大特征值λ=1是單根,但除1外還有其它模為1的特征根,并且有性質(zhì)WΝ=[V1V2?VΝ]WkΝ=[Vk1Vk2?VkΝ]其中V1=WΝWΝ-1\:W1V2=W1WΝ\:W2\~\:VΝ=WΝ-1WΝ-2\:W1WΝW,W2,\:,WN互異,W稱為循環(huán)矩陣,其循環(huán)周期為N。V1,\:,VN均為素陣,故V∞i(i=1,\:,N)存在,且(WΝ)∞=[V∞1V∞2?V∞Ν]設(shè)k=k1N+r,1≤r≤N,那么limk→∞Wk=limk′→∞Wk′Ν+r=(WΝ)∞Wr極限值隨r(r=1,2,\:,N-1)而改變,故W∞不存在。為此取ˉW∞=1ΝΝ-1∑r=1Wr(WΝ)∞(9)作為平均極限矩陣。由(Ι+W+\:+WΝ-1)(Ι-W)=Ι-WΝI-WN為對(duì)角元均非零的準(zhǔn)對(duì)角陣,故I-WN可逆I-W也可逆,有Ι+W+\:+WΝ-1=(Ι-WΝ)(Ι-W)-1即ˉW∞=1Ν(Ι-WΝ)(Ι-W)-1(WΝ)∞(10)容易看出ˉW∞仍為非負(fù)列隨機(jī)矩陣,且仍為不可約素陣。故其最大特征值1為單根,其它特征值模均小于1,ˉW∞的列向量就是ˉW∞的歸一化特征向量,也就是元素的平均極限相對(duì)排序向量。Saaty建議用式(9)(10)求出ˉW∞,整個(gè)計(jì)算過程繁復(fù)。下面的定理與算法,可以簡(jiǎn)化計(jì)算。定理5(加權(quán))超矩陣(3)與平均極限矩陣ˉW∞屬于最大特征值1的特征向量相同。證明設(shè)W的屬于λ=1的特征向量為X,則ˉW∞=1C(Ι+W+\:+WΝ-1)(WΝ)∞X=X故X就是ˉW∞的屬于1的特征向量。這樣我們只要求出W的屬于1的歸一化特征向量ˉW∞就可以得到,但W除單根1外還有其它模為1的特征根,不能用常規(guī)幕法求其相應(yīng)特征向量,可用帶有原點(diǎn)位移的幕法求出X。其算法如下:設(shè)W的特征值為λ1=|λ2|=\:|λr|>|λr+1|≥\:≥|λn|,λ1=1,λ1對(duì)應(yīng)的歸一化特征向量為X1。|λ2|=\:=|λr|=1,但λ2,\:,λr均非1,故只能為-1或復(fù)數(shù)a+bi,其中a2+b2=1,且|a|<1,|b|<1,構(gòu)造矩陣A=I+W,其特征值為μ1,\:,μn,易知μi=λi+1,i=1,\:,n,且顯然地除μ1=2外,其余|μi|<2,i=2,\:,n.故μ1=2是A的模最大特征值,這是單根,且不存在其它模與它相同的特征值。μ1對(duì)應(yīng)的歸一化特征向量就是X1。故只要用冪法求出A的μ1=2的特征向量X1,就可得到ˉW∞=(X1,\:,X1)(11)6.4有正整數(shù)t、at的情形系統(tǒng)結(jié)構(gòu)如圖5所示。其超矩陣為W=[W11W12\:W1ΝW21W22\:W2Ν\~\:WΝ1WΝ2\:WΝΝ](12)此超矩陣是非負(fù)不可約的。對(duì)此矩陣,我們有下面結(jié)論:引理1設(shè)A為n階非負(fù)不可約矩陣,則對(duì)任意σ>0,σI+A為素陣。由此可知,對(duì)內(nèi)部依存系統(tǒng)的超矩陣,總可用冪法或帶有位移的幕法求出W∞。引理2設(shè)A為素陣,則對(duì)每個(gè)正整數(shù)t,At也是素陣。引理3設(shè)A為n階非負(fù)不可約矩陣,若對(duì)所有1≤i≤n,有aii>0,則A為素陣。引理4設(shè)A為n階非負(fù)不可約矩陣,則對(duì)每個(gè)1≤i,j≤n,存在正整數(shù)t=t(i,j)使得At=(a(t)ik)的元素a(t)ij>0。以上引理證明可參閱文獻(xiàn)。定理6設(shè)A為n階非負(fù)不可約矩陣,若A至少有一個(gè)對(duì)角元aij>0(1≤i≤n),則A必為素陣。證明不失一般性設(shè)a11>0,則由引理4知,對(duì)A的第一行元素存在正整數(shù)t2,\:,tn使a(t2)12>0,\:,a(tn)1n>0,于是a(t2+1)12=a11a(t2)12+\:+a1na(t2)n2≥a11a(t2)12≥0并對(duì)任意t>t2有a(t)12>0,同理有t>t3時(shí)