第八章离散模型

第八章 离散模型,8.1,层次分析模型,8.2,循环比赛的名次,8.3,社会经济系统的冲量过程,8.4,效益的合理分配,y,离散模型,离散模型：差分方程（第,7,章）、整数规划（第,4,章）、图论、对策论、网络流、,分析社会经济系统的有力工具,只用到代数、集合及图论（少许）的知识,8.1,层次分析模型,背景,日常工作、生活中的决策问题,涉及经济、社会等方面的因素,作比较判断时人的主观选择起相当大的作用，各因素的重要性难以量化,Saaty,于1970,年代提出层次分析法,AHP,(Analytic Hierarchy Process),AHP,一种,定性与定量相结合的、系统化、层次化,的分析方法,目标层,O(,选择旅游地,),P,2,黄山,P,1,桂林,P,3,北戴河,准则层,方案层,C,3,居住,C,1,景色,C,2,费用,C,4,饮食,C,5,旅途,一.,层次分析法的基本步骤,例.,选择旅游地,如何在,3,个目的地中按照景色、费用、居住条件等因素选择,.,“选择旅游地”思维过程的归纳,将决策问题分为,3,个层次：目标层,O，,准则层,C，,方案层,P；,每层有若干元素，,各层元素间的关系用相连的直线表示。,通过相互比较确定各准则对目标的权重，及各方案对每一准则的权重。,将上述两组权重进行综合，确定各方案对目标的权重。,层次分析法将定性分析与定量分析结合起来完成以上步骤，给出决策问题的定量结果。,层次分析法的基本步骤,成对比较阵和权向量,元素之间两两对比，对比采用相对尺度,设要比较各准则,C,1,C,2,C,n,对目标,O,的重要性,A,成对比较阵,A,是正互反阵,要由,A,确定,C,1,C,n,对,O,的权向量,选择旅游地,成对比较的不一致情况,一致比较,不一致,允许不一致，但要确定不一致的允许范围,考察完全一致的情况,成对比较阵和权向量,成对比较完全一致的情况,满足,的,正互反阵,A,称,一致阵,，如,A,的秩为,1，,A,的唯一非零特征根为,n,A,的任一列向量是对应于,n,的特征向量,A,的归一化特征向量可作为权向量,对于不一致,(,但在允许范围内,),的成对比较阵,A,，,建议用对应于最大特征根,的特征向量作为权向量,w,，,即,一致阵性质,成对比较阵和权向量,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,尺度较优。,便于定性到定量的转化：,成对比较阵和权向量,一致性检验,对,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,的获利,公理化方法,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,个派别组成，人数分别为,4