|
|
球队赛程最佳安排方案模型
一．问题的提出
体育比赛，作为丰富大﹑中﹑小学生的课外活动的手段之一，受到社会和学校的大力支持以及同学们的热烈欢迎。赛程安排是否合理将直接影响到同学们参加的积极性。所以，建立一支模型确定赛程安排以及评价比赛的公平性和合理性有十分重要的现实意义。
下面有支例子：
A B C D E 没两场比赛相间隔场次数
A X 1 9 3 6 1，2，2
B 1 X 2 5 8 0，2，2
C 9 2 X 7 10 4，1，0
D 3 5 7 X 4 0，0，1
E 6 8 10 4 X 1，1，1
某学校要进行一场球赛，一共有五支队参加。由于只有一支场地，只能进行单循环赛。一共有十场比赛。他们的赛程是这样安排的：记5支球队为A，B，S，D，E，在下表左半部分的右上角的10个空格中的1，2…10，代表各队参加比赛的场次，即第1场A对B，第2场B对C…第10场C对E。
表一
从表中我们很容易看出，这支赛程的安排很不合理，各队每两场中得到的休息时间很不均等。显然这支赛程对A，E有利，而对D则很不公平。
下面要求我们编制一支赛程，要求两场比赛之间的时间间隔尽可能的均衡。即：
1． 对于5支球队的比赛，给出一支各队每两场比赛中间至少相隔一场的赛程。
2． 当有n支球队比赛时，各队每两场比赛中间间隔的场次数的上限是多少。
3． 在达到2）的上限的条件下，给出n=8，n=9的赛程，并给出它的编制过程。
4． 除了每两场比赛间隔场次外，给出几支其他方面的指标来衡量一支赛程的优劣，并说明在3）中给出的赛程达到这些指标的程度。
二．问题分析
这是一支排序问题。在有N支队的情况下，因为是单循环赛，有排列组合的知识易知一共要进行Cn2 即n(n-1)/2场比赛。因为任意两场比赛的两支队是不完全相同的，所以共有(N(N—1)/2)！种不同的赛程。在那么多不同的赛程中，有的各队每两场比赛间相隔的场次数（也是各队每两场比赛中间得到的休整时间）有的较多，有的较少。这就存在不公平。我们的任务是在那么多不同的赛程中间找一支各队每两场比赛间相隔的场次数较均等的赛程（或称最优赛程）。由于有n支队参加比赛的总的不同赛程数是一个定数（（N（N—1）/2）！），因此最优赛程是存在的。而且由于文中将要说道的原因，最优赛程是不唯一的。
三．问题的假设
1． 两队组合进行一场比赛，不考虑第几场比赛只考虑每队两场比赛的间隔数。
2． 不考虑各参赛队实力对赛程安排的影响。
3． 每队都能如期按时间参加比赛，不考虑天气，场地，队员受伤等因素对赛程的影响。
4． 当参赛的总队数小于3时候，赛程只有一种，没有研究的实际意义，我们默认参赛的总队数是大于等于3的。
四 符号说明
建模中所用到的符号如下：
A：上限
N：参赛的队数
P1，P2，P3，…；PI，PJ：表示第1，2，3…I，J个参赛队；以及它们的变形如P（N—1）等前面的P表示参赛队，后面的数字及代数式表示参赛队的序数即第几个参赛队。
五 模型的建立和求解
（1）.上限的确定
定义（上限）：N队进行比赛，共有N（N—1）/2）！种不同的赛程，在第PI种赛程中，各队每两场比赛中间最少的场次间隔为M，把各种赛程中各队每两场比赛的最少场次间隔中的最大值定义为场次数最少间隔的上限，简称上限。记为A。
定理 1 在一支有N个队参加的比赛中，上限是唯一存在的。
证明 因为参赛队数N是已知的，所以不同的赛程数（N（N—1）/2）是固定的。每一种赛程安排都有一个各队间隔的最少场数，所以上限是存在的。因为最大值只能有一个，所以上限是唯一的。
定理2在一支有N个队参加的比赛中，上限A=（TRUNC（N—3）/2）。（对（N—3）/2取整）。
证明 1．假设A>TRUNC（（N-3）/2），则有上限的定义知：A最少应为TRUNC（（N-3）/2）+1。
当N为偶数时，有
TRUNC（（N-3）/2）=N/2—2
有上限的定义知：
（A+1）（N—1）+N N(N—1)/2
即： （N/2 —1）（N—1）+N N(N—1)/2
化简得： 1 0
显然是假设是错误的。
同理可证N为奇数是假设也是错误的。
2．假设A< TRUNC（（N-3）/2），则有上限的定义知：其最大只能为 A= TRUNC（（N-3）/2）—1。
设N=5时，A= TRUNC（（N-3）/2）—1=0。易排出P1P2→P3P4→P5P1→P2P3→P4P5→P1P3→P2P5→P4P1→P3P5→P2P4，其上限为1。
所以假设是错误的。
有1，2以及定理1知，A=（TRUNC（N—3）/2）。
（2）最优赛程的确定
我们所要求的最优赛程是各队没两场比赛中间得到的休息时间比较均等的赛程。也是上限所在的赛程。在这一节里我们将介绍寻找最优赛程的方法，也是寻找上限所在的赛程的方法。
定义（正规赛程） 在一个赛程中第PI个队已经参加了K场比赛，在参加K+1场比赛时，其他各队参加比赛的场次数最大不大于K+2的赛程叫做正规赛程。
定理3 不是正规赛程的赛程一定不是最优赛程。
证明 假设一个最优赛程不是最优赛程，有正规赛程的定义知：
PI， PJ，当PI参加了K场比赛时，PJ已经参加了K+2场，这样可以调换PI和PJ，使得PI，PJ之间的休息时间更均等，从而是赛程更优。所以假设是错误的。所以不是正规赛程的赛程一定不是最优赛程。
定义（一个循环）：在有N支球队参加的球赛中，每支球队都至少参加一次，而且所有球队参加的场次都相等，所进行比赛的最少场数称为一个循环。
有常识知：当N为偶数时打一个循环需要进行N/2场，当N为奇数时打一个循环需要进行N场。
定理 4在一支有N个队参加的比赛中，上限所在的赛程是一个有有限个循环所组成的赛程。
证明 对于确定的参赛队数N，其比赛总场数是一定的，一共要进行N（N—1）/2比赛。
假设上限所在的赛程不是一个有有限个循环所组成的赛程。则有
（1）当N为偶数时，把N/2场连续的比赛分为一段，一共可分为N—1段。
假设前K（K=0，1，2…N—1）段比赛都是整个循环，则在前K段比赛中各队参加的场次数都相同。当进行第K+1段比赛时，若第K+1段是最后一段，则每个队只剩一场比赛，组成一个循环。若第K+1段是不是最后一段，设有PI没有参加第K+1段比赛，则 PJ，使得PJ参加了第K+1段的两场比赛，当PI在次参加比赛时，PJ参加的比赛常数比PI参加的场数多2或者更多，则赛程不是正规赛程，就不是最优赛程，从而也不是上限所在的赛程。
（2）同理可证N为奇数时定理成立。
证毕。
有定理4可知上限所在的赛程是一个有有限个循环所组成的赛程。根据一个循环的定义，我们可以把有N个队参加的比赛的赛程的参赛队组合分组，使得每组是一个循环。下面介绍分组的方法。
把N个队的N（N—1）/2场比赛的参赛队组合排成下面的形式：
表二
P1，P2
P1，P3 P2，P3
P1，P4 P2，P4 P3，P4
P1，P5 P2，P5 P3，P5 P4，P5
… … … … …
… … … … … P（N-1），P（N-2）
P1，PN P2，PN P3，PN P4，PN … P（N-2），PN P（N-1），PN
N+1 2N+2 3N+3 4N+4 … （N-2）*N+N-2 （N-1）*N+N-1
把各个参赛队的下标按与水平线成1350 对角线求和，结果如上图所示。
按求和的结果先把最小的和最大的为一组，次小的和次大的分为一组…依次论推。
当N为奇数时，各组的每场比赛的参赛队的组合依次为：
P1，P（N—I）；P2，P（N—I+1）；……P（N—I），PN；P1，PI+1；P2，P（I+2）；……P（N—1+1），PN；可划分为（N—1）/2个组，每个组的每个队都参加两场比赛，有一个循环的定义知，这正好是一个循环。
当N为偶数时，各组的每场比赛的参赛队的组合依次为：
P1，P（N—I）；P2，P（N—I+1）；……P（N—I），PN；P1，PI；P2，PI+1；……P（N—I—1），PN；
易知这每组是两个循环，并且非常容易划分开。
最后剩下最中间的那一列：
P1，PN/2+1；P2，PN/2+2；……PN/2，PN；正好是一个循环。
下面我们考虑对每个循环的排列。
当N为奇数时：
在每一个循环中，各个队都参加了两场比赛，设有一循环为：
P1，P2；P2，P3；P3，P4；……PN—2，PN—1；PN—1，PN；PN，P1。
其他形式的循环可以通过下标之间的调换等价到这种形式。
根据上限的要求，我们把第一个循环排为：
P1，P2；P3，P4；……PN—2，PN—1；PN，P1；P2，P3；……PN—1，PN。
然后任取一个循环作为第二个循环。在排第二个循环时，在循环中找这样的组合，使得其下标的两个数字在它前面相隔A个的两个组合出现的数字，并且除去它前面的组合出现的数字。依上例第二个循环的第一个组合应为在PN—2，PN—1，P1三队组成的组合中，在所选的第二个循环出现的中任选一个。依次论推，一直到排完。
当N为偶数时：
有一个循环的定义知每一个循环的的任意组合都满足上限的要求。所以可任取一个循环作为第一个循环。往下的排法同N为奇数时的情况。
（3）具体问题求解
1）对于5支球队的比赛易排出P1P2→P3P4→P5P1→P2P3→P4P5→P1P3→P2P5→P4P1→P3P5→P2P4。
2）当有N支球队参加时，有定理2知各队每两场比赛中间相隔的场次数的上限为TRUNC（N—3）/2）。
3）在达到2）的上限的条件下，当N=8时有排序：
表三
P1 P2 P3 P4 P5 P6 P7 P8 每两场比赛相隔场次数
P1 \ 1 20 5 24 9 17 13 3,3,3,3,2,3
P2 1 \ 23 28 19 6 14 10 4,3,3,4,3,4
P3 20 23 \ 2 12 15 26 7 4,4,2,4,2,2
P4 5 28 2 \ 16 25 11 21 2,5,4,4,3,2
P5 24 19 12 16 \ 3 8 27 4,3,3,2,4,2
P6 9 6 15 25 3 \ 22 18 2,2,5,2,3,2
P7 17 14 26 11 8 22 \ 4 3,2,2,2,4,3
P8 13 10 7 21 27 18 4 \ 2,2,2,4,2,5
编制过程：
（1）分组。
表四
P1，P2
P1，P3 P2，P3
P1，P4 P2，P4 P3，P4
P1，P5 P2，P5 P3，P5 P4，P5
P1，P6 P2，P6 P3，P6 P4，P6 P5，P6
P1，P7 P2，P7 P3，P7 P4，P7 P5，P7 P6，P7
P1，P8 P2，P8 P3，P8 P4，P8 P5，P8 P6，P8 P7，P8
N=8，为偶数。可分为4组。
表五
第一组 P1，P2；P2，P3；P3，P4；P4，P5；P5，P6；P6，P7；P7，P8；P8，P1
第二组 P1，P3；P2，P4；P3，P5；P4，P6；P5，P7；P6，P8；P1，P7；P2，P8
第三组 P1，P4；P2，P5；P3，P6；P4，P7；P5，P8；P1，P6；P2，P7；P3，P8
第四组 P1，P5；P2，P6；P3，P7；P4，P8；
（2）把每组划分为整个循环。
表六
第一个循环 P1，P2；P3，P4；P5，P6；P7，P8
第二个循环 P1，P4；P2，P7；P3，P6；P5，P8
第三个循环 P1，P6；P2，P5；P3，P8；P4，P7
第四个循环 P2，P3；P4，P5；P6，P7；P8，P1
第五个循环 P1，P7；P2，P4；P3，P5；P6，P8
第六个循环 P3，P1；P2，P8；P5，P7；P4，P6
第七个循环 P1，P5；P2，P6；P3，P7；P4，P8；
（3）排序。
先排第一个循环有：P1，P2；P3，P4；P5，P6；P7，P8
在排第二个循环时有：从P1，P2，P3，P4所组成的组合中在第二个循环中有P1，P4；放在第二组的第一位；然后有P3，P5，P6所组成的组合中在第二组中有P3，P6；放在第二组的第二位；然后有P5，P7，P8所组成的组合中在第二组中有P7，P8；放在第二组的第三位；剩下一组，放在第四位。依次类推，排到第七个循环，可达到表三的结果。
当N=9时有排序：
表七
P1 P2 P3 P4 P5 P6 P7 P8 P9 每两场比赛相隔场次数
P1 \ 1 32 10 23 19 14 28 5 3，4，3，4，3，4，3
P2 1 \ 36 6 31 11 26 16 21 4，4，4，4，4，4，4
P3 32 36 \ 2 27 7 22 12 17 4，4，4，4，4，4，3
P4 10 6 2 \ 35 15 30 20 25 3，3，4，4，4，4，4
P5 23 31 27 35 \ 3 18 8 13 4，4，4，4，3，3，3
P6 19 11 7 15 3 \ 34 24 29 3，3，3，3，4，4，4
P7 14 26 22 30 18 34 \ 4 9 4，4，3，3，3，3，3
P8 28 16 12 20 8 24 4 \ 33 3，3，3，3，3，3，4
P9 5 21 17 25 13 29 9 33 \ 3，3，3，3，3，3，3
编制过程：
（1）分组：
表八
P1，P2
P1，P3 P2，P3
P1，P4 P2，P4 P3，P4
P1，P5 P2，P5 P3，P5 P4，P5
P1，P6 P2，P6 P3，P6 P4，P6 P5，P6
P1，P7 P2，P7 P3，P7 P4，P7 P5，P7 P6，P7
P1，P8 P2，P8 P3，P8 P4，P8 P5，P8 P6，P8 P7，P8
P1，P9 P2，P9 P3，P9 P4，P9 P5，P9 P6，P9 P7，P9 P8，P9
N=9，是奇数，要分四组。
表九
第一组 P1，P2；P2，P3；P3，P4；P4，P5；P5，P6；P6，P7；P7，P8；P8，P9；P9；P1
第二组 P1，P3；P2，P4；P3，P5；P4，P6；P5，P7；P6，P8；P7，P9；P1，P8；P2，P9
第三组 P1，P4；P2，P5；P3，P6；P4，P7；P5，P8；P6，P9；P1，P7；P2，P8；P3，P9
第四组 P1，P5；P2，P6；P3，P7；P4，P8；P5，P9；P4，P9；P3，P8；P2，P7；P1，P6
每组都是一个循环，这比N为偶数时少了一步。
所以有：
表十
第一个循环 P1，P2；P2，P3；P3，P4；P4，P5；P5，P6；P6，P7；P7，P8；P8，P9；P9；P1
第二个循环 P1，P3；P2，P4；P3，P5；P4，P6；P5，P7；P6，P8；P7，P9；P1，P8；P2，P9
第三个循环 P1，P4；P2，P5；P3，P6；P4，P7；P5，P8；P6，P9；P1，P7；P2，P8；P3，P9
第四个循环 P1，P5；P2，P6；P3，P7；P4，P8；P5，P9；P4，P9；P3，P8；P2，P7；P1，P6
（2）排序。
第一个循环可排为P1，P2； P3，P4； P5，P6； P7，P8； P9；P1；P2，P3；P4，P5；P6，P7；P8，P9。
在排第二个循环时考虑第一个循环中与第二个循环相隔为三场和四场的参赛队，并除去与它不相隔的那场比赛出现的队。在这里是P1，P2，P3。在这里取P1，P3；仿照N为偶数时的情况，依次类推，可排出如表七所示的结果。
4）除了两场比赛的场次间隔外，我们认为后打的队对先打的技术熟悉也是影响赛程公平的一个方面。在这方面我们所排出的赛程也是符合的非常好的。当为偶数个队时，不存在先打后打情况；当为奇数个队时有一个队在方面先占了一点优势（仅一场的优势），不过在后面的比赛中对这个队的那点优势作了调整。总的来说还是符合的很好的。
六 模型的评价及改进
在我们的模型中，首先，我们明确了上限的概念，给出了上限的表达式，并作了分析和证明。然后明确了最优赛程就是上限所在的赛程，两者的关系是等价的。我们首先定义了几个名词和定理，对最优赛程所具有的性质进行了分析和证明，然后很自然的给出了找最优赛程的方法，并给出了任意大小规模的单循环的赛程排序方法。很自然的解决了问题。
总的来说，我们成功的构造了模型，并且当队数很大时工作量也不大，在后面的事例中也可以说明我们的方法是行之有效的。虽然我们引如了若干个定理和定义，但是我们认为有的地方证明的还不够严谨，表述的不那么清晰。在最后的时间里，我们还想到了所有的最优赛程都是等价的，但是由于时间关系没能写进去。
[此贴子已经被HUASHI3483于2003-12-20 16:23:25编辑过]
|
|
发表于 2003-7-27 02:55:57