赛程安排 东华理工大学 数学建模论文2

发布时间：

赛程安排的数学模型
摘要：针对题目提出的问题,即怎样编制出一个合理、公平的赛程安排及各队
每两场比赛中间相隔的场次数的上限问题,作了详尽、细致、深入的分析,在分析过程中,我们针对参赛球队的个数n可为奇数也可为偶数的情况下,分别用“最优配对排列法”和“循环滚动法”这两种不同的方法来解决,当n为奇数时,用“最优配对排列法”编制赛程;n为偶数时,用“循环滚动法”编制赛程.所谓“最优配对排列法”就是先按顺序给球队两两赋值并找出数值最小且遵循“距离最远、所打场数最少、无相同数值出现”原则的两支球队进行配对并又赋予新的值,再寻找数值最小的两个队进行配对,以此推出,就可以编制最优赛程;而“循环滚动法”就是把球队按顺序编号后分为左、右各一半,然后左一半按序号依次往下排列,右边紧接左边序号由下向上排列,再固定左上角的球队,其它球队按逆时针(或顺时针方向滚动,从而得出最优赛程.当n为奇数时,我们利用算法语言编制出了一套程序,这样就可以解决n为较大值时,人工无法列出赛程表问题.文中我们利用这两种方法对n的值按顺序进行举例归纳,以表格的形式建立出最优的数学模型,总结出在尽量公平的情况下各队每两场比赛中间相隔的场次的上限值n
2
本文讨论单场地上单循环赛的合理安排问题．运用图论算法给出了不同参赛队敷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有利,对D则不公平。ABCDE每两场比赛间相隔场次A
X
1
9
3
6
122

BCDE
1936
X258
2X710
57X4
8104X
022410001111

从上面的例子出发讨论以下问题:
1对于5支球队的比赛,给出一个各队每两场比赛中间都至少相隔一场的赛程;
2当n支球队比赛时,各队每两场比赛最小相隔场次数的上界是什么;3在达到2的上限的条件下,给出n=8,n=9的赛程,并说明它们的编制过程;
除了每两场比赛间相隔场次数这一指标外,你还能给出哪些指标来衡量一个赛程
的优劣,并说明3中给出的赛程达到这些指标的程度。
n支球队比赛时,各队每两场比赛中间都至少相隔的场次数的上限模型的假设
1在比赛期间,每支球队的比赛不受天气、场地、人为等因素的影响，每个队的实力相当．
2在比赛过程中不会出现意外的停赛事故．3给每支球队都编上队号，依次为1，2，3．⋯，n
4每两场比赛间隔时间相等，且这段时间不足以恢复队员体力．5比赛不安排在每支球队的主场进行;6）赛程不受比赛时间长短的影响.符号说明
n:球队号(n=1,2,3,„,nN:n个队参赛时，共需比赛的场次数；SUP（n：相隔场次数上限；M：表示n=8的赛程；M*：表示n=9的赛程；
d(vi：第i支球队的度数，既第支球队已参赛场数；
r：平均相隔场次数；rmax：r的上限；

f
：总体最大偏差；
f
min
：f的下限；
g：球队最大偏差；g
E
min
：g的下限；
R：所有球队组成的一个集合；E：所有球队比赛的集合；
：已安排比赛的场次的集合；
1
e(v,v
i
j
：第i支球队与第J支球队比赛、
问题的分析与模型的建立
问题一：
对于5支球队的情况，给出各队每两场比赛问至少相隔一场的赛程．5支球队共比赛N=10场．以5支球队为顶点．每两支球队之间进行的比赛为相应顶点间的边，则构成一个5阶完全图G，在图G中寻找一条满足条件的路径即可．见图1和表1．

图15支球队比赛关系图5支球队比赛赛程安排表12
1X1
21X
392
435
568

每两场比赛间相隔场次122022

345
936
258
X710
7X4
104X
410001111
问题二：
当n支球队比赛时，各队每两场比赛中间相隔的场次数的上限是多少?分3种情况考虑：
1第1种情况：单独考虑某一个队的最大上限，球队可以连续打比赛．最大上限为SUP(n=Cn1这很显然，无须证明．
2第2种情况：若只单独考虑某一个队的最大上限，每支球队的连续两场比赛间至少相隔一场．
公理．如果2≤n≤4，则必有一支球队连续的两场比赛之间不相隔任何场次．定理1．如果n=5，则各队每两场比赛中间相隔的场次数的上限是2．显然，证明略．
定理2．如果n≥6，则各队每两场比赛中间相隔的场次数的上限为SUP(n=Cn2n4．证明：用数学归纳法来证明．
(1当n=6时，SUP(6=7=C62*64．当n=7时，SUP(6=11=C72*7+4．(2假设n=k(k>7时，SUP(k=Ck2k+4成立．
由于是以k个球队为顶点，以每两球队之间的比赛为边，构成一个k阶完全图．设
2
22
2
2
v能达到上限SUP(k，即v打第一场和第SUP(k+2场，此时d(v=2．随后
i
i
i

的比赛就间一场，打一场，直至最后一场比赛．当n=k+1时，就新加一个顶点vk1要使vi打完第SUP(k+1+2场时d(vi=2，则d(vk1应为k一2，所以SUP(k+1=SUP(k+k-2．因此，
当n=k+1时，SUP(k+1=Ck-2k+4+(k-2=即当n=k+1时成立．
所以SUP(n=Cn-2n+4．(n≥6且n∈N
(3第三种情况：从整体考虑各队的最小上限，当n支球队比赛时，各队每两场比
n3赛中间相隔的场次数的上限1≤证明如下：2
2
2
k1k-2(k+1+4
2
(1设n为奇数，n=2k+1．共比赛N=k(2k+1场．考察前k+1场，有2k+2个队参赛，于是至少有1个队两次参赛，这个队在这两场比赛间相隔场次数r不超过
n3
(k+1-1-1=k-1=．2
(2设n为偶数，n=2k．共比赛N=k(2k一1场．同上，在前k+1场中至少有1个队(记这样的一个队为A两次参赛，记A第j场比赛在赛程中是第aj场，于是a1≥1，
a
2
≤k+1．
n3①若a2≤k+1，则r=a2—a1-1≤k-2=2
n3②若a2=k+1，但a1>1，同样有r=a2-a1-1≤k-2=2
③若a1=1，a2=k+1，在前k+1场中除A外有2k个队参赛，于是至少又有1个队(记这样的一个队为B两次参赛，记B第j场比赛在赛程中是第bj场，则必有b1≥1，
b，或b>1，b≤k+1(即不可能b=1，b：k+1，故r=b=b-1≤
2
1
2
1
2
2
1

n3k-2=2
问题三：
满足上限的情况下，n=8和n=9的赛程安排及编排过程．
1满足第1种上限的赛程很明显，在这里就不讨论其赛程安排及编排过程了．2根据第2种上限可得：
(1当n=9时，SUP(8=16．赛程安排略．(2当n=9时，SUP(9=22．赛程安排略．(3编排算法：
令R={v1,v2,...,vn}为点集合，
E={e(v1,v2，e(v1，v3，⋯，e(v1，vn，e(v2，v1，⋯，e(vn1，vn}为边集合，
2
E
1
=，I=0，W=．
①任取起始点v1；
②就近原则选取点v2，得e(v1，v2，i=i+1，e(v1，v2=i，E1=E1+{e(v1，v2}．
③在R-{v1，v2}里任选两个点vi,vj得e(vi,vj，i=i+1，e(vi,vj=i，
E=E
1
1
+{e(vi,vj}．
④在R一{v1，vi,vj}里任选两个点vi,vj得e(vi,vj．

⑤如果e(vi,vj∈E-E1，则I=I+1，=I，e(vi,vj=I，E1=E1+{e(vi,vj}．否贝U转⑥
⑥如果e(vi,vjE—E1，则w=w+{vi}．R一{v1，vi,vj}一w在里任选两个点，vi,vj，得e(vi,vj，转⑤．
⑦重复④⑤，直到i≥SUP(n+1，转下一步；⑧在R一{v1，vi,vj}里任选一个点=i，E1=E1+{e(v1，⑨在R-{
v，得e(v，v，i=i+1，e(v，v
*
1
*
1
*
v}；
*
v，v}里任选两个点v,v，得e(v,v，转⑤；
1
*
ijij
⑩当I>Cn退出，否则转⑤．3根据第3种上限可得：
(1n=8，相隔场次数的上限为r=2．记8支球队为1，2，⋯8，共28场比赛．一种编制赛程的办法是将赛程分为7轮，每轮4场，各队在每轮中相遇，具体如下：“1”号固定左上角的逆时针轮转法[1][3]’，具体编排方法是，先将⋯1’号确定在左上角，其他各号按大小顺序沿着逆时针方向依次捉对并列，排出第一轮次序；“I”号固定左上角不动，其他各号每轮按逆时针方向轮转动一个号位，从而排出以后格伦的全部次序，这样就得到整个赛程M。见表2表28支队的参赛比赛顺序（逆时针轮换法）第一轮(11—8(22-7(33-6(44-5
以上方法可以推广用于n为偶数的情况．
第二轮(51-7(68-6(72-5(83-4
第三轮(91-6(107-5(118-4(122-3
第四轮(131-5（14）6-4（15）7-3（16）8-2
第五轮
（17）1-4（18）5-3(196-2(207-8
第六轮(211-3（22）4-2(235-8(246-7
第七轮(251-2（26）3-8（27）4-7（28）5-6
2

(2n=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支队．
表39支球队参赛的比赛顺序的初始化
1234
②在格的右侧沿各对角线填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，„．表49支球队参赛的比赛顺序的第一次轮转1234
③在格的右侧沿各对角线填2，4，6，方法与上类似．最后在未满的8个格中填9，得到表5按照表5先列后行的顺序排列得到赛程M’，即第1场1对9，第2场3对2，„，第36场2对1．
表59支球队参赛的比赛顺序1234
119325476
289315274
386395172
484695371
582645973
681624975
783614279
885634129
987654321
11357
283157
383517
4865371
586573
6816475
7836147
88563412
987654321
11357
28357
38357
48657
58657
68647
78647
88642
98642

以上方法可以推广用于n为奇数的情况．
问题四：
给出衡量指标来衡量问题3中根据第3种上限编排的赛程的达标程度．
1平均相隔场次数．记第i队第j个间隔场次数为Cij,i=1，2，⋯，n，j=1，2,„，
nn2
1
n一2，则平均相隔场次数为r=,r是赛程整体意义下的Cij
nn2i1ji
指标，它越大越好．检查n=8的赛程M，得r=3；
n=9的赛程M*，得r=220／63=3．49．
2
2kk,n2k12实际上，可以得到r的上限：rmax=rmax的4k1k1,n2k
证明如下：
(1当n=2k+1时，所有间隔场次数之和：
S=Cij=2C2k1+2(C2k1-1+„+2[C2k1一(k-1]+
2
2
2
inn2i1j1
(C2k1-k+[-2×1-2×2-„-2×k-(k+1]一(2k+1一(2k-2(2k+1=(2k+1C2k1-4(1+2+„+k-1一3k-k-1-2k-1-4k+2k+2=
2
2
2
2k12k1.2k4k1k4k24k4k32k2k
2
2
4k2kkk4k12k2ks
k所以rmax=22
nn22k12k14k14k1
32

2

22
(2当n=2k时，所有间隔场次数之和：
S=Cij=2C2k1-4(1+2+„+k-1-2k—2k-4k+6k
i1j1inn2
2
2

=
2k(2k1.2k(k1.k22
4.4k2k4k(k2k1
22
2
4k(k2k1S
所以rmax=
n(n22k(2k2
22kk,n2k12所以rmax=4k1k1,n2k
(k1
k1
2
k1
上述结果表明，赛程M和M*都已达到了这个上限．
2场次的最大偏差．
定义fmax︱Cij-r︱为总体最大偏差，g=max︱Cij-（n-2）*r︱
ij
i
n2j1
为球队最大偏差，它们都越小越好．检查n=8的赛程M，得f=1，g=1；n=9的赛程M*,得f=0.5，g=3.5．
221
k2,n2k1,
min4k1
1,n2k
实际上，可以得到f的下限：
f
以及n=2k时g的下限：g
min

结果表明，赛程达到了厂和g下限，M*也达到了f的下限．
模型的评价
本模型讨论了一个在单场地上进行单循环赛的赛程安排问题先是通过合理假设，
充分利用赛程安排的特点，成功地解决了赛程安排中劳逸机会不均等问题，并给出了不同参赛队数n的赛程安排．在上限的讨论中，从单独考虑一个队的最大上限和整体考虑各队的最大上限的两个不同角度来探讨相隔场次数的上限，从而求出3种不同情况下的上限；在讨论时将／'t为奇数和偶数的两种情况统一起来，使模型更具有普遍和实用性．最后给出了平均相隔场次数和相隔场次数的最大偏差来衡量赛程的优越性，这两种衡量方法是比较科学和简单明了的．本模型在问

题2的讨论中，前两种上限只考虑一个队的最大上限，使这个队的比赛全部挤在一起，这样可能导致严重的劳逸不均及各队参赛进度相差太大；而各队连续两场比赛中问得到的休整时间不同，从而使这个赛程有失公平性，所以由此给出的赛程就是一种劣等赛程．相对而言在第3种上限下建立的赛程，队数为的相隔场次
n3n3
数至少为，即每个队连续两场比赛间相隔场数都大于等于，并22
且用平均相隔场次数和最大偏差衡量了这赛程的优越性．从问题4可以得到第3种上限为最佳上限，其相应编排出的和亦为理想的赛程．总的说来，本模型直观、实用，表达方法及数学原理简单明了，又易于理解、实现及推广．参考文献：
[1]程嘉炎．乓球竞赛法研究[M]．人民体育出版社，1981．[2]王树禾．图论及其算法[M]．中国科技出版社，1990．[3]王蒲．运动竞赛方法研究[M]．人民体育出版社，2001
[4]曹永存．实用C语言程序设计教程[M]．中央民族大学出版社，1994．[5]寿纪麟．数学建模方法与范例[M]．西安交通大学出版社．1993．


赛程安排 东华理工大学 数学建模论文2

推荐内容

相关推荐