赛程安排数学模型520

1赛程安排数学模型徐龙(湖南科技学院数学与计算科学系湖南永州425100)摘要:本文对赛程安排问题进行了分析，构建了以“轮转法”为基础的数学模型，提供了如何编制赛程的方法．利用“轮转法”所编制的赛程的间隔场次数上、下限及其相应的评价指标分别就球队数为偶数和奇数的情况进行了讨论．最后证明了当球队数为(6)NN偶数时，由“轮转法”所编制的赛程是最优的．关键词:数学模型；赛程安排；轮转法；赛场间隔TheMathematicalModelofCompetitionScheduleArrangementXuLong(DepartmentofMathematicsandComputationalScience，HunanUniversityofScienceandEngineering，Yongzhou，425100，Hunan）Abstract:Thisarticlehascarriedontheanalysistothequestionofcompetitionschedulearrangementandhasconstructedthemathematicalmodelof“thelawofrotates”.Moreover,italsoprovidedthemethodtoestablishthecompetitionschedule.Italsodiscussedaboutthesituationrespectivelywhentheteamnumberisevenoroddthroughtheupperlimitandlowerlimitofthenumberofcompetitionschedulethatisestablishedbythe“thelawofrotates”andthecorrespondingappraisaltarget.Finally,itprovedthatthecompetitionschemeismostsuperiorestablishedby“thelawofrotates”whentheteamnumberisodd.Keyword:mathematicalmodel;competitionschedulearrangement;thelawofrotates;gap1引言运动会作为一种体育赛事应重视它的公平性，运动会的赛制包括：循环赛、排位赛和淘汰赛本文主要考虑循环赛中各队赛程的间隔时间单循环球类比赛适用于参赛队比较少的公平竞赛，通常采用的是“轮转法”等手工编排，在编排过程中可综合考虑其它比赛因素．本题解决的是单场地单循环的竞赛赛程安排，单循环是指所有参赛队在竞赛中均能相遇一次，最后按各队在竞赛中的得分多少、胜负场次来排列名次。单循环一般在参赛队不太多，又有足够的竞赛时间才能采用。2单循环由于参加竞赛的各队都有相遇比赛的机会，是一种比较公平合理的比赛制度。体现这种比赛公平性的最大因素是某队每两场比赛的间隔场次数．单循环的竞赛场数公式为:SN(N-1)（场数）=2；1()()NNLNN为偶数轮数（为奇数）2模型2.1问题的提出为简单起见设某运动会的某项目有5个代表队,首先我们考虑所有的代表队在同一场地上进行单循环赛,共要进行10场比赛,那么如何安排赛程才公平呢?下面是随意安排的一个赛程,记5个代表队为12345T,T,T,T,T．在下表左半部分的右上三角的10个空格中,随手填上1,2,...,10,就得到一个赛程．即第一场1T对2T,第二场2T对3T,...,第十场3T对5T．为方便起见,将这些数字沿着对角线对称地填入左下角．这个赛程的公平性如何呢？不妨看看各代表队每两场比赛中间得到的休整时间是否均等,表的右半部分是各队每两场比赛间相隔的场次数,显然这个赛程对1T，5T有利,对4T则不公平.1T2T3T4T5T每两场比赛间相隔场次数1TX19361222T1X2580223T92X7104104T357X40015T68104X111表１从上面的例子出发引发了我们对以下问题的讨论:问题(1):对于5代表队的比赛,给出一个各队每两场比赛中间都至少相隔一场的赛程．问题(2):当有N个代表队比赛时,各队每两场比赛中间相隔的场次数的上限是多少?在达到(2)的上限的条件下,给出N=8,N=9,N=n(nZ)的赛程．2.2模型假设（1）假设在赛程安排中,各队的地位都是平等的，任何一个队都没有优先3权．（2）假设比赛是连续的,不间断,不受场地,天气等因素的影响．（3）假设在比赛中任何一个队都不得弃权,不能因队员受伤或意外事故影响赛程．（4）假设每天进行一场比赛．2.3符号的说明KT:第k支球队iT—jT：球队iT和jT进行的比赛(k)iP：第k支球队KT在第i轮的位号g((k)iP)：第i轮中位于(k)iP号位上的球队h((k)iP))：第i轮中位于(k)iP号位上的球队KT所进行的比赛在全赛程中的场次dmax：全赛程的间隔场次数上限dmin：全赛程的间隔场次数下限V(dmax,dmin)：全赛程的间隔场次数上限与下限之差2.4模型的建立和求解2.4.1对于问题（1）的求解对5支球队的比赛,给出一个各队每两场比赛中间都至少相隔一场的赛程，其上限为21T2T3T4T5T每两场比赛间相隔场次数1TX24681112T2X7952113T47X1102224T691X31225T85103X121表２42.4.2对于问题（2）的求解（一）当参赛球队数N为偶数时赛程的编制步骤1将所要进行的2NC场比赛平均分为N-1轮，每轮为2NC12NN场比赛,并且要求每支球队在该轮比赛中有且仅有一场比赛．步骤2在第一轮中将位号1,2,…,N和球队12T,T,NT按左边由上而下，右边由下而上(逆时针方向)排成完整的两列，并记录轮场次和总场次如下:位号第1轮位号轮场次总场次11T———NTN1122T———1NTN-12233T———NTN-233……………iTi———1NiTN-i+1ii……………2N2NT———N-1T12N+12N2N表3步骤3由第1轮的位号和比赛场次的安排用以下方法生成第2轮的位号和比赛场次的安排．将NT固定N在号位不变1T,2T,…,N-2T均按逆时针方向依次转移一个位置，N-1T由原来的N-1号位转移到1号位．如下表：位号第1轮位号轮场次总场次11T———NTN1122T———1NTN-12233T———NTN-233……………iTi———1NiTN-i+1ii……………2NN21T———N2T2N+12N2N表45重复步骤3的过程,由第2轮的赛程生成第3轮的赛程，依次类推，由第i轮的赛程生成第i+1轮的赛程(i=1,2,,N-2)．步骤4由上述步骤1、2、3可依次得出第1,2,…,N-1轮的场次安排,然后按总场次的顺序排列即可得到一个完整的赛程表．我们将由上面4个步骤所得到的赛程编制方法称为“轮转法”．下面给出有N=8支球队参赛,由上述“轮转法”所生成的赛程表：表5计算间隔场次数的上、下限对上述给出的“轮转法”所得的赛程给出如下结论：结论1各队在每一轮中有且仅有一场比赛，因此该球队在第i轮的比赛即是该队的第i场比赛．结论2各队的第i场比赛在全赛程的总场次=赛程的前(i-1)轮所需比赛的场数+该队第i场比赛在该轮(即第i轮)中的轮场次．结论3各队的第i场与第i+1场比赛的间隔数=该队的第(i+1)场比赛在全赛程的总场次—该队的第i场比赛在全赛程的总场次－1．结论4当参赛队数N(6)为偶数时，由上述轮转法所编制的赛程球队前1T2T3T4T5T6T7T8T每两场比赛间相隔场次数1Tx1726112362014443222T17x12227192254432223T2612X818315214322244T11228x41427174322445T237184x2810132224446T61931428x2492244437T20215271024x52444328T12521171395x3333336后两场比赛间隔数的上限为2N，下限为2N-2．下面给出结论4的证明：构造如下的位置转移函数，用于刻划第k支球队kT由第i轮的(k)iP号位转移到第i+1轮的(k)i1P号位．(k)(k)ii(k)(k)(k)i+1ii(k)(k)iiP+11PN-2P=f(P)=1P=N-1P,P=N，当，当当（１）其中(k)iP{1,2,,N}i=1,2,…,N-2；(1)(2)(N)111P=1,P=2,,P=N显然(1)所定义的位置转移函数是定义在从位号集{1,2,,N}到自身上的一个1-1对应．由结论1可知，在第i轮中位于(k)iP号位上的球队所进行的比赛在该轮中的场次为：(k)(k)ii(k)i(k)(k)iiP,P2g(P)=N(N+1)-P,P2N当当（２）（2）式子所定义的函数称为轮场次函数,用于记录球队kT在第i轮位于(k)iP号位上的比赛在该轮中的场次．由结论2可知,在第i轮中位于(k)iP号位上的球队kT所进行的比赛在全赛程中的场次为：(k)(k)iiNh(P)=(i-1)+g(P)2（３）（3）式子所定义的函数称为全程场次函数，用于记录球队kT在第i轮位于(k)iP号位上的比赛在全赛程中的场次．由结论3得球队kT在i轮中所进行的i场与在i+1轮中所进行的第i+1场比赛之间的间隔数为：7(k)i(k)i(k)(k)(k)(k)ii+1ii(k)i(k)iNN,1P-122NN-1,P=22NNd(P)=h(P)-h(P)-1=,+1PN-222N-2,P=N-12N,P=N2当当当当当（４）（4）式子所定义的函数称为间隔场次函数，用于刻划球队kT所进行的第i场与第i+1场比赛之间的间隔数．因此,从间隔场次函数我们得到结论4是正确的．对于参赛队数N为偶数的情形,由上述“轮转法”可以得到一个可行的编制方案(满足各队每两场比赛都至少间隔一场)．(二)当参赛球队数N(7)为奇数时记这N支球队为12NT,T,,T,可以虚拟一个参赛队，记为：0T,使之成为N+1(偶数)支球队,然后按照队数为偶数的情形进行讨论．具体步骤如下：步骤1将所要进行的2N+1C场比赛平均分为(N+1)-1轮，每轮为2N+1CN+1=N2场比赛(其中有1场是虚拟赛)，并且要求每支球队在该轮比赛中有且仅有一场比赛．步骤2在第一轮中将位号1,2,…,N+1和球队012NT,T,T,,T,按左边由上而下,右边由下而上(逆时针方向)排成完整的两列,并记录轮场次和总场次如下：位号第1轮位号轮场次10T———NTN+1121T———N-1TN232-T———N-2TN-13┇┇┇┇8N+12N-121T———N+12TN+112N+112表6步骤3由第1轮的位号和比赛场次的安排用以下方法生成第2轮的位号和比赛场次的安排．将NT固定在N+1号位不变,012N-2T,T,T,,T,均按逆时针方向依次转移一个位置，N-1T由原来的N号位转移到1号位．如下表：位号第2轮位号轮场次1N-1T———NTN+1120T———N-2TN231T———N-3TN-13┇┇┇┇12NN-121T———N-12TN+11212N表7重复步骤3，可依次得出第1,2,…,N轮的赛程,然后将含有的虚拟赛剔除，按顺序即可排出满足要求(满足各队每两场比赛都至少间隔一场)的一个赛程．下面给出用上述“轮转法”所编制的N=9支球队的一个赛程：1T2T3T4T5T6T7T8T9T每两场比赛间相隔场次数1TX1630112762413344472222T16X12267232202944332223T3012X822319342543622434T11268X41835152132322485T277224X3614311726244346T62331836X32101323234837T24219351432X289644433298T1