赛程安排 数学建模

题目 赛程安排

摘要

比赛一定要具有公平性，公平性又涉及到各个队出场的先后次序，对于对抗激

烈，消耗体力大的竞技比赛，比赛间的休整尤其重要，休整时间的长短对参赛队的竞技水平的发挥有大的影响。本文主要研究赛程安排问题，通过建立数学模型来研究。

对于问题一，题目要求对于5支球队的比赛，给出一个各队至少每两场比赛中间都至少相隔一场的赛程。通过分析这个题目，可以采用穷举法，即将可能出现的结果一一列举，但按照此方法会造成结果的遗漏。因此在解决本题过程中，在确定上限的前提下，然后采用计算机编制的方法将结果全部列出。其中的一种结果见下表（表1）。

对于问题二，首先是对问题的理解：竞赛排序的方法有多种，而每一种方法都有一个最小的各队两场比赛中间的间隔，在这里认为这个上限为所有排序方法中最小的各队每两场比赛间隔场次数目的最小值。然后用轮转法排出一个例子然后由一般到全部得出结论并对结论的存在性和最优性进行证明。

当n为偶数时可以直接利用轮转法并得到如下结论：

n结论1：当n?2k(k?2)时，各队每两场比赛间隔场次数的上限为m??2

2当n为技奇数时我们将假设有第n?1个队转化为偶数个队求解，得到如下结论：

?n?3,各个队伍每两场比赛比赛间隔上限为0??n?5,各个队伍每两场比赛比赛间隔上限为1?结论2：?n-1

n?2k?1,(k?3),各个队伍没两场比赛间隔上限为m?-2?2?对于问题三，在问题二解决的基础上，直接令n?8,n?9，代入问题二求解运用的方法便可得到它们的赛程安排。

对于问题四，首先题目要求，分析可能会影响赛程优劣的因素。通过分析发现平均相隔场次数也可以影响赛程的优劣。令cij为第i队第j个间隔场次数，

nn?21（i?1,2,....,n;j?1,2,3,......,n?2）。所以平均相隔场次数为t???cij，t越

n(n?2)ij大越好

关键词：轮转法 最优性 存在性

一、问题重述

1.1背景分析

众所周知在竞技比赛中公平性是至关重要的。公平性表现在很多方面，例如参赛队出场的先后次序，比赛的休整情况。对于对抗激励，消耗体力大的竞技比赛，比赛间的休整尤其重要，休整时间的长短对参赛队竞技水平的发挥有很大的影响，因此一个很好的赛程安排应该使每个队在比赛期间的修整时间尽可能均等。为此我们研究以下问题。[1] 1.2需要解决的问题

假设你所在的年级有5个班，每班一支球队在场地进行单循环比赛，共要进行10场比赛，如何安排赛程使各队来说都尽量公平？下面是随便安排的一个赛程：记5支球队为ABCD在下表左半部分的又上三角的10个小空格中，随手写上1,2,?10，就得到一个赛程，即第1场A对B，第2场B对C，?，第10场C对E，为方便起见将这些数据沿对角线对称地填入左下三角。

这个赛程的公平性如何呢，不妨只看看各队每两场比赛中间得到的休整是否均等。表的右半部分是各队每两场比赛间相隔的场次数，显然这个赛程对A,E有利，对D不公平。

A B C D E 每两场比赛间相隔场次数 A X 1 9 3 6 1, 2, 2 B C D E 1 9 3 6 X 2 5 8 2 X 7 10 5 7 X 4 8 10 4 X 0, 2, 2 4, 1, 0 0, 0, 1 1, 1, 1 从上面的例子出发讨论以下问题： 1）对于5支球队的比赛，给出一个各队每两场比赛中间都至少相隔场的赛程。 2）当n支球队比赛时，各队每两场比赛中间相隔的场次数的上限是多少。 3）在达到2）的条件下，给出n?8,n?9的赛程，并说明它们的编制过程。 4）除了每两场比赛间相隔次数这一指标外，你还能给出哪些指标来衡量一个赛程的优劣，并说明3）中给出的赛程达到这些指标的程度。

二、模型假设

1)假设每场比赛都能够正常进行即不存在意外情况； 2)假设每场比赛时间相同；

3)假设比赛而公平性只与赛程的安排有关，而与其他因素无关； 4)假设每一段比赛时间内各队实力基本稳定；

1

三、符号说明

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

m cij t f各队每两场比赛中间相隔的场次数上限 第i队第j个间隔场次数 各队每两场比赛中间平均相隔场次数 最大偏差 最小间隔场次数 比赛总场次数 三、问题分析

r N

2.1对于问题一的分析:

对于第一问题目要求对于5只球队的比赛，给出一个各队至少每两场比赛中间都至少相隔一场的赛程。在解决这个题目的过程中首先可能会想到穷举法，即逐一列举出来。这样做会造成结果不全面，会造成遗漏，而且非常复杂，给题目解决造成了很大的困难。因此对解决此题过程中，首先确定赛程安排的上下限，即上限为2场。然后采用计算机或者手工编制的方法来完成。 2.2对于问题二的分析:

对于要求求出n球队比赛是的上下限，竞赛排序的方法有多种，而每一种方法都有一个最小的各队两场比赛中间的间隔，在这里认为这个上限为所有排序方法中最小的各队每两场比赛间隔场次数目的最小值（对于本题中我们的求解是否满足我们对问题的理解在模型的检验中给出证明）。在解决这个问题时我们用轮转法来进行求解：在单循环赛中各队普遍出现一次，称为“一轮”。每两个队之间的比赛一次成

队数?（队数-1）为“一次”。在知道球队总数的情况下可以求出比赛的总场数：次数=，

2n?(n?1)当有n个队参加比赛时，比赛场次数为，轮换一次成为一轮。这时就要对n2n的奇偶性分两种情况进行讨论。当n为偶数时，一轮正好两两两对赛，需要打场

2n比赛。轮数j?n-1，每轮比赛中的场数?；当n为奇数时为了方便解决问题，假

2设存在一个虚拟的队伍第n?1个队参与到单循环赛中，进而将n为奇数的情形转化为n为偶数的情况罗列出赛程序列，然后将含有第n?1个队伍参加的比赛从赛程中

n-1除去进而对问题进行求解。轮数j?n，每轮比赛中比赛的场数?。

22.3对于问题三的分析:

2

基于问题二，在结果问题三的过程中，只需要令n?8,n?9，代入问题二求解运用的方法便可得到它们的赛程安排。 2.4对于问题四的分析:

对于问题四，题目要求除了每两场比赛间相隔次数这一指标外，再找出其他指标来衡量一个赛程的优劣，并说明3）中给出的赛程达到这些指标的程度。。首先题目要求，分析可能会影响赛程优劣的因素。通过分析发现平均相隔场次数也可以影响赛程的优劣。令cij为第i队第j个间隔场次数，（i?1,2,....,n;j?1,2,3,......,n?2）。

nn?21所以平均相隔场次数为t???cij，t越大越好即t越大，对赛程越有利。

n(n?2)ij五、 模型的建立与求解

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

对于第一问题目要求对于5只球队的比赛，给出一个各队至少每两场比赛中间都至少相隔一场的赛程。在解决这个题目的过程中首先可能会想到穷举法，即逐一列举出来。这样做会造成结果不全面，会造成遗漏，而且非常复杂，给题目解决造成了很大的困难。因此对解决此题过程中，首先确定赛程安排的上下限，即上限为2场。然后采用计算机或者手工编制的方法来完成。

利用Matlab求解得出满足要求的编制方法共有240种，见下表：

?5时每两场比赛间相隔的场次数表1：n ABCDEA B C D E 平均每两场比赛相间隔场次数 1,21, 2,2,2 1,1,1 2,1,1 1,2,2 X 10 8 5 3 10 X 4 7 8 4 X 2 6 5 7 2 X 9 369 其编制过程如下，不妨假设第一场，A对B，记为A?B。第二场比赛为C?D，在各队每两场比赛中间至少相隔一场的前提要求下，仅有E、、AB可以参加第三场比赛，即E，由于A、B已在第一场比赛过，故排除A-B，则仅剩?A、A?B、E?B下E-A,E-B两种可。不妨假设第三场比赛为E-A。以此类推，以后各场比赛程序安排为B?C,D?E,A?C,B?D,E?C,A?D,B?E因此球队之间进行的单循环赛，所以任何两队之间只能进行一场比赛。即对任何一队而言，曾经与其交战过的队在此后的比赛中不再相遇。

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

对第二个问题中各队每两场比赛中间相隔场次数的上限的理解：竞赛排序的方法有多种，而每一种方法都有一个最小的各队两场比赛中间的间隔，在这里认为这个上限为所有排序方法中最小的各队每两场比赛间隔场次数目的最小值（对于本题中我们的求解是否满足我们对问题的理解在模型的检验中给出证明。

3

在解决这个问题时我们用轮转法来进行求解：在单循环赛中各队普遍出现一次，称为“一轮”。每两个队之间的比赛一次成为“一次”。 （1）单循环赛场次数：

队数?（队数-1）次数=

2 （2）单循环轮数的计算：

n?(n?1)设有n个对参加比赛，由（1）的结果得知比赛场次数为，轮换一次成

2为一轮。因为轮数的确定要受到队伍数目n的影响，因此将问题转换为两种情况来解答：

n1、当n为偶数时，一轮正好两两两对赛，需要打场比赛。轮数j?n-1，每轮

2n比赛中的场数?

22、当n为奇数时为了方便解决问题，假设存在一个虚拟的队伍第n?1个队参与到单循环赛中，进而将n为奇数的情形转化为n为偶数的情况罗列出赛程序列，然后将含有第n?1个队伍参加的比赛从赛程中出去进而对问题进行求解。

n-1 轮数j?n，每轮比赛中比赛的场数?

2在解决第二问时，同样要根据n为奇数与偶数将问题分为两种情况来进行解答 1、当n为偶数的情形

按照轮转法的编排思路，我们对n?6进行分析。首先将“1”号固定在左上角不动，其它各号按大小顺序依次排序，依照这种方法排出以后各轮的全对阵情况，其竞赛次序如下表所示：

表2：n?6时竞赛的次序

第一轮 1?6 2?5 3?4 第二轮 1?5 6?4 2?3 第三轮 第四轮 1?3 第五轮 1?4 5?3 6?2 4?2 5?6 1?2 3?6 4?5 其中每个参赛队比赛期间的间隔分布如下：

表3：n?6时每两场比赛间相隔的场次数 参赛队 间隔分布 1 2,2,2,2 2 3,1,13 3 2,1,1,3 4 1,1,3,3 5 1,3,3,1 6 3,3,2,1 利用Matlab软件编程实现轮转法，从程序结果中得到100以内的偶数个队伍之间比赛时，各自的上限m，如下表所示：

4

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新幼儿教育赛程安排 数学建模 全文阅读和word下载服务。