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

2010高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：参赛队员（打印并签名）：1.指导教师或指导教师组负责人（打印并签名广日期：年月日赛区评阅编号（由赛区组委会评阅前进行编号）：2010高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：一个给足球队排名次的方法戚立峰毛威马斌

（北京大学数学系，100871）

指导教师樊启洪摘要本文利用层次分析法建立了一个为足球排名次的数学模型.它首先用来排名次的数据是否充分做出判断，在能够排名次时对数据的可依赖程度做出估计，然后给出名次.文中证明了这个名次正是比赛成绩所体现的各队实力的顺序.文中将看到此模型充分考虑了排名结果对各场比赛的重要性的反馈影响，基本上消除了由于比赛对手的强弱不同造成的不公平现象.文中还证明了模型的稳定性，这保证了各队在发挥水平上的小的波动不会对排名顺序造成大的变动.本模型比较完满地解决了足球队排名次问题，而且经过简单修改，它可以适用于任何一种对抗型比赛的排名.§1问题的提出及分析本题的表1给出的是我国12支足球队在1988-1989年全国甲级联赛中的成绩，要求通过建立数学模型，对各队进行排名次.按照通常的理解，排名的目的是根据比赛成绩排出反映各队真实实力状况的一个顺序.为达到这一点，一个好的排名算法应满足下面一些基本要求：（1）保序性；（2）稳定性；（3）能够处理不同场比赛的权重；（4）能够判断成绩表的可约性；（5）能够准确地进行补残；（6）容忍不一致现象；（7）对数据可依赖程度给出较为精确的描述.可以想象，各队的真实实力水平在成绩表中反映出来（见§3假定H）,所以根据排名目的，我们要求排名顺序与成绩表反映的各队实力水平的顺序是一致的这就是要求（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模型设计及其算法一、基本假设和名词约定假设I参赛各队存在客观的真实实力(见名词约定1).这是任何一种排名算法的基础.假设n在每场比赛中体现出来的强队对弱队的表面实力对比是以它们的真实实力对比为中心的互相对立的正态分布.(见名词约定2)这条假设保证了我们可以以比赛成绩为依据对球队的真实实力进行排名，另外它在很大程度上反映了球队水平发挥的不稳定性.名词约定.称w=(Wi,W2,…,Wn)为真实实力向量，如果Wi的大小表现了Ti的实力强弱.当Wi的大小表现了Ti在比赛中出色程度时，称W为排名向量.由假设R，两者应是近似相同的，以后就把它们当成同一个..称Ti对Tj这场比赛中体现出来的T对Tj的相对强弱程度为Ti对Tj的表面实力对比，一般记作a。，当I对Tj成绩残缺是约定a。=0.显然地有(i)aj0,(ii)aji-,(iii)aH1.由(2.1)矩阵A=(aj)nn就称为比赛成绩的判断矩阵，它是可以通过各种方法(见§5)从比赛成绩中求出来的.由假设n，若T对Tj成绩不残缺且W/Wj1时有aj〜N(W，Wj,j)(2.2)这里w是真实实力向量.1一.称万阵Ann为正互反对称的，右(1)aij>0,(2)为一，1i,jn.显aij然一个无残缺的比赛成绩的判断矩阵是正互反对称的.，，一一一一一，一，，一…"八A0、一.称矩阵Ann是可约的，若A能用行列同时调换化A,这里Ai,A4都AA是方阵，在［1］的227页证明了一个判断矩阵可约当且仅当成绩表可约..称判断矩阵A是一致的，若对任意1i,k,jn满足a0ajkaik.显然地,A一致则存在w,使得wiA(—)nn(2.3)Wj.称矩阵A的最大正特征根max为主特征根；对应于max的右特征向量Wn称为主特征向量，若Wi1且Wi>0.i1由非负矩阵的Perron-Frobenius定理，一个判断矩阵A的max存在唯一且可1以让对应于max的特征向量W1的每个分量都大于零，令W即得主特征1Wi

i1向量.二、模型设计与算法我们的模型的主要部分是一个算法，模型的输入是一张成绩表，输出是关于是否可约的判断、数据可依赖程度值和排名次的结果.算法(一)根据比赛成绩表构造判断矩阵A.i从1至1Jn,j从1到n的循环.1)若T与Tj互胜场次相等，则1°净胜球=0时令a。aji1；跳出作下一步循环;2°T净胜球多时以T净胜Tj一场作后续处理.2)若T净胜Tjk场且k>0,则2°mjTi胜Tj平均每场净胜球数;3°a3°ajbijdij,aji1/aij•3）若T与Tj无比赛成绩,则ajaji0.（二）检测A的可约性，如果可约则输出可约信息后退出.（三）构造辅助矩阵3）若T与Tj无比赛成绩,则ajaji0.（二）检测A的可约性，如果可约则输出可约信息后退出.（三）构造辅助矩阵Ai从1到n,j从1到n循环（四）计算A的主特征根max和住特征向量W.1）允许误差,任取初始正向量X0X10,X20，…,Xn0，令k=0,计算mo0maxxi1iniT10——xm02)迭代计算Aymk11k1一x；mk1直到|mk1mk|3)kyii1（五）按W各分量由大到小的顺序对参赛各队排名次.（六）计算TOC\o"1-5"\h\z22,ajdaijdh11;WiWjWi/WjwWjWi/Wjaj0aj0ij丫n（^J）nm；其中mi为A的第i行0的个数.

2i12根据2h查x2表得到可依赖程度aP（x22h）.关于算法的几点说明算法的第（一）步可以有多种不同的方法，这在§5还将讨论.第（二）步实际上是把A看作有向图的邻接矩阵表示求图是否连通.算法是标准的，可参阅任何一本有关于算法的书，这里省略.它在可约时作的退出处理保证了以后各步处理的是一个不可约阵.第（三）步使用的是幕法，其整个算法收敛性和正确性的证明可参阅［1］的103页.第（四）步是一个排序，可参阅任何一本有关算法的书.…-2第（五）步我们举了一个例子，若算出2h=47.56,r=48,则在x表的自由度为48一行找到47.56,它所在的列的a值为65流右.§3算法的理论分析一、排名的合理性和保序性要求关于为什么无残缺的判断矩阵A的主特征向量就是排名向量是层次分析法中特征根发的基础，可以在［1］的211页找到详细证明，这里只作简单说明.先假〜定比赛无残缺，此时算法中A=A.先看一下A为一致矩阵时，有（2.3）式存w使得A（Wi/Wj）nn,显然向量w就是排名向量.n而我们有（Wi/wj）wjnWi,i1,2,…，n;i1即Awnw（3.1）在［1］的109页证明了下述定理：定理n阶互反矩阵是一致的，当且仅当maxn.再由（3.1）可见w还是A的主特征向量，这样，对于一个一致矩阵A,求排名向量就是求A的主特征向量.对于一个不一致的判断矩阵A（注意：无残缺），令11AHaj（3.2）i,jnnwaj/||A||,1in;（3.3）由于W是A的第i列元素（即Ti与其他队的表面实力对比）的和被||A||除，可以猜测它给出了Ti的排序权重.但正如问题分析中所提到的，工与「的实力对比必须考虑到将I与1连结起来的所有场比赛，反应到判断矩阵A上就是所有a1a可「国仙都要考虑进去.令ajk是Ak的第i行j列元素，不难看出

kaj%%2akaj%%2aik-ijii1i21iki1(3.4)而ajk)就是考虑了所有经过k场比赛将工，Tj连结起来的路径后反映的Ti,Tj的相对强弱，称其为T对Tj的k步优势.当ikij时a』1,所以(3.4)式成为nnn♦…♦…aik2j；ik21a…a…aaijaii1aik1ji11ik11i11I<ik1注意到等式右端一项正是a注意到等式右端一项正是a(k1),所以k步优势就隐含了k-1步以及k-2,…，1.n同(3.3)式，令w(k)ajk)/1|Ak||,i1,…,n;j1再令w(k)(W1(k),…,wnk))T,可以想象，当k足够大时，w⑻就给出了A所反映的排名向量.在［1］的104页正证明了等式TOC\o"1-5"\h\zAke…tlimw,其中e(1,1,…⑴；keAew是A的主特征向量.即limw(k)w；k7所以在充分考虑了足够步优势后得到的排名向量w()就是A的主特征向量w.上面的讨论表明在比赛无残缺时，我们的排名是合理的和保序的，下面来看看残缺的情况.二、残缺的处理对于一个残缺的判断矩阵A,可以通过下述方法转化成一中讨论的情形如果这样得到得矩阵C=(Cj)nn的主特征向量为w,那么当djwi/wj时，我们认为补残是准确的.如果令C(Cj)nn；~~A(aij)nn；则有下面命题成立：~命题Cww等价于Aww.

n证CijWiWi,i1,…，n.ji〜由上述命题还可知,C的最大特征根也是A的主特征根,C的主特征向量也是〜A的主特征向量.这样，我们只需解AWmaxW即可，这正是算法（三）、（四）步作的工作.从上面讨论可知，本模型对于残缺的处理是非常准确的，满足了要求（1）,（5）.另外算法第（二）步对成绩表的可约性作出了判断，这也满足了因为残缺而提出的要求（4）.下面继续讨论其余四个要求三、对手的强弱对自己名次的影响〜排名向量满足AWmaxW,即~~如果Ti对Tk成绩不残缺，则aikaik0,固定a^，令Wk变大，则a^Wk就会变大，从而引起Wi变大.这实际上是排名结果对每场比赛权重的反馈影响.这样的话，若T对Tk战线固定，Ti排名靠前，Tk也会因此受益.这就满足了要求（3）.四、模型稳定性的分析不加证明地引用下面定理（[1]103页）.定理则A为nn复矩阵，1是A的单特征根，B是nn矩阵，则一定可以从~~A+Be（其中||足够小）的特征根中找到一个特征根满足1O（）.~由名词的约定6中解释A的最大特征根是单的，由上述定理可知，只要判断矩阵的变动微小，主特征根的变动是微小的，进一步容易证明线性方程组~n（AmaxE）w0的满足Wi1的解的变动是微小的，即主特征向量的变动是微i1小的，排名是稳定的，满足了要求（2）.五、关于可依赖程度的分析很明显本模型是容忍不一致现象的，即满足要求（6）.当A是一个残缺的不一致矩阵时，由它得到的排名向量设为w,由名词约定（1）我们认为这既是真实实力向量，令aiiij1,i,j1,，n.（3.5）Wi/Wj则由（2.2）则由（2.2）式可知Wi/Wj1时,aijWi/Wjij^j(0,W/Wj).(3.6)为计算方便，我们进一步假定Wi/Wj1时,aijWi/Wjij^j(0,W/Wj).(3.6)为计算方便，我们进一步假定Wi/Wj1时,W/wj2为常数,(3.7)则h可看作A的前后矛盾程度h/其中mi为第i行零的个数.W/Wja.

ij2W/Wj1aj0,ij,再由22~Xr,2ij.(3.8)n(n1)r2那么对某个固定A0,可以通过（3.10）求出r0,通过（3.8）求出ho,设随机变量h/2〜x：,则查x2表可得到haP(—如)2haP(—如)2)(3.11)称a为A。的可依赖程度.则一个判断矩阵A0的可依赖程度为a就表示，如果与A。相同的几个队在同样的比赛程序（队编号相同，残缺元素相同）下踢大量赛季的比赛（假定各队水平不长进），判断矩阵为A0的这次的前后矛盾程度h0比大约a100%勺赛季的比赛前后矛盾程度h要小.2的值可以用统计的方法估出，在本模型中我们只是简单地取2=-.2a临界值的确定可以很灵活地由比赛组织者决定，也可以通过大量好的和坏的比赛成绩比较给出一个值.这样，我们的模型就满足了要求（7）.§4模型运行结果的分析我们在计算机上实现了上述模型，并对表1中的数据进行了排名，结果是令人满意的，运算时间小于1秒，得到的结果是：排名顺序（由强到弱）:丁7,丁3,丁1,丁9,丁2,10,丁8,丁12,丁6,丁5,丁11,丁4.数据可依赖程度为65%T7踢了9场比赛，全部获胜,T4踢了9场比赛全部输掉,所以T7第一而T4最末是显然的.下面考虑一对水平接近的队T3和Ti.在T3,工与其它队的比赛中，只有丁9,丁4,7的比赛中，Ti成绩比T3稍好，而在与其余6个队的比赛中，T3成绩都优于Ti,而且在T3与Ti比赛时T3在净胜球方面占了上风，因此将T3排在工前面是合适的.数据可依赖程度为65■明表1中所给数据还是不错的，当然优于算法中取2=1是先验的，这个指标暂时还不是准确的.2模型有缺点及改进方向通过与现行的一些排名方法比较，上述模型的优势是很明显的；）它存在反馈机制，并且具有稳定性，保证了排名的公平和令人信服；）能较准确地处理残缺，不一致等性质差的数据，对比赛程序没有严格的要）灵活机动，这包括了它提供了对比赛成绩表进行取舍的参考指标，以及它适合任意N个队任何对抗型比赛的排名；）满足保序性.模型主要的一个缺点就是算法复杂，必须用到计算机，而且对指导教练制定战略造成了困难，这是无法改进的，但这同时也使球队的战术水平在比赛中的地位上升，有利于刺激竞争.另外我们还基于另一种思路建立了一个便于手算的模型,优于算法简单，效果没有本模型好，本文中省略.在从成绩表构造判断矩阵时用到的方法也不是最好的，它只是为了简单和较合乎常识，这一步在整个模型里引入的误差最大.稍微复杂一点的方法是根据成绩通过查表或专家咨询获得实力对比的值.另外一个不足之处是在某些残缺元素过多的情况下排名的稳定性和可靠性较低,而可依赖程度这个指标并没有考虑这些情况.如比较下面两个判断矩阵，它们的差别就不大.TOC\o"1-5"\h\z11210与01112102100011011但排名结果分别为T4,飞,丁2,工和丁2,工万3,丁4结构变化很大.这种情况可以也只能对比赛程序作一些要求，以避免这种几乎可约的情形，本模型并没有作这种工作.还有就是像§4所说的，可依赖程度的计算中取1011000101=10110001012这可以通过用统计的方法估出2来解决.不基于本模型的不足，模型的改进余地也是很大的.它只使用了层次分析法中单一准则一个层次的排序方法，可以考虑使用多个准则和递阶层次，比如将净胜局数，净胜球数，射门次数，犯规次数作为四个准则，两个层次.甚至能将观众反应等许多细小因素考虑在内，使排名更加反应球队实力.参考文献[1]王莲芬，许树柏，层次分析法引论，中国人民大学出版社，北京,1990[2]叶其孝主编，大学生数学建模竞赛辅导教材，湖南教育出版社，1993[3]许卓群等编，数据结构，高等教育出版社，1987。[4]杜荣骞编，生物统计学，高等教育出版社，1985。关于“球队排名次问题”的几点评注北京清华大学蔡大用一、出题背景和题目特点1993年数学模型竞赛征题期间，正好中国足球在世界杯外围赛中再次失利.不久后有关报刊发布了世界足球队的排名顺序.仔细观察不难发现，在公布的球队中有的队之间有从来没比赛过，不少人发生了如下疑问：.报刊上公布的球队排序的依据是什么..如何客观、公正地评价球队之间的智力对比，取消一些赛制一一偶然或人为因素的影响.也就是说，要求我们建立一个客观的评估方法，只依据过去一段时间内（几个赛季或几年）每个球队的战绩给出各队的优劣次序.解决类似问题的竞赛图法有较强的限制，它要求所评估的各队中任何两队必须比赛过，而且两队之间比赛的场次要一样.显然，在世界范围内取得这样的数据时相当困难的.为了克服传统竞赛图法的局限性，我们拟出本题供参赛者思考.B题的特点.有很强的实际背景，而且一旦给出了成功的模型和软件，它将有很大的使用价值.显然，它可以用于相当多的体育比赛（几乎所有的球类，棋类，击剑……），而且也有可能用于社会领域中其他问题..很多数学工具可有用武之地：正如参考答案及很多参赛者的答卷中所示,B题涉及数学模型、矩阵论、图论、层次分析、概率统计、模糊数学、数值分析等诸多数学领域中的方法.也有的作者用到了计算机科学中的各种技巧和分析方法..是一个相当“开放”的题目.它没有事先给出的标准答案和最优方案，是一个研究性、探索性较强的题目，给参赛者（甚至每个人）者B留下了足够的思考空间.虽然赛事已过，但它依然是一个余味未尽的研究课题.当然，与优点相关的自然有不少缺点.比如，没有传统方法可循，题目显得粗糙、不成熟.所提供的数据也不完全合理，人工的斧凿痕迹很多等等.二、对于各种方法的诗议对于数学模型竞赛来说，评判一个方的优劣，我们着眼于三点：对于模型的假设是否合理.所建模型构思是否新颖，其给出的结果是否合乎实际，而且具有一般性.叙述是否清楚.基于这种标准，我们认为有些答卷是十分优秀的.例1首先定义了评分向量S（其含意和参考答案中含意相近），然后考虑了各种因素建立了一种曲线性模型.S=F（S）,其中F（）是一个n维向量函数，并建立了求解上面非线性方程组的迭代法.例2尽管理论上并没有能证明迭代法的收敛性，但模型的构思十分可取.例3球队排序问题转化成一个整数规划问题，建模的出发点十分简单明了，有其精彩之处。例4用层次分析法（AHP完整地分析并解决了问题并且理论分析和各种因素的讨论十分完整.例5用图论的办法成功地处理了数据缺损等方面的困难，建立了一般性的模型.参考了传统的体育界沿用的评分办法，但对缺损数数据援用了统计学中各种（也包括作者自己设计的）数据缺损的处理办法.还有很多思路.如用Fuzzy数学理论，概率论,灰色系统理论等，不能一一枚举.总之，尽管得奖者是少数，但每份答案均有其合理的部分，反映出了年轻人的智慧火花.当然，由于全国数学模型竞赛刚刚举办两次，组织者和参赛者都缺乏经验，难免有些不尽人意之处.有些参赛者对竞赛的宗旨和题目要求理解有些偏颇，他们着力于赛制的猜测、分组的分析，甚