离散数学模型.ppt

第八章 离散模型,8.1,层次分析模型,8.2,循环比赛的名次,8.3,社会经济系统的冲量过程,8.4,效益的合理分配,y,离散模型,离散模型：差分方程（第,7,章）、整数规划（第,4,章）、图论、对策论、网络流、,分析社会经济系统的有力工具,只用到代数、集合及图论（少许）的知识,8.1,层次分析模型,背景,日常工作、生活中的决策问题,涉及经济、社会等方面的因素,作比较判断时人的主观选择起相当大的作用，各因素的重要性难以量化,层次分析法,层次分析法是对一些较为复杂、较为模糊的问题作出决策的简易方法，它特别适用于那些难于完全定量分析的问题。当我们面对决策问题时，容易发现，影响我们作决策的因素很多，其中某些因素存在定量指标，可以给以度量，但也有些因素不存在定量指标，只能定性地比较它们的强弱。,Saaty,于,1970,年代提出层次分析法,AHP,(Analytic Hierarchy Process),AHP,一种,定性与定量相结合的、系统化、层次化,的分析方法,1,）建立层次分析结构模型,深入分析实际问题，将有关因素自上而下分层（目标,准则或指标,方案或对象），上层受下层影响，而层内各因素基本上相对独立。,2,）构造成对比较阵,用成对比较法和,1,9,尺度，构造各层对上一层每一因素的成对比较阵。,3,）计算权向量并作一致性检验,对每一成对比较阵计算最大特征根和特征向量，作一致性检验，若通过，则特征向量为权向量。,4,）计算组合权向量（作组合一致性检验,*,）,组合权向量可作为决策的定量依据。,一,.,层次分析法的基本步骤,1,建立层次结构模型,在用层次分析法研究问题时，首先要根据问题的因果关系并将这些关系分解成若干个层次。,同一层次的诸因素从属于上一层的因素或对上层因素有影响,同时又支配下一层的因素或受下层因素的作用。,较简单的问题通常可分解为目标层（最高层）、准则层（中间层）和方案措施层（最低层）。,中间可有,1,个或几个层次。,与其他决策问题一样，研究分析者不一定是决策者，不应自作主张地作出决策。,目标层,O(,选择旅游地,),P,2,黄山,P,1,桂林,P,3,北戴河,准则层,方案层,C,3,居住,C,1,景色,C,2,费用,C,4,饮食,C,5,旅途,例,.,选择旅游地,如何在,3,个目的地中按照景色、费用、居住条件等因素选择,.,“选择旅游地”思维过程的归纳,将决策问题分为,3,个层次：目标层,O,，,准则层,C,，,方案层,P,；,每层有若干元素，,各层元素间的关系用相连的直线表示。,通过相互比较确定各准则对目标的权重，及各方案对每一准则的权重。,将上述两组权重进行综合，确定各方案对目标的权重。,层次分析法将定性分析与定量分析结合起来完成以上步骤，给出决策问题的定量结果。,2,构造成对比较阵和权向量,元素之间两两对比，对比采用相对尺度,设要比较各准则,C,1,C,2,C,n,对目标,O,的重要性,A,成对比较阵,A,是正互反阵,要由,A,确定,C,1,C,n,对,O,的权向量,选择旅游地,成对比较的不一致情况,一致比较,不一致,正互反阵,A,称,一致阵,允许不一致，但要确定不一致的允许范围,定理,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,。（,证明从略）,对于不一致,(,但在允许范围内,),的成对比较阵,A,，,建议用对应于最大特征根,的特征向量作为权向量,w,，即,根据定理,1,2,，我们可以由,max,是否等于,n,来检验判断,矩阵,A,是否为一致矩阵。由于特征根连续地依赖于,aij,，,故,max,比,n,大得越多，,A,的非一致性程度也就越为严重，,max,对应的标准化特征向量也就越不能真实地反映出,X,=,x,1,xn,在对因素,Z,的影响中所占的比重。因此，,对决策者提供的判断矩阵有必要作一次一致性检验，,以决定是否能接受它。,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,尺度较优。,便于定性到定量的转化：,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,的结果如下,“,选择旅游地,”,中准则层对目标的权向量及一致性检验,准则层对目标的,成对比较阵,最大特征根,=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?,1,2,3,4,5,6,6,支球队比赛结果,排名次序为,1,，,3,，,2,，,5,，,4,，,6,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,带符号有向图,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,加权有向图,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,冲量过程,（,Pulse Process),研究由某元素,v,i,变化引起的系统的演变过程,v,i,(,t,),v,i,在时段,t,的,值,；,p,i,(,t,),v,i,在时段,t,的,改变量,(,冲量,),冲量过程模型,或,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,简单冲量过程,S,的稳定性,任意时段,S,的各元素的值和冲量是否为有限,(,稳定,),S,不稳定时如何改变可以控制的关系使之变为稳定,S,冲量稳定,对任意,i,t,|,p,i,(,t,)|,有界,S,值稳定,对任意,i,t,|,v,i,(,t,)|,有界,值稳定,冲量稳定,S,的稳定性取决于,W,的特征根,记,W,的非零特征根为,S,冲量稳定,|,|,1,S,冲量稳定,|,|,1,且均为单根,S,值稳定,S,冲量稳定,且,不等于,1,对于能源利用系统的邻接矩阵,A,特征多项式,能源利用系统存在,冲量不稳定,的简单冲量过程,简单冲量过程,S,的稳定性,简单冲量过程的稳定性,改进的玫瑰形图,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,简单冲量过程,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,若,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,+,8.4,效益的合理分配,例,甲乙丙三人合作经商，若甲乙合作获利,7,元，,甲丙合作获利,5,元，乙丙合作获利,4,元，,三人合作获利,11,元。又知每人单干获利,1,元。,问三人合作时如何分配获利？,记甲乙丙三人分配为,解不唯一,(5，3，3),(4，4，3),(5，4，2),(1),Shapley,合作对策,I,v,n,人合作对策，,v,特征函数,n,人从,v,(,I,),得到的分配，满足,v,(,s,),子集,s,的获利,特征函数实质上描述了各种合作产生的效益，也意味着全部合作对象参加合作是最好的。,核心,(Core):,对任意的子集,记,都有,用向量 表示合作后效益的分配，,其中 是分配给第个合作人的部分。,Shapley,提出了以下公理：,设,V,是,I,上的特征函数，是合作对策，则有,公理,1,合作获利对每人的分配与此人的标号无关。,公理,2,，即每人分配数的总和等于总获利数。,公理,3,若对所有包含的,i,的子集,S,有：,V(S-i)=V(S),，,=0,。,即若第,i,人在他参加的任一合作中均不,作出任何贡献，则他不应从合作中获利,公理,4,若此,n,个人同时进行两项互不影响的合作，则两项合作的分配也应互不影响，每人的分配额即两项合作单独进行时应分配数的和,。,公理化方法,s,子集,s,中的元素数目，,S,i,包含,i,的所有子集,由,s,决定的,“,贡献,”,的权重,Shapley,值,i,对合作,s,的,“,贡献,”,Shapley,合作对策,三人,(,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,合作对策的应用,例,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,污水处理的,5,种方案,1,）单独建厂,总投资,2,）,1,2,合作,3,）,2,3,合作,4,）,1,3,合作,总,投资,总投资,合作不会实现,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,如何分担？,特征函数,v,(,s,),联合,(,集,s,),建厂比单独建厂节约的投资,三,城从,节约投资,v,(,I,),中得到的分配,Shapley,合作对策,计算,城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,最大，如何解释？,合作对策的应用,例,2,派别在团体中的权重,90,人的团体由,3,个派别组成，人数分别为,40,30,20,人。团体表决时需过半数的赞成票方可通过。,虽然,3,派人数相差很大,若每个派别的成员同时投赞成票或反对票，用,Shapley,合作对策,计算,各派别在团体中的权重。,团体,I,=1,2,3,，,依次代表,3,个派别,=,否则,，,的成员超过,定义,特征函数,0,45,1,),(,s,s,v,优点：,公正、合理，有公理化基础。,如,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,个,),的特征函数，实际上常做不到。,设只知道,无,i,参加时,n-,1,方合作的获利,全体合作的获利,求解合作对策的其他方法,例,.,甲乙丙三人合作经商，若甲乙合作获利,7,元，,甲丙合作获利,5,元，乙丙合作获利,4,元，三人,合作获利,11,元。问三人合作时如何分配获利？,（,2,）协商解,1,1,将剩余获利 平均分配,模型,以,n-,1,方合作的获利为下限,求解,x,i,的,下限,（,3,）,Nash,解,为现状点（谈判时的威慑点）,在此基础上,“,均匀地,”,分配全体合作的获利,B,模型,平均分配获利,B,3,）,Nash,解,2,）协商解,（,4,）最小距离解,模型,第,i,方的边际效益,若令,4,）最小距离解,2,）协商解,（,5,）满意解,d,i,现状点,(,最低点,),e,i,理想点,(,最高点,),模型,5,）基于满意度的解,2,）协商解,（,6,）,Raiffi,解,与协商解,x,=(5,4,2),比较,求解合作对策的,6,种方法（可分为三类）,Shapley,合作对策,A,类,B,类,协商解,Nash,解,最小距离解,满意解,d,i,现状,e,i,理想,B,类,4,种方法相同,例：有一资方,(,甲,),和二劳方,(,乙,丙,),仅当资方与至少一劳方合作时才获利,10,元，应如何分配该获利？,Raiffi,解,C,类,B,类：计算简单，便于理解，可用于各方实力相差不大的情况；一般来说它偏袒强者。,C,类：,考虑了分配的上下限，又吸取了,Shapley,的思想，在一定程度上保护弱者。,A,类：公正合理；需要信息多，计算复杂。,求解合作对策的三类方法小结,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,）,简单多数规则的主要优点是简单易行，使用方便。但可惜的是这一规则有时会违反传递性,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,数规则得出,的结果未必合理,能找到一种在任何情况下都“公平”的选举规则吗,什么是“公平”的选举规则,“公平”的选举规则应当满足,以下,公理,公理,1,投票人对候选人排出的所有可能排列都是可以实现的。,公理,2,如果对所有的,i,，,有,(xy),i,，,则必须有,(xy),。,公理,3,如果在两次选举中，对任意,I,由，,。,公理,4,如果两次选举中，每个投票人对,x,、,y,的排序都未改变，则对,x,、,y,的排序两次结果也应相同。,公理,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,。,证明,V,xy,只能含有一个元素,某评选人,i,。,反证,假定,V,xy,至少含有两个元素，,则,V,xy,必可分解为两个非空集合的和,即,与 非空且不相交，且均不可能是任一对候选人的决定性集合,假设,根据公理,1,，以下选举是允许的：,当 时，,（,xyz,）,i,当 时，,（,zxy,）,i,当 时，,（,y,z,x,）,i,其中,z,是任一另外的候选人,考察选举结果,(xz),是不可能，否则 是,x,、,z,的决定性集合，故必,有,(z,x),。又,V,xy,是,x,、,y,的决定性能合，故必有,(xy),。,由传递性,(z,x),。,得,是,y,、,z,的决定性集合，从而导出矛盾。,以上证明说明,V,xy,不能分解,，即,V,xy,=i,，,i,为某一投票人。,进一步说明,：对于任意另外的候选人,z,，,V=i,也是,x,、,z,的决定性集合,。,考虑另一次选举,：,(x,yz),i,，而（,yzx,）,jI,显然，由于全体一致意见，（,yz,）,必成立。又,i,是,x,、,y,的决定性集合，故应有（,x,y,）。,于是，由传递性，必有（,x,z,）。,再由公理,4,，,y,的插入不应影响,x,、,z,的排序，故,i,也是,x,、,z,的决定性集合。类似还可证明，如果,是异议于,x,、,z,的任一候选人，,i,也是,w,、,z,的决定性集合，这就是说，,评选人,i,是选举的独裁者,。,Arrow,的公理系统隐含矛盾,例,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,，必须有,（,x,y,）,(4),再与第二次选举比较并根据公理,3,，则应有,（,x=z,）,(4),与第三次比较并根据公理,3,，应有,（,y=z,）,(4),x,y,，,x=z,与,y=z,居然同时成立,！,改进方案,一个可以考虑的改进方案为要求评选人给出他对每一候选人优劣程度的评价，然后按定量方式决定候选人的顺序，但矛盾仍然不能避免，总可以构造出类似于,Borda,数规则中例那样的例子来。,解决这一问题的另一途径是事先适当限制评选人的排序方式，使得可能出现的情况数减少，以便保证一个合理的选举规则的存在。,