《电工赛论文-比赛项目的排序.doc》由会员分享，可在线阅读，更多相关《电工赛论文-比赛项目的排序.doc（37页珍藏版）》请在三一文库上搜索。
1、比赛项目的排序摘要本文针对运动会中合理安排比赛项目顺序的问题，引入了图论中的一些分析方法和最短路算法，将它们与matlab编程、C语言编程实现有机地结合起来，全面考虑了运动会的比赛报名情况，重点考察了任意两个比赛项目报名的相关性，在此基础上建立了赋权图模型，其合理性和实用性都很好。模型求解的结果达到了“使连续参加两项比赛的运动员人次尽可能的少”的目的。针对问题一和问题二，我们从运动会的比赛报名表出发，以“使连续参加两项比赛的运动员人次尽可能的少”为目标建立模型。我们先利用matlab程序求出了比赛报名相关性矩阵F，再利用图论理论对比赛报名相关性矩阵F进行分析，建立了赋权图模型，将求解“使连续参
2、加两项比赛的运动员人次尽可能的少”的问题转化为求解图中一条经过所有点的最短路径的问题。在求解模型时，我们采用了Dijkstra方法的思想，采用了C语言编程处理的方法，实现了最短路算法。对于小型运动会，我们得到了使连续参加两项比赛的运动员总人次m=2、不合理度b1.8%的比赛项目排序；对于大型运动会，我们得到了使连续参加两项比赛的运动员总人次m=8、不合理度b0.22%的比赛项目排序。我们在建立和求解模型的过程中，所用到的知识并不复杂，计算量也不是很大，结果准确可靠，具有实际指导意义。针对问题三，我们首先从理论上证明Dijkstra方法是合理可行的。通过比较Dijkstra方法与全排列算法（穷举
3、法），我们发现Dijkstra方法比全排列算法具有更大的优越性，更适合于题中模型的求解。我们对计算结果进行了全面的分析，并编写了matlab程序对结果进行测试，说明了计算的结果是正确的，算法是合理的。针对问题四，我们分析了运动会中的比赛间隔时间，并提出了利用合理设计的比赛间隔时间，来解决“运动员连续参加比赛”问题的建议及方案。关键词：相关性矩阵 图论 赋权图 最短路算法 Dijkstra方法 matlab编程 C语言编程371问题的提出1.1基本情况全民健身计划是1995年在国务院领导下，由国家体委会同有关部门、各群众组织和社会团体共同推行的一项依托社会、全民参与的体育健身计划，是与实现社会主
4、义现代化目标相配套的社会系统工程和跨世纪的发展战略规划。现在，以全民健身为主要内容的群众性体育活动蓬勃开展，举国上下形成了全民健身的热潮，人民群众健康水平不断提高，同时也扩大了竞技体育的社会影响，提高了竞技体育水平。现在各级、各类、各种运动比赛比比皆是，这不但提高了全民的身体素质，而且使一批运动员脱颖而出，成为运动健将，为国家争得了荣誉。1.2相关信息在各种运动比赛中，为了使比赛公平、公正、合理的举行，一个基本要求是：在比赛项目排序过程中，尽可能使每个运动员不连续参加两项比赛，以便运动员恢复体力，发挥正常水平。1.3需要解决的问题1表1是某个小型运动会的比赛报名表。有14个比赛项目，40名运动
5、员参加比赛。表中第1行表示14个比赛项目，第1列表示40名运动员，表中“”号位置表示运动员参加此项比赛。建立此问题的数学模型，并且合理安排比赛项目顺序，使连续参加两项比赛的运动员人次尽可能的少；2文件“运动员报名表”（见附件）中给出了某个运动比赛的报名情况。共有61个比赛项目，1050人参加比赛。请给出算法及其框图，同时给出合理的比赛项目排序表，使连续参加两项比赛的运动员人次尽可能的少；3说明上述算法的合理性；4对“问题2”的比赛排序结果，给出解决“运动员连续参加比赛”问题的建议及方案。表1 某小型运动会的比赛报名表项目运动员12345678910111213141#2#3#4#5#6#7#8
6、#9#10#11#12#13#14#15#16#17#18#19#20#21#22#23#24#25#26#27#28# 29#30 #31#32#33#34#35#36#37#38#39#40#2.问题的分析全民健身计划是1995年在国务院领导下，由国家体委会同有关部门、各群众组织和社会团体共同推行的一项依托社会、全民参与的体育健身计划，是与实现社会主义现代化目标相配套的社会系统工程和跨世纪的发展战略规划。体育比赛是全民健身计划中不可或缺的重要组成部分。为了科学地举办体育比赛，使比赛公平、公正、合理的进行，我们要合理安排比赛项目顺序，使连续参加两项比赛的运动员人次尽可能的少。本题目要求我们根
7、据运动会的比赛报名表，建立比赛项目合理排序问题的数学模型，并给出合理的比赛项目排序表，使连续参加两项比赛的运动员人次尽可能的少。同时，题目要求我们根据比赛排序结果，给出解决“运动员连续参加比赛”问题的建议及方案。为使我们的模型尽可能地贴近现实，具有实用性和建设性，我们首先正确统计出任意两个比赛项目的相关性，即任意两项比赛同时举行时，连续参加这两项比赛的运动员人次，再对比赛项目的相关性进行分析，给出合理的比赛项目排序表。合理的假设也是本题的关键，它保证了我们建立的数学模型是现实可行的。同时，为了便于分析和计算，我们还引入了图论中的一些概念和分析方法，为我们构建和完善数学模型起到了重要的作用。3.
8、图论中一些概念的引入3.1图论的基本概念 图论是利用图来进行分析的运筹学分支，它广泛地应用在物理学、化学、控制论、信息论、科学管理、电子计算机等各个领域。在实际生活中，有很多问题可以用图论的理论和方法来解决。将庞大复杂的工程系统和管理问题用图描述，可以解决很多工程设计和管理决策的最优化问题。3.2图论的几个名词定义边 图中两点之间不带箭头的联线称为边。弧 图中两点之间带箭头的联线称为弧。无向图 由点和边所构成的图称为无向图。有向图 由点和弧所构成的图称为有向图。赋权图 给图,对中的每一条边，相应地有一个数，则称这样的图 为赋权图，称为边上的权。3.3最短路问题的基本概念给定一个赋权有向图，即给
9、了一个有向图,对每一个弧，相应地有权，又给定中的两个顶点，设是中从到的一条路，定义路的权是中所有弧的权之和，记为，最短路问题就是要在所有从到的路中，求一条权最小的路，即求一条从到的路，使 式中对中所有从到的路取最小，称是从到的最短路，路的权称为从到的距离，记为。3.4最短路算法重要结论：如果是中从到的最短路，是中的一个点，那么，从沿到的路是从到的最短路。Dijkstra方法：当所有的时，目前公认最好的方法是Dijkstra方法。Dijkstra方法的基本思想是从出发，逐步地向外探寻最短路。执行过程中，与每个点对应，记录下一个数（称为这个点的标号），它或者表示从到该点的最短路的权（称为标号）、或
10、者是从到该点的最短路的权的上界(称为标号)，方法的每一步是去修改标号，并且把某一个具标号的点改变为具标号的点，从而使中具标号的顶点数多一个，这样，至多经过步，就可以求出从到各点的最短路。4.模型假设与约定4.1总体假设运动员报名表等现有数据真实可信。4.2具体假设与约定1.假设同一时间只进行一项比赛，任意两项比赛进行的时间不会发生重叠。2.假设比赛间隔时间可视为相等的一段较小时间，相对于比赛进行时间可忽略，在建立模型时可以不用考虑。3.假设运动员报名了就会参加比赛，即运动员不会放弃比赛。4.假设比赛项目不会取消，也不会更改，即比赛项目是确定的。5.模型建立与求解5.1问题一5.1.1 对数据的
11、分析通过对小型运动会比赛报名表的数据分析，我们得到小型运动会各项目报名人数的统计信息如表2所示：表2 小型运动会各项目报名人数的统计信息项目1234567891011121314报名总人数686978710610610810总计有111人次报名参加了比赛。5.1.2 参数的定义D：报名数据矩阵D(i,j)=1，表示第i位运动员报名参加了第j项比赛；D(i,j)=0，表示第i位运动员未报名参加第j项比赛；F：比赛报名相关性矩阵 F(i,j)表示第i个项目与第j个项目连续举行时，有F(i,j)人次连续参加这两项比赛。X：比赛项目排列次序矩阵N：比赛次序相关性矩阵N( i )表示连续参加X( i )
12、与X(i+1)两项比赛的运动员人次m：一次运动会中，连续参加两项比赛的运动员总人次S：实际参赛数据矩阵S(i,j)=1，表示第i位运动员实际参加了次序为j的比赛；S(i,j)=0，表示第i位运动员未实际参加次序为j的比赛；b：不合理度，定义为： 5.1.3 比赛报名相关性的求解根据定义，比赛报名相关性矩阵F的任一元素Fij表示第i个项目与第j个项目连续举行时，有Fij 人次连续参加这两项比赛。利用比赛报名相关性矩阵F与报名数据矩阵D的关系，编写matlab程序1求解比赛报名相关性矩阵F（源程序见附件一）。程序流程图如图1所示：运行程序，得到小型运动会各比赛项目之间的报名相关性如表3所示：表3
13、小型运动会各比赛项目之间的报名相关性 项目相关值 F(i,j)项目1234567891011121314162120010121111228141011131021311610003110221424191121021011501017201110112600012812111212711020171110221801311211012142291110111161113110231211121101003111101010111631112102012241031010131221112230118414111122121310410图1 求解小型运动会比赛报名相关性矩阵F的matlab程序
14、流程图5.1.4 模型的建立我们使用图论的方法，对“合理安排比赛项目排序”的问题进行研究。首先，我们对图论中参数所代表的意义作如下定义2：点：点表示第i个项目边：每一条边表示第i个项目和第j个项目连续举行。权：每一条边上的权表示第i个项目与第j个项目连续举行时，有人次连续参加这两项比赛，即F(i,j)通过对图论中参数所代表的意义进行定义，我们可以建立一个赋权图模型，图中总共有14个点，182条边。点分别代表第1个项目第14个项目，每一条边表示第i个项目和第j个项目连续举行，每一条边上的权表示第i个项目与第j个项目连续举行时，有人次连续参加这两项比赛，即F(i,j)。通过对小型运动会各比赛项目之
15、间的报名相关性矩阵F进行分析，我们可以得到赋权图中每一条边上的权值如表4所示：表4 小型运动会赋权图模型中每一条边上的权值 12345678910111213141/212001012111122/141011131021311/100031102214241/112102101150101/201110112600012/121112127110201/111022180131121/121422911101111/1113110231211121/1003111101010111/3111210201224103/1013122111223011/4141111221213104/(当i=
16、j时，无意义)设图T=(V,E)是图G=(V,E)支撑子图，如果T=(V,E)是一个树的话，则称T=(V,E)是G的一个支撑树。(T)是所有权之和。我们需要找到T*使得(T*)是G 的所有支撑树中权最小者，即： 综上所述，我们建立模型如下：其中：Z为目标函数值，即图中一条经过14个点的最短路径D为报名数据矩阵D(i,j)=1，表示第i位运动员报名参加了第j项比赛；D(i,j)=0，表示第i位运动员未报名参加第j项比赛；F为比赛报名相关性矩阵 F(i,j)表示第i个项目与第j个项目连续举行时，有F(i,j)人次连续参加这两项比赛。为赋权图上的点，表示第i个项目为赋权图上的一条边，表示第i个项目和
17、第j个项目连续举行为边上的权，表示第i个项目与第j个项目连续举行时，有人次连续参加这两项比赛5.1.5 模型的求解对于我们所建立的赋权图模型，“使连续参加两项比赛的运动员人次尽可能的少”即在图中求出一条经过14个点的最短路径。对于最短路算法，当所有的时，目前公认最好的方法是Dijkstra方法。Dijkstra方法的基本思想是从出发，逐步地向外探寻最短路。执行过程中，与每个点对应，记录下一个数（称为这个点的标号），它或者表示从到该点的最短路的权（称为标号）、或者是从到该点的最短路的权的上界(称为标号)，方法的每一步是去修改标号，并且把某一个具标号的点改变为具标号的点，从而使中具标号的顶点数多一
18、个，这样，至多经过步，就可以求出从到各点的最短路。我们利用Dijkstra方法的思想，采用了如下的算法:为了减少计算量，提高计算速度。我们利用已经计算出来的小型运动会比赛报名相关性矩阵F来进行计算。矩阵F为一14阶方阵, 其中每一元素F(i,j),代表权值 。先取第一列，将其数据划去，代表最先进行第一项比赛，在第一行内找出最小值（表示下一个将进行与第一项比赛相关性最小的比赛），记录下最小值，假设它在第K列，则划去第K列的数据，表示第K项比赛在是在第二位次进行。若遇到第一行内有多个相同的最小值，即有多个项目与第一个项目的权值相同，设这几个值分别在第K1，K2，K3.列，.则依次考虑K1，K2，K
19、3.行，比较这几行的最小值的大小（划去的数据不予考虑），假设其中的最小值在第Ki行，记录下最小值，划去第Ki列的数据，也就表示第Ki项比赛在第二位次进行。同时这样做就保证了第三位次的比赛与第二位次的比赛的权值是最小的。（若K1，K2，K3.行依然有若干行有相同的最小值，并且又都是最小的，则取这若干行中行号最小的行。）在对第二位次以及以后的比赛都重复以上过程，直到第N-1项。将每次记录下的最小值相加，就得到了以第一项比赛为第一位次时的权值总和的最小值，同时也得到了一个比赛次序。在依次将第二项，第三项比赛做为第一位次的比赛，重复以上的过程，记录下每次的最小权值总和和它对应的比赛排序。再比较这些最小
20、权值总和，找出其中最小的。至此我们就认为，该最小值就是我们所要求的解，它会使最少人次连续两次参加比赛，它对应的比赛顺序即是合理的比赛项目排序。我们使用C语言编程实现最短路算法（源程序见附件一）程序流程图如图2所示：图2 小型运动会最短路算法C语言实现程序流程图运行程序，得到合理的比赛项目排序如表5所示表5 小型运动会合理的比赛项目排序次序1234567891011121314项目1310941412263711518运行程序，同时得到：连续参加两项比赛的运动员总人次m=2由于比赛项目排列次序矩阵X的方向不影响连续参加两项比赛的运动员总人次m，所以合理的比赛项目排序反向后，依然是另一个合理的比赛
21、项目排序。5.1.6 结果分析由于我们采用了C语言编程处理的方法，实现了最短路算法的Dijkstra方法，有效地减少了计算量，缩短了计算时间，提高了计算精度，保证了计算结果的准确性和很高的计算效率。根据不合理度b的定义对于小型运动会，连续参加两项比赛的运动员总人次m=2，报名参加比赛的运动员总人次111 ，所以：对于小型运动会有：不合理度b1.8%，不合理度很小，说明对于“使连续参加两项比赛的运动员人次尽可能的少”的目标，利用以上模型求得的比赛项目排序已经很合理。比赛项目排列次序矩阵X13 10 9 4 14 12 2 6 3 7 11 5 1 8根据实际参赛数据矩阵S的定义，S(i,j)=1
22、，表示第i位运动员实际参加了次序为j的比赛；S(i,j)=0，表示第i位运动员未实际参加次序为j的比赛；我们根据比赛项目排列次序矩阵X可以得到实际参赛数据矩阵S如表6所示表6 运动员实际参赛情况项目运动员131094141226371151811010001010000020000010000100130101001000000040000010010000151000100000100060000000100010071000010000000080100100000000090101001000100010000100100100101110011010000000120100000000
23、000113010010000001001400010000100001150000010010000116001001000010001700001001000000180000010001000019010000001000002000010000000010210010100000000022000000100001002300000100010000241000100001000125010000100000102600001000000100270000000100100028000000100000012900000100001010300001000000010031000001
24、01000001320100000001000033000100010000003410001000100010350000010100010036000100000100003701100000000010380100100100000139101000000001014010100001010000根据运动员实际参赛情况，我们可以得到运动员连续参加比赛的具体情况如表7所示：表7 小型运动会运动员连续参加比赛的具体情况运动员连续参加的比赛11414371095.1.7 模型分析1.模型评价我们建立模型时，从小型运动会的比赛报名表出发，以“使连续参加两项比赛的运动员人次尽可能的少”为目标建立模
25、型。我们先利用matlab程序求出了比赛报名相关性矩阵F，再利用图论理论对比赛报名相关性矩阵F进行分析，建立了赋权图模型，将求解“使连续参加两项比赛的运动员人次尽可能的少”的问题转化为求解图中一条经过14个点的最短路径的问题。在求解模型时，我们采用了Dijkstra方法的思想，采用C语言编程处理的方法，实现了最短路算法，得到了使连续参加两项比赛的运动员总人次m=2的比赛项目排序。2.模型优缺点分析与改进方向模型的优点1. 根据小型运动会的比赛报名表，我们通过图论方法分析，建立了赋权图模型，更直接地展现了比赛报名表内部各个比赛项目之间的联系，使比赛组织者更加合理的安排比赛项目排序。2. 模型的重
26、点是在于安排比赛项目排序，使连续参加两项比赛的运动员人次尽可能的少，在用matlab对数据矩阵进行处理时，我们先将数据矩阵转换为Excei格式，再利用matlab对Excei格式的数据矩阵进行整体读入，使得我们能整体用到这些数据，保证计算结果的可靠性。3. 求解模型时采用的Dijkstra方法可以很好的解决最短路径的问题，求得的比赛项目排序满足“使连续参加两项比赛的运动员人次尽可能的少”，结果结果准确可靠，具有实际指导意义。模型的缺陷与改进求解模型时采用的Dijkstra方法并不是解决最短路径问题的计算效率最高的算法，当数据量较大时，可采用哈密顿循环断链的方法求哈密顿路径，对模型进行改进。5.
27、2问题二5.2.1 对数据的分析通过对大型运动会运动员报名表的数据分析，我们得到大型运动会各项目报名人数的统计信息如表8所示：表8 大型运动会各项目报名人数的统计信息项目123456789101112131415报名人数685771547072716657676571576856项目161718192021222324252627282930报名人数755163566346615159555256545765项目313233343536373839404142434445报名人数666568604856555158555863615860项目46474849505152535455565758
28、596061报名人数60565361596746516459685170595549总计有3644人次报名参加了运动会比赛5.2.2 参数的定义D：报名数据矩阵D(i,j)=1，表示第i位运动员报名参加了第j项比赛；D(i,j)=0，表示第i位运动员未报名参加第j项比赛；F：比赛报名相关性矩阵 F(i,j)表示第i个项目与第j个项目连续举行时，有F(i,j)人次连续参加这两项比赛。X：比赛项目排列次序矩阵N：比赛次序相关性矩阵N( i )表示连续参加X( i )与X(i+1)两项比赛的运动员人次m：一次运动会中，连续参加两项比赛的运动员总人次S：实际参赛数据矩阵S(i,j)=1，表示第i位运动
29、员实际参加了次序为j的比赛；S(i,j)=0，表示第i位运动员未实际参加次序为j的比赛；b：不合理度，定义为： 5.2.3 比赛报名相关性的求解根据定义，比赛报名相关性矩阵F的任一元素Fij表示第i个项目与第j个项目连续举行时，有Fij 人次连续参加这两项比赛。利用比赛报名相关性矩阵F与报名数据矩阵D的关系，编写matlab程序求解比赛报名相关性矩阵F（源程序见附件二）。程序流程图如图3所示：图3 求解大型运动会比赛报名相关性矩阵F的matlab程序流程图运行程序，得到大型运动会各比赛项目之间的报名相关性如表9所示(完整的结果见附件四)：表9 大型运动会各比赛项目之间的报名相关性 项目相关值
30、F(i,j)项目12345675657585960611682264136614222257531335452303257123319443214632543146424415413370432156426133147283171537331438714243245665962346842301576444112451230258154257422702205942346133325953602324452002555361201123412033495.2.4 模型的建立我们使用图论的方法，对“合理安排比赛项目排序”的问题进行研究。首先，我们对图论中参数所代表的意义作如下定义：点：点表示第i
31、个项目边：每一条边表示第i个项目和第j个项目连续举行。权：每一条边上的权表示第i个项目与第j个项目连续举行时，有人次连续参加这两项比赛，即F(i,j)通过对图论中参数所代表的意义进行定义，我们可以建立一个赋权图模型，图中总共有61个点，3660条边。点分别代表第1个项目第61个项目，每一条边表示第i个项目和第j个项目连续举行，每一条边上的权表示第i个项目与第j个项目连续举行时，有人次连续参加这两项比赛，即F(i,j)。通过对大型运动会各比赛项目之间的报名相关性矩阵F进行分析，我们可以得到赋权图中每一条边上的权值如表10所示(完整的结果见附件四)：表10 大型运动会赋权图模型中每一条边上的权值 12345675657585960611/22641366142222/53133545230325/23319443214632/31464244154133/43215642613314/83171537331438/424324566596234/423015764441124/230258154257422/220594234613332/536023244520025/361201123412033/(当i=j时，无意义)设图T=(V,E)是图G=(V,E)支撑子图，如果T=(V,E)是一个树的话，则称T=(V,E)是G的一个支撑树。(T)是所有权之和。