全国大学生《数学建模》竞赛：1993B

一个给足球队排名次的方法 贼立峰 毛威马斌 (北京大学数学系,101) 摘要本文利用层次分析法建立了一个为足球队排名次的数学模型它首先对用来排 名次的数据是否充分作出判断,在能够排名次时对数据的可依赖程度作出估计,然后给出名 次,文中证明了这个名次正是比赛成绩所体现的各队实力的顺 序 文中将看到此模型充分考虑了排名结果对各场比赛成绩的重要性的反馈影响,基本上消 除了由于比赛对手的强弱不同造成的不公平现象:文中还证明了模型的稳定性,这保证了各队 在发挥水平上的小的波动不会对排名顺序造成大的变动.本模型比较完满地解决了足球队排 名次问题,而且经过简单修改,它可以适用于任何一种对抗型比赛的排名 81问题的提出及分析 本题的表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平6,a平b 在上述比赛中a表现应比b出色,但按积分法计算a,b都积2分.其原因就在于积分法 没有把a平c,c胜d,d平b这组比赛中所体现的a,b实力对比情况考虑进去 要求(2)是说成绩表小的变动不会对排名结果造成巨大影响这是由于球队发挥水平 存在正常波动而必须提出的,如果这种正常的小波动引起名次的巨大变化,那么排名就不令 人信服 要求(3)使得不同场比赛在排名中的地位不同,这是因为在实际比赛中,往往会有的队不 幸遇到较强的队而输掉.为了避免由于对手的强弱不同造成的不公平,要求(3)是必须的但现 行的排名制度大都满足不了要求(3),以致于许多时候“运气”对名次起了重要作用; 要求(4)-(7)是为适应实际比赛中可能会出现在一些复杂情况而提出的 首先是可能某两个队之间没有打比赛,我们称之为数据(成绩)残缺对于两队成绩残 缺,只能通过它们同其他队的比赛成绩来判断它们的实力对比如果残缺元素过多,就有可

个给足球队排名灭的方法 19 能导致参赛队分成两组,组与组之间没有比赛,称这种情况为成绩表可约,这时显然是不应 排名次的.这样就有要求(4),(5); 其次是前后比赛成绩矛盾,比如说a胜b,b胜c,c平a,称这种情况为数据不一致如果 不一致情况过于严重,说明比赛偶然因素太大,数据的可依赖程度太低,应该考虑放弃比赛 或绩所以排名算法还应满足(6),(7) 本文使用的层次分析法的特征根方法已满足了上述要求,下面将在§2中给出具体算 ,53中给出算法满足上述要求的解释和论证 52模型设计及其算法 、基本假设和名词约定 假设I参赛各队存在客观的真实实力(见名词约定1),这是任何一种排名算法的基 假设Ⅱ在每场比赛中体现出来的强队对弱队的表面实力对比是以它们的真实实力 比为中心的互相独立的正态分布.(见名词约定2) 这条假设保证了我们可以以比赛成绩为依据对球队的真实实力进行排名,另外它在很 大程度上反映了球队水平发挥的不稳定性 名词约定 1.称w=(u1,w2,…,n)为真实实力向量,如果的大小表现了T的实力强弱当 的大小表现了T在比赛中出色程度时,称w为排名向量由假设Ⅱ,两者应是近似相同 ,以后就把它们当成同一个 2.称T对T这场比赛中体现出来的T对T的相对强弱程度为T对T的表面实力 比,一般记作a,当T与T成绩残缺时约定a=0.显然地有 (i)ai>0, (i)a=1/ai. (iii) a=1 (2.1) 矩阵A=(a)n×n就称为比赛成绩的判断矩阵,它是可以通过各种方法(见§5)从比 成绩中求出来的 由假设Ⅱ,若T对T成绩不残缺且t/t≥1时有 a;-N(w: /w;, of) (2.2) 邀里w是真实实力向量 那主草书( 3.称方阵A,x,为正互反对称的,若(1)a1>0,(2)a1=1,1≤,≤,显然一个 液缺的比赛成绩的判断矩阵是正互反对称的 4.称矩阵A,是可约的,若A能用行列阿时调换化为(4101,这里A,A都是方 在11的22页证明了一个判断矩阵可约当且仅当成绩表可钩形部 5.称判断矩阵A是一致的若对任意1≤i,k,≤n满足an…·a1=a显然地,A 测存在w,使得 6.称矩阵A的最大正特征根Amx为主特征根;对应于Amx的右特征向量w称为主特征 量,若∑1=1且1>0

全国大学生数学建模竞赛优秀论文汇编 由非负矩阵的 Perron-Frobenius定理,一个判断矩阵A的λ存在唯一且可以让对应于 Am的特征向量v的每个分量都大于零,令w=m①/∑即得主特征向量 出二、模型设计与算法 对赛出9, 我们的模型的主要部分是一个算法,模型的输入是一张成绩表,输出是关于是否可约的 判断、数据可依赖程度值和排名次的结果 算法 出中E至, (一)根据比赛成绩表构造判断矩阵A i从1到n,从1到n的循环 其是面S8 1)若T与T互胜场次相等,则 1净胜球=0时令a=a=1跳出作下一步循环; 2T净胜球多时以T净胜T一场作后续处理 t2)若T净胜Tk场且k>0,则出中在1量 6(2k,1≤k≤4;(阳),的时的小中出 出2 2m=T胜T平均每场净胜球数;的得法 或[答 d=10,0≤m≤2; (-1,m<0,出中赛出溶小大的 3ag=by+ d, a i=1/ai 3)若T与T无比赛成绩,则a=a=0.出原测赛为到 (二)检测A的可约性,如果可约则输出可约信息后退出,,与一,出 1.(三)构造辅助矩阵A ai从1到n,从1到n循环 ≠j且a≠0; 出中 an={m+1,i=j,其中m为A的第;行0的个数; (四)计算A的主特征根=、和主特征向量w 实定真是里 1)允许误差c,任取初始正向量x=(x10,x2,x0),令k三0,计算 Ino- max 滑出的 2)迭代计算 面的 (k+1) A max Iar m}+1 k=k+1 直到|m41-mk1<e

个给足球队排名次的方法 3)Amax mii w 的凯其已,) (五)按w各分量由大到小的顺序对参赛各队排名次,距中 (六)计算 ,部 h=∑ 1)+ 的“ 的y=2(”21∑,其中m为A的第行0的个数 根据2查x2表得到可依赖程度a=P(x2>2M) 关于算法的几点说明 算法的第(一)步可以有多种不同的方法,这在§5还将讨论 第(二)步实际上是把A看作有向图的邻接矩阵表示求图是否连通算法是标准的,可 参阅任何一本关于算法的书,这里省略.它在可约时作的退出处理保证了以后各步处理的是 个不可约阵 第(四)步使用的是幂法,其整个算法收敛性和正确性的证明可参阅[1]的103页 向第(五)步是一个排序,可参阅任何一本关于算法的书 第(六)步我们举一个例子,若算出2h=4756,r=48,则在x2表的自由度为48一行 找到47.56,它所在的列的a值为65%左右 83·算法的理论分析 一、排名的合理性和保序性要求 关于为什么无残缺的判断矩阵A的主特征向量就是排名向量是层次分析法中特征根 法的基础,可以在[1]的211页找到详细证明,这里只作简单说明先假定比赛无残缺,此时 算法中A=A 先看一下A为一致矩阵时,由(2.3)式存w使得A=(v/c)n×n显然向量w就是排 名向量 而我们有 (w1/w;)·w;=n·w;,i=1,2 nw (3.1 在[1]的109页证明了下述定理: 定理n阶正互反矩阵是一致的,当且仅当Amx=n 再由(3.1)可见w还是A的主特征向量,这样,对于一个一致矩阵A,求排名向量就是 求A的主特征向量 对于一个不一致的判断矩阵A(注意:无残缺),令 I A s (3.2 u4=∑a;/‖A‖,1≤i≤n, (3.3) 命面

全国大学生数学建模竞赛优秀论文汇编 由于w;是A的第i列元素(即T与其他队的表面实力对比)的和被‖A‖除,可以猜 测它给出了T的排序权重 但正如问题分析中所提到的,T与T的实力对比必须考虑到将T与T连结起来的所 有场比赛,反应到判断矩阵A上就是所有a2a12“a,都要考虑进去 令a)是A的第行j列元素,不难看出 (3.4) 面a就是考虑了所有经过k场比赛将T,T连结起来的路径后反映的T,T的相对强弱, 称其为T对T的k步优势 当:1=时a1=1,所以(3,4)式成为。A 具的干关 a+“∑a 注意到等式右端后一项正是a猜),所以k步优势就隐含了k一1步以及k-2,…,1 同(3,3)式,令“a41,=1,“,,,的是( 再令w()=(v12),…,v)T,可以想象,当k足够大时,w4就给出了A所反映的排名向 量在[1的104页证明了等式 w,其中e=(1,1,…,1) 的,, 是A的主特征向量 货 所以在充分考虑了足够多步优势后得到的排名向量w(=就是A的主特征向量w 上面的讨论表明在比赛无残缺时,我们的排名是合理的和保序的,下面来看残缺的 中 二、残缺的处理 对于一个残缺的判断矩阵A,可以通过下述方法转化成一中讨论的情形 =1“,≠0 1dn,an=0,其中d为正数 如果这样得到的矩阵C=(c)×的主特征向量为w,那么当d=m;/v时,我们认为补 残是准确的.如果令 ≠0 0;且,, ,E再 ≠0,i≠ 六县买(.C)由 0,i≠ m;+1,i=j,m;是A的第i行0的个数 则有下面命题成立

一个给足球队排名次的方法 命题Cw=Aw等价于Aw=Aw.距的当,勇长 证 Awa,i= I +∑(1/v)w+m1=A ∑吗+(m1+1)m=k,N为? 0台∑a1=e,=1,“,n 证毕 由上述命题还可知,C的最大正特征根也是A的主特征根,C的主特征向量也是A的主 特征向量这样,我们只需解Aw=)kmw即可,这正是算法(三)、(四)步作的工作 从上面讨论可知,本模型对于残缺的处理是非常准确的,满足了要求(1),(5)另外算法 的第(二)步对成绩表的可约性作出了判断,这也满足了因为残缺而提出的要求(4) 下面继续讨论其余四个要求 的回三、对手的强弱对自己名次的影响一,的 排名向量满足Aw=Am,w,即(纸同号用)并的个具 出的的0的1 民要面,( 如果T对T成绩不残缺,则a=a>0,固定a,令变大,则aawk就会变大,从而引 起v;变大这实际上是排名结果对每场比赛权重的反馈影响 这样的话若T对T战线固定,T排名靠前,T也会因此受益这就满足了要求(3) 四、模型稳定性的分析 求的门, 不加证明地引用下面定理([1]103页) 定理设A为n×n复矩阵,A1是A的单特征根,B是n×n矩阵,则一定可以从A +B.(其中11足够小)的特征根中找到一个特征根X满足A=A1+O(e) 由名词的约定6中解释A的最大正特征根是单的,由上述定理可知,只要判断矩阵的变 动微小,主特征根的变动是微小的,进一步容易证明线性方程组(A-kmxE)w=0的满足 ∑u1=1的解的变动是微小的,即主特征向量的变动是微小的,排名是稳定的,满足了要 求(2)求 出圈,等全,出部Q 关于可依赖程度的分析 许只,中出 很明显本模型是容忍不一致现象的,即满足要求(6) 当A是一个残缺的不一致矩阵时,由它得到的排名向量设为w,由名词约定(1)我们认 为这就是真实实力向量,令 的不是斜中1块20长 (3.5) 则由(2.2)式知v;/v≥1时

24 全国大学生数学建模竞赛优秀论文汇编 为计算方便,我们进一步假定w;/;≥1时 d2为常数 (3.7) h=∑8+∑8 则h可看作A的前后矛盾程度,再由(3.6),(3.7)可知 02-x2, 其中 (3.10) m;为第i行零的个数 五大景的 那么对某个固定A0,可以通过(3.10)求出,通过(3.8)求出h0,设随机变量h/a2 x2,则查x2表可得到千本,面话 是出 别(= (3.11) 称a为A的可依赖程度则一个判断矩阵An的可依赖程度为a就表示,如果与An相同的 几个队在同样的比赛程序(队编号相同,残缺元素相同)下踢大量赛季的比赛(假定各队水 平不长进),判断矩阵为A0的这次的前后矛盾程度ho比大约a×100%的赛季的比赛前后 矛盾程度h要小 a2的值可以用统计的方法估出,在本模型中我们只是简单地取=1. a临界值的确定可以很灵活地由比赛组织者决定,也可以通过大量好的和坏的比赛成 绩比较给出一个值 这样,我们的模型就满足了要求(7) §4模型运行结果的分析 我们在计算机上实现了上述模型,并对表1中的数据进行了排名,结果是令人满意的, 运算时间小于1秒,得到的结果是 排名顺序(由强到弱):T,T3,T,T,T2,T1,,T12,T,T,T1,T,若小 更1数据可依赖程度为65%;断查的 T踢了9场比赛,全部获胜,T4踢了9场比赛全部输掉,所以T第一而T4最末是显然 的.下面考虑一对水平接近的队T3和T1 在T3,T1与其他队的比赛中,只有与T9,T4,T5的比赛中,T1成绩比T3稍好,而在与 其余6个队的比赛中,T3成绩都优于T1,而且在T3与T1比赛时T3在净胜球方面占了上 风,因此,将T3排在T1前面是合适的 数据可依赖程度为65%说明表1中所给数据还是不错的,当然由于算法中取a2=1 是先验的,这个指标暂时还不是准确的 ,1≤“(.2)由 模型优缺点及改进方向 通过与现行的一些排名方法的比较,上述模型的优势是很明显的:

一个给足球队排名次的方法 1)它存在反馈机制,并且具有稳定性,保证了排名的公平和令人信服; 2)能较准确地处理残缺,不致等性质很差的数据,对比赛程序没有严格的要求; 灵活机动,这包括了它提供了对比赛成绩表进行取舍的参考指标,以及它适合任意 N个队任何对抗型比赛的排名; 4)满足保序性 模型主要的一个缺点就是算法复杂,必须用到计算机,而且对指导教练制定战略造成了 1难,这是无法改进的,但这同时也使球队的战术水平在比赛中的地位上升,有利于刺激竞 争另外我们还基于另一种思路建立了一个便于手算的模型,由于算法简单,效果没有本模 型好,本文中省略中回得 在从成绩表构造判断矩阵时用到的方法也不是最好的,它只是为了简单和较合乎常识 这一步在整个模型里引入的误差最大,稍微复杂一点的方法是根据成绩通过查表或专家咨 询获得实力对比的值 另外一个不足这处是在某些残缺元素过多的情况下排名的稳定性和可靠性较低,而可 依赖程度这个指标并没有考虑这些情况如比较下面两个判断矩阵,它们的差别就不大 的两是1010.2 两 与0011 11 但排名结果分别为T4,T,T2,T1和T2,T1,T3,T.结构变化很大,这种情况可以也 只能对比赛程序作一些要求,以避免这种几乎可约的情形,本模型并没有作这种工作 还有就是象§4所说的,可依赖程度的计算中取a2=5是没有多少道理的,这可以通 过用统计的方法估出a2来解决 不基于本模型的不足,模型的改进余地也是很大的它只使用了层次分析法中单一准则 个层次的排序方法,可以考虑使用多个准则和递阶层次,比如将净胜局数,净胜球数,射门 次数,犯规次数作成四个准则两个层次甚至能将观众反应等许多细小因素考虑在内,使排 名更加反应球队实力,空善工不留(人个)的,日的的 参考文献 目自关为, 王莲芬许树柏,层次分析法引论,中国人民大学出版社,北京,19,合全不置的 [2]叶其孝主编大学生数学建模竞赛辅导教材,湖南教育出版社,1 [3]许卓群等编,数据结构,高等教育出版社,1987 [4]杜荣骞编生物统计学,高等教育出版社,1985 甜的式钟王线,二 张,设面式个一民,来赛 合话平( 原一具且而,润实平合否果盐的出 否业思理浪(C 阳十县是,路动书发于 当因,(时中善意其)8量向和 身法非

且共,顷用团的了 =关于“球队排名次问题”的几点评注市( 意计合,将四 回益,(C 北京清华大学 蔡大用 卦虽 书原,其出其点个一国主到 出平是月同,方法县,亚 4一、出题背景和题目特点中7一立件 1993年数学模型竞赛征题期间,正好中国足球队在世界杯外围赛中再次失利不久后 有关报刊公布了世界足球队的排名顺序仔细观察不难发现在公布的球队中有的队之间从 来没有比赛过,不少人发生了如下疑问 以能图大最张的,里法个弃一2 报刊上公布的球队排序的依据是什么 2.如何客观、公正地评价球队之间的实力对比,消除一些赛制一偶然或人为因素的 影响,小四言 也就是说,要求我们建立一个客观的评估方法,只依据过去一段时间内(几个赛季或几 年)每个球队的战绩给出各队的优劣次序 解决类似问题的竞赛图法有较强的限制,它要求所评估的各队中任何两队必须比赛过 而且两队之间比赛的场次要一样.显然,在世界范围内取得这样的数据是相当困难的 为了克服传统竞赛图法的局限性,我们拟出本题供参赛者思考,果 B题的特点1.有很强的实际背景而且一旦给出了成功的模型和软件,它将有很大的 实用价值.显然,它可以用于相当多的体育比赛(几乎所有的球类、棋类、击剑……),而且也 有可能用于社会领域中其他问题 2.很多数学工具可有用武之地:正如参考答案及很多参赛者的答卷中所示,B题涉及 数学模型、矩阵论、图论层次分析概率统计、模糊数学数值分析等诸多数学领域中的方 法也有的作者用到了计算机科学中的各种技巧和分析方法,,中 3:是一个相当“开放”的题目它没有事先给出的标准答案和最优方案,是一个研究性 探索性较强的题目,给参赛者(甚至每个人)都留下了足够的思考空间虽然赛事已过但它 依然是一个余味未尽的研究课题 当然,与优点相关的自然有不少缺点比如,没有传统方法可循,题目显得粗糙、不成熟 所提供的数据也不完全合理,人工的斧凿痕迹很多等等 事顶学学大,主车其 出示,弹,平草! 二、对于各种方法的诌议 对于数学模型竞赛来说,评判一个方法的优劣,我们着眼于三点 1)对于模型的假设是否合理 2)所建模型构思是否新颖,其给出的结果是否合乎实际,而且具有一般性 3)叙述是否清楚 基于这种标准,我们认为有些答卷是十分优秀的 例1.首先定义了评分向量S(其含意和参考答案中含意相近),然后考虑了各种因素建 立了一种非线性模型

关于“球队排名次问题的几点评注 S=F(S) 其中F()是一个n维向量函数并建立了求解上面非线性方程组的迭代法 尽管理论上并没能证明迭代法的收敛性,但模型的构思是十分可取的 例2把球队排序问题转化成一个整数规划问题,建模的出发点十分简单明瞭,有其精 处 例3用层次分析法(AHP)完整地分析并解决了问题,理论分析和各种因素的讨论十分 完整 例4.用图论的办法,成功地处理了数据缺损等方面的困难,建立了一般性的模型 例5.参考了传统的体育界沿用的评分办法,但对缺损数据援用了统计学中各种(也包 括作者自己设计的)数据缺损的处理办法 还有很多思路如用Fuy数学理论、概率论、灰色系统理论等,不能一一枚举总之,尽 管得奖者是少数,但每份答案均有其合理的部份,反映出了年轻人的智慧火花 当然,由于全国数学模型竞赛刚刚举办两次,组织者和参赛者都缺乏经验,难免有些不 尽人意之处 有些参赛者对竞赛的宗旨和题目要求理解有些偏颇,他们着力于赛制的猜测、分组的分 析,甚至查阅了体育年鉴等参考资料,按照当年比赛的实况和结果着手于探索本题的“正确 答案”这不能不说是方法学上的失误;也有的参赛者基本上用了体育界沿用的比得分、比净 胜球等传统方法,只不过把这些成法电算化这种方法没有能克服传统方法的弱点(虽然有 的作者已经分析了这个弱点),也缺乏新意;还有的参赛者拘泥于具体的数据,设计了特殊的 算法,“成功地”解决了这一具体问题,但没有一般意义 尽管有如上的偏颇,但参赛者思想活跃及富有探索创新的精神,确实呈现了百花齐放的 局面,这是我们始料不及的有人得了奖有人没有,但从“重要的在于参与”的意义上大家都 是成功者