循环比赛名次R

实验报告

实验课名称： 数学模型 指导教师： 朱

学生姓名： 年级专业： 应用统计学 学号： 2

实验名称： 循环比赛的名次 实验日期： 年 10 月 9 日 实验成绩： 实验1. 熟悉图论模型的建模方法。 目2. 熟悉掌握用matlab处理图论模型中的相关计算。 的 1

一.问题重述 若干支足球队参加单循环比赛，各队两两交锋，假设每场比赛只计胜负，不计比分，且不允许平局。在循环赛结束后怎样根据他们的比赛结果排列名次呢。我们的目标就是针对这种不规则的比赛数据提出一种算法，尽可能合理地反映各队真实水平。 二．问题分析 实有六支球队进行比赛，其中1队战胜2，3，4，5，6队，而验输给了3队；5队战胜3，6队，而输给1，2，4队。 内现用图的顶点表示球队，而用连接两个顶点的，以箭头标明容 方向的边表示两支球队的比赛结果。 根据比赛结果排名次的一个办法是在图中顺箭头方向寻找一条通过全部6个顶点的路径，如3 1 2 4 5 6 这表示3队胜1队，1队胜2队，…，于是3队为冠军，1队为亚军等等。但是还可以找出其他路径，如1 4 6 3 2 5，决定谁是冠军。 排名次的另一个办法是计算得分，即每支球队获胜的场次。上例中1队胜4场，2，3队各胜3场，4，5队各胜2场，6队胜1场。由此虽可决定1队为冠军，但2，3队之间与4，5队之间无法决出高低。 2

5 6 1 2 3 4 实 验 内 容 三.模型假设 1. 比赛是确定型的，或者每个队方差均为0，抽样结果就是均值； 2. 比赛的结果是可以精确反映相对实力的，没有误差； 3. 比赛的场次是完全的，任意两个队之间都有比赛成绩。 ‘ 3

四.符号说明 Pij A aij S n 第i支球队胜第j支球队的概率 邻接矩阵 表示第i支球队与第j支球队的能力 顶点的得分 表示n支球队 五.模型建立和解决 设n支球队或队员比赛，第i支球队与第j支球队由比赛表现的能力为：aij= pij aji=1-pij (i=1,2,…n j=1,2,…n) 其中pij 表示第i支球队胜第j支球队的概率。 且设 aij=0，则第i支球队胜其余n-1支球队的能力表示为： Si=aij (i=1,2,3…n) j1n则各球队的排名根据{sij}的大小进行。 𝒂𝒊𝒋={𝟏，存在从顶点𝐢到𝐣的有向边 （1） 𝟎，否则D对于开始提出的6支球队循环比赛的结果，不难看出这个竞赛图是双向连通的。写出其邻接矩阵 4

1 0 1 1 10 0 0 0 1 1 11 1 0 1 0 0A1 10 0 0 0 0 0 1 0 0 11 0 0 00 0 （2） 若记顶点的得分向量为s=(𝒔𝟏,𝒔𝟐,...,𝒔𝒏)𝑻，其中𝒔𝒊是顶点i的得分，则由（1）不难知道 S=A1，1=(1,1,…,1)𝑻， （3） 由（2），（3）式容易算出s=（4，3，3，2，2，1)𝑻 记s=𝒔(𝟏),称为一级得分向量，进一步计算， 𝒔(𝟐)=A𝒔(𝟐) (4) 称为2级得分向量，每支球队（顶点）的2级得分是他战胜的各个球队的（1级）得分之和，与1级得分相比，2级得分更有理由作为排名次的依据。继续这个程序，得到k级得分向量。 𝒔(𝟑)=A𝒔(𝒌−𝟏)=𝑨𝒌1，k=1,2,…(5) 𝒔(𝟏)=（4，3，3，2，2，1)𝑻，𝒔(𝟐)=(𝟖，𝟓，𝟗，𝟑，𝟒，𝟑)𝑻 𝒔(𝟑)=(15,10,16,7,12,9)𝑻,𝒔(𝟒)=(38, 28,32,21,25,16)𝑻 K越大，用𝒔(𝒌)作为排名次的依据越合理，如果k→∞时，𝒔(𝒌)收敛于某个极限得分向量，那么就可以用这个向量作为排名次的依据。再利用Perron-Frobenius定理，素阵A的最大特征根为正5

单根𝛌，𝛌对应正特征向量s,且有𝐥𝐢𝐦𝑨𝒌𝒌→∞𝝀𝒌=s(6) 进一步算出A的最大特征值根𝛌=2.232和特征向量s=(0.238,0.1,0.231,0.113,0.150,0.104)𝑻,从而排出名次为{𝟏,𝟑,𝟐,𝟓,𝟒,𝟔}. 六、模型优缺点以及改进 优点： 该方案简单易行,原理清晰,依据可靠,论证有力,结论最优。并将现实中的问题用简单的线性规划问题进行分析计算，结构简单，计算方便。 缺点： 该模型在处理此问题时有假设与理想化的思想，与实际问题的求解还有一定的距离。 6

7

通过此次建模，令我们有了一次正式的亲自动手的机会。有利于激发我们学习数学的兴趣，丰富我们数学探索的情感体验；有利心于我们自觉检验，巩固所学的数学知识，促进对所学知识的吸收。得本次实验让我们收获颇丰。，也使我们深刻认识到我们还存在着体很多不足之处。比如分工不明确，在细节问题上粗心大意，小组会 间沟通不及时等等。但是有了这次的教训，在以后的建模活动中，相信我们一定会将现在发现的问题一点点克服。 教师评语

8