第四版《數(shù)學(xué)模型》PPT_第8章課件

1、第八章 離散模型8.1 層次分析模型8.2 循環(huán)比賽的名次8.3 社會經(jīng)濟系統(tǒng)的沖量過程8.4 公平的席位分配8.5 存在公正的選舉規(guī)則嗎8.6 價格指數(shù)離散模型 離散模型：代數(shù)方程與差分方程（第6章）、整數(shù)規(guī)劃（第4章）、圖論、對策論、網(wǎng)絡(luò)流、 應(yīng)用較廣,是分析社會經(jīng)濟系統(tǒng)的有力工具. 只用到代數(shù)、集合及(少許)圖論的知識.8.1 層次分析模型背景 日常工作、生活中的決策問題. 涉及經(jīng)濟、社會等方面的因素. 作比較判斷時人的主觀選擇起相當(dāng)大 的作用，各因素的重要性難以量化. Saaty于20世紀(jì)70年代提出層次分析法 AHP (Analytic Hierarchy Process) AHP一

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

3、對比較陣和權(quán)向量 元素之間兩兩對比，對比采用相對尺度 設(shè)要比較各準(zhǔn)則C1,C2,Cn對目標(biāo)O的重要性A成對比較陣A是正互反陣要由A確定C1,Cn對O的權(quán)向量選擇旅游地成對比較的不一致情況一致比較允許不一致，但要確定不一致的允許范圍考察完全一致的情況成對比較陣和權(quán)向量不一致成對比較完全一致的情況滿足的正互反陣A稱一致陣，如 A的秩為1，A的唯一非零特征根為n A的任一列向量是對應(yīng)于n 的特征向量 A的歸一化特征向量可作為權(quán)向量一致陣性質(zhì)成對比較陣和權(quán)向量對于不一致(但在允許范圍內(nèi))的成對比較陣A,建議用對應(yīng)于最大特征根 的特征向量作為權(quán)向量w ，即wAwl=2 4 6 8比較尺度aij Saat

4、y等人提出19尺度aij 取值1,2,9及其互反數(shù)1,1/2, ,1/9尺度 1 3 5 7 9 相同 稍強 強 明顯強 絕對強aij = 1,1/2, ,1/9的重要性與上面相反 心理學(xué)家認(rèn)為成對比較的因素不宜超過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)向量，與實際對比發(fā)現(xiàn)， 19尺度較優(yōu). 便于定性到定量的轉(zhuǎn)化：成對比較陣和權(quán)向量一致性檢驗對A確定不一致的允許范圍已知：n 階一致陣的唯一非零特征根為n可證：n 階正互反陣最大特征根 n, 且 =n時為一致陣定義一致性指標(biāo):C

5、I 越大，不一致越嚴(yán)重RI000.580.901.121.241.321.411.451.491.51 n1234567891110為衡量CI 的大小，引入隨機一致性指標(biāo) RI隨機模擬得到aij , 形成A，計算CI 即得RI.定義一致性比率CR = CI/RI當(dāng)CR0.1時通過一致性檢驗Saaty的結(jié)果如下“選擇旅游地”中準(zhǔn)則層對目標(biāo)的權(quán)向量及一致性檢驗準(zhǔn)則層對目標(biāo)的成對比較陣最大特征根=5.073權(quán)向量(特征向量)w =(0.263,0.475,0.055,0.090,0.110)T一致性指標(biāo)隨機一致性指標(biāo) RI=1.12 (查表)一致性比率CR=0.018/1.12=0.0163)個頂點

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

7、客觀規(guī)律；方針政策例 能源利用系統(tǒng)的預(yù)測+-+-+-+v2v1v3v4v6v7v5帶符號有向圖G1=(V,E)的鄰接矩陣AV頂點集 , 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 的改變

8、量(沖量)沖量過程模型或能源利用系統(tǒng)的預(yù)測簡單沖量過程初始沖量p(0)中某個分量為1，其余為0的沖量過程.若開始時能源利用量有突然增加，預(yù)測系統(tǒng)的演變.設(shè)能源利用系統(tǒng)的 p(t)和v(t)-110-11-100011-100000100000010000000231-10010-12-21-110-11-11-10103-32-211-1簡單沖量過程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的特征

9、根記W的非零特征根為 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)定性 簡單沖量過程的穩(wěn)定性 改進的玫瑰形圖S* 帶符號的有向圖雙向連通，且存在一個位于所有回路上的中心頂點.回路長度 構(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)

10、v2v1 =1a3=(+1)v1v3v5v1+(-1)v1v4v7v1+(+1)v1v3v2v1=1, a4=0, 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 若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+簡單沖量

11、過程S*的穩(wěn)定性 社會經(jīng)濟系統(tǒng)的沖量過程 定性與定量相結(jié)合的系統(tǒng)分析方法, 適合社會經(jīng)濟 領(lǐng)域中復(fù)雜大系統(tǒng)的宏觀研究. 解決問題的關(guān)鍵是確定研究的對象及其范圍(系統(tǒng) 的邊界), 以及各因素間的相互關(guān)系. 以能源系統(tǒng)為例介紹有向圖和沖量過程的建模方法. 沖量過程模型及預(yù)測是簡單的, 但是穩(wěn)定性判斷及 其改進比較復(fù)雜.8.4 公平的席位分配每十年，美國聯(lián)邦政府進行一次全國人口普查(census)。各州在聯(lián)邦眾議院的代表名額也據(jù)此重新確定。公平的席位分配問題（apportionment）2000年人口普查后，猶他州（Utah）向聯(lián)邦政府提出控訴，說分配給卡羅萊納州的名額應(yīng)該是他們的。問題的數(shù)學(xué)本質(zhì)是

12、什么？事實上，過去200年來，美國國會在名額分配上打過多起法律官司，曾有過長期爭論并用過四種分配方案。一個簡單例子系別 學(xué)生 比例 20席的分配 人數(shù) （%） 比例 結(jié)果 甲 103 51.5 乙 63 31.5 丙 34 17.0總和 200 100.0 20.0 2021席的分配 比例 結(jié)果10.815 6.615 3.570 21.000 21問題三個系學(xué)生共200名(甲100，乙60，丙40)，代表會議共20席，按比例分配，三個系分別為10, 6, 4席.因?qū)W生轉(zhuǎn)系, 三系人數(shù)為103, 63, 34, 如何分配20席?若代表會議增加1席，如何分配21席?比例加慣例對丙系公平嗎？系別

13、學(xué)生 比例 20席的分配 人數(shù) （%） 比例 結(jié)果 甲 103 51.5 10.3 乙 63 31.5 6.3 丙 34 17.0 3.4 總和 200 100.0 20.0 20系別 學(xué)生 比例 20席的分配 人數(shù) （%） 比例 結(jié)果 甲 103 51.5 10.3 10 乙 63 31.5 6.3 6 丙 34 17.0 3.4 4總和 200 100.0 20.0 2021席的分配 比例 結(jié)果10.815 11 6.615 7 3.570 321.000 21模型已知: m方人數(shù)分別為 p1, p2, pm, 記總?cè)藬?shù)為 P= p1+p2+pm, 待分配的總席位為N. 各方先分配qi的整

14、數(shù)部分qi, 總余額為 記ri =qi-qi, 則第i方的分配名額ni為要求已知份額向量q=(q1, , qm)0, 找一個非負(fù)整數(shù)分配向量n=(n1, , nm), 使n與q最接近.比例加慣例法記 qi=Npi /P, 稱為第i方的份額(i =1,2, m) 背景Hamilton (比例加慣例) 方法 A. Hamilton提出的這種辦法1792年被美國國會否決 1850-1900年被美國國會采用(稱為Vinton法) 又稱為最大剩余法（GR: Greatest Remainders）或最大分?jǐn)?shù)法（LF: Largest Fractions） ，等等 席位悖論總席位增加反而可能導(dǎo)致某州席位減

15、少 1880年Alabama州曾遇到，又稱Alabama悖論 該方法的另一個重大缺陷： （下頁給例子） 人口悖論某州人口增加較多反而可能該州席位減少 Hamilton方法的不公平性1. p1, p2, pm不變, N的增加會使某個ni減少 (上例).2. N不變, pi 比pj的增長率大, 會使 ni減少 nj增加(下例).pinii=110311i=2637i=3343和20021pi1146434212ni116421pini1031063634420020pi114(+10.6%)6338(+11.8%)215ni116320“公平”分配方法衡量公平分配的數(shù)量指標(biāo) 人數(shù) 席位 A方 p1

16、 n1B方 p2 n2當(dāng)p1/n1= p2/n2 時，分配公平 p1/n1 p2/n2 對A的絕對不公平度p1=150, n1=10, p1/n1=15p2=100, n2=10, p2/n2=10p1=1050, n1=10, p1/n1=105p2=1000, n2=10, p2/n2=100p1/n1 p2/n2=5但后者對A的不公平程度已大大降低!雖二者的絕對不公平度相同若 p1/n1 p2/n2 ，對 不公平A p1/n1 p2/n2=5公平分配方案應(yīng)使 rA , rB 盡量小設(shè)A, B已分別有n1, n2 席, 若增加1席, 問應(yīng)分給A, 還是B?不妨設(shè)分配開始時 p1/n1 p2

17、/n2 ，即對A不公平. 對A的相對不公平度將絕對度量改為相對度量類似地定義 rB(n1,n2) 將一次性的席位分配轉(zhuǎn)化為動態(tài)的席位分配, 即“公平”分配方法若 p1/n1 p2/n2 ，定義1）若 p1/(n1+1) p2/n2 ，則這席應(yīng)給 A2）若 p1/(n1+1) p2/(n2+1)，應(yīng)計算rB(n1+1, n2)應(yīng)計算rA(n1, n2+1)若rB(n1+1, n2) p2/n2 問：p1/n1rA(n1, n2+1), 則這席應(yīng)給 B當(dāng) rB(n1+1, n2) 1)A=x, y, z, u, v, m位候選人集合( m 1)選民 i (I ) 對全體候選人投票 A的一個排序 p

18、i根據(jù)全體候選人的投票 pi (i = 1, 2, , n) 確定群體對A的一個排序 p (選舉結(jié)果 )選舉規(guī)則：pi (i = 1, 2, , n) p 的對應(yīng)關(guān)系（群體一致函數(shù)）選舉規(guī)則選舉規(guī)則排序pi (i = 1, 2, , n)和 p應(yīng)滿足的性質(zhì)(公理)： 對于任意的 x, y A, 或者 x優(yōu)于y (xy ), 或者 x 等同 y (xy ), 或者 x劣于y (xy時，選舉結(jié)果 p中才有xy （yuv， p2 : yxuv， p3 : xuvy， 選舉結(jié)果 p : xyuv簡單多數(shù)規(guī)則 使用方便 不滿足排序的可傳遞性例2 . p1 : xyz， p2 : yzx， p3 : zx

19、y，按規(guī)則 p 應(yīng)有 xy, yz, zx 破壞可傳遞性選舉規(guī)則2 記分規(guī)則（Borda數(shù)）Bi(x) pi 中劣于x的候選人數(shù)目(i = 1, 2, , n)例1. 設(shè)I=1, 2, 3對A=x, y, u, v的投票為 p1 : xyuv， p2 : yxuv， p3 : xuvy， x 在選舉中的分?jǐn)?shù), 稱Borda數(shù)當(dāng)且僅當(dāng)B(x) B(y)時，選舉結(jié)果 p中才有xyB1(x)=3, B2(x)=2, B3(x)=2 B(x)= 7B(y)=5, B(u)=3, B(v)=1p: xyuv例2. p1 : xyz， p2 : yzx， p3 : zxy，選舉規(guī)則2 記分規(guī)則（Borda

20、數(shù)）B(x)= B(y)=B(z)=3 p: xyz問題：投票時只要求順序，而記分規(guī)則考慮優(yōu)劣程度例3. 設(shè)I=1, 2, 3, 4對A=x, y, z, u, v的投票為 p1, p2, p3 : xyzuv， p4 : yzuvx，兩種規(guī)則都有不滿意之處，是否有適合所有情況的、公正合理的規(guī)則？公理化方法！ B(x)= 12, B(y)= 13違反多數(shù)人的意愿 yxArrow公理：選舉規(guī)則應(yīng)滿足的5條公理公理1 （選舉的完全性）選民對候選人的任何一種排序都是允許的.公理2 （選舉結(jié)果與選民投票的正相關(guān)性）對于pi (i = 1, 2, , n), 設(shè)p : xy. 若pi (i = 1, 2

21、, , n)中x, y的排序相同或x提前, 其他候選人排序不變，則p : xy.公理3 （無關(guān)候選人的獨立性）設(shè)A1是A的子集，若在pi 和pi (i = 1, 2, , n)中A1內(nèi)候選人的排序相同，則p 和p 中A1內(nèi)候選人的排序也相同.Arrow公理：選舉規(guī)則應(yīng)滿足的5條公理公理4 （選民的主權(quán)性）對任意候選人x, y，存在pi (i = 1, 2, , n) 使 p : xy.公理5 （選民的非獨裁性）不存在這樣的選民i ，使對任意候選人x, y， 只要pi: xy, 選舉規(guī)則就確定 p : xy.討論滿足上述5條公理的選舉規(guī)則 當(dāng)只有2位候選人時簡單多數(shù)規(guī)則滿足Arrow公理. 至少

22、有3位候選人時是否存在滿足Arrow公理的規(guī)則?Arrow定理當(dāng)至少有3位候選人時, 不存在滿足對公理3提出置疑3個p(4)出現(xiàn)矛盾A1外候選人的插入影響A1內(nèi)排序的優(yōu)劣Arrow公理的選舉規(guī)則公理3未考慮排序的優(yōu)劣怎么辦?聯(lián)合尺度下的選舉規(guī)則所有候選人按照同一指標(biāo)在0,1尺度上確定各自的位置.所有選民在0,1尺度上確定各自理想候選人的位置.00.10.70.91xyuv0.40.6123 p1 : uv yx， p2 : yvxu， p3 : vuyx 簡單多數(shù)規(guī)則得 p: vuyx若有奇數(shù)個選民, pi由聯(lián)合尺度得到, j是居中的那位選民, 則pj與簡單多數(shù)規(guī)則得到的p一致, 且滿足Arr

23、ow公理.候選人與選民的聯(lián)合尺度聯(lián)合尺度限制了投票情況, 才能夠滿足Arrow公理.最小距離意義下的選舉規(guī)則I=1, 2, , n 選民集合, A=x, y, z, u, v, 候選人集合P A的所有排序的集合, 合理地定義兩點pi 和 pj的“距離”pi P 中的一個點I 的一次投票: p1, pn從投票 p1, pn確定選舉結(jié)果歸結(jié)為, 在集合P 中找一個點 p, 使它到 n個點的總距離最小.可以用公理化的方法定義距離 最小距離意義下的選舉規(guī)則任意一對候選人x, y在選民投票pi , pj中的距離定義為pi , pj之間的距離定義為候選人成對地跑遍集合A例 p1 : xyz， p2 : x

24、zy 最小距離意義下的選舉規(guī)則從投票 p1, pn確定選舉結(jié)果 p的準(zhǔn)則.平均地照顧各位選民的意見.對與多數(shù)選民意見不同的少數(shù)選民的意見給予更多考慮.缺點 沒有確定p的有效方法 (基本上是枚舉法). p可能不唯一 (習(xí)題20).存在公正的選舉規(guī)則嗎 選舉規(guī)則 通過選民投票確定對候選人的排序. 規(guī)定排序的性質(zhì)提出一組公理尋求選舉規(guī)則. 若公理過多、過于嚴(yán)格可能得不到滿足公理的結(jié)果. 若公理過少、過于寬松可能無法得到結(jié)果或不惟一. Arrow得到了反面結(jié)果不存在滿足公理的選舉規(guī)則. 聯(lián)合尺度規(guī)則以縮小應(yīng)用范圍為代價換取一定結(jié)果. 最小距離規(guī)則不便于應(yīng)用.8.6 價格指數(shù)問題價格指數(shù)是消費品價格變化的度量.幾百年來，經(jīng)濟學(xué)家們提出了許多種價格指數(shù).如何評價這些價格指數(shù)的合理性？從種、種商品的價格指數(shù)談起對一種給定商品，原價p0, 現(xiàn)