數(shù)學(xué)建模課件

層次分析方法建模三類不同關(guān)係及其相應(yīng)處理方法①

嚴(yán)格確定關(guān)係與機(jī)理分析方法.例:商高定理a2+b2=c2;

歐姆定律v=ri;

牛頓冷卻定律Q=k(T-T’)/b.特點(diǎn):涉及各門學(xué)科的各種成功範(fàn)例;但不是自然界最廣泛的關(guān)係.cabTT’Qb②

隨機(jī)關(guān)係與概率統(tǒng)計(jì)方法.例:擲骰(tou)子一次不一定出現(xiàn)紅四;但擲六次可期望出現(xiàn)一次紅四.在一定條件下可以說,擲一次出現(xiàn)紅四的概率是1/6.男嬰自然出生的概率可以嚴(yán)格證明是1/2.測量誤差服從正態(tài)分佈規(guī)律等等.特點(diǎn):既確定又不完全確定.③不確定關(guān)係與系統(tǒng)分析方法.例:疫情(例如非典,禽流感等)預(yù)測,股票預(yù)測等;三峽大壩壩高與壩址等的決策;城市建設(shè)規(guī)劃;商品進(jìn)貨計(jì)畫等.特點(diǎn):答案的不確定性與多樣性,即一般地存在若干各有優(yōu)缺點(diǎn)的答案.需要用系統(tǒng)分析方法,從不同的角度對它們進(jìn)行優(yōu)缺點(diǎn)分析,可行性分析,短期,長期效益分析等,以權(quán)衡利弊,並結(jié)合實(shí)際情況作出最滿意(注意這個(gè)提法)的選擇.層次分析方法是為處理這類決策問題的一個(gè)行之有效的新方法.決策問題的特性①

廣泛性:

生活中處處有決策問題.衣:—

或買或做?款式顏色,價(jià)格,品質(zhì)(面料,做工等)如何?等等.食:—(請朋友吃飯)或家宴或上飯館?如何點(diǎn)(備)菜?中餐,西餐或火鍋?包席,點(diǎn)菜或自助餐?等等.住:—

買房或租房?價(jià)格?遠(yuǎn)或近?大或小?廳室廚衛(wèi)配置?購物,上班,上學(xué)是否方便?鄰居與環(huán)境如何?等等.行:—(旅遊)旅行社或自主遊?國內(nèi)或國外?遠(yuǎn)或近?往何方向?看什麼(山,水,洞,古跡,風(fēng)情)?等等.工作:—升學(xué)或就業(yè)的決策,個(gè)人今後發(fā)展的規(guī)劃等等.機(jī)構(gòu)工作:—研究課題的選擇;為疑難病癥確定治療方案;招標(biāo)招工的最後確定;購買設(shè)備,上馬新產(chǎn)品的最後決定等等(涉及因素,背景與知識(shí)的廣泛性).②

答案的不確定性與多樣性,即不存在唯一的毫無爭議的答案,只存在相對滿意的答案(滿意解).③

答案存在較強(qiáng)的主觀性,不同喜好的人會(huì)作出不同的決定(穿衣戴帽各有所好)特性①說明決策問題的重要性;特性②和③說明決策問題的複雜性.具體來講,決策問題常常難以量化,結(jié)論易犯主觀性毛病,不經(jīng)充分討論研究和適當(dāng)量化,就不能作出有足夠說服力的結(jié)論.因決策問題而產(chǎn)生層次分析方法1970年代後期,針對決策問題的上述特性,力求以較客觀的定量化方式來分析和解決決策問題,美國學(xué)者T.L.Saaty提出層次分析方法(簡稱AHP,英文全名是:AnalyticHierarchyProcess)以後的發(fā)展證明,此法是解決決策問題的一個(gè)行之有效的好方法,一經(jīng)提出,立即在世界範(fàn)圍迅速傳播,產(chǎn)生巨大影響.1980年該法也傳入我國.例旅遊選點(diǎn)問題某小家庭打算在五一黃金周出門旅遊,他們擬從萬佛湖,天堂寨和黃山三景點(diǎn)中挑選一個(gè)作為旅遊目的地,如何決策?zy3y4y1x1,x2,x3y5y2萬佛湖天堂寨黃山景色費(fèi)用食宿交通其他目標(biāo)指標(biāo)對象y1v1v2自然人文§3.2層次分析基本步驟步驟①建立層次模型目標(biāo)層:就是最後決策.對象層:列出可供選擇的對象.指標(biāo)層(還可細(xì)分):列出影響決策的主要因素.主要指標(biāo)的選取是關(guān)鍵,應(yīng)該仔細(xì)列出一切影響決策的因素,並通過認(rèn)真的分析和比較,從中(按計(jì)算能力)選出若干最關(guān)鍵的因素(本旅遊問題選了5個(gè)).步驟②確定指標(biāo)層對目標(biāo)的權(quán):Wz(y1,…,y5)=(w1,…,w5)=(0.48,0.27,0.05,0.10,0.10).及對象層對每個(gè)指標(biāo)的權(quán):Wyi(x1,x2,x3),i=1,…,5.步驟③確定對象層對目標(biāo)的組合權(quán)(最後答案):Wz(x1,x2,x3)=Wz(y1,…,y5)A,

其中的A

是5行3列的矩陣,其第i行是Wyi.uv1

設(shè)要考慮下層因素

v1,…,vn對其直接上層因素u

的重要性貢獻(xiàn).

例如:u為景色;v1,v2

分別為人文景色,自然景色.某人認(rèn)為,人文景色重要性比之自然景色是四六開,即

4:6.自然想到用一個(gè)行向量W=(0.4,

0.6)來表示這個(gè)觀點(diǎn).v2用向量表示下層因素的重要性權(quán)向量的概念

元素全為非負(fù)且其和等於1的行向量

W=(w1,…,wn)稱為權(quán)向量,滿足w1,…,wn

0,w1+…+wn=1.

任何正向量

W=(w1,…,wn)乘以正數(shù)

1/(w1+…+wn)後所得向量都是一個(gè)權(quán)向量,這個(gè)權(quán)向量稱為正向量

W

的歸一化.上述旅遊問題的組合權(quán)向量計(jì)算結(jié)果:Wz(x1,x2,x3)=(0.30,0.22,0.47)結(jié)論:三景點(diǎn)對旅遊選址重要性的大小順序是:黃山,萬佛湖,天堂寨.A=Wz(x1,x2,x3)=Wz(y1,…,y5)A=(0.30,0.22,0.47).組合權(quán)向量計(jì)算公式:

Wz(y1,…,y5)=(0.48,0.27,0.05,0.10,0.10);

Wz(x1,x2,x3)=Wz(y1,…,y5)A=(0.30,0.22,0.47).例如第一個(gè)對象(萬佛湖)對選點(diǎn)重要性貢獻(xiàn)是0.480.08+0.270.63+0.050.43+0.100.63+0.100.17=0.30.(加權(quán)平均)A=§3.3層次分析的理論基礎(chǔ)uv1vnA.基本工作模式是計(jì)算下層因素

v1,…,vn對其直接上層因素

u

的權(quán):Wu(v1,…,vn).這裏,

v1,…,vn可以是對象層(因素層)或其子層;u

可以是目標(biāo)或因素層的某一個(gè)因素.B.AHP用成對比較法及9級(jí)記分法產(chǎn)生比較矩陣作為分析計(jì)算的基礎(chǔ)

仍以求旅遊問題的指標(biāo)層對目標(biāo)的權(quán)Wz(y1,…,y5)=(w1,…,w5)為例.即使你心目中已有了關(guān)於五個(gè)指標(biāo)對目標(biāo)重要性的一個(gè)估計(jì),但要你一下子寫出你的權(quán)(w1,…,w5)的具體值,哪怕是近似值你也會(huì)感到很困難,因?yàn)樯婕?個(gè)因素的全面綜合比較.

層次分析方法(AHP)所建議的解決辦法是一種把困難化整為零的所謂成對比較法

,即每次只比較兩個(gè)因素重要性的比值:wi/wj,i,j=1,…,n

另外,AHP還建議估計(jì)wi/wj時(shí),採用9級(jí)記分法,即:總是取其中小的一個(gè)為1,大的一個(gè)只在前9個(gè)正整數(shù)中取值.其尺度及含義如下(8,6,4,2取相應(yīng)的中間含義):尺度97531含義絕對強(qiáng)很強(qiáng)強(qiáng)稍強(qiáng)相同權(quán)Wz(y1,…,y5)=(w1,…,w5)的一個(gè)比較矩陣該比較矩陣A=(aij)

(wi/wj)的每個(gè)對角元均為1:wi/wi

1;先將y1與y2,y3,y4,y5成對比較得A的第1行;一般地,將yi與其它yj比較得A的第i行★.下麵是某人定出的一個(gè)比較矩陣:127551/214331/71/411/21/31/51/32111/51/3311A=★構(gòu)造比較矩陣其實(shí)只需要估定對角線(不包括對角線)以上的元素aij,1i<jn即可,因?yàn)?每個(gè)aii=1;aji=1/aij,1i<jn.具體操作過程是:先直接寫出每個(gè)aii=1;接著定a12,a13,…,a1n;然後直接寫出a21,a31,…,an1;下一步定a23,…,a2n;然後直接寫出a32,…,an2;再下一步定a34,…,a3n;然後直接寫出a43,…,an3;依此類推,直到定完為止.C.比較矩陣的一致性

按定義,比較矩陣恒為正矩陣並滿足

i,j,aij{1,…,9,1/2,1/3,…,1/9},aii=1,aijaji=1.

理想的比較矩陣應(yīng)滿足一致性條件:

i,j,k,aik=aijajk.證:所謂理想的比較矩陣應(yīng)該嚴(yán)格滿足:對任意i,j都有:aij=wi/wj,於是對任意i,j,k都有aik=(wi/wj)(wj/wk)=aijajk.

比較矩陣體現(xiàn)各因素成對比較的記錄,可操作性好,這是其本質(zhì)方面.

但如果建立比較矩陣時(shí)工作不夠投入,缺乏全局平衡,弄不好就會(huì)產(chǎn)生嚴(yán)重不一致的比較矩陣.我們用下麵兩個(gè)例子加以說明.提醒注意

比較矩陣一致性好壞的舉例例如,求權(quán)Wy1(x1,x2,x3)時(shí),兩個(gè)人分別作出下列兩個(gè)比較矩陣:11/31/8311/3831122?16?1/61A=.,A

=對這兩個(gè)比較矩陣,a13=a12a23

都不成立.對A,因1/8=a13與

a12a23=1/9

較為接近,故比較矩陣

A

滿足一致性條件較好.但對A,2=a13與

a12a23=12

則相差太遠(yuǎn),故A滿足一致性條件較差,應(yīng)該推倒重來.

稍後,我們要介紹AHP為此專門制定的可靠性檢驗(yàn)方法,利用這個(gè)檢驗(yàn)方法,可以有效地發(fā)現(xiàn)並摒棄那些因粗製濫造而不合要求的比較矩陣.一致矩陣的概念定義:比較矩陣A=(aij)稱為一致矩陣,如果它滿足一致性條件:i,j,k,aik=aijajk性質(zhì):若比較矩陣A是一致矩陣,則存在權(quán)向量W=(w1,…,wn)嚴(yán)格滿足:i,j,aij=wi/wj.於是所以,當(dāng)比較矩陣A是一致矩陣時(shí),A的任一列的歸一化向量正好等於對應(yīng)的權(quán)向量.=[wi/wj].w1

┇wn1/w1

1/wnA=D.從比較矩陣近似計(jì)算權(quán)向量假設(shè)已有一個(gè)通過可靠性檢驗(yàn)的比較矩陣A,則可由它近似地決定權(quán)向量W=(w1,…,wn).

AHP

給出下列近似公式:Wu(v1,…,vn)=(1/n)(1+…+n),

其中,

j為A的第j列的歸一化,Wu

為1,…,n的平均值.a1j

┇anj

j=(1/(a1j++anj))計(jì)算權(quán)向量

Wy1(x1,x2,x3)已知11/31/8311/3831A=各列歸一化1/120.33/4.330.13/1.463/121/4.330.33/1.468/123/4.331/1.46各行求和0.250.712.05除以n=30.080.240.68Wy1(x1,x2,x3).思考題3-1

對旅遊選點(diǎn)問題假設(shè)已構(gòu)造了下列能通過可靠性檢驗(yàn)的有關(guān)比較矩陣:1341/3111/4111131131/31/31111/4111/4441Ay2(x)=

Ay4(x)=Ay3(x)=Ay5(x)=試求:對應(yīng)權(quán)向量的近似值.思考題3-2

求n階全1方陣:J=(aij),i,j,aij=1的譜(特徵值的集合),並求出對應(yīng)於最大特徵值r(J)=n

的一個(gè)歸一化正特徵向量.由思考題3-2的答案可見

矩陣J

的譜是:(J)={n,0,…,0},最大特徵值是

r(J)=n.

正向量e=(1,…,1)T是J

的對應(yīng)最大特徵值

n

的一個(gè)特徵向量:Je=n(1,…,1)T=

ne.於是,J

的對應(yīng)最大特徵值

n

的一個(gè)歸一化正特徵向量是:(1/n)e=(1/n,…,1/n)T.正方陣的最大特徵值及其特徵向量元素全為正數(shù)的實(shí)矩陣稱為正矩陣.正矩陣在應(yīng)用中非常重要,其原因可以說是基於下麵由德國數(shù)學(xué)家

Perron

在1908年得到的一個(gè)定理(證明較難,從略).定理1

任何正方陣

A

都有唯一最大特徵值r(A),其值大於

A

的任何特徵值的模數(shù),並有對應(yīng)於它的正特徵向量.E.比較矩陣最大特徵值及其特徵向量比較矩陣A屬於所謂正互反矩陣(i,j,aij0,aijaji=1)

的範(fàn)疇,它滿足定理1的條件.下麵的定理2對層次分析的理論推導(dǎo)有關(guān)鍵意義,它可由定理1推出.定理2

若關(guān)於權(quán)向量

W=(w1,…,wn)得到的比較矩陣

A

是一致矩陣,則

A

的最大特徵值為

r(A)=n,並且權(quán)向量

W

就是A的對應(yīng)於r(A)的唯一歸一化正特徵向量.證:由定理1,只需證正方陣

A

的唯一最大特徵值為

r(A)=n,並且權(quán)向量

W是A

的對應(yīng)於

r(A)的特徵向量即可(因r(A)為單特徵值).

w1

┇wn1/w1

1/wnw1?wnD=A～D-1D=J(全1矩陣)∴r(A)=r(J)=n;AWT=n[w1,…,w1]T=nWT.w1-1?wn-1D-1=求近似一致矩陣的最大特徵值

如果

A

是近似於一致矩陣的比較矩陣,則可用前面介紹的近似方法求出

A

所對應(yīng)的權(quán)向量

W=(w1,…,wn)T,從而根據(jù)定理2,AWTr(A)WT.令A(yù)WT=(b1,…,bn)T,則bir(A)wi.i=1,…,n.因此,AHP

給出下列求r(A)的近似公式:r(A)(b1/w1+…+bn/wn)/n.求近似一致矩陣最大特徵值的例例1:關(guān)於旅遊選點(diǎn)問題,我們已對權(quán)

Wy1(x)構(gòu)造過比較矩陣A並求得Wy1(x)(0.082,0.236,0.682).現(xiàn)計(jì)算矩陣A的最大特徵值

r(A)如下:11/31/8311/3831AW=0.0820.2360.6820.2460.7092.046=r(A)=(0.246/0.082+0.709/0.236+2.046/0.682)/3=3.001注:也不難得到r(A)的精確值為3.0015416.127551/214331/71/411/21/31/51/32111/51/3311A=W=0.4740.2120.0540.0990.110AW=2.421.340.270.500.55r(A)=例2:

關(guān)於旅遊選點(diǎn)問題,前面我們也對權(quán)Wz(y)構(gòu)造過比較矩陣

A

並求得

W=Wz(y).現(xiàn)計(jì)算A的最大特徵值如下:思考題3-3

對旅遊選點(diǎn)問題假設(shè)已構(gòu)造了下列能通過可靠性檢驗(yàn)的有關(guān)比較矩陣:1341/3111/4111131131/31/31111/4111/4441Ay2(x)=

Ay4(x)=Ay3(x)=Ay5(x)=試求:這些比較矩陣的最大特徵值的近似值(提示:利用思考題3-1的結(jié)果).F.比較矩陣的一致性檢驗(yàn)檢驗(yàn)必要性:通過檢驗(yàn)可以做到合格者放心使用,不合格者推倒重來.檢驗(yàn)前提:已知對應(yīng)權(quán)

Wu(v1,…,vn)的比較矩陣A並已求得其最大特徵值的近似值r.檢驗(yàn)步驟:⑴計(jì)算一致性指標(biāo)CI=|r-n|/(n-1)⑵計(jì)算可靠性指標(biāo)CR=CI/RI⑶檢驗(yàn)規(guī)則:比較矩陣為可靠,當(dāng)且僅當(dāng)CR

0.1(相當(dāng)於小10倍以上,可根據(jù)重要性調(diào)整).檢驗(yàn)指標(biāo)的解釋?

CI(n)=|r-n|/(n-1)是比較矩陣

A

的最大特徵值r對同階一致矩陣最大特徵值(=n)的相對偏差,其值越小越好.?RI(n)稱為隨機(jī)一致性指標(biāo),是不假思索隨機(jī)地構(gòu)造出來的比較矩陣的一致性指標(biāo)平均值,AHP對不同n用500-1000個(gè)隨機(jī)樣本算出平均值列成下表★:n234567891011RI00.580.901.121.241.321.411.451.491.51

★:RI(2)=0是因?yàn)?階正互反矩陣總是一致的;RI(n)是n的單調(diào)增加函數(shù),說明n越大比較矩陣偏離一致矩陣的傾向越大.例:檢驗(yàn)下列兩個(gè)比較矩陣:

11/31/8311/3831A=r(A)=3.001,CI=0.001/2=0.0005,通過!

CR=0.0005/0.58<0.0011221/2161/21/61A=r(A)=3.37,CI=0.37/2=0.185,通不過!

CR=0.185/0.58>0.3思考題3-4

對例2及思考題3-3中的比較矩陣Ay2(x)做可靠性檢驗(yàn).G.多層指標(biāo)的處理?

可能出現(xiàn)多層指標(biāo)情形,例如對旅遊選點(diǎn)題的景色指標(biāo)y1下可再細(xì)分為人文景觀v1,自然景觀v2兩種(如下一幻燈片所示).?

對多層指標(biāo)情形的處理與單層指標(biāo)情形僅在求組合權(quán)Wz(x1,x2,x3)時(shí)有所不同.下麵說明如何求這個(gè)組合權(quán).問題的關(guān)鍵是如何求Wy1(x1,x2,x3)?(因求出它後就可按從前的方法求組合權(quán)Wz(x))?

一個(gè)很自然的解決辦法是:把y1視為目標(biāo);v1,v2視為指標(biāo)層;x1,x2,x3視為對象層得到一個(gè)子層次結(jié)構(gòu),從而可按前面的方法求出Wy1(x).例

旅遊選點(diǎn)問題zx1,x2,x3景色費(fèi)用食宿交通其他目標(biāo)指標(biāo)對象y1v1v2自然人文y2y3y4y5注:

多次使用這個(gè)化整為零的辦法可以解決任何更復(fù)雜的多層次結(jié)構(gòu)問題.

§3.4層次分析的若干問題

本節(jié)從應(yīng)用的角度討論幾個(gè)有關(guān)問題.它們是:⑴

不完全層次分析(不同於上面討論的每個(gè)因素都支配著下一層的所有因素的完全層次分析情形);⑵

集體層次分析;⑶

成對比較矩陣殘缺時(shí)的處理.⑴

不完全層次分析實(shí)例

以某教研室教師工作考核為例.該教研室共4名教師:x1,x2,x3,x4.不完全性表現(xiàn)在x1,x2只教學(xué);x3既教學(xué)又科研;x4只科研.教學(xué)科研y2y1zx1x4x3x2?用前面的方法先求出Wz(y1,y2)=(

1,2);Wy1(x1,x2,x3)=(

1,2,3);Wy2(x3,x4)=(3,

4).其次作矩陣

B=?

最後仍有

1

2

3000

3

4不完全層次分析組合權(quán)的計(jì)算意義:減少主觀性的根本措施.辦法①:每個(gè)人對同一問題各自作層次分析,再將他們的結(jié)果取平均值.設(shè)共有m個(gè)人,他們各自為決定權(quán)

W=Wu(v1,…,vn),提供計(jì)算結(jié)果:Wj=(w1j,…,wnj),j=1,…,m.則可綜合大家意見得最終結(jié)果為Wu(v1,…,vn)=(1/m)(W1+…+Wm)=(w1,…,wn)其中

wi=(1/m)(w1i+…+wni),i=1,…n.②:每人只建立比較矩陣,統(tǒng)一由一人取他們的綜合平均值得到最後的比較矩陣,再由此人進(jìn)行AHP計(jì)算求得權(quán)

W=Wu(v1,…,vn).

⑵集體層次分析值得一提的是:

求綜合平均比較矩陣時(shí),只須對任意i<j,求

aij的平均值,並用公式

aji=1/aij決定

aji的值即可.此外,常用發(fā)專家諮詢表的辦法尋求aij的平均值(這個(gè)平均值可以是算術(shù)平均值或幾何平均值).⑶成對比較矩陣殘缺時(shí)的處理?

專家或有關(guān)人士由於某種原因會(huì)無法對某兩個(gè)因素給出相互對比的結(jié)果aij,於是成對比較矩陣出現(xiàn)殘缺(不能補(bǔ)0,因?yàn)橐骯ij>0).這就產(chǎn)生如何對此作修正,以便能繼續(xù)進(jìn)行權(quán)向量計(jì)算的問題.?

下麵通過一個(gè)簡例,介紹一種處理方法.設(shè)一成對比較矩陣為

A=其中,符號(hào)表示殘缺.?

記由A計(jì)算的權(quán)向量為w=(w1,w2,w3)T,我們知道,用wi/wj代替殘缺的aij是合理的;Aw=rw可以代替為Cw=rw,其中

C=不難看出:Cw=rw又可以代替為Bw=rw,其中

B=(例如,Cw的第一元是w1+2w2+w1,Bw的第一元是2w1+2w2,它們相等)?

注:因a13殘缺,沒有比較1,3二因素的直接資訊,但可通過a12和a23獲得間接資訊.對比較矩陣有多個(gè)殘缺元的一般情形矩陣B的作法是

bij=0,當(dāng)aij=,ij;

bii=mi+1,mi為第i行的個(gè)數(shù),i=j;

其他bij=aij.

並非任何殘缺矩陣都是可以修補(bǔ)的.怎樣的殘缺矩陣才是可以接受的呢?這個(gè)問題的答案依賴於比較矩陣中的0元的分佈情況,已經(jīng)證明:可以接受的殘缺比較矩陣只是屬於所謂”不可約矩陣”類★的比較矩陣.★

實(shí)方陣A稱為不可約矩陣,如果把A的行列編號(hào)做適當(dāng)調(diào)整之後,可使A變?yōu)橄轮謮K形式:其中,對角塊A11,A22都是方陣.這個(gè)條件等價(jià)於用一個(gè)置換矩陣P及其轉(zhuǎn)置矩陣(也是逆矩陣)分別左,右乘A之後可使A變?yōu)樯鲜龇謮K形式.§3.5層次分析的廣泛應(yīng)用1980年文獻(xiàn):T.L.Saaty,TheAnaliticHierarchyProcess,NcGram-HillCompany,1980.問世之後,AHP方法迅速在全世界得到認(rèn)可與採用,並廣為流傳.在涉及,評(píng)價(jià),預(yù)測等方面的問題,遍及經(jīng)濟(jì)計(jì)畫與管理,能源政策與分配,行為科學(xué),軍事指揮,運(yùn)輸,農(nóng)業(yè),教育,醫(yī)療,環(huán)境等領(lǐng)域都取得了顯著的成績。

AHP方法1980年代初也傳入我國並取得很大成績.大家今天學(xué)過此法以後,在你們今後的學(xué)習(xí)和工作中也許會(huì)派上用場.

下麵介紹層次分析的幾個(gè)應(yīng)用實(shí)例.實(shí)例1

某城市供熱系統(tǒng)改造方案解：化為分別以效益y1,費(fèi)用y2為目標(biāo)的兩個(gè)層次分析問題,並分別求得組合權(quán)向量為

W1=(0.101,0.264,0.326,0.256,0.053)和

W2=(0.056,0.326,0.192,0.388,0.040).W1的第3分量最大說明:熱電聯(lián)供效益最好;而W2的第5,第1分量最小說明:沼氣,高效煤製品費(fèi)用最低.問題是如何把兩個(gè)方面結(jié)合起來進(jìn)行分析.

把它們結(jié)合在一起進(jìn)行綜合分析時(shí),可利用W1,W2的特點(diǎn)定義一個(gè)綜合權(quán)向量W,其分量是W1的分量除以W2的對應(yīng)分量.zy1節(jié)能環(huán)境社會(huì)y2投資舊設(shè)備社會(huì)x2x1x3x4x5高效煤製品區(qū)域供熱熱電聯(lián)供煤氣化郊區(qū)沼氣化效益費(fèi)用代入已求出數(shù)據(jù)得到向量(0.101/0.056,0.264/0.032,0.326/0.192,0.256/0.388,0.053/0.040)再歸一化得

W=(0.288,0.128,0.268,0.104,0.212).綜合意見:

推廣高效煤爐及煤製品雖然效益不太高,但所需費(fèi)用很低,少量資金投入即可迅速生效,可優(yōu)先實(shí)施.待資金積累較多以後再上馬熱電聯(lián)供方案.實(shí)例2

科技成果的綜合評(píng)價(jià)科技成果涉及的領(lǐng)域很廣,種類繁多,這裏指的是直接應(yīng)用於國民經(jīng)濟(jì)的某個(gè)生產(chǎn)部門後,可迅速地轉(zhuǎn)化為生產(chǎn)力.帶來可定量計(jì)算的經(jīng)濟(jì)效益的那一類成果.評(píng)價(jià)準(zhǔn)則先分為效益,水準(zhǔn)和規(guī)模3類;再在每類中確定若干具體指標(biāo).如此構(gòu)造的一個(gè)層次結(jié)構(gòu)如下圖所示.實(shí)例2科技成果評(píng)價(jià)效益C1若干待評(píng)價(jià)科技成果水準(zhǔn)C2規(guī)模C3直接經(jīng)濟(jì)效益社會(huì)效益間接經(jīng)濟(jì)效益技術(shù)創(chuàng)新技術(shù)水準(zhǔn)學(xué)術(shù)創(chuàng)新學(xué)識(shí)水準(zhǔn)實(shí)例3大國綜合實(shí)力排名次實(shí)力排名外貿(mào)經(jīng)濟(jì)軍力人力社會(huì)科技參加排名國家實(shí)例4個(gè)人工作選擇一個(gè)本科畢業(yè)大學(xué)生面臨選擇工作崗位,他(她)將要考慮的擇業(yè)原則是:

能夠發(fā)揮自己才幹為國家作貢獻(xiàn);豐厚的收入;適合個(gè)人的興趣與發(fā)展;良好的聲譽(yù);人際關(guān)係和地理位置.於是可以構(gòu)成如下圖所示的層次結(jié)構(gòu):實(shí)例4關(guān)係貢獻(xiàn)收入發(fā)展位置聲譽(yù)可供選擇單位工作選擇思考題3-5:

對你將來報(bào)考研究生或找工作,取4個(gè)你最在意的指標(biāo)因素,和3個(gè)對象,用層次分析作一個(gè)定量計(jì)算,並檢驗(yàn)計(jì)算結(jié)果的合理性(只要求對個(gè)別比較矩陣做可靠性檢驗(yàn)).實(shí)例5MCM-92B有關(guān)問題1992年國際大學(xué)生數(shù)學(xué)建模競賽B題是關(guān)於為沿海地區(qū)服務(wù)的電力公司處理風(fēng)暴引起電力中斷的應(yīng)急系統(tǒng)修復(fù)計(jì)畫.題中給出具體的電腦資料庫,列舉了一次事故發(fā)生當(dāng)天,該公司接到的修復(fù)請求者及所涉及人數(shù),並把請求者分類為居民點(diǎn),政府部門,工業(yè),商業(yè),社區(qū)和緊急單位等六類.該問題要求建立安排工作計(jì)畫的客觀準(zhǔn)則,勢必涉及按給定數(shù)據(jù)為請求者類型的優(yōu)先順序排序.這裏介紹某參賽隊(duì)用層次分析排序的詳情.先建立如下層次結(jié)構(gòu):合理排序

z單位重要性

y1

影響人數(shù)

y2居民點(diǎn)x1緊急單位x6政府部門x2工業(yè)x3商業(yè)x4社區(qū)x5

在第二層兩個(gè)因素之間進(jìn)行比較,一種觀點(diǎn)認(rèn)為”單位重要性”比之”影響人數(shù)”為”強(qiáng)”,從而決定指標(biāo)層對目標(biāo)層的權(quán)向量為wz(y1,y2)=(5/6,1/6).

為了求對象層關(guān)於因素y1的權(quán)向量,將六個(gè)對象,即六類修復(fù)請求者之間進(jìn)行成對比較,一種觀點(diǎn)給出下列比較矩陣(其中,六個(gè)對象,按

居民點(diǎn),政府部門,工業(yè),商業(yè),社區(qū)和緊急單位依次排序,即y1=居民點(diǎn),…,y6=緊急單位):用數(shù)學(xué)軟體求得A的最大特徵值為r(A)=6.589,對應(yīng)歸一化特徵向量為(0.026,0.188,0.141,0.045,0.051,0.549).對於這個(gè)比較矩陣有CI=0.589/5=0.118,CR=0.118/1.24<0.1,能通過一致性檢驗(yàn).所以上述向量可以取為權(quán)wy1(x1,…,x6).MCM92-B問題提供的數(shù)據(jù)有總共87865人,各類型所占比率即為對”影響人數(shù)”的權(quán)係數(shù):wy2(x1,…,x6)

=(0.018,0.067,0.012,0.862,0.035,0.004).最後求得組合權(quán)向量為

wz(x1,…,x6)=(5/6)wy1(x)+(1/6)wy2(x)

=(0.025,0.168,0.119,0.181,0.048,0.458)請求者類型的優(yōu)先順序即可按此向量排序.單位類型居民點(diǎn)政府部門工業(yè)商業(yè)社區(qū)緊急單位影響人數(shù)161559001035758203100395矩陣分析方法建模§4.1迴圈聯(lián)賽的獎(jiǎng)金分配及排名次問題§4.2有限網(wǎng)路的一些有趣問題§4.3數(shù)據(jù)處理的一些有趣問題§4.1

迴圈聯(lián)賽的數(shù)學(xué)建模問題隨著人們生活水準(zhǔn)的提高,人們不但喜愛體育,而且喜愛體育比賽,出現(xiàn)千千萬萬的各種體育比賽迷.隨著我國經(jīng)濟(jì)的迅速崛起,各種超級(jí)聯(lián)賽也應(yīng)運(yùn)而生.大型賽事常常是人們飯後茶餘的主要話題.體育比賽中也有數(shù)學(xué)建模問題,本節(jié)就來介紹,迴圈聯(lián)賽的獎(jiǎng)金分配及排名次所涉及的數(shù)學(xué)建模問題.A

迴圈聯(lián)賽的獎(jiǎng)金分配問題背景已有多年迴圈比賽歷史的

n支球隊(duì):T1,T2,…,Tn

今年照例舉行無平局的迴圈聯(lián)賽,約定按下列規(guī)則發(fā)放獎(jiǎng)金:規(guī)則戰(zhàn)勝Ti得獎(jiǎng)金

xia

元,a

為待定的獎(jiǎng)金單位(換句話說,各隊(duì)獎(jiǎng)金按比例

x1:x2:

:xn發(fā)放).問題如何合理地決定獎(jiǎng)金係數(shù)向量

x=(x1,x2,…,xn)T(準(zhǔn)確到相差正因數(shù)

a),使對每一隊(duì)來說都保持公平?問題分析與假設(shè)獎(jiǎng)金向量的公平性體現(xiàn)在:Ti越強(qiáng)

xi越大.(戰(zhàn)勝強(qiáng)隊(duì)是衡量球隊(duì)發(fā)揮好的標(biāo)誌)各隊(duì)強(qiáng)弱程度用勝負(fù)概率矩陣

F=(fij)來刻畫,fij

表示

Ti

戰(zhàn)勝

Tj

的概率.假設(shè):

n

個(gè)隊(duì)中沒有特別強(qiáng)或特別弱的隊(duì)(否則該隊(duì)早已升級(jí)或降級(jí)離開了),即

i,j,0<fij<1,fij=1-fji;

為方便起見,更設(shè)i,fii=0.勝負(fù)概率矩陣簡例

設(shè)n=3;在過去的十場比賽中

T1對T26勝4負(fù);T1對T37勝3負(fù);T2對T32勝8負(fù),

則勝負(fù)概率矩陣為:00.60.70.400.20.30.80F

=勝負(fù)概率矩陣需要精細(xì)地確定僅按過去Ti,Tj兩隊(duì)比賽總場數(shù)及勝負(fù)場數(shù)之比確定fij,雖然操作簡單,但是過於粗糙,因?yàn)楸荣愑写筚?中賽和小賽之分.對於較大比賽,兩隊(duì)都較重視,比賽成績較能反映兩隊(duì)的實(shí)際情況.反之,他們對於較小比賽一般不夠重視,其成績不能準(zhǔn)確代表兩隊(duì)的實(shí)際情況.此外,也應(yīng)把大勝,中勝和小勝加以區(qū)分.故要精細(xì)地確定fij,應(yīng)區(qū)別對待大,中,小賽.和區(qū)別對待大勝,中勝和小勝,並用層次分析方法制定相應(yīng)的權(quán)向量.用層次分析合理決定勝負(fù)概率矩陣之例zy2y3y1大賽中賽小賽x1x2x3x4大勝小勝平負(fù)WZ(y)=(4/7,2/7,1/7);i,Wyi(x)=(3/6,2/6,1/6,0).即,對比賽等級(jí)用4:2:1加權(quán);對比賽勝負(fù)程度用3:2:1:0

加權(quán).例如,某兩隊(duì)的歷史記錄由下表給定,用此公式算出的勝負(fù)概率是:fij=4/7.場次12345等級(jí)大賽中賽小賽小賽中賽Ti:Tj小勝小負(fù)大負(fù)小負(fù)小勝如果僅用勝負(fù)次數(shù)計(jì)算Ti和Tj的勝負(fù)概率,則因Ti是5場2勝;Tj是5場3勝,由此即得:fij=2/(2+3)=2/5;fji=3/(2+3)=3/5.如果用上面介紹的加權(quán)辦法計(jì)算Ti和Tj的得分di和dj的話,則di=4

2+0+0+0+22=12;dj=0+22+13+12=9.fij=12/(12+9)=4/7;fji=1-fij=3/7.上述二結(jié)果大相庭徑,哪個(gè)更合理?按體育常識(shí)而論,正確的答案應(yīng)該是後者.合理性討論數(shù)學(xué)建模Ti可期望共獲獎(jiǎng)金數(shù)為:★Ti可期望共失獎(jiǎng)金數(shù)為:易見獎(jiǎng)金向量為公平的充要條件是:令ui=

j=1nfji,aij=fij/ui,則(1)等價(jià)於或Ax=x

(2)★因Ti可期望戰(zhàn)勝而獲獎(jiǎng)金數(shù)為fijxja,j=1,…,n,故Ti可期望共獲獎(jiǎng)金數(shù)為:

j=1nfijxja.

因Tj可期望戰(zhàn)勝Ti而獲獎(jiǎng)金數(shù)為fjixia,j=1,…,n,故Ti可期望共失獎(jiǎng)金數(shù)為:

j=1nfjixia.這樣一來,上述兩個(gè)求和式就有了它們的實(shí)際意義.在數(shù)學(xué)的學(xué)習(xí)中,我們經(jīng)常要對一個(gè)死的數(shù)學(xué)式子,通過對它的含義的解釋,而賦予它生命,這種所謂”理解性的翻譯”,對數(shù)學(xué)建模尤為重要.例如對例1,上述方程組的係數(shù)矩陣計(jì)算如下:00.60.70.400.20.30.80F

=06/712/701/71/38/90A

=基於上述分析得:結(jié)論:如果由勝負(fù)概率矩陣

F

形成的矩陣

A以1為單特徵值,並且有對應(yīng)於1的正特徵向量

x,則此向量

x

可取為唯一合理的獎(jiǎng)金向量.證:我們所討論問題的合理獎(jiǎng)金向量,按所定規(guī)則,必須是滿足方程組(2)的一個(gè)正向量,並要求這樣的正向量不計(jì)較相差一個(gè)任意常數(shù)因數(shù)是唯一的.注:由下麵的定理４.1與定理4.2推出,上述結(jié)論所要求的條件總能滿足,因此,本問題恒有解.有關(guān)數(shù)學(xué)背景知識(shí)定義:實(shí)方陣

A=(aij)稱為正(非負(fù))矩陣,如果

i,j,aij

>()0;非負(fù)方陣

A

稱為本原矩陣,如果存在正整數(shù)

m

使得

Am

為正矩陣.定理4.1:任意本原矩陣A都恰有一個(gè)正特徵值r(A),其值大於其他特徵值的模數(shù)(故r(A)為單特徵值,任意兩個(gè)對應(yīng)於它的特徵向量都線性相關(guān)),並且存在對應(yīng)於

r(A)的正特徵向量x.定理4.2:當(dāng)n3時(shí),獎(jiǎng)金分配問題中定義的矩陣

A

是本原矩陣,並且

r(A)=1.定理4.2

的證明定理4.2:

獎(jiǎng)金分配問題中定義的矩陣

A

是本原矩陣,並且

r(A)=1.證:

因

ij,aij=fij/ui

0,故當(dāng)n3時(shí),

A2

是一個(gè)正矩陣,即

A

是本原矩陣.從而,按定理4.1,有對應(yīng)於

r(A)的正特徵向量x:Ax=r(A)x.令v=(u1,…,un)T,則vTA

=

vT.於是vTx

=

vTAx

=

r(A)vTx.

因

vTx

0,由上式推出r(A)=1.0+++0+++0A2=0+++0+++0+++++++++=vTA=(u1,…,un)f11/u1

f1n/u1

fn1/un

fnn/un=(u1,…,un)=vT其中,ui=

j=1nfji求獎(jiǎng)金向量方法與例方法:

首先由歷史記錄確定勝負(fù)概率矩陣

F;其次由

F

確定矩陣

A;最後由適當(dāng)數(shù)學(xué)軟體,例如,Matlab,求出對應(yīng)於

A

的特徵值1的任一個(gè)正特徵向量

x,則此向量x

可取為合理的獎(jiǎng)金向量.對於前面討論的例1:我們首先由勝負(fù)概率矩陣F求得矩陣A為:

A

=

其次,利用數(shù)學(xué)軟體

Matlab

的行命令:A=[0,6/7,1;2/7,0,1/7;1/3,8/9,0];[V,D]=eig(A)求得對應(yīng)於A的最大特徵值為1,對應(yīng)於1的一個(gè)正特徵向量是:xT=(0.7910,0.3020,0.5321),這個(gè)正向量就是我們要求的獎(jiǎng)金向量.06/712/701/71/38/90方法:

設(shè)獎(jiǎng)金總額預(yù)算值為S,則由上式立即求得a=S/(x1u1+…+xnun).如何由獎(jiǎng)金總額決定獎(jiǎng)金單位?例如對例1有

a=S/1.455.

如果迴圈聯(lián)賽組委會(huì)的獎(jiǎng)金總額預(yù)算為3萬元左右時(shí),S=3(萬).則

a=3/1.455=2.062.所以,戰(zhàn)勝T1得獎(jiǎng)金

x1a=0.791

2.062=1.631(萬元);戰(zhàn)勝T2得獎(jiǎng)金

x2a=0.302

2.062=0.623(萬元);戰(zhàn)勝T3得獎(jiǎng)金

x3a=0.532

2.062=1.097(萬元).注:此三數(shù)之和為3.35萬,並不正好是3萬.如果強(qiáng)隊(duì)均輸,則獎(jiǎng)金總數(shù)為:21.631+1.097=4.36(萬元);如果弱隊(duì)均輸,則獎(jiǎng)金總數(shù)為20.623+1.097=2.34(萬元),它們的平均值正是3.35萬元.B

迴圈聯(lián)賽各隊(duì)排名次問題背景已有多年迴圈比賽歷史的俱樂部欲為所屬

n支球隊(duì):

T1,T2,…,Tn按強(qiáng)弱排名次.方法根據(jù)勝負(fù)概率矩陣

F=(fij)計(jì)算各隊(duì)的得分向量

v=(v1,…,vn)和評(píng)分向量u=(u1,…,un),其規(guī)則是:規(guī)則

vi=

j=1nfijuj,i=1,…,n(1)uj

的意義是每個(gè)戰(zhàn)勝

Tj的隊(duì)都得分

uj.問題如何決定向量

u

和

v,使對每一隊(duì)都保持公平?問題分析與假設(shè)公平地決定向量v=(v1,…,vn)和u=(u1,…,un)體現(xiàn)在:v1:

:vn=u1:

:un,或存在正數(shù)滿足=v1/u1=…=vn/un

即

v=

u.(2)

將(1)代入(2)得

Fu=

u.(3)結(jié)論:勝負(fù)概率矩陣F是本原矩陣(F2為正矩陣),從而由前面的定理4.1,F恰有一個(gè)正特徵值

,其所對應(yīng)的任何正特徵向量(只有倍數(shù)差別)都可取為得分向量v或評(píng)分向量u.因向量v與u相差正常數(shù)倍,故可按v或u的各分量的大小為各隊(duì)排名次.例1例1:我們有勝負(fù)概率矩陣

利用Matlab的下列行命令:F=[0,0.6,0.7;0.4,0,0.2;0.3,0.8,0];[V,D]=eig(F)求得對應(yīng)於F的正特徵值0.9414的一個(gè)特徵向量是:vT=(0.6985,0.4199,0.5794),此向量v即可取為我們要求的得分向量.按v的分量的大小為各隊(duì)排名次的結(jié)果是:T1,T3,T2F=00.60.70.400.20.30.80也可用獎(jiǎng)金向量為各隊(duì)排名次例1:由合理獎(jiǎng)金向量xT=(x1,…,xn)的性質(zhì)知:對任二球隊(duì)Ti和Tj都有xi

xj

Ti比Tj強(qiáng).因此,也可按x1,…,xn的大小為各隊(duì)排名次.例如,對於例1我們已求得合理的獎(jiǎng)金向量為

xT=(0.7910,0.3020,0.5321).按x的分量的大小為各隊(duì)排名次的結(jié)果是:T1,T3,T2.

這個(gè)結(jié)果與前面按得分向量v的分量的大小為各隊(duì)排名次的結(jié)果相一致的事實(shí)也說明我們以上的分析是正確的.

如果要對這兩個(gè)方法進(jìn)行評(píng)優(yōu)的話,應(yīng)該說,本節(jié)的方法較優(yōu),因?yàn)榇朔椒ㄖ苯永镁仃嘑即可求出結(jié)果,而用上一個(gè)方法,則還需要從F再計(jì)算矩陣A的額外工作量.兩個(gè)方法的比較

一個(gè)實(shí)例:下表為某個(gè)俱樂部的4支足球隊(duì)的比賽記錄,試用本節(jié)方法為這4支球隊(duì)排名次.T2T3T43:0,1:1,2:22:1,2:3,0:02:1,3:1T11:43:1,2:3T25:2,4:2T3規(guī)定fij=0.6uij+0.4vij,uij為平均場分;vij為平均進(jìn)球分.場分:勝2,平1,負(fù)0;進(jìn)球分:進(jìn)一球1分.例如,u21=(2+1+1)/(2+2+2)=2/3(每場總分是2),v21=(3+1+2)/(3+2+4)=2/3;f21=0.6u21+0.4v21=2/3.01/31/24/352/3023/2543/901/22/2508/6531/3547/9057/650首先請大家驗(yàn)證矩陣F有如下數(shù)值:F=其次用Matlab算出矩陣F的對應(yīng)於唯一正特徵值1.2263的一個(gè)正特徵向量是:U=(0.329,0.617,0.242,0.673)T,用它為各隊(duì)排名次得:T4,T2,T1,T3§4.2

有限網(wǎng)路的一些有趣問題

電腦網(wǎng),交通網(wǎng),灌溉網(wǎng),輸電網(wǎng),電話網(wǎng)等都是常見的有限網(wǎng)路.

有限網(wǎng)路的數(shù)學(xué)模型是有限無向圖.無向圖G是一個(gè)二重組:G=V,E,其中V是非空有限集合,它的元素稱為結(jié)點(diǎn),E也是(非空)有限集合,它的元素稱為邊.圖G的邊e是一個(gè)結(jié)點(diǎn)二重組:e=(a,b),a,bV,稱e與a,b關(guān)聯(lián),或a,b與e關(guān)聯(lián),或a與b相鄰接.無向圖可用一些點(diǎn)和連接兩點(diǎn)間的連線(邊)的一個(gè)圖形來表示.本節(jié)將討論關(guān)於有限網(wǎng)路的兩個(gè)有趣問題.問題

1背景:設(shè)有限網(wǎng)路的各點(diǎn)僅取0或1兩種狀態(tài);開始時(shí)刻每點(diǎn)都取‘0’;以後每次從各點(diǎn)中任選一點(diǎn)令其改變狀態(tài),同時(shí)也令與此點(diǎn)相鄰接的所有結(jié)點(diǎn)改變狀態(tài).例1:下列4點(diǎn)網(wǎng)路前幾次狀態(tài)改變情況如下:0

0001110

11111110000

0

問題1:對任何網(wǎng)路是否總能經(jīng)有限次改變狀態(tài)後使網(wǎng)路從‘全0’狀態(tài)變?yōu)椤?’狀態(tài)?

問題1在一些情況下具有明確的實(shí)際意義.例如:如果所考慮的有限網(wǎng)路代表照明網(wǎng)路;

‘0’,‘1’

兩種狀態(tài)分別代表關(guān)燈,開燈;其中某盞燈改變狀態(tài)時(shí)與之相鄰接的每盞燈也同時(shí)改變其狀態(tài).

則問題1的意義是:每一次選定一盞燈令它及與之相鄰的燈都改變狀態(tài),能否經(jīng)有限次改變後使此有限照明網(wǎng)路從開始時(shí)全部關(guān)燈過渡到全部開燈?問題1的實(shí)際意義數(shù)學(xué)建模準(zhǔn)備用(0,1)向量描述網(wǎng)路狀態(tài):第k次改變結(jié)束時(shí),網(wǎng)路狀態(tài)用向量x(k)=(x1k,…,xnk)T表示,其中,xik=0或1表示第k次改變結(jié)束時(shí)網(wǎng)路的第i個(gè)結(jié)點(diǎn)的狀態(tài)是‘0’或‘1’.例1:x(0)=(0,0,0,0),x(1)=(1,1,0,1),x(2)=(1,0,1,0),x(3)=(0,0,0,1),x(4)=(1,1,1,1).(結(jié)點(diǎn)編號(hào)見後)關(guān)鍵是:尋求x(k)與x(k+1)的關(guān)係.如能得到從x(k)計(jì)算x(k+1)的公式,則問題的解決就有了辦法.作網(wǎng)路的鄰接矩陣A=(aij),aij=0或1,由結(jié)點(diǎn)i與結(jié)點(diǎn)j鄰接或不鄰接而定;並令

i,aii=1.對例1得1101111001111011A=

將該網(wǎng)路的左上角結(jié)點(diǎn)編號(hào)為1,並按反時(shí)針順序把其餘點(diǎn)依次標(biāo)號(hào)為2,3,4.令

ei表示第i個(gè)元素為1其餘元素為0的n維列向量(n階單位矩陣第i列),則Aei表示A的第i列.易見:

x(1)T=(1,1,0,1)=(0,0,0,0)+(1,1,0,1)=x(0)+Ae1

(上一次選擇了第1點(diǎn));x(2)T=(1,0,1,0)=(1,1,0,1)+(0,1,1,1)=x(1)+Ae3=x(0)+A(e1+e3)(上一次選擇了第3點(diǎn),取按位加:1+1=0);同樣可得x(3)T=(0,0,0,1)=x(0)+A(e1+e3+e4);x(4)T=(1,1,1,1)=x(0)+A(e1+e3+e4+e2).一般地,x(k+1)=x(k)+Aeu,這裏,u是第k次選定點(diǎn)的序數(shù).證:Aeu為A的第u列,x(k)+Aeu的第i元是x(k)的與Aeu的第i元的按位加,注意當(dāng)Aeu的第i元是0時(shí),表示第i結(jié)點(diǎn)與選定的第u結(jié)點(diǎn)不相鄰,按我們的規(guī)則,第i點(diǎn)保持原狀態(tài),即與第k次的狀態(tài)相同,這正與按位加法性質(zhì):”0加何數(shù)仍為何數(shù)”的結(jié)論相一致;當(dāng)Aeu的第i元是1時(shí),表示第i結(jié)點(diǎn)與選定的第u結(jié)點(diǎn)相鄰(規(guī)定:每個(gè)結(jié)點(diǎn)都與自己相鄰),按我們的規(guī)則,第i點(diǎn)要改變狀態(tài),即與第k次的狀態(tài)不同,這正與按位加法性質(zhì):1+0=1,1+1=0

的結(jié)論相一致.結(jié)論結(jié)論:令e表示元素全為1的n維向量.如果方程

Ax=e

在2元域

Z2

中有解x=ei1+ei2+…+eim,則依次選點(diǎn)i1,i2,…,im

讓網(wǎng)路作m次改變狀態(tài),可使網(wǎng)路從全0狀態(tài)變?yōu)槿?狀態(tài).注:由於域Z2中加法是可交換的,故結(jié)果只與此m個(gè)點(diǎn)有關(guān),而與選擇他們的順序無關(guān),即按任意順序選擇此m個(gè)點(diǎn),讓網(wǎng)路改變狀態(tài),其結(jié)果都可使網(wǎng)路變?yōu)槿?狀態(tài).

2元域定義為代數(shù)系統(tǒng):Z2=

{0,1},+,

,其中加法定義為0+1=1+0=1;1+1=0+0=0

乘法定義為0

1=1

0=00=0;1

1=1易見:{0,1}關(guān)於上述加法,乘法構(gòu)成交換群;滿足加法,乘法的分配律;並且非0元(1)有乘法逆元(1),所以,Z2是一個(gè)域.可以象實(shí)矩陣一樣,定義Z2上的矩陣(元素取值於Z2的矩陣)及其加,乘法運(yùn)算,只須注意兩點(diǎn):①1+1=0;②結(jié)果是Z2上的矩陣.Z2上的線性方程組的理論與實(shí)線性方程組的理論完全類似.解法也差不多.這個(gè)只有兩個(gè)元素的有限域,在許多領(lǐng)域都有重要應(yīng)用.演算法目的:尋求方程Ax=e在2元域Z2中的解x.演算法:為在域Z2中解線性方程組Ax=e,我們把增廣矩陣(A┊e)用域Z2中初等行變換化為(E┊x)的形式,其中E為單位矩陣,則x即為所要求的解.例11101

11110

10111

11011

1(Ae)

交換上三角陣對角矩陣所需要的解為:x=(1,1,1,1)T=e1+e2+e3+e4.1101

10011

00111

10110

01101

10110

00011

00001

11000

10100

10010

10001

11101

10110

00011

00111

1Ax=e在域Z2中恒有解證:由數(shù)域Z2上線性方程組一般理論知:Ax=e在域Z2上無解當(dāng)且僅當(dāng)在Z2中可把該方程組化為0=1的矛盾方程.因此,若此方程組無解,則把它的一些方程,不失一般性,可假設(shè)為前k個(gè)方程加到一起會(huì)得到矛盾方程:0=1.於是有

i=1kaij=0,j=1,…,n,1=1+1+…+1(共k個(gè)).因此,k是奇數(shù),和

i=1k

j=1kaij=0(*)但由於A是對角元全為1的對稱矩陣和k是奇數(shù),又推出(*)式左邊等於1

的矛盾.∴Ax=e在域Z2上不可能無解.

矩陣A是對稱的蘊(yùn)涵其非0對角元的個(gè)數(shù)必為偶數(shù).(*)式左邊等於A的前k行k列的非0元之和在Z2中的值.因?yàn)?在這裏非0元就是1;對角元全為1;並且k是奇數(shù).所以,(*)式左邊等於奇數(shù)個(gè)1在Z2中之和,此值必等於1.應(yīng)用於問題1得出的結(jié)論結(jié)論:

對任意有限網(wǎng)路,適當(dāng)依次選點(diǎn)作有限次改變狀態(tài),都可使網(wǎng)路從全0狀態(tài)變?yōu)槿?狀態(tài).思考題4-1:對開始為全0狀態(tài)的下列兩網(wǎng)路,如何選一些結(jié)點(diǎn),每次改變一點(diǎn)狀態(tài)使網(wǎng)路最後變?yōu)槿?狀態(tài)?你能編一個(gè)(例如Matlab)程式求解有關(guān)方程組嗎?(1)(2)123465798思考題4-2:對任意有限網(wǎng)路及任意初始狀態(tài),適當(dāng)依次選點(diǎn)作有限次改變狀態(tài)都可使網(wǎng)路變?yōu)槿?狀態(tài)嗎?(提示:以下列網(wǎng)路為例,考慮你的答案.)從任意狀態(tài)變?yōu)槿?狀態(tài)的討論由思考題4-2知:一般不能保證從任意狀態(tài)都能變?yōu)槿?狀態(tài).自然要提出問題:網(wǎng)路滿足什麼條件,才能保證從任意初始狀態(tài)出發(fā),都能經(jīng)有限次按規(guī)則改變狀態(tài)後達(dá)到全1狀態(tài)?(等價(jià)於:從任意初始狀態(tài)開始變到任意指定的狀態(tài)結(jié)束)利用前面建立的數(shù)學(xué)模型不難找到我們需要的答案,其理論依據(jù)是下麵的定理4.3.二元域Z2上線性方程組的一個(gè)定理定理４.3

在二元域Z2上,若detA0,則線性方程組Ax=b對任意右端b恒有唯一解.證:設(shè)detA0,對線性方程組Ax=b的係數(shù)矩陣施行Z2中行初等變換,任何時(shí)候都不會(huì)變出零列,否則,令變換矩陣的乘積為P便有det(PA)=0蘊(yùn)涵detA=0的矛盾.因此,對增廣矩陣(A┊b)在Z2中施行行初等變換,一定可化為(E┊x)的形式(E為單位矩陣),從而,所唯一確定的x就是該方程組的唯一解

.

也可用二元數(shù)域Z2上的矩陣?yán)碚撟C明定理4.3,其要點(diǎn)如下:

按Z2上的矩陣?yán)碚?當(dāng)detA0時(shí),A在Z2上有逆矩陣A-1,滿足:A-1是Z2上的矩陣,並且A-1A=E.以A-1左乘線性方程組Ax=b的兩端即得

x=A-1b.這就證明了,Ax=b對任意右端b恒有唯一解A-1b.應(yīng)用舉例例如,對於思考題4-2⑴中的網(wǎng)路,我們知道它的係數(shù)矩陣A,經(jīng)Z2中行初等變換可以化為下列矩陣:由此可以斷定detA0,從而按定理4.3,此網(wǎng)路無論從任何指定狀態(tài)開始,經(jīng)有限次改變狀態(tài)都可以變到全1狀態(tài).問題

2背景:設(shè)有限網(wǎng)路的各點(diǎn)僅取‘+’或‘-’兩種狀態(tài);已知其開始時(shí)刻每點(diǎn)的狀態(tài);以後按下列規(guī)則,定時(shí)改變網(wǎng)路的狀態(tài).規(guī)則:對於每點(diǎn),若上一時(shí)刻其鄰點(diǎn)取‘+’,取‘-’的數(shù)目相同時(shí)維持原狀態(tài);否則,將此點(diǎn)改變?yōu)槠涠鄶?shù)鄰點(diǎn)的狀態(tài).+++++++---+++++++++++++--+++--+++--+++--變化規(guī)律:例1趨於穩(wěn)定,例2趨於交叉迴圈.自然要問:對任意網(wǎng)路和任意初始狀態(tài),是否都有這個(gè)變化規(guī)律,即:不是趨於穩(wěn)定,便是趨於交叉迴圈?例1例2問題2:對任何網(wǎng)路和任意初始狀態(tài),是否總會(huì)趨於穩(wěn)定或趨於交叉迴圈?

換句話說,是否總是成立:當(dāng)k充分大時(shí),第k+2時(shí)刻的狀態(tài)恒與第k時(shí)刻的狀態(tài)相同?試對你的結(jié)論給出嚴(yán)格證明.數(shù)學(xué)建模準(zhǔn)備用(1,-1)向量描述網(wǎng)路狀態(tài):第

k

次改變後,網(wǎng)路狀態(tài)用(行)向量x(k)=(x1k,…,xnk)表示,其中,xik

=1或-1表示第k次改變後網(wǎng)路的第i個(gè)結(jié)點(diǎn)的狀態(tài)是”+”或”-”.例1:將該網(wǎng)路的最上面一結(jié)點(diǎn)編號(hào)為1,並按反時(shí)針順序把其餘結(jié)點(diǎn)標(biāo)號(hào)為

2,3,4,5,則

x(0)T=(1,-1,1,1,-1),x(1)T=(-1,1,1,1,1),x(2)T=(1,1,1,1,1)=x(k)T,k=3,4,…

數(shù)學(xué)建模問題2的數(shù)學(xué)模型歸結(jié)為證明定理4:對任何網(wǎng)路和任意初始狀態(tài)都存在正整數(shù)N,使得

kN,x(k+2)=x(k).(例如,對例1,N=2;對例2,N=0.)分析與證明關(guān)鍵仍是求x(k+1)與x(k)間的關(guān)係,與前面一樣,需要巧妙地構(gòu)作一個(gè)網(wǎng)路矩陣A=(aij).這個(gè)矩陣應(yīng)與網(wǎng)路的鄰接結(jié)構(gòu)和問題的遊戲(改變狀態(tài))規(guī)則密切相關(guān),具體作法是:aij=0或1,由結(jié)點(diǎn)與結(jié)點(diǎn)鄰接或不鄰接而定;aii=1/2(1/2可代以小於1的任意正數(shù)).例如,對例1,例2有1/2100111/2101011/2100011/2111011/2A=幾個(gè)引理引理1:對任意k0,x(k+1)與

Ax(k)的每個(gè)對應(yīng)分量都同號(hào).證:這直接由網(wǎng)路矩陣A的定義及變化規(guī)則推出.例如,對例1,1/2100111/2101011/2100011/2111011/2Ax(0)=1-111-1=-++++與

x(1)=-11111同號(hào).這裏,0<1/2<1和1/21=蘊(yùn)涵:Ax(k)每個(gè)分量當(dāng)上一時(shí)刻對應(yīng)點(diǎn)的鄰點(diǎn)取+,取-的數(shù)目相同時(shí)與上時(shí)刻對應(yīng)點(diǎn)同號(hào);

否則,取多數(shù)鄰點(diǎn)的符號(hào).由規(guī)則知必與x(k+1)同號(hào).定義

k

的下列能量函數(shù):f(k)=x(k+1)TAx(k)=x(k)TAx(k+1).(因A為對稱陣)對例1,f(0)=7/2;f(1)=19/2;f(k)=eTAe=29/2,k=2,3,…令S={y=(y1,…,yn)T|y1,…,yn{1,-1}},則S是有2n個(gè)元素的有限集.能量函數(shù)引理2:對任何正整數(shù)k都有f(k)=MAXyS(yTAx(k))證:我們有f(k)=x(k+1)TAx(k);對任何正整數(shù)

k,x(k)每個(gè)分量的絕對值都為

1,並且S中的任何向量

y

也是如此.由引理1知,Ax(k)與x(k+1)一樣無零分量.

因此,yTAx(k)取最大值當(dāng)且僅當(dāng)

yT與

Ax(k)同號(hào),或等價(jià)地(用引理1),yTAx(k)取最大值當(dāng)且僅當(dāng)

y=x(k+1).引理3:極限

limkf(k)存在.證:因

k,x(k-1)S,故由引理2推出

f(k)

x(k-1)TAx(k)=f(k-1).即{f(k)}是單調(diào)不減實(shí)數(shù)列.此外,對任何正整數(shù)k,x(k)每個(gè)分量的絕對值都為

1,A為元素不大於1的非負(fù)矩陣,於是又有

f(k)=x(k+1)TAx(k)

i=1n

j=1naji

n2(有限數(shù)).換句話說,{f(k)}是有上界的單調(diào)不減的實(shí)數(shù)序列,由極限理論得證:這個(gè)序列的極限存在.定理4.4:對任何網(wǎng)路和任意初始狀態(tài)都存在正整數(shù)N,使得

kN,x(k+2)=x(k).證:令limkf(k)=L(有限數(shù));W={yTAz|y,zS}.則f(k)=x(k+1)TAx(k)

W,從而f(k)至多取|W|=|S|2=(2n)2=

4n個(gè)不同的值,所以,一定存在足夠大的正整數(shù)N,使得kN,f(k)=f(k+1)=L.由能量函數(shù)f(k)的定義及引理2,上式等價(jià)於kN,MAXyS(yTAx(k))=x(k)TAx(k+1)=x(k+2)TAx(k+1).

所以,x(k)與x(k+2)所有分量必同號(hào),從而得證

kN,x(k+2)=x(k).§4.3

數(shù)據(jù)處理的一些有趣問題大家知道,數(shù)據(jù)處理中的二元數(shù)組就是一個(gè)實(shí)數(shù)矩陣

A=(aij).因此,下麵關(guān)於實(shí)矩陣的問題3,問題4所得出的結(jié)論會(huì)是有用的.問題3問題3:試證對任意(任意行列數(shù),任意取值)的實(shí)矩陣

A=(aij),施行乘一行或一列以-1

的運(yùn)算若干次後,總能得到所有行和,所有列和都不小於

0

的一個(gè)矩陣.證:對

A

施行乘一行或一列以-1的運(yùn)算若干次後,一切可能的結(jié)果組成下列有限集:S={

A=A1,A2,…,Ak

},k

2mn,

其中,m,n分別為矩陣

A的行,列數(shù).(因?qū)ν恍?列施行此種運(yùn)算兩次等價(jià)於保持不動(dòng))引入下之能量函數(shù)f:

SR,B=(bij)S,f(B)=i=1k

j=1k

bij.因k為有限實(shí)數(shù),故存在u{1,…,k}使得f(Au)=max{f(A1),…,f(Ak)}.下麵用反證法證明:矩陣Au有我們所需要的性質(zhì).如果Au

的某一,例如,第h行和

rh

0.令A(yù)t為以

-1乘

Au第h行所得的矩陣,則

f(At)=

f(Au)+

At第h行和

-

Au第h行和

=

f(Au)+2|