全国数学建模竞赛获奖论文赛程安排优化模型(02年全国一等奖)14.pdfVIP

全国数学建模竞赛获奖论文赛程安排优化模型(02年全国一等奖)14--第1页

全国数学建模竞赛获奖论文赛程安排优化模型（02年全国

一等奖）14

全国数学建模竞赛获奖论文赛程安排优化模型(02年全

国一等奖)14

赛程安排模型

赛程安排优化模型

张智勇梁星赖新峰

摘要:体育竞赛在日趋紧张的现代生活中已被人们提到了越来越重要的位置。

中国申办

2008年奥运会的成功更加提升了体育在人们生活中的份量。在对抗性强的单

循环比赛中，

赛程安排的不同，对公平性影响很大。故本文集中精力讨论的问题是如何编制

出最优的赛程

安排方案，尽量使得对每支球队来说都是公平合理的。

对于第一问，我们用计算机编程，发现在满足限制条件“每两场比赛中间相隔

场次数至

少为1”的情形下，总的编排方案共有240种，并且得出如下结论:

定理1:当参赛队数n5时满足限制条件“每两场比赛中间都至少相隔一场”

的每种

赛程安排都具有相同的公平性。

第二问，当参赛队为偶数时，我们可以用轮转法?来编排赛程方案。并且得到

如下两个

定理。

全国数学建模竞赛获奖论文赛程安排优化模型(02年全国一等奖)14--第1页

全国数学建模竞赛获奖论文赛程安排优化模型(02年全国一等奖)14--第2页

2k?4

定理2:当参赛队为n2kk?2时，各队每两场比赛中间至少间隔场比赛的

2

排法是存在的。

定理3:当参赛队为n2kk?2时，各队每两场比赛中间相隔的场次数的上限

是

2k?4

。

2

当参赛队为奇数时，本文给出了三种编排方法:蛇形法，轮转法?，轮转法?。

这三种

方法中，蛇形法的操作最简单，但是它的推广性较差，只适用于当n

5的情形，还没有找

到当参赛队n多于5的赛程最优编排方法。轮转法?的操作简便、规律性强，

对于任意参赛

队数都可很方便地编出赛程方案，但是这种方法编排出的方案对于奇数支球队

来说不是最优

方案，不过，它仅仅只比上限少1。对于参赛球队较多时，这也是一种很好的

编排方法。轮

转法?操作性比前两种方案稍显复杂，但是对于有任意奇数支参赛队的比赛，

它都能编出一

种最优的方案。对于奇数情形，本文得到如下结论:

定理5:当参赛队为n2k+1k?1时，每个队相邻两场比赛的最小间隔不可

能超过

全国数学建模竞赛获奖论文赛程安排优化模型(02年全国一等奖)14--第2页

全国数学建模竞赛获奖论文赛程安排优化模型(02年全国一等奖)14--第3页

k?1。

定理6:当参赛队为n2k+1k?1时，各队每两场比赛中间至少间隔k?1场

比赛的

排法是存在的。

除了题中给出的用“