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

赛程安排的数学模型摘要：针对题目提出的问题,即怎样编制出一个合理、公平的赛程安排及各队每两场比赛中间相隔的场次数的上限问题,作了详尽、细致、深入的分析,在分析过程中,我们针对参赛球队的个数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有利,对D则不公平。ABCDE每两场比赛间相隔场次AX1936122B1X258022C92X710410D357X4001E68104X111从上面的例子出发讨论以下问题: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(vi)：第i支球队的度数，既第支球队已参赛场数；r：平均相隔场次数；rmax：r的上限；f：总体最大偏差；fmin：f的下限；g：球队最大偏差；gmin：g的下限；R：所有球队组成的一个集合；E：所有球队比赛的集合；E1：已安排比赛的场次的集合；e(vvji,)：第i支球队与第J支球队比赛、问题的分析与模型的建立问题一：对于5支球队的情况，给出各队每两场比赛问至少相隔一场的赛程．5支球队共比赛N=10场．以5支球队为顶点．每两支球队之间进行的比赛为相应顶点间的边，则构成一个5阶完全图G，在图G中寻找一条满足条件的路径即可．见图1和表1．图15支球队比赛关系图5支球队比赛赛程安排表12345每两场比赛间相隔场次1X193612221X258022392X7104104357X4001568104X111问题二：当n支球队比赛时，各队每两场比赛中间相隔的场次数的上限是多少?分3种情况考虑：1)第1种情况：单独考虑某一个队的最大上限，球队可以连续打比赛．最大上限为SUP(n)=Cn21这很显然，无须证明．2)第2种情况：若只单独考虑某一个队的最大上限，每支球队的连续两场比赛间至少相隔一场．公理．如果2≤n≤4，则必有一支球队连续的两场比赛之间不相隔任何场次．定理1．如果n=5，则各队每两场比赛中间相隔的场次数的上限是2．显然，证明略．定理2．如果n≥6，则各队每两场比赛中间相隔的场次数的上限为SUP(n)=422nCn．证明：用数学归纳法来证明．(1)当n=6时，SUP(6)=7=46*226C．当n=7时，SUP(6)=11=C272*7+4．(2)假设n=k(k7)时，SUP(k)=Ck22k+4成立．由于是以k个球队为顶点，以每两球队之间的比赛为边，构成一个k阶完全图．设vi能达到上限SUP(k)，即vi打第一场和第SUP(k)+2场，此时d(vi)=2．随后的比赛就间一场，打一场，直至最后一场比赛．当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)=Ck2-2k+4+(k-2)=21kk-2(k+1)+4即当n=k+1时成立．所以SUP(n)=Cn2-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场，于是a1≥1，a2≤k+1．①若a2≤k+1，则r=a2—a1-1≤k-2=23n②若a2=k+1，但a11，同样有r=a2-a1-1≤k-2=23n③若a1=1，a2=k+1，在前k+1场中除A外有2k个队参赛，于是至少又有1个队(记这样的一个队为B)两次参赛，记B第j场比赛在赛程中是第bj场，则必有b1≥1，b2k+1，或b11，b2≤k+1(即不可能b1=1，b2：k+1)，故r=b2=b1-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={vvvn,...,,21}为点集合，E={e(v1,v2)，e(v1，v3)，⋯，e(v1，vn)，e(v2，v1)，⋯，e(vn1，vn)}为边集合，E1=，I=0，W=．①任取起始点v1；②就近原则选取点v2，得e(v1，v2)，i=i+1，e(v1，v2)=i，E1=E1+{e(v1，v2)}．③在R-{v1，v2}里任选两个点vvji,得e(vvji,)，i=i+1，e(vvji,)=i，E1=E1+{e(vvji,)}．④在R一{v1，vvji,}里任选两个点vvji,得e(vvji,)．⑤如果e(vvji,)∈E-E1，则I=I+1，=I，e(vvji,)=I，E1=E1+{e(vvji,)}．否贝U转⑥⑥如果e(vvji,)E—E1，则w=w+{vi}．R一{v1，vvji,}一w在里任选两个点，vvji,，得e(vvji,)，转⑤．⑦重复④⑤，直到i≥SUP(n)+1，转下一步；⑧在R一{v1，vvji,}里任选一个点v*，得e(v1，v*)，i=i+1，e(v1，v*)=i，E1=E1+{e(v1，v*)}；⑨在R-{v1，v*}里任选两个点vvji,，得e(vvji,)，转⑤；⑩当ICn2退出，否则转⑤．3)根据第3种上限可得：(1)n=8，相隔场次数的上限为r=2．记8支球队为1，2，⋯8，共28场比赛．一种编制赛程的办法是将赛程分为7轮，每轮4场，各队在每轮中相遇，具体如下：“1”号固定左上角的逆时针轮转法[1][3]’，具体编排方法是，先将⋯1’号确定在左上角，其他各号按大小顺序沿着逆时针方向依次捉对并列，排出第一轮次序；“I”号固定左上角不动，其他各号每轮按逆时针方向轮转动一个号位，从而排出以后格伦的全部次序，这样就得到整个赛程M。见表2表28支队的参赛比赛顺序（逆时针轮换法）第一轮第二轮第三轮第四轮第五轮第六轮第七轮(1)1—8(5)1-7(9)1-6(13)1-5（17）1-4(21)1-3(25)1-2(2)2-7(6)8-6(10)7-5（14）6-4（18）5-3（22）4-2（26）3-8(3)3-6(7)2-5(11)8-4（15）7-3(19)6-2(23)5-8（27）4-7(4)4-5(8)3-4(12)2-3（16）8-2(20)7-8(24)6-7（28）5-6以上方法可以推广用于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支队．表39支球队参赛的比赛顺序的初始化1234567891188888888233366666635555544444777777722②在格的右侧沿各对角线填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支球队参赛的比赛顺序的第一次轮转12345678911888881838587233136666163653555153544414347777173757221③在格的右侧沿各对角线填2，4，6，方法与上类似．最后在未满的8个格中填9，得到表5按照表5先列后行的顺序排列得到赛程M’，即第1场1对9，第2场3对2，…，第36场2对1．表59支球队参赛的比赛顺序1234567891198986848281838587232313969646261636535452515359494241434767472717375792921以上方法可以推广用于n为奇数的情况．问题四：给出衡量指标来衡量问题3中根据第3种上限编排的赛程的达标程度．1)平均相隔场次数．记第i队第j个间隔场次数为Cij,i=1，2，⋯，n，j=1，2,…，n一2，则平均相隔场次数为r=ninijijCnn1221,r是赛程整体意义下的指标，它越大越好．检查n=8的赛程M，得r=3；n=9的赛程M*，得r=220／63=3．49．实际上，可以得到r的上限：rmax=knkknkkk2,112,14222rmax的证明如下：(1)当n=2k+1时，所有间隔场次数之和：S=niinjijC121=2Ck212+2(Ck212-1)+…+2[Ck212一(k-1)]+(Ck212-k)+[-2×1-2×2-…-2×k