赛程安排数学建模问题.doc

资源描述

赛程安排数学建模问题.doc

《赛程安排数学建模问题.doc》由会员分享，可在线阅读，更多相关《赛程安排数学建模问题.doc（14页珍藏版）》请在冰点文库上搜索。

赛程安排数学建模问题.doc

题目赛程安排

摘要

赛程安排在体育活动中举足轻重，在很大程度上影响比赛的结果；本文主要针对最优赛程安排方案建立相应的数学模型，给出最优赛程的安排方案。

对于问题一，要给出一个各队每两场比赛中间都至少相隔一场的赛。

因为参赛队伍只有5个，容易操作，所以可以利用排除-假设法可以得到一种满足条件的赛程安排，即。

对于问题二，考虑到各队每两场比赛中间至少相隔一场，我们用逆时针轮转法对比赛队伍进行排序，并根据这种方法，用编出相应编程得出不同队伍比赛间隔的上限，再根据数据总结出规律，当为偶数时各队每两场比赛中间相隔的场次数的上限为场，用软件验证其准确性。

用同样的方法可知，当为奇数时各队每两场比赛中间相隔的场次数的上限为。

对于问题三，在达到第二问上限的情况下，可通过轮换模型得到的赛程安排。

时一种赛程安排如下：

（1,2）,（3,5）,（4,6）,（8,7）,（1,3）,（4,2）,（8,5）,（7,6）,（1,4）,（8,3）,（7,2）,（6,5）,（1,8）,（7,4）,（6,3）,（5,2）,（1,7）,（6,8）,（5,4）,（2,3）,（1,6）,（5,7）,（2,8）,（3,4）,（1,5）,（2,6）,（3,7）,（4,8）

时一种赛程安排如下：

（1,2）,（3,4）,（5,6）,（7,8）,（1,9）,（2,4）,（3,6）,（5,8）,（7,9）,（1,4）,（2,6）,（3,8）,（5,9）,（1,7）,（4,6）,（8,2）,（9,3）,（5,7）,（1,6）,（4,8）,（2,9）,（3,7）,（1,5）,（6,8）,（4,9）,（2,7）,（3,5）,（1,8）,（6,9）,（4,7）,（2,5）,（1,3）,（8,9）,（6,7）,（4,5）,（2,3）.

对于问题四，我们可以用每个队的每两场比赛中间间隔的场次数之和来衡量赛程的公平性。

当不同时，大的队伍对其比赛结果越有利。

当相同时，用每次间隔场次的标准差来衡量赛程的公平性，其中标准差越小的队对其比赛的结果越有利。

当相同且每次间隔场次的标准差也相同时，两个队比赛时，我们用双方已参加比赛的次数来衡量比赛赛程的优劣，其中在双方比赛时，已参加比赛次数越少，其比赛的结果越有利。

关键词：

排除-假设法逆时针轮转法标准差

一、问题重述

1.1背景分析

当今社会，随着经济的增长和科学技术的发展，人们的生活水平不断的提高，体育竞赛也在日趋紧张的现代生活中被人们提到了越来越重要的位置。

北京奥运会的成功更加提升了体育在人们生活中的份量，体育活动在生活中起着举足轻重的作用。

而这些体育运动中，公平性又显得尤其重要。

特别是在对抗性强的单循环比赛中，赛程安排的不同，对比赛结果响很大。

本文主要着手于最优赛程安排方案，尽量给出赛程安排使得对每支球队来说都很公平。

1.2问题重述

假设你所在的年级有5个班，每班一支球队在同一块场地上进行单循环赛（所谓单循环赛是所有参加比赛的队均能相遇一次，最后按各队在全部比赛中的积分、得失分率排列名次）要进行10场比赛。

如何安排赛程使对各队来说都尽量公平呢？

下面是随便安排的一个赛程:

记5支球队为，在下表左半部分的右上三角的10个空格中,随手填上就得到一个赛程,即第场对,第场对,¼,第场对.为方便起见将这些数字沿对角线对称地填入左下三角。

这个赛程的公平性如何呢,不妨只看看各队每两场比赛中间得到的休整时间是否均等。

表的右半部分是各队每两场比赛间相隔的场次数,显然这个赛程对,有利,对则不公平。

表一

每两场比赛间相隔场数

从上面的例子出发讨论以下问题:

问题一：

对于支球队的比赛,给出一个各队每两场比赛中间都至少相隔一场的赛程。

问题二：

当支球队比赛时,各队每两场比赛中间相隔的场次数的上限是多少。

问题三：

在达到）的上限的条件下,给出的赛程,并说明它们的编制过程。

问题四：

除了每两场比赛间相隔场次数这一指标外,你还能给出哪些指标来衡量一个赛程的优劣,并说明）中给出的赛程达到这些指标的程度。

二、模型假设

结合本题实际，为确保模型求解的准确性和合理性，我们排除了一些因素的干扰，提出以下几点假设：

1、比赛期间，比赛不受任何外界因素影响。

2、每天比赛的时间段固定并且每场比赛时间相同。

3、任两球队在相同的休息时间里都能够得到同等程度的休息。

4、比赛在一天中指定的时间准时开始和结束并且严格按原赛程的规定执行，不存在因为其他原因造成的停赛的出现。

5、所建模型仅考虑开始比赛期间相邻两场比赛之间的休息时间队参赛队的影响，不考虑第一场比赛之前和最后一场比赛之后的休息时间对参赛队的影响。

三、符号说明

3.1符号说明

为了便于问题的求解，我们给出以下符号说明：

表示参赛队伍的数量

表示各队每两场比赛中间隔的场次数的上限

表示参赛队的轮数

表示相邻两场比赛的间隔场数

每个队的每两场比赛中间间隔的场次数的标准差

每个队的每两场比赛中间间隔的场次数之和

各队在全部赛程中间隔场次数

在全部赛程中间隔场数的总次数

3.2名词解释:

1、上限

上限为每两场比赛中间相隔的场次数的最小值。

2、单循环赛　

单循环赛是所有参加比赛的队均能相遇一次，最后按各队在全部比赛中的积分、得失分率排列名次。

3、排除—假设法

当某一变因素的存在形式限定在有限种可能（如某命题成立或不成立，如与大小：

有大于、小于和等于三种情况）时，假设该因素处于某种情况（如命题成立，如），并以此为条件进行推理。

四、问题分析

4.1对问题一的分析

对于问题一，假设这五支球队分别定义为队，那么这五支球队比赛的总场次数为10。

第一场出场队伍组合有种可能，要满足各队每两场比赛中间都至少相隔一场这个条件，所以第二场比赛共有种可能，以此类推共有种可能。

其中一种可能如下表二：

表二、五支队伍参赛赛程安排表

每两场比赛间相隔场次数

1,2,2

2,2,2

1,1,1

2,1,1

1,2,1

最后再用编程来验证此排除—假设法的准确性，发现结果相同即证明针对参赛队伍较少的情况此种方法简易可行。

4.2对问题二的分析

为了方便计算、便于表示，我们将参加比赛的球队由编号分别为字母A、B、C、D…分别用数字1、2、3、4、……等代替表示，固定第1队,按左边由上而下、右边由下而上（即逆时针转动）排成完整的两列。

再将比赛场地的顺序按轮转法排出，分别讨论。

根据这种逆时针轮转法，用编出相应软件得出不同队伍参赛时比赛间隔的上限，如当时，算出各队每两场比赛中间相隔的场次数的上限分别为1，2,3,4……，分析以上数据可以得到如下规律，当为偶数时，各队每两场比赛中间相隔的场次数的上限为场；最后再用软件验证得到这种逆时针轮转法的准确性。

用同样的方法可知，当为基数时各队每两场比赛中间相隔的场次数的上限为。

4.3对问题三的分析

在达到第二问上限的情况下，可通过轮换模型得到的赛程安排。

当时，把1固定在左上角不动，其余元素按逆时针轮转法轮换，一共轮换了次。

用编程得到一种赛程安排如下：

其中每一个数代表一个队，括号里表示每两个队进行比赛。

同样可以得到的一种赛程安排：

4.4对问题四的分析

先用用每个队的每两场比赛中间间隔的场次数之和来衡量赛程的公平性。

当不同时，大的队伍对其比赛结果越有利。

当相同时，用每次间隔场次的方差来衡量赛程的公平性，其中方差越小的队对其比赛的结果越有利。

当相同且每次间隔场次的方差也相同时，两个队比赛时，我们用双方已参加比赛的次数来衡量比赛赛程的优劣，其中在双方比赛时，已参加比赛次数越少的队，对其比赛的结果就越有利。

五、模型的建立与求解

5.1问题一的模型建立与求解

根据对实际问题的分析可知，进行单循环赛时各队每两场比赛中间得到的休整时间是否均等，对于球赛的输赢起着决定性的作用，问题一需要我们对于支球队的比赛，给出一个各队每两场比赛中间都至少相隔一场的赛程，因为队伍较少，所以利用排除-假设法可以得到一种理想的赛程安排。

假设这五支球队分别定义为队，5支球队进行单循环赛比赛的总场次数，则五支球队比赛的总场次数为。

五支球队进行比赛，因为五支球队没有明显的次序特征，所以第一场比赛出场队伍组合有种可能。

假设两支球队先进行比赛，要满足各队每两场比赛中间都至少相隔一场这个条件，因此第二场比赛只能从这三个球队中选择两支进行比赛，共有种选择，即。

假设第二场比赛队伍组合为，在之前条件约束下，仅有可以参加第三场比赛，即，可以设第三场比赛队伍组合为。

因为球队之间进行的是单循环赛，所以在任何两队之间只能进行一场比赛，对任何一队而言，曾经与其交战过的队，在以后的比赛中当不再相遇。

以此类推，以后各场比赛赛程安排可以为。

所以符合条件的比赛场数共有场。

如图一所示：

图一、五个队伍参赛赛程安排图

因为五个队伍比赛场次数较少可以将其转化成如下形式的赛程表三，可以直观清晰的看出每两场比赛相隔场次数的特点。

表三、五个队伍比赛间隔场次表

每两场比赛间相隔场次数

下面我们利用编程验证这种假设-排除法的准确性，编程能求出总的场次比赛情况，只要从中找出与上面对应的赛程安排就能证明此种方法准确。

下表四为软件求解出的相应结果，五个队伍参加五轮十场比赛满足要求的赛程安排：

表四、五个队伍参赛赛程安排

1-2

5-1

4-5

2-4

1-4

3-4

2-3

1-3

5-3

2-5

从表格可以看出，结果与假设-排除法得出的结果相同，证明针对参赛队伍较少的情况此种方法简易可行。

5.2问题二的模型建立与求解

考虑到各队每两场比赛中间都至少相隔一场时让赛程尽可能公平的情况下，求每两场比赛中间相隔的场次数的上限。

题目要求我们安排支球队的单循环赛程，并使赛程对各队来说尽量做到公平。

要想做到公平，其衡量的指标之一是：

考虑各队每两场比赛之间得到的休整时间是否均等、或是差距不大为此采用“逆时针轮转法”对此问题进行处理，首先我们将参加比赛的球队由编号分别为字母分别用数字等代替表示，然后固定第1队，按左边由上而下、右边由下而上（即逆时针转动）排成完整的两列。

为了确定比赛顺序，要先将比赛场次的顺序按轮转法排出。

仔细观察我们可以发现，奇数会出现轮空的情况，而偶数则不会出现轮空的现象，所以要将参赛队伍的数量根据奇偶性进行讨论（当N=<4时，各队的每两场比赛中间相隔的场次数的上限为0，在此不予讨论。

）：

（1）当为偶数时,各队每两场比赛之间相隔的场次数的上限分析如下：

当时，根据附录中的程序算出总共的比赛次数为15场，如下表所示：

表五、6个参赛队的单循环赛比赛场次顺序轮转表

第一轮

第二轮

第三轮

第四轮

第五轮

1----6

5----1

1----4

1----3

1----2

2----5

4----6

3----5

2----4

3----6

4----6

2----3

2----6

5----6

4----5

将其转化成如下形式的赛程表六，可以直观清晰的看出每两场比赛相隔场次数的特点。

表六、赛程与相隔场次数表

每两场比赛间隔场次数

由此表可得当=6时，各队每两场比赛中间相隔的场次数的上限为1。

由此我们通过编程得出当=8，10，……等偶数时重复当=6时的算法并计算他们的上限。

得出参赛对数与队每两场比赛中间相隔的场次数的上限的关系如下表七：

表七、当为偶数时的参赛队伍数与上限关系表

参赛对数

…

上限

…

因此，由上述图表可推测得出规律：

当N为偶数时，各队每两场比赛之间相隔的场次数的上限为：

场。

当时，经过编程得出各队每两场比赛中间相隔的场次数的上限为48，经由我们推导出来的公式计算得当时，各队每两场比赛中间相隔的场次数的上限也为48，由此便可验证公式的正确性。

（2）当N为奇数时各队每两场比赛之间相隔的场次数的上限分析如下：

当N=5时,根据附录中的程序算出总共的比赛次数为10场，如下表八所示：

表八、五个队伍参赛赛程安排表

第一轮

第二轮

第三轮

第四轮

第五轮

1-2

1-5

4-5

2-4

1-4

3-4

3-2

1-3

5-3

2-5

将其转化成如下形式的赛程表九，可以直观清晰的看出每两场比赛相隔场次数的特点。

表九、赛程与相隔场次数表

每两场比赛间相隔场次数

1,2,2

2,2,2

1,1,1

2,1,1

1,2,1

由此表可得当时，各队每两场比赛中间相隔的场次数的上限为1.由此我们通过编程得出当等奇数时重复当时的算法并计算他们的上限。

得出参赛对数与队每两场比赛中间相隔的场次数的上限的关系如下表十：

表十、当为奇数时的参赛队伍数与上限关系表

参赛对数

…

上限

…

因此，由上述图表可推测得出规律：

当为奇数时，各队每两场比赛之间相隔的场次数的上限为：

。

5.3问题三的模型建立与求解

在达到第二问上限的情况下，可通过轮换模型得到和的赛程安排。

当时，把1固定在左上角不动，其余元素按逆时针轮换法轮换，一共轮换了次。

根据附录中的的编程得到当时的具体轮换过程可见下表十一：

表十一、八个队伍参赛赛程表

第一轮

1--2

3--5

4--6

8--7

第二轮

1--3

4--2

8--5

7--6

第三轮

1--4

8--3

7--2

1--5

第四轮

1--8

7--4

6--3

5--2

第五轮

1--7

6--8

5--4

2--3

第六轮

1--6

5--7

2--8

3--4

第七轮

1--5

2--6

3--7

4—8

由上表可知，具体赛程安排如下：

时每两场比赛间隔相隔场次数如下表十二：

表十二、各队伍比赛相隔场次数表

队

相隔的场次数

相隔场次总数

3，3，3，3，3，3

4，4，4，3，2，2

2，4，4，4，3，2

2，2，4，4，4，3

4，4，3，2，2，2

4，3，2，2，2，4

3，2，2，2，4，4

2，2，2，4，4，4

当时,采用逆时针轮转法.将队号数为1的队伍位子固定不变且遇到偶数轮时在该轮中轮空,因要和上一轮轮空的队配成比赛,奇数轮中1则不能轮空.从奇数轮到偶数轮逆时针轮换。

由偶数轮到奇数轮时第一列不变,第二列向上移一个位置,使得第一组最后一组轮空.一共轮转次.

时的具体轮换过程可见下表十三（轮空位用0替代）

表十三、八个队伍参赛赛程表

第一轮

第二轮

第三轮

第四轮

第五轮

第六轮

第七轮

第八轮

1--2

1--0

1--4

1--0

1--6

1--0

1--8

1--0

3--4

2--4

2--6

4--6

4--8

6--8

6--9

8--9

5--6

3--6

3--8

2--8

2--9

4--9

4--7

6--7

7--8

5--8

5--9

3--9

3--7

2--7

2--5

4--5

9--0

7--9

7--0

5--7

5--0

3--5

3--0

2--3

根据逆时针轮转法，表中奇数轮末尾遇0轮空与相邻的偶数轮首位遇0轮空的两支队搭配比赛。

例如第三轮末尾第五场第七队轮空，第四轮首位第一场第一队轮空，则十四场比赛队伍组合为第七队和第一队。

由上表可知，具体赛程安排如下：

队每两场比赛间隔相隔场次数如下表十四：

表十四、各队伍比赛相隔场次数表

队

相隔的场次数

相隔场次总数

3434343

4444444

4444443

3344444

4444333

3333444

4433333

3333334

3333333

通过验证这两种模型都是满足条件的.并且这两种模型都可以扩充到N为任偶数或是奇数的情况.

5.4问题四的模型的建立与求解

前面三问都是在只考虑每两场比赛间相隔场次数这一指标下讨论赛程的公平性，即赛程安排都是以各队休整时间是否均等作为最优目标。

在这种情况下，只能做到尽可能的均衡，而不可能使各队的总的间隔时间场次数完全相等。

由此，我们想到可以用每个队的每两场比赛中间间隔的场次数之和来衡量赛程的公平性。

很显然，对于越大的队，他们休整时间比其他的队就长，对于他们的比赛结果就越有利。

当每个队的每两场比赛中间间隔的场次数之和相等时，我们可以根据每次间隔场次的波动程度来衡量赛程的优劣，在此我们引入另一个指标——标准差来衡量赛程的优劣。

由下面图二中的疲劳指数可知在休整时间相同的两个队参赛队比赛时，一个队的标准差越大时对此对越不利。

图二、运动员疲劳指数图

在实际比赛过程中还有一些客观的人为对已参加比赛队伍的比赛情况的分析，这一因素也会对比赛的结果产生影响。

所以当每个队的每两场比赛中间间隔的场次数之和和每次间隔场次的标准差相等时，我们可以比较两队在进行比赛时双方已参加比赛的次数来衡量这次比赛的优劣。

我们知道在这两个队进行比赛时，哪一方已经参加的次数越多，被对方所掌握的信息就越多，就越易被对方看出本队的优势与不足从而制定针对本队的方案。

这样便会对参赛多的一方产生不利的影响。

综合上述可得：

我们可以先利用SUM来衡量赛程安排的公平性，当各队的SUM不同时，大的队，对其比赛的结果就越有利。

当相同时，我们用每次间隔场次的方差来衡量赛程的公平性，其中标准差越小的队，对其比赛的结果就越有利。

当相同且每次间隔场次的标准差也相同时，两个队比赛时，我们用双方已参加比赛的次数来衡量比赛程的优劣，其中在双方比赛时，已参加比赛次数越少的队，对其比赛的结果就越有利。

当时，1到8队比赛时的相隔场次总数分别18,19,19,19,17,17,17,18根据我们定义的赛程标准，我们首先可以看出这场比赛对第二、第三、第四队的比赛结果比较有利。

在根据标准差可知这三队的标准差相等，所以不存在不公平因素。

最后我们看他们互相比赛时各队已参加比赛次数。

当第二队与第三队比赛时，双方均已参加四场比赛，所以不存在不公平因素；当第二队与第四队比赛时双方均已参加一场比赛，所以不存在不公平因素；当第三队与第四队比赛时双方均已参加五场比赛，所以不存在不公平因素。

由此可见此场比赛对第二、第三、第四队的比赛结果比较有利。

当时，1到9队比赛时的相隔场次总数分别24，28，27，26，25，24，23，22，21。

由此可知本次比赛对第二队有利。

六、模型的评价与改进

6.1模型的优点

1、赛程的编制能够推广到任意数的情况。

2、合理恰当的使用了表格和图形，使数据的体现和意思的表达更加清晰。

3、用排除-假设法可以得到一种理想的赛程安排。

4、用来检验结果是否准确，便于对结果的肯定。

5、逆时针轮转法可以使各队每两场比赛中间有至少相隔一场的情况下使赛程尽可能公平。

6、逆时针轮转法所建立的模型实际操作性强,方法简便,当参赛队数较多时，可以借助计算机实现赛程的编制。

7、逆时针轮转法使各轮比赛搭配合适，每轮比赛都有势均力敌的比赛，使各轮比赛都保持紧张氛围。

6.2模型的缺点

1、排除-假设法只适用于参赛队伍较少的情况下，不具有普遍性。

2、由于是单循环赛,所以在安排时不必考虑真实实力的差异,但在实际中往往不是单循环赛,这还有待进一步改进.

3、当N（7）为级数支球队时,未能证明所建立的赛程优劣指标下由“轮转法”所到的赛

展开阅读全文