第八章離散模型8.1層次分析模型8.2循環比賽名次y第1頁離散模型離散模型：差分方程（第7章）、整數規劃（第4章）、圖論、對策論、網絡流、……分析社會經濟系統有力工具只用到代數、集合及圖論（少許）知識第2頁8.1層次分析模型背景日常工作、生活中決議問題包括經濟、社會等方面原因作比較判斷時人主觀選擇起相當大作用，各原因主要性難以量化Saaty于1970年代提出層次分析法AHP(AnalyticHierarchyProcess)AHP——一個定性與定量相結合、系統化、層次化分析方法第3頁目標層O(選擇旅游地)P2黃山P1桂林P3北戴河準則層方案層C3居住C1景色C2費用C4飲食C5旅途一.層次分析法基本步驟例.選擇旅游地怎樣在3個目標地中按照景色、費用、居住條件等原因選擇.第4頁“選擇旅游地”思維過程歸納將決議問題分為3個層次：目標層O，準則層C，方案層P；每層有若干元素，各層元素間關系用相連直線表示。經過相互比較確定各準則對目標權重，及各方案對每一準則權重。將上述兩組權重進行綜合，確定各方案對目標權重。層次分析法將定性分析與定量分析結合起來完成以上步驟，給出決議問題定量結果。第5頁層次分析法基本步驟成對比較陣和權向量元素之間兩兩對比，對比采取相對尺度設要比較各準則C1,C2,…,Cn對目標O主要性A~成對比較陣A是正互反陣要由A確定C1,…,Cn對O權向量選擇旅游地第6頁成對比較不一致情況一致比較不一致允許不一致，但要確定不一致允許范圍考查完全一致情況成對比較陣和權向量第7頁成對比較完全一致情況滿足正互反陣A稱一致陣，如

A秩為1，A唯一非零特征根為n

A任一列向量是對應于n特征向量

A歸一化特征向量可作為權向量對于不一致(但在允許范圍內)成對比較陣A，提議用對應于最大特征根

特征向量作為權向量w，即一致陣性質成對比較陣和權向量第8頁2468比較尺度aij

Saaty等人提出1~9尺度——aij

取值1,2,…,9及其互反數1,1/2,…,1/9尺度13579相同稍強強顯著強絕對強aij=1,1/2,,…1/9主要性與上面相反心理學家認為成對比較原因不宜超出9個用1~3,1~5,…1~17,…,1p~9p

(p=2,3,4,5),d+0.1~d+0.9(d=1,2,3,4)等27種比較尺度對若干實例結構成對比較陣，算出權向量，與實際對比發覺，1~9尺度較優。便于定性到定量轉化：成對比較陣和權向量第9頁一致性檢驗對A確定不一致允許范圍已知：n階一致陣唯一非零特征根為n可證：n階正互反陣最大特征根

n,且

=n時為一致陣定義一致性指標:CI越大，不一致越嚴重RI000.580.901.121.241.321.411.451.491.51

n1234567891110為衡量CI大小，引入隨機一致性指標RI——隨機模擬得到aij,形成A，計算CI即得RI。定義一致性比率CR=CI/RI當CR<0.1時，經過一致性檢驗Saaty結果以下第10頁“選擇旅游地”中準則層對目標權向量及一致性檢驗準則層對目標成對比較陣最大特征根

=5.073權向量(特征向量)w=(0.263,0.475,0.055,0.090,0.110)T一致性指標隨機一致性指標RI=1.12(查表)一致性比率CR=0.018/1.12=0.016<0.1經過一致性檢驗第11頁組合權向量記第2層（準則）對第1層（目標）權向量為一樣求第3層(方案)對第2層每一元素(準則)權向量方案層對C1(景色)成對比較陣方案層對C2(費用)成對比較陣…Cn…Bn最大特征根

1

2

…

n

權向量w1(3)w2(3)…

wn(3)第12頁第3層對第2層計算結果k10.5950.2770.1293.0050.0030.00100.00503.0020.6820.2360.082230.1420.4290.42933.0090.1750.1930.633430.6680.1660.1665組合權向量RI=0.58(n=3),

CIk

均可經過一致性檢驗w(2)

0.2630.4750.0550.0900.110方案P1對目標組合權重為0.5950.263+…=0.300方案層對目標組合權向量為(0.300,0.246,0.456)T第13頁組合權向量第1層O第2層C1,…Cn第3層P1,…Pm第2層對第1層權向量第3層對第2層各元素權向量結構矩陣則第3層對第1層組合權向量第s層對第1層組合權向量其中W(p)是由第p層對第p-1層權向量組成矩陣第14頁層次分析法基本步驟1）建立層次分析結構模型深入分析實際問題，將相關原因自上而下分層（目標—準則或指標—方案或對象），上層受下層影響，而層內各原因基本上相對獨立。2）結構成對比較陣用成對比較法和1~9尺度，結構各層對上一層每一原因成對比較陣。3）計算權向量并作一致性檢驗對每一成對比較陣計算最大特征根和特征向量，作一致性檢驗，若經過，則特征向量為權向量。4）計算組合權向量（作組合一致性檢驗*）組合權向量可作為決議定量依據。第15頁二.層次分析法廣泛應用應用領域：經濟計劃和管理，能源政策和分配，人才選拔和評價，生產決議，交通運輸，科研選題，產業結構，教育，醫療，環境，軍事等。處理問題類型：決議、評價、分析、預測等。建立層次分析結構模型是關鍵一步，要有主要決議層參加。結構成對比較陣是數量依據，應由經驗豐富、判斷力強教授給出。第16頁國家綜合實力國民收入軍事力量科技水平社會穩定對外貿易美、俄、中、日、德等大國工作選擇貢獻收入發展聲譽關系位置供選擇崗位例1國家實力分析例2工作選擇第17頁過河效益A經濟效益B1社會效益B2環境效益B3節約時間C1收入C2岸間商業C3當地商業C4建筑就業C5安全可靠C6交往溝通C7自豪感C8舒適C9進出方便C10美化C11橋梁D1隧道D2渡船D3（1）過河效益層次結構例3

橫渡江河、海峽方案抉擇第18頁過河代價A經濟代價

B1環境代價B3社會代價B2投入資金C1操作維護C2沖擊渡船業C3沖擊生活方式C4交通擁擠C5居民搬遷C6汽車排放物C7對水污染C8對生態破壞C9橋梁D1隧道D2渡船D2（2）過河代價層次結構例3

橫渡江河、海峽方案抉擇第19頁待評價科技結果直接經濟效益C11間接經濟效益C12社會效益C13學識水平C21學術創新C22技術水平C23技術創新C24效益C1水平C2規模C3科技結果評價例4科技結果綜合評價第20頁三.層次分析法若干問題正互反陣最大特征根是否為正數？特征向量是否為正向量？一致性指標能否反應正互反陣靠近一致陣程度？怎樣簡化計算正互反陣最大特征根和特征向量？為何用特征向量作為權向量？當層次結構不完全或成對比較陣有空缺時怎樣用層次分析法？第21頁1.正互反陣最大特征根和特征向量性質定理1正矩陣A最大特征根

是正單根，對應正特征向量w，且定理2n階正互反陣A最大特征根

n,

=n是A為一致陣充要條件。正互反陣最大特征根是正數，特征向量是正向量。一致性指標定義合理第22頁2.正互反陣最大特征根和特征向量簡化計算準確計算復雜和無須要簡化計算思緒——一致陣任一列向量都是特征向量，一致性尚好正互反陣列向量都應近似特征向量，可取其某種意義下平均。和法——取列向量算術平均列向量歸一化算術平均準確結果:w=(0.588,0.322,0.090)T,=3.010第23頁根法——取列向量幾何平均冪法——迭代算法1）任取初始向量w(0),k:=0，設置精度

2)計算3）歸一化5)計算簡化計算4）若，停頓；不然，k:=k+1,轉2第24頁3.特征向量作為權向量——成對比較多步累積效應問題一致陣A,權向量w=(w1,…wn)T,aij=wi/wjA不一致,應選權向量w使wi/wj與

aij相差盡可能小（對全部i,j)。用擬合方法確定w非線性最小二乘線性化——對數最小二乘結果與根法相同第25頁按不一樣準則確定權向量不一樣，特征向量有什么優點。成對比較Ci:Cj(直接比較）aij~1步強度aisasj~Ci經過Cs與Cj比較aij(2)

~2步強度更能反應Ci對Cj強度多步累積效應表達多步累積效應定理1特征向量表達多步累積效應當k足夠大,Ak第i行元素反應Ci權重求Ak行和第26頁4.不完全層次結構中組合權向量計算完全層次結構：上層每一元素與下層全部元素相關聯不完全層次結構設第2層對第1層權向量w(2)=(w1(2),w2(2))T已定第3層對第2層權向量w1(3)=(w11(3),w12(3),w13(3),0)Tw2(3)=(0,0,w23(3),w24(3)T已得討論由w(2),W(3)=(w1(3),

w2(3))計算第3層對第1層權向量w(3）方法貢獻O教學C1科研C2P2P1P3P4例:評價教師貢獻層次結構P1,P2只作教學,P4只作科研,P3兼作教學、科研。C1,C2支配元素數目不等第27頁不考慮支配元素數目不等影響仍用計算支配元素越多權重越大用支配元素數目n1,n2對w(2)加權修正若C1,C2主要性相同,w(2)=(1/2,1/2)T,

P1~P4能力相同,w1(3)=(1/3,1/3,1/3,0)T,w2(3)=(0,0,1/2,1/2)T公正評價應為：P1:P2:P3:P4=1:1:2:1再用計算w(3)=(1/6,1/6,5/12,1/4)Tw(3)=(1/5,1/5,2/5,1/5)T支配元素越多權重越小教學、科研任務由上級安排教學、科研靠個人主動性考查一個特例：第28頁5.殘缺成對比較陣處理mi~A第i行中

個數

為殘缺元素輔助矩陣第29頁6.更復雜層次結構遞階層次結構：層內各元素獨立，無相互影響和支配；層間自上而下、逐層傳遞，無反饋和循環。

更復雜層次結構：層內各元素間存在相互影響或支配；層間存在反饋或循環。制動底盤車輪方向盤發動機減震裝置剎車轉向運行加速性能汽車行駛性能汽車1汽車2汽車n……例第30頁層次分析法優點

系統性——將對象視作系統，按照分解、比較、判斷、綜合思維方式進行決議——系統分析（與機理分析、測試分析并列）；

實用性——定性與定量相結合，能處理傳統優化方法不能處理問題；

簡練性——計算簡便，結果明確，便于決議者直接了解和掌握。層次分析法局限

囿舊——只能從原方案中選優，不能產生新方案；

粗略——定性化為定量，結果粗糙；主觀——主觀原因作用大，結果可能難以服人。第31頁層次分析法中新元素導入保序條件當決議環境發生改變時，層次分析法中遞階層次結構中元素有可能增加或降低。問題：假定原有元素兩兩比較判斷不變，因為新元素導入或原有元素降低，單一準則下原有元素排序權值百分比是否改變？它們排序是否改變？在何種條件下可保持排序不變？強保序性：排序權值百分比關系不變弱保序性（保序）：排序保持不變第32頁例：設有3個方案，它們判斷矩陣和排序權向量為增加新方案，得到新判斷矩陣及排序權向量新方案引入，使得方案次序發生了逆轉。第33頁若將判斷矩陣A改為此時方案排序是原來相同。第34頁結論：第35頁8.2循環比賽名次

n支球隊循環賽，每場比賽只計勝敗，沒有平局。依據比賽結果排出各隊名次方法1：尋找按箭頭方向經過全部頂點路徑。123456312456146325方法2：計算得分：1隊勝4場，2,3隊各勝3場，4,5隊各勝2場，6隊勝1場。無法排名2,3隊，4,5隊無法排名6支球隊比賽結果……第36頁3隊打敗了得分較高球隊（即強隊）。考慮二級得分向量，即計算被它們打敗球隊得分之和。例：3隊打敗了1，2，4隊，期得分總和為：4+3+2=9表明：3隊是冠軍，1隊是亞軍，。。。。，繼續這個想法考慮三級得分向量第37頁以這類推有各隊名次排列有所波動。第38頁

當競賽圖是雙向連通而且最少有四個頂點時，上述向量會收斂于一個固定向量，這就給出了競賽中排列名次一個方法。競賽圖：有向圖中每對頂點之間都有一條邊相連。雙向連通：對于每一對頂點，存在兩條有向路徑（每條路徑由一條或幾條邊組成），使兩頂點能夠相互連通，這種有向圖稱為雙向連通。第39頁雙向連通競賽圖G=(V,E)名次排序鄰接矩陣得分向量第40頁對于n(>3)個頂點雙向連通競賽圖，存在正整數r，使鄰接矩陣A滿足Ar>0，A稱素陣素陣A最大特征根為正單根

，對應正特征向量S，且用S排名第41頁1234566支球隊比賽結果排名次序為{1，3，2，5，4，6}第42頁普通排名問題算法：（1）結構有向競賽圖G=(V,E)：將每個參賽者作為G一個頂點，即（2）將G全部雙向連通分圖排序為第43頁（3）對G最少有四個頂點每一個雙向連通分圖，求其鄰接矩陣最大特征值所對應特征向量。按照特征向量分量大小，依次定出該分圖對應參賽者名次。對G僅有三個頂點雙向連通分圖，其對應參賽者名次并列。第44頁例：V1V3V5V2V4連通子圖：V4V1,V2,V3,V5第45頁用競賽圖處理足球隊排名問題：排名問題是依據各隊相互比賽成績排出一個盡可能反應各隊真正實力一個次序。為此，我們提出以下一些基本標準：（1）一隊排在另一隊之前，不能只考慮這兩隊戰績，而應充分考慮這兩隊全部比賽場次成績。（2）要充分考慮對手強弱原因。（3）假如兩隊之間因為種種原因，沒有比賽或者雙方打成平局，就由這兩隊與其它隊比賽戰績來確定它們強弱。第46頁依據上述標準，據比賽成績表，結構競賽圖以下：第47頁依據建邊情況，可建立矩陣第48頁第49頁第50頁(4)參考上述方法得到鄰接陣，得到競賽圖G.按照上述算法，經步驟（1）得到（5）針對競賽圖G，按照前述排名方