赛程安排数学建模.doc

题目 赛程安排摘要 比赛一定要具有公平性，公平性又涉及到各个队出场的先后次序，对于对抗激烈，消耗体力大的竞技比赛，比赛间的休整尤其重要，休整时间的长短对参赛队的竞技水平的发挥有大的影响。本文主要研究赛程安排问题，通过建立数学模型来研究。 对于问题一，题目要求对于5支球队的比赛，给出一个各队至少每两场比赛中间都至少相隔一场的赛程。通过分析这个题目，可以采用穷举法，即将可能出现的结果一一列举，但按照此方法会造成结果的遗漏。因此在解决本题过程中，在确定上限的前提下，然后采用计算机编制的方法将结果全部列出。其中的一种结果见下表（表1）。对于问题二，首先是对问题的理解：竞赛排序的方法有多种，而每一种方法都有一个最小的各队两场比赛中间的间隔，在这里认为这个上限为所有排序方法中最小的各队每两场比赛间隔场次数目的最小值。然后用轮转法排出一个例子然后由一般到全部得出结论并对结论的存在性和最优性进行证明。当为偶数时可以直接利用轮转法并得到如下结论：结论1：当时，各队每两场比赛间隔场次数的上限为当为技奇数时我们将假设有第个队转化为偶数个队求解，得到如下结论：结论2：对于问题三，在问题二解决的基础上，直接令，代入问题二求解运用的方法便可得到它们的赛程安排。 对于问题四，首先题目要求，分析可能会影响赛程优劣的因素。通过分析发现平均相隔场次数也可以影响赛程的优劣。令为第队第个间隔场次数，（）。所以平均相隔场次数为，越大越好关键词：轮转法 最优性 存在性1、 问题重述1.1背景分析众所周知在竞技比赛中公平性是至关重要的。公平性表现在很多方面，例如参赛队出场的先后次序，比赛的休整情况。对于对抗激励，消耗体力大的竞技比赛，比赛间的休整尤其重要，休整时间的长短对参赛队竞技水平的发挥有很大的影响，因此一个很好的赛程安排应该使每个队在比赛期间的修整时间尽可能均等。为此我们研究以下问题。11.2需要解决的问题假设你所在的年级有5个班，每班一支球队在场地进行单循环比赛，共要进行场比赛，如何安排赛程使各队来说都尽量公平？下面是随便安排的一个赛程：记5支球队为在下表左半部分的又上三角的个小空格中，随手写上，就得到一个赛程，即第1场，第2场，第10场，为方便起见将这些数据沿对角线对称地填入左下三角。 这个赛程的公平性如何呢，不妨只看看各队每两场比赛中间得到的休整是否均等。表的右半部分是各队每两场比赛间相隔的场次数，显然这个赛程对有利，对不公平。ABCDE每两场比赛间相隔场次数AX19361, 2, 2B1X2580, 2, 2C92X7104, 1, 0D357X40, 0, 1E68104X1, 1, 1从上面的例子出发讨论以下问题：1）对于5支球队的比赛，给出一个各队每两场比赛中间都至少相隔场的赛程。 2）当支球队比赛时，各队每两场比赛中间相隔的场次数的上限是多少。3）在达到2）的条件下，给出的赛程，并说明它们的编制过程。4）除了每两场比赛间相隔次数这一指标外，你还能给出哪些指标来衡量一个赛程的优劣，并说明3）中给出的赛程达到这些指标的程度。 2、 模型假设1)假设每场比赛都能够正常进行即不存在意外情况；2)假设每场比赛时间相同；3)假设比赛而公平性只与赛程的安排有关，而与其他因素无关；4)假设每一段比赛时间内各队实力基本稳定；三、符号说明为了方便问题的求解，我们给出以下符号说明:各队每两场比赛中间相隔的场次数上限第队第个间隔场次数各队每两场比赛中间平均相隔场次数最大偏差最小间隔场次数比赛总场次数3、 问题分析2.1对于问题一的分析: 对于第一问题目要求对于5只球队的比赛，给出一个各队至少每两场比赛中间都至少相隔一场的赛程。在解决这个题目的过程中首先可能会想到穷举法，即逐一列举出来。这样做会造成结果不全面，会造成遗漏，而且非常复杂，给题目解决造成了很大的困难。因此对解决此题过程中，首先确定赛程安排的上下限，即上限为2场。然后采用计算机或者手工编制的方法来完成。2.2对于问题二的分析:对于要求求出球队比赛是的上下限，竞赛排序的方法有多种，而每一种方法都有一个最小的各队两场比赛中间的间隔，在这里认为这个上限为所有排序方法中最小的各队每两场比赛间隔场次数目的最小值（对于本题中我们的求解是否满足我们对问题的理解在模型的检验中给出证明）。在解决这个问题时我们用轮转法来进行求解：在单循环赛中各队普遍出现一次，称为“一轮”。每两个队之间的比赛一次成为“一次”。在知道球队总数的情况下可以求出比赛的总场数：次数=，当有个队参加比赛时，比赛场次数为，轮换一次成为一轮。这时就要对的奇偶性分两种情况进行讨论。当为偶数时，一轮正好两两两对赛，需要打场比赛。，每轮比赛中的；当为奇数时为了方便解决问题，假设存在一个虚拟的队伍第个队参与到单循环赛中，进而将为奇数的情形转化为为偶数的情况罗列出赛程序列，然后将含有第个队伍参加的比赛从赛程中除去进而对问题进行求解。，每轮比赛中比赛的。 2.3对于问题三的分析: 基于问题二，在结果问题三的过程中，只需要令，代入问题二求解运用的方法便可得到它们的赛程安排。 2.4对于问题四的分析:对于问题四，题目要求除了每两场比赛间相隔次数这一指标外，再找出其他指标来衡量一个赛程的优劣，并说明3）中给出的赛程达到这些指标的程度。首先题目要求，分析可能会影响赛程优劣的因素。通过分析发现平均相隔场次数也可以影响赛程的优劣。令为第队第个间隔场次数，（）。所以平均相隔场次数为，越大越好即越大，对赛程越有利。五、 模型的建立与求解5.1对于问题一的模型建立与求解：对于第一问题目要求对于5只球队的比赛，给出一个各队至少每两场比赛中间都至少相隔一场的赛程。在解决这个题目的过程中首先可能会想到穷举法，即逐一列举出来。这样做会造成结果不全面，会造成遗漏，而且非常复杂，给题目解决造成了很大的困难。因此对解决此题过程中，首先确定赛程安排的上下限，即上限为2场。然后采用计算机或者手工编制的方法来完成。 利用求解得出满足要求的编制方法共有240种，见下表：表1：平均每两场比赛相间隔场次数其编制过程如下，不妨假设第一场，记为。第二场比赛为，在各队每两场比赛中间至少相隔一场的前提要求下，仅有可以参加第三场比赛，即，由于已在第一场比赛过，故排除，则仅剩下两种可。不妨假设第三场比赛为。以此类推，以后各场比赛程序安排为因此球队之间进行的单循环赛，所以任何两队之间只能进行一场比赛。即对任何一队而言，曾经与其交战过的队在此后的比赛中不再相遇。5.2对于问题二的模型建立与求解：对第二个问题中各队每两场比赛中间相隔场次数的上限的理解：竞赛排序的方法有多种，而每一种方法都有一个最小的各队两场比赛中间的间隔，在这里认为这个上限为所有排序方法中最小的各队每两场比赛间隔场次数目的最小值（对于本题中我们的求解是否满足我们对问题的理解在模型的检验中给出证明。在解决这个问题时我们用轮转法来进行求解：在单循环赛中各队普遍出现一次，称为“一轮”。每两个队之间的比赛一次成为“一次”。 （1）单循环赛场次数：次数= （2）单循环轮数的计算：设有个对参加比赛，由（1）的结果得知比赛场次数为，轮换一次成为一轮。因为轮数的确定要受到队伍数目的影响，因此将问题转换为两种情况来解答：1、当为偶数时，一轮正好两两两对赛，需要打场比赛。，每轮比赛中的2、 当为奇数时为了方便解决问题，假设存在一个虚拟的队伍第个队参与到单循环赛中，进而将为奇数的情形转化为为偶数的情况罗列出赛程序列，然后将含有第个队伍参加的比赛从赛程中出去进而对问题进行求解。 ，每轮比赛中比赛的在解决第二问时，同样要根据为奇数与偶数将问题分为两种情况来进行解答1、 当为偶数的情形 按照轮转法的编排思路，我们对进行分析。首先将“1”号固定在左上角不动，其它各号按大小顺序依次排序，依照这种方法排出以后各轮的全对阵情况，其竞赛次序如下表所示：表：时竞赛的次序第一轮第二轮第三轮第四轮第五轮 其中每个参赛队比赛期间的间隔分布如下： 表：时每两场比赛间相隔的场次数参赛队间隔分布利用软件编程实现轮转法，从程序结果中得到以内的偶数个队伍之间比赛时，各自的上限，如下表所示：表：以内偶数个队伍比赛及其对应的间隔上限参赛队数上限 由此我们根据上述表格猜测结论：结论1：当时，各队每两场比赛间隔场次数的上限为下面是对结论的证明：首先证明它的存在性：因为不相邻两轮之间各队每两场之间的间隔一定比相邻两轮之间各队每两场之间的间隔大，所以在这里我们只考虑相邻两轮之间的情况，即对进行讨论。对于第轮第一列第个元素，当时出现在第轮第一列第一个位置，那么这个队伍在这两场比赛中的间隔为；当时出现在第轮第一列第个位置，那么这个队伍在这两场比赛中的间隔为；当时出现在第轮第二列第个位置，那么这个队伍在这两场比赛中的间隔为。然后证明它的最优性2：利用反证法来进行证明，假设当时存在一个。要保证间隔场比赛，显然在前场比赛一个队不可能比赛两场。也就是个队伍在第一轮中全部出场，否则将会造成某一个队在前两场比赛间隔小于。在第一轮全部队伍出场的情况下，要是参加第场比赛的两个队伍与他们各自前一场至少相隔场，它们必须是参加了第一场比赛的队伍，也就是说比赛两次这与单循环赛制任意两个队伍只比赛一次是矛盾的，那么结论最优性可证。因为我们认为的各队每两场比赛中间相隔场次数的上限，我们认为这个上限为各各队每两场比赛间隔场次数目的最小值，经过上面的讨论得出最小的间隔次数为，因此我们说各队没两场比赛中间间隔的场次数的上限为，将代入即结论得证。2、 当为奇数的情形： 我们假设存在一个虚拟的队伍第队也参与到单循环赛。在解决为奇数时我们以为例，此时增加一个虚拟的第支队伍。同样的按照上面的轮转法对个队伍的竞赛次序进行排列，其竞赛次序如下表所示：表：时竞赛的次序第一轮第二轮第三轮第四轮第五轮第六轮第七轮 根据（1）中对结论的猜测与证明可以得到：各队每两场比赛间隔场次数的上限为，但是这种情况下时时的结果，并且每轮比赛中的。而现在需要的是如表（见附录）这种为奇数、每轮比赛中比赛的的结果。 因此,将代入就可以得到我们所需要的结论： 当时，各队每两场比赛间隔场次数的上限为。我们将代入结论发现与事实不相符因此将另外的罗列出与其它奇数进行区分区分：结论2：5.3对于问题三的模型建立与求解：根据二中的偶数支队伍竞赛次序排列的方法可以得到时竞赛次序的排列表如下所示：表：时竞赛的次序第一轮第二轮第三轮第四轮第五轮第六轮第七轮当求时的竞赛次序的排列时根据第二问要先求出的竞赛次序的排列表，如表所示见（附录2） 进而将有第队参加的比赛都去除掉就可以得到个队伍比赛的次序。 表：时竞赛的次序 第一轮第二轮第三轮第四轮第五轮第六轮第七轮第八轮第九轮5.4对于问题四的模型建立与求解：已知“各队每两场比赛最小相隔场次的上限”这一指标外，还有其他一些指标来衡量比赛优劣，例如：(1)、平均相隔场次： 令为第队第个间隔场次数，（）。所以平均相隔场次数为，越大越好。检查的赛程得；检查的赛程得。可以得到的上界为上述结果得出，给出的赛程都已经达到了此上界。（2）、相隔场次的最大偏差： 在赛程中每队每两场比赛相隔场次的均匀性可以由的偏差来衡量。表示整个相隔场次的最大偏差，表示球队之间相隔场次的最大偏；并且两者都是越小越好。分别检查的赛程得。 实际上两者均有下界： 上述结果表明所给出的赛程均达到了此下界。（3）、球队出场顺序： 我们知道在赛程按照完美匹配后，分成了若干轮，一支球队出场的次序越靠后越对其有利，在同一轮里出场越靠后越有利。按照此思想就得到衡量一 个赛程优劣的另一指标。对于所给出的赛程，可以知道每队的出场次序：表10：每个队的出场次序队号出场场次1，5，9，13，17，21，252，7，12，16，19，22，253，8，12，15，18，21，264，8，11，14，17，22，274，7，10，13，18，23，283，6，9，14，19，24，282，5，10，15，20，24，271，6，11，16，20，23，26通过分析比较，可以得出结论，此赛程安排很合理，公平。同理，可以得出结论，的赛程安排是比较公平的。六、 模型的检验 在检验第二问中建立的模型是否满足我们对问题的理解时，我们用另外的一种模型来求证：设赛程中某两场比赛时两个队伍，队参加的下一场比赛是要使各队没两场比赛是最小间隔次数，那么在在这两场比赛之间除三个队伍之外还有支队伍在比赛。有上述叙述可以得到结论：结论3：为了是结论更加令人信服我们对结论中为奇数与为偶数进行证明，证明的详细过程如下所示： 当为奇数时，假设 那么比赛总的场次数为： 在前场比赛中，共有个队伍参加了比赛，那么至少有一个队伍残疾了两次比赛，假设这个队伍为。 两场比赛的间隔次数不会超过 其中，代入上式并进行求证就可以得到： 当为偶数时，假设， 比赛的总场次为在前场比赛中至少有一个队伍（假设为队）参加了两次比赛，第场比赛在赛程中是场，因此，若，则通过上面可以求证出结论是正确的。然后用这个模型与第二问中对问题求解的模型对比来进行分析：当为偶数时：有结论可知：有结论中当为偶数时可知其结果一样；当为奇数时：由结论与结论可知：当为时两种模型所得结果一样，当为大于的奇数时可知结论总比结论大。也就是说相对于其它模型，本题中所给的模型求出的各队每两场比赛书间隔最小。因此我们认为在在对问题求解的过程中，建立的模型满足对问题的理解。七、 模型的评价与改进本模型的结果成功地给出了同一场地单曲循环赛各队每两场比赛中间相隔次数上限的计算公式，有一定的理论意义与实际意义。关于同一场地单循环赛赛程编排法，至今实际中都采用“循环规则”，通过我们的研究发现此规则虽然简单、对于为偶数的赛程，符合，从而有公平性，对于为奇数，编派的赛程,有失公平性。从比赛与休整的节奏，第一队最有利，第五队最不利，另外从各队总间隔场次数看，也有较大的差异，说明实际赛程编织法有待改进。而本模型算法提出的“生成规则”（ 为奇数编排法）。本模型直接推算出每队每两场比赛相隔的场数的上、下限，准确度高、稳定性好。此外它还是一个算法，该算法有推广的价值，方法合理可行，电脑程序只需要输入队便有合理的结果。 该模型的缺点是，对于问题中线性规划模型本质上是穷举法，时间复杂度大，效率很低，改进模型的思路，任研究尝试人工智能模型表示等等。赛程的安排没有考虑到各球队的实力、队员的心理素质以及天气等因素，因此它只是一个优化模型。赛程只考虑了比赛间相隔场次数的问题，即没有考虑到顺序的问题，对最后一场比赛的两队而言是较有利的。八、参考文献1/p-703991447147.html2/view/68f9fed86f1aff00bed51eeb.html附录附录1表时竞赛的次序第一轮第二轮第三轮第四轮第五轮第六轮第七轮表：时竞赛的次序第一轮第二轮第三轮第四轮第五轮第六轮第七轮第八轮第九轮附录2问题一的编程：w=1 2;1 3;1 4;1 5;2 3;2 4;2 5;3 4;3 5;4 5;c=1;for j=1:10A(1)=j;for k=1:10if k=j&w(j,1)=w(k,1)&w(j,2)=w(k,2)&w(j,2)=w(k,1)&w(j,1)=w(k,2)A(2)=k;for l=1:10if l=k&l=j&w(k,1)=w(l,1)&w(k,2)=w(l,2)&w(k,2)=w(l,1)&w(k,1)=w(l,2)A(3)=l;for m=1:10if m=k&m=j&m=l&w(l,1)=w(m,1)&w(l,2)=w(m,2)&w