比赛项目排序的研究

1比赛项目排序的研究（马元陈三磊刘世家）摘要：本论文研究了比赛中经常碰到的问题，即如何合理安排赛程，使得连续参加两项比赛的运动员人数达到最少，达到公平的目的。通过对题目的分析并结合实际，提出合理假设，把参赛表转化为0-1矩阵，运用有关矩阵的知识，结合运筹学中图与网络分析原理，利用Matlab和WinQSB软件分析并计算出结果，最终给出合理的比赛项目顺序，并提出优化的建议和方案。关键词：0-1矩阵WinQSBMatlab图与网络分析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:最优矩阵2i:运动员序号（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,2…n)，即连续参加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从矩阵中可以很清楚地看出任意两个比赛项目连续进行，导致连续参加两个项目的3运动员人数例w12表示若项目一与项目二排在一起，共有两个人连续参加了项目一与项目二，而w11表示项目一与项目一的重复人数，这与本题无关，不予考虑。此时问题演变成如何安排14个项目的顺序，使得连续参加比赛的运动员人数最少。即对矩阵W=[b1,b2,b3,b4,b5,b6,b7,b8,b9,b10,b11,b12,b13,b14]的各列重新排序四、模型的求解（1）“旅行推销商”问题：一个推销商从n个城市v1v2vn中某一个城市出发，到其他n-1个城市推销商品，每个城市都必须访问并只经过一次，最后回到出发点，那么如何安排他的旅行路线使其总距离最短。我们发现，所求的问题与“旅行推销商”问题很相似，我们可以将此W矩阵问题看作为14个城市，现在就是要使连接这14个城市的路线最短，只不过“旅行推销商”问题是一个闭环的回路，项目排序问题是一条直线而已，如果我们运用Hamilton回路解法求出最优解，再在这个闭环回路中找出距离最长（即影响力最大的两个相临项目）的两个项目，从中把它割段，使闭环回路变成一条直线，便可得到我们所要的模型的解了定义：[Hamilton回路]设b1,b2,b3…bn是图G中的n个顶点，若有一条从某一顶点bj(1≤j≤n)出发，经过各节点一次且仅一次，最后返回出发点bj的回路，则称此回路为Hamilton回路。形成的圈称为H圈。（2）Hamilton回路求解原理：1,任取初始H圈：C0=v1,v2…vi,…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,v13,对C重复步骤（2），直到条件不满足为止，最后得到的C即为所求。（3）运用WinQSB软件可以进行对hamilton回路的求解。运行WinQSB软件，调用子程序NetworkModeling,进入主界面后,选择TravelingSalesmenProblem,设置14个项目。采用三种近似方法：最近城市法（NearestNeighborHeuristic），两两交换法（CheapestInsertionHeuristic），逐步包围法（Tow-wayExchangeImprovementHeuristic）求得的最优项目顺序中连续参赛的运动员人数依次为9，6，4，因为前两种方法的连续参赛运动员数目为9和6，大于第三种的4人，所以第三种方法优于前两种，则对于前两种方法不于考虑。采用第三种方法求得的结果如下表：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。按照此种排序，共有三人连续参加了两项比赛。转换为网络图如下所示（粗线处为断开点）：进一步简化图表为：26184113971310121455（4）运用Matlab软件找出连续参加两项比赛的运动员及赛次。首先，建立系数矩阵m=[2,6,1,8,4,9,3,11,7,5,13,10,12,14]。然后，求出最优矩阵，运用Matlab中的排序命令，B=A(：，m)，调整后结果如下所示：010000110001000000100010000101000100000010000010010000011000000010010000100000001000000000000001011000000000001001000100100010010101000100001000010000010000001000000010100000000010100000110100000000001001000001000000101000011010000000000000000000010001000000010000100001010000000010000010000000010000000010000000000001000110001000010100010100000000101000000000100000100000100000010010000000000001000010000100000100001000001010000000010000000001001000100100000000100100010001000010000000100100000100010000000100100000101010100000001060000101000110000100010010100图中方框即表示连续参加两项比赛的项目和人次。从表中可以看出，已经使连续参加两项比赛的运动员人次达到了最少。且只有第一名运动员连续参加了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.6[2]张照贵西南财经大学出版社2006.9[3]黄桐城上海人民出版社2004.4[4]胡守信李柏年科学出版社2004.6附录一：项目运动员12345678910111213141####2###3###74###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##833##34####35###36##37###38####39####40####附录二：011000001000100000000100110001010000010000001000010001000000000000101100001100000000000000000001100000000001000101010000011000110100100000000101000000001100000001010000000010000100010011000100000000100001000100000000001011000000010000000100000010000100001000000100001001000000000000000000100001010010000000000000001000010000000011000011110000000100000000100000000100000100001000010000010000001000000000110090001100000000000000101000100000000100100000001010000000010100000000011000011000001000