足球比赛日程安排问题.docx
《足球比赛日程安排问题.docx》由会员分享，可在线阅读，更多相关《足球比赛日程安排问题.docx（15页珍藏版）》请在冰点文库上搜索。
足球比赛日程安排问题
数学建模论文
题目：
比赛日程安排问题
学院：
计算机科学与工程学院
系别：
计算机科学与技术
班级：
080402
姓名：
李真雄
学号：
20082365
TEL：
155****5725
目录
1．题目1
2．摘要1
3.问题重述1
2．模型建立2
2.1模型假设2
2.2符号设定3
2.3模型建立4
3．模型计算5
注：
当n支球队比赛时，各队每两场比赛中间隔的场次数的上限为[（n-3）/2]。
10
4．模型推广12
当n支球队比赛时，各队每两场比赛中间隔的场次数的上限为[（n-3）/2]12
附录:
13
1．题目
比赛日程安排
2．摘要
本文在合理假设的基础上，由问题的数学实质，建立出问题的线性规划模型；由问题的特殊性将n分为偶数与奇数分别研究，获得关于各队每两场比赛之间相隔天数上限的一般公式；运用归纳的方法发现了这种特殊排序中的对称规律，并由逆时针法编写出计算程序。
文中对赛程优劣的评价指标也作了较多的探讨。
（1）对于7支球队的比赛，给出了一个各队每两场比赛中间都至少相隔一场的赛程，利用图论知识可以得出一个简单可行的日程安排表。
（2）当n支球队比赛时，各队每两场比赛中间相隔的场次数的上限是[（n-3）/2]，在达到以上上限的条件下，利用循环轮转模型编制了n=8和n=9的赛程。
（3）给出衡量一个赛程优劣的指标，如总间隔数、平均间隔数、间隔数方差等，并使这些指标达到最优！
3.问题重述
（1）7支球队进行单循环比赛，每天一场，给出一个比赛日程，使每支球队在两场比赛之间至少间隔一天（要有安排赛日程的可操作的方法）。
（2）若有8支、9支球队，如何安排；能使每支球队在两场比赛之间至少间隔两天吗。
（3）推广到n支球队的情形，如何安排；每支球队在两场比赛之间可至少间隔多少天。
（4）你建议用哪些指标衡量比赛日程的优劣，如何使这些指标达到最优。
2．模型建立
2.1模型假设
1.基本假设：
（1）设n支参赛队在同一场地上进行单循环赛；
（2）假设赛程的公平性只与赛程安排有关，而与裁判等其它因素无关；
（3）在假设
（2）赛程的公平性就是指各队每两场比赛中间得到休整时间均等性，其中“每队每两场比赛”限定为指“每队每相邻两场比赛；
2.在假设
（1）下，即n个队同一场地进行循环赛共有M=
场比赛，有M=（
）！
种赛程安排，通常M是较大的数字。
M种赛程中各队比赛间隔情况不同，因而对各队的比赛有影响。
题目中4个问题相互联系，基本的题是赛程安排公平性及其编排法；
3.各队每两场比赛中间隔的场次数的上限,每个队都满足的间隔上限，其数学表达：
d=maxdi
di=min
i=1,2,3,…..
!
j,k,t=1,2,3,…n
2.2符号设定
表1
n
参赛队数
N
比赛场数
M
赛程总共安排数
j队与k队比赛场次序号数
t队与j队及k队两场比赛间最小相隔天数
i-j
第i队与第j队比赛
e
各队在全部赛程中间隔天数
d
各队每两场比赛中间相隔天数的上限
di
第i赛程各队每两场比赛间相隔最小天数
2.3模型建立
建模思想[1]：
d的数学实质是一个最大值，因此可用一个线性规划模型来描述。
具体考虑满足上限d要求的赛程编排法，则由于问题的特殊性，可将n分为偶数与奇数分别考虑；
（1）当n=2k,我们建立一种称为‘循环规则”的赛程编制法,并得到d的公式，作出证明；（3）当n=2k+1，建立一种称为“移位规则”的赛程编制法,并得到d的公式，作出证明；两种证明的思路方法一样，都属于“构造证明法”。
最后将n为偶数与奇数的上限公式统一起来。
一般模型：
d=maxdi
di=min
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次则生成矩阵，由生成矩阵从第一行
生起依次相邻两数表示一场比赛。
此赛程满足各队每两场比赛中间相隔天数达到上限d=[（n-3）/2].由此可得结果。
（2）表4是用实际方法对n=7编制的赛程（首轮1队轮空，1队不动）。
其弊端是此赛程d=1，而按公式d=[（n-3）/2]=2。
说明各队每两场比赛中间极不均等，如有间隔6场，有间隔1场，具体到一个队（如5队比赛与休整时间极不均等）。
从比赛与休整的节奏，第一队最有利，第五队最不利，另外从各队总间隔场次数看，也有较大差异，说明实际赛程编制法有待改进。
而本模型算法提出的“生成规则”（见上文n为奇数编派法）既简便又公平。
表3
1
2
3
4
5
6
7
每两场比赛间相隔场次数
总间隔场次数
1
X
19
16
13
10
7
4
2，2，2，2，2
10
2
19
X
9
17
5
15
1
3，3，5，1，1
13
3
16
9
X
6
14
2
12
3，2，2，1，1
9
4
13
17
6
X
3
11
20
2，4，1，3，2
12
5
10
5
14
3
X
21
8
1，2，1，3，6
13
6
7
15
2
11
21
X
18
4，3，3，2，2
14
7
4
1
12
20
8
18
X
2，3，3，5，1
14
（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天：
表4
B-G
C-F
D-E
A-G
B-E
C-D
A-F
G-E
B-C
A-E
F-D
G-C
F-B
A-C
B-D
F-G
A-B
D-G
E-F
A-D
E-C
问题
（2）的解：
n=8的编制过程：
循环规则[2]
八个队排成一个42矩阵，同一行两数表示这两队比赛（称为比赛矩阵），此矩阵表示第一轮比赛安排，如图1下面的安排中将某队（如1队）固定不移动，余下的队逆时针循环移动1位（上、下相邻两数的位置叫“1位”），得第二轮比赛安排，如图2
图1图2
按此规则移动6次，既得8队比赛28场的一个赛程，此赛程满足各队每两场比赛中间相隔场次数，达到上限d=[（8-3）/2]=2见表5。
表5
1
2
3
4
5
6
7
8
比赛相隔场次数
总场次数
1
X
1
25
5
21
9
17
13
3，3，3，3，3，3
18
2
1
X
16
20
26
6
11
23
4，4，4，3，2，2
19
3
25
16
X
2
12
19
22
7
4，4，3，2，2，2
17
4
5
20
2
X
15
24
27
10
2，4，4，4，3，2
19
5
21
26
12
15
X
3
8
18
4，3，2，2，2，4
17
6
9
6
19
24
3
X
14
28
2，2，4，4，4，3
19
7
17
11
22
27
8
14
X
4
3，2，2，2，4，4
17
8
13
23
7
10
18
28
4
X
2，2，2，4，4，4
18
一般n=2k，一个赛程有M=
场比赛，按此规则需移动（n-2）次，得满足d的赛程。
由“循环规则”编程得一上结果。
综上可得适当的日程安排：
表6
1-8
2-7
3-6
4-5
1-7
8-6
2-5
3-4
1-6
7-5
8-4
2-3
1-5
6-4
7-3
8-2
1-4
5-3
6-2
7-8
1-3
4-2
5-8
6-7
1-2
3-8
4-7
5-6
注：
当n支球队比赛时，各队每两场比赛中间隔的场次数的上限为[（n-3）/2]。
9支队伍也类似,具循环法则，得表：
1
2
3
4
5
6
7
8
9
1
33
29
25
21
17
13
9
5
2
33
16
30
11
27
6
24
1
3
29
16
12
26
7
23
2
20
4
25
30
12
8
22
3
19
34
5
21
11
26
8
4
18
35
15
6
17
27
7
22
4
36
14
31
7
13
6
23
3
18
36
32
10
8
9
24
2
19
35
14
32
28
9
5
1
20
34
15
31
10
28
注：
9支队伍是单数，其与8支队伍区别在于，它要先虚拟一个0队伍，以便于与循环轮转法则进行运算。
如：
1234510234
0987698765
其中，当队伍碰到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这个指标外，各队在整个赛程中总间隔场天数e的差异程度E也是一个重要指标。
可设E=Emax-Emin，E越大说明各队总体休整间隔数的差异大。
E越大说明各队总体休整间隔天数的差异大。
这里n=8的赛程中差异度较小，表现出各队总体休整时间较为均匀，因而此赛程就指标而言，也较为公平的。
而且要考虑到比赛的间隔方差的大小，波动性。
应合理考察各队情况，合理安排各队比赛间隔天数，保证各队队员可充分发挥。
关于赛程的优劣，除考虑公平性外，还有效率性问题，即考虑如何合理紧凑地安排赛程，使赛程的时间较短。
[3]
所以，要使以上指标达到最优，我们可以从以下方向入手：
1.尽可能使得总体休息时间均匀，差异小；
2．间隔方差尽可能小；
2.观察各队情况后进行时间调配；
3.尽量使日程安排公平，而且考虑效率，使得时间合理紧凑！
4．模型推广
当n支球队比赛时，各队每两场比赛中间隔的场次数的上限为[（n-3）/2]
证明：
有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]。
附录:
1.逆时针转换法[4][5]：
#include
#include
#include
usingnamespacestd;
typedefstd:
:
vectorint_array;
typedefstd:
:
vector:
vector>gap;
voidmain（）{
intteam_count;//队伍总数
std:
:
cout<<"输入队伍总数：
"<:
endl;
std:
:
cin>>team_count;
intvirtual_team_count=team_count;//虚拟队伍数，保证是偶数
if（virtual_team_count%2!
=0）
++virtual_team_count;
intturn_count=virtual_team_count-1;//比赛轮数
intgame_count_per_turn=virtual_team_count/2;//每轮的比赛数
int_arraygame_numbers（virtual_team_count）;//所有的队伍号码
gapteamgap（team_count,vector（0））;
for（inta=1;a<=team_count;++a）
game_numbers[a-1]=a;
if（virtual_team_count!
=team_count）
game_numbers[virtual_team_count-1]=0;//虚拟的队伍号码为0
intcountsum=0,n,m;
for（inti=1;i<=turn_count;++i）{
std:
:
cout<<"第"<";
for（intj=1;j<=game_count_per_turn;j++）{
if（game_numbers[j-1]==0||game_numbers[virtual_team_count-j]==0）
std:
:
cout<<"无";
else{
cout<<"<"<";
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<:
endl;
std:
:
rotate（game_numbers.begin（）+1,game_numbers.end（）-1,game_numbers.end（））;
}
for（intp=0;pcout<<"第"<";
for（vector:
:
iteratorit=teamgap[p].begin（）;it!
=teamgap[p].end（）;++it）
cout<<*it<<"";
cout<}
for（p=0;pcout<<"第"<";
for（vector:
:
iteratorit=teamgap[p].begin（）;it!
=teamgap[p].end（）-1;++it）
cout<<*（it+1）-*it-1<<"";
cout<}
}
程序运行结果截图：
位规则考虑一般n=2k+1，先建立一个2k（2k+1）矩阵称之为“生成矩阵”，由此矩阵即可生成赛程。
下面是此矩阵的生成规则：
将任一队（如2k+1队）先占第2k+1列的各行，余下各队占第一行的余下位置，不妨设1，2，…2k队分别占第一行的1，2，…2k列。
（1）将第一行前2k个数按下述规则向下移动得第二行，依次类似得其余各行；
A.将奇数行从第一行算起的第奇数个数右移1位到下一行；
B.将奇数行的第偶数个数左移1位到下一行；
C.将偶数行的第奇数个数左移1位到下一行；
D．将偶数行的第偶数个数右移1位到下一行；
E．不能移动（指移出矩阵外）的数垂直下移到下一行，如此移动n-2次则生成矩阵，由生成矩阵从第一行
生起依次相邻两数表示一场比赛。
此赛程满足各队每两场比赛中间相隔场次数达到上限d=[（n-3）/2].由此可得结果。
3.间隔上限数学表达：
d=maxdidi=min
i=1,2,3,…..
!
j,k,t=1,2,3,…n
参考文献
升级会员 