数模——基于排列组合的赛事安排问题

目录一、问题重述1二、问题分析22.1问题一的分析22.2问题二的分析22.3问题三的分析2三、基本假设2四、基本符号说明2五、“合理赛程”的标准制定3六、关于赛程安排简化模型36.1模型的建立与求解36.2结果分析66.3改进方向与评估7七、对于简化模型进行优化77.1模型建立与求解77.2结果分析97.3改进方向及评估9八、结论10九、其他“合理性标准”的参考意见10十、参考文献10十一、附录1111.1模型一源码1111.2模型二源码1418基于排列组合的赛事安排问题【摘要】由于赛事安排需要考虑因素颇多，同时对于不同具体的项目有不同的安排，而本次题目所给报名表并没有列出具体项目，所以为了模型的建立，本次建模决定加入部分假设，忽略部分因素，以达到简化模型的目的。对于第一个简化模型的建立，我是以所有运动员的休息时间的总时间为标准进行比较，具体算法是将所得的14个项目以不同的顺序排列组合，分别算出每一种情况的总时间，时间与时间之间相互比较，从而得到最大值，而此时最大值所存在的赛程安排即为我的标准中的“最合理”赛程安排。但由于14种情况的排列组合过多，等到遍历完所有情况花费的时间也过多。所以我将第一个模型优化，精简了项目的个数，如果存在两个项目没有同一个人选择，那么这两个项目可同时进行，精简项目，减少项目数量后，只剩下八个项目，排列组合次数减少了，算出结果。关键词：排列组合，C语言，模型优化，数据转换一、 问题重述随着经济的增长和科学技术的发展，人们的生活水平不断的提高，生活中的许多东西都趋向于智能化、自动化的方向发展，有利于节约时间，减少人工，降低成本。如今体育竞赛也在日趋紧张的现代生活中被人们提到了越来越重要的位置。我们知道，在体育运动中，赛程安排的不同，对比赛结果影响很大。而传统的编排记录工作是采用人工进行的, 工作量大, 耗时多。所以，若能给出智能化的赛程编排，同时得到合理、公平的赛程，对竞技比赛来说是很重要的。为此本文将对于给出的运动会报名表1研究如下问题：（1） 根据你的经验，给出“合理赛程”的标准。（2） 对此例作分析，通过你的算法给出赛程表。（3） 对你的方案作出评价，并就其他“合理性”标准提出你的参考意见。表1 某小型运动会比赛报名表二、 问题分析运动会的编排工作一般由赛前编排, 赛中临场编排记录公告和赛后成绩整编打印三部分组成, 工作程序复杂而细致, 要求严格、迅速、准确且符合公平竞争以及其它有关竞赛编排原则。1但是几乎所有的赛程编排一般是根据具体的项目来进行合理安排，且需要考虑的相关因素较多，所以本题决定采用步步优化机制。2.1 问题一的分析对于第一个问题，是需要根据我的经验，给出“合理赛程”的标准，但实际上作为一个并不怎么关注体育赛事的大学生来说可能给出的经验与实际相差过多，于是决定参考部分已举办运动会的学校以及国际赛事制定出标准。2.2 问题二的分析此问题需要对所给例子进行分析，但由于所给例子中并没有给出具体项目，且所给的表中有1440矩阵，每一种方案的计算就需要花费不少时间，所以决定首先在假设忽略部分因素，将每一个项目看作一样的，进行分析；然后再去除部分假设进行优化。2.3 问题三的分析题目要求对我的方案作出评价，并就其他“合理性”标准提出你的参考意见。实际上，对方案作出评价主要是看我所写的赛程表是否达到了我在问题一中制定的标准，同时对我没有提到的标准提出我自己的观点三、 基本假设（1） 假设参加完一个项目对运动员本身的精力没有影响（2） 不考虑运动会期间由于天气等其他原因延时的情况（3） 假设每个项目类型相类似（4） 假设每两个项目之间除了比赛占用时间无其他停顿时间四、 基本符号说明A代表将运动员报名表转化的数字矩阵aij代表第i个项目第j个队员的参与情况1表示该队员参与了该项目0表示该队员未参与该项目Tn代表每个项目所占用时间（n=114）RT代表每一个运动员参与项目过程中间隔休息时间总和SRT代表所有运动员间隔休息时间总和五、 “合理赛程”的标准制定1. 运动员的休息时间要足够长，即RT的值的大小为其中一个判断标准2. 求取SRT最大值，SRT为最大值的赛程安排最为合理3. 项目不具有冲突的，可以同时进行。有冲突（比如有同学同时报该项目）的也可以同时进行，但这种冲突越小越好；即考虑到冲突项目同时进行的赛程安排要优于未考虑的赛程安排4. 针对于生活实际不同项目进行的时间也是不同的，那么考虑到时间的不同性的赛程安排要优于未考虑的赛程安排六、 关于赛程安排简化模型6.1 模型的建立与求解1) 问题化简首先为了简化问题，我决定在原假设上再增加部分假设，此方法有利于问题的解决。假设提出：（1） 假设每一个项目的时间都相同即（2） 假设所有的项目都不同时进行2) 数据整理为方便计算，本人将表1，转化为了数字（如下表2），以便于用矩阵运算，或者需采用其他方法，用数字也较为方便。表2 运动员参与项数值表示同时将这些数据导入一个二维数组，进行计算。3) 采用C语言编程进行计算此方法的原理即为将14个项目的所有组合全部列出，然后对每一个队员进行分析，计算出每一个队员从一个项目到达另一个项目的时间差，算上他所有参加的项目中间的间隔时间，则为一个队员的RT，再对所有队员分别计算，然后球所有队员的时间总和SRT，此总和作为判断参量，最后选取总和值最大的一组14个项目的排列作为“合理赛程”。我采用C语言编程后，发现每计算一组大概都需要10秒而对于14种情况的排列总共有14!这么多种情况，大约为87178291200大概需要1016005天，说明算法不够精简，于是象征性的算了一组。以供分析。图6-1随意一组数据实验结果此图针对于刚开始的情况，做了一个测试。但为了验证排序功能的好坏，给出了数据如图6-2。图6-2检验结果图中1代表变换次数，如果1大于100次用省略号代替。6.2 结果分析由图6-1中可以看出此程序行之有效.从图6-2中可以看出前面1-6个项目顺序一直没变，原因就是排序是从右往左的，由于次数较多排不到1-6的变化，但是由1的多少可以确定它是能够找到时间间隔最大的数值的，找到只是时间的问题。不过如同枚举法，需一一列举，又因为数量庞大，不能一一列举完毕，于是虽可用但不建议使用。6.3 改进方向与评估我们用组合排列法建立的模型可以清楚知道每一种情况，也可以知道每一种结果，但是14个项目的全排列数目过大，计算虽有结果但是不建议采用。建议可以缩减项目，再使用。七、 对于简化模型进行优化7.1 模型建立与求解 既然是对模型的优化，那么显然模型的基本原理与模型一致，但也存在着区别，最主要的区别在于更新了假设减少了项目。1) 假设更新A. 假设每一个项目的时间都相同即B. 假设项目可同时进行2) 数据整理由于存在可同时进行的项目，为了简化问题，我就决定直接删掉部分数据，但一般选取原则是若有两个项目没有人同时参加那么就删掉，并且删掉的其中一组会是参与人员较少的那一组。整理可得表3。为了与原表格对比，于是决定不改变序号，只是删掉部分数据，由于可同时进行，对结果的影响也不会很大。且对原表格观察发现，项目1与项目5、项目2与项目6、项目3与项目7与项目11、项目4与项目9、项目10与项目12这几组项目中，无重复队员可以同时进行。于是删掉了项目1、2、7、9、11、12共六组数据。而剩下的一组数据作为代表排序。表3 简化后的表格3) 模型求解本次求解与上次同理，同样是利用C语言对所有1-8组情况进行遍历，以便于求得最大的间隔时间。图7-1 优化后模型结果图中1代表变换次数，如果1大于100次用省略号代替。7.2 结果分析显然由图中结果的可知在删去部分数据的情况下，可得到一组有着最大时间间隔的项目排序，即为：8、5、13、10、4、6、3、14。而由于可同时进行删去了部分项目，如今总的顺序大致是8，5与1，13，10与12，4与9，6与2，3与7与11，14。7.3 改进方向及评估针对于优化后的模型，可以看出一个优点在于简化了计算的次数，使用程序能得出结果，这是相对于简化模型一个较大的优势，其次多考虑了一个因素，当然这也是与实际情况比较相符的。但是显然优化后的模型还是存在着很多假设，与实际情况相差较大，并且对于项目的能否同时进行虽有判断标准，但是都是定量诉说，没有一个定性的指标，所以可以在此基础上增加一个关联度参数，以表征这两个项目的相关性，若相关性太强，则两个项目类型越相同，能同时进行，或者是能连着进行的可能性越小，利用这个判断之后，然后再利用C语言编程，导入数据，进行排序。八、 结论如今体育比赛在人们心中的地位日益上升，合理高效快捷安排赛程表变得愈发重要，本文主要针对于图表1所给的模糊报名表，给出了赛事安排的具体方案，原理清晰，方法通俗，最主要的原理是通过枚举法计算出运动员的休息时间，挑选出能使休息时间达到最大值的赛程安排，做为最合理的安排，以期望为研究赛事安排的研究人员提供部分参考意见。九、 其他“合理性标准”的参考意见我们通过查阅资料还看到了其他规则，现列举如下：（1） 安排兼项时，要尽量把相关项目分开编排，减少冲突。（2） 不同组别的同一田赛项目，一般不连续安排。（3） 不同组别的同一径赛项目，最好衔接进行。3对于以上规则，我们发现以上规则多针对于具体项目而定，在此题中不太适用，但是对于实际情况来说，这些是需要考虑的，一般情况下，我们会选择将部分田赛项目同时进行，将耗费体力的径赛项目尽量分开。其次，还应该增加一些约束条件，比如：总的时间应该为一个定值，否则当然是所有项目都分开时间越长越好。总之，这是一个比较复杂的问题，如果想要研究清楚每一种情况，可以参考选用遗传算法，定义出适当的适应度函数求解。4十、 参考文献1 李宁川 黄熹，田径运动会电脑编排系统的研究，安徽体育科技，第1期，1999年，100页。2 黄希斌，怎样做好田径运动会的组织编排工作，福州师专学报，第18卷第2期，1998年,66页67页。3 蒋尚亭，基于免疫遗传算法的高校运动会赛程编排问题研究与实现，合肥学院学报，第24卷第1期，2014年，42页。4 林 峰, 杨金远，基于遗传算法的校园田径运动会赛程编排，吉林化工学院学报，第27卷第4期，2010年，88页5 李学文 李炳照 王宏洲，数学建模优秀论文精选与点评（2015-2010），出版地：北京，清华大学出版社，2011年，30页。十一、 附录11.1 模型一源码#include#includevoid perm(int list41,int s,int e,void (*cbk)(int list41) ;void swap(int (*o)41,int a,int b);void cbk_print(int (*subs)41);int max=0;main()int list1441=0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,1,0,0,0,0,1,0,0,1,0,0,0,1,1,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,2,1,0,1,1,0,0,0,0,0,0,0,0,0,1,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,1,1,1,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,0,4,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,1,0,0,0,1,0,5,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,1,0,1,0,0,1,0,1,6,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,7,0,1,0,1,0,0,0,1,0,0,0,1,0,1,1,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,1,0,0,0,0,0,0,1,1,0,8,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,9,0,0,1,0,0,0,0,0,1,0,0,1,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,1,1,0,0,10,0,1,0,0,1,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,0,0,11,0,1,0,1,0,0,1,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,12,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,1,13,0,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,0,1,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,14;int s=0;int e=13;void (*p)(int (*)41);p=cbk_print;perm(list,s,e,p);return 0;void perm(int list41,int s,int e,void (*cbk)(int list41) int i; if(se) (*cbk)(list); else printf(1); for(i=s; i=e; i+) swap(list,s,i); perm(list,s+1,e,cbk); swap(list,s,i); void swap(int (*o)41,int a,int b) int tmp40,j;for(j=0;j41;j+)tmpj=oaj;oaj=obj;obj=tmpj;void cbk_print(int (*subs)41)int count=0,Time14,i,j,k,w;int sum=0,Sum=0;for(j=0;j40;j+)count=0;sum=0;for(i=0;i=2)for(k=1;kmax)max=Sum;printf(时间间隔：t%dn,max);printf(顺序：);for(w=0;w14;w+)printf(tt%dn,subsw40);11.2 模型二源码#include#includevoid perm(int list41,int s,int e,void (*cbk)(int list41) ;void swap(int (*o)41,int a,int b);void cbk_print(int (*subs)41);int max=0;main()int list1441=1,0,1,1,0,0,0,0,0,0,0,0,0,1,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,1,1,1,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,0,4,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,1,0,0,0,1,0,5,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,1,0,1,0,0,1,0,1,6,0,1,0,1,0,0,0,1,0,0,0,1,0,1,1,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,1,0,0,0,0,0,0,1,1,0,8,0,0,1,0,0,0,0,0,1,0,0,1,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,1,1,0,0,10,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,1,13,0,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,0,1,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,14;int s=3;int e=7;void (*p)(int (*)41);p=cbk_print;perm(list,s,e,p);return 0;void perm(int list41,int s,int e,void (*cbk)(int list41) int i; if(se) (*cbk)(list); else printf(1); for(i=s; i=e; i+) swap(list,s,i); perm(list,s+1,e,cbk); swap(list,s,i); void swap(int (*o)41,int a,int b) int tmp40,j;for(j=0;j41;j+)tmpj=oaj;oaj=obj;obj=tmpj;void cbk_print(int (*subs)41)int count=0,Time14,i,j,k,w;int sum=0,Sum=0;for(j=0;j40;j+)count=0;sum=0;for(i=0;i=2)for(k=1;kmax)max=Sum;printf(时间间隔：t%dn,max);printf(顺序：);for(w=0;w8;w+)printf(tt%dn,subsw40);