排名决策数学模型解答（页）.doc

河南理工大学公选课《数学建模》课程论文姓 名论文题目排名决策学 号学院、专业论文分数教师填写：排名决策摘要本文利用得分向量法建立数学模型解决了一个为足球对排名次的问题.首先画出球 队比赛的胜负关系图，（1）看是否存在唯一的完全路径，若存在唯一的完全路径，则有 完全路径确定的定点顺序与得分多少排列的顺序完全一致2）若不存在唯一完全路径, 则按照得分向量法，求出邻接矩阵的特征根，及特征向量作为得分向量的极限即得分向 量的极限，來求解排名次序文中还写出了得分向量求解的算法，考虑了排名是否公平 的问题等该模型是稳定的，而且非常简单，容易理解，求解过程方便，易于验证本模型比较完满地解决了足球队排名次问题，简单、易行、计算方便，直接用程序 实现，可扩展性强，而且经过简单修改,它还可以适用其它的对抗型比赛的排名竞赛图、双相连通图、矩阵乘法算法、Perron-Frobenius定理、得分向量问题描述有七个足球队参加的循环赛，每次比赛不允许平局，只计胜负，胜负情况如卜•表, 请给出七个队好的排名方式ABCD E F GA胜胜B胜C胜胜胜D胜胜胜E胜胜 胜F胜G胜胜胜胜胜胜胜胜问题分析本题是排名问题的求解故口J用竞赛图的方式來表示七个队伍方分别用七个顶点表 示，胜负关系则用有向边表示如图所示：AD E从图中可以看岀不存在唯一完全路径，但是该竞赛图是双向连通图，所以可建立邻 接矩阵，利用得分向量法来求解。

最后得出公平的排名为{D, F, C, A, B, G, E}模型假设(1) 足球队之间进行单循坏比赛(2) 各球队Z间两两交锋(3) 每场比赛只计胜负，不及比分(4) 不允许平局模型建立(1)本题中七个组球队的循环比赛中没有平局，所以假设胜一局得1分，负一局得0分,由此建立邻接矩阵001100110101000001110M =0100111100000111001010110000來表示各个队伍之间比赛的胜负情况建立得分向量来表示各个队伍的总得分情况，S =(S】,S2，・・・，S7)t (2)则由(1)不难知道s⑴二A 1, 1= (1, 1,…，1) T (3)1级向量表示的是各个队伍的总得分情况因为比赛过程中存在总得分相同的队伍，所以1级的得分向量无法排出全部的名次, 所以需要进一步计算高级的得分向量s⑵二A s⑴ (4)称为2级得分向量，2级得分向量表示每支球队所战胜的各个球队的得分之和，与1级 向量相比，2级得分向量更有理由作为排名的依据继续这个程序得到k级得分向量s(k)二人 二八,k二 1,2,・・・ (5)k越大，用s00作为排名的依据越合理，如果k->8时s00收敛于某个极限得分向量，那 么就可以用这个极限得分向量作为排名的依据。

因为对于n^4个顶点的双向竞赛连通图，存在正整数r,使得邻接矩阵A满足A*>0.这样的A称为素阵再利用著名的Perron-Frobenius定理，索阵A的最大特征根为正单根入,入对应正 特征向量s,且有lim28Akl(6)与（5）式比较可知k级得分向量s, k->->时将趋向于A的对应于最大特征根的特征 向量s, s就是作为排名依据的得分向量模型求解 由程序求得得分向量如下：s ⑴二(3, 3, 3, 4, 2, 4, 2)1S⑵二(9, & 10, 11,5, 10, 6) TS⑶二(27, 24, 26, 29, 15, 2& 18)TS⑷二(73, 68, 72, 85, 45, 84, 50)1S⑸二(207, 190, 214, 247, 123, 236, 140) T S⑹=(601, 544, 606, 689, 347, 660, 404)T 进一步算出邻接矩阵的特征根为X =1最后得出公平的排名为{D, F, C, A, B, G, E} o结果表示由模型求解过程得岀最终答案，公平的排名为:{D, F, C, A, B, G, E}模型评价该模型简单易行，操作简单，计算方便而且也很好的解决了排名决策问题，运行稳 定，应该算是一个成功的模型。

参考文献[1] 姜启源，谢金星，叶俊，《数学模型》（第三版），北京：高等教育岀版社，2003. 8[2] 袁震东，数学建模方法，一上海：华东师范大学出版社，2003. 1[3] 同济大学应用数学系，《线性代数》（第四版），高等教育出版社，2003. 7[4] 谭永基等，《数学模型》复旦大学岀版社，2005.2附录求得分向量的程序代码(C++实现)#includeitincludcusing namespeice std;void dfxl (int a[7] [7], int n) : // n 级得分向量int main(){while (1){int a[7] [7]二{0,0, 1, 1,0,0, 1,1,0, 1,0, 1,0, 0,0, 0, 0, 1, 1, 1,0,0, 1,0, 0, 1, 1, 1,1,0, 0, 0, 0, 0, 1,1, 1,0, 0, 1,0, 1,0, 1, 1,0, 0, 0, 0};int n;cout，z请输入级数n:cin>>n;dfxl (a, n);cout<