资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,足球赛排名方案,B(1),表1,给出的是我国12支足球队在19881989年全国甲级队联赛中的成,绩,要求通过建立数学模型,对各队进行排名次。排名的目的是根据比赛,成绩排出反映各队真实实力的一个顺序。为达到这一点,一个好的排名算,法应满足下面一些,基本要求,:,(1)保序性;(2)稳定性;(3)能够处理不同场比赛的全重;,(4)能够判断成绩表的可约性;(5)能够准确地进行补惨;(6)容,忍不一致现象;(7)对数据可依赖程度给出较为精确的描述。,要求(1),为了满足,排名顺序与成绩表反映的各队实力水平的顺序是一,致的,。,要求(3)使得不同场比赛在排名中的地位不同,这是因为在实际比赛,中,往往会有的队不幸遇到较强的队而输掉。,要求(4)(7)是为适应实际比赛中可能会出现的一些复杂情况而,提出的。,首先,是可能某两个队之间没有打比赛,我们称之为数据(成绩),残缺,。,其次,是前后比赛矛盾,比如说,a,胜,b,b,胜,c,c,平,a,称这种情况为数据,不一致。,足球赛排名方案,B(2),表1,0:1 2:2 2:0 3:1 1:0 0:1 0:2 1:0 1:1,1:0 1:0 3:1 1:3 2:1 4:0 1:1,0:0 0:2 1:0,2:0 0:0 1:1 2:1 1:1 0:0 2:0 0:2,0:1 2:0 1:1 0:0 1:1 0:0,1:3 0:0,4:2 2:1 3:0 1:0 0:1 1:0 0:1,1:1,0:0,2:3 0:1 0:5 2:1 0:1 0:1,2:3 1:3 0:0 1:1,0:1 1:0 0:1,1:2 1:1,1:0 2:1 3:1 3:1 2:0,2:0 3:0 3:0,0:0 1:0 2:2,0:1 1:1 3:1 0:0,1:2 1:0,2:0 0:1,3:0,1:0 1:0 1:0,0:0,1:0 2:0,1:1,1:2,1:1,足球赛排名方案,B(3),模型设计及其算法,算法的理论分析,足球赛排名方案,B(4),模型设计及其算法,基本架设和名次约定,假设,I,.,参赛各队存在可观的真实实力(见名次约定1)。这是任何一种排名算法的基础。,假设,II.,在每场比赛中体现出来的强队对弱队的表面实力对比是 以它们的真实实力对比为中心的互相独立的正态分布。(见名次约定2),足球赛排名方案,B(5),名次约定,1.称 为真实实力向量,其分量的大小表现了各队的实力强弱。若其大小表现了在比赛中出色程度时,称为排名向量。由假设,II,,两者应是近似形同的,以后就把它们当成同一个。,2.称这场比赛中体现出来的各队的相对强弱程度为各队的表面实力对比,一般记作,a,ij,,显然地有,矩阵 就称为比赛成绩的判断矩阵,它是可以通过各种方法从,比赛成绩中求出来的。,由假设,II,,若 对 成绩不残缺且 时有,(2),这是 的真实实力向量。,足球赛排名方案,B(6),3.称方阵,A,为正互反对称的,若,(1),(2),显然一个无残缺的比赛成绩的判断矩阵是正互反对称的。,4.称矩阵 是可约的,若 能用行列同时调换化为 ,这里 ,都是方阵。一个,判断,矩阵可约当且仅当成绩表可约。,5.称判断矩阵,A,是一致的,若对任意 满足 。,显然地,一致则存在 ,使得,(3),6.称矩阵,A,的最大正特征根 为主特征根;对应于 的右特征向量,w,称,为主特征向量,若,,且,由非负距阵的,Perron-Frobenius,定理,一个判断距阵,A,存在为一,个对应于 的特征向量 ,其每个分量都大于零,令 即,得主特征向量。,足球赛排名方案,B(7),模型的设计预算法,我们的模型的主要部分是一个算法,模型的输入是一张成绩表,输出是,关于是否可约的判断、数据可依赖程度值和排名次的结果。,算法,(一),根据比赛成绩表构造判断矩阵。,i,从1到,n,j,从1到,n,循环。,1.,若 与 互胜场次相等,则,1)净胜球=0时令,;,跳出做下一步循环;,2),净胜球多时以净胜一场作后续处理。,2.,若净胜场,则,1),2),胜 平均每场净胜球数,;,足球赛排名方案,B(8),3),3.,若 与 无比赛成绩,则 。,(二),检测的可约性,如果可约则输出可约信息后退出。,(三),构造辅助矩阵,i,从1到,n,j,从1到,n,循环,(四),计算 的主特征根 何主特征向量,1.,允许误差 ,任取初始正向量 ,令 ,计算,足球赛排名方案,B(1),2.,迭代计算,直到,3.,(五),按 各分量由达到小的顺序队参赛各队排名次。,足球赛排名方案,B(10),(六),计算,,其中 为 的第 行0的个数。,根据2,h,查 表得到可依赖程度 。,关于算法的基点说明,算法的第(一)步可以由多种不同的方法,这在,后面,还将讨论。,第(二)步实际上是把,A,看作有向图的邻接矩阵表示求图是否连通,算法是标准的,可参阅任何一本关于算法的书,这里省略。它在可约时作的退出处理保证了以后各步处理的是一个不可约阵。,第(四)步使用的是幂法,其整个算法收敛性和正确,证明略。,第(五)步是一个排序,可参阅任何一本关于算法的书。,第,(,六,),步我们举一个例子,若算出2,h47.56,r=48,则在 表的自由度为48一行找到47.56,它所在的列的 值为65左右。,足球赛排名方案,B(11),算法的理论分析,下面讨论上面的算法是否满足七个基本要求。,排名的合理性和保序性要求,先假定比赛无残缺,此时算法中,先看一下 为一致矩阵时,由(3)式存在 使得 ,显然 向量 就是排名向量。,而我们有,即 (4),不加证明地给出下面定理,定理,.,n,阶正互反矩阵是一致的;当且仅当,再由(4)可见,w,还是,A,的主特征向量,这样,对于一个一致矩阵,A,,求排名向量就是求,A,的主特征向量。,足球赛排名方案,B(12),对于一个不一致的判断矩阵,A(,注意:无残缺),令,(5),(6),由于 是,A,的第,i,列元素(即,T,i,与其他队的表面实力对比)的和被 除,可,以猜测它给出了,T,i,的排序权重。,但正如问题分析中所提到的,,T,i,与,T,j,的实力对比必须考虑到将,T,i,与,T,j,连,结起来的所有场比赛,反应到判断矩阵,A,上就是所有 都要考,虑进去。令,a,(k),ij,是,A,K,的第,i,行,j,列元素,不难看出,(7),而 就是 考虑了所有经过,k,场比赛将,T,i,,T,j,连结起来的路径后反映的,T,i,T,j,的相对强弱,称其为,T,i,对,T,j,的,k,步优势。,当 时 ,所以(7)式成为,足球赛排名方案,B(13),注意到等式右端一项正是 ,所以,k,步优势就隐含了,k-1,步以及,k-2,1.,同(6)式,令,再令 ,可以想象,当,k,足够大时,就给出了,A,所反,映的排名向量。,即,所以在充分考虑了足够多步优势后得到的排名向量 就是,A,的主特征,向量,w。,上面的讨论表明在比赛无残缺时,我们的排名是合理的和保序的,,下面来看残缺的情况。,足球赛排名方案,B(14),残缺的处理,对于一个残缺的判断矩阵,A,,可以通过下述方法转化成上面讨论的情形,如果这样得到的矩阵 的主特征向量为,w,,那么当,时,我们认为补残是准确。如果令,则由下面命题成立:,足球赛排名方案,B(15),命题,等价于 。,证:,由上述命题可知,,C,的最大正特征根也是 的主特征根,,C,的主特征向量,也是,A,的主特征向量。这样,我们只需解 即可,这正是算法,(三)、(四)步作的工作。,从上面讨论可知,本模型对于残缺的处理是非常准确的,满足要求,(1)保序性,(5)能够准确地进行补残。另外算法的第(二)步对成绩表,的可约性作出了判断,这也满足了因为残缺而提出的要求(4)能够判断成,绩表地可约性。,足球赛排名方案,B(16),对手的强弱对自己名次的影响,排名向量满足 ,即,如果 对 成绩不残缺,则 ,固定 ,令 变大,则,就会变大,从而引起 变大,这实际上是排名结果对每场比赛权,重的反馈影响。,这样的话,若 对 战绩固定,排名靠前,也会因此受益。这就,满足了要求(3)能够处理不同场比赛的权重。,足球赛排名方案,B(17),模型稳定性的分析,不加证明地引用下面定理,定理。,设,A,为 非负矩阵,是,A,的单特征根,,B,是 矩阵,则一,定可以从 (其中 足够小)的特阵根中找到一个特征根 满,足 。,由名次约定6中解释 的最大正特征根是单的,由上述定理可知,只,要判断矩阵的变动微小,主特征根的变动就是微小的,进一步容易证明线,性方程组,的满足 的解的变动是微小的,即主特,征向量的变动是微小的,排名是稳定的,满足了要求(2)稳定性。,足球赛排名方案,B(18),关于可依赖程度的分析,当,A,是一个残缺的不一致矩阵时,由它得到的排名向量设为,w,,由名次,约定(1)我们认为这就是真实实力向量,令,(8),则由(2)式知 时,,(9),为计算方便,我们进一步假定 时,,(10),为常数,,令,(11),足球赛排名方案,B(19),则,h,可看作,A,的前后矛盾程度,再由(9),(10)可知,(12),其中,(13),为第,i,行零的个数。,那么对某个固定的 可知通过(13)求出 ,通过(11)求出 ,设,随机变量 ,则查 表可得到,(14),称,a,为 的可依赖程度,则一个判断矩阵 的可依赖程度为,a,就表示,如果与,相同的几个队在同样的比赛程序(队编号相同,残缺元素形同)下踢大量的赛季,比赛(假定各队水平不长进),判断矩阵 为的这次的前后矛盾程度 比大约,的赛季的比赛前后矛盾程度,h,要小。的值,可以用统计的方法估计,在本,模型中我们只是简单地取 。,这样,我们的模型就满足了要求(7),对数据可依赖程度给出较为精确的描述,。,足球赛排名方案,B(20),模型运行结果的分析,我们在计算机上实现了上述模型,运算得到的结果是:,排名顺序,(有强到弱):。,数据可依赖程度为65%;,踢了9场比赛,全部获胜,踢了9场比赛全部输掉,所以 第一而,最末是显然的。下面考虑一对水平接近的队 和 。,在 ,与其他队的比赛中,只有与 的比赛中,成绩比,T,3,稍好,而在与其余6个队比赛中,,T,3,成绩都优于 ,而且在,T,3,与 比赛时,T,3,在净胜球方面占了上风,因此,将,T,3,排在 前面是合适的。,数据可依赖程度为65%说明表1中所给数据还是不错的,当然算法中,取,是,先验的,这个指标暂时还不是准确的。,足球赛排名方案,B(21),模型优缺点及改进方向,优点,它存在反馈机制,并且具有稳定性,保证了排名的公平和令人信服,;,能准确地处理残缺,不一致的甚至很差的数据,对比赛程序没有严格的要求;,灵活机动,这包括了提供了对比赛成绩进行取舍的参考指标,适合任意,N,个队任何对抗性比赛的排名;,满足保序性。,缺点,算法复杂,必须用到计算机,这是无法改进的,。,在从成绩表构造判断矩阵时利用的方法也不是最好的,它只是为了,简单和,较合乎尝试,,这一步在整个模型里引入的误差最大。稍微复杂一,点的方法是根据成绩通过查表后,通过专家咨询获得实力对比的值。,足球赛排名方案,B(22),在某些残缺元素过多的情况下排名的稳定性和可靠性较低,而可依赖靠程度这个指标并没有考虑这些情况。比如下面两个判断矩阵,它们的差别就不大。,与,但排名结果分别为 和 。结构变化很大。这种情况可以也只能对比赛程序作一些要求,以避免这种几乎可约的情形,本模型并没有作这种工作。,可依赖程度的计算中取 是没有多少道理的,这可以通过用统,计的方法估出 来解决。,足球赛排名方案,B(23),模型的改进,它只使用了层次分析法中单一准则一个层次的排序方法,可以考虑使用多个准则和递阶层次,比如将净胜局数,净胜球数,射门次数,犯规次数做成四个准则,两个层次。甚至能将观众反映等许多细小因素考虑在内,使排名更加反映球队实力。,
展开阅读全文