资源描述
本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢,第八章 离散模型,8.1 层次分析模型,8.2 循环比赛名次,8.3 社会经济系统冲量过程,8.4,效益合理分配,y,1/84,离散模型,离散模型：差分方程（第7章）、整数规划（第4章）、图论、对策论、网络流、,分析社会经济系统有力工具,只用到代数、集合及图论（少许）知识,2/84,8.1 层次分析模型,背景,日常工作、生活中决议问题,包括经济、社会等方面原因,作比较判断时人主观选择起相当大作用，各原因主要性难以量化,3/84,层次分析法,层次分析法是对一些较为复杂、较为含糊问题作出决议简易方法，它尤其适合用于那些难于完全定量分析问题。当我们面对决议问题时，轻易发觉，影响我们作决议原因很多，其中一些原因存在定量指标，能够给以度量，但也有些原因不存在定量指标，只能定性地比较它们强弱。,Saaty于1970年代提出层次分析法,AHP,(Analytic Hierarchy Process),AHP一个,定性与定量相结合、系统化、层次化,分析方法,4/84,1）建立层次分析结构模型,深入分析实际问题，将相关原因自上而下分层（目标准则或指标方案或对象），上层受下层影响，而层内各原因基本上相对独立。,2）结构成对比较阵,用成对比较法和,1,9,尺度，结构各层对上一层每一原因成对比较阵。,3）计算权向量并作一致性检验,对每一成对比较阵计算最大特征根和特征向量，作一致性检验，若经过，则特征向量为权向量。,4）计算组合权向量（作组合一致性检验,*,）,组合权向量可作为决议定量依据。,一.层次分析法基本步骤,5/84,1 建立层次结构模型,在用层次分析法研究问题时，首先要依据问题因果关系并将这些关系分解成若干个层次。,同一层次诸原因隶属于上一层原因或对上层原因有影响,同时又支配下一层原因或受下层原因作用。,较简单问题通常可分解为目标层（最高层）、准则层（中间层）和方案办法层（最低层）。,中间可有1个或几个层次。,与其它决议问题一样，研究分析者不一定是决议者，不应自作主张地作出决议。,6/84,目标层,O(选择旅游地),P,2,黄山,P,1,桂林,P,3,北戴河,准则层,方案层,C,3,居住,C,1,景色,C,2,费用,C,4,饮食,C,5,旅途,例.选择旅游地,怎样在3个目标地中按照景色、费用、居住条件等原因选择.,7/84,“选择旅游地”思维过程归纳,将决议问题分为3个层次：目标层O，准则层C，方案层P；每层有若干元素，各层元素间关系用相连直线表示。,经过相互比较确定各准则对目标权重，及各方案对每一准则权重。,将上述两组权重进行综合，确定各方案对目标权重。,层次分析法将定性分析与定量分析结合起来完成以上步骤，给出决议问题定量结果。,8/84,2 结构成对比较阵和权向量,元素之间两两对比，对比采取相对尺度,设要比较各准则C,1,C,2,C,n,对目标O主要性,A,成对比较阵,A,是正互反阵,要由,A,确定C,1,C,n,对O权向量,选择旅游地,9/84,成对比较不一致情况,一致比较,不一致,正互反阵,A,称,一致阵,允许不一致，但要确定不一致允许范围,10/84,11/84,定理2,若A为一致矩阵，则,（1）A必为正互反矩阵。,（2）A转置矩阵A,T,也是一致矩阵。,（3）A任意两行成百分比，百分比因子（即w,i,/w,j,）大于零，从而,rank,（A）=1（一样，A任意两列也成百分比）。,（4）A最大特征根,max,=,n,，其中,n,为矩阵A阶。A其余特征根均为零。,（5）若A最大特征根,max,对应特征向量为,W,=（w,1,w,n,）,I,，则,a,ij,=w,i,/w,j,，,i,j,=1,2,n,。,定理1,正互反矩阵A最大特征根,max,必为正实数，其对应特征向量全部分量均为正实数。A其余特征根模均严格小于,max,。（证实从略）,12/84,对于不一致(但在允许范围内)成对比较阵,A,，提议用对应于最大特征根,特征向量作为权向量,w,，即,依据定理1,2，我们能够由max是否等于,n,来检验判断,矩阵A是否为一致矩阵。因为特征根连续地依赖于,aij,，,故max比,n,大得越多，A非一致性程度也就越为严重，,max对应标准化特征向量也就越不能真实地反应出,X,=,x,1,xn,在对原因Z影响中所占比重。所以，,对决议者提供判断矩阵有必要作一次一致性检验，,以决定是否能接收它。,13/84,2 4 6 8,比较尺度,a,ij,Saaty等人提出19尺度,a,ij,取值1,2,9及其互反数1,1/2,1/9,尺度 1 3 5 7 9,相同 稍强 强 显著强 绝对强,a,ij,=,1,1/2,1/9,主要性与上面相反,心理学家认为成对比较原因不宜超出9个,用13,15,117,1,p,9,p,(,p,=2,3,4,5),d,+0.1,d,+0.9(,d,=1,2,3,4)等27种比较尺度对若干实例结构成对比较阵，算出权向量，与实际对比发觉，19尺度较优。,便于定性到定量转化：,14/84,3 一致性检验,对,A,确定不一致允许范围,已知：,n,阶一致阵唯一非零特征根为,n,可证：,n,阶正互反阵最大特征根,n,且,=,n,时为一致阵,定义一致性指标:,CI,越大，不一致越严重,RI,0,0,0.58,0.90,1.12,1.24,1.32,1.41,1.45,1.49,1.51,n,1,2,3,4,5,6,7,8,9,11,10,为衡量,CI,大小，引入,随机一致性指标,RI,随机模拟得到,a,ij,形成,A,，计算,CI,即得,RI,。,定义一致性比率,CR=CI,/,RI,当,CR,0.1时，经过一致性检验,Saaty结果以下,15/84,“选择旅游地”中准则层对目标权向量及一致性检验,准则层对目标,成对比较阵,最大特征根,=5.073,权向量(特征向量),w,=(0.263,0.475,0.055,0.090,0.110),T,一致性指标,随机一致性指标,RI=,1.12(,查表),一致性比率,CR,=0.018/1.12=0.0163)个顶点双向连通竞赛图，存在正整数,r,，使邻接矩阵,A,满足,A,r,0，,A,称,素阵,素阵,A,最大特征根为正单根,，对应正特征向量,s,，,且,排名为1，2，4，3,用,s,排名,1,2,3,4,(4),1,2,3,4?,40/84,1,2,3,4,5,6,6支球队比赛结果,排名次序为1，3，2，5，4，6,41/84,42/84,43/84,v,1,能源利用量；,v,2,能源价格；,v,3,能源生产率；,v,4,环境质量；,v,5,工业产值；,v,6,就业机会；,v,7,人口总数。,8.3 社会经济系统冲量过程,系统元素图顶点,元素间影响带方向弧,影响正反面弧旁+、号,带符号有向图,影响直接影响,符号客观规律；方针政策,例 能源利用系统预测,+,-,+,-,+,+,+,+,-,-,+,v,2,v,1,v,3,v,4,v,6,v,7,v,5,44/84,带符号有向图G,1,=(,V,E,)邻接矩阵,A,V,顶点集,E,弧集,定性模型,-,v,i,v,j,+,某时段,v,i,增加造成下时段,v,j,增加,降低,带符号有向图G,1,+,-,+,-,+,+,+,+,-,-,+,v,2,v,1,v,3,v,4,v,6,v,7,v,5,45/84,加权有向图G,2,及其邻接矩阵,W,定量模型,某时段,v,i,增加1单位造成下时段,v,j,增加,w,ij,单位,v,7,0.3,1,1.5,1,1.5,1.2,0.8,-,2,-,2,-,0.7,-,0.5,v,1,v,2,v,3,v,4,v,5,v,6,加权有向图G,2,46/84,冲量过程,（Pulse Process),研究由某元素,v,i,改变引发系统演变过程,v,i,(,t,),v,i,在时段,t,值,；,p,i,(,t,),v,i,在时段,t,改变量(冲量),冲量过程模型,或,47/84,2,3,1,-1,0,0,1,0,-1,2,-2,1,-1,1,0,-1,1,-1,1,-1,0,1,0,3,-3,2,-2,1,1,-1,能源利用系统预测,简单冲量过程初始冲量,p,(0)中,某个分量为1，其余为0冲量过程,若开始时能源利用量有突然增加，预测系统演变,设,能源利用系统,p,(,t,)和,v,(,t,),-,1,1,0,-1,1,-1,0,0,0,1,1,-1,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,48/84,简单冲量过程,S,稳定性,任意时段S各元素值和冲量是否为有限(稳定),S不稳定时怎样改变能够控制关系使之变为稳定,S,冲量稳定,对任意,i,t,|,p,i,(,t,)|有界,S,值稳定,对任意,i,t,|,v,i,(,t,)|有界,值稳定,冲量稳定,S稳定性取决于,W,特征根,记,W,非零特征根为,49/84,S冲量稳定,|,|,1,S冲量稳定,|,|,1且均为单根,S值稳定,S冲量稳定,且,不等于1,对于能源利用系统邻接矩阵,A,特征多项式,能源利用系统存在,冲量不稳定,简单冲量过程,简单冲量过程,S,稳定性,50/84,简单冲量过程稳定性,改进玫瑰形图S,*,带符号有向图双向连通，且存在一个位于全部回路上中心顶点。,回路长度,组成回路边数,回路符号,组成回路各有向边符号+1或-1之乘积,a,k,长度为,k,回路符号和,r,使,a,k,不等于,0最大整数,S,*,冲量稳定,若S,*,冲量稳定，则S,*,值稳定,+,-,+,-,+,+,+,+,-,-,+,v,2,v,1,v,3,v,4,v,6,v,7,v,5,51/84,简单冲量过程S,*,稳定性,a,1,=0,a,2,=,(-1),v,1,v,2,(-1),v,2,v,1,=1,a,3,=(+1),v,1,v,3,v,5,v,1,+(-1),v,1,v,4,v,7,v,1,+(+1),v,1,v,3,v,2,v,1,=1,a,4,=0,a,5,=1,r,=5,S,*,冲量稳定,(-1),v,1,v,2,(+1),v,1,v,2,(由勉励利用变为限制利用),a,2,=,-,1,+,S,*,冲量不稳定,A,特征多项式,S,*,冲量稳定,S,*,冲量稳定,|,|,1且均为单根,v,1,利用量,v,2,价格,v,7,+,-,+,-,+,+,+,+,-,-,+,v,2,v,1,v,3,v,4,v,6,v,5,52/84,若,S,*,冲量稳定，则S,*,值稳定,S,*,冲量稳定,v,3,能源生产率,v,5,工业产值,(-1),v,3,v,5,违反客观规律,S,*,值不稳定,S,*,值稳定,(+1),v,3,v,5,(-1),v,3,v,5,能源利用系统值不应稳定？,-,+,-,+,+,+,+,+,-,-,+,v,2,v,1,v,3,v,4,v,6,v,7,v,5,+,53/84,8.4,效益合理分配,例,甲乙丙三人合作经商，若甲乙合作赢利7元，,甲丙合作赢利5元，乙丙合作赢利4元，,三人合作赢利11元。又知每人单干赢利1元。,问三人合作时怎样分配赢利？,记甲乙丙三人分配为,解不唯一,(5，3，3),(4，4，3),(5，4，2),54/84,(1),Shapley,合作对策,I,v,n,人合作对策，,v,特征函数,n,人从,v,(,I,)得到分配，满足,v,(,s,)子集,s,赢利,55/84,特征函数实质上描述了各种合作产生效益，也意味着全部合作对象参加合作是最好。,关键(Core):对任意子集 ,记 ,都有,用向量 表示合作后效益分配，,其中 是分配给第个合作人部分。,56/84,Shapley,提出了以下公理：,设,V,是,I,上特征函数，是合作对策，则有,公理,1,合作赢利对每人分配与此人标号无关。,公理,2,，即每人分配数总和等于总赢利数。,公理,3,若对全部包含i子集S有：,V(S-i)=V(S)，,=0。,即若第,i,人在他参加任一合作中均不,作出任何贡献，则他不应从合作中赢利,公理,4,若此n个人同时进行两项互不影响合作，则两项合作分配也应互不影响，每人分配额即两项合作单独进行时应分配数和,。,57/84,公理化方法,s,子集,s,中元素数目，,S,i,包含,i,全部子集,由,s,决定“贡献”权重,Shapley值,i,对合作,s,“贡献”,Shapley,合作对策,58/84,三人(,I,=1,2,3)经商中甲分配,x,1,计算,1/3 1/6 1/6 1/3,1 1 2 1 3,I,1 7 5 11,0 1 1 4,1 6 4 7,1/3 1 2/3 7/3,x,1,=13/3,类似可得,x,2,=23/6,x,3,=17/6,1 2 2 3,59/84,合作对策应用,例1 污水处理费用合理分担,20km,38km,河流,三城镇地理位置示意图,1,2,3,污水处理，排入河流,三城镇可单独建处理厂，或联合建厂(用管道将污水由上游城镇送往下游城镇),Q,1,=5,Q,3,=5,Q,2,=3,Q,污水量，,L,管道长度,建厂费用,P,1,=73,Q,0.712,管道费用,P,2,=0.66,Q,0.51,L,60/84,污水处理,5,种方案,1）单独建厂,总投资,2）1,2合作,3）2,3合作,4）1,3合作,总,投资,总投资,合作不会实现,61/84,5）三城合作总投资,D,5,最小,应联合建厂,建厂费：,d,1,=73,(5+3+5),0.712,=453,12管道费：,d,2,=0.66 5,0.51,20=30,23管道费：,d,3,=0.66(5+3),0.51,38=73,D,5,城3提议：,d,1,按 5:3:5分担,d,2,d,3,由城1,2担负,城2提议：,d,3,由城1,2按 5:3分担,d,2,由城1,担负,城1计算：,城3分担,d,1,5/13=174C(3),城2分担,d,1,3/13+,d,3,3/8,=132C(1),不一样意,D,5,怎样分担？,62/84,特征函数,v,(,s,)联合(集,s,)建厂比单独建厂节约投资,三,城从节约投资,v,(,I,)中得到分配,Shapley,合作对策,63/84,计算,城1从节约投资中得到分配,x,1,1 1 2 1 3 I,0 40 0 64,0 0 0 25,0 40 0 39,1 2 2 3,1/3 1/6 1/6 1/3,0 6.7,0 13,x,1,=19.7,城1 C(1)-,x,1,=,210.4,城2 C(2)-,x,2,=,127.8,城3 C(3)-,x,3,=,217.8,三城在总投资556中分担,x,2,=32.1,x,3,=12.2,x,2,最大，怎样解释？,64/84,合作对策应用,例2 派别在团体中权重,90人团体由3个派别组成，人数分别为40,30,20人。团体表决时需过半数赞成票方可经过。,即使3派人数相差很大,若每个派别组员同时投赞成票或反对票，用Shapley,合作对策计算,各派别在团体中权重。,团体,I,=1,2,3，依次代表3个派别,=,不然,，,组员超出,定义,特征函数,0,45,1,),(,s,s,v,65/84,优点：,公正、合理，有公理化基础。,如,n,个单位治理污染,通常知道第,i,方单独治理投资,y,i,和,n,方共同治理投资,Y,及第,i,方不参加时其余,n,-1方投资,z,i,(,i,=1,2,n,).,确定共同治理时各方分担费用。,其它,v,(,s,)均不知道,无法用Shapley,合作对策求解,Shapley,合作对策小结,若定义特征函数为合作赢利(节约投资)，则有,缺点：,需要知道全部合作赢利，即要定义,I,=1,2,n,全部子集(共2,n,-1个)特征函数，实际上常做不到。,66/84,设只知道,无,i,参加时,n-,1方合作赢利,全体合作赢利,求解合作对策其它方法,例.甲乙丙三人合作经商，若甲乙合作赢利7元，,甲丙合作赢利5元，乙丙合作赢利4元，三人,合作赢利11元。问三人合作时怎样分配赢利？,67/84,（2）协商解,1,1,将剩下赢利 平均分配,模型,以,n-,1方合作赢利为下限,求解,x,i,下限,68/84,（3）Nash解,为现实状况点（谈判时威慑点）,在此基础上“均匀地”分配全体合作赢利,B,模型,平均分配赢利B,3）Nash解,2）协商解,69/84,（4）最小距离解,模型,第,i,方边际效益,若令,4）最小距离解,2）协商解,70/84,（5）满意解,d,i,现实状况点(最低点),e,i,理想点(最高点),模型,5）基于满意度解,2）协商解,71/84,（6）,Raiffi,解,与协商解,x,=(5,4,2)比较,72/84,求解合作对策,6,种方法（可分为三类）,Shapley,合作对策,A类,B类,协商解,Nash解,最小距离解,满意解,d,i,现实状况,e,i,理想,B类4种方法相同,73/84,例：有一资方(甲)和二劳方(乙,丙),仅当资方与最少一劳方合作时才赢利10元，应怎样分配该赢利？,Raiffi,解,C类,74/84,B类：计算简单，便于了解，可用于各方实力相差不大情况；普通来说它偏袒强者。,C类：考虑了分配上下限，又吸收了Shapley思想，在一定程度上保护弱者。,A类：公正合理；需要信息多，计算复杂。,求解合作对策三类方法小结,75/84,8.5,公平选举是可能吗?,什么是选举,所谓选举，其实质就是在评选人对候选人先后（优劣）次序排队基础上，依据某一事先要求选举规则决定出候选人一个先后次序，即得出选举结果。现用,I=1,2,n,表示评选人集合，用有限集A=x,y,表示候选人集合，用,=,y),i,表示评选人,i,认为x优于y，用,(xy),表示选举结果为x优于y并用,p,i,表示评选人i排序，,p,表示选举结果。,A,排序应满足,以下,性质：,(1),择一性,关系式(xy)、(x=y)、(xy),i,评选人超出半数时选举结果才为,(xy),。,有时要超出,2/3,多数等,例1,设,I=1,2,3,A=x,y,u,v，,三位评选人选票为,p,1,:xyu=v,p,2,:yxuv,p,3,:x=uvy,依据选举规划，结果应为,P:xyuv,例2,设,I=1,2,3,A=x,y,z,p,1,:xyz,p,2,:yzx,p,3,:zxy,依据规则，自然应有,(xy),(yz),和,(zx),违反传递性（2）,简单多数规则主要优点是简单易行，使用方便。但可惜是这一规则有时会违反传递性,77/84,Borda,数规则,记,B,i,(x),为,p,1,中劣于x候选人数目，记 ，称,B(x),为x,Borda,数，,Borda,数规则要求,按,Borda,数大小排列候选人优劣次序，即当,B(x)B(y),时有,(xy),，两关系式中等号必须同时成立。,对于例,子,，,计算出,B(x)=B(y)=B(z)=3,故选举结果为,x=y=z,用,Borda,数规则得出,结果更合乎常理,例3,I=1,2,3,4,A=x,y,z,u,v，,选票情况为,p,1,p,2,p,3,:xyzuv,P,4,:yzuvx,计算得,B(x)=12，B(y)=13,故选举结果为,yx,但有三人认为,x,优于,y,用,Borda,数规则得出,结果未必合理,78/84,能找到一个在任何情况下都“公平”选举规则吗,什么是“公平”选举规则,“公平”选举规则应该满足,以下,公理,公理1,投票人对候选人排出全部可能排列都是能够实现。,公理2,假如对全部,i，,有,(xy),i,，,则必须有,(xy)。,公理3,假如在两次选举中，对任意,I,由，,。,公理4,假如两次选举中，每个投票人对,x、y,排序都未改变，则对,x、y,排序两次结果也应相同。,79/84,公理5,不存在这么投票人,i，,使得对任意一对候选人,x、y，,只要,有,(xy),i,，就必有,(xy)。,有满足上述公理选举规则吗,Arrow,不可能性定理使上述想法终止,定理,假如最少有三名候选人，则满足公理1,公理5选举规划,实际上是不可能存在。,证：,将证实由公理1,公理4必可导出存在一个独裁者，从而违反了公理5,首先引入决定性集合概念。,称I子集,V,xy,为候选人x、y决定性集合，假如由全部,V,xy,中I,有(xy),i,必可导出(xy)。,显然决定性集合是必定存在，由公理2或实际一次选举得到。,找出全部决定性集合中含元素最少一个，不妨仍记为,V,xy,。,80/84,证实,V,xy,只能含有一个元素某评选人,i。,反证,假定,V,xy,最少含有两个元素，,则,V,xy,必可分解为两个非空集合和,即,与 非空且不相交，且均不可能是任一对候选人决定性集合,假设,依据公理1，以下选举是允许：,当 时，,（xyz）,i,当 时，,（zxy）,i,当 时，,（yzx）,i,其中z是任一另外候选人,考查选举结果,(xz)是不可能，不然 是x、z决定性集合，故必,有(zx)。又,V,xy,是x、y决定性能合，故必有(xy)。,由传递性(zx)。得 是y、z决定性集合，从而导出矛盾。,以上证实说明,V,xy,不能分解,，即,V,xy,=i，i,为某一投票人。,81/84,深入说明,：对于任意另外候选人,z，V=i,也是,x、z,决定性集合,。,考虑另一次选举,：,(xyz),i,，而（yzx）,jI,显然，因为全体一致意见，（yz）必成立。又i是x、y决定性集合，故应有（xy）。于是，由传递性，必有（xz）。再由公理4，y插入不应影响x、z排序，故i也是x、z决定性集合。类似还可证实，假如是异议于x、z任一候选人，i也是w、z决定性集合，这就是说，,评选人i是选举独裁者,。,Arrow,公理系统隐含矛盾,82/84,例4,设,I=1,2,A=x,y,z，,考查以下四次选举：,（第一次）,x,y,z,（第三次）,y,z,x,x,y,z z,y,x,结果应有,x,y,合理结果,y=z,（第二次）,x,z,y,（第四次）,x,y,z,z,x,y z,x,y,合理结果,x=z,结果？,由公理1，第四次选举应该是,有效,由公理2，必须有,（xy）,(4),再与第二次选举比较并依据公理3，则应有,（x=z）,(4),与第三次比较并依据公理3，应有,（y=z）,(4),xy，x=z与y=z,竟然同时成立,！,83/84,改进方案,一个能够考虑改进方案为要求评选人给出他对每一候选人优劣程度评价，然后按定量方式决定候选人次序，但矛盾依然不能防止，总能够结构出类似于,Borda,数规则中例那样例子来。,处理这一问题另一路径是事先适当限制评选人排序方式，使得可能出现情况数降低，方便确保一个合理选举规则存在。,84/84,
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
