补考日程安排优化模型.docVIP

学生学号

论文成绩

武汉理工大学

建模论文

任课教师＿＿＿＿＿＿＿＿＿＿＿＿

论文题目＿＿＿＿＿＿＿＿＿＿＿＿

学院班级＿＿＿＿＿＿＿＿＿＿＿＿

姓名＿＿＿＿＿＿＿＿＿＿＿＿

2012——2013学年第二学期

补考日程安排优化模型

摘要：在高校教育工作中，经常会遇到补考课程的时间安排问题。此题告诉我们一名学生可能会有多门补考科目，但在每一个时间段内，每位学生只能参加一门考试，所以考试中，有些科目是不能安排在同一时间段内的。此题要求我们把11门课程考试在两天的8个时间段内安排好，并且尽量防止冲突，最好把考试安排在上午。我应用建模思想建立数学模型，根据对课程能同时进行考试和不能同时进行考试的分类思想，应用图解和0—1规划解题，运用LINGO软件进行计算，得出了需要在7个时间段内安排考试，有多种安排方式〔例:周六上午8:00–9:35,K1,K4,K8,K9;9:55–11:30，K5;下午13:30–15:05，K7;15:25–17:00,K10.周日上午8:00–9:35，K2，K3;9:55–11:30，K6;下午13:30–15:05，K11〕。

关键词：补考，日程安排，0—1规划，数学建模

问题重述

各大高校通常都在开学前的周六、周日完成补考。现就北京工业大学某次开学前的补考进行安排，要求每天的考试时间分为4个时间段，分别为：8:00–9:35，9:55–11:30，13:30–15:05，15:25–17:00。由于有的学生有多门补考，因此，有些课程安排在一个时段补考会产生冲突〔例如，学生张三要补考高等数学和普通物理，如果将这两门课安排在一个时段补考就产生冲突〕。现有11门课程〔K1，K2，…，K11〕需要安排补考，表A给出11门课程的补考是否有冲突的情况。

表A：11门课程补考有冲突的情况〔×为有冲突，－为无冲突〕

课程

K1

K2

K3

K4

K5

K6

K7

K8

K9

K10

K11

K1

－

×

－

－

×

－

×

－

－

×

×

K2

×

－

－

－

×

－

×

－

－

×

×

K3

－

－

－

×

×

×

×

－

×

×

×

K4

－

－

×

－

×

×

×

－

－

×

×

K5

×

×

×

×

－

×

×

×

×

×

×

K6

－

－

×

×

×

－

×

－

×

×

×

K7

×

×

×

×

×

×

－

×

×

×

×

K8

－

－

－

－

×

－

×

－

－

×

×

K9

－

－

×

－

×

×

×

－

－

×

×

K10

×

×

×

×

×

×

×

×

×

－

×

K11

×

×

×

×

×

×

×

×

×

×

－

要求：

〔1〕就该问题建立相应的数学模型、求解，帮助教务处制定一份详细的补考时间表，使得每位学生在每个时段都只需参加一门考试；

〔2〕如果有可能，补考时间尽量安排在上午；

〔3〕如果无法解决冲突问题，尽量使重要的课程不冲突〔课程编号越小越重要，例如，K1比K2重要〕。

问题分析

根据要求，一名学生可能会有多门补考科目，而每一位学生每场考试只能参加一门，从而安排的考试次数应不小于2，有些课程又不能同时进行考试，应对课程进行分类，把能同时考的放在一起，在使考试不冲突的情况下，尽量把考试安排在上午。

模型假设

监考老师足够，没有缺旷的情况。

学生没有缺考的情况。

考场数量足够多，考场设施一切正常。

学生可以连续参加几场考试。

符号说明

Xi

0-1规划中的变量，取1或0

i

对应变量中的第i门课程

模型建立求解

方法一：图论求解

把11门课程作为11个结点，可以同时进行的课程之间用边连起来，如下列图

由上图可以看出，K5,K7,K10,K11是四个孤立点。它们只能分别单独地安排在四个时间段。

并且可以发现K2，K4,K8，K9或者K1，K4,K8，K9这四个结点可构成完全图，所以它们可以同时进行。〔如下列图〕

此种情况下，剩余的K1,K6同时进行，K3单独；或者K1，K3同时进行，K6单独。

此时，剩余的K2,K6同时进行，K3单独；或者K2，K3同时进行，K6单独。

方法二：0-1规划求解

对考试的课程进行编号用Xi(i∈[1,11])表示，我们可以做0-1规划模型进行求解。

记Xi=1,表示第i门课程不可以同时进行考试;记Xi=0,表示第i门课程可以同时进行考试。

在发现K5,K7