赛程安排的数学模型与分析 1．前言 n支球队在同一场地上进行单循环赛有多种赛程安排，问题是如何编制符合公平性的赛程，数学上这是一个满足一定指标要求的配对排序问题。 本文在合理假设的基础上，由问题的数学实质，建立出问题的线性规划模型；由问题的特殊性将n分为偶数与奇数分别研究，获得关于各队每两场比赛之间相隔场次数上限的一般公式，用构造性方法加以证明；运用归纳的方法发现了这种特殊排序中的对称规律，由此设计出符合上限要求的计算机算法与实际人工编制法。文中对赛程优劣的评价指标也作了较多的探讨。 本文一个特点是，分析研究迄今体育界实际使用的赛程“循环编制法”，发现其对n为奇数时编制的赛程公平性差，给出了一种n 为奇数时编制简便、结果合理的人工编制法。 2．问题的提出

你所在的年级有5个班，每班一支球队在同一块场地上进行单循环赛, 共要进行10场比赛. 如何安排赛程使对各队来说都尽量公平呢. 下面是随便安排的一个赛程: 记5支球队为A, B, C, D, E，在下表左半部分的右上三角的10个空格中, 随手填上1,2,10, 就得到一个赛程, 即第1场A对B, 第2场B对C, , 第10场C对E. 为方便起见将这些数字沿对角线对称地填入左下三角.

这个赛程的公平性如何呢, 不妨只看看各队每两场比赛中间得到的休整时间是否均等. 表的右半部分是各队每两场比赛间相隔的场次数, 显然这个赛 程对A, E有利, 对D则不公平.

A B C D E 每两场比赛间相隔场次数 A X 1 9 3 6 1, 2, 2 B 1 X 2 5 8 0, 2, 2 C 9 2 X 7 10 4, 1, 0 D 3 5 7 X 4 0, 0, 1 E 6 8 10 4 X 1, 1, 1

从上面的例子出发讨论以下问题: 1) 对于5支球队的比赛, 给出一个各队每两场比赛中间都至少相隔一场的赛程. 2) 当n支球队比赛时, 各队每两场比赛中间相隔的场次数的上限是多少. 3) 在达到2) 的上限的条件下, 给出n=8, n=9的赛程, 并说明它们的编制过程. 4) 除了每两场比赛间相隔场次数这一指标外, 你还能给出哪些指标来衡量一个赛程的优劣, 并说明3) 中给出的赛程达到这些指标的程度.

赛程安排直接影响比赛的公平性，如何建立衡量一个赛程的优劣的指标，建立编制公平合理的排列问题的数学研究，也有数学意义。

3．基本假设（1）设n支参赛队在同一场地上进行单循环赛。（2）假设赛程的公平性只与赛程安排有关，而与裁判等其它因素无关。（3）在假设（2）下赛程的公平性就是指各队每两场比赛中间得到休整时间均等性，其中“每队每两场比赛”限定为指“每队每相邻两场比赛”。（4）假设任相邻两场比赛之间间隔时间相同。

4．建立模型 4.1符号说明 n 参赛队数 N 比赛场数 M 赛程总共安排数

jka j队与k队比赛场次序号数

jktP t队与j队及k队两场比赛间最小相隔场次数 (I,j) 第i队与第j队比赛 e 各队在全部赛程中间隔场次数 d 各队每两场比赛中间相隔场次数的上限 di 第i赛程各队每两场比赛间相隔最小场次数

4.2 问题分析 在假设（1）下，即n个队在同～场地进何单循环赛共有M=2nC场比赛，有M=（2nC）！种赛程安排，通常M是较大的数字。M种赛程中各队比赛间隔情况不同，因而对各队的比赛有影响。题目中4个问题相互联系，基本的题是赛程安排公平性及其编排法。赛程的公平性而对所有参赛队而言，同时问题（2）中“各队每两场比赛中间隔的场次数的上限”‘ 应指每个队都满足的间隔上限，其数学 表达：

d=max di

di=minjktP i=1,2,3,….. 2nC! j,k,t=1,2,3,…n 4.3 建模思想 d的数学实质是一个最大值，因此可用一个线性规划模型来描述。具体考虑满足上限d要求的赛程编排法，则由于问题的特殊性，可将n分为偶数与奇数分别考虑；

当n=2k,我们建立一种称为‘循环规则”的赛程编制法, 并得到d的公式，作出证明； 当n=2k+1，建立一种称为“移位规则”的赛程编制法, 并得到d的公式，作出证明； 两种证明的思路方法一样，都属于“构造证明法”。最后将n为偶数与奇数的上限公式统一起来。 4.4 一般模型 d=max di di=minjktP 



ntkjCilmkjaaaNaCCaaaaaastnmljkjkjknjnknnkjkkkjjktktj...3,2,1,,...3,2,1),(1)1(01p

.211

22

jkt

 5. 模型求解 5.1 问题（1）的解 表1 A B C D E 每两场比赛间相隔场次数 总间隔场次数 A X 1 7 4 10 2，2，2 6 B 1 X 9 6 3 1，2，2 5 C 7 9 X 2 5 2，1，1 4 D 4 6 2 X 8 1，1，1 3 E 10 3 5 8 X 1，2，1 4

其中d=1,具体编排法见下面问题3）解中n为奇数的方法。 5.2 问题（2）的解

当参赛队n=2k或2k-1(k=3,4,5„),各队每两场比赛中间相隔的场次数的上限为d=23n ,n=5,6,7„. 当n=8时：见表2 表2 A1 A2 A3 A4 A5 A6 A7 A8 每两场比赛间相隔场次数 总间隔场次数 A1 X 1 25 5 21 9 17 13 3，3，3，3，3，3 18 A2 1 X 16 20 26 6 11 23 4，4，4，3，2，2 19 A3 25 16 X 2 12 19 22 7 4，4，3，2，2，2 17 A4 5 20 2 X 15 24 27 10 2，4，4，4，3，2 19 A5 21 26 12 15 X 3 8 18 4，3，2，2，2，4 17 A6 9 6 19 24 3 X 14 28 2，2，4，4，4，3 19 A7 17 11 22 27 8 14 X 4 3，2，2，2，4，4 17 A8 13 23 7 10 18 28 4 X 2，2，2，4，4，4 18

当n=9时：见表3 表3 A1 A2 A3 A4 A5 A6 A7 A8 A9 每两场比赛间相隔场次数 总间隔场次数 A1 X 1 31 6 26 11 21 16 36 4，4，4，4，4，4，4 28 A2 1 X 35 10 30 15 25 20 5 3，4，4，4，4，4，4 27 A3 31 35 X 2 22 7 17 12 27 4，4，4，4，4，3，3 26 A4 6 10 2 X 34 19 29 24 14 3，3，3，4，4，4，4 25 A5 26 30 22 34 X 3 13 8 18 4，4，4，3，3，3，3 24 A6 11 15 7 19 3 X 33 28 23 3，3，3，3，3，4，4 23 A7 21 25 17 29 13 33 X 4 9 4，3，3，3，3，3，3 22 A8 16 20 12 24 8 28 4 X 32 3，3，3，3，3，3，3 21 A9 36 5 27 14 18 23 9 32 X 3，4，3，4，3，4，3 24

为方便起见，设i表示n队中第i 个队(i=1,2,3„..n) 5.2.1 n=8的编制过程：循环规则 八个队排成一个42矩阵，同一行两数表示这两队比赛（称为比赛矩阵），此矩阵表示第一轮比赛安排，如图1 下面的安排中将某队（如1队）固定不移动，余下的队逆时针循环移动1位（上、下相邻两数的位置叫“1位”），得第二轮比赛安排，如图2 56784321 



45673281

图1 图2 按此规则移动6次，既得8队比赛28场的一个赛程，此赛程满足各队每两场比赛中间相隔场次数，达到上限d=[(8-3)/2]=2,此赛程见表2。

一般n=2k，一个赛程有M=2nC场比赛，按此规则需移动（n-2）次，得满足d的赛程。 由“循环规则”编程得一上结果。 5.2.2 n=9的编制过程：移位规则 考虑一般n=2k+1，先建立一个2k(2k+1)矩阵称之为“生成矩阵”，由此矩阵即可生成赛程。下面是此矩阵的生成规则：

（1） 将任一队（如2k+1队）先占第2k+1列的各行，余下各队占第一行的余下位置，不妨设1，2，„2k队分别占第一行的1，2，„2k列。 （2） 将第一行前2k个数按下述规则向下移动得第二行，依次类似得其余各行；

a. 将奇数行从第一行算起的第奇数个数右移1位到下一行； b. 将奇数行的第偶数个数左移1位到下一行； c. 将偶数行的第奇数个数左移1位到下一行； d. 将偶数行的第偶数个数右移1位到下一行；

e. 不能移动（指移出矩阵外）的数垂直下移到下一行，如此移动n-2次则生成矩阵，由生成矩阵从第一行11a生起依次相邻两数表示一场比赛。此赛程满足各队每两场比赛中间相隔场次数达到上限d=[(n-3)/2].

当n=9时，d=[(9-3)/2]=3生成矩阵如图3。





913931254527768486935953957172718381846264624975978987836563654142412321