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

赛程安排模型 赛程安排优化模型 张智勇 梁星 赖新峰 摘 要：体育竞赛在日趋紧张的现代生活中已被人们提到了越来越重要的位置。中国申办 2008 年奥运会的成功更加提升了体育在人们生活中的份量。在对抗性强的单循环比赛中， 赛程安排的不同，对公平性影响很大。故本文集中精力讨论的问题是如何编制出最优的赛程 安排方案，尽量使得对每支球队来说都是公平合理的。 对于第一问，我们用计算机编程，发现在满足限制条件“每两场比赛中间相隔场次数至 少为1”的情形下，总的编排方案共有240 种，并且得出如下结论： 定理 1：当参赛队数n 5 时满足限制条件“每两场比赛中间都至少相隔一场”的每种 赛程安排都具有相同的公平性。 第二问，当参赛队为偶数时，我们可以用轮转法Ⅰ来编排赛程方案。并且得到如下两个 定理。 2k −4 定理 2 ：当参赛队为n 2k (k ≥2) 时，各队每两场比赛中间至少间隔 场比赛的 2 排法是存在的。 定理 3 ：当参赛队为n 2k (k ≥2) 时，各队每两场比赛中间相隔的场次数的上限是 2k −4 。 2 当参赛队为奇数时，本文给出了三种编排方法：蛇形法，轮转法Ⅱ，轮转法Ⅲ。这三种 方法中，蛇形法的操作最简单，但是它的推广性较差，只适用于当n 5 的情形，还没有找 到当参赛队n 多于5 的赛程最优编排方法。轮转法Ⅱ的操作简便、规律性强，对于任意参赛 队数都可很方便地编出赛程方案，但是这种方法编排出的方案对于奇数支球队来说不是最优 方案，不过，它仅仅只比上限少1。对于参赛球队较多时，这也是一种很好的编排方法。轮 转法Ⅲ操作性比前两种方案稍显复杂，但是对于有任意奇数支参赛队的比赛，它都能编出一 种最优的方案。对于奇数情形，本文得到如下结论： 定理 5 ：当参赛队为n 2k +1(k ≥1) 时，每个队相邻两场比赛的最小间隔不可能超过 k −1。 定理 6：当参赛队为n 2k +1(k ≥1) 时，各队每两场比赛中间至少间隔k −1场比赛的 排法是存在的。 除了题中给出的用“每两场比赛中间得到休整时间是否均等”这一指标来衡量比赛的公 平性外，本模型还采用了：“各队的相邻两场比赛的场次数的和”和“方差”两个指标来衡 量赛程安排的优劣。 第 1 页 共 1 页 赛程安排模型 赛程安排优化模型 一、 问题的提出 体育运动日益成为国家、地区社会生活中的重要组成部分，体育运动赛事越来越频繁。 每项体育比赛都需要编制赛程安排，大型比赛的赛程安排是一项繁琐的工作。赛程安排的优 劣对各参赛队水平的发挥影响重大，为了使比赛公正、公平，我们在编制赛程安排时应使得 对每个参赛队尽可能平等。比赛的公平性表现在很多方面，针对赛程安排方面，比如，比赛 的先后次序以及比赛期间每两场比赛间休整时间的长短对比赛影响重大。对于对抗性强、体 力消耗大比赛，比赛期间的休整对一个参赛队状态的调整至关重要。因此，充分、公正、公 平的反映各参赛队的实力，尽管我们无法做到赛程安排对每个队完全平等，然而我们应该尽 量使竞赛公平。在此背景下出现下面的问题： 现有五支球队在同一块场地上进行单循环赛，共要进行 10 场比赛。如何安排赛程使对 各队来说都尽量公平呢？下面是随便安排的一个赛程： 记 5 支球队为 A ， B ， C ， D ， E ， 在下表左半部分的右上三角的 10 个空格中，随手填上 1，2 ，…10， 就得到一个赛程， 即 第 1 场 A 对 B ，第2 场 B 对 C，…，第 10 场 C 对 E 。为方便起见将这些数字沿对角线对称 地填入左下三角。