數(shù)學(xué)建模 層次分析法,競(jìng)賽圖

1、第八章 離散模型8.1 層次分析模型8.2 循環(huán)比賽的名次y離散模型 離散模型：差分方程（第7章）、整數(shù)規(guī)劃（第4章）、圖論、對(duì)策論、網(wǎng)絡(luò)流、 分析社會(huì)經(jīng)濟(jì)系統(tǒng)的有力工具 只用到代數(shù)、集合及圖論（少許）的知識(shí)8.1 層次分析模型背景 日常工作、生活中的決策問(wèn)題 涉及經(jīng)濟(jì)、社會(huì)等方面的因素 作比較判斷時(shí)人的主觀選擇起相當(dāng)大的作用，各因素的重要性難以量化 Saaty于1970年代提出層次分析法 AHP (Analytic Hierarchy Process) AHP一種定性與定量相結(jié)合的、系統(tǒng)化、層次化的分析方法目標(biāo)層O(選擇旅游地)P2黃山P1桂林P3北戴河準(zhǔn)則層方案層C3居住C1景色C2費(fèi)用C

2、4飲食C5旅途一. 層次分析法的基本步驟例. 選擇旅游地如何在3個(gè)目的地中按照景色、費(fèi)用、居住條件等因素選擇.“選擇旅游地”思維過(guò)程的歸納 將決策問(wèn)題分為3個(gè)層次：目標(biāo)層O，準(zhǔn)則層C，方案層P；每層有若干元素， 各層元素間的關(guān)系用相連的直線表示。 通過(guò)相互比較確定各準(zhǔn)則對(duì)目標(biāo)的權(quán)重，及各方案對(duì)每一準(zhǔn)則的權(quán)重。 將上述兩組權(quán)重進(jìn)行綜合，確定各方案對(duì)目標(biāo)的權(quán)重。層次分析法將定性分析與定量分析結(jié)合起來(lái)完成以上步驟，給出決策問(wèn)題的定量結(jié)果。層次分析法的基本步驟成對(duì)比較陣和權(quán)向量 元素之間兩兩對(duì)比，對(duì)比采用相對(duì)尺度 設(shè)要比較各準(zhǔn)則C1,C2, , Cn對(duì)目標(biāo)O的重要性A成對(duì)比較陣A是正互反陣要由A確定C

3、1, , Cn對(duì)O的權(quán)向量選擇旅游地成對(duì)比較的不一致情況一致比較不一致允許不一致，但要確定不一致的允許范圍考察完全一致的情況成對(duì)比較陣和權(quán)向量成對(duì)比較完全一致的情況滿足的正互反陣A稱一致陣，如 A的秩為1，A的唯一非零特征根為n A的任一列向量是對(duì)應(yīng)于n 的特征向量 A的歸一化特征向量可作為權(quán)向量對(duì)于不一致(但在允許范圍內(nèi))的成對(duì)比較陣A，建議用對(duì)應(yīng)于最大特征根的特征向量作為權(quán)向量w ，即一致陣性質(zhì)成對(duì)比較陣和權(quán)向量2 4 6 8比較尺度aij Saaty等人提出19尺度aij 取值1,2, , 9及其互反數(shù)1,1/2, , 1/9尺度 1 3 5 7 9 相同 稍強(qiáng) 強(qiáng) 明顯強(qiáng) 絕對(duì)強(qiáng)aij

4、 = 1,1/2, ,1/9的重要性與上面相反 心理學(xué)家認(rèn)為成對(duì)比較的因素不宜超過(guò)9個(gè) 用13,15,117,1p9p (p=2,3,4,5), d+0.1d+0.9 (d=1,2,3,4)等27種比較尺度對(duì)若干實(shí)例構(gòu)造成對(duì)比較陣，算出權(quán)向量，與實(shí)際對(duì)比發(fā)現(xiàn)， 19尺度較優(yōu)。 便于定性到定量的轉(zhuǎn)化：成對(duì)比較陣和權(quán)向量一致性檢驗(yàn)對(duì)A確定不一致的允許范圍已知：n 階一致陣的唯一非零特征根為n可證：n 階正互反陣最大特征根 n, 且 =n時(shí)為一致陣定義一致性指標(biāo):CI 越大，不一致越嚴(yán)重RI000.580.901.121.241.321.411.451.491.51 n1234567891110為衡

5、量CI 的大小，引入隨機(jī)一致性指標(biāo) RI隨機(jī)模擬得到aij , 形成A，計(jì)算CI 即得RI。定義一致性比率 CR = CI/RI 當(dāng)CR0.1時(shí)，通過(guò)一致性檢驗(yàn)Saaty的結(jié)果如下“選擇旅游地”中準(zhǔn)則層對(duì)目標(biāo)的權(quán)向量及一致性檢驗(yàn)準(zhǔn)則層對(duì)目標(biāo)的成對(duì)比較陣最大特征根=5.073權(quán)向量(特征向量)w =(0.263,0.475,0.055,0.090,0.110)T一致性指標(biāo)隨機(jī)一致性指標(biāo) RI=1.12 (查表)一致性比率CR=0.018/1.12=0.0163)個(gè)頂點(diǎn)的雙向連通競(jìng)賽圖，存在正整數(shù)r，使鄰接矩陣A 滿足Ar 0，A稱素陣 素陣A的最大特征根為正單根，對(duì)應(yīng)正特征向量S，且用S排名12

6、34566支球隊(duì)比賽結(jié)果排名次序?yàn)?，3， 2，5，4，6一般排名問(wèn)題的算法：（1）構(gòu)造有向競(jìng)賽圖G=(V,E)：將每個(gè)參賽者作為G的一個(gè)頂點(diǎn)，即（2）將G的所有雙向連通分圖排序?yàn)椋?）對(duì)G的至少有四個(gè)頂點(diǎn)的每一個(gè)雙向連通分圖，求其鄰接矩陣的最大特征值所對(duì)應(yīng)的特征向量。按照特征向量分量的大小，依次定出該分圖對(duì)應(yīng)參賽者的名次。對(duì)G的僅有三個(gè)頂點(diǎn)的雙向連通分圖，其對(duì)應(yīng)參賽者的名次并列。例：V1V3V5V2V4連通子圖：V4V1,V2,V3,V5用競(jìng)賽圖解決足球隊(duì)排名問(wèn)題： 排名問(wèn)題是根據(jù)各隊(duì)相互比賽的成績(jī)排出一個(gè)盡可能反映各隊(duì)真正實(shí)力的一個(gè)順序。為此，我們提出如下的一些基本原則：（1）一隊(duì)排在另一

7、隊(duì)之前，不能只考慮這兩隊(duì)的戰(zhàn)績(jī)，而應(yīng)充分考慮這兩隊(duì)所有比賽場(chǎng)次的成績(jī)。（2）要充分考慮對(duì)手的強(qiáng)弱因素。（3）如果兩隊(duì)之間由于種種原因，沒有比賽或者雙方打成平局，就由這兩隊(duì)與其他隊(duì)比賽的戰(zhàn)績(jī)來(lái)確定它們的強(qiáng)弱。根據(jù)上述原則，據(jù)比賽成績(jī)表，構(gòu)造競(jìng)賽圖如下：根據(jù)建邊情況，可建立矩陣(4)參照上述方法得到的鄰接陣，得到競(jìng)賽圖G.按照上述算法，經(jīng)步驟（1）得到（5）針對(duì)競(jìng)賽圖G，按照前述的排名方法進(jìn)行排序。經(jīng)過(guò)步驟（2）得到，經(jīng)過(guò)步驟（3）得到鄰接矩陣：經(jīng)過(guò)步驟（4）得到競(jìng)賽圖G, T7,T3,T1,T9,T10,T2,T8,T6,T12,T5,T11,T4圖G包含的連通分圖：T7T3T1,T2,T8,T9,T10-雙向