2006年全国研究生数学建模竞赛D题优秀论文(北京理工大学)-李然,王继辉.pdfVIP

2006年全国研究生数学建模竞赛D题优秀论文(北京理工大学)-李然,王继辉--第1页

北京理工大学：李然，王继辉，王建秋

全国第三届研究生数学建模竞赛

题目学生面试问题

北京理工大学：李然，王继辉，王建秋

摘要：

本文通过使用图论、局部有哪些信誉好的足球投注网站算法确定了给定条件下的老师数量的最小值

M，建立了分配老师的组合优化模型，并求解模型给出具体分组情况，最后提出

了改进的公平性指标。

问题1：论文通过解决对偶命题来实现的，使用图论的边、度关系知识，获

取M的一个较优下界(M=,同时回答了Mmod3条件下M的更精确的下

n

1148

2



界)，然后利用这个下界，使用局部有哪些信誉好的足球投注网站算法，有哪些信誉好的足球投注网站完全图Km中的无边重复的

K的个数，从而找到最小的M。

4

问题2：将问题抽象为一个TTP（TimeTablePlanning），建立了分配老师与

学生的组合优化模型，通过设定约束条件的优先级别，确定了优化目标，并利用

遗传算法对模型进行求解，给定M,N的“面试组”方案（结果详见正文）。

问题3:前半部分的思路与问题1相同，M的一个较优下界为不小于

n的偶数，同时在局部有哪些信誉好的足球投注网站算法中多引入一个状态矩阵S，而且还研究

1148

2



2

了此条件下文（理）老师分配“面试组”时的最大利用率近似为；后半部分的

3

思路与问题2相同，修改问题2已建立的模型及优化目标。

问题4：从面试的均匀性、公平性和信度出发，考虑到当前学科交叉和学生

的综合素质日益重要，我们提出新的分配方案--每4位老师同时面试3位学生，

每位学生随机参加3场面试。

关键字:对偶完全图较优下界局部有哪些信誉好的足球投注网站算法TTP遗传算法公平性指标

2006年全国研究生数学建模竞赛一等奖1

2006年全国研究生数学建模竞赛D题优秀论文(北京理工大学)-李然,王继辉--第1页

2006年全国研究生数学建模竞赛D题优秀论文(北京理工大学)-李然,王继辉--第2页

北京理工大学：李然，王继辉，王建秋

问题1

设G为m阶无向简单图，若G中的每个定点均与其余的（m-1）个顶点相邻，

则称G为m阶无向完全图，记为Km.如四阶完全图K4。

如果用G的每个顶点来表示不同的老师，用G中的边来表示老师在同一个“面

试组”这一关系，则G中无边重复的K4图，就对应了一个“面试组”方案，同

时，每有一个面试方案，就意味着老师可以接受一个考生的面试请求。于是本问

题就等价于下面一个对偶的图论问题：

对偶命题1：设G是一个m阶无向完全图Km，n为G中无重复边的K4的个