比赛项目排序的研究.doc

比赛项目排序的研究（马元 陈三磊 刘世家）摘 要：本论文研究了比赛中经常碰到的问题，即如何合理安排赛程，使得连续参加两项比赛的运动员人数达到最少，达到公平的目的。通过对题目的分析并结合实际，提出合理假设，把参赛表转化为0-1矩阵，运用有关矩阵的知识，结合运筹学中图与网络分析原理，利用Matlab和WinQSB软件分析并计算出结果，最终给出合理的比赛项目顺序，并提出优化的建议和方案。关键词： 0-1矩阵 WinQSB Matlab 图与网络分析 Hanmilton回路一、问题的提出在各种运动比赛中，为了使比赛公平、公正、合理的举行，一个基本要求是：在比赛项目排序过程中，尽可能使每个运动员不连续参加两项比赛，以便运动员恢复体力，发挥正常水平。1表1是某个小型运动会的比赛报名表。有14个比赛项目，40名运动员参加比赛。表中第1行表示14个比赛项目，第1列表示40名运动员，表中“”号位置表示运动员参加此项比赛。建立此问题的数学模型，并且合理安排比赛项目顺序，使连续参加两项比赛的运动员人次尽可能的少；2说明上述算法的合理性；3对“问题2”的比赛排序结果，给出解决“运动员连续参加比赛”问题的建议及方案。二、问题的分析思路1：把表1看成是一个40*14的0-1矩阵，0表示运动员没有参加了这个项目，1表示参加，设此0-1矩阵为矩阵A，那么问题中安排合理的比赛顺序用数学语言表示为调整A的列向量使之成为矩阵B，若B满足一定的条件后，会使B中行向量连续出现1的次数最少，那么B就是最终要排出的比赛项目矩阵。在这个过程中，我们使用了Hanmilton回路、Matlab 、WinQSB软件等来求解B。三 、模型的建立 1 模型假设：（1）每个运动员都能按时参加比赛；（2）天气情况良好，不出现因天气原因中断比赛项目；（3）单纯比赛项目的早与迟不影响运动员的技能发挥；（4）两项比赛不会同时进行；（5）运动员在一夜休息后，体力可以得到充分恢复；（6）比赛中不考虑个人因素（如裁判不公等）影响比赛的公平性。2 符号说明 A:初始矩阵 B:最优矩阵 i :运动员序号 （i=1,2,m） j: 项目序号 (j=1,2,n) bj:第j个项目 (j=1,2,n) pi:初始矩阵A的列向量 xij:第i个运动员参加的第j项项目，xij=1表示参加，xij=0表示不参加。 wrs:第r项比赛项目对第s项的影响度(r,s=1,2n)，即连续参加r项目和s项目的运动员人数。W：表示影响力矩阵，即任意两个项目连续进行，导致连续参加两个比赛项目的运动员人数的组合而形成的14*14矩阵,wrs为W矩阵的元素 3 模型的建立:（1）把附录一变换为0-1矩阵A，如图附录二所示。然后运用Matlab软件求出A矩阵的列矩阵AT（2）求出影响力矩阵W 由符号说明，可知wrs=xr1* xs1+ xr2* xs2+ + xrm* xsm 由矩阵相关知识知W= AT *A,运用Matlab软件求得W矩阵如下b1b2b3b4b5b6b7b8b9b10b11b12b13b14b162120010121111b228141011131021b311610003110221b424191121021011b501017201110112b600012812111212b711020171110221b8013112110121422b911101111611131b10231211121101003b1111010101116311b12102012241031010b1312211122301184b14111122121310410从矩阵中可以很清楚地看出任意两个比赛项目连续进行，导致连续参加两个项目的运动员人数例w12表示若项目一与项目二排在一起，共有两个人连续参加了项目一与项目二，而w11表示项目一与项目一的重复人数，这与本题无关，不予考虑。此时问题演变成如何安排14个项目的顺序，使得连续参加比赛的运动员人数最少。即对矩阵W=b1,b2,b3,b4,b5,b6,b7,b8,b9,b10,b11,b12,b13,b14的各列重新排序四、模型的求解（1）“旅行推销商”问题：一个推销商从n个城市v1 v2 vn中某一个城市出发，到其他n-1个城市推销商品，每个城市都必须访问并只经过一次，最后回到出发点，那么如何安排他的旅行路线使其总距离最短。 我们发现，所求的问题与“旅行推销商”问题很相似，我们可以将此W矩阵问题看作为14个城市，现在就是要使连接这14个城市的路线最短，只不过“旅行推销商”问题是一个闭环的回路，项目排序问题是一条直线而已，如果我们运用Hamilton回路解法求出最优解，再在这个闭环回路中找出距离最长（即影响力最大的两个相临项目）的两个项目，从中把它割段，使闭环回路变成一条直线，便可得到我们所要的模型的解了 定义：Hamilton回路设b1, b2, b3bn是图G中的n个顶点，若有一条从某一顶点bj(1jn)出发，经过各节点一次且仅一次，最后返回出发点bj的回路，则称此回路为Hamilton回路。形成的圈称为H圈。（2）Hamilton回路求解原理：1,任取初始H圈：C0=v1 ,v2vi,vj,vn, v12,对所有的i,j,1i+1jn,若w(vi,vj)+w(vi+1,vj+1) w(vi,vi+1)+w(vj, vj+1) 则在C0删去边(vi,vi+1)和(vj, vj+1)而加入边(vi,vj)和(vi+1,vj+1)，形成新的H圈C，即： C=v1,v2,vi ,vj ,vj-1 ,vi+1 ,vj+1 ,vn ,v 1 3,对C重复步骤（2），直到条件不满足为止，最后得到的C即为所求。 （3）运用WinQSB软件可以进行对hamilton回路的求解。运行WinQSB软件，调用子程序Network Modeling,进入主界面后,选择Traveling Salesmen Problem,设置14个项目。采用三种近似方法：最近城市法（Nearest Neighbor Heuristic），两两交换法（Cheapest Insertion Heuristic），逐步包围法（Tow-way Exchange Improvement Heuristic）求得的最优项目顺序中连续参赛的运动员人数依次为9，6，4，因为前两种方法的连续参赛运动员数目为9和6，大于第三种的4人，所以第三种方法优于前两种，则对于前两种方法不于考虑。采用第三种方法求得的结果如下表：从表中看出,从b14到b2，b8到b4,b9到b3,b5到b13，都有一人连续参加两项比赛。所以断点处可以为四处任意一点，假设在b14到b2处断开，则比赛项目排序为b2,b6,b1,b8,b4,b9,b3,b11,b7,b5,b13,b10,b12,b14。按照此种排序，共有三人连续参加了两项比赛。转换为网络图如下所示（粗线处为断开点）：48162进一步简化图表为：71139141210135（4）运用Matlab软件找出连续参加两项比赛的运动员及赛次。首先，建立系数矩阵m=2,6,1,8,4,9,3,11,7,5,13,10,12,14。然后，求出最优矩阵，运用Matlab中的排序命令，B=A(：，m)，调整后结果如下所示：0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 1 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 0 图中方框即表示连续参加两项比赛的项目和人次。从表中可以看出，已经使连续参加两项比赛的运动员人次达到了最少。且只有第一名运动员连续参加了b3和b11两个比赛项目，第14名运动员连续参加了b4和b9两个比赛项目，第39名运动员连续参加了b5和b13两个比赛项目，其它的运动员都不存在比赛的连续性了。五、综合评价本文通过利用数学工具，严格对模型进行求解，具有科学性，而且简单易行。适用范围比较宽，并且要求有一定的软件操作能力。六、建议及方案1、对于有运动员连续参加的两项比赛，尽量不要在同一天进行。由于全部运动员都不连续参加两项比赛的可能性很小，如果运动员连续参加的两项比赛分别在两天中进行，那么运动员就有时间来恢复体力。故可以将两个连续的项目安排在不同的两天，倘若安排合理的话，运动员连续参加两项比赛的人次可近似地降为零。对本比赛而言，假设所有比赛项目要在四天内完成，那么可以将比赛日程安排如下：第一天：b2,b6,b1,b8第二天：b4,b9,b3第三天：b11,b7,b5,b13第四天：b10,b12,b14如果按照此比赛日程进行，最终只有14号运动员连续参加了b4和b9两个比赛项目。2、对项目的加权由于考虑到运动项目消耗体力的程度不同，故可以给运动项目加权。如果运动员连续参加比赛不可避免的话，则应该安排那些权重小的项目连续。如果两个项目的权重都很大，为追求冲突最少，就应该考虑将这两个项目分开。如果两个连续项目的权重一大一小，则应该将权重小的项目放在前面，权重大的项目放在后面。这样会更加合理，更符合实际，更加公平。参考文献： 1 赵静 但琦 高等教育出版社 2003.62 张照贵 西南财经大学出版社 2006.93 黄桐城 上海人民出版社 2004.44 胡守信 李柏年 科学出版社 2004.6附录一：项目运动员12345678910111213141#2#3#4#5#6#7#8#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#附录二：011000001000100000000100110001010000010000001000010001000000000000101100001100000000000000000001100000000001000101010000011000110100100000000101000000001100000001010000000010000100010011000100000000100001000100000000001011000000010000000100000010000100001000000100001001000000000000000