數(shù)學建模 層次分析法競賽圖_第1頁
數(shù)學建模 層次分析法競賽圖_第2頁
數(shù)學建模 層次分析法競賽圖_第3頁
數(shù)學建模 層次分析法競賽圖_第4頁
數(shù)學建模 層次分析法競賽圖_第5頁
已閱讀5頁,還剩51頁未讀 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

數(shù)學建模層次分析法競賽圖第一頁,共五十六頁,編輯于2023年,星期三離散模型離散模型:差分方程(第7章)、整數(shù)規(guī)劃(第4章)、圖論、對策論、網(wǎng)絡(luò)流、……分析社會經(jīng)濟系統(tǒng)的有力工具只用到代數(shù)、集合及圖論(少許)的知識第二頁,共五十六頁,編輯于2023年,星期三8.1層次分析模型背景日常工作、生活中的決策問題涉及經(jīng)濟、社會等方面的因素作比較判斷時人的主觀選擇起相當大的作用,各因素的重要性難以量化Saaty于1970年代提出層次分析法AHP(AnalyticHierarchyProcess)AHP——一種定性與定量相結(jié)合的、系統(tǒng)化、層次化的分析方法第三頁,共五十六頁,編輯于2023年,星期三目標層O(選擇旅游地)P2黃山P1桂林P3北戴河準則層方案層C3居住C1景色C2費用C4飲食C5旅途一.層次分析法的基本步驟例.選擇旅游地如何在3個目的地中按照景色、費用、居住條件等因素選擇.第四頁,共五十六頁,編輯于2023年,星期三“選擇旅游地”思維過程的歸納將決策問題分為3個層次:目標層O,準則層C,方案層P;每層有若干元素,各層元素間的關(guān)系用相連的直線表示。通過相互比較確定各準則對目標的權(quán)重,及各方案對每一準則的權(quán)重。將上述兩組權(quán)重進行綜合,確定各方案對目標的權(quán)重。層次分析法將定性分析與定量分析結(jié)合起來完成以上步驟,給出決策問題的定量結(jié)果。第五頁,共五十六頁,編輯于2023年,星期三層次分析法的基本步驟成對比較陣和權(quán)向量元素之間兩兩對比,對比采用相對尺度設(shè)要比較各準則C1,C2,…,Cn對目標O的重要性A~成對比較陣A是正互反陣要由A確定C1,…,Cn對O的權(quán)向量選擇旅游地第六頁,共五十六頁,編輯于2023年,星期三成對比較的不一致情況一致比較不一致允許不一致,但要確定不一致的允許范圍考察完全一致的情況成對比較陣和權(quán)向量第七頁,共五十六頁,編輯于2023年,星期三成對比較完全一致的情況滿足的正互反陣A稱一致陣,如

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

A的任一列向量是對應(yīng)于n的特征向量

A的歸一化特征向量可作為權(quán)向量對于不一致(但在允許范圍內(nèi))的成對比較陣A,建議用對應(yīng)于最大特征根的特征向量作為權(quán)向量w,即一致陣性質(zhì)成對比較陣和權(quán)向量第八頁,共五十六頁,編輯于2023年,星期三2468比較尺度aij

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

取值1,2,…,9及其互反數(shù)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種比較尺度對若干實例構(gòu)造成對比較陣,算出權(quán)向量,與實際對比發(fā)現(xiàn),1~9尺度較優(yōu)。便于定性到定量的轉(zhuǎn)化:成對比較陣和權(quán)向量第九頁,共五十六頁,編輯于2023年,星期三一致性檢驗對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的結(jié)果如下第十頁,共五十六頁,編輯于2023年,星期三“選擇旅游地”中準則層對目標的權(quán)向量及一致性檢驗準則層對目標的成對比較陣最大特征根=5.073權(quán)向量(特征向量)w=(0.263,0.475,0.055,0.090,0.110)T一致性指標隨機一致性指標RI=1.12(查表)一致性比率CR=0.018/1.12=0.016<0.1通過一致性檢驗第十一頁,共五十六頁,編輯于2023年,星期三組合權(quán)向量記第2層(準則)對第1層(目標)的權(quán)向量為同樣求第3層(方案)對第2層每一元素(準則)的權(quán)向量方案層對C1(景色)的成對比較陣方案層對C2(費用)的成對比較陣…Cn…Bn最大特征根1

2

n

權(quán)向量w1(3)w2(3)…

wn(3)第十二頁,共五十六頁,編輯于2023年,星期三第3層對第2層的計算結(jié)果k10.5950.2770.1293.0050.0030.00100.00503.0020.6820.2360.082230.1420.4290.42933.0090.1750.1930.633430.6680.1660.1665組合權(quán)向量RI=0.58(n=3),

CIk

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

0.2630.4750.0550.0900.110方案P1對目標的組合權(quán)重為0.5950.263+…=0.300方案層對目標的組合權(quán)向量為(0.300,0.246,0.456)T第十三頁,共五十六頁,編輯于2023年,星期三組合權(quán)向量第1層O第2層C1,…Cn第3層P1,…Pm第2層對第1層的權(quán)向量第3層對第2層各元素的權(quán)向量構(gòu)造矩陣則第3層對第1層的組合權(quán)向量第s層對第1層的組合權(quán)向量其中W(p)是由第p層對第p-1層權(quán)向量組成的矩陣第十四頁,共五十六頁,編輯于2023年,星期三層次分析法的基本步驟1)建立層次分析結(jié)構(gòu)模型深入分析實際問題,將有關(guān)因素自上而下分層(目標—準則或指標—方案或?qū)ο螅蠈邮芟聦佑绊?,而層?nèi)各因素基本上相對獨立。2)構(gòu)造成對比較陣用成對比較法和1~9尺度,構(gòu)造各層對上一層每一因素的成對比較陣。3)計算權(quán)向量并作一致性檢驗對每一成對比較陣計算最大特征根和特征向量,作一致性檢驗,若通過,則特征向量為權(quán)向量。4)計算組合權(quán)向量(作組合一致性檢驗*)組合權(quán)向量可作為決策的定量依據(jù)。第十五頁,共五十六頁,編輯于2023年,星期三二.層次分析法的廣泛應(yīng)用應(yīng)用領(lǐng)域:經(jīng)濟計劃和管理,能源政策和分配,人才選拔和評價,生產(chǎn)決策,交通運輸,科研選題,產(chǎn)業(yè)結(jié)構(gòu),教育,醫(yī)療,環(huán)境,軍事等。處理問題類型:決策、評價、分析、預(yù)測等。建立層次分析結(jié)構(gòu)模型是關(guān)鍵一步,要有主要決策層參與。構(gòu)造成對比較陣是數(shù)量依據(jù),應(yīng)由經(jīng)驗豐富、判斷力強的專家給出。第十六頁,共五十六頁,編輯于2023年,星期三國家綜合實力國民收入軍事力量科技水平社會穩(wěn)定對外貿(mào)易美、俄、中、日、德等大國工作選擇貢獻收入發(fā)展聲譽關(guān)系位置供選擇的崗位例1國家實力分析例2工作選擇第十七頁,共五十六頁,編輯于2023年,星期三過河的效益A經(jīng)濟效益B1社會效益B2環(huán)境效益B3節(jié)省時間C1收入C2岸間商業(yè)C3當?shù)厣虡I(yè)C4建筑就業(yè)C5安全可靠C6交往溝通C7自豪感C8舒適C9進出方便C10美化C11橋梁D1隧道D2渡船D3(1)過河效益層次結(jié)構(gòu)例3橫渡江河、海峽方案的抉擇第十八頁,共五十六頁,編輯于2023年,星期三過河的代價A經(jīng)濟代價B1環(huán)境代價B3社會代價B2投入資金C1操作維護C2沖擊渡船業(yè)C3沖擊生活方式C4交通擁擠C5居民搬遷C6汽車排放物C7對水的污染C8對生態(tài)的破壞C9橋梁D1隧道D2渡船D2(2)過河代價層次結(jié)構(gòu)例3橫渡江河、海峽方案的抉擇第十九頁,共五十六頁,編輯于2023年,星期三待評價的科技成果直接經(jīng)濟效益C11間接經(jīng)濟效益C12社會效益C13學識水平C21學術(shù)創(chuàng)新C22技術(shù)水平C23技術(shù)創(chuàng)新C24效益C1水平C2規(guī)模C3科技成果評價例4科技成果的綜合評價第二十頁,共五十六頁,編輯于2023年,星期三三.層次分析法的若干問題正互反陣的最大特征根是否為正數(shù)?特征向量是否為正向量?一致性指標能否反映正互反陣接近一致陣的程度?怎樣簡化計算正互反陣的最大特征根和特征向量?為什么用特征向量作為權(quán)向量?當層次結(jié)構(gòu)不完全或成對比較陣有空缺時怎樣用層次分析法?第二十一頁,共五十六頁,編輯于2023年,星期三1.正互反陣的最大特征根和特征向量的性質(zhì)定理1正矩陣A的最大特征根是正單根,對應(yīng)正特征向量w,且定理2n階正互反陣A的最大特征根

n,=n是A為一致陣的充要條件。正互反陣的最大特征根是正數(shù),特征向量是正向量。一致性指標定義合理第二十二頁,共五十六頁,編輯于2023年,星期三2.正互反陣最大特征根和特征向量的簡化計算精確計算的復(fù)雜和不必要簡化計算的思路——一致陣的任一列向量都是特征向量,一致性尚好的正互反陣的列向量都應(yīng)近似特征向量,可取其某種意義下的平均。和法——取列向量的算術(shù)平均列向量歸一化算術(shù)平均精確結(jié)果:w=(0.588,0.322,0.090)T,=3.010第二十三頁,共五十六頁,編輯于2023年,星期三根法——取列向量的幾何平均冪法——迭代算法1)任取初始向量w(0),k:=0,設(shè)置精度2)計算3)歸一化5)計算簡化計算4)若,停止;否則,k:=k+1,轉(zhuǎn)2第二十四頁,共五十六頁,編輯于2023年,星期三3.特征向量作為權(quán)向量——成對比較的多步累積效應(yīng)問題一致陣A,權(quán)向量w=(w1,…wn)T,aij=wi/wjA不一致,應(yīng)選權(quán)向量w使wi/wj與

aij相差盡量小(對所有i,j)。用擬合方法確定w非線性最小二乘線性化——對數(shù)最小二乘結(jié)果與根法相同第二十五頁,共五十六頁,編輯于2023年,星期三按不同準則確定的權(quán)向量不同,特征向量有什么優(yōu)點。成對比較Ci:Cj(直接比較)aij~1步強度aisasj~Ci通過Cs與Cj的比較aij(2)

~2步強度更能反映Ci對Cj的強度多步累積效應(yīng)體現(xiàn)多步累積效應(yīng)定理1特征向量體現(xiàn)多步累積效應(yīng)當k足夠大,Ak第i行元素反映Ci的權(quán)重求Ak的行和第二十六頁,共五十六頁,編輯于2023年,星期三4.不完全層次結(jié)構(gòu)中組合權(quán)向量的計算完全層次結(jié)構(gòu):上層每一元素與下層所有元素相關(guān)聯(lián)不完全層次結(jié)構(gòu)設(shè)第2層對第1層權(quán)向量w(2)=(w1(2),w2(2))T已定第3層對第2層權(quán)向量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層權(quán)向量w(3)的方法貢獻O教學C1科研C2P2P1P3P4例:評價教師貢獻的層次結(jié)構(gòu)P1,P2只作教學,P4只作科研,P3兼作教學、科研。C1,C2支配元素的數(shù)目不等第二十七頁,共五十六頁,編輯于2023年,星期三不考慮支配元素數(shù)目不等的影響仍用計算支配元素越多權(quán)重越大用支配元素數(shù)目n1,n2對w(2)加權(quán)修正若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公正的評價應(yīng)為: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支配元素越多權(quán)重越小教學、科研任務(wù)由上級安排教學、科研靠個人積極性考察一個特例:第二十八頁,共五十六頁,編輯于2023年,星期三5.殘缺成對比較陣的處理mi~A第i行中的個數(shù)為殘缺元素輔助矩陣第二十九頁,共五十六頁,編輯于2023年,星期三6.更復(fù)雜的層次結(jié)構(gòu)遞階層次結(jié)構(gòu):層內(nèi)各元素獨立,無相互影響和支配;層間自上而下、逐層傳遞,無反饋和循環(huán)。

更復(fù)雜的層次結(jié)構(gòu):層內(nèi)各元素間存在相互影響或支配;層間存在反饋或循環(huán)。制動底盤車輪方向盤發(fā)動機減震裝置剎車轉(zhuǎn)向運行加速性能汽車行駛性能汽車1汽車2汽車n……例第三十頁,共五十六頁,編輯于2023年,星期三層次分析法的優(yōu)點

系統(tǒng)性——將對象視作系統(tǒng),按照分解、比較、判斷、綜合的思維方式進行決策——系統(tǒng)分析(與機理分析、測試分析并列);

實用性——定性與定量相結(jié)合,能處理傳統(tǒng)的優(yōu)化方法不能解決的問題;

簡潔性——計算簡便,結(jié)果明確,便于決策者直接了解和掌握。層次分析法的局限

囿舊——只能從原方案中選優(yōu),不能產(chǎn)生新方案;

粗略——定性化為定量,結(jié)果粗糙;主觀——主觀因素作用大,結(jié)果可能難以服人。第三十一頁,共五十六頁,編輯于2023年,星期三層次分析法中新元素導入的保序條件當決策環(huán)境發(fā)生變化時,層次分析法中的遞階層次結(jié)構(gòu)中的元素有可能增加或減少。問題:假定原有元素的兩兩比較判斷不變,由于新元素的導入或原有元素的減少,單一準則下原有元素的排序權(quán)值的比例是否改變?它們的排序是否改變?在何種條件下可保持排序不變?強保序性:排序權(quán)值的比例關(guān)系不變?nèi)醣P蛐裕ūP颍号判虮3植蛔兊谌?,共五十六頁,編輯?023年,星期三例:設(shè)有3個方案,它們的判斷矩陣和排序權(quán)向量為增加新的方案,得到新的判斷矩陣及排序權(quán)向量新方案的引入,使得方案的順序發(fā)生了逆轉(zhuǎn)。第三十三頁,共五十六頁,編輯于2023年,星期三若將判斷矩陣A改為此時方案的排序是原來相同。第三十四頁,共五十六頁,編輯于2023年,星期三結(jié)論:第三十五頁,共五十六頁,編輯于2023年,星期三8.2循環(huán)比賽的名次

n支球隊循環(huán)賽,每場比賽只計勝負,沒有平局。根據(jù)比賽結(jié)果排出各隊名次方法1:尋找按箭頭方向通過全部頂點的路徑。123456312456146325方法2:計算得分:1隊勝4場,2,3隊各勝3場,4,5隊各勝2場,6隊勝1場。無法排名2,3隊,4,5隊無法排名6支球隊比賽結(jié)果……第三十六頁,共五十六頁,編輯于2023年,星期三3隊打敗了得分較高的球隊(即強隊)??紤]二級得分向量,即計算被它們打敗球隊的的得分之和。例:3隊打敗了1,2,4隊,期得分總和為:4+3+2=9表明:3隊是冠軍,1隊是亞軍,。。。。,繼續(xù)這個想法考慮三級得分向量第三十七頁,共五十六頁,編輯于2023年,星期三以此類推有各隊的名次排列有所波動。第三十八頁,共五十六頁,編輯于2023年,星期三

當競賽圖是雙向連通并且至少有四個頂點時,上述向量會收斂于一個固定的向量,這就給出了競賽中排列名次的一種方法。競賽圖:有向圖中每對頂點之間都有一條邊相連。雙向連通:對于每一對頂點,存在兩條有向路徑(每條路徑由一條或幾條邊組成),使兩頂點可以相互連通,這種有向圖稱為雙向連通的。第三十九頁,共五十六頁,編輯于2023年,星期三雙向連通競賽圖G=(V,E)的名次排序鄰接矩陣得分向量第四十頁,共五十六頁,編輯于2023年,星期三對于n(>3)個頂點的雙向連通競賽圖,存在正整數(shù)r,使鄰接矩陣A滿足Ar>0,A稱素陣素陣A的最大特征根為正單根,對應(yīng)正特征向量S,且用S排名第四十一頁,共五十六頁,編輯于2023年,星期三1234566支球隊比賽結(jié)果排名次序為{1,3,2,5,4,6}第四十二頁,共五十六頁,編輯于2023年,星期三一般排名問題的算法:(1)構(gòu)造有向競賽圖G=(V,E):將每個參賽者作為G的一個頂點,即(2)將G的所有雙向連通分圖排序為第四十三頁,共五十六頁,編輯于2023年,星期三(3)對G的至少有四個頂點的每一個雙向連通分圖,求其鄰接矩陣的最大特征值所對應(yīng)的特征向量。按照特征向量分量的大小,依次定出該分圖對應(yīng)參賽者的名次。對G的僅有三個頂點的雙向連通分圖,其對應(yīng)參賽者的名次并列。第四十四頁,共五十六頁,編輯于2023年,星期三例:V1V3V5V2V4連通子圖:V4V1,V2,V3,V5第四十五頁,共五十六頁,編輯于2023年,星期三用競賽圖解決足球隊排名問題:排名問題是根據(jù)各隊相互比賽的成績排出一個盡可能反映各隊真正實力的一個順序。為此,我們提出如下的一些基本原則:(1)一隊排在另一隊之前,不能只考慮這兩隊的戰(zhàn)績,而應(yīng)充分考慮這兩隊所有比賽場次的成績。(2)要充分考慮對手的強弱因素。(3)如果兩隊之間由于種種原因,沒有比賽或者雙方打成平局,就由這兩隊與其他隊比賽的戰(zhàn)績來確定它們的強弱。第四十六頁,共五十六頁,編輯于2023年,星期三根據(jù)上述原則,據(jù)比賽成績表,構(gòu)造競賽圖如下:第四十七頁,共五十六頁,編輯于2023年,星期三根據(jù)建邊情況,可建立矩陣第四十八頁,共五十六頁,編輯于2023年,星期三第四十九頁,共五十六頁,編輯于2023年,星期三第五十頁,共五十六頁,編輯于2023年,星期三(4)參照上述方法得到的鄰接陣,得到競賽圖G.按照上述算法,經(jīng)步驟(1)得到(5)針對競賽圖G,按照前述的排名方法進行排序。第五十一頁,共五十六頁,編輯于2023年,星期三T1T2T3T4T5T6T7T8T9T10T11T12T1

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論