一个给足球队排名次的方法 贼立峰 毛威马斌 (北京大学数学系,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的个数 则有下面命题成立