数学建模解决有关足球队排名问题 (2)

五、 模型的建立和求解

方法一、竞赛图法

（问题一）、设计一个依据这些成绩排出诸队名次的算法并给出用该算法排名次的结果

根据问题的假设和比赛成绩表，我们构造竞赛图如下：

以n个参赛队T1,T2,T3,…,Tn为竞赛图G 的顶点，G的边集按如下算法求得：

i从1到n循环，j从1到n循环。

若Ti胜Tj的场次多，则以Ti为尾Tj为头，作边（Ti，Tj）；若Tj胜Ti的场次多，则建边（Tj，Ti），若两队之间胜的场次相同，则以两队比赛进球多的一队为尾，另一头为头建边，否则不建 边。若两队之间没有比赛则不建边。 根据建边情况，可建立矩阵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 T11T1 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)(2)(2)(2)(2)1，a(2)2, a3, a4，a5, a6, a7, a8, a(2)9, a(2), a(2)(2)

1011, a12）=(7,6,17,0,0,1,24,4,6,5,0,1)

- 6 -

T12 0 1 1 1 0 0

三级得分向量：

（a（3）1,a（3）2,a（3）3, a（3）4，a（3）5, a（3）6, a（3）7, a（3）8, a（3）

（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

以数值大的对队为尾建边，否则Ti与Tj两队随机i与aj，

决定胜负并建边，从而得邻接矩阵，根据上述所示，可以得到下面的情况：

1、Ti与Tj之间建边 1)、aii=0；

2)、当i≠j时，若Ti，Tj建边，则取aij=1，aji=0

3，Ti与Tj之间为建边

1） ai>aj，aij=1； 2） ai

（2）（2）

3） ai>aj，aij=1；

（2）（2）

4） ai

（2）（2）

5） ai

如下所示： 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如下图所示：

- 7 -

对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算出这个邻接矩阵的最大特征值和相应的特征向量

考虑到一级和二级的得分向量，其排名顺序为： 由强到弱

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称为主特征向量，

T10 1 0 0 1 0

且wi>0

- 8 -

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<0) (iii)aij=bij+dij,aji=1/aij (2)若Ti与Tj无比赛成绩，则aij=aji=0则根据以上规

则，可建立如下的判断矩阵A T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 T11 T12 T1 1 T2 1 T3 2 T4 1/6 T5 1/2 T6 1/2 T7 4 T8 2 T9 1/5 T10 1 T11 0 T12 0 1 1 2 1/2 1 1/2 1 1 1/2 2 0 0 1/2 1/2 1 1/2 1/2 1/3 2 1/2 1/2 1/2 0 0 6 2 2 1 2 2 1 1/2 2 1 2 2 5 0 2 0 2 0 2 0 0 1/2 0 2 2 2 3 1/2 1/2 1 0 0 0 0 0 0 1/4 1 1/2 1/5 0 0 1 1/4 1/7 1/7 1/2 1/2 1/2 1 2 1/2 0 0 4 1 2 1 1/2 1 5 2 2 1/2 0 0 7 1/2 1 1/4 1/2 1/2 1 1/2 2 1/2 0 0 7 1 4 1 1/2 1/2 0 0 0 0 0 0 0 0 2 1/2 0 0 2 2 2 1 2 2 2 2 1 1/2 2 1 5)检测A的可约性，如果可约则输出可约信息后退出。

- 9 -

6）构造辅助矩阵B

i从1到n循环，j从1 到n循环

bij=aij (i≠j且aij≠0)； bij=mi+1 （i=j，其中mi为A 的第i行0的个数）；bij=0（aij=0） T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 T11 T12 T1 3 T2 1 T3 2 1 3 2 1/2 6 2 1/2 2 1 3 2 2 2 2 3 1/4 1/2 5 1 1 2 2 0 0 7 3 1/2 2 0 0 4 1 2 0 0 7 4 0 0 2 0 2 2 2 2 0 0 0 0 1/2 0 2 1 2 2 1/2 6 1/2 0 T4 1/6 1/2 1/2 3 1/2 1/2 1/5 1/2 1/2 1/2 0 T5 1/2 1 T7 4 T8 2 T10 1 T11 0 T12 0 1 1 2 0 0 1/2 2 5 2 5 0 1/2 0 7 0 0 0 0 0 0 3 T6 1/2 1/2 1/3 2 2 1/2 2 0 1/2 2 0 0 0 0 2 1/4 3 1/7 2 1/7 1 1/2 1 1/2 1 1/4 3 T9 1/5 1/2 1/2 2 0 0 1/2 0 1/2 1/2 1/2 1/2 6 1/2 1/2 2 计算B的主特征根§max主特征向量w1 利用“和法”计算，

（1） 将A的每一列向量归一化得

（2）对

按行求和得

(3)将归一化得

即为近视特征向量，

（4）计算， 作为最大特征根的近似值。

7）按w的各分量由大到小的顺序对参赛各队排名次

- 10 -

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新小学教育数学建模解决有关足球队排名问题 (2)全文阅读和word下载服务。