《赛程安排数学模型(共15页).doc》由会员分享，可在线阅读，更多相关《赛程安排数学模型(共15页).doc（15页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上赛程安排数学模型徐龙(湖南科技学院数学与计算科学系 湖南 永州 )摘要: 本文对赛程安排问题进行了分析，构建了以“轮转法”为基础的数学模型，提供了如何编制赛程的方法利用“轮转法”所编制的赛程的间隔场次数上、下限及其相应的评价指标分别就球队数为偶数和奇数的情况进行了讨论最后证明了当球队数为偶数时，由“轮转法”所编制的赛程是最优的关键词: 数学模型；赛程安排；轮转法；赛场间隔 The Mathematical Model of Competition Schedule ArrangementXu Long (Department of Mathematics and Co
2、mputational Science，Hunan University ofScience and Engineering，Yongzhou，Hunan）Abstract: This article has carried on the analysis to the question of competition schedule arrangement and has constructed the mathematical model of “the law of rotates” . Moreover ,it also provided the method to establish
3、 the competition schedule. It also discussed about the situation respectively when the team number is even or odd through the upper limit and lower limit of the number of competition schedule that is established by the “the law of rotates” and the corresponding appraisal target. Finally, it proved t
4、hat the competition scheme is most superior established by “the law of rotates” when the team number is odd.Key word: mathematical model; competition schedule arrangement; the law of rotates; gap1 引言运动会作为一种体育赛事应重视它的公平性，运动会的赛制包括：循环赛、排位赛和淘汰赛本文主要考虑循环赛中各队赛程的间隔时间单循环球类比赛适用于参赛队比较少的公平竞赛，通常采用的是“轮转法”等手工编排，在编排
5、过程中可综合考虑其它比赛因素本题解决的是单场地单循环的竞赛赛程安排，单循环是指所有参赛队在竞赛中均能相遇一次，最后按各队在竞赛中的得分多少、胜负场次来排列名次。 单循环一般在参赛队不太多，又有足够的竞赛时间才能采用。单循环由于参加竞赛的各队都有相遇比赛的机会， 是一种比较公平合理的比赛制度。 体现这种比赛公平性的最大因素是某队每两场比赛的间隔场次数单循环的竞赛场数公式为:；2 模型2.1 问题的提出为简单起见设某运动会的某项目有5个代表队, 首先我们考虑所有的代表队在同一场地上进行单循环赛, 共要进行10 场比赛, 那么如何安排赛程才公平呢? 下面是随意安排的一个赛程, 记5个代表队为在下表左
6、半部分的右上三角的10个空格中, 随手填上1, 2,. . . , 10, 就得到一个赛程即第一场对, 第二场 对,. . . , 第十场对为方便起见, 将这些数字沿着对角线对称地填入左下角这个赛程的公平性如何呢？不妨看看各代表队每两场比赛中间得到的休整时间是否均等, 表的右半部分是各队每两场比赛间相隔的场次数, 显然这个赛程对，有利, 对则不公平.每两场比赛间相隔场次数X19361221X25802292X710410357X400168104X111表从上面的例子出发引发了我们对以下问题的讨论:问题(1):对于5代表队的比赛, 给出一个各队每两场比赛中间都至少相隔一场的赛程问题(2):当有
7、N个代表队比赛时, 各队每两场比赛中间相隔的场次数的上限是多少?在达到(2) 的上限的条件下, 给出N = 8,N = 9,N=n()的赛程2.2 模型假设（1）假设在赛程安排中, 各队的地位都是平等的，任何一个队都没有优先权（2）假设比赛是连续的, 不间断, 不受场地, 天气等因素的影响（3）假设在比赛中任何一个队都不得弃权, 不能因队员受伤或意外事故影响赛程（4）假设每天进行一场比赛2.3 符号的说明:第k支球队：球队和进行的比赛：第k支球队在第i轮的位号g()：第i轮中位于号位上的球队h()：第i轮中位于号位上的球队所进行的比赛在全赛程中的场次dmax：全赛程的间隔场次数上限dmin：全
8、赛程的间隔场次数下限V(dmax,dmin) ：全赛程的间隔场次数上限与下限之差2.4 模型的建立和求解2.4.1 对于问题（1）的求解对5支球队的比赛,给出一个各队每两场比赛中间都至少相隔一场的赛程，其上限为2每两场比赛间相隔场次数X24681112X79521147X110222691X312285103X121表2.4.2对于问题（2）的求解（一）当参赛球队数为偶数时赛程的编制步骤1将所要进行的场比赛平均分为N-1轮，每轮为场比赛,并且要求每支球队在该轮比赛中有且仅有一场比赛步骤2在第一轮中将位号1,2,N和球队按左边由上而下，右边由下而上(逆时针方向)排成完整的两列，并记录轮场次和总场
9、次如下:位号第1轮位号轮场次总场次1N112N-1223N-233iN-i+1ii+1表3步骤3由第1轮的位号和比赛场次的安排用以下方法生成第2轮的位号和比赛场次的安排将固定N在号位不变, , 均按逆时针方向依次转移一个位置，由原来的N-1号位转移到1号位如下表：位号第1轮位号轮场次总场次1N112N-1223N-233iN-i+1ii+1表4重复步骤3的过程,由第2轮的赛程生成第3轮的赛程，依次类推，由第i轮的赛程生成第i+1轮的赛程步骤4由上述步骤1、2、3可依次得出第1,2,N-1轮的场次安排,然后按总场次的顺序排列即可得到一个完整的赛程表我们将由上面4个步骤所得到的赛程编制方法称为“轮
10、转法”下面给出有 N = 8 支球队参赛 ,由上述“轮转法”所生成的赛程表：每两场比赛间相隔场次数x17261123620144432217x12227192254432222612X8183152143222411228x4142717432244237184x28101322244461931428x24922444320215271024x524443212521171395x333333表5计算间隔场次数的上、下限对上述给出的“轮转法”所得的赛程给出如下结论：结论1各队在每一轮中有且仅有一场比赛，因此该球队在第i轮的比赛即是该队的第i场比赛结论2各队的第i场比赛在全赛程的总场次=赛程的
11、前(i-1)轮所需比赛的场数+该队第i场比赛在该轮(即第i轮)中的轮场次结论3各队的第i场与第i+1场比赛的间隔数=该队的第(i+1)场比赛在全赛程的总场次该队的第i场比赛在全赛程的总场次1结论4当参赛队数N( 6)为偶数时，由上述轮转法所编制的赛程球队前后两场比赛间隔数的上限为，下限为-2下面给出结论4的证明：构造如下的位置转移函数，用于刻划第k支球队由第i轮的号位转移到第i+1轮的号位（）其中 i=1,2,N-2；显然(1)所定义的位置转移函数是定义在从位号集到自身上的一个1-1对应由结论1可知，在第i轮中位于号位上的球队所进行的比赛在该轮中的场次为：（）（2）式子所定义的函数称为轮场次函
12、数,用于记录球队在第i轮位于号位上的比赛在该轮中的场次由结论2可知,在第i轮中位于号位上的球队所进行的比赛在全赛程中的场次为：（）（3）式子所定义的函数称为全程场次函数，用于记录球队在第i轮位于号位上的比赛在全赛程中的场次由结论3得球队在i轮中所进行的i场与在i+1轮中所进行的第i+1场比赛之间的间隔数为：（）（4）式子所定义的函数称为间隔场次函数，用于刻划球队所进行的第i场与第i+1场比赛之间的间隔数因此,从间隔场次函数我们得到结论4是正确的对于参赛队数N为偶数的情形,由上述“轮转法”可以得到一个可行的编制方案(满足各队每两场比赛都至少间隔一场)(二) 当参赛球队数N(7)为奇数时记这N支球
13、队为,可以虚拟一个参赛队，记为：,使之成为N+1(偶数)支球队,然后按照队数为偶数的情形进行讨论具体步骤如下：步骤1 将所要进行的场比赛平均分为(N+1)-1轮，每轮为场比赛(其中有1场是虚拟赛)，并且要求每支球队在该轮比赛中有且仅有一场比赛 步骤2 在第一轮中将位号1,2,N+1和球队,按左边由上而下,右边由下而上(逆时针方向)排成完整的两列,并记录轮场次和总场次如下：位号第1轮位号轮场次1N+112N23N-13表6步骤3由第1轮的位号和比赛场次的安排用以下方法生成第2轮的位号和比赛场次的安排将固定在N+1号位不变, 均按逆时针方向依次转移一个位置，由原来的N号位转移到1号位如下表：位号第
14、2轮位号轮场次1N+112N23N-13表7重复步骤3，可依次得出第1,2,N轮的赛程,然后将含有的虚拟赛剔除，按顺序即可排出满足要求(满足各队每两场比赛都至少间隔一场)的一个赛程下面给出用上述“轮转法”所编制的 N=9 支球队的一个赛程：每两场比赛间相隔场次数X16301127624133444722216X12267232202944332223012X8223193425436224311268X4183515213232248277224X36143117262443462331836X321013232348324219351432X28964443321203415311028X5
15、344472233292521171395X3333333表8由上述编制过程,可以得出如下结论：结论8 当参赛队数N(7)为奇数时，由上述“轮转法”所编制的赛程球队前后两场比赛间隔数的上限为N-1，下限为对结论8我们作如下解释:设在第k轮中与虚拟球队比赛的球队是 (即是轮空的)，那么球队在第k-1轮的轮场次到第k+1轮的轮场次之间的最大间隔为:dmax=(N+12+1)-2+(N+12-1)=N-1，且dmax=N-1就是该赛程的最大间隔场次数用同样的方法考察第k-1轮和第k轮中球队没有出现轮空的间隔场次数,可以得到球队的间隔场次数下限dmin=,且dmin=就是该赛程的最小间隔场次数结论9
16、单数队在5个队以上时倒数的第二数字队则在第四轮开始每轮均同上轮轮空队进行比赛,如上述代表队由此产生了球类比赛中的不公平竞争现象。为了解决结论9这一问题,目前的比赛大多采用“贝格尔轮转法” ，其优点是单数队参加时可避免第二轮的轮空队从第四轮起每场都与前一轮的轮空队比赛的不合理现象贝格尔轮转法：贝格尔轮转法是国际上采用的一种编排方法。表(9)为7个队参赛轮次表。其轮转方法是：（1）最大号数（尾数或0）左右摆，右下号数提上来，先摆后转，按逆时针方向转移。（2）也可根据参赛队数的多少来确定轮转位置的数目。即3或4个队，依次轮转一个位置，5或6个队，依次轮转两个位置，7或8个队，依次轮转三个位置等，每增
17、加两个队，则增加一个轮转位置. 第一轮 第二轮 第三轮 第四轮 第五轮 第六轮 第七轮 表9无论比赛队是单数还是双数，最后一轮时，必定是“0”或最大的一个代号在右上角，“1”在右下角.根据参赛队的个数不同，“1”朝逆时针方向移动一个位置时，应按规定的间隔数移动（见表10），“0”或最大代号数应先于“1”移动位置。 间隔移动参赛队数间隔移动数4队以下056队178队2910队31112队4“1”进行间隔移动时，凡遇到“0”或最大代号数时应先越过，不作间隔计算.综合（一）和（二），可以借助计算机实现赛程的编制赛程安排表2. 模型的优化性探讨下面说明利用轮转法所编制的赛程是最优化的利用整个赛程方差，
18、第i队场次间隔的方差和整个赛程安排场次间隔的，来评价赛的优劣，显然当越小的时候间隔场次数越集中，整个赛程方差和第i队场次间隔的方差就越小，整个赛程的间隔场次数就越大，赛程的公平性就越好，反之则越差下面说明任何一个有偶数支球队的单循环赛赛程用“轮转法”所编制的赛程是最优的假设有另外一个参赛球队数相同的赛程用“轮转法”所编制的赛程更优，则将所要进行的场比赛按照赛程比赛的次序平均分为 N - 1轮，每轮场 则一定存在某队，其间隔场次数至多为，从而有如下结论：结论5 任何一个有 N 支球队的单循环赛赛程的间隔场次数下限为其中 由结论 5 ,可以进而得出以下结论：结论 6 任何一个有 N（）支球队的单循
19、环赛赛程的间隔场次数不可能出现如下关系：假设有某 N 支球队的单循环赛赛程的间隔场数上、下限均为，即：dmax = dmin =，则球队的前后两场的间隔数都是，这样将会出现两个队在每一轮的比赛中都相遇，这种赛程是不符合竞赛规则的 ，从而结论 6 是成立的结论 6说明了这样的理想赛程()是不存在的下面通过调整“理想赛程”的间隔场次数的上、下限，可得出符合实际的赛程.显然，当间隔场次数的上限增大时，必然使得间隔场次数的下限减少因为某个队的间隔场次数的增大这种利益是通过牺牲其他球队的利益（间隔场次数的减少）来获取的因此由这些变化关系和结论 6 可以知道若理想赛程的间隔场次数上限dmax 由增加1达到
20、时，下限dmin必定会减少，即有：，从而得到如下的结论7：结论 7 任何一个有偶数支球队的单循环赛赛程用“轮转法”所编制的赛程是最优的2. 模型评价与改进上述采用“轮转法”所建立的模型实际操作性强 ,方法简便 ,当参赛队数较多时，可以借助计算机实现赛程的编制这一模型在实际生活中有较强的推广性和实用性改进方向:（1）由于假设每天只赛一场, 所以使问题得到了简化, 如果一天赛两场, 那么这样的赛程难度将会加大, 还需进一步改进（2）由于是单循环赛, 所以在安排时不必考虑真实实力的差异, 但在实际中往往不是单循环赛, 这还有待进一步改进.（3）当N（7）为级数支球队时, 未能证明所建立的赛程优劣指标
21、下由“轮转法”所到的赛程是最优的因此应对奇数的情况进一步论证赛程的最优性或者找出其他更能兼顾各队平性的编制赛程的方法结束语本文对赛程安排问题进行了分析，构建了“轮转法”的数学模型, 提供了如何编制赛程的方法利用“轮转法”所编制的赛程的间隔场次数上、下限及其相应的评价指标分别就球队数为偶数和奇数的情况进行了讨论最后证明了当球队数为偶数时，由“轮转法”所编制的赛程是最优的.参考文献1 王向东数学实验M北京：高等教育出版社(第一版)，2004：5-10. 2 边馥萍，侯文华，梁冯珍数学模型方法与算法M北京：高等教育出版(第一版)，2005：42-533 茆诗松，程依明，濮晓龙.概率论与数理统计教程M
22、.北京:高等教育出版(第一版),2004：71-1094 动竞赛方法研究M.北京:人民体育出版社,2001：99-1085 育素养导论M.北京:科学出版社,2000：58-636 淑清.FORTRAN语言M.北京:清华大学出版社,2001：200-2567 Rbability，Random variables and stochastic processes AM.Papoulis,McGraw-Hill books Co，1965：136-162.8 Richard F.Bass，A Brief troduction to measure theory and integrationMSpr
23、inger Verleg，New York Inc，1998：195-206.致谢本文从命题到完成都得到了指导老师周立平老师的大力帮助在此，感谢周立平老师的悉心指导。同时也感谢唐琴同学的帮助附录该程序为N=5时的轮转法赛程编制程序，实际上可完成个球队的赛程编制任务，JAVA 程序如下 public class Team public static void main(String args) String team = 1,2,3,4,5,0;/参赛的各队 int len = team.length; for(int i=1;i len;i+) System.out.println(); System.out.println(第+i+ 轮); for(int j=0;j0;k-) teamk=teamk-1; team1=temp; /将临时变量temp赋给数组的第二值 运行结果：C:javajava Team第1 轮 1 - 02 - 53 - 4第2 轮1 - 50 - 42 - 3第3 轮1 - 45 - 30 - 2第4 轮1 - 34 - 25 - 0第5 轮1 - 23 - 04 - 5专心-专注-专业