数学建模-B题-球队排名问题-答案详解

2010高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：参赛队员(打印并签名)：1.2.3.指导教师或指导教师组负责人(打印并签名)：日期：年月日赛区评阅编号（由赛区组委会评阅前进行编号）：2010高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：1一个给足球队排名次的方法戚立峰毛威马斌（北京大学数学系,100871）指导教师樊启洪摘要本文利用层次分析法建立了一个为足球排名次的数学模型．它首先用来排名次的数据是否充分做出判断,在能够排名次时对数据的可依赖程度做出估计,然后给出名次．文中证明了这个名次正是比赛成绩所体现的各队实力的顺序．文中将看到此模型充分考虑了排名结果对各场比赛的重要性的反馈影响,基本上消除了由于比赛对手的强弱不同造成的不公平现象．文中还证明了模型的稳定性,这保证了各队在发挥水平上的小的波动不会对排名顺序造成大的变动．本模型比较完满地解决了足球队排名次问题,而且经过简单修改,它可以适用于任何一种对抗型比赛的排名．2§1问题的提出及分析本题的表1给出的是我国12支足球队在1988-1989年全国甲级联赛中的成绩,要求通过建立数学模型,对各队进行排名次．按照通常的理解,排名的目的是根据比赛成绩排出反映各队真实实力状况的一个顺序．为达到这一点,一个好的排名算法应满足下面一些基本要求：（1）保序性；（2）稳定性；（3）能够处理不同场比赛的权重；（4）能够判断成绩表的可约性；（5）能够准确地进行补残；（6）容忍不一致现象；（7）对数据可依赖程度给出较为精确的描述．可以想象,各队的真实实力水平在成绩表中反映出来（见§3假定Ⅱ）,所以根据排名目的,我们要求排名顺序与成绩表反映的各队实力水平的顺序是一致的,这就是要求（1）．也就是说,如果a比b表现出色,a的名次就应排在b前面．但a比b出色不能只是由a对b这一场比赛所决定,必须参考a,b相对于其他队的成绩,像a平c,c胜d,d平b这组比赛对a,b的相对表现是有影响的．为使一个算法满足保序性,就必须充分考虑到将a,b连结起来的所有场比赛．下面的例子表明积分法布满足保序性．例1a平c,c胜d,d平b,a平b．在上述比赛中a表现应比b出色,但按积分法计算a,b都积2分．其原因就在于积分法没有把a平c,c胜d,d平b这组比赛中所体现的a,b实力对比情况考虑进去；要求（2）就是说成绩表小的变动不会对排名结果造成巨大影响．这是由于球队发挥水平存在正常波动而必须提供的,如果这种正常的小波动引起名次的巨大变化,那么排名就不令人信服；要求（3）使得不同场比赛在排名中的地位不同,这是因为在实际比赛中,往往会有的队不幸遇到较强的队而输掉．为了避免由于对手的强弱不同造成的不公平,要求（3）是必须的．但现在的排名制度大都满足不了要求（3）,以至于许多时候“运气”对名次起了重要作用；要求（4）—（7）是为了适应实际比赛中可能会出现在一些复杂情况而提出的．首先是可能某两个队之间没有打比赛,我们称之为数据（成绩）残缺．对于两队成绩残缺,只能通过它们同其他队的比赛成绩来判断它们的实力比较．如果残缺元素过多,就有可能导致参赛队分成两组,组与组之间没有比赛,称这种情况为成绩表可约,这时显然是不应该排名次的．这样就有要求（4）,（5）；其次是前后比赛成绩矛盾,比如说a胜b,b胜c,c平a,称这种情况为数据不一致．如果不一致的情况过于严重,说明比赛偶然因素太大,数据的可依赖程度太低,应该考虑放弃比赛成绩．所以排名算法还应满足（6）,（7）．本文使用的层次分析法的特征根方法已满足了上述要求,下面将在§2中给出具体算法．§3中给出算发满足上述要求的解释和论证．§2模型设计及其算法一、基本假设和名词约定假设Ⅰ参赛各队存在客观的真实实力（见名词约定1）．这是任何一种排3名算法的基础．假设Ⅱ在每场比赛中体现出来的强队对弱队的表面实力对比是以它们的真实实力对比为中心的互相对立的正态分布．（见名词约定2）这条假设保证了我们可以以比赛成绩为依据对球队的真实实力进行排名,另外它在很大程度上反映了球队水平发挥的不稳定性．名词约定1．称w=(12,,,n…)为真实实力向量,如果iw的大小表现了iT的实力强弱．当iw的大小表现了iT在比赛中出色程度时,称w为排名向量．由假设Ⅱ,两者应是近似相同的,以后就把它们当成同一个．2．称iT对jT这场比赛中体现出来的iT对jT的相对强弱程度为iT对jT的表面实力对比,一般记作ija,当iT对jT成绩残缺是约定ija＝０．显然地有1()0,(),()1.ijjiiiijiaiiaiiiaa（2.1）矩阵Ａ＝()ijnna就称为比赛成绩的判断矩阵,它是可以通过各种方法（见§５）从比赛成绩中求出来的．由假设Ⅱ,若iT对jT成绩不残缺且1ijww时有2~(,)ijijijaNww（2.2）这里w是真实实力向量．3．称方阵nnA为正互反对称的,若（1）ija0,（2）1jiijaa,1,ijn．显然一个无残缺的比赛成绩的判断矩阵是正互反对称的．4．称矩阵nnA是可约的,若A能用行列同时调换化1240AAA,这里1A,4A都是方阵,在[1]的227页证明了一个判断矩阵可约当且仅当成绩表可约．5．称判断矩阵A是一致的,若对任意1,,ikjn满足ijjkikaaa．显然地,A一致则存在w,使得()innjwAw（2.3）6．称矩阵A的最大正特征根max为主特征根；对应于max的右特征向量w称为主特征向量,若11niiw且iw0．4由非负矩阵的Perron-Frobenius定理,一个判断矩阵A的max存在唯一且可以让对应于max的特征向量1w的每个分量都大于零,令111nii即得主特征向量．二、模型设计与算法我们的模型的主要部分是一个算法,模型的输入是一张成绩表,输出是关于是否可约的判断、数据可依赖程度值和排名次的结果．算法（一）根据比赛成绩表构造判断矩阵A．i从1到n,j从1到n的循环．1）若iT与jT互胜场次相等,则1净胜球=0时令1ijjiaa；跳出作下一步循环；2iT净胜球多时以iT净胜jT一场作后续处理．2）若iT净胜jTk场且k0,则2,14;19,4.ijkkbk2ijimT胜jT平均每场净胜球数；1,2;0,02;1,0.ijijijijmdmm3,1/ijijijjiijabdaa．3）若iT与jT无比赛成绩,则0ijjiaa．（二）检测A的可约性,如果可约则输出可约信息后退出．（三）构造辅助矩阵～Ａi从1到n,j从1到n循环~,01,A000.ijijijiiijaijaamijmia且；，其中为的第行的个数；，（四）计算～Ａ的主特征根max和住特征向量w．51）允许误差,任取初始正向量000012,,,Tnxxxx…,令k=0,计算001maxiinmx；0000101,,Tnyyyxm…．2）迭代计算1kkxy～Ａ；111maxkkiinmx；1111kkkyxm；1kk；直到1||kkmm．3）max1;kknkiiymwy．（五）按w各分量由大到小的顺序对参赛各队排名次．（六）计算220011//ijijijijijij；1(1)22niimnnY；其中im为A的第i行0的个数．根据2h查2x表得到可依赖程度2(2)aPxh．关于算法的几点说明算法的第(一)步可以有多种不同的方法,这在§5还将讨论．第(二)步实际上是把A看作有向图的邻接矩阵表示求图是否连通．算法是标准的,可参阅任何一本有关于算法的书,这里省略．它在可约时作的退出处理保证了以后各步处理的是一个不可约阵．第(三)步使用的是幂法,其整个算法收敛性和正确性的证明可参阅[1]的103页．第(四)步是一个排序,可参阅任何一本有关算法的书．第(五)步我们举了一个例子,若算出2h=47.56,r=48,则在2x表的自由度为48一行找到47.56,它所在的列的a值为65%左右．6§3算法的理论分析一、排名的合理性和保序性要求关于为什么无残缺的判断矩阵A的主特征向量就是排名向量是层次分析法中特征根发的基础,可以在[1]的211页找到详细证明,这里只作简单说明．先假定比赛无残缺,此时算法中~A=A．先看一下A为一致矩阵时,有（2.3）式存w使得A(/)ijnnww,显然向量w就是排名向量．而我们有1(/),1,2,,nijjii…；即Awnw（3.1）在[1]的109页证明了下述定理：定理n阶互反矩阵是一致的,当且仅当maxn．再由（3.1）可见w还是A的主特征向量,这样,对于一个一致矩阵A,求排名向量就是求A的主特征向量．对于一个不一致的判断矩阵A（注意：无残缺）,令1,||A||ijijna（3.2）1/||A||,1niijiwain；（3.3）由于iw是A的第i列元素（即iT与其他队的表面实力对比）的和被||A||除,可以猜测它给出了iT的排序权重．但正如问题分析中所提到的,iT与jT的实力对比必须考虑到将iT与jT连结起来的所有场比赛,反应到判断矩阵A上就是所有1121kiiiiijaaa…都要考虑进去．令kija是Ak的第i行j列元素,不难看出112k-1121111knnnkijiiiiijiiiaaaa……（3.4）而()kija就是考虑了所有经过k场比赛将iT,jT连结起来的路径后反映的7iT,jT的相对强弱,称其为iT对jT的k步优势.当1kij时11kija,所以（3.4）式成为111211121()1111kkkkknnnnkijiiijiiijiiiiiiaaaaa…………；注意到等式右端一项正是(1)kija,所以k步优势就隐含了k-1步以及k-2,…,1.同（3.3）式,令()()1/||A||,1,,nkkkijjwain…；再令()()()1(,,)kkkTn…,可以想象,当k足够大时,()kw就给出了A所反映的排名向量.在[1]的104页正证明了等式AlimAkTkkewee,其中(1,1,,1)Te…；w是A的主特征向量.即()limkkww；所以在充分考虑了足够步优势后得到的排名向量()w就是A的主特征向量w.上面的讨论表明在比赛无残缺时,我们的排名是合理的和保序的,下面来看看残缺的情况.二、残缺的处理对于一个残缺的判断矩阵A,可以通过下述方法转化成一中讨论的情形,0,,0,ijijijijijijaacdad其中为正数，如果这样得到得矩阵C=()ijnnc的主特征向量为w,那么当/ijijdww时,我们认为补残是准确的.如果令,0;/,0;ijijijijijaacwwa_,