2022年高教社杯全国大学生数学建模竞赛D题

1、 102022 高教社杯全国大学生数学建模竞赛 D 题赛程安排5 个班，每班一支球队在同一块场地上进展单10 场竞赛。如何安排赛程使对各队来说都尽量公正呢？下面是任凭安排的一个赛程：记5 支球队为10 个空格中，顺手填上 1，2，10，1 场 A B2 B C，第 10 场 C对E。为便利起见将这些数字沿对角线对称地填入左下三角。这个赛程的公正如何呢？不妨只看看各队每两场竞赛中间得到数，明显这个赛程对A，E有刮，对D则不公正。ABCDE每两场比场间相隔场次数A19361，2，2B12580，2，2C927104，1，0D35740，0，1E681041，1，1从上面的例子动身争辩以下问题5 相

2、隔一场的赛程。当n 限是多？2)n=8，n=9 的赛程，并说明它们的编制过程。3)中给出的赛程到达这些指标的程度。问题的分析 体育竞赛要消耗大量的体力，特别是球类竞赛，必需进展多场长时间的比赛，体力是否充分直接影响到成绩的优劣。5 个A 队是最有利的，由于这样的赛程他可以利D 队3 场，明显这对他来讲是很不利的。由此可以看出，为了的赛程安排应当是对每个队都尽量做到公正。问题1)的解答有多种方法(甚至是凑的方法)都能给出一个到达要求的赛程，如(表1)。ABCDE每两场竞赛间相隔场次数A16931，2，2B147102，2，2C64281，1，1D97252，1，1E310851，2，1(1)1

3、5 个球队各队每两场竞赛中间相隔的场次数的上限。的解答 n 数的上限是rn3，证明如下：2设赛程中某场竞赛是i，j兩队，i队参与的下一场竞赛是i，k兩间必需有除i，j，k 2r 支球队参赛，于是n2r+3,r 为n3整数即得r2。的解答 n=8，相隔场次数的上限为r=28 1，2，3，4，5，6，7，828 场竞赛。一种编制赛程的方法是将赛分为7 4 场，各队在每轮中相遇，具体步骤如下：1构造M13578 8463 447 8。2M213378462 轮，方法是：M1 1 不7 个数字按逆时针转动，换一个位置。31 M ，将M ,312 2357154683781465786178618641

4、6324753287421423123536875468771 1 22 3 428 5 7。队相隔的场次数相隔场次总数13, 3, 3, 队相隔的场次数相隔场次总数13, 3, 3, 3, 3, 31824, 4, 4, 3, 2, 21932, 4, 4, 4, 3, 21944, 4, 3, 2, 2, 21752, 2, 4, 4, 4, 31964, 3, 2, 2, 2, 41772, 2, 2, 4, 4, 41883, 2, 2, 2, 4, 417(2)以上方法可以推广用于n 为偶数的状况。N=9r=39 1，2，9，36场。一种编制赛程的方法是：1. 49 的表格，如(3)

5、i 行第j 列的格子记作(i，j)，1 1 2 3 4 7 7)8，6，4，21 支队。1118283848586878889233366666635555544444777777722(3)2. 1，3，5，74。自(2，2)至(4，4)，跳过一列再自(1，6)至(4，9)11 的总数(包括格子左侧的)8，自(3，4)至(4，5)，跳过一列再自(1，7)至(3，9)33 的总数(包括格子左侧的)8，12345678911888881838587233136666163653555153544414347777173757221(4)在格的右侧沿各对角线填 2，4，6，方法与上类似。最终在未8

6、 9，得到(5)5 先列后行的挨次排列得到赛程M，即第1 场1 对9，第2 场3 对2，第36 场2 对1。简洁得到赛程各队每两场竞赛中间相隔的场次数及其总数，如(6)所示。M=1234567891198986848281838587232313969646261636535452515359494241434767472717375792921(5)队相隔的场次数相隔场次总和14，4，4，4，4，4，42824，4，4，4，4，4，32733，3，4，4，4，4，42644，4，4，4，3，3，32553，3，3，3，4，4，42464，4，3，3，3，3，32373，3，3，3，3，3，4

7、2283，3，3，3，3，3，32193，4，3，4，3，4，3(表 6)24以上方法可以推广到n 为奇数的状况。的解答衡量赛程优劣的其它指标除了“各队每两场竞赛之间最小相隔场次的上界”这一指标外，还可以用一些指标来衡量赛程的优劣，如平均相隔场次ij记第i 队第j 个间隔场次数为c，i=1,2,n,j=1,2,n-2,则平均相隔场次为ij1r 1nn2cn n2iji1(1)r是赛程整体意义下的指标，它越大越好。而(1)式右端的求和2 3 最终一列之和。检查 n=8 的赛程(表 2)r 3；检 n=9 的赛程(表 6)，得r 220/ 633.49。实际上，可以得到r的上界为2k2r k 4k

8、2 1,n 2k 1maxk1,n(2)上述结果说明，(2)、(6)给出的赛程都已到达了这个上界。相隔场次数的最大偏差c赛程中各队每兩场竞赛相隔场次“均匀性可由 ij 与r偏差来度量，定义cf max c r(3)ri,jijn2g max c n2rn2iij(4)f 为整个赛程相隔场次数的最大偏差，g 为球队之间相隔场次的最大偏差，它们都是越小越好。n=8 的赛程(2)f=1，g=1n=9 的赛程(6)，得f=0.5，=5.5。实际上，可以得到f 的下界为2k2,n 2k 1fmin 4k2 1(5)1,n2k以及n=2k时g 的下界为(6)g1(6)min上述结果说明，(2)给出的赛程到

9、达了f 和g 的下界，(6)给出的赛程也到达了f的下界。几个留意问题：2)“各队每兩场竞赛最大相隔场次的上限”此理解应有r 2n3 r n赛最大相隔场次数的上限为界于这两者之间即2样编制的赛程恰好是最优的。n32这2. 对于r 2大局部队都分别对n为偶数和n为奇数兩种情设n为奇数，n=2k+1N=k(2k+1)k+1场，2k+2 1 个队两次参赛，这个队在这兩场比n3赛间相隔场次数r不超过(k+1) 11=k-1=2。设n为偶数，n=2k。共竞赛N=k(2k1)场。同上，在前k+1场中至少有一个队(记这样的一个队为A)两次参赛，记Aj 场竞赛在赛程中是第a场，于是ja 1,a1k 1。假设 k

10、 1r aa 1 k 2 则，21则n32；假设ak 1但1r a 1 k 2 n32122 ；a 1,a1 k 1k+1 场中除A2k 1 个队(B)B j 场竞赛在赛程中是第bj 场，则必有b1,b2 k 1,b或1或1,b2k 1(1即不行能b 1,b k 1)，故(1r b212b 1 k 2 1n32对赛程优劣的其它指标争辩，对赛程优劣其它指标只要是合理时间竞赛一场与每天安排竞赛三场(上午、下午、晚上各赛一场)中间休息的时间是不一样的；有的队认为和所对应竞赛队的强弱也有关，要保证能胜，我可以多派些替补队员上场，让主力队员多休息。还有的信息，以便考虑对策。以下是另外几种方法：方法11)

11、 对于5 支球队给出了一种各队每场竞赛中间至少相隔一场的赛程安排。方法如下：记5支球队为A、B、C、D、E如下(7)所示ABCDE每两场竞赛间隔场次数(表ABCDE每两场竞赛间隔场次数A16931,2,2B147102,2,2C64281,1,1D97252,1,1E310851,2,1编制过程为如图一所示不防假设第一场竞赛A 对BAB。其次场竞赛为CD，E、A、B 可以参与第三场竞赛，即EA，EB，AB，由于A、B已在第一场竞赛过，故排解AB，则只乘下EA，EB 两种可能，不妨假设第三场竞赛为EA。以此类推，以后各场竞赛程序安排为BC，DE，AC，BD，EC，AD，BE。由于球队之间进展的是

12、单循环赛，所以任何两队之间只能进展一场竞赛。即对任何一队而言，曾经与其交战过的队，在以后的竞赛当中不再相遇。BEBEADECBDBCABACEADEBEBCABEAEADAABCDEBEB图一 图一 5 支球队赛程安排的对于N1、2、N。分两种状况编排赛程：当N 为大于5 N-1 轮，将最大号固定右上角(由于各号码在排序过程中时机均等，不妨假设放置的号是最大号)，其他各号按大小挨次沿逆时针方向配对，排出第一轮；最大号固定在右上角不动，其他各号出N8 支球队的编制法如(8)所示(表8)8 支球队赛程安排编制过程第一轮第一轮其次轮第三轮第四轮第五轮第六轮第七轮1878685848382827167

13、5645342313625147362514745342312716756这种方法和我们所讲的方法其实是一样的。为N 5 支球队的奇数时，用轮转法()，方法如下：首先将全都赛程分为(N1)/2 轮。称为大轮(马上全部赛程翻一依次配队，排法第一轮。最小号固定不变，上方的小轮其他各号按顺N 为奇数的赛程安排。9 支球队的编制法如(9)所示。(表9)9 支球队赛程安排的编制过程及竞赛次序第一轮其次轮第三轮第四轮191213142839425337485962465768795161718192233445839425367485962765768798方法2(1) 对于N 为偶数时方法和前面的根本相

14、像，具体编制不作介绍。只把结果列于下(表11)(2) 对于N为奇数时的编制方法如下：N(N1)/2 个格，每一格表示一场竞赛。图 二n11置于第一场竞赛，再依次每 2场参与一场竞赛，直到整个赛程完毕。再A将置于A 完毕的位置，开头往回隔 1 次每21n1n 12场参与一场竞赛，然后依次每 2场参与一场竞赛，直到整个赛程完毕。A3置于AA 2 次每An1n 12场参与一场竞赛，然后依次每 2场参与一场竞赛，直到整个赛程完毕。ii1依此类推，将 A置于A回(iii1n1每 2n 12场参与一场竞赛，直到整13 14个赛程开头或完毕。nn安排在其它的竞赛场次即可。A116A1161116212631

15、36A2A3A4A5A6A7A8A91510141923283227121722273236261015202530353813182327313537111519242934491418222630344812162024283359131721252933每两场竞赛间相隔场次数休息总场数123(表每两场竞赛间相隔场次数休息总场数123AAAAAAAAA123456789A 36631112616211444444428A36 227722121732444444327A62 351530202510334444426A431273531881323444433325A51171533424

16、2919333344424A626223018344914443333323A716122082443328333333422A821172513299335333333321AA913210231914285343434324每两场竞赛间相隔场次数休 息A1333333总场数18每两场竞赛间相隔场次数休 息A1333333总场数18A21 2062311261619A352024102715219A49624282431919A513231028418718A617112714482217A721261531881217A825162197221217AAAAAAAA123456781591

17、3172125444322244432224443222444322244432224443222方法3将参赛球队从小到大编号：1、2、N。然后按以下步骤进展编排：1 的参赛队固定在定点o 上，然后2、3、4、N。1 号固定不动，对于奇数队，以“8”字的写法相反方向蠕动，而对偶数队，则以“8”字的写法方向进展蠕动。每一轮蠕动一个位置。5、7 个参赛队(奇数)的模型如下：6、8 个参赛球队(偶数)的模型如下以顶点“1”为界将模型分为上下两局部，然后以项点为起u ,u始点按逆时针方向将上下两局部记为上局部记为 12,uN，1d ,d下局部记为： 12,dN2。例如16配队方法如下：对于奇数队：1i定点d ,1ud1,ud2,uN定点1(ii)du ,d u ,du， du112233NN21对于偶数队：定点d1,u d1,u d2,， u dnn 18 9 支球队的赛程编排结果如下表12 13。表12N=12的赛程编排结果第轮一第轮二第轮三第轮四第轮五第轮六第轮七每两场竞赛相隔场次数181716151413121:3333332:443222278675643524383:43