足球队排名次.doc

B题 足球队排名次 下表给出了我国12支足球队在19881989年全国足球甲级联赛中的成绩，要求 1）设计一个依据这些成绩排出诸队名次的算法，并给出用该算法排出名次的结果。 2）把算法推广到任意N个队的情况。 3）讨论：数据应具备什么样的条件，用你的方法才能够排出诸队的名次。 对下表的说明： 1）12支球队依次记作T1，T2，。T12。 2）符号X表示两队未曾比赛。 3）数字表示两队比赛的结果，如T3行与T8行交叉的数字表示：T3与T8比赛了2场；T3与T8的进球数之比为0：1和3：1。 TTTTTTTTTTTTTX0：11：00：02：21：00：22：03：11：03：11：00：11：30：22：11：04：01：11：1XXTX2：00：10：02：01：12：11：11：10：00：02：01：10：20：0XXT1：3X0：04：21：10：02：13：01：01：40：13：11：02：30：12：0XXTX2：30：10：52：32：11：30：10：00：11：1XXTX0：1XXXX1：01：20：01：1TXXXXXXXTX1：02：00：02：13：01：00：13：13：02：21：13：12：0TX1：22：01：00：13：03：10：0TX1：00：01：01：0TX1：02：01：1TX1：21：1TX从表中给出的比赛成绩看，数据是不整齐的：某些队之间有三场比赛的成绩，另外某些队之间则只有两场或一场比赛的成绩，还有一些队之间没有比赛成绩以下的解答主要参考了中国科技大学获特等奖队的论文1 合理的假设1排名仅根据现有比赛结果，不考虑其他因素。2每场比赛对于估计排名的重要程度是一样的，具有相同的可信度，不同的比赛相互独立3有些队之间没有比赛，完全是由于比赛安排的原因造成的，不是由于球队在以前比赛中的胜负造成的，也不是由于某一方弃权造成的(根据比赛规则，弃权一方应被判输球，从而应在数据表中显示出来)4按流行的赛制，以二分制计算比赛积分，即：胜一场得2分，平一场得1分，输一场得0分(当然也可以按三分制计算积分，将胜一场的得分改为3分，以鼓励进攻，这样的修改对我们的模型不造成任何困难.).作出以上的假设，一方面是由于原题没有提供更多的信息，我们没有理由认为某场比赛比别的比赛更具有特殊性等当然，按照数学建模竞赛的规则，在原题条件不够的情况下允许自己查阅资料，补充信息但本题中如果真的从体育资料中去查出19881989年我国足球甲级队联赛的具体情况，在模型中予以反映，所建立的模型就失去了普遍意义因此，做出上述假设的更重要的出发点是为了使所建立的模型能够具有普适性，适合于各种不同的比赛 2 问题的分析 众所周知，足球界对同一赛事中比赛结果的排名有现成的算法例如：循环比赛结果的排名，按前述二分制(或三分制)计算总积分，以总积分的高低来决定名次的先后(总积分相同者，再比净胜球数的多少，总进球数的多少，等等)但是，这一算法着眼于排出比赛的胜负名次，并不总能合理地反映出各队真实水平的高低比赛名次当然主要决定于各队的真实水平，但各队在比赛场次安排中“运气”的好坏也有相当的影响比如，某队在比赛中避开了强队而大胜弱队，就是由于“运气”好而得分高的例子我们不能完全排除这一类因素，但应尽可能合理地考虑并处理它。 另外，足球界的上述算法只适用于同一赛事的比赛结果，对于不同赛事的混合结果，特别对于比赛场次及数据参差不齐的情况(如本题所给的数据)，就显得无能为力了。我们的目标就是要针对这种不规则的比赛数据提出一种算法，尽可能合理地反映各队的真实水平3 初步的排名方案 我们先从最通行的算法开始，通过分析其缺点而一步步加以改进 模型1总积分法：按两分制(或三分制)计算各队在所有比赛中总的积分，按总积分的高低排出名次。 但是，在所给的数据表中，各队比赛场次有多有少，而按我们的假设，比赛场次的多少并不是由于该队在以前的比赛中的胜负所致如果按总计分法，则比赛场次少的队吃亏为了克服这一不合理性，很自然改进为： 模型2平均积分法：将每个队的总积分除以该队参加比赛的场数，得出每场平均积分按各队平均积分的高低来排名。上述方法当然还可以做出一些小的改进比如再将净胜球数、总进球数等因素也折算成一定的分数，计入总分。4 特征向量法的提出 在我们看来，以上总积分法和平均记分法(及其考虑了净胜球数、总进球数之后的改良版本)最大的不合理性是：在计算比赛得分时没有考虑对手的强弱比如，胜强队和胜弱队同样都得2分，这就明显不合理由此看来，更合理的算法应当是：胜强队得分应该多一些，胜弱队的得分应该少一些用数学语言说，应该给每个队赋予一个“强弱系数”xi，(非负实数)，来反映该队实力的强弱，强队的系数大，弱队的系数小如果对手的强弱系数为xi，你胜了它，你的得分就用这个系数对基本得分(2分)进行加权，为2分xi分。为了叙述方便，将第i队记为Ti(1iN)要算出Ti的总的得分，先对每个Tj，算出Ti对Tj的各场比赛中按二分制的平均得分，记为aij如果Ti与Tj没有比赛过，就取aij=0特别aii=0(严格说来，对没有比赛过的队Ti，Tj，取aij=0并不合理，这等于是判这两个队各输一场，他们相对于其他的队就吃亏了对这种情形的详细讨论将在后面进行)将Ti对Tj的上述得分aij用Tj的强弱系数xj，加权，则Ti对Tj的得分变为aijxj，Ti的总得分为 (1)这样算出的各队的总得分反映了各队实力强弱的比，可以作为排名的标准 我们的目的是为了求出反映各队实力强弱比的向量，但为了求Y又要用到反映各队实力强弱比的另一个向量将X，Y都写成列向量形式，并记矩阵，则以上的计算公式(1)可以写成矩阵形式 (2)由于X未知，当然不能直接从这个公式算出Y来，但既然X与Y同样部是反映各队实力强弱比的向量，有理由认为它们所反映的比相等，即存在正实数，使Y=X即AX=X，是A的特征根，X是属于的特征向量 为叙述方便，我们把矩阵A称为得分矩阵，它的元素是对的各场比赛的平均得分，是非负实数按矩阵论的术语，A是非负矩阵按照矩阵论中关于非负矩阵的Perron-Frobenius定理，不可约的非负矩阵存在最大正实特征根，对应于唯一(可相差常数倍)的实特征向量这里，说某个非负矩阵不可约，是指它不可能仅仅通过各行之间的置换和各列之间的置换化成至少有两个对角块的准对角阵如果得分矩阵A可约，就意味着N支足球队可以分成若干组(至少两组)，所有的比赛都只在同组的队之间举行不同组的队之间从未比赛过，在这样的情况下，显然不可能判定不同组的队之间的水平的高低因此，要能对各队排出名次，至少应要求得分矩阵是不可约的(如果将每个队用一个顶点表示，两队之间如果有比赛，就在相应的两个顶点之间连一条边，这样得到一个反映各队比赛情况的竞赛图，得分矩阵不可约，即相当于这个竞赛图是连通图)这时就可以由Perron-Frobenius定理知道A存在最大正实特征根及相应的特征向量X。可以取这个X作为反映各队实力比的向量。 在实际计算中，要求出矩阵的特征根需要解一元N次方程，这一般是很困难的，更不用说还要求特征向量了。而上述Perron-Frobenius定理还指出： 设是全由1组成的N维列向量，A是不可约的非负矩阵，是它的最大正实特征根，则极限存在，且就是A的对应于的特征向量由此得出计算X的实用算法如下注意，我们所需要的是的各分量的比值而将各分量同时扩大或缩小相同的倍数后，其比值不变。为了使X由这比值唯一决定，我们将X的各分量同时除以它们的和，即用代替X，化成的情形我们称满足条件的向量为“归一化向量”称上述将非负向量化成归一化向量X(x1+xN)的过程为“归一化”.先取的归一化向量作为X的初始值换句话说：既然一开始并不知道各队实力的强弱，不妨先认为各队实力相同将X=X(1)代入(2)式，算出Y(1)=AX(1)作为Y的最初近似值(即先不加权，直接计算的总分作为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的上述定理可知，这一迭代过程是收敛的，极限存在且就是A的对应于最大正实特征根的特征向量实际计算时，只要X(m+1)X(m)的各分量的绝对值都小于预先给定的误差允许值，就可以结束计算，取X=X(m+1)求A的特征向量X的这一算法，在计算数学中通常叫做“幂方法”5 水平比矩阵法上面提出的特征向量法，是在建立了得分矩阵之后，求出A的对应于最大正实特征根的特征向量，作为代表各队水平比的向量，以它为依据来为各队排名次以下我们还要提出进一步改进后的模型，它们都以求特征向量为基础，都可以叫做特征向量法这些模型的区别是矩阵A的构造方法不同我们将上述计算得分矩阵A的特征向量的模型称为：模型3 得分矩阵法：矩阵的元素aij是对各场比赛按二分制(或三分制)算出的平均得分当与没有比赛过时取aij=0.模型3比模型1，2更合理但仔细考察仍有不合理性：用来加权的向量代表的是各队水平的比，而算出的向量的各分量是各队的得分，严格说起来，向量_代表的是各队水平的差而不是比比如有某个队屡战屡败，得分为0，它所对应的这当然说明它比别的队都差，但也不能说它与别队的水平比是0，或说别的队的水平是它的无穷大倍设想将记分制改为：胜一场得1分，平得0分，败得-1分，这也是合理的这样就相当于将各队的得分各减去1分，Y的各分量同时减去l，它们相互的差不变，但比却变了.而代表各队水平比的向量X却不应因此改变由此看来，更合理的办法应该是：用反映与的水平的比的正实数bij代替aij , 用水平比矩阵来代替得分矩阵这样，由Y=BX算出的向量Y就仍是水平比向量，它才真正应该与X成正比从而是特征向量.水平比矩阵B与得分矩阵A的一个显著区别是：所有的矩阵元素bij都是正实数，不能为0而且，既然bij是与的水平比，而bji是与的水bij与bji就应当互为倒数特别bii=1 (即与自己的水平比为1)这样的矩阵B称为互反矩阵. B的元素bij，(1i，jN)是各队两两之间的水平比，而所求出的特征向量X就是各队的水平比这正是 “层次分析法”的主要思想 现在的问题是：怎样具体算出水平比矩阵B呢? 显然应当根据与比赛的成绩来算出bij。很自然会想到用Ti，Tj相互比赛得分的比aij/aji作为bij，这样bji=aji/aij自然也就是bij。的倒数了但这也有一个问题，假如aji=0怎么办? 我们可以认为，凡是有资格参加比赛的队Ti的水平都不是0，而是有一个起码的水平分a0(a是待定参数)将这个起码分a加上比赛得分aij，作为Ti对Tj的水平分反过来，a+aji是对的水平分，而就可作为与的水平比参数a可由体育界的人士根据经验来确定，它的大小在一定程度上反映比赛的成绩的可信程度，以及偶然因素起作用的机会的大小这样就得到模型4参数法：预先取定参数a(正实数)设任意对的各场比赛平均得分为aij,则取所有的bij组成水平比矩阵.再求出B的对应于最大正实特征根的特征向量作为反映各队水平比的向量 当与未比赛时，两队水平比bij应怎样选取呢? 我们取.这样的取法的正确性当然无可争议但问题是xi, xj未知，当ij时不能得到bij的确切的值(当i=j时有确切值.)记J=1JN与比赛过，S：1JNjJ是与Ti未比赛过的队的编号的集合(包括i在内)则对任意1iN，当jJ时bij可以由比赛成绩算出，是已知的；而当jS时bij=xi/xj. 我们有其中是与未比赛过的队(包括自己)的个数，可见，我们可以用矩阵代替B来进行计算也就是说，如果共有r个队(包括Ti自己)没有和Ti比赛过，则取bii=r，而当与没有比赛(且ij)时将bij, bji都取作0再用幂方法求所得到的矩阵的特征向量即可。6 概率法上述模型4中的参数a的选定带有主观随意性，不能令人满意而且，a是否应因，的不同而易，也是问题更主要的问题是：计算bij时所用的得分aij是用平均积分法得出的，其中有不合理性：试想如果与只赛了一场，一战一胜得2分，平均得aij=2；假如对赛了三场，三战三胜，共得6分，平均得分aij仍为2分但实际上，三战三胜的难度显然比一战一胜大，而两者得分相同，这就不合理应该让三战三胜的得分比一战一胜的得分多，这才是合理的为什么我们觉得三战三胜的难度显然比一战一胜大呢? 假如胜的概率是70，则一战一胜的概率也就是70，很有可能实现；但三战三胜的概率就只有(70)3=343，很难实现，如果实现了，就有理由认为胜的概率不只70，而有可能是89由此得出以下的模型模型5 概率法：对任何两个队，客观存在着胜的概率pij，用pij和pji的比bij=pij/pji作为与的水平比，构造出水平比矩阵B，算出各队的水平比向量 以pij/pji作为与的水平比，其合理性当然是毋容置疑的但同样显而易见的问题是：怎样找出概率pij来呢? 当然只能以两队的比赛成绩为依据，从成绩表中的数据算出pij来从统计的角度看，两队进行若干场比赛的结果，并不能绝对地反映两队水平的高低但这些结果却是pij和pji在一定程度上的实现我们设法从这些结果反推出pij，pji，具体来说，根据在对的各场比赛中的总得分(注意不是平均积分)来计算pij。我们的主要想法是：假如pij，pji预先给定了，则可以由它们分别算出在对的各场比赛中总共得0分，1分，2分，的概率，这些概率都是pij和pji的函数假如的实际总得分为m分，就有理由认为得m分的概率比得其它分的概率都大(这就是极大似然估计的思想：认为实际发生了的事件比没有发生的事件的概率更大)这样就可以得到关于pij，pji的一些不等式，其中包含参数m解这些不等式就可得到pij，pji对于m的依赖关系，从而可以由已知数m(由比赛成绩表算出)决定未知的户pij，pji.将这个想法付诸实施时，需要解决一个技术性问题：平局的概率怎样计算? 为此，我们将每场比赛想象成由两个半场组成，每半场只有胜负，没有平局(注意这只是为分析问题而想象的两个半场，并不是实际比赛的上半场和下半场)在两个半场中一胜一负就是全场的平局，而两胜、两负则分别是全场的胜和负我们还规定在半场中胜得1分，负得0分，则全场的胜，平，负的得分就分别是2，1，0分，与原来的规定一致将在半场中战胜的概率qij作为唯一一个独立参数，简记为q，则qij=1-q由此可以算出对进行多场比赛时的各种得分情况出现的概率比如，在三场比赛中如果得4分(可能是两胜一负或一胜两平)，那就是在6个“半场”中胜4个半场，负2个半场，概率为一般的，在n场比赛中得m分的概率为如果在对的n场比赛中实际的总得分为m，则认为得m分的概率比得其他分的概率都大，即：对所有的0kn，km对给定的m值解出这些不等式，就得到由m决定的q的取值范围，结果如下：一场比赛二场比赛三场比赛积分q积分q积分q2lOO67一lO33一O67OO334321OO8一lO6-O8O4一O602一O4O-O2654321OO86一lO71一O86O57一O71043一O57029一O43O14一O29O一014 这里，的每一种得分值m对应于q的一个取值范围将q值到底定在这个范围里的什么位置呢? 这个选择的自由仍留给体育界人士，按比赛结果的可信度来决定比如，可以选在范围的下限或上限，或中间一个更为合理的处理办法是：根据净胜球数w的多少来决定把q值选在所得范围的高处或低处，也就是说，将q设计成w的某个递增函数，其取值范围就是的总得分m所决定的q的范围，随w的增加而趋近于这个范围的上界q值决定之后，就可算出pij，pji从而算出bij(等于q2(1-q)2)也不妨直接取bij=q(1-q)与没有比赛的情形，按模型4同样的方法处。7 模型的检验和比较前述五种方法得到的排名结果如下表：名次方案123456789101112(1)T7T1T3T9T2T10T8T5T4T12T6T11(2)T7T1T3T9T2T10T8T6T5T12T11T4(3)T7T1T3T2T10T9T8T6T5T12T11T4(4)T7T1T3T10T2T9T8T6T5T12T11T4(5)T7T1T3T2T10T8T9T6T5T12T4T11其中：(1)总积分法；(2)平均积分法；(3)得分矩阵法；(4)参数珐；(5)概率法既然数学模型必须接受实际检验，那么，为解决这个问题的前述各种模型孰优孰劣，用什么标准检验呢?当然，直观上说，每战必胜的队一定排在第一，每战必败的队一定排在最末，无论用哪一个模型算出来的结果都是这样，这检验不出模型的优劣而互有胜负的队到底谁优谁劣，各种模型的答案不一，似乎又拿不出一个令人信服的客观标准来说明某个模型比别的模型更合理有的同学查出国家体委对1988-1989年甲级足球队的排名来作为标准答案，这也是不对的这一方面使对这一问题的解答失去普遍意义. 同时，任何人的排名结果只能是某一种模型所得的结果，其合理性本身就是被检验的对象而不是检验别人的标准在这方面，中国科大获特等奖队提出的计算机模拟的办法，应该说是一种比较客观，令人信服的检验办法他们的想法其实很简单：在计算机上随机地产生一个按元素大小顺序排列的向量认为代表N支假想的球队的实力强弱的比，决定它们相互比赛胜负的概率在计算机上让这些球队按T规定的胜负概率进行模拟比赛，任意两个队比赛的场次可以是0, 1，2，3场，产生出若干参差不齐的比赛成绩，如本题的数据情况那样然后利用前面所说的各种模型，由这些比赛结果来对这些队进行排名显然，这里的排名结果是有标准答案的，那就是由最初的向量T规定的排名顺序由各种模型的排出的名次，与这个标准答案越接近，就说明这个模型越好，从而用达样的模型按本题的数据表排出的结果也就可以认为更正确为了衡量各种模型排出的名次与预先规定的标准名次的偏差，定义偏差.其中ri是第i个队的标准名次，Ri是模型给它排出的名次为了减少计算机模拟中的随机性的影响，使所得结果更为可靠，可以对同一个T进行多次模拟，计算每种模型所排出的名次的偏差的平均值，按照平均偏差的大小来判定模型的优劣中国科大队在N=12的情形下进行了100次模拟，得出的平均偏差的情况如下：算法12345E21362004172812121198不难看出，检验的结果与前面的分析是一致的，即特征向量算法(模型35)明显优于前面两种模型，而以概率法(模型5)为最优8 模型的进一步分析 1稳定性分忻：一个好的模型所预见的结果不应该由于初始数据的微小波动而有大的改变为检验稳定度，随机地改变一到三场的比赛成绩，以排名结果的变化大小的程度来检验模型的稳定程度，排名结果变化大小的程度按前面所定义的偏差来衡量. 结果发现模型4和5都有很好的稳定程度 2模型4中参数n的选择：依次试取为1至10间的整数值，用前面所说计算机模拟的方法检验，发现取=4时的偏差最小。 9模型的检验补充给定12支足球队间的比赛结果，如何排定它们的名次? 已知的信息是：各队间的比赛场次有多有少，甚至有些队之间从未交战，整个比赛数据是不规则的在这种情况下，什么样的排名规则是合理的?一般地，如何推广到任意n支球队的情况?针对这个问题我们可以设计多种排名算法，并分别用来处理题中的数据，得到各自的结果但到底哪一种算法更好，哪一种排名结果更合理，还必须给出评价一般地，对这些算法的合理程度在理论上做定量的分析是很困难的，只能采取计算机模拟的方法我们首先假定(1)每支球队都有自己的实力水平，这一水平在全部比赛期间大体保持不变(2)两支球队交战时，实力差别越大，强队获胜的可能性就越大(3)称一个排名算法更合理，是指它给出的结果更接近各队的实力顺序在这几条合理的假设下，我们给出测试排名算法的方法如下设n为参赛的球队数，构造一个n元随机向量SS的每个元素是0，1区间内的随机数记si为S的第i个元素，它代表球队的实力记Ri为的实力名次根据向量S的值产生一组比赛数据，具体做法是： 对任意不同的i和j，先用随机数决定和比赛的场数kij，(从0，1，2，3中选取)kij的选取应保证整个比赛图是连通的，即若和不曾比赛(kij=0)，则有，使对任意1lm-1，有和交战过()这是排名算法能够工作的前提条件然后，产生每场比赛的比分不妨设sisj(比强)，按以下经验公式确定在一场比赛中不同结果的概率： , , (1).根据一个0，1均匀分布的随机数的值按(1)式决定比赛的胜者(或者是平局) 0 1设和的比分为gi:gj，则(1) 当胜时，取 gj=rand(4)，gi=gj+1+rand(1.5+6(si-sj) (2)(2) 当胜时，取 gj=rand(4)，gj=gi+1+rand(2) (3) (3)当平局时，取 gi=gj=rand(6) (4)其中，rand(n)产生0n-1均匀分布的随机整数，x是小于等于x的最大整数模拟比赛完成后，用给定算法对球队进行排序记为排得的名次，令 (5)代表算法排名对实力排名的误差显然，E越小表明算法越合理为了消除随机因素带来的干扰，应模拟足够多次，取E的算术平均值瓦作判断的依据设对n=12时，对某6种算法各模拟比赛100次，得到结果如下表表241排名算法平均误差算法12345E21362004172812121198从表中可见，算法4和算法5的平均误差最小进一步检查这两种算法的方差，如果不超过允许的范围，就可以采用它们作为优选方案，并采纳其排名结果