數(shù)學(xué)建模 第八章課件

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

2、桂林P3北戴河準(zhǔn)則層方案層C3居住C1景色C2費(fèi)用C4飲食C5旅途一. 層次分析法的基本步驟例. 選擇旅游地如何在3個目的地中按照景色、費(fèi)用、居住條件等因素選擇.“選擇旅游地”思維過程的歸納 將決策問題分為3個層次：目標(biāo)層O，準(zhǔn)則層C，方案層P；每層有若干元素， 各層元素間的關(guān)系用相連的直線表示。 通過相互比較確定各準(zhǔn)則對目標(biāo)的權(quán)重，及各方案對每一準(zhǔn)則的權(quán)重。 將上述兩組權(quán)重進(jìn)行綜合，確定各方案對目標(biāo)的權(quán)重。層次分析法將定性分析與定量分析結(jié)合起來完成以上步驟，給出決策問題的定量結(jié)果。成對比較的不一致情況一致比較不一致允許不一致，但要確定不一致的允許范圍考察完全一致的情況成對比較陣和權(quán)向量成對比

3、較完全一致的情況滿足的正互反陣A稱一致陣，如 A的秩為1，A的唯一非零特征根為n A的任一列向量是對應(yīng)于n 的特征向量 A的歸一化特征向量可作為權(quán)向量對于不一致(但在允許范圍內(nèi))的成對比較陣A，建議用對應(yīng)于最大特征根的特征向量作為權(quán)向量w ，即一致陣性質(zhì)成對比較陣和權(quán)向量一致性檢驗(yàn)對A確定不一致的允許范圍已知：n 階一致陣的唯一非零特征根為n可證：n 階正互反陣最大特征根 n, 且 =n時為一致陣定義一致性指標(biāo):CI 越大，不一致越嚴(yán)重RI000.580.901.121.241.321.411.451.491.51 n1234567891110為衡量CI 的大小，引入隨機(jī)一致性指標(biāo) RI隨機(jī)模

4、擬得到aij , 形成A，計算CI 即得RI。定義一致性比率 CR = CI/RI 當(dāng)CR0.1時，通過一致性檢驗(yàn)Saaty的結(jié)果如下E = EIG(X) is a vector containing the eigenvalues of a square matrix X. V,D = EIG(X) produces a diagonal matrix D of eigenvalues and a full matrix V whose columns are the corresponding eigenvectors so that X*V = V*DA=1,1/2,4,3,3;2,1,

5、7,5,5;1/4,1/7,1,1/2,1/3; 1/3,1/5,2,1,1;1/3,1/5,3,1,1;V,D,flag=eigs(A);la=D(1,1)wa=V(:,1);wa=wa/sum(wa)CIA=(la-length(wa)/(length(wa)-1)CRA=CI/RI(length(wa)“選擇旅游地”中準(zhǔn)則層對目標(biāo)的權(quán)向量及一致性檢驗(yàn)準(zhǔn)則層對目標(biāo)的成對比較陣最大特征根=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)個頂點(diǎn)

6、的雙向連通競賽圖，存在正整數(shù)r，使鄰接矩陣A 滿足Ar 0，A稱素陣 素陣A的最大特征根為正單根，對應(yīng)正特征向量s，且排名為1，2，4，3用s排名1234(4)1, 2, 3, 4?1234566支球隊比賽結(jié)果排名次序?yàn)?，3， 2，5，4，6v1能源利用量； v2能源價格；v3能源生產(chǎn)率； v4環(huán)境質(zhì)量；v5工業(yè)產(chǎn)值； v6就業(yè)機(jī)會；v7人口總數(shù)。8.3 社會經(jīng)濟(jì)系統(tǒng)的沖量過程系統(tǒng)的元素圖的頂點(diǎn)元素間的影響帶方向的弧影響的正反面弧旁的+、 號帶符號的有向圖影響直接影響符號客觀規(guī)律；方針政策例 能源利用系統(tǒng)的預(yù)測+-+-+-+v2v1v3v4v6v7v5帶符號有向圖G1=(V,E)的鄰接矩陣A

7、V頂點(diǎn)集 E弧集定性模型-vivj+某時段vi 增加導(dǎo)致下時段vj 增加減少帶符號的有向圖G1+-+-+-+v2v1v3v4v6v7v5加權(quán)有向圖G2及其鄰接矩陣W定量模型某時段vi 增加1單位導(dǎo)致下時段vj 增加wij單位v70.311.511.51.20.8-2-2-0.7-0.5v1v2v3v4v5v6加權(quán)有向圖G2沖量過程（Pulse Process)研究由某元素vi變化引起的系統(tǒng)的演變過程 vi(t) vi在時段t 的值； pi(t) vi在時段t 的改變量(沖量)沖量過程模型或231-10010-12-21-110-11-11-10103-32-211-1能源利用系統(tǒng)的預(yù)測簡單沖量

8、過程初始沖量p(0)中某個分量為1，其余為0的沖量過程若開始時能源利用量有突然增加，預(yù)測系統(tǒng)的演變設(shè)能源利用系統(tǒng)的 p(t)和v(t)-110-11-100011-100000100000010000000簡單沖量過程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的非零特征根為 S沖量穩(wěn)定 | | 1 S沖量穩(wěn)定 | | 1且均為單根 S值穩(wěn)定 S沖量穩(wěn)定且不等于1對于能源利用系統(tǒng)的鄰接矩陣A

9、特征多項(xiàng)式能源利用系統(tǒng)存在沖量不穩(wěn)定的簡單沖量過程簡單沖量過程S的穩(wěn)定性 簡單沖量過程的穩(wěn)定性 改進(jìn)的玫瑰形圖S* 帶符號的有向圖雙向連通，且存在一個位于所有回路上的中心頂點(diǎn)?；芈烽L度 構(gòu)成回路的邊數(shù)回路符號 構(gòu)成回路的各有向邊符號+1或-1之乘積ak長度為k的回路符號和r使ak不等于0的最大整數(shù) S*沖量穩(wěn)定 若S*沖量穩(wěn)定，則S*值穩(wěn)定 +-+-+-+v2v1v3v4v6v7v5簡單沖量過程S*的穩(wěn)定性 a1=0, a2= (-1)v1v2 (-1)v2v1 =1a3=(+1)v1v3v5v1+(-1)v1v4v7v1+(+1)v1v3v2v1=1, a4=0, a5=1, r=5 S*沖

10、量穩(wěn)定 (-1)v1v2(+1)v1v2(由鼓勵利用變?yōu)橄拗评? a2 =-1+S*沖量不穩(wěn)定A的特征多項(xiàng)式S*沖量穩(wěn)定 S*沖量穩(wěn)定 | | 1且均為單根v1利用量, v2價格v7+-+-+-+v2v1v3v4v6v5 若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)的值不應(yīng)穩(wěn)定？-+-+-+v2v1v3v4v6v7v5+8.4 效益的合理分配例甲乙丙三人合作經(jīng)商，若甲乙合作獲利7元，甲丙合作獲利5元，乙丙合作獲利4元，三人合作獲利11元。又知每人單干獲利1元。問三人合

11、作時如何分配獲利？記甲乙丙三人分配為解不唯一(5，3，3)(4，4，3)(5，4，2) (1) Shapley合作對策 I,v n人合作對策，v特征函數(shù)n人從v(I)得到的分配，滿足v(s) 子集s的獲利公理化方法s子集 s中的元素數(shù)目， Si 包含i的所有子集由s決定的“貢獻(xiàn)”的權(quán)重 Shapley值 i 對合作s 的“貢獻(xiàn)”Shapley合作對策三人(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合

12、作對策的應(yīng)用 例1 污水處理費(fèi)用的合理分擔(dān)20km38km河流三城鎮(zhèn)地理位置示意圖123 污水處理，排入河流三城鎮(zhèn)可單獨(dú)建處理廠，或聯(lián)合建廠(用管道將污水由上游城鎮(zhèn)送往下游城鎮(zhèn))Q1=5Q3=5Q2=3Q污水量，L管道長度建廠費(fèi)用P1=73Q0.712管道費(fèi)用P2=0.66Q0.51L污水處理的5 種方案1）單獨(dú)建廠總投資2）1, 2合作3）2, 3合作4）1, 3合作總投資總投資合作不會實(shí)現(xiàn)5）三城合作總投資D5最小, 應(yīng)聯(lián)合建廠 建廠費(fèi)：d1=73(5+3+5)0.712=453 12管道費(fèi)：d2=0.66 50.51 20=30 23管道費(fèi)：d3=0.66 (5+3)0.51 38=73

13、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計算：城3分擔(dān)d15/13=174C(3), 城2分擔(dān)d13/13+d3 3/8 =132C(1)不同意D5如何分擔(dān)？特征函數(shù)v(s)聯(lián)合(集s)建廠比單獨(dú)建廠節(jié)約的投資三城從節(jié)約投資v(I)中得到的分配 Shapley合作對策計算城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

14、)-x2=127.8, 城3 C(3)-x3=217.8三城在總投資556中的分擔(dān)x2 =32.1, x3=12.2x2最大，如何解釋？合作對策的應(yīng)用 例2 派別在團(tuán)體中的權(quán)重 90人的團(tuán)體由3個派別組成，人數(shù)分別為40, 30, 20人。團(tuán)體表決時需過半數(shù)的贊成票方可通過。雖然3派人數(shù)相差很大若每個派別的成員同時投贊成票或反對票，用Shapley合作對策計算各派別在團(tuán)體中的權(quán)重。團(tuán)體 I=1,2,3，依次代表3個派別=否則，的成員超過定義特征函數(shù)045,1)(ssv優(yōu)點(diǎn)：公正、合理，有公理化基礎(chǔ)。如n個單位治理污染, 通常知道第i方單獨(dú)治理的投資yi 和n方共同治理的投資Y, 及第i方不參加

15、時其余n-1方的投資zi (i=1,2, n). 確定共同治理時各方分擔(dān)的費(fèi)用。其它v(s)均不知道, 無法用Shapley合作對策求解Shapley合作對策小結(jié)若定義特征函數(shù)為合作的獲利(節(jié)約的投資)，則有缺點(diǎn)：需要知道所有合作的獲利，即要定義I=1,2,n的所有子集(共2n-1個)的特征函數(shù)，實(shí)際上常做不到。設(shè)只知道無 i 參加時n-1方合作的獲利全體合作的獲利求解合作對策的其他方法例. 甲乙丙三人合作經(jīng)商，若甲乙合作獲利7元，甲丙合作獲利5元，乙丙合作獲利4元，三人合作獲利11元。問三人合作時如何分配獲利？（2）協(xié)商解11將剩余獲利 平均分配 模型以n-1方合作的獲利為下限求解 xi 的

16、下限（3）Nash解 為現(xiàn)狀點(diǎn)（談判時的威懾點(diǎn)）在此基礎(chǔ)上“均勻地”分配全體合作的獲利B模型平均分配獲利B3）Nash解 2）協(xié)商解（4）最小距離解模型 第i 方的邊際效益若令4）最小距離解 2）協(xié)商解（5）滿意解di現(xiàn)狀點(diǎn)(最低點(diǎn))ei理想點(diǎn)(最高點(diǎn))模型5）基于滿意度的解 2）協(xié)商解（6）Raiffi 解與協(xié)商解x=(5,4,2)比較求解合作對策的6種方法（可分為三類）Shapley合作對策A類B類協(xié)商解Nash解 最小距離解滿意解di現(xiàn)狀, ei理想B類4種方法相同例：有一資方(甲)和二勞方(乙,丙), 僅當(dāng)資方與至少一勞方合作時才獲利10元，應(yīng)如何分配該獲利？Raiffi解C類B類：計

17、算簡單，便于理解，可用于各方實(shí)力相差不大的情況；一般來說它偏袒強(qiáng)者。 C類： 考慮了分配的上下限，又吸取了Shapley的思想，在一定程度上保護(hù)弱者。A類：公正合理；需要信息多，計算復(fù)雜。求解合作對策的三類方法小結(jié)根據(jù)若干人對某些對象的決策結(jié)果，綜合出這個群體的決策結(jié)果的過程稱為群體決策(Group Decisionmaking)8.5 存在公正的選舉規(guī)則嗎？我們把根據(jù)每個人對評選對象的排序來確定這個群體對評選對象排序的決策過程，描述為一次選舉。有若干選民和若干候選人，每個選民的一次投票是按照自己的標(biāo)準(zhǔn)對各候選人優(yōu)劣順序的一次排序，而選舉規(guī)則要根據(jù)所有選民的排序確定選舉結(jié)果。本節(jié)首先給出這種排

18、序的一般性質(zhì)，討論簡單的選舉規(guī)則并指出它們的缺點(diǎn)，然后論證在一定意義上所謂公正的選舉規(guī)則是不存在的。最后介紹一個特殊的選舉規(guī)則簡單選舉規(guī)則I=(1,2,n)表示選民集合，m個字母構(gòu)成的A=x,y,z,u,v,表示候選人集合。選舉要求每個選民iI對全體候選人投票，即對A的一個排序，記作pi。所謂選舉規(guī)則是根據(jù)pi(i=1,2,n)確定選舉結(jié)果，即群體對A的排序，記做p，這種由(p1,p2,pn)到p的對應(yīng)關(guān)系在群體決策中稱為群體一致函數(shù)(Group consensus function)作為對集合A的任何一個排序pi和p，必須具備以下兩個性質(zhì)，也可稱為公理：對于任意的x,yA，下面三種關(guān)系必有且

19、僅有一種成立：x優(yōu)于y，記xy；x等同y，記xy，x劣于y，記xy時，選舉結(jié)果為xy(和B(y)時，xy成立(和x。但在投票中有三位選民認(rèn)為xy，只有一位認(rèn)為yx，只是他把y和x分別排在首位和末位，致使選舉結(jié)果服從了他個人的意愿，這是不能為多數(shù)人接受的。Arrow公理和Arrow定理公理1 （選舉的完全性）選民對候選人的任何一種排序都是允許的公理2 （選舉結(jié)果與選民投票正相關(guān)）若對于某次投票pi(i=1,2,n)，選舉規(guī)則確定的選舉結(jié)果p中包含xy，而另一次投票pI (I=1, 2, ,n)中x與y的順序或者與pi相同，或者x提前，而其它候選人的順序不變。那么在選舉規(guī)則確定的另一次選舉結(jié)果p中也應(yīng)包括xy公理3 （無關(guān)候選人的獨(dú)立性）設(shè)A1是候選人集合A的子集。若在兩次投票pi和pi(i=1,2,n)中A1內(nèi)各候選人的排序相同，那么選舉規(guī)則確定的兩次選舉結(jié)果p和p中A1內(nèi)各候選人的排序也應(yīng)該相同。公理4 （選民的主權(quán)性）多于任意一對候選人x,yA，存在一種投票pi(i=1,2,n)，使得選舉規(guī)則能由pi確定選舉結(jié)果中有xy公理5 （選民的非獨(dú)裁性）不存在這樣的選民i，使得對于任意一對候選人x,y，只要pi中有(x