目 录
一.问题的提出
二.问题的重述
三.模型的假设
四.符号说明
五.模型的建立和求解
六.模型的评价与推广
七.参考文献
足球队排名
摘要
本论文针对足球的排名问题设计一个依据各队的成绩排出各队的名次的模型。对于这个足球队排名问题,我们采用竞赛图法和层次分析法这两种方法给出足球队的排名顺序。用竞赛图法我们应该先建立竞赛图,以n个队,T1,T2,T3„.Tn为竞赛图的G的顶点集建立竞赛图G的边集就可以算出各队的排名顺序。这个名次正是比赛成绩所体现的各队实力的顺序,所建立的模型充分考虑了排名结果对各场比赛成绩的重要性的反馈影响基本上消除了由于比赛对手的强弱不同造成的不公平现象,本模型比较完满的解决了足球队排名出问题,而且经过简单的修改,他可适用于任何一种对抗赛的排名。
关键词:竞赛图 、邻接矩阵、最大特征值、特征向量
一、 提出问题
附表给出的是我国12支球队字1988~1989年全国甲级联赛中的成绩,要求建立数学模型,对各队进行排名次。排名的目的是根据比赛成绩排出反映各队正是实力状况的一个顺序,所以说一个好的排名算法应满足下面的一些基本要求: (1) 保序性:我们认为各队的真实实力水平在成绩表中反映出
来,所以根据排名的目的,我们要求排名顺序与成绩表所反映的各队的真实水平是一致的。
(2) 稳定性:成绩表中校的变动不会对排名造成巨大的影响。 (3) 能够处理不同场次的权重:应为不同比赛在排名中的地位
不同,往往会出现有的对不信遇到较强的对而输掉,避免由于对手的强弱不同造成的不公平 (4) 能够准确的进行补残:两个队之间没有打比赛,我们只为
成绩表残缺,对于两队成绩的残缺,只能通过他们同其他队的比赛成绩判断他们实力的大小。 (5) 能够判断成绩表的可约性。 (6) 容忍不一致现象
(7) 对数据可依赖程度给出较为精确的描述。
二、 问题的重述
下表给出了我国12 只足球队在1988—1989 年全国足球甲级联赛中的成绩要求(见附表一)
1) 设计一个依据这些成绩排出诸队名次的算法并给出用该算法排名次的结果
2) 把算法推广到任意N 个队的情况
3) 讨论数据应具备什么样的条件用你的方法才能够排出诸队的名次
对下表的说明
1) 12 支球队依次记作 T1,T2,··· T12 2) 符号 X 表示两队未曾比赛
3) 数字表示两队比赛结果如T3 行与T8 列交叉处的数字表示T3 与T8 比赛
了2 场T1 与T2 的进球数之比为 0:1 和 3 :1
三、 模型的假设
根据建边情况,可建立矩阵A=aij如下: 1)aii=0;
2)当i≠j时,若Ti,Tj建边,则取aij=1,aji=0; 若Ti,Tj之间未建边,则aij、 aji不计数 则建立A的矩阵如下表所示: T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 T11 T1 0 0 1 1 1 0 0 1 T2 0 0 1 1 1 0 T3 1 1 0 1 1 1 0 1 1 T4 0 0 0 0 0 0 0 0 0 0 T5 0 0 1 0 0 T6 0 0 0 1 1 0 T7 1 1 1 0 1 1 1 1 T8 1 0 1 0 0 1 T9 0 0 1 0 0 1 1 T10 1 0 1 0 0 0 1 T11 0 0 0 0 0 T12 1 0 0 0 1 (2)、对i从1到n计分,其计算得分量为ai,然后再计算其二级的分量a(2)i其计算结果如下: 一级得分向量:
(a1,a2, a3, a4,a5, a6, a7, a8, a9, a10, a11, a12)=(4,3,7,0,1,2,8,3,4,4,0,2) 二级得分向量:
(a(2)(2)(2)1,a(2)2, a3, a(2)4,a(2)5, a(2)6, a7, a(2)8, a(2)9, a(2)(2)(2)10, a11, a12)=(7,6,17,0,0,1,24,4,6,5,0,1)
三级得分向量:
(a(3)3)(3)1,a(3)2,a(3)(3)3)3, a4,a(5, a(6, a7, a(3)(3)
8, a(3)(3)(3)
9, a10, a11, a12)= (7,7,23,0,0,0,40,7,12,7,0,1) (3)、i从1到n循环,j从1 到n循环。
如果Ti与Tj之间没有边连接,则比较ai与aj,如果ai>aj则建立(Ti,Tj),如果ai
i与aj,
以数值大的对队为尾建边,否则Ti与Tj两队随机决定胜负并建边,从而得邻接矩阵,根据上述所示,可以得到下面的情况:
1、Ti与Tj之间建边 1)、aii=0;
2)、当i≠j时,若Ti,Tj建边,则取aij=1,aji=0
3,Ti与Tj之间为建边
1) ai>aj,aij=1;
T12 0 1 1 1 0 0
2) ai
3) a(2)(2)
i>aj,aij=1;
4) a(2)(2)
i
5) a(2)(2)
i
如下所示: T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 T11 T12 T1 0 1 0 1 1 1 0 0 1 1 1 1 T2 0 0 0 1 1 1 0 1 1 0 1 1 T3 1 1 0 1 1 1 0 1 1 1 1 1 T4 0 0 0 0 0 0 0 0 0 0 0 0 T5 0 0 0 1 0 0 0 0 0 0 1 0 T6 0 0 0 1 1 0 0 0 0 0 1 1 T7 1 1 1 1 1 1 0 1 1 1 1 1 T8 1 0 0 1 1 0 0 0 0 1 1 T9 0 0 0 1 1 1 0 1 0 1 1 1 T10 0 1 0 1 1 1 0 1 0 0 1 1 T11 0 0 0 1 0 0 0 0 0 0 0 0 T12 0 0 0 1 1 0 0 0 0 0 1 0
(4)经过邻接矩阵可以得到8个竞赛图G1,G2,G3,G4,G5,G6,G7,G8
如下图所示:
对G3求得其邻接矩阵为下图所示: T1 T2 T8 T9 T1 0 1 0 1 T2 0 0 1 1 T8 1 0 0 0 T9 0 0 1 0 T10 0 1 1 0
用matlab算出这个邻接矩阵的最大特征值和相应的特征向量
T101 0 0 1 0
考虑到一级和二级的得分向量,其排名顺序为: 有强到弱
T7,T3,T1,T9,T10,T2,T8,T6,T12,T11,T5,T4
这种排法是合理的,首先T7踢了9场比赛,8胜1平,T4踢了9场比赛,全部输掉。所以T7排第一。T4排最末是合理的,对T3与T1 两队,他们在其他比赛中,只有与T9,T4,T5的比赛中,T1比T3稍好些,而在其余6个对的比赛中,T3的成绩都由于T1,而且在T3与T1 的比赛时,在净胜球方面占了上风,因此将T3排在T1前面是合适的。 方法二、层次分析法
(问题二)、把算法推广到任意N 个队的情况 (一)模型的设计
1)我们用wi表现Ti对的实力的强弱,则用 w=(w1,w2,w3,„wn)为真实实力的向量,有假设可知,他也为排名的向量。
2)我们用aij表示Ti对Tj这场比赛中,Ti对Tj的相对强弱程度,当成绩残缺是我们约定aij=0,显然有:
(i)aij≥0 (ii)aji=1/aij (iii)aii=1 矩阵A=(aij)n*n成为比赛成绩的判断矩阵;
3)称判断矩阵A是一致,若对任意的1≤i,k,j≤n满足aij*ajk=aik,则A 一致存在w,使得
A=(wi/wj)n*n
称A的最大特征根§max为主特征根,对应于§max的主特征向量w称为主特征向量,
且wi>0
4)构造判断矩阵A
i从1到n循环,j从1 到n循环。
(1)若Ti与Tj互胜场次相等,则 (i) 净胜球为0时,令aij= aji=1;
(ii) Ti净胜球多时以Ti净胜Tj一场做后续处
理。
(2)若Ti净胜Tjk场(场数,不是进球数)且k>0,则 (i)bij=2k(1≤k≤4);
(ii)mij=Ti胜Tj平均每场净胜球数;
Dij=1(mij>2),dij=0(0≤mij≤2),dij=-1(mij
则,可建立如下的判断矩阵A
6)构造辅助矩阵B
i从1到n循环,j从1 到n循环
bij=aij (i≠j且aij≠0); bij=mi+1 (i=j,其中mi为A 的第i
6) max利用“和法”计算,
(1) 将A的每一列向量归一化得
(2)对
按行求和得
(3)将归一化得
即为近视特征向量,
(4)计算,
作为最大特征根的近似值。
7)按w的各分量由大到小的顺序对参赛各队排名次
六、 模型的评价与推广
通过与现行的一些比较,用竞赛图法求出排名的结果,是比较简单的,但要将其推广到n的对来进行排名,是比较麻烦的,主要是在计算机上运行的结果不太明确,虽然用matlab能够将其最大特征值和特征向量算来,但结果太长,且不容易比较。但对于只有有限个对的排名是比较简单的。对于n个队,我们采用了层次分析法,他就具有明显的优势了: (1) 它存在反馈机制,并且具有稳定性,保证了排名的稳定性,
保证了排名的公平性; (2) 能较准确的处理残缺、不一致等性质很差的数据,对比赛
程序没有严格的要求; (3) 灵活机动,这包括它提供了对比赛成绩表进行取舍的参考
指标,以及他适合N个队任何对抗赛的排名; (4) 满足保序性。
模型的一个缺点就是算法复杂。在从成绩构造判断矩阵时用到的方法也不是最好的,这一步在整个模型里引入误差最大,稍微复杂一点的方法是根据成绩通过查表或专家咨询活的实力对比值。 另外一个不足之处是在莫残缺元素过多的情况下排名的稳定性和可靠性较低。
模型的改进余地也是很大的,他只是使用了层次分析法中单一准则一个层次的排序方法,可以考虑使用多个准则和梯阶层次,比
如将净胜球数,净胜局数,射门次数,犯规次数作为四个准则,两个层次。
七、参考文献
【1】 姜启源等。数学模型。高等教育出版社,2003 【2】 周仪仺、郝孝量,数学建模实验,西安交通大学出版社,
2007
【3】 费伟勁,线性代数,复旦大学出版社,2008
目 录
一.问题的提出
二.问题的重述
三.模型的假设
四.符号说明
五.模型的建立和求解
六.模型的评价与推广
七.参考文献
足球队排名
摘要
本论文针对足球的排名问题设计一个依据各队的成绩排出各队的名次的模型。对于这个足球队排名问题,我们采用竞赛图法和层次分析法这两种方法给出足球队的排名顺序。用竞赛图法我们应该先建立竞赛图,以n个队,T1,T2,T3„.Tn为竞赛图的G的顶点集建立竞赛图G的边集就可以算出各队的排名顺序。这个名次正是比赛成绩所体现的各队实力的顺序,所建立的模型充分考虑了排名结果对各场比赛成绩的重要性的反馈影响基本上消除了由于比赛对手的强弱不同造成的不公平现象,本模型比较完满的解决了足球队排名出问题,而且经过简单的修改,他可适用于任何一种对抗赛的排名。
关键词:竞赛图 、邻接矩阵、最大特征值、特征向量
一、 提出问题
附表给出的是我国12支球队字1988~1989年全国甲级联赛中的成绩,要求建立数学模型,对各队进行排名次。排名的目的是根据比赛成绩排出反映各队正是实力状况的一个顺序,所以说一个好的排名算法应满足下面的一些基本要求: (1) 保序性:我们认为各队的真实实力水平在成绩表中反映出
来,所以根据排名的目的,我们要求排名顺序与成绩表所反映的各队的真实水平是一致的。
(2) 稳定性:成绩表中校的变动不会对排名造成巨大的影响。 (3) 能够处理不同场次的权重:应为不同比赛在排名中的地位
不同,往往会出现有的对不信遇到较强的对而输掉,避免由于对手的强弱不同造成的不公平 (4) 能够准确的进行补残:两个队之间没有打比赛,我们只为
成绩表残缺,对于两队成绩的残缺,只能通过他们同其他队的比赛成绩判断他们实力的大小。 (5) 能够判断成绩表的可约性。 (6) 容忍不一致现象
(7) 对数据可依赖程度给出较为精确的描述。
二、 问题的重述
下表给出了我国12 只足球队在1988—1989 年全国足球甲级联赛中的成绩要求(见附表一)
1) 设计一个依据这些成绩排出诸队名次的算法并给出用该算法排名次的结果
2) 把算法推广到任意N 个队的情况
3) 讨论数据应具备什么样的条件用你的方法才能够排出诸队的名次
对下表的说明
1) 12 支球队依次记作 T1,T2,··· T12 2) 符号 X 表示两队未曾比赛
3) 数字表示两队比赛结果如T3 行与T8 列交叉处的数字表示T3 与T8 比赛
了2 场T1 与T2 的进球数之比为 0:1 和 3 :1
三、 模型的假设
根据建边情况,可建立矩阵A=aij如下: 1)aii=0;
2)当i≠j时,若Ti,Tj建边,则取aij=1,aji=0; 若Ti,Tj之间未建边,则aij、 aji不计数 则建立A的矩阵如下表所示: T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 T11 T1 0 0 1 1 1 0 0 1 T2 0 0 1 1 1 0 T3 1 1 0 1 1 1 0 1 1 T4 0 0 0 0 0 0 0 0 0 0 T5 0 0 1 0 0 T6 0 0 0 1 1 0 T7 1 1 1 0 1 1 1 1 T8 1 0 1 0 0 1 T9 0 0 1 0 0 1 1 T10 1 0 1 0 0 0 1 T11 0 0 0 0 0 T12 1 0 0 0 1 (2)、对i从1到n计分,其计算得分量为ai,然后再计算其二级的分量a(2)i其计算结果如下: 一级得分向量:
(a1,a2, a3, a4,a5, a6, a7, a8, a9, a10, a11, a12)=(4,3,7,0,1,2,8,3,4,4,0,2) 二级得分向量:
(a(2)(2)(2)1,a(2)2, a3, a(2)4,a(2)5, a(2)6, a7, a(2)8, a(2)9, a(2)(2)(2)10, a11, a12)=(7,6,17,0,0,1,24,4,6,5,0,1)
三级得分向量:
(a(3)3)(3)1,a(3)2,a(3)(3)3)3, a4,a(5, a(6, a7, a(3)(3)
8, a(3)(3)(3)
9, a10, a11, a12)= (7,7,23,0,0,0,40,7,12,7,0,1) (3)、i从1到n循环,j从1 到n循环。
如果Ti与Tj之间没有边连接,则比较ai与aj,如果ai>aj则建立(Ti,Tj),如果ai
i与aj,
以数值大的对队为尾建边,否则Ti与Tj两队随机决定胜负并建边,从而得邻接矩阵,根据上述所示,可以得到下面的情况:
1、Ti与Tj之间建边 1)、aii=0;
2)、当i≠j时,若Ti,Tj建边,则取aij=1,aji=0
3,Ti与Tj之间为建边
1) ai>aj,aij=1;
T12 0 1 1 1 0 0
2) ai
3) a(2)(2)
i>aj,aij=1;
4) a(2)(2)
i
5) a(2)(2)
i
如下所示: T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 T11 T12 T1 0 1 0 1 1 1 0 0 1 1 1 1 T2 0 0 0 1 1 1 0 1 1 0 1 1 T3 1 1 0 1 1 1 0 1 1 1 1 1 T4 0 0 0 0 0 0 0 0 0 0 0 0 T5 0 0 0 1 0 0 0 0 0 0 1 0 T6 0 0 0 1 1 0 0 0 0 0 1 1 T7 1 1 1 1 1 1 0 1 1 1 1 1 T8 1 0 0 1 1 0 0 0 0 1 1 T9 0 0 0 1 1 1 0 1 0 1 1 1 T10 0 1 0 1 1 1 0 1 0 0 1 1 T11 0 0 0 1 0 0 0 0 0 0 0 0 T12 0 0 0 1 1 0 0 0 0 0 1 0
(4)经过邻接矩阵可以得到8个竞赛图G1,G2,G3,G4,G5,G6,G7,G8
如下图所示:
对G3求得其邻接矩阵为下图所示: T1 T2 T8 T9 T1 0 1 0 1 T2 0 0 1 1 T8 1 0 0 0 T9 0 0 1 0 T10 0 1 1 0
用matlab算出这个邻接矩阵的最大特征值和相应的特征向量
T101 0 0 1 0
考虑到一级和二级的得分向量,其排名顺序为: 有强到弱
T7,T3,T1,T9,T10,T2,T8,T6,T12,T11,T5,T4
这种排法是合理的,首先T7踢了9场比赛,8胜1平,T4踢了9场比赛,全部输掉。所以T7排第一。T4排最末是合理的,对T3与T1 两队,他们在其他比赛中,只有与T9,T4,T5的比赛中,T1比T3稍好些,而在其余6个对的比赛中,T3的成绩都由于T1,而且在T3与T1 的比赛时,在净胜球方面占了上风,因此将T3排在T1前面是合适的。 方法二、层次分析法
(问题二)、把算法推广到任意N 个队的情况 (一)模型的设计
1)我们用wi表现Ti对的实力的强弱,则用 w=(w1,w2,w3,„wn)为真实实力的向量,有假设可知,他也为排名的向量。
2)我们用aij表示Ti对Tj这场比赛中,Ti对Tj的相对强弱程度,当成绩残缺是我们约定aij=0,显然有:
(i)aij≥0 (ii)aji=1/aij (iii)aii=1 矩阵A=(aij)n*n成为比赛成绩的判断矩阵;
3)称判断矩阵A是一致,若对任意的1≤i,k,j≤n满足aij*ajk=aik,则A 一致存在w,使得
A=(wi/wj)n*n
称A的最大特征根§max为主特征根,对应于§max的主特征向量w称为主特征向量,
且wi>0
4)构造判断矩阵A
i从1到n循环,j从1 到n循环。
(1)若Ti与Tj互胜场次相等,则 (i) 净胜球为0时,令aij= aji=1;
(ii) Ti净胜球多时以Ti净胜Tj一场做后续处
理。
(2)若Ti净胜Tjk场(场数,不是进球数)且k>0,则 (i)bij=2k(1≤k≤4);
(ii)mij=Ti胜Tj平均每场净胜球数;
Dij=1(mij>2),dij=0(0≤mij≤2),dij=-1(mij
则,可建立如下的判断矩阵A
6)构造辅助矩阵B
i从1到n循环,j从1 到n循环
bij=aij (i≠j且aij≠0); bij=mi+1 (i=j,其中mi为A 的第i
6) max利用“和法”计算,
(1) 将A的每一列向量归一化得
(2)对
按行求和得
(3)将归一化得
即为近视特征向量,
(4)计算,
作为最大特征根的近似值。
7)按w的各分量由大到小的顺序对参赛各队排名次
六、 模型的评价与推广
通过与现行的一些比较,用竞赛图法求出排名的结果,是比较简单的,但要将其推广到n的对来进行排名,是比较麻烦的,主要是在计算机上运行的结果不太明确,虽然用matlab能够将其最大特征值和特征向量算来,但结果太长,且不容易比较。但对于只有有限个对的排名是比较简单的。对于n个队,我们采用了层次分析法,他就具有明显的优势了: (1) 它存在反馈机制,并且具有稳定性,保证了排名的稳定性,
保证了排名的公平性; (2) 能较准确的处理残缺、不一致等性质很差的数据,对比赛
程序没有严格的要求; (3) 灵活机动,这包括它提供了对比赛成绩表进行取舍的参考
指标,以及他适合N个队任何对抗赛的排名; (4) 满足保序性。
模型的一个缺点就是算法复杂。在从成绩构造判断矩阵时用到的方法也不是最好的,这一步在整个模型里引入误差最大,稍微复杂一点的方法是根据成绩通过查表或专家咨询活的实力对比值。 另外一个不足之处是在莫残缺元素过多的情况下排名的稳定性和可靠性较低。
模型的改进余地也是很大的,他只是使用了层次分析法中单一准则一个层次的排序方法,可以考虑使用多个准则和梯阶层次,比
如将净胜球数,净胜局数,射门次数,犯规次数作为四个准则,两个层次。
七、参考文献
【1】 姜启源等。数学模型。高等教育出版社,2003 【2】 周仪仺、郝孝量,数学建模实验,西安交通大学出版社,
2007
【3】 费伟勁,线性代数,复旦大学出版社,2008