數(shù)學建模之離散模型

1、關(guān)于數(shù)學建模之離散模型第一張，PPT共六十五頁，創(chuàng)作于2022年6月離散模型 離散模型：差分方程（第7章）、整數(shù)規(guī)劃（第4章）、圖論、對策論、網(wǎng)絡(luò)流、 分析社會經(jīng)濟系統(tǒng)的有力工具 只用到代數(shù)、集合及圖論（少許）的知識第二張，PPT共六十五頁，創(chuàng)作于2022年6月8.1 層次分析模型背景 日常工作、生活中的決策問題 涉及經(jīng)濟、社會等方面的因素 作比較判斷時人的主觀選擇起相當大的作用，各因素的重要性難以量化 Saaty于1970年代提出層次分析法 AHP (Analytic Hierarchy Process) AHP一種定性與定量相結(jié)合的、系統(tǒng)化、層次化的分析方法第三張，PPT共六十五頁，創(chuàng)作于

2、2022年6月目標層O(選擇旅游地)P2海南P1桂林P3張家界準則層方案層C3居住C1景色C2費用C4飲食C5旅途一. 層次分析法的基本步驟例. 選擇旅游地如何在3個目的地中按照景色、費用、居住條件等因素選擇.第四張，PPT共六十五頁，創(chuàng)作于2022年6月“選擇旅游地”思維過程的歸納 將決策問題分為3個層次：目標層O，準則層C，方案層P；每層有若干元素， 各層元素間的關(guān)系用相連的直線表示。 通過相互比較確定各準則對目標的權(quán)重，及各方案對每一準則的權(quán)重。 將上述兩組權(quán)重進行綜合，確定各方案對目標的權(quán)重。層次分析法將定性分析與定量分析結(jié)合起來完成以上步驟，給出決策問題的定量結(jié)果。第五張，PPT共六

3、十五頁，創(chuàng)作于2022年6月層次分析法的基本步驟成對比較陣和權(quán)向量 元素之間兩兩對比，對比采用相對尺度 設(shè)要比較各準則C1,C2, , Cn對目標O的重要性A成對比較陣A是正互反陣要由A確定C1, , Cn對O的權(quán)向量選擇旅游地景色費用居住飲食旅途第六張，PPT共六十五頁，創(chuàng)作于2022年6月成對比較的不一致情況一致比較不一致允許不一致，但要確定不一致的允許范圍考察完全一致的情況成對比較陣和權(quán)向量第七張，PPT共六十五頁，創(chuàng)作于2022年6月成對比較完全一致的情況滿足的正互反陣A稱一致陣，如 A的秩為1，A的唯一非零特征根為n A的任一列向量是對應于n 的特征向量 A的歸一化特征向量可作為權(quán)向

4、量對于不一致(但在允許范圍內(nèi))的成對比較陣A，建議用對應于最大特征根的特征向量作為權(quán)向量w ，即一致陣性質(zhì)成對比較陣和權(quán)向量第八張，PPT共六十五頁，創(chuàng)作于2022年6月2 4 6 8比較尺度aij Saaty等人提出19尺度aij 取值1,2, , 9及其互反數(shù)1,1/2, , 1/9尺度 1 3 5 7 9 相同 稍強 強 明顯強 絕對強aij = 1,1/2, ,1/9的重要性與上面相反 心理學家認為成對比較的因素不宜超過9個 用13,15,117,1p9p (p=2,3,4,5), d+0.1d+0.9 (d=1,2,3,4)等27種比較尺度對若干實例構(gòu)造成對比較陣，算出權(quán)向量，與實際

5、對比發(fā)現(xiàn)， 19尺度較優(yōu)。 便于定性到定量的轉(zhuǎn)化：成對比較陣和權(quán)向量第九張，PPT共六十五頁，創(chuàng)作于2022年6月一致性檢驗對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 當CR0.1時，通過一致性檢驗Saaty的結(jié)果如下第十張，PPT共六十五頁

6、，創(chuàng)作于2022年6月“選擇旅游地”中準則層對目標的權(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= n , = n是A為一致陣的充要條件。 正互反陣的最大特征根是正數(shù)，特征向量是正向量。一致性指標 定義合理第二十張，PPT共六十五頁，創(chuàng)作于2022年6月2. 正互反陣最大特征根和特征向量的簡化計算 精確計算的復雜和不必要 簡化計算的思路一致陣的任一列向量都是特征向量，一致性尚好的正互反陣的列

7、向量都應近似特征向量，可取其某種意義下的平均。和法取列向量的算術(shù)平均列向量歸一化算術(shù)平均精確結(jié)果:w=(0.588,0.322,0.090)T, =3.010第二十一張，PPT共六十五頁，創(chuàng)作于2022年6月根法取列向量的幾何平均冪法迭代算法1）任取初始向量w(0), k:=0，設(shè)置精度2) 計算3）歸一化5) 計算簡化計算4）若 ，停止；否則，k:=k+1, 轉(zhuǎn)2第二十二張，PPT共六十五頁，創(chuàng)作于2022年6月3. 特征向量作為權(quán)向量成對比較的多步累積效應問題一致陣A, 權(quán)向量w=(w1,wn)T, aij=wi/wjA不一致, 應選權(quán)向量w使wi/wj與 aij相差盡量?。▽λ衖,j)

8、。用擬合方法確定w非線性最小二乘線性化對數(shù)最小二乘結(jié)果與根法相同第二十三張，PPT共六十五頁，創(chuàng)作于2022年6月 按不同準則確定的權(quán)向量不同，特征向量有什么優(yōu)點。成對比較Ci:Cj (直接比較）aij 1步強度aisasj Ci通過Cs 與Cj的比較aij(2) 2步強度更能反映Ci對Cj 的強度多步累積效應體現(xiàn)多步累積效應定理1特征向量體現(xiàn)多步累積效應當k足夠大, Ak第i行元素反映Ci的權(quán)重求Ak的行和第二十四張，PPT共六十五頁，創(chuàng)作于2022年6月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

9、),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科研C2P2 P1P3P4例: 評價教師貢獻的層次結(jié)構(gòu)P1,P2只作教學, P4只作科研, P3兼作教學、科研。C1,C2支配元素的數(shù)目不等第二十五張，PPT共六十五頁，創(chuàng)作于2022年6月 不考慮支配元素數(shù)目不等的影響 仍用 計算 支配元素越多權(quán)重越大用支配元素數(shù)目n1,n2對w(2)加權(quán)修正 若C1,C2重要性相同, w(2)=(1/

10、2,1/2)T, P1P4能力相同, 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 支配元素越多權(quán)重越小教學、科研任務由上級安排教學、科研靠個人積極性考察一個特例：第二十六張，PPT共六十五頁，創(chuàng)作于2022年6月5. 殘缺成對比較陣的處理miA第i 行中的個數(shù)為殘缺元素輔助矩陣第二十七張，PPT共六十五頁，創(chuàng)作于2022年6月6. 更復雜的層次結(jié)構(gòu) 遞階層次結(jié)構(gòu)：層內(nèi)各元素獨立，無相互影響和

11、支配；層間自上而下、逐層傳遞，無反饋和循環(huán)。 更復雜的層次結(jié)構(gòu)：層內(nèi)各元素間存在相互影響或支配；層間存在反饋或循環(huán)。制動底盤車輪方向盤發(fā)動機減震裝置剎車轉(zhuǎn)向運行加速性能汽車行駛性能汽車1汽車2汽車n例第二十八張，PPT共六十五頁，創(chuàng)作于2022年6月 層次分析法的優(yōu)點 系統(tǒng)性將對象視作系統(tǒng)，按照分解、比較、判斷、綜合的思維方式進行決策系統(tǒng)分析（與機理分析、測試分析并列）； 實用性定性與定量相結(jié)合，能處理傳統(tǒng)的優(yōu)化方法不能解決的問題； 簡潔性計算簡便，結(jié)果明確，便于決策者直接了解和掌握。層次分析法的局限 囿舊只能從原方案中選優(yōu)，不能產(chǎn)生新方案； 粗略定性化為定量，結(jié)果粗糙； 主觀主觀因素作用大，

12、結(jié)果可能難以服人。第二十九張，PPT共六十五頁，創(chuàng)作于2022年6月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é)果32，4 5排名 132456 合理嗎第三十張，PPT共六十五頁，創(chuàng)作于2022年6月123(1)123(2)1234(1)1234(2)1234(3)1234(4)循環(huán)比賽的結(jié)果競賽圖每對頂點間都有邊相連的有向圖3個頂

13、點的競賽圖名次1，2，3(1,2,3)并列1, 2, 3, 42,(1,3,4)(1,3,4), 24個頂點的競賽圖名次(1,2),(3,4)1, 2, 3, 4?第三十一張，PPT共六十五頁，創(chuàng)作于2022年6月123412341234(1)(2)(3)1234(4)競賽圖的3種形式 具有唯一的完全路徑，如(1)； 雙向連通圖任一對頂點存在兩條有向路徑相互連通，如(4)； 其他，如(2)， (3) 。競賽圖的性質(zhì) 必存在完全路徑； 若存在唯一的完全路徑，則由它確定的頂點順序與按得分排列的順序一致，如(1) 。第三十二張，PPT共六十五頁，創(chuàng)作于2022年6月1234(4)雙向連通競賽圖G=(

14、V,E)的名次排序鄰接矩陣得分向量第三十三張，PPT共六十五頁，創(chuàng)作于2022年6月雙向連通競賽圖的名次排序 對于n(3)個頂點的雙向連通競賽圖，存在正整數(shù)r，使鄰接矩陣A 滿足Ar 0，A稱素陣 素陣A的最大特征根為正單根，對應正特征向量s，且排名為1，2，4，3用s排名1234(4)1, 2, 3, 4?第三十四張，PPT共六十五頁，創(chuàng)作于2022年6月1234566支球隊比賽結(jié)果排名次序為1，3， 2，5，4，6第三十五張，PPT共六十五頁，創(chuàng)作于2022年6月v1能源利用量； v2能源價格；v3能源生產(chǎn)率； v4環(huán)境質(zhì)量；v5工業(yè)產(chǎn)值； v6就業(yè)機會；v7人口總數(shù)。8.3 社會經(jīng)濟系統(tǒng)

15、的沖量過程系統(tǒng)的元素圖的頂點元素間的影響帶方向的弧影響的正反面弧旁的+、 號帶符號的有向圖影響直接影響符號客觀規(guī)律；方針政策例 能源利用系統(tǒng)的預測+-+-+-+v2v1v3v4v6v7v5第三十六張，PPT共六十五頁，創(chuàng)作于2022年6月帶符號有向圖G1=(V,E)的鄰接矩陣AV頂點集 E弧集定性模型-vivj+某時段vi 增加導致下時段vj 增加減少帶符號的有向圖G1+-+-+-+v2v1v3v4v6v7v5第三十七張，PPT共六十五頁，創(chuàng)作于2022年6月加權(quán)有向圖G2及其鄰接矩陣W定量模型某時段vi 增加1單位導致下時段vj 增加wij單位v70.311.511.51.20.8-2-2-

16、0.7-0.5v1v2v3v4v5v6加權(quán)有向圖G2第三十八張，PPT共六十五頁，創(chuàng)作于2022年6月沖量過程（Pulse Process)研究由某元素vi變化引起的系統(tǒng)的演變過程 vi(t) vi在時段t 的值； pi(t) vi在時段t 的改變量(沖量)沖量過程模型或第三十九張，PPT共六十五頁，創(chuàng)作于2022年6月231-10010-12-21-110-11-11-10103-32-211-1能源利用系統(tǒng)的預測簡單沖量過程初始沖量p(0)中某個分量為1，其余為0的沖量過程若開始時能源利用量有突然增加，預測系統(tǒng)的演變設(shè)能源利用系統(tǒng)的 p(t)和v(t)-110-11-100011-1000

17、00100000010000000第四十張，PPT共六十五頁，創(chuàng)作于2022年6月簡單沖量過程S的穩(wěn)定性 任意時段S的各元素的值和沖量是否為有限(穩(wěn)定) S不穩(wěn)定時如何改變可以控制的關(guān)系使之變?yōu)榉€(wěn)定 S沖量穩(wěn)定對任意 i,t, | pi(t) |有界 S值穩(wěn)定對任意 i,t, | vi(t) |有界值穩(wěn)定沖量穩(wěn)定S的穩(wěn)定性取決于W的特征根記W的非零特征根為第四十一張，PPT共六十五頁，創(chuàng)作于2022年6月 S沖量穩(wěn)定 | | 1 S沖量穩(wěn)定 | | 1且均為單根 S值穩(wěn)定 S沖量穩(wěn)定且不等于1對于能源利用系統(tǒng)的鄰接矩陣A特征多項式能源利用系統(tǒng)存在沖量不穩(wěn)定的簡單沖量過程簡單沖量過程S的穩(wěn)定性

18、第四十二張，PPT共六十五頁，創(chuàng)作于2022年6月簡單沖量過程的穩(wěn)定性 改進的玫瑰形圖S* 帶符號的有向圖雙向連通，且存在一個位于所有回路上的中心頂點?；芈烽L度 構(gòu)成回路的邊數(shù)回路符號 構(gòu)成回路的各有向邊符號+1或-1之乘積ak長度為k的回路符號和r使ak不等于0的最大整數(shù) S*沖量穩(wěn)定 若S*沖量穩(wěn)定，則S*值穩(wěn)定 +-+-+-+v2v1v3v4v6v7v5第四十三張，PPT共六十五頁，創(chuàng)作于2022年6月簡單沖量過程S*的穩(wěn)定性 a1=0, a2= (-1)v1v2 (-1)v2v1 =1a3=(+1)v1v3v5v1+(-1)v1v4v7v1+(+1)v1v3v2v1=1, a4=0,

19、a5=1, r=5 S*沖量穩(wěn)定 (-1)v1v2(+1)v1v2(由鼓勵利用變?yōu)橄拗评? a2 =-1+S*沖量不穩(wěn)定A的特征多項式S*沖量穩(wěn)定 S*沖量穩(wěn)定 | | 1且均為單根v1利用量, v2價格v7+-+-+-+v2v1v3v4v6v5第四十四張，PPT共六十五頁，創(chuàng)作于2022年6月 若S*沖量穩(wěn)定，則S*值穩(wěn)定 S*沖量穩(wěn)定 v3能源生產(chǎn)率 v5工業(yè)產(chǎn)值(-1)v3v5 違反客觀規(guī)律S*值不穩(wěn)定S*值穩(wěn)定(+1)v3v5 (-1)v3v5能源利用系統(tǒng)的值不應穩(wěn)定？-+-+-+v2v1v3v4v6v7v5+第四十五張，PPT共六十五頁，創(chuàng)作于2022年6月8.4 效益的合理分配例

20、甲乙丙三人合作經(jīng)商，若甲乙合作獲利7元，甲丙合作獲利5元，乙丙合作獲利4元，三人合作獲利11元。又知每人單干獲利1元。問三人合作時如何分配獲利？記甲乙丙三人分配為解不唯一(5，3，3)(4，4，3)(5，4，2)第四十六張，PPT共六十五頁，創(chuàng)作于2022年6月 (1) Shapley合作對策 I,v n人合作對策，v特征函數(shù)n人從v(I)得到的分配，滿足v(s) 子集s的獲利第四十七張，PPT共六十五頁，創(chuàng)作于2022年6月公理化方法s子集 s中的元素數(shù)目， Si 包含i的所有子集由s決定的“貢獻”的權(quán)重 Shapley值 i 對合作s 的“貢獻”Shapley合作對策第四十八張，PPT共六

21、十五頁，創(chuàng)作于2022年6月三人(I=1,2,3)經(jīng)商中甲的分配x1的計算 1/3 1/6 1/6 1/31 1 2 1 3 I1 7 5 11 0 1 1 4 1 6 4 7 1/3 1 2/3 7/3x1=13/3類似可得 x2=23/6, x3=17/61 2 2 3第四十九張，PPT共六十五頁，創(chuàng)作于2022年6月合作對策的應用 例1 污水處理費用的合理分擔20km38km河流三城鎮(zhèn)地理位置示意圖123 污水處理，排入河流三城鎮(zhèn)可單獨建處理廠，或聯(lián)合建廠(用管道將污水由上游城鎮(zhèn)送往下游城鎮(zhèn))Q1=5Q3=5Q2=3Q污水量，L管道長度建廠費用P1=73Q0.712管道費用P2=0.66

22、Q0.51L第五十張，PPT共六十五頁，創(chuàng)作于2022年6月污水處理的5 種方案1）單獨建廠總投資2）1, 2合作3）2, 3合作4）1, 3合作總投資總投資合作不會實現(xiàn)第五十一張，PPT共六十五頁，創(chuàng)作于2022年6月5）三城合作總投資D5最小, 應聯(lián)合建廠 建廠費：d1=73(5+3+5)0.712=453 12管道費：d2=0.66 50.51 20=30 23管道費：d3=0.66 (5+3)0.51 38=73D5城3建議：d1 按 5:3:5分擔, d2,d3由城1,2擔負城2建議：d3由城1,2按 5:3分擔, d2由城1擔負城1計算：城3分擔d15/13=174C(3), 城2

23、分擔d13/13+d3 3/8 =132C(1)不同意D5如何分擔？第五十二張，PPT共六十五頁，創(chuàng)作于2022年6月特征函數(shù)v(s)聯(lián)合(集s)建廠比單獨建廠節(jié)約的投資三城從節(jié)約投資v(I)中得到的分配 Shapley合作對策第五十三張，PPT共六十五頁，創(chuàng)作于2022年6月計算城1從節(jié)約投資中得到的分配x11 1 2 1 3 I 0 40 0 640 0 0 250 40 0 39 1 2 2 31/3 1/6 1/6 1/3 0 6.7 0 13 x1 =19.7,城1 C(1)-x1=210.4, 城2 C(2)-x2=127.8, 城3 C(3)-x3=217.8三城在總投資556中

24、的分擔x2 =32.1, x3=12.2x2最大，如何解釋？第五十四張，PPT共六十五頁，創(chuàng)作于2022年6月合作對策的應用 例2 派別在團體中的權(quán)重 90人的團體由3個派別組成，人數(shù)分別為40, 30, 20人。團體表決時需過半數(shù)的贊成票方可通過。雖然3派人數(shù)相差很大若每個派別的成員同時投贊成票或反對票，用Shapley合作對策計算各派別在團體中的權(quán)重。團體 I=1,2,3，依次代表3個派別=否則，的成員超過定義特征函數(shù)045,1)(ssv第五十五張，PPT共六十五頁，創(chuàng)作于2022年6月優(yōu)點：公正、合理，有公理化基礎(chǔ)。如n個單位治理污染, 通常知道第i方單獨治理的投資yi 和n方共同治理的投資Y, 及第i方不參加時其余n-1方的投資zi (i=1,2, n). 確定共同治理時各方分擔的費用。其它v(s