M08数学建模燕大省名师优质课赛课获奖课件市赛课一等奖课件.ppt

本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。谢谢您,第八章 离散模型,8.1 层次分析模型,8.2 循环比赛名次,8.3 社会经济系统冲量过程,8.4,效益合理分配,y,第1页,离散模型,离散模型：差分方程（第7章）、整数规划（第4章）、图论、对策论、网络流、,分析社会经济系统有力工具,只用到代数、集合及图论（少许）知识,第2页,8.1 层次分析模型,背景,日常工作、生活中决议问题,包括经济、社会等方面原因,作比较判断时人主观选择起相当大作用，各原因主要性难以量化,Saaty于1970年代提出层次分析法,AHP,(Analytic Hierarchy Process),AHP一个,定性与定量相结合、系统化、层次化,分析方法,第3页,目标层,O(选择旅游地),P,2,黄山,P,1,桂林,P,3,北戴河,准则层,方案层,C,3,居住,C,1,景色,C,2,费用,C,4,饮食,C,5,旅途,一.层次分析法基本步骤,例.选择旅游地,怎样在3个目标地中按照景色、费用、居住条件等原因选择.,第4页,“选择旅游地”思维过程归纳,将决议问题分为3个层次：目标层O，准则层C，方案层P；每层有若干元素，各层元素间关系用相连直线表示。,经过相互比较确定各准则对目标权重，及各方案对每一准则权重。,将上述两组权重进行综合，确定各方案对目标权重。,层次分析法将定性分析与定量分析结合起来完成以上步骤，给出决议问题定量结果。,第5页,层次分析法基本步骤,成对比较阵和权向量,元素之间两两对比，对比采取相对尺度,设要比较各准则C,1,C,2,C,n,对目标O主要性,A,成对比较阵,A,是正互反阵,要由,A,确定C,1,C,n,对O权向量,选择旅游地,第6页,成对比较不一致情况,一致比较,不一致,允许不一致，但要确定不一致允许范围,考查完全一致情况,成对比较阵和权向量,第7页,成对比较完全一致情况,满足,正互反阵,A,称,一致阵,，如,A,秩为1，,A,唯一非零特征根为,n,A,任一列向量是对应于,n,特征向量,A,归一化特征向量可作为权向量,对于不一致(但在允许范围内)成对比较阵,A,，提议用对应于最大特征根,特征向量作为权向量,w,，即,一致阵性质,成对比较阵和权向量,第8页,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尺度较优。,便于定性到定量转化：,成对比较阵和权向量,第9页,一致性检验,对,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结果以下,第10页,“选择旅游地”中准则层对目标权向量及一致性检验,准则层对目标,成对比较阵,最大特征根,=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?,第36页,1,2,3,4,5,6,6支球队比赛结果,排名次序为1，3，2，5，46,第37页,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,第38页,带符号有向图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,第39页,加权有向图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,第40页,冲量过程,（Pulse Process),研究由某元素,v,i,改变引发系统演变过程,v,i,(,t,),v,i,在时段,t,值,；,p,i,(,t,),v,i,在时段,t,改变量(冲量),冲量过程模型,或,第41页,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,第42页,简单冲量过程,S,稳定性,任意时段S各元素值和冲量是否为有限(稳定),S不稳定时怎样改变能够控制关系使之变为稳定,S,冲量稳定,对任意,i,t,|,p,i,(,t,)|有界,S,值稳定,对任意,i,t,|,v,i,(,t,)|有界,值稳定,冲量稳定,S稳定性取决于,W,特征根,记,W,非零特征根为,第43页,S冲量稳定,|,|,1,S冲量稳定,|,|,1且均为单根,S值稳定,S冲量稳定,且,不等于1,对于能源利用系统邻接矩阵,A,特征多项式,能源利用系统存在,冲量不稳定,简单冲量过程,简单冲量过程,S,稳定性,第44页,简单冲量过程稳定性,改进玫瑰形图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,第45页,简单冲量过程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,第46页,若,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,+,第47页,8.4,效益合理分配,例,甲乙丙三人合作经商，若甲乙合作赢利7元，,甲丙合作赢利5元，乙丙合作赢利4元，,三人合作赢利11元。又知每人单干赢利1元。,问三人合作时怎样分配赢利？,记甲乙丙三人分配为,解不唯一,(5，3，3),(4，4，3),(5，4，2),第48页,(1),Shapley,合作对策,I,v,n,人合作对策，,v,特征函数,n,人从,v,(,I,)得到分配，满足,v,(,s,)子集,s,赢利,第49页,公理化方法,s,子集,s,中元素数目，,S,i,包含,i,全部子集,由,s,决定“贡献”权重,Shapley值,i,对合作,s,“贡献”,Shapley,合作对策,第50页,三人(,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,第51页,合作对策应用,例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,第52页,污水处理,5,种方案,1）单独建厂,总投资,2）1,2合作,3）2,3合作,4）1,3合作,总,投资,总投资,合作不会实现,第53页,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,怎样分担？,第54页,特征函数,v,(,s,)联合(集,s,)建厂比单独建厂节约投资,三,城从节约投资,v,(,I,)中得到分配,Shapley,合作对策,第55页,计算,城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,最大，怎样解释？,第56页,合作对策应用,例2 派别在团体中权重,90人团体由3个派别组成，人数分别为40,30,20人。团体表决时需过半数赞成票方可经过。,即使3派人数相差很大,若每个派别组员同时投赞成票或反对票，用Shapley,合作对策计算,各派别在团体中权重。,团体,I,=1,2,3，依次代表3个派别,=,不然,，,组员超出,定义,特征函数,0,45,1,),(,s,s,v,第57页,优点：,公正、合理，有公理化基础。,如,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个)特征函数，实际上常做不到。,第58页,设只知道,无,i,参加时,n-,1方合作赢利,全体合作赢利,求解合作对策其它方法,例.甲乙丙三人合作经商，若甲乙合作赢利7元，,甲丙合作赢利5元，乙丙合作赢利4元，三人,合作赢利11元。问三人合作时怎样分配赢利？,第59页,（2）协商解,1,1,将剩下赢利 平均分配,模型,以,n-,1方合作赢利为下限,求解,x,i,下限,第60页,（3）Nash解,为现实状况点（谈判时威慑点）,在此基础上“均匀地”分配全体合作赢利,B,模型,平均分配赢利B,3）Nash解,2）协商解,第61页,（4）最小距离解,模型,第,i,方边际效益,若令,4）最小距离解,2）协商解,第62页,（5）满意解,d,i,现实状况点(最低点),e,i,理想点(最高点),模型,5）基于满意度解,2）协商解,第63页,（6）,Raiffi,解,与协商解,x,=(5,4,2)比较,第64页,求解合作对策,6,种方法（可分为三类）,Shapley,合作对策,A类,B类,协商解,Nash解,最小距离解,满意解,d,i,现实状况,e,i,理想,B类4种方法相同,第65页,例：有一资方(甲)和二劳方(乙,丙),仅当资方与最少一劳方合作时才赢利10元，应怎样分配该赢利？,Raiffi,解,C类,第66页,B类：计算简单，便于了解，可用于各方实力相差不大情况；普通来说它偏袒强者。,C类：考虑了分配上下限，又吸收了Shapley思想，在一定程度上保护弱者。,A类：公正合理；需要信息多，计算复杂。,求解合作对策三类方法小结,第67页,