当前位置:文档之家› 足球比赛日程安排问题

足球比赛日程安排问题

数学建模论文题目:比赛日程安排问题学院:计算机科学与工程学院系别:计算机科学与技术班级:080402姓名:李真雄学号:20082365TEL :155****5725目录1.题目 (2)2.摘要 (2)3.问题重述 (2)2.模型建立 (3)2.1模型假设 (3)2.2符号设定 (4)2.3模型建立 (5)3.模型计算 (6)注:当n支球队比赛时,各队每两场比赛中间隔的场次数的上限为[(n-3)/2]。

(11)4.模型推广 (13)当n支球队比赛时,各队每两场比赛中间隔的场次数的上限为[(n-3)/2] (13)附录: (14)11.题目比赛日程安排2.摘要本文在合理假设的基础上,由问题的数学实质,建立出问题的线性规划模型;由问题的特殊性将n分为偶数与奇数分别研究,获得关于各队每两场比赛之间相隔天数上限的一般公式;运用归纳的方法发现了这种特殊排序中的对称规律,并由逆时针法编写出计算程序。

文中对赛程优劣的评价指标也作了较多的探讨。

(1)对于7支球队的比赛,给出了一个各队每两场比赛中间都至少相隔一场的赛程,利用图论知识可以得出一个简单可行的日程安排表。

(2)当n支球队比赛时,各队每两场比赛中间相隔的场次数的上限是[(n-3)/2],在达到以上上限的条件下,利用循环轮转模型编制了n=8和n=9的赛程。

(3)给出衡量一个赛程优劣的指标,如总间隔数、平均间隔数、间隔数方差等,并使这些指标达到最优!3.问题重述(1)7支球队进行单循环比赛,每天一场,给出一个比赛日2程,使每支球队在两场比赛之间至少间隔一天(要有安排赛日程的可操作的方法)。

(2)若有8支、9支球队,如何安排;能使每支球队在两场比赛之间至少间隔两天吗。

(3)推广到n支球队的情形,如何安排;每支球队在两场比赛之间可至少间隔多少天。

(4)你建议用哪些指标衡量比赛日程的优劣,如何使这些指标达到最优。

2.模型建立2.1模型假设1.基本假设:(1)设n支参赛队在同一场地上进行单循环赛;(2)假设赛程的公平性只与赛程安排有关,而与裁判等其它因素无关;(3)在假设(2)赛程的公平性就是指各队每两场比赛中间得到休整时间均等性,其中“每队每两场比赛”限定为指“每队每相邻两场比赛;32.在假设(1)下,即n个队同一场地进行循环赛共有M=2C场比赛,n有M=(2C)!种赛程安排,通常M是较大的数字。

M种赛程中各队比n赛间隔情况不同,因而对各队的比赛有影响。

题目中4个问题相互联系,基本的题是赛程安排公平性及其编排法;3.各队每两场比赛中间隔的场次数的上限,每个队都满足的间隔上限,其数学表达:d=max didi=minP i=1,2,3,….. 2n C!jktj,k,t=1,2,3,…n2.2符号设定表142.3模型建立建模思想[1]:d的数学实质是一个最大值,因此可用一个线性规划模型来描述。

具体考虑满足上限d要求的赛程编排法,则由于问题的特殊性,可将n分为偶数与奇数分别考虑;(1)当n=2k,我们建立一种称为‘循环规则”的赛程编制法,并得到d的公式,作出证明;(3)当n=2k+1,建立一种称为“移位规则”的赛程编制法,并得到d的公式,作出证明;两种证明的思路方法一样,都属于“构造证明法”。

最后将n为偶数与奇数的上限公式统一起来。

一般模型:d=max di56di=min jktP ⎪⎪⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎪⎪⎨⎧==≠≥∈+===--=∑∑==n t k j C i l m k j a a a N a C C a a a a a a st nml jk jk jk n j nk n n kj kk kjjk tk tj ...3,2,1,,...3,2,1),(1)1(01p .21122jkt 3.模型计算问题(1)的解n=7的编制过程:(1).移位规则,考虑一般n=2k+1,先建立一个2k(2k+1)矩阵称之为“生成矩阵”,由此矩阵即可生成赛程。

下面是此矩阵的生成规则:①将任一队(如2k+1队)先占第2k+1列的各行,余下各队占第一行的余下位置,不妨设1,2,…2k 队分别占第一行的1,2,…2k 列。

②将第一行前2k 个数按下述规则向下移动得第二行,依次类似得其余各行;将奇数行从第一行算起的第奇数个数右移1位到下一行; A. 将奇数行的第偶数个数左移1位到下一行;B.将偶数行的第奇数个数左移1位到下一行;C.将偶数行的第偶数个数右移1位到下一行;D.不能移动(指移出矩阵外)的数垂直下移到下一行,如此移动n-2次则生成矩阵,由生成矩阵从第一行a生起依次相邻两数表示一11场比赛。

此赛程满足各队每两场比赛中间相隔天数达到上限d=[(n-3)/2].由此可得结果。

(2)表4是用实际方法对n=7编制的赛程(首轮1队轮空,1队不动)。

其弊端是此赛程d=1,而按公式d=[(n-3)/2]=2。

说明各队每两场比赛中间极不均等,如有间隔6场,有间隔1场,具体到一个队(如5队比赛与休整时间极不均等)。

从比赛与休整的节奏,第一队最有利,第五队最不利,另外从各队总间隔场次数看,也有较大差异,说明实际赛程编制法有待改进。

而本模型算法提出的“生成规则”(见上文n为奇数编派法)既简便又公平。

表37(3).图论知识求解每个队的对手如下表示:A(B,C,D,E,F,G);B(A,C,D,E,F,G);C(A,B,D,E,F,G);D(A,B,C,E,F,G);E(A,B,C,D,F,G);F(A,B,C,D,E,G);G(A,B,C,D,E,F)通过图论知识:可以得到,当有7个队时,且每队每场比赛之间最多隔2天:表489问题(2)的解:n=8的编制过程:循环规则[2]八个队排成一个42矩阵,同一行两数表示这两队比赛(称为比赛矩阵),此矩阵表示第一轮比赛安排,如图1下面的安排中将某队(如1队)固定不移动,余下的队逆时针循环移动1位(上、下相邻两数的位置叫“1位”),得第二轮比赛安排,如图2⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡56784321⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡45673281 图1 图2按此规则移动6次,既得8队比赛28场的一个赛程,此赛程满足各队每两场比赛中间相隔场次数,达到上限d=[(8-3)/2]=2见表5。

表5一般n=2k,一个赛程有M=2C场比赛,按此规则需移动(n-2)次,n得满足d的赛程。

由“循环规则”编程得一上结果。

10综上可得适当的日程安排:表6注:当n支球队比赛时,各队每两场比赛中间隔的场次数的上限为[(n-3)/2]。

9支队伍也类似,具循环法则,得表:注:9支队伍是单数,其与8支队伍区别在于,它要先虚拟一个0队伍,以便于与循环轮转法则进行运算。

如: 1 2 3 4 5 1 0 2 3 4110 9 8 7 6 9 8 7 6 5其中,当队伍碰到0队时,说明当时比赛是没有的,而其他则正常进行比赛,0对只是一个虚拟队伍,用于循环轮转法的进行赛事安排。

问题(3)的解:证明:有n支队伍,对任意一支队伍k , 设其相邻的两场比赛为 k-i, k-j,中间间隔p场比赛。

现在即求p的上限值。

由于此两场比赛已有k , i , j 参加,为达到间隔上限,中间p场比赛中不能出现此三支队伍,即还剩下n-3支队伍,且此n-3支队伍在p场比赛中最多只能出现一次。

当n为奇数时,n-3为偶数,则p最多即为(n-3)/2场(此时(n-3)/2=[(n-3)/2])。

当n为偶数时,n-3为奇数,则有一队要轮空,即p最多则为(n-3-1)/2场(此时(n-3-1)/2=[(n-3)/2])。

综上所述,各队两场比赛中间隔的天数的上限为[(n-3)/2]。

所以,对于7支或8支球队,有如上适当安排,但不能使每支球队在两场比赛之间至少隔两天,应该是最多隔两天。

其证明见上详证!问题(4)的解:4.衡量一个赛程优劣,除各队每两场比赛间相隔天数上限d这个指12标外,各队在整个赛程中总间隔场天数e的差异程度E也是一个重要指标。

可设E=Emax-Emin,E越大说明各队总体休整间隔数的差异大。

E越大说明各队总体休整间隔天数的差异大。

这里n=8的赛程中差异度较小,表现出各队总体休整时间较为均匀,因而此赛程就指标而言,也较为公平的。

而且要考虑到比赛的间隔方差的大小,波动性。

应合理考察各队情况,合理安排各队比赛间隔天数,保证各队队员可充分发挥。

关于赛程的优劣,除考虑公平性外,还有效率性问题,即考虑如何合理紧凑地安排赛程,使赛程的时间较短。

[3]所以,要使以上指标达到最优,我们可以从以下方向入手:1.尽可能使得总体休息时间均匀,差异小;2.间隔方差尽可能小;2.观察各队情况后进行时间调配;3.尽量使日程安排公平,而且考虑效率,使得时间合理紧凑!4.模型推广当n支球队比赛时,各队每两场比赛中间隔的场次数的上限为[(n-3)/2]证明:有n支队伍,对任意一支队伍k ,设其相邻的两场比赛13为 k-i, k-j,中间间隔p场比赛。

现在即求p的上限值。

由于此两场比赛已有k , i ,j 参加,为达到间隔上限,中间p场比赛中不能出现此三支队伍,即还剩下n-3支队伍,且此n-3支队伍在p 场比赛中最多只能出现一次。

当n为奇数时,n-3为偶数,则p最多即为(n-3)/2场(此时(n-3)/2=[(n-3)/2])。

当n为偶数时,n-3为奇数,则有一队要轮空,即p最多则为(n-3-1)/2场(此时(n-3-1)/2=[(n-3)/2])。

综上所述,各队两场比赛中间隔的天数的上限为[(n-3)/2]。

附录:1.逆时针转换法[4][5]:#include <iostream>#include <vector>#include <algorithm>using namespace std;typedef std::vector<int> int_array;typedef std:: vector<std:: vector<int> > gap;void main(){14int team_count;//队伍总数std::cout<<"输入队伍总数: "<<std::endl;std::cin >> team_count;int virtual_team_count = team_count;//虚拟队伍数,保证是偶数if (virtual_team_count % 2 != 0)++virtual_team_count;int turn_count = virtual_team_count - 1;//比赛轮数int game_count_per_turn = virtual_team_count / 2;//每轮的比赛数int_array game_numbers(virtual_team_count);//所有的队伍号码 gap teamgap(team_count, vector<int>(0));for(int a = 1; a <= team_count; ++a)game_numbers[a - 1] = a;if (virtual_team_count != team_count)game_numbers[virtual_team_count - 1] = 0;//虚拟的队伍号码为0 int countsum=0,n,m;for (int i = 1; i <= turn_count; ++i) {std::cout<< "第"<< i << "轮:";for (int j = 1; j <= game_count_per_turn; j++) {if(game_numbers[j - 1]==0||game_numbers[virtual_team_count - j]==0)std::cout<<"无 ";else{15cout<< "<" << game_numbers[j - 1] << "," << game_numbers[virtual_team_count - j] << "> ";n = game_numbers[j - 1] - 1;m = game_numbers[virtual_team_count - j]-1 ;countsum++;teamgap[n].push_back(countsum);teamgap[m].push_back(countsum);}}std::cout << std::endl;std::rotate(game_numbers.begin() + 1, game_numbers.end() - 1, game_numbers.end());}for(int p = 0; p < team_count; p++ ){cout <<"第 "<<p+1<<" 支队伍的比赛场次为: ";for (vector<int>::iterator it = teamgap[p].begin();it!=teamgap[p].end();++it)cout<< *it << " ";cout<<endl;}for( p = 0; p < team_count; p++ ){cout <<"第 "<<p+1<<" 支队伍的休息天数依次为: ";for (vector<int>::iterator it = teamgap[p].begin();it!=teamgap[p].end()-1;++it)cout<< *(it+1) - *it - 1 << " ";16cout<<endl;}}程序运行结果截图:位规则考虑一般n=2k+1,先建立一个2k(2k+1)矩阵称之为“生成矩阵”,由此矩阵即可生成赛程。

相关主题