赛程安排的数学模型摘要：针对题目提出的问题, 即怎样编制出一个合理、公平的赛程安排及各队每两场比赛中间相隔的场次数的上限问题, 作了详尽、细致、深入的分析, 在分析过程中, 我们针对参赛球队的个数n 可为奇数也可为偶数的情况下, 分别用“最优配对排列法”和“循环滚动法”这两种不同的方法来解决, 当n 为奇数时, 用“最优配对排列法”编制赛程; n 为偶数时, 用“循环滚动法”编制赛程. 所谓“最优配对排列法”就是先按顺序给球队两两赋值并找出数值最小且遵循“距离最远、所打场数最少、无相同数值出现”原则的两支球队进行配对并又赋予新的值, 再寻找数值最小的两个队进行配对, 以此推出, 就可以编制最优赛程; 而“循环滚动法”就是把球队按顺序编号后分为左、右各一半, 然后左一半按序号依次往下排列, 右边紧接左边序号由下向上排列, 再固定左上角的球队, 其它球队按逆时针(或顺时针) 方向滚动, 从而得出最优赛程. 当n 为奇数时, 我们利用算法语言编制出了一套程序, 这样就可以解决n 为较大值时, 人工无法列出赛程表问题. 文中我们利用这两种方法对n 的值按顺序进行举例归纳, 以表格的形式建立出最优的数学模型, 总结出在尽量公平的情况下各队每两场比赛中间相隔的场次的上限值[]2n=∂本文讨论单场地上单循环赛的合理安排问题．运用图论算法给出了不同参赛队敷n的赛程安排，并确定了其中各队相隔两场的最大间隔场次的上限．该算法将n 为奇数和偶数的两种情况统一起来了，具有一定普遍性．给出了两种不同的衡量指标，从不同的角度衡量该赛程的优越性、关键词：单循环赛程；数学模型；算法；平均场次数问题重述今有5 支球队在同一块场地上进行单循环赛,共要进行10 场比赛,如何安排赛程使得对各队来说都尽量公平呢? 下面是随便安排的一个赛程:记5支球队为A ,B ,C ,D ,E ,在下表左半部分的右上三角的10 个空格中,随手填上1 ,2 , ⋯,10 ,就得到一个赛程,即第1 场A 对B ,第2 场B 对C , ⋯,第10 场C对E。

为方便起见将这些数字沿对角线对称地填入左下三角。

这个赛程的公平性如何呢,不防只看看各队每两场比赛中间得到的休整时间是否均等,表的右半部分是各队每两场比赛间相隔的场次数,显然这个赛程对A ,E 有从上面的例子出发讨论以下问题:1) 对于5 支球队的比赛,给出一个各队每两场比赛中间都至少相隔一场的赛程;2) 当n 支球队比赛时,各队每两场比赛最小相隔场次数的上界是什么;3) 在达到2) 的上限的条件下,给出n = 8 ,n = 9的赛程,并说明它们的编制过程;除了每两场比赛间相隔场次数这一指标外,你还能给出哪些指标来衡量一个赛程的优劣,并说明3) 中给出的赛程达到这些指标的程度。

n 支球队比赛时, 各队每两场比赛中间都至少相隔的场次数的上限模型的假设1)在比赛期间, 每支球队的比赛不受天气、场地、人为等因素的影响，每个队的实力相当．2)在比赛过程中不会出现意外的停赛事故．3)给每支球队都编上队号，依次为1，2，3．⋯，n4)每两场比赛间隔时间相等，且这段时间不足以恢复队员体力．5)比赛不安排在每支球队的主场进行;6）赛程不受比赛时间长短的影响.符号说明n:球队号(n=1,2,3,…,n) N:n个队参赛时，共需比赛的场次数；SUP （n)：相隔场次数上限； M ：表示n=8的赛程；M*：表示n=9的赛程；d(v i )：第i支球队的度数，既第支球队已参赛场数；r：平均相隔场次数；r m ax：r的上限；f：总体最大偏差；f：f的下限；ming：球队最大偏差；g min：g的下限；R：所有球队组成的一个集合； E：所有球队比赛的集合；E1：已安排比赛的场次的集合；e(vv j,)：第i支球队与第J支球队比赛、i问题的分析与模型的建立问题一：对于5支球队的情况，给出各队每两场比赛问至少相隔一场的赛程．5支球队共比赛N=10场．以5支球队为顶点．每两支球队之间进行的比赛为相应顶点间的边，则构成一个5阶完全图G，在图G中寻找一条满足条件的路径即可．见图1和表1．图1 5支球队比赛关系图5 支球队比赛赛程安排表问题二：当n 支球队比赛时，各队每两场比赛中间相隔的场次数的上限是多少?分3种情况考虑：1)第1种情况：单独考虑某一个队的最大上限，球队可以连续打比赛．最大上限为SUP(n)=C n 21-这很显然，无须证明．2)第2种情况：若只单独考虑某一个队的最大上限，每支球队的连续两场比赛间至少相隔一场．公理．如果2≤n ≤4，则必有一支球队连续的两场比赛之间不相隔任何场次． 定理1．如果n=5，则各队每两场比赛中间相隔的场次数的上限是2． 显然，证明略．定理2．如果n ≥6，则各队每两场比赛中间相隔的场次数的上限为SUP(n)=422+-n C n ． 证明：用数学归纳法来证明．(1)当n=6时，SUP(6)=7=46*226=-C ． 当n=7时，SUP(6) =11=-C 27 2 *7+4． (2)假设n=k(k>7)时， SUP(k) =-C k 22k+4成立．由于是以k 个球队为顶点，以每两球队之间的比赛为边，构成一个k 阶完全图．设v i能达到上限SUP(k)，即v i打第一场和第SUP (k) +2场，此时d (v i) =2．随后的比赛就间一场，打一场，直至最后一场比赛．当n=k+1时，就新加一个顶点v k 1+要使v i 打完第SUP(k+1) +2场时d(v i ) =2，则d(v k 1+ )应为k 一2，所以SUP(k+1) =SUP(k) +k-2．因此，当n=k+1时，SUP(k+1)=C k 2- 2k+4+ (k-2)= ()21k k + - 2(k+1) +4即当n=k+1时成立．所以SUP(n)=C n 2-2n+4． (n ≥6且n ∈N)(3)第三种情况：从整体考虑各队的最小上限，当n 支球队比赛时，各队每两场比赛中间相隔的场次数的上限1≤⎥⎦⎤⎢⎣⎡-23n 证明如下： (1)设n 为奇数，n=2k+ 1．共比赛N=k(2k+1)场．考察前k+1场，有2k+2个队参赛，于是至少有1个队两次参赛，这个队在这两场比赛间相隔场次数r 不超过(k+1)-1-1=k-1=⎥⎦⎤⎢⎣⎡-23n ． (2)设n 为偶数，n=2k ．共比赛N =k(2k 一1)场．同上，在前k+1场中至少有1个队(记这样的一个队为A )两次参赛，记A 第j 场比赛在赛程中是第aj 场，于是 a 1≥ 1，a2≤ k+1．①若a 2≤k+1，则r=a 2—a 1-1≤k-2=⎥⎦⎤⎢⎣⎡-23n ② 若a 2=k+1，但a 1>1，同样有r=a 2- a 1- 1≤k-2=⎥⎦⎤⎢⎣⎡-23n ③ 若a 1=1，a 2=k+1，在前k +1场中除A 外有2k 个队参赛，于是至少又有1个队(记这样的一个队为B)两次参赛，记B 第j 场比赛在赛程中是第b j 场，则必有b 1≥1，b2<k+1，或b 1>1，b 2≤k+1(即不可能b 1=1，b 2：k+1)，故r=b 2=b 1-1≤k-2=⎥⎦⎤⎢⎣⎡-23n 问题三：满足上限的情况下，n=8和n=9的赛程安排及编排过程．1)满足第1种上限的赛程很明显，在这里就不讨论其赛程安排及编排过程了． 2)根据第2种上限可得：(1)当n=9时，SUP(8) =16．赛程安排略． (2)当n=9时，SUP(9) =22．赛程安排略． (3)编排算[]法2 ：令R= { v v v n ,...,,21 }为点集合，E= {e(v 1,v 2 )，e(v 1，v 3)，⋯ ，e(v 1，v n )，e(v 2 ，v 1)，⋯ ，e(v n 1-，v n )}为边集合，E1= ϕ， I = 0， W = ϕ．① 任取起始点v 1；② 就近原则选取点v 2 ，得e(v 1，v 2 )，i=i+1，e(v 1，v 2 )=i ，E 1=E 1+ { e(v 1，v 2 )}．③ 在R-{v 1，v 2 }里任选两个点v v j i ,得e(v v j i ,)，i=i+1，e(v v j i , ) =i ，E 1=E1+{e(v v j i ,)}．④ 在R 一{v 1，v v j i ,}里任选两个点v v j i ,得e(v v j i , )．⑤如果e(v v j i ,)∈E-E 1，则I=I+1，=I ， e(v v j i , ) =I ，E 1=E 1 +{e(v v j i ,)}．否贝U 转⑥⑥ 如果e(v v j i , ) E —E 1，则 w=w+ {v i }．R 一{v 1，v v j i ,} 一w 在里任选两个点，v v j i ,，得e(v v j i ,)，转⑤．⑦ 重复 ④⑤ ，直到i ≥SUP(n)+1，转下一步； ⑧ 在R 一{v 1，v v j i , }里任选一个点v*，得e(v 1，v *) ， i=i+1，e(v 1，v *)=i ，E 1=E 1+ {e(v 1，v*)}；⑨ 在R-{v 1，v *}里任选两个点vv j i, ，得e(vv j i,)，转⑤ ；⑩ 当I>C n 2退出，否则转⑤． 3)根据第3种上限可得：(1)n=8，相隔场次数的上限为r=2．记8支球队为1，2，⋯8，共28场比赛．一种编制赛程的办法是将赛程分为7轮，每轮4场，各队在每轮中相遇，具体如下： “1”号固定左上角的逆时针轮转法[1] [3]’ ，具体编排方法是，先将⋯1’号确定在左上角，其他各号按大小顺序沿着逆时针方向依次捉对并列，排出第一轮次序； “I ”号固定左上角不动，其他各号每轮按逆时针方向轮转动一个号位，从而排出以后格伦的全部次序，这样就得到整个赛程M 。

见表2 表2 8支队的参赛比赛顺序（逆时针轮换法）以上方法可以推广用于n 为偶数的情况．(2)n=9，相隔场次数的上限为r=3．记9支球队为1，2，⋯9，共36场比赛．一种编制赛程的办法是：①画一4×9的表格，如表3第i行第j列的格子记作(i，j)，在每格左侧先按行依次填1，3，5，7( 第1行1个1，第2行3个3，⋯，第4行7个7 )，后按行依次填8，6，4，2，构成每场比赛的第1支队．表3 9支球队参赛的比赛顺序的初始化②在格的右侧沿各对角线填1，3，5，7，如表4 自(2，2)至(4，4)，跳过一列再自(1，6)至(4，9)填1，使1的总数(包括格子左侧的)为8，自(3，4)至(4，5)，跳过一列再自(1，7)至(3，9)填3，使3的总数(包括格子左侧的)为8，…．表4 9支球队参赛的比赛顺序的第一次轮转③在格的右侧沿各对角线填2，4，6，方法与上类似．最后在未满的8个格中填9，得到表5按照表5先列后行的顺序排列得到赛程M’，即第1场1对9，第2场3对2，…，第36场2对1．表5 9支球队参赛的比赛顺序以上方法可以推广用于n 为奇数的情况．问题四：给出衡量指标来衡量问题3中根据第3种上限编排的赛程的达标程度．1) 平均相隔场次数．记第i 队第j 个间隔场次数为C ij ,i=1，2，⋯ ，n ，j=1，2,…，n 一2，则平均相隔场次数为r =()∑∑=-=-n i n i j ijC n n 1221, r 是赛程整体意义下的指标，它越大越好． 检查n=8的赛程M ，得r =3；n=9的赛程M*，得r = 220／63=3．49．实际上， 可以得到r 的上限：r m ax =⎪⎩⎪⎨⎧=-+=--k n k k n k k k 2,112,14222r m ax 的证明如下：(1)当n=2k+1时，所有间隔场次数之和：S = ∑∑==-=n i i n j ij C 121 =2C k 212+ + 2 (C k 212+-1 )+…+ 2[C k 212+一( k-1)]+(C k 212+-k)+[-2×1-2×2-… -2× k-(k +1)] 一(2k +1) 一(2k -2) (2k +1) = (2k +1) C k 212+-4 (1+2+… + k-1) 一3k-k-1-2k-1-k 24+2k+2=()()()k k k k k k k k k k --=----++232244421422.1212所以r m ax =()()()()1421421412122422222223--=---=-+--=-k k k k k k k k k k k k n n s(2)当n=2k 时，所有间隔场次数之和：S=∑∑==-=n i i n j ij C 121=2C k 212+-4(1 + 2 + … + k - 1 ) - 2k — 2k -k 24 +6 k=)12(4242).1(.422).12(222+-=+----k k k k k k k k k k所以r m ax =11)22(2)12(4)2()1(22-=-=-+-=--k k k k k k n n Sk k所以r m ax =⎪⎩⎪⎨⎧=-+=--k n k k n k k k 2,112,14222 上述结果表明，赛程M 和M*都已达到了这个上限．2)场次的最大偏差．定义max ijf =︱C ij -r ︱为总体最大偏差，g=max i︱∑-=21n j ij C -（n-2）*r ︱为球队最大偏差， 它们都越小越好． 检查n=8的赛程M ，得f=1，g =1； n=9的赛程M*,得f=0.5，g =3.5．实际上，可以得到f 的下限：⎪⎩⎪⎨⎧=+=--k n k n k k f2,1,12,141222min 以及n=2k 时g 的下限：gmin结果表明，赛程 达到了厂和g 下限，M*也达到了f 的下限．模型的评价本模型讨论了一个在单场地上进行单循环赛的赛程安排问题先是通过合理假设，充分利用赛程安排的特点，成功地解决了赛程安排中劳逸机会不均等问题，并给出了不同参赛队数n 的赛程安排． 在上限的讨论中，从单独考虑一个队的最大上限和整体考虑各队的最大上限的两个不同角度来探讨相隔场次数的上限，从而求出3种不同情况下的上限；在讨论时将／'t 为奇数和偶数的两种情况统一起来，使模型更具有普遍和实用性．最后给出了平均相隔场次数和相隔场次数的最大偏差来衡量赛程的优越性，这两种衡量方法是比较科学和简单明了的．本模型在问题2的讨论中，前两种上限只考虑一个队的最大上限，使这个队的比赛全部挤在一起，这样可能导致严重的劳逸不均及各队参赛进度相差太大；而各队连续两场比赛中问得到的休整时间不同，从而使这个赛程有失公平性，所以由此给出的赛程就是一种劣等赛程．相对而言在第3种上限下建立的赛程，队数为的相隔场次数至少为 ⎥⎦⎤⎢⎣⎡-23n ，即每个队连续两场比赛间相隔场数都大于等于⎥⎦⎤⎢⎣⎡-23n ，并且用平均相隔场次数和最大偏差衡量了这赛程的优越性．从问题4可以得到第3种上限为最佳上限，其相应编排出的和亦为理想的赛程．总的说来，本模型直观、实用，表达方法及数学原理简单明了，又易于理解、实现及推广．参考文献：[1]程嘉炎．乓球竞赛法研究[M]．人民体育出版社，1981．[2]王树禾．图论及其算法[M]．中国科技出版社，1990．[3]王蒲．运动竞赛方法研究[M]．人民体育出版社，2001[4]曹永存．实用C 语言程序设计教程[M]．中央民族大学出版社，1994．[5]寿纪麟．数学建模方法与范例[M]．西安交通大学出版社．1993．。