數(shù)學(xué)建模資料 (2).ppt

第八章離散模型 8 1層次分析模型8 2循環(huán)比賽的名次8 3社會(huì)經(jīng)濟(jì)系統(tǒng)的沖量過程8 4效益的合理分配 y 離散模型 離散模型 差分方程 第7章 整數(shù)規(guī)劃 第4章 圖論 對(duì)策論 網(wǎng)絡(luò)流 分析社會(huì)經(jīng)濟(jì)系統(tǒng)的有力工具 只用到代數(shù) 集合及圖論 少許 的知識(shí) 8 1層次分析模型 背景 日常工作 生活中的決策問題 涉及經(jīng)濟(jì) 社會(huì)等方面的因素 作比較判斷時(shí)人的主觀選擇起相當(dāng)大的作用 各因素的重要性難以量化 Saaty于1970年代提出層次分析法AHP AnalyticHierarchyProcess AHP 一種定性與定量相結(jié)合的 系統(tǒng)化 層次化的分析方法 目標(biāo)層 O 選擇旅游地 準(zhǔn)則層 方案層 一 層次分析法的基本步驟 例 選擇旅游地 如何在3個(gè)目的地中按照景色 費(fèi)用 居住條件等因素選擇 選擇旅游地 思維過程的歸納 將決策問題分為3個(gè)層次 目標(biāo)層O 準(zhǔn)則層C 方案層P 每層有若干元素 各層元素間的關(guān)系用相連的直線表示 通過相互比較確定各準(zhǔn)則對(duì)目標(biāo)的權(quán)重 及各方案對(duì)每一準(zhǔn)則的權(quán)重 將上述兩組權(quán)重進(jìn)行綜合 確定各方案對(duì)目標(biāo)的權(quán)重 層次分析法將定性分析與定量分析結(jié)合起來完成以上步驟 給出決策問題的定量結(jié)果 層次分析法的基本步驟 成對(duì)比較陣和權(quán)向量 元素之間兩兩對(duì)比 對(duì)比采用相對(duì)尺度 設(shè)要比較各準(zhǔn)則C1 C2 Cn對(duì)目標(biāo)O的重要性 A 成對(duì)比較陣 A是正互反陣 要由A確定C1 Cn對(duì)O的權(quán)向量 選擇旅游地 成對(duì)比較的不一致情況 允許不一致 但要確定不一致的允許范圍 考察完全一致的情況 成對(duì)比較陣和權(quán)向量 成對(duì)比較完全一致的情況 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)向量 2468 比較尺度aij Saaty等人提出1 9尺度 aij取值1 2 9及其互反數(shù)1 1 2 1 9 心理學(xué)家認(rèn)為成對(duì)比較的因素不宜超過9個(gè) 用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種比較尺度對(duì)若干實(shí)例構(gòu)造成對(duì)比較陣 算出權(quán)向量 與實(shí)際對(duì)比發(fā)現(xiàn) 1 9尺度較優(yōu) 便于定性到定量的轉(zhuǎn)化 成對(duì)比較陣和權(quán)向量 一致性檢驗(yàn) 對(duì)A確定不一致的允許范圍 已知 n階一致陣的唯一非零特征根為n 可證 n階正互反陣最大特征根 n 且 n時(shí)為一致陣 定義一致性指標(biāo) CI越大 不一致越嚴(yán)重 為衡量CI的大小 引入隨機(jī)一致性指標(biāo)RI 隨機(jī)模擬得到aij 形成A 計(jì)算CI即得RI 定義一致性比率CR CI RI 當(dāng)CR 0 1時(shí) 通過一致性檢驗(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 016 0 1 通過一致性檢驗(yàn) 組合權(quán)向量 記第2層 準(zhǔn)則 對(duì)第1層 目標(biāo) 的權(quán)向量為 同樣求第3層 方案 對(duì)第2層每一元素 準(zhǔn)則 的權(quán)向量 方案層對(duì)C1 景色 的成對(duì)比較陣 方案層對(duì)C2 費(fèi)用 的成對(duì)比較陣 最大特征根 1 2 n 權(quán)向量w1 3 w2 3 wn 3 組合權(quán)向量 RI 0 58 n 3 CIk均可通過一致性檢驗(yàn) w 2 0 2630 4750 0550 0900 110 方案P1對(duì)目標(biāo)的組合權(quán)重為0 595 0 263 0 300 方案層對(duì)目標(biāo)的組合權(quán)向量為 0 300 0 246 0 456 T 組合權(quán)向量 第2層對(duì)第1層的權(quán)向量 第3層對(duì)第2層各元素的權(quán)向量 構(gòu)造矩陣 則第3層對(duì)第1層的組合權(quán)向量 第s層對(duì)第1層的組合權(quán)向量 其中W p 是由第p層對(duì)第p 1層權(quán)向量組成的矩陣 層次分析法的基本步驟 1 建立層次分析結(jié)構(gòu)模型 深入分析實(shí)際問題 將有關(guān)因素自上而下分層 目標(biāo) 準(zhǔn)則或指標(biāo) 方案或?qū)ο?上層受下層影響 而層內(nèi)各因素基本上相對(duì)獨(dú)立 2 構(gòu)造成對(duì)比較陣 用成對(duì)比較法和1 9尺度 構(gòu)造各層對(duì)上一層每一因素的成對(duì)比較陣 3 計(jì)算權(quán)向量并作一致性檢驗(yàn) 對(duì)每一成對(duì)比較陣計(jì)算最大特征根和特征向量 作一致性檢驗(yàn) 若通過 則特征向量為權(quán)向量 4 計(jì)算組合權(quán)向量 作組合一致性檢驗(yàn) 組合權(quán)向量可作為決策的定量依據(jù) 二 層次分析法的廣泛應(yīng)用 應(yīng)用領(lǐng)域 經(jīng)濟(jì)計(jì)劃和管理 能源政策和分配 人才選拔和評(píng)價(jià) 生產(chǎn)決策 交通運(yùn)輸 科研選題 產(chǎn)業(yè)結(jié)構(gòu) 教育 醫(yī)療 環(huán)境 軍事等 處理問題類型 決策 評(píng)價(jià) 分析 預(yù)測(cè)等 建立層次分析結(jié)構(gòu)模型是關(guān)鍵一步 要有主要決策層參與 構(gòu)造成對(duì)比較陣是數(shù)量依據(jù) 應(yīng)由經(jīng)驗(yàn)豐富 判斷力強(qiáng)的專家給出 例1國家實(shí)力分析 例2工作選擇 例3橫渡江河 海峽方案的抉擇 例3橫渡江河 海峽方案的抉擇 例4科技成果的綜合評(píng)價(jià) 三 層次分析法的若干問題 正互反陣的最大特征根是否為正數(shù) 特征向量是否為正向量 一致性指標(biāo)能否反映正互反陣接近一致陣的程度 怎樣簡(jiǎn)化計(jì)算正互反陣的最大特征根和特征向量 為什么用特征向量作為權(quán)向量 當(dāng)層次結(jié)構(gòu)不完全或成對(duì)比較陣有空缺時(shí)怎樣用層次分析法 1 正互反陣的最大特征根和特征向量的性質(zhì) 定理1正矩陣A的最大特征根 是正單根 對(duì)應(yīng)正特征向量w 且 定理2n階正互反陣A的最大特征根 n n是A為一致陣的充要條件 2 正互反陣最大特征根和特征向量的簡(jiǎn)化計(jì)算 精確計(jì)算的復(fù)雜和不必要 簡(jiǎn)化計(jì)算的思路 一致陣的任一列向量都是特征向量 一致性尚好的正互反陣的列向量都應(yīng)近似特征向量 可取其某種意義下的平均 和法 取列向量的算術(shù)平均 精確結(jié)果 w 0 588 0 322 0 090 T 3 010 根法 取列向量的幾何平均 冪法 迭代算法 1 任取初始向量w 0 k 0 設(shè)置精度 2 計(jì)算 3 歸一化 5 計(jì)算 簡(jiǎn)化計(jì)算 4 若 停止 否則 k k 1 轉(zhuǎn)2 3 特征向量作為權(quán)向量 成對(duì)比較的多步累積效應(yīng) 問題 一致陣A 權(quán)向量w w1 wn T aij wi wj A不一致 應(yīng)選權(quán)向量w使wi wj與aij相差盡量小 對(duì)所有i j 非線性最小二乘 線性化 對(duì)數(shù)最小二乘 結(jié)果與根法相同 按不同準(zhǔn)則確定的權(quán)向量不同 特征向量有什么優(yōu)點(diǎn) 成對(duì)比較 Ci Cj 直接比較 aij 1步強(qiáng)度 aisasj Ci通過Cs與Cj的比較 aij 2 2步強(qiáng)度 更能反映Ci對(duì)Cj的強(qiáng)度 多步累積效應(yīng) 體現(xiàn)多步累積效應(yīng) 定理1 特征向量體現(xiàn)多步累積效應(yīng) 4 不完全層次結(jié)構(gòu)中組合權(quán)向量的計(jì)算 完全層次結(jié)構(gòu) 上層每一元素與下層所有元素相關(guān)聯(lián) 不完全層次結(jié)構(gòu) 設(shè)第2層對(duì)第1層權(quán)向量w 2 w1 2 w2 2 T已定 第3層對(duì)第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 計(jì)算第3層對(duì)第1層權(quán)向量w 3 的方法 例 評(píng)價(jià)教師貢獻(xiàn)的層次結(jié)構(gòu) P1 P2只作教學(xué) P4只作科研 P3兼作教學(xué) 科研 C1 C2支配元素的數(shù)目不等 不考慮支配元素?cái)?shù)目不等的影響 仍用計(jì)算 支配元素越多權(quán)重越大 用支配元素?cái)?shù)目n1 n2對(duì)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 公正的評(píng)價(jià)應(yīng)為 P1 P2 P3 P4 1 1 2 1 再用計(jì)算 支配元素越多權(quán)重越小 教學(xué) 科研任務(wù)由上級(jí)安排 教學(xué) 科研靠個(gè)人積極性 考察一個(gè)特例 5 殘缺成對(duì)比較陣的處理 mi A第i行中 的個(gè)數(shù) 為殘缺元素 6 更復(fù)雜的層次結(jié)構(gòu) 遞階層次結(jié)構(gòu) 層內(nèi)各元素獨(dú)立 無相互影響和支配 層間自上而下 逐層傳遞 無反饋和循環(huán) 更復(fù)雜的層次結(jié)構(gòu) 層內(nèi)各元素間存在相互影響或支配 層間存在反饋或循環(huán) 例 層次分析法的優(yōu)點(diǎn) 系統(tǒng)性 將對(duì)象視作系統(tǒng) 按照分解 比較 判斷 綜合的思維方式進(jìn)行決策 系統(tǒng)分析 與機(jī)理分析 測(cè)試分析并列 實(shí)用性 定性與定量相結(jié)合 能處理傳統(tǒng)的優(yōu)化方法不能解決的問題 簡(jiǎn)潔性 計(jì)算簡(jiǎn)便 結(jié)果明確 便于決策者直接了解和掌握 層次分析法的局限 囿舊 只能從原方案中選優(yōu) 不能產(chǎn)生新方案 粗略 定性化為定量 結(jié)果粗糙 主觀 主觀因素作用大 結(jié)果可能難以服人 8 2循環(huán)比賽的名次 n支球隊(duì)循環(huán)賽 每場(chǎng)比賽只計(jì)勝負(fù) 沒有平局 根據(jù)比賽結(jié)果排出各隊(duì)名次 方法1 尋找按箭頭方向通過全部頂點(diǎn)的路徑 312456 146325 方法2 計(jì)算得分 1隊(duì)勝4場(chǎng) 2 3隊(duì)各勝3場(chǎng) 4 5隊(duì)各勝2場(chǎng) 6隊(duì)勝1場(chǎng) 2 3隊(duì) 4 5隊(duì)無法排名 6支球隊(duì)比賽結(jié)果 3 2 4 5 循環(huán)比賽的結(jié)果 競(jìng)賽圖每對(duì)頂點(diǎn)間都有邊相連的有向圖 3個(gè)頂點(diǎn)的競(jìng)賽圖 名次 1 2 3 1 2 3 并列 1 2 3 4 2 1 3 4 1 3 4 2 4個(gè)頂點(diǎn)的競(jìng)賽圖 名次 1 2 3 4 1 2 3 4 競(jìng)賽圖的3種形式 具有唯一的完全路徑 如 1 雙向連通圖 任一對(duì)頂點(diǎn)存在兩條有向路徑相互連通 如 4 其他 如 2 3 競(jìng)賽圖的性質(zhì) 必存在完全路徑 若存在唯一的完全路徑 則由它確定的頂點(diǎn)順序與按得分排列的順序一致 如 1 雙向連通競(jìng)賽圖G V E 的名次排序 鄰接矩陣 得分向量 雙向連通競(jìng)賽圖的名次排序 對(duì)于n 3 個(gè)頂點(diǎn)的雙向連通競(jìng)賽圖 存在正整數(shù)r 使鄰接矩陣A滿足Ar 0 A稱素陣 素陣A的最大特征根為正單根 對(duì)應(yīng)正特征向量s 且 排名為 1 2 4 3 1 2 3 4 6支球隊(duì)比賽結(jié)果 排名次序?yàn)?1 3 2 5 4 6 v1 能源利用量 v2 能源價(jià)格 v3 能源生產(chǎn)率 v4 環(huán)境質(zhì)量 v5 工業(yè)產(chǎn)值 v6 就業(yè)機(jī)會(huì) v7 人口總數(shù) 8 3社會(huì)經(jīng)濟(jì)系統(tǒng)的沖量過程 系統(tǒng)的元素 圖的頂點(diǎn) 元素間的影響 帶方向的弧 影響的正反面 弧旁的 號(hào) 帶符號(hào)的有向圖 影響 直接影響 符號(hào) 客觀規(guī)律 方針政策 例能源利用系統(tǒng)的預(yù)測(cè) 帶符號(hào)有向圖G1 V E 的鄰接矩陣A V 頂點(diǎn)集E 弧集 定性模型 帶符號(hào)的有向圖G1 加權(quán)有向圖G2及其鄰接矩陣W 定量模型 某時(shí)段vi增加1單位導(dǎo)致下時(shí)段vj增加wij單位 v7 沖量過程 PulseProcess 研究由某元素vi變化引起的系統(tǒng)的演變過程 vi t vi在時(shí)段t的值 pi t vi在時(shí)段t的改變量 沖量 沖量過程模型 或 能源利用系統(tǒng)的預(yù)測(cè) 簡(jiǎn)單沖量過程 初始沖量p 0 中某個(gè)分量為1 其余為0的沖量過程 若開始時(shí)能源利用量有突然增加 預(yù)測(cè)系統(tǒng)的演變 設(shè) 能源利用系統(tǒng)的p t 和v t 簡(jiǎn)單沖量過程S的穩(wěn)定性 任意時(shí)段S的各元素的值和沖量是否為有限 穩(wěn)定 S不穩(wěn)定時(shí)如何改變可以控制的關(guān)系使之變?yōu)榉€(wěn)定 S沖量穩(wěn)定 對(duì)任意i t pi t 有界 S值穩(wěn)定 對(duì)任意i t vi t 有界 記W的非零特征根為 S沖量穩(wěn)定 1 S沖量穩(wěn)定 1且均為單根 S值穩(wěn)定 S沖量穩(wěn)定且 不等于1 對(duì)于能源利用系統(tǒng)的鄰接矩陣A 特征多項(xiàng)式 能源利用系統(tǒng)存在沖量不穩(wěn)定的簡(jiǎn)單沖量過程 簡(jiǎn)單沖量過程S的穩(wěn)定性 簡(jiǎn)單沖量過程的穩(wěn)定性 改進(jìn)的玫瑰形圖S 帶符號(hào)的有向圖雙向連通 且存在一個(gè)位于所有回路上的中心頂點(diǎn) 回路長度 構(gòu)成回路的邊數(shù) 回路符號(hào) 構(gòu)成回路的各有向邊符號(hào) 1或 1之乘積 ak 長度為k的回路符號(hào)和 r 使ak不等于0的最大整數(shù) S 沖量穩(wěn)定 若S 沖量穩(wěn)定 則S 值穩(wěn)定 簡(jiǎn)單沖量過程S 的穩(wěn)定性 a1 0 a2 1 v1v2 1 v2v1 1 a3 1 v1v3v5v1 1 v1v4v7v1 1 v1v3v2v1 1 a4 0 a5 1 r 5 S 沖量穩(wěn)定 1 v1v2 1 v1v2 由鼓勵(lì)利用變?yōu)橄拗评?a2 1 S 沖量穩(wěn)定 1且均為單根 v1 利用量 v2 價(jià)格 v7 若S 沖量穩(wěn)定 則S 值穩(wěn)定 S 沖量穩(wěn)定 v3 能源生產(chǎn)率v5 工業(yè)產(chǎn)值 S 值穩(wěn)定 能源利用系統(tǒng)的值不應(yīng)穩(wěn)定 8 4效益的合理分配 例 甲乙丙三人合作經(jīng)商 若甲乙合作獲利7元 甲丙合作獲利5元 乙丙合作獲利4元 三人合作獲利11元 又知每人單干獲利1元 問三人合作時(shí)如何分配獲利 記甲乙丙三人分配為 解不唯一 5 3 3 4 4 3 5 4 2 1 Shapley合作對(duì)策 I v n人合作對(duì)策 v 特征函數(shù) n人從v I 得到的分配 滿足 v s 子集s的獲利 公理化方法 s 子集s中的元素?cái)?shù)目 Si 包含i的所有子集 由 s 決定的 貢獻(xiàn) 的權(quán)重 i對(duì)合作s的 貢獻(xiàn) Shapley合作對(duì)策 三人 I 1 2 3 經(jīng)商中甲的分配x1的計(jì)算 1 31 61 61 3 11213I 17511 0114 1647 1 312 37 3 x1 13 3 類似可得x2 23 6 x3 17 6 1223 合作對(duì)策的應(yīng)用例1污水處理費(fèi)用的合理分擔(dān) 污水處理 排入河流 三城鎮(zhèn)可單獨(dú)建處理廠 或聯(lián)合建廠 用管道將污水由上游城鎮(zhèn)送往下游城鎮(zhèn) Q 污水量 L 管道長度建廠費(fèi)用P1 73Q0 712管道費(fèi)用P2 0 66Q0 51L 污水處理的5種方案 1 單獨(dú)建廠 總投資 2 1 2合作 3 2 3合作 4 1 3合作 總投資 總投資 合作不會(huì)實(shí)現(xiàn) 5 三城合作總投資 D5最小 應(yīng)聯(lián)合建廠 建廠費(fèi) d1 73 5 3 5 0 712 4531 2管道費(fèi) d2 0 66 50 51 20 302 3管道費(fèi) d3 0 66 5 3 0 51 38 73 D5 城3建議 d1按5 3 5分擔(dān) d2 d3由城1 2擔(dān)負(fù) 城2建議 d3由城1 2按5 3分擔(dān) d2由城1擔(dān)負(fù) 城1計(jì)算 城3分擔(dān)d1 5 13 174C 1 不同意 D5如何分擔(dān) 特征函數(shù)v s 聯(lián)合 集s 建廠比單獨(dú)建廠節(jié)約的投資 三城從節(jié)約投資v I 中得到的分配 Shapley合作對(duì)策 計(jì)算城1從節(jié)約投資中得到的分配x1 x1 19 7 城1C 1 x1 210 4 城2C 2 x2 127 8 城3C 3 x3 217 8 x2 32 1 x3 12 2 x2最大 如何解釋 合作對(duì)策的應(yīng)用例2派別在團(tuán)體中的權(quán)重 90人的團(tuán)體由3個(gè)派別組成 人數(shù)分別為40 30 20人 團(tuán)體表決時(shí)需過半數(shù)的贊成票方可通過 雖然3派人數(shù)相差很大 若每個(gè)派別的成員同時(shí)投贊成票或反對(duì)票 用Shapley合作對(duì)策計(jì)算各派別在團(tuán)體中的權(quán)重 團(tuán)體I 1 2 3 依次代表3個(gè)派別 優(yōu)點(diǎn) 公正 合理 有公理