1、第四章 矩陣分析方法建模4.1 循環聯賽的獎金分配及排名次問題4.2 有限網絡的一些有趣問題4.3 數據處理的一些有趣問題4.1 循環聯賽的數學建模問題隨著人們生活水平的提高,人們不但喜愛體育,而且喜愛體育比賽,出現千千萬萬的各種體育比賽迷.隨著我國經濟的迅速崛起,各種超級聯賽也應運而生.大型賽事常常是人們飯后茶余的主要話題.體育比賽中也有數學建模問題,本節就來介紹,循環聯賽的獎金分配及排名次所涉及的數學建模問題.A 循環聯賽的獎金分配問題背景 已有多年循環比賽歷史的 n支球隊:T1,T2,Tn 今年照例舉行無平局的循環聯賽,約定按下列規則發放獎金:規則 戰勝Ti得獎金 xia 元,a 為待定

2、的獎金單位(換句話說,各隊獎金按比例 x1:x2: :xn發放).問題 如何合理地決定獎金(系數)向量 x=(x1,x2,xn)T(準確到相差正因子 a),使對每一隊來說都保持公平?問題分析與假設獎金向量的公平性體現在: Ti越強 xi越大. (戰勝強隊是衡量球隊發揮好的標志) 各隊強弱程度用勝負概率矩陣 F=(fij) 來刻畫,fij 表示過去 Ti 戰勝 Tj 的概率.假設: n 個隊中沒有特別強或特別弱的隊(否則該隊早已升級或降級離開了),即i,j,0fij()0;非負方陣 A 稱為本原矩 陣,如果存在正整數 m 使得 Am 為正矩陣.定理4.1:任意本原矩陣A都恰有一個正特征值r(A)

3、,其值大于其它特征值的模數(故r(A)為單特征值,任意兩個對應于它的特征向量都線性相關),并且存在對應于 r(A)的正特征向量x.定理4.2:當n3時,獎金分配問題中定義的矩陣 A 是本原矩陣,并且 r(A)=1.定理4.2 的證明定理4.2: 獎金分配問題中定義的矩陣 A 是本原矩陣,并且 r(A)=1.證: 因ij,aij=fij/ui 0,故當n3時, A2 是一個正矩陣,即 A 是本原矩陣. 從而,按定理4.1,有對應于 r(A)的正特征向量x: Ax=r(A)x.令v=(u1,un)T,則 vTA = vT. 于是 vTx = vTAx = r(A)vTx. 因 vTx 0,由上式推

4、出 r(A)=1.A2=AA=vTA=(u1,un)f11/u1f1n/u1fn1/unfnn/un=(u1,un)=vT其中,ui=j=1nfji求獎金向量方法與例方法: 首先由歷史記錄確定勝負概率矩陣 F; 其次由 F 確定矩陣 A; 最后由適當數學軟件,例如,Matlab,求出對應于 A 的特征值1的任一個正特征向量 x,則此向量 x 可取為合理的獎金向量.對于前面討論的例1:我們首先由勝負概率矩陣F求得矩陣A為: A = 其次,利用數學軟件 Matlab 的行命令:A=0,6/7,1;2/7,0,1/7;1/3,8/9,0;V,D=eig(A)求得對應于A的最大特征值為1,對應于1的一

5、個正特征向量是:xT=(0.7910,0.3020,0.5321),這個正向量就是我們要求的獎金向量.06/712/701/71/38/90方法: 設獎金總額預算值為S,則由上式立即求得 a=S/(x1u1+xnun).對例1有 a=S/(0.79100.7+0.30201.4+0.53210.9)=S/1.455.如何由獎金總額決定獎金單位?例如對例1有 a=S/1.455. 如果循環聯賽組委會的獎金總額預算為 3萬元左右時,S=3(萬).則 a=3/1.455=2.062.所以,戰勝T1得獎金 x1a=0.7912.062=1.631(萬元);戰勝T2得獎金 x2a=0.3022.062=

6、0.623(萬元);戰勝T3得獎金 x3a=0.5322.062=1.097(萬元).注:此三數之和為3.35萬,并不正好是3萬.如果強隊均輸,則獎金總數為: 21.631+1.097=4.36(萬元);如果弱隊均輸,則獎金總數為20.623+1.097=2.34(萬元),它們的平均值正是3.35萬元.B 循環聯賽各隊排名次問題背景 已有多年循環比賽歷史的俱樂部欲為所屬n支球隊:T1,T2,Tn按強弱排名次.方法 首先制定評分標準,即確立評分向量u=(u1,un),uj的意義是每個戰勝Tj的隊都得分uj;其次根據勝負概率矩陣F=(fij)和評分向量u計算各隊的得分向量v=(v1,vn)其規則是

7、:規則 vi=j=1nfijuj, i=1,n 或 v=Fu (1) 問題 如何決定向量u和v,使對每一隊都保持公平?問題分析與假設公平地決定向量v=(v1,vn)和u=(u1,un)體現在:v1: :vn=u1: :un,或存在正數滿足 =v1/u1=vn/un 即 v=u. (2) 將(2)代入(1)得 Fu=u. (3)結論:勝負概率矩陣F是本原矩陣(F2為正矩陣),從而由前面的定理4.1,F恰有一個正特征值,其所對應的任何正特征向量(只有倍數差別)都可取為得分向量v或評分向量u.因向量v與u相差正常數倍,故可按v或u的各分量的大小為各隊排名次.例1例1:我們有勝負概率矩陣 利用Matl

8、ab的下列行命令:F=0,0.6,0.7;0.4,0,0.2;0.3,0.8,0;V,D=eig(F)求得對應于F的正特征值0.9414的一個特征向量是:vT=(0.6985,0.4199,0.5794), 此向量v即可取為我們要求的得分向量.按v的分量的大小為各隊排名次的結果是: T1, T3, T2F=00.60.70.400.20.30.80也可用獎金向量為各隊排名次例1:由合理獎金向量xT=(x1,xn)的性質知:對任二球隊Ti和Tj都有xixj Ti比Tj強.因此,也可按x1,xn的大小為各隊排名次.例如,對于例1我們已求得合理的獎金向量為 xT=(0.7910,0.3020,0.5

9、321).按x的分量的大小為各隊排名次的結果是:T1, T3, T2. 這個結果與前面按得分向量v的分量的大小為各隊排名次的結果相一致的事實也說明我們以上的分析是正確的. 如果要對這兩個方法進行評優的話,應該說,本節的方法較優,因為此方法直接利用矩陣F即可求出結果,而用上節的方法,則還需要從F再計算矩陣A的額外工作量.兩個方法的比較 一個實例:下表為某個俱樂部的4支足球隊的比賽記錄,試用本節方法為這4支球隊排名次.T2T3T43:0, 1:1, 2:22:1, 2:3, 0:02:1, 3:1T11:43:1, 2:3T25:2, 4:2T3規定fij=0.6uij+0.4vij,uij為平均

10、場分;vij為平均進球分. 場分:勝2,平1,負0;進球分:進一球1分.例如,u21=(2+1+1)/(2+2+2)=2/3(每場總分是2), v21=(3+1+2)/(3+2+4)=2/3; f21=0.6 u21+0.4 v21=2/3.f12=1-f21=1-2/3=1/3.T2T3T43:0, 1:1, 2:22:1, 2:3, 0:02:1, 3:1T11:43:1, 2:3T25:2, 4:2T3規定fij=0.6uij+0.4vij,uij為平均場分;vij為平均進球分. 場分:勝2,平1,負0;進球分:進一球1分.再如,u31=(2+0+1)/(2+2+2)=1/2(每場總分是

11、2), v21=(2+2+0)/(3+5+0)=1/2; f31=0.6 u31+0.4v31=1/2.f13=1-f31=1-1/2=1/2.01/31/24/352/3023/2543/901/22/2508/6531/3547/9057/650U=(0.329,0.617,0.242,0.673)T,用它為各隊排名次得: T4,T2,T1,T3其次用Matlab算出矩陣F的對應于唯一正特征值1.2263的一個正特征向量是:首先請大家驗證矩陣F有如下數值: A=G12346579812543G=V,E,V=1,2,3,4,5,E=(1,2),(1,5),(2,3), (2,5),(3,4)

12、,(4,5)4.2 有限網絡的一些有趣問題計算機網,交通網,灌溉網,輸電網,電話網等都是常見的有限網絡.有限網絡的數學模型是有限無向圖.無向圖G是一個二重組:G=V,E,其中V是非空有限集合,它的元素稱為結點,E也是(非空)有限集合,它的元素稱為邊.圖G的邊e是一個結點二重組:e=(a,b),a,bV,稱e與a,b關聯,或a,b與e關聯,或a與b相鄰接.無向圖可用一些點和連接兩點間的連線(邊)的一個圖形來表示.本節將討論關于有限網絡的兩個有趣問題.問題 1背景:設有限網絡的各點僅取0或1兩種狀態;開始時刻每點都取0;以后每次從各點中任選一點令其改變狀態,同時也令與此點相鄰接的所有結點改變狀態.

13、例1:下列4點網絡前幾次狀態改變情況如下:00001110111111100000問題1:對任何網絡是否總能經有限次改變狀態后使網絡從全0狀態變為全1狀態? 問題1在一些情況下具有明確的實際意義.例如:如果所考慮的有限網絡代表照明網絡; 0,1 兩種狀態分別代表關燈,開燈;其中某盞燈改變狀態時與之相鄰接的每盞燈也同時改變其狀態. 則問題1的意義是:每一次選定一盞燈令它及與之相鄰的燈都改變狀態,能否經有限次改變后使此有限照明網絡從開始時全部關燈過渡到全部開燈?問題1的實際意義數學建模準備用(0,1)向量描述網絡狀態:第k次改變結束時,網絡狀態用向量x(k)=(x1k,xnk)T表示,其中,xik

14、=0或1表示第k次改變結束時網絡的第i個結點的狀態是0或1.(結點編號辦法：左上角結點編號為1,并按反時針順序把其余點依次標號為2,n.)例1: x(0)=(0,0,0,0)T,x(1)=(1,1,0,1)T, x(2)=(1,0,1,0)T,x(3)=(0,0,0,1)T, x(4)=(1,1,1,1)T. 關鍵是:尋求x(k)與x(k+1)的關系.如能得到從x(k)計算x(k+1)的公式,則問題的解決就有了辦法.作網絡的鄰接矩陣A=(aij),aij=0或1(A是對稱矩陣),由結點i與結點j鄰接或不鄰接而定;并令i,aii=1. 對例1得1101111001111011A =令 ei表示第

15、i個元素為1其余元素為0的n維列向量(n階單位矩陣第i列),則Aei表示A的第i列. 易見: 1423x(1)=(1,1,0,1)T=(0,0,0,0)T+(1,1,0,1)T =x(0)+Ae1 (上一次選擇了第1點); x(2)=(1,0,1,0)T=(1,1,0,1)T+(0,1,1,1)T =x(1)+Ae3 =x(0)+A(e1+e3) (上一次選擇了第3點,取按位加:1+1=0); 同樣可得x(3)=(0,0,0,1)T=x(2)+Ae4=x(0)+A(e1+e3+e4); x(4)=(1,1,1,1)T=x(3)+Ae2 =x(0)+A(e1+e3+e4+e2).一般地,x(k+

16、1)=x(k)+Aeu(即x(k)與A的第u列按位加),這里,u是第k次選定點的序數.證:Aeu為A的第u列,x(k)+Aeu的第i元是x(k)的與Aeu的第i元的按位加,注意當Aeu的第i元是0時,表示第i結點與選定的第u結點不相鄰,按我們的規則,第i點保持原狀態,即與第k次的狀態相同,這正與按位加法性質:”0加何數仍為何數”的結論相一致; 當Aeu的第i元是1時,表示第i結點與選定的第u結點相鄰(規定:每個結點都與自己相鄰),按我們的規則,第i點要改變狀態,即與第k次的狀態不同,這正與按位加法性質: 1+0=1,1+1=0 的結論相一致.結論結論:令e表示元素全為1的n維列向量.如果方程

17、Ax=e 在2元域 Z2 中有解x=ei1+ei2+eim,則依次選點i1,i2,im 讓網絡作m次改變狀態,可使網絡從全0狀態變為全1狀態.注:由于域Z2中加法是可交換的,故結果只與此m個點有關,而與選擇他們的順序無關,即按任意順序選擇此m個點,讓網絡改變狀態,其結果都可使網絡變為全1狀態.請你對例1作一個試驗.2元域定義為代數系統:Z2 =0,1,+,其中 加法定義為 0+1=1+0=1;1+1=0+0=0 乘法定義為 01=10=00=0;11=1易見:0,1關于上述加法,乘法構成交換群;滿足加法,乘法的分配律;并且非0元(1)有乘法逆元(1),所以,Z2是一個域.可以象實矩陣一樣,定義

18、Z2上的矩陣(元素取值于Z2的矩陣)及其加,乘法運算,只須注意兩點:1+1=0;運算結果是Z2上的矩陣.Z2上的線性方程組的理論與實線性方程組的理論完全類似.解法也差不多.這個只有兩個元素的有限域,在許多領域都有重要應用.算法目的:尋求方程Ax=e在2元域Z2中的解x.算法:為在域Z2中解線性方程組Ax=e,我們把增廣矩陣(Ae)用域Z2中初等行變換(僅兩類,即,交換兩行;和把一行加到另一行),化為(Ex)的形式,其中E為單位矩陣,則x即為所要求的解.依據:對任意可逆矩陣(例如,初等矩陣乘積)P方程Ax=e與方程PAx=Pe同解,特別,當PA=E時有,x=Pe.例111011111010111

19、110111(Ae) =交換上三角陣對角矩陣所需要的解為: x=(1,1,1,1)T=e1+e2+e3+e4.101110110000110000111000101001001010001111011011000011001111行加行加行加11011001100111101100思考題4-1:對開始為全0狀態的下列兩網絡,如何選一些結點,每次改變一點狀態,使網絡最后變為全1狀態?你能編一個(例如Matlab)程序求解有關方程組嗎?(1)(2)123465798110011111011011101001111110111(Ae) =1100110010000111010011110001001

20、10011011101001000000100001111110011011101001000000100000011100001010001001000000100000011交換上三角陣對角矩陣1100111101011100011111011鄰接矩陣:23451思考題#4-1(1)所需解為: x=(1,1,0,0,1)T=e1+e2+e5.01111111110000000000Ax=e在域Z2中恒有解證:由數域Z2上線性方程組一般理論知: Ax=e在域Z2上無解當且僅當在Z2中該方程組可經初等變換化為0=1的矛盾方程.因此,若此方程組無解,則把它的一些方程,不失一般性,可假設為前k個方

21、程加到一起會得到矛盾方程:0=1.于是有i=1kaij=0,j=1,n,1=1+1+1(共k個).因此,k是奇數,和 i=1kj=1kaij=0 (*)但由于A是對角元全為1的對稱矩陣和k是奇數,又推出(*)式左邊等于1的矛盾. Ax=e在域Z2上不可能無解.矩陣A是對稱的蘊涵其非0對角元的個數必為偶數.(*)式左邊等于A的前k行k列的非0元之和在Z2中的值.因為,在這里非0元就是1;對角元全為1;并且k是奇數.所以,(*)式左邊等于奇數個1在Z2中之和,此值必等于1.應用于問題1得出的結論結論: 對任意有限網絡,適當依次選點作有限次改變狀態,都可使網絡從全0狀態變為全1狀態.思考題4-2:對

22、任意有限網絡及任意初始狀態,適當依次選點作有限次改變狀態都可使網絡變為全1狀態嗎? (提示:以下列網絡為例,考慮你的答案.)從任意狀態變為全1狀態的討論由思考題4-2知:一般不能保證從任意狀態都能變為全1狀態.自然要提出問題:網絡滿足什麼條件,才能保證從任意初始狀態出發,都能經有限次按規則改變狀態后達到全1狀態?(等價于:從任意初始狀態開始變到任意指定的狀態結束)利用前面建立的數學模型不難找到我們需要的答案,其理論依據是下面的定理4.3.二元域Z2上線性方程組的一個定理定理.3 在二元域Z2上,若detA0,則線性方程組Ax=b對任意右端b恒有唯一解.證:設detA0,對線性方程組Ax=b的系

23、數矩陣施行Z2中行初等變換(僅兩類),任何時候都不會變出零列,否則,令變換矩陣的乘積為P便有det(PA)=0蘊涵detA=0的矛盾.因此,對增廣矩陣(Ab)在Z2中施行行初等變換,一定可化為(Ex)的形式(E為單位矩陣),從而,所唯一確定的x就是該方程組的唯一解.也可用二元數域Z2上的矩陣理論證明定理4.3,其要點如下: 按Z2上的矩陣理論,當detA0時,A在Z2上有逆矩陣A-1,滿足:A-1是Z2上的矩陣,并且A-1A=E.以A-1左乘線性方程組Ax=b的兩端即得 x=A-1b.這就證明了,Ax=b對任意右端b恒有唯一解A-1b.應用舉例例如,對于思考題4-1(1)中的網絡,我們知道它的

24、系數矩陣A,經Z2中行初等變換可以化為下列矩陣:由此可以斷定detA=10,從而按定理4.3,此網絡無論從任何指定狀態開始,經有限次改變狀態都可以變到全1狀態.12345問題 2背景:設有限網絡的各點僅取+或-兩種狀態;已知其開始時刻每點的狀態;以后按下列規則,定時改變網絡的狀態.規則:對于每點,若上一時刻其鄰點取+,取-的數目相同時維持原狀態;否則,將此點改變為其多數鄰點的狀態.+-+-+-+-+-變化規律: 例1趨于穩定,例2趨于交叉循環.自然要問:對任意網絡和任意初始狀態,是否都有這個變化規律,即:不是趨于穩定,便是趨于交叉循環?例1例2問題2:對任何網絡和任意初始狀態,是否總會趨于穩定或趨于交叉循環? 換句話說,是否總是成立:當k充分大時,第k+2時刻的狀態恒與第k時刻的狀態相同?試對你的結論給出嚴格證明.數學建模準備用(1,-1)向量描述網絡狀態:第 k 次改變 后,網絡狀態用(行)向量x(k)=(x1k,xnk)表示,其中,xik =1或-1表示第k次改變后網絡的第i個結點的狀態是”+”或”-”.例1:將該網絡的最上面一結點編號為1,并按反時針順序把其余結點標號為 2,3,4, 5,則 x(0)T=(1,-1,1,1,-1), x(1)T=(-1,1,1,1,1), x(2)T=(1,