赛程安排优化模型论文

《赛程安排优化模型论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、赛程安排模型第10页共10页赛程安排模型赛程安排优化换型张智勇梁星赖新峰摘要：体育竞赛在日趋紧张的现代生活中已被人们提到了越来越重要的位置。中国申办2008年奥运会的成功更加提升了体育在人们生活中的份量。在对抗性强的单循环比赛中，赛程安排的不同，对公平性影响很大。故本文集中精力讨论的问题是如何编制出最优的赛程安排方案，尽量使得对每支球队来说都是公平合理的。对于第一问，我们用计算机编程，发现在满足限制条件“每两场比赛中间相隔场次数至少为1”的情形下，总的编排方案共有240种，并且得出如下结论：定理1:当参赛队数《=5时满足限制条件“每两场比赛

2、中间都至少相隔一场”的每种赛程安排都具有相同的公平性。第二问，当参赛队为偶数时，我们可以用轮转法I来编排赛程方案。并且得到如下两个定理。2k_4定理2:当参赛队为《=2k(k>2)时，各队每两场比赛中间至少间隔场比赛的排法是存在的。定理3:当参赛队为《=2k(k>2)时，各队每两场比赛中间相隔的场次数的上限是2k-42当参赛队为奇数时，本文给出了三种编排方法：蛇形法，轮转法II，轮转法III。这三种方法中，蛇形法的操作最简单，但是它的推广性较差，只适用于当《=5的情形，还没有找到当参赛队《多于5的赛程最优编排方法。轮转法II的操作简便、规律

3、性强，对于任意参赛队数都可很方便地编出赛程方案，但是这种方法编排出的方案对于奇数支球队来说不是最优方案，不过，它仅仅只比上限少1。对于参赛球队较多时，这也是一种很好的编排方法。轮转法III操作性比前两种方案稍显复杂，但是对于有任意奇数支参赛队的比赛，它都能编出一种最优的方案。对于奇数情形，本文得到如下结论：定理5:当参赛队为《=2k+1(k>1)时，每个队相邻两场比赛的最小间隔不可能超过k-1。定理6:当参赛队为《=2k+1(k21)时，各队每两场比赛中间至少间隔k-1场比赛的排法是存在的。除了题中给出的用“每两场比赛中间得到休整时间是否均

4、等”这一指标来衡量比赛的公平性外，本模型还采用了：“各队的相邻两场比赛的场次数的和”和“方差”两个指标来衡量赛程安排的优劣。赛程安排优化换型一、问题的提出体育运动日益成为国家、地区社会生活中的重要组成部分，体育运动赛事越来越频繁。每项体育比赛都需要编制赛程安排，大型比赛的赛程安排是一项繁琐的工作。赛程安排的优劣对各参赛队水平的发挥影响重大，为了使比赛公正、公平，我们在编制赛程安排时应使得第10页共10页赛程安排模型对每个参赛队尽可能平等。比赛的公平性表现在很多方面，针对赛程安排方面，比如，比赛的先后次序以及比赛期间每两场比赛间休整时间的长短

5、对比赛影响重大。对于对抗性强、体力消耗大比赛，比赛期间的休整对一个参赛队状态的调整至关重要。因此，充分、公正、公平的反映各参赛队的实力，尽管我们无法做到赛程安排对每个队完全平等，然而我们应该尽量使竞赛公平。在此背景下出现下面的问题：现有五支球队在同一块场地上进行单循环赛，共要进行10场比赛。如何安排赛程使对各队来说都尽量公平呢？下面是随便安排的一个赛程：记5支球队为A，B，C，D，E，在下表左半部分的右上三角的10个空格中，随手填上1，2,...10，就得到一个赛程，即第1场A对B，第2场B对C，…，第10场C对E。为方便起见将这些数字沿对

6、角线对称地填入左下三角。这个赛程的公平性如何呢，不妨只看看各队每两场比赛中间得到的休整时间是否均等。表的右半部分是各队每两场比赛间相隔的场次数，显然这个赛程对A，E有利，对D则不公平。ABCDE每两场比赛间相隔场次数AX19361,2,2B1X2580,2,2C92X7104,1,0D357X40,0,1E68104X1,1,1从上面的例子出发讨论以下问题：(1)对于5支球队的比赛，给出一个各队每两场比赛中间都至少相隔一场的赛程。(2)«支球队比赛时，各队每两场比赛中间相隔的场次数的上限是多少。(3)在达到（2)的上限的条件下，给出《=8,

7、《=9的赛程，并说明它们的编制过程。(4)除了每两场比赛间相隔场次数这一指标外，你还能给出哪些指标来衡量一个赛程的优劣，并说明（3)中给出的赛程达到这些指标的程度。二、问题分析第10页共10页赛程安排模型本题所要考虑的就是如何安排赛程，使得对参赛的各队都尽可能的公平、公正。对于第一问，我们要解决的问题是：（1)符合限制条件“每两场比赛中间都至少相隔一场的赛程”的编排方案总共有多少种？（2)给出一种最优的并且容易编排的赛程方案。赛程要求每两场比赛中间都至少相隔一场的赛程，且公平性仅依据各队每两场比赛中间得到的休整时间是否均等来衡量。第二问，当

8、参赛球队是2、3、4支时，每两场比赛中间相隔场次数的上限显然是0,即一定存在某个队连续比赛的情况出现。当参赛球队数《增加时，上限数会逐渐按某种关系随之增加，这种关系是这个题目的关