数学建模论文题目：比赛日程安排问题学院：计算机科学与工程学院系别：计算机科学与技术班级：080402姓名：李真雄学号：20082365TEL : 155****5725目录1. 题目 22. 摘要 23. 问题重述 22. 模型建立 32.1模型假设 32.2符号设定 42.3模型建立 53. 模型计算 6注：当n支球队比赛时，各队每两场比赛中间隔的场次数的上限为[(n-3)/2] 114. 模型推广 13当n支球队比赛时，各队每两场比赛中间隔的场次数的上限为[(n-3)/2] 13附录： 141 .题目比赛日程安排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= C2场比赛，n有M= ( c2)!种赛程安排，通常M是较大的数字M种赛程中各队比 n赛间隔情况不同，因而对各队的比赛有影响题目中4个问题相互联系，基本的题是赛程安排公平性及其编排法；3. 各队每两场比赛中间隔的场次数的上限，每个队都满足的间隔上限，其数学表达：d=max didi=min Pjkfj,k,t=1,2,3, ・・・n2.2符号设定表1n参赛队数N比赛场数M赛程总共安排数ajkj队与k队比赛场次序号数Pjktt队与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=max dipjkt—atkI-1a = aa _ = 0di=minPjktst .<乙乙 a = C 2( C 2 + 1) j=i k=ia g Na > 1a "丰 a (j Y k, m y l)i = 1,2,3...C 2nj, k, t = 1,2,3... n3・模型计算问题（1）的解n=7的编制过程：（1）.移位规则，考虑一般n=2k+1,先建立一个 2k（2k+1）矩阵称之为“生成矩阵”，由此矩阵即可生成赛程下面是 此矩阵的生成规则:① 将任一队（如2k+1队）先占第2k+1列的各行，余下各队占第一行 的余下位置，不妨设1, 2,・・・2k队分别占第一行的1, 2,・・・2k歹U② 将第一行前2k个数按下述规则向下移动得第二行，依次类似得其 余各行；将奇数行从第一行算起的第奇数个数右移1位到下一行；A. 将奇数行的第偶数个数左移1位到下一行；B. 将偶数行的第奇数个数左移1位到下一行；C. 将偶数行的第偶数个数右移1位到下一行；D. 不能移动（指移出矩阵外）的数垂直下移到下一行，如此移动n-2 次则生成矩阵，由生成矩阵从第一行"1生起依次相邻两数表示一 场比赛。
此赛程满足各队每两场比赛中间相隔天数达到上限 d=[（n-3）/2].由此可得结果2）表4是用实际方法对n=7编制的赛程（首轮1队轮空，1队 不动）其弊端是此赛程d=1，而按公式d=[（n-3）/2]=2说明各队每 两场比赛中间极不均等，如有间隔6场，有间隔1场，具体到一个队 （如5队比赛与休整时间极不均等）从比赛与休整的节奏，第一队 最有利，第五队最不利，另外从各队总间隔场次数看，也有较大差异， 说明实际赛程编制法有待改进而本模型算法提出的“生成规则”（见 上文n为奇数编派法）既简便又公平1234567每两场比赛间相隔场次数总间隔场次数1X19161310742, 2, 2, 2, 210219X91751513, 3, 5, 1, 1133169X6142123, 2, 2, 1, 19413176X311202, 4, 1, 3, 2125105143X2181, 2, 1, 3, 613671521121X184, 3, 3, 2, 2147411220818X2, 3, 3, 5, 114(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天：B-GC-FD-EA-GB-EC-DA-FG-EB-CA-EF-DG-CF-BA-CB-DF-GA-BD-GE-FA-DE-C问题（2）的解：n=8的编制过程：循环规则[2]八个队排成一个42矩阵，同一行两数表示这两队比赛（称为比赛矩 阵），此矩阵表示第一轮比赛安排，如图1下面的安排中将某队（如 1队）固定不移动，余下的队逆时针循环移动1位（上、下相邻两数 的位置叫“1位”），得第二轮比赛安排，如图2「18 -「17 -2 匕7863625_ 45」_ 34」图2图1按此规则移动6次，既得8队比赛28场的一个赛程，此赛程满足各队每两场比赛中间相隔场次数，达到上限d=[(8-3)/2]=2见表5。
表512345678比赛相隔场次数总场次数1X125521917133，3，3，3，3，31821X162026611234， 4， 4， 3， 2， 21932516X212192274， 4， 3， 2， 2， 21745202X152427102， 4， 4， 4， 3， 219521261215X38184， 3， 2， 2， 2， 41769619243X14282， 2， 4， 4， 4， 319717112227814X43， 2， 2， 2， 4， 4178132371018284X2， 2， 2， 4， 4， 418一般n=2k，一个赛程有M= C 2场比赛，按此规则需移动(n-2)次， n得满足d的赛程由“循环规则”编程得一上结果综上可得适当的日程安排：表61-82-73-64-51-78-62-53-41-67-58-42-31-56-47-38-21-45-36-27-81-34-25-86-71-23-84-75-6注：当n支球队比赛时，各队每两场比赛中间隔的场次数的上限为 [(n-3)/2]9支队伍也类似，具循环法则，得表:123456789133292521171395233163011276241329161226723220425301282231934521112684183515617277224361431713623318363210892421935143228951203415311028注：9支队伍是单数，其与8支队伍区别在于，它要先虚拟一个0队伍，以便于与循环轮转法则进行运算。
如：1 2 3 4 5 1 0 2 3 4其中，当队伍碰到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])o综上所述，各队两场比赛中间隔的天数的上 限为[(n-3)/。