赛程安排数学建模问题

题目赛程安排摘要赛程安排在体育活动中举足轻重，在很大程度上影响比赛的结果；本文主要针对最优赛程安排方案建立相应的数学模型，给出最优赛程的安排方案。对于问题一，要给出一个各队每两场比赛中间都至少相隔一场的赛。因为参赛队伍只有5个，容易操作，所以可以利用排除-假设法可以得到一种满足条件的赛程安排，即,,,,,,,,,ABCDEABCDEACBDECADBE。对于问题二，考虑到各队每两场比赛中间至少相隔一场，我们用逆时针轮转法对比赛队伍进行排序，并根据这种方法，用Matlab编出相应编程得出不同队伍比赛间隔的上限，再根据数据总结出规律，当N为偶数时各队每两场比赛中间相隔的场次数的上限为22N场，用Matlab软件验证其准确性。用同样的方法可知，当N为奇数时各队每两场比赛中间相隔的场次数的上限为N32（）。对于问题三，在达到第二问上限的情况下，可通过轮换模型得到8,9NN的赛程安排。N8时一种赛程安排如下：(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)9N时一种赛程安排如下：(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).对于问题四，我们可以用每个队的每两场比赛中间间隔的场次数之和SUM来衡量赛程的公平性。当SUM不同时，SUM大的队伍对其比赛结果越有利。当SUM相同时，用每次间隔场次的标准差来衡量赛程的公平性，其中标准差越小的队对其比赛的结果越有利。当SUM相同且每次间隔场次的标准差也相同时，两个队比赛时，我们用双方已参加比赛的次数来衡量比赛赛程的优劣，其中在双方比赛时，已参加比赛次数越少，其比赛的结果越有利。关键词：排除-假设法逆时针轮转法Matlab标准差1一、问题重述1.1背景分析当今社会，随着经济的增长和科学技术的发展，人们的生活水平不断的提高，体育竞赛也在日趋紧张的现代生活中被人们提到了越来越重要的位置。北京奥运会的成功更加提升了体育在人们生活中的份量，体育活动在生活中起着举足轻重的作用。而这些体育运动中，公平性又显得尤其重要。特别是在对抗性强的单循环比赛中，赛程安排的不同，对比赛结果响很大。本文主要着手于最优赛程安排方案，尽量给出赛程安排使得对每支球队来说都很公平。1.2问题重述假设你所在的年级有5个班，每班一支球队在同一块场地上进行单循环赛（所谓单循环赛是所有参加比赛的队均能相遇一次，最后按各队在全部比赛中的积分、得失分率排列名次）要进行10场比赛。如何安排赛程使对各队来说都尽量公平呢？下面是随便安排的一个赛程:记5支球队为,,,,ABCDE，在下表左半部分的右上三角的10个空格中,随手填上1,2,3...10,就得到一个赛程,即第1场A对B,第2场B对C,,第10场C对E.为方便起见将这些数字沿对角线对称地填入左下三角。这个赛程的公平性如何呢,不妨只看看各队每两场比赛中间得到的休整时间是否均等。表的右半部分是各队每两场比赛间相隔的场次数,显然这个赛程对A,有利E,对D则不公平。表一ABCDE每两场比赛间相隔场数AX19361,2,2B1X2580,2,2C92X7104,1,0D357X40,0,1E68104X1,1,1从上面的例子出发讨论以下问题:问题一：对于5支球队的比赛,给出一个各队每两场比赛中间都至少相隔一场的赛程。问题二：当n支球队比赛时,各队每两场比赛中间相隔的场次数的上限是多少。问题三：在达到2)的上限的条件下,给出8,9nn的赛程,并说明它们的编制过程。问题四：除了每两场比赛间相隔场次数这一指标外,你还能给出哪些指标来衡量一个赛程的优劣,并说明3)中给出的赛程达到这些指标的程度。2二、模型假设结合本题实际，为确保模型求解的准确性和合理性，我们排除了一些因素的干扰，提出以下几点假设：1、比赛期间，比赛不受任何外界因素影响。2、每天比赛的时间段固定并且每场比赛时间相同。3、任两球队在相同的休息时间里都能够得到同等程度的休息。4、比赛在一天中指定的时间准时开始和结束并且严格按原赛程的规定执行，不存在因为其他原因造成的停赛的出现。5、所建模型仅考虑开始比赛期间相邻两场比赛之间的休息时间队参赛队的影响，不考虑第一场比赛之前和最后一场比赛之后的休息时间对参赛队的影响。三、符号说明3.1符号说明为了便于问题的求解，我们给出以下符号说明：N表示参赛队伍的数量M表示各队每两场比赛中间隔的场次数的上限a表示参赛队的轮数ix表示相邻两场比赛的间隔场数1,2,3inS每个队的每两场比赛中间间隔的场次数的标准差SUM每个队的每两场比赛中间间隔的场次数之和d各队在全部赛程中间隔场次数D在全部赛程中间隔场数的总次数3.2名词解释:1、上限上限为每两场比赛中间相隔的场次数的最小值。2、单循环赛单循环赛是所有参加比赛的队均能相遇一次，最后按各队在全部比赛中的积分、得失分率排列名次。3、排除—假设法当某一变因素的存在形式限定在有限种可能（如某命题成立或不成立，如a与b大小：有大于、小于和等于三种情况）时，假设该因素处于某种情况（如命题成立，如ab），并以此为条件进行推理。四、问题分析4.1对问题一的分析对于问题一，假设这五支球队分别定义为,,,,ABCDE队，那么这五支球队比赛的总场次数为10。第一场出场队伍组合有2510C种可能，要满足各队每两场比赛中间都至少相隔一场这个条件，所以第二场比赛共有23C种可能，以此类3推共有10*3*2*2*2240种可能。其中一种可能如下表二：表二、五支队伍参赛赛程安排表ABCDE每两场比赛间相隔场次数AX16931,2,2B1X47102,2,2C64X281,1,1D972X52,1,1E31085X1,2,1最后再用Matlab编程来验证此排除—假设法的准确性，发现结果相同即证明针对参赛队伍较少的情况此种方法简易可行。4.2对问题二的分析为了方便计算、便于表示，我们将参加比赛的球队由编号分别为字母A、B、C、D…分别用数字1、2、3、4、……等代替表示，固定第1队,按左边由上而下、右边由下而上(即逆时针转动)排成完整的两列。再将比赛场地的顺序按轮转法排出，分别讨论。根据这种逆时针轮转法，用Matlab编出相应软件得出不同队伍参赛时比赛间隔的上限，如当6,8,10,12n时，算出各队每两场比赛中间相隔的场次数的上限分别为1，2,3,4……，分析以上数据可以得到如下规律，当N为偶数时，各队每两场比赛中间相隔的场次数的上限为22N场；最后再用软件验证得到这种逆时针轮转法的准确性。用同样的方法可知，当N为基数时各队每两场比赛中间相隔的场次数的上限为32N。4.3对问题三的分析在达到第二问上限的情况下，可通过轮换模型得到8,9NN的赛程安排。当8N时，把1固定在左上角不动，其余元素按逆时针轮转法轮换，一共轮换了2N次。用Matlab编程得到一种赛程安排如下：(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)其中每一个数代表一个队，括号里表示每两个队进行比赛。同样可以得到9N的一种赛程安排：(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)4.4对问题四的分析先用用每个队的每两场比赛中间间隔的场次数之和SUM来衡量赛程的公平性。当SUM不同时，SUM大的队伍对其比赛结果越有利。当SUM相同时，用4每次间隔场次的方差来衡量赛程的公平性，其中方差越小的队对其比赛的结果越有利。当SUM相同且每次间隔场次的方差也相同时，两个队比赛时，我们用双方已参加比赛的次数来衡量比赛赛程的优劣，其中在双方比赛时，已参加比赛次数越少的队，对其比赛的结果就越有利。五、模型的建立与求解5.1问题一的模型建立与求解根据对实际问题的分析可知，进行单循环赛时各队每两场比赛中间得到的休整时间是否均等，对于球赛的输赢起着决定性的作用，问题一需要我们对于5支球队的比赛，给出一个各队每两场比赛中间都至少相隔一场的赛程，因为队伍较少，所以利用排除-假设法可以得到一种理想的赛程安排。假设这五支球队分别定义为,,,,ABCDE队，5支球队进行单循环赛比赛的总场次数(1)2nnx，则五支球队比赛的总场次数为5*(51)2x。五支球队进行比赛，因为五支球队没有明显的次序特征，所以第一场比赛出场队伍组合有2510C种可能。假设,AB两支球队先进行比赛，要满足各队每两场比赛中间都至少相隔一场这个条件，因此第二场比赛只能从,,CDE这三个球队中选择两支进行比赛，共有23C种选择，即,,CDCEDE。假设第二场比赛队伍组合为CD，在之前条件约束下，仅有,,ABE可以参加第三场比赛，即,,ABAEBE，可以设第三场比赛队伍组合为EA。因为球队之间进行的是单循环赛，所以在任何两队之间只能进行一场比赛，对任何一队而言，曾经与其交战过的队，在以后的比赛中当不再相遇。以此类推，以后各场比赛赛程安排可以为,,,,,,BCDEACBDECADBE。所以符合条件的比赛场数共有103222240场。如图一所示：图一、五个队伍参赛赛程安排图因为五个队伍比赛场次数较少可以将其转化成如下形式的赛程表三，可以直观清晰的看出每两场比赛相隔场次数的特点。表三、五个队伍比赛间隔场次表ABCDE每两场比赛间相隔场次数AX16931,2,2B1X47102,2,25C64X281,1,1D972X52,1,1E31085X1,2,1下面我们利用Matlab编程验证这种假设-排除法的准确性，编程能求出总的240场次比赛情况，只要从中找出与上面对应的赛程安排就能证明此种方法准确。下表四为Matlab软件求解出的相应结果，五个队伍参加五轮十场比赛满足要求的赛程安排：表四、五个队伍参赛赛程安排1-25-14-52-41-43-42-31-35-32-5从表格可以看出，结果与假设-排除法得出的结果相同，证明针对参赛队伍较少的情况此种方法简易可行。5.2问题二的模型建立与求解考虑到各队每两场比赛中间都至少相隔一场时让赛程尽可能公平的情况下，求每两场比赛中间相隔的场次数的上限。题目要求我们安排N支球队的单循环赛程，并使赛程对各队来说尽量做到公平。要想做到公平，其衡量的指标之一是：考虑各队每两场比赛之间得到的休整时间是否均等、或是差距不大为此采用“逆时针轮转法”对此问题进行处理，首先我们将参加比赛的球队由编号分别为字母,,,ABCD分别用数字1234...、、、等代替表示，然后固定第1队，按左边由上而下、右边由下而上(即逆时针转动)排成完整的两列。为了确定比赛顺序，要先将比赛场次的顺序按轮转法排出。仔细观察我们可以发现