足球队排名次

B题足球队排名次下表给出了我国12支足球队在1988—1989年全国足球甲级联赛中的成绩，要求1）设计一个依据这些成绩排出诸队名次的算法，并给出用该算法排出名次的结果。2）把算法推广到任意N个队的情况。3）讨论：数据应具备什么样的条件，用你的方法才能够排出诸队的名次。对下表的说明：1）12支球队依次记作T1，T2，。。。T12。2）符号X表示两队未曾比赛。3）数字表示两队比赛的结果，如T3行与T8行交叉的数字表示：T3与T8比赛了2场；T3与T8的进球数之比为0：1和3：1。T1T2T3T4T5T6T7T8T9T10T11T12T1X0：11：00：02：21：00：22：03：11：03：11：00：11：30：22：11：04：01：11：1XXT2X2：00：10：02：01：12：11：11：10：00：02：01：10：20：0XXT31：3X0：04：21：10：02：13：01：01：40：13：11：02：30：12：0XXT4X2：30：10：52：32：11：30：10：00：11：1XXT5X0：1XXXX1：01：20：01：1T6XXXXXXXT7X1：02：00：02：13：01：00：13：13：02：21：13：12：0T8X1：22：01：00：13：03：10：0T9X1：00：01：01：0T10X1：02：01：1T11X1：21：1T12X从表中给出的比赛成绩看，数据是不整齐的：某些队之间有三场比赛的成绩，另外某些队之间则只有两场或一场比赛的成绩，还有一些队之间没有比赛成绩．以下的解答主要参考了中国科技大学获特等奖队的论文§1合理的假设1．排名仅根据现有比赛结果，不考虑其他因素。2．每场比赛对于估计排名的重要程度是一样的，具有相同的可信度，不同的比赛相互独立．3．有些队之间没有比赛，完全是由于比赛安排的原因造成的，不是由于球队在以前比赛中的胜负造成的，也不是由于某一方弃权造成的(根据比赛规则，弃权一方应被判输球，从而应在数据表中显示出来)．4．按流行的赛制，以二分制计算比赛积分，即：胜一场得2分，平一场得1分，输一场得0分．(当然也可以按三分制计算积分，将胜一场的得分改为3分，以鼓励进攻，这样的修改对我们的模型不造成任何困难.).作出以上的假设，一方面是由于原题没有提供更多的信息，我们没有理由认为某场比赛比别的比赛更具有特殊性等．当然，按照数学建模竞赛的规则，在原题条件不够的情况下允许自己查阅资料，补充信息．但本题中如果真的从体育资料中去查出1988—1989年我国足球甲级队联赛的具体情况，在模型中予以反映，所建立的模型就失去了普遍意义．因此，做出上述假设的更重要的出发点是为了使所建立的模型能够具有普适性，适合于各种不同的比赛．§2问题的分析众所周知，足球界对同一赛事中比赛结果的排名有现成的算法．例如：循环比赛结果的排名，按前述二分制(或三分制)计算总积分，以总积分的高低来决定名次的先后(总积分相同者，再比净胜球数的多少，总进球数的多少，等等)．但是，这一算法着眼于排出比赛的胜负名次，并不总能合理地反映出各队真实水平的高低．比赛名次当然主要决定于各队的真实水平，但各队在比赛场次安排中“运气”的好坏也有相当的影响．比如，某队在比赛中避开了强队而大胜弱队，就是由于“运气”好而得分高的例子．我们不能完全排除这一类因素，但应尽可能合理地考虑并处理它。另外，足球界的上述算法只适用于同一赛事的比赛结果，对于不同赛事的混合结果，特别对于比赛场次及数据参差不齐的情况(如本题所给的数据)，就显得无能为力了。我们的目标就是要针对这种不规则的比赛数据提出一种算法，尽可能合理地反映各队的真实水平．§3初步的排名方案我们先从最通行的算法开始，通过分析其缺点而一步步加以改进．模型1总积分法：按两分制(或三分制)计算各队在所有比赛中总的积分，按总积分的高低排出名次。但是，在所给的数据表中，各队比赛场次有多有少，而按我们的假设，比赛场次的多少并不是由于该队在以前的比赛中的胜负所致．如果按总计分法，则比赛场次少的队吃亏．为了克服这一不合理性，很自然改进为：模型2平均积分法：将每个队的总积分除以该队参加比赛的场数，得出每场平均积分．按各队平均积分的高低来排名。上述方法当然还可以做出一些小的改进．比如再将净胜球数、总进球数等因素也折算成一定的分数，计入总分。§4特征向量法的提出在我们看来，以上总积分法和平均记分法(及其考虑了净胜球数、总进球数之后的改良版本)最大的不合理性是：在计算比赛得分时没有考虑对手的强弱．比如，胜强队和胜弱队同样都得2分，这就明显不合理．由此看来，更合理的算法应当是：胜强队得分应该多一些，胜弱队的得分应该少一些．用数学语言说，应该给每个队赋予一个“强弱系数”xi，(非负实数)，来反映该队实力的强弱，强队的系数大，弱队的系数小．如果对手的强弱系数为xi，你胜了它，你的得分就用这个系数对基本得分(2分)进行加权，为2分×xi分。为了叙述方便，将第i队记为Ti(1≤i≤N)．要算出Ti的总的得分，先对每个Tj，算出Ti对Tj的各场比赛中按二分制的平均得分，记为aij．如果Ti与Tj没有比赛过，就取aij=0．特别aii=0．(严格说来，对没有比赛过的队Ti，Tj，取aij=0并不合理，这等于是判这两个队各输一场，他们相对于其他的队就吃亏了．对这种情形的详细讨论将在后面进行．)将Ti对Tj的上述得分aij用Tj的强弱系数xj，加权，则Ti对Tj的得分变为aijxj，Ti的总得分为NiNiixaxay11(1)这样算出的各队的总得分Nyy,,1反映了各队实力强弱的比，可以作为排名的标准．我们的目的是为了求出反映各队实力强弱比的向量),,(1NyyY，但为了求Y又要用到反映各队实力强弱比的另一个向量),,(1NxxX．将X，Y都写成列向量形式，并记矩阵NNijaA)(，则以上的计算公式(1)可以写成矩阵形式AXY(2)由于X未知，当然不能直接从这个公式算出Y来，但既然X与Y同样部是反映各队实力强弱比的向量，有理由认为它们所反映的比相等，即存在正实数λ，使Y=λX．即AX=λX，λ是A的特征根，X是属于λ的特征向量．为叙述方便，我们把矩阵A称为得分矩阵，它的元素ija是iT对jT的各场比赛的平均得分，是非负实数．按矩阵论的术语，A是非负矩阵．按照矩阵论中关于非负矩阵的Perron-Frobenius定理，不可约的非负矩阵存在最大正实特征根，对应于唯一(可相差常数倍)的实特征向量),,(1NxxX’．这里，说某个非负矩阵不可约，是指它不可能仅仅通过各行之间的置换和各列之间的置换化成至少有两个对角块的准对角阵．如果得分矩阵A可约，就意味着N支足球队可以分成若干组(至少两组)，所有的比赛都只在同组的队之间举行．不同组的队之间从未比赛过，在这样的情况下，显然不可能判定不同组的队之间的水平的高低．因此，要能对各队排出名次，至少应要求得分矩阵是不可约的．(如果将每个队用一个顶点表示，两队之间如果有比赛，就在相应的两个顶点之间连一条边，这样得到一个反映各队比赛情况的竞赛图，得分矩阵不可约，即相当于这个竞赛图是连通图．)这时就可以由Perron-Frobenius定理知道A存在最大正实特征根及相应的特征向量X。可以取这个X作为反映各队实力比的向量。在实际计算中，要求出矩阵的特征根需要解一元N次方程，这一般是很困难的，更不用说还要求特征向量了。而上述Perron-Frobenius定理还指出：设)1,1,1(e是全由1组成的N维列向量，A是不可约的非负矩阵，λ是它的最大正实特征根，则极限mmmeAXlim存在，且就是A的对应于λ的特征向量．由此得出计算X的实用算法如下．注意，我们所需要的是),,(1NxxX的各分量的比值．而将各分量同时扩大或缩小相同的倍数后，其比值不变。为了使X由这比值唯一决定，我们将X的各分量同时除以它们的和Nxxx1，即用)/,,/(/1xxxxxXN代替X，化成11Nxx的情形．我们称满足条件11Nxx的向量),,(1NxxX为“归一化向量”．称上述将非负向量),,(1NxxX化成归一化向量X／(x1+…+xN)的过程为“归一化”.先取)1,1,1(e的归一化向量)/1,,/1()1(nnX作为X的初始值．换句话说：既然一开始并不知道各队实力的强弱，不妨先认为各队实力相同．将X=X(1)代入(2)式，算出Y(1)=AX(1)作为Y的最初近似值．(即先不加权，直接计算iT的总分iNiaa1作为y(1)的第i分量．y(1)当然比X(1)更好地反映了各队实力强弱的比，归一化后得到的X(2)作为X的更好的近似值．再用这个X(2)算出Y的更好的近似值y(2)=Ax(2)．这个过程可以不断进行下去，即在得到X的第m个近似值x(m)之后，再由X(m)算出Y(m)，将Y(m)归一化后得到X(m+1)，作为X的第m+1个近似值．由Perron-Frobenius的上述定理可知，这一迭代过程是收敛的，极限)(limmXXm存在且就是A的对应于最大正实特征根的特征向量．实际计算时，只要X(m+1)－X(m)的各分量的绝对值都小于预先给定的误差允许值ε，就可以结束计算，取X=X(m+1)．求A的特征向量X的这一算法，在计算数学中通常叫做“幂方法”．§5水平比矩阵法上面提出的特征向量法，是在建立了得分矩阵NNijaA)(之后，求出A的对应于最大正实特征根的特征向量，作为代表各队水平比的向量，以它为依据来为各队排名次．以下我们还要提出进一步改进后的模型，它们都以求特征向量为基础，都可以叫做特征向量法．这些模型的区别是矩阵A的构造方法不同．我们将上述计算得分矩阵A的特征向量的模型称为：模型3得分矩阵法：矩阵NNijaA)(的元素aij是iT对jT各场比赛按二分制(或三分制)算出的平均得分．当iT与jT没有比赛过时取aij=0.模型3比模型1，2更合理．但仔细考察仍有不合理性：用来加权的向量),,(1NxxX代表的是各队水平的比，而算出的向量AXyyYN),,(1的各分量是各队的得分，严格说起来，向量_),,(1NyyY代表的是各队水平的差而不是比．比如有某个队屡战屡败，得分为0，它所对应的0iy．这当然说明它比别的队都差，但也不能说它与别队的水平比是0，或说别的队的水平是它的无穷大倍．设想将记分制改为：胜一场得1分，平得0分，败得-1分，这也是合理的．这样就相当于将各队的得分各减去1分，Y的各分量同时减去l，它们相互的差不变，但比却变了.而代表各．队水平比的向量X却不应因此改变．由此看来，更合理的办法应该是：用反映iT与jT的水平的比的正实数bij代替aij,用水平比矩阵NNijbB)(来代替得分矩阵．这样，由Y=BX算出的向量Y就仍是水平比向量，它才真正应该与X成正比从而是特征向量.水平比矩阵B与得分矩阵A的一个显著区别是：所有的矩阵元素bij都是正实数，不能为0．而且，既然bij是iT与jT的水平比，而bji是iT与jT的水bij与bji就应当互为倒数．特别bii=1(即iT与自己的水平比为1)．这样的矩阵B称为互反矩阵.B的元素bij，(1≤i，j≤N)是各队两两之间的水平比，而所求出的特征向量X就是各队的水平比．这正是“层次分析法”的主要思想．现在的问题是：怎样具体算出水平比矩阵B呢?显然应当根据iT与jT比赛的成绩来算出bij。很自然会想到用Ti，Tj相互比赛得分的比aij/aji作为bij，这样bji=aji/aij自然也就是bij。的倒数了．但这也有一个问题，假如aji=0怎么办?我们可以认为，凡是有资格参加比赛的队Ti的水平都不是0，而是有一个起码的水平分a0(a是待定参数)．将这个起码分a加上比赛得分aij，作为Ti对Tj的水平分．反过来，a+aji是iT对jT的水平分，而)/()(jiijijaaaab就可作为iT与jT的水平比．参数a可由体育界的人士根据经