期末考试监考的安排

姓名： 朱大照胡亚静王丽丽数学建模论文

期末考试监考的安排

摘 要

本文针对监考安排问题，设置一般假设、确定约束条件，建立了整数规划模型和逐级优化模型，并且结合人工排考的4种考试模式，进一步优化排考问题。本文模型一：以利用考场最少为目标，确定多重约束条件，建立整数规划数学模型，通过MATLAB编程求解，得到一个监考安排方案。模型二：以考试时间最短为目标，从时间安排，考场安排、教师安排三个方面建立数学模型，针对时间安排，用枚举法列举所有合理的考试时间模式4种（模式表见附录一），采用线性规划确定采用的考试模式。对考场安排和教师安排，在假设监考教师充足的前提下，用0-1规划和不同教师监考场数差值最小，建立考场安排与监考教师安排模型。通过用LINGO编程求解，求出最短考试时间为2.33天，并得出考场安排（见表二）。

此外，我们建立平均考场容量利用率的评价模型来评价各时间段考场安排的合理程度，得出模型二所建模式的平均考场容量利用率约为93%，远高于模型一的平均考场容量利用率，因此，模型二所得方案为良好考场安排方案。

关键词：逐级优化，0-1规划，枚举法，多重约束条件，平均考场容量利用率

问题重述：

考场安排是高校考务管理活动的主要组成部分，由于排考冲突条件多，数据量大，人工排考无疑是一种繁复、琐碎的工作。随着高校进一步扩招，人工排考的问题更显得突出。研究自动排考算法，解决现阶段存在的问题，实现考试安排的快捷高效具有一定的现实意义。

我们从数学方面分析该问题，以期能给各院系教务人员有所帮助，假设某学院期末考试现有的监考教师有120位，考试课程有100门，并且各课程的考试时间有90、120分钟两种情况，同时每位学生相邻两场考试间隔为1.5-100小时，该学院有50个专业参与考试，该学院共有50个考场。由于选修课程，可在一周时间内进行随堂考试，所以以下只针对必修课程和基础课程的考试安排。

一、 模型假设

1上同一门课的学生分在不同的考场； 2.每场考试需参加考试的学生均到场； 3.每个安排有考试的考场均能正常进行考试。

二、符号说明

an：表示监考老师的编号，n=1,2,3,…,120；

b：表示课程编号，b=1,2,3,…,100；

c：表示专业编号，c=1,2,3，…，50；

d：表示考场编号，d=1,2,3,…,50；

i： 表示某种考试模式，i=1,2，3,4

Pd：第d个考场的容量； ：表示C专业k班的学生；

CWkBtbRb：表示第b门课程在t时间是否考试（取1表示是，取0表示否）； ：表示考第b门课程的人数；

xi：表示采用第i种考试模式（i=1,2，3,4）所需天数； yid：表示第d考场采用i模式；

T0：表示安排所有考试的时间段集合;T01,2,3，4,5,6 hatd：表示第a位教师在t时间段是否监考第d个考场（取1表示是，取0表示否）；

考场d是否使用（取1表示有，取0表示否）；

ztd：在时间tytbd：表示时间t课程b在第d考场考试；

门考试课程（取1表示有，取0表示否）；

Acb：表示第c个专业是否有bt：表示考试的时间

三、模型建立与求解

1.模型一 在上同一门课的学生分在不同的考场的条件下求最少考场数量。

每个教室要么作为考场，要么不做考场，对教室进行编号，设为sl.当做考场时，赋值为1，否则为0，题中要求Min sl ，我们可以用0-1规划（参考大连海事大学数学建模讲义（张运杰编））模型进行求解，模型如下： 最少教室数量,目标函数为： Min sl

l150l150Subject to

1,表示第l间教室作为考场； sl 0,表示第l间教室不作为考场； 由于每个考场又必须有两名教师监考，因此教师的人数要大于考场数的二倍：

501202sll1a

nn1假设学生连续两场考试间隔最短为1.5小时最长为100小时，又每个学生相邻两门课考试时间间隔需满足：

1.5CWktj1CWktj100

综上所述，建立的模型：

50Min sl

l1s.t.

1,表示第l间教室作为考场； sl 0,表示第l间教室不作为考场；501202sll1an1n

1.5CWktj1CWktj100

2.模型二 在监考老师充足(120人)前提下求出期末考试的最短时间 2.1 模型建立 2.1.1考试时间安排

用xi表示采用第i种考试模式（i=1,2，3，4）所用的天数，xi是非负整数。由此以采用某些合理考试模式所需的考试天数最少为目标，得到目标函数：

4minzx

ii1为使考场容量最大化，假设采用考场D21-D50，每场考试所有考场可容纳1500人考试。为满足90min,120min各个考试时间段的考试人数要求，即考试人数不超过考场容量，有以下约束条件：

1）采取某些合理考试模式下，参加考试时间为90min科目考试总人数不应超过考场容量：

415004x13xi8000

i22）采取某些合理考试模式下，参加考试时间为120min科目考试总人数不应超过

考场容量：

41500xi3500

i2综上所述，建立模型：

4minzx

ii14s.t.15004x13xi8000

i2

1500xi3500

i24x0

ii142.1.2考场安排

在完成考试时间段安排后，我们引进0-1变量ytbd表示时间t课程b在第d考场考试，取1表示是，取0表示否。其中：

(t,b)Bt,btb1,tT0,b1,2,3,…，100，d1,2,3,…,50

在时间t考场d可能用也可能不用，用0-1变量ztd表示，取1表示是，取0表示否，tT0，d{1,2,3……50}。

目标是在每个考试时间段t，考场的利用率应尽可能高，即所有考场余量尽

50可能少，即mintT0(Pd=1dztd-t,bBRbytbd)。要满足的约束条件为：

501）保证每门课程都有考场，ytbd=1；

d=12）时间t考场d内的考生总数不超过考场容量，即

d{1,2,3……50}，tT0

(t,b)BRbytbdPdztd，

综上所述，建立如下整数规划模型：

50min(PtT0d=1dztd-Rbytbd)

s.t. (t,b)BRbytbdPdztd，d1,2,3……50，tT0

50d=1ytbd=1，tT0，(t,b)B

ytbd0,1，tT0，(t,b)B，d1,2,3……50

ztd=0,1 ，tT0，d1,2,3……50

2.1.3监考教师安排

监考教师的安排属于任务分配问题。第a位教师在t时间段是否监考第d个考场，引进0-1变量用hatd表示，取1表示监考，取0表示否。

目标是要保证各种情况下的教师监考场数尽量平均，也就是监考次数最多的教师与监考次数最少的教师的差值最小，即

T0minmaxat=150T0d=1hatd-minat=1hatd d=150需要满足的约束条件为：

1）在t时间段，第a位教师至多在一个考场监考，即

50hd=1adt1，tT0，a1,2,3,…，120

2）每个考场的监考教师为2人，每个考场的容量为Pd，则在第t时间段，第d个考场的安排的监考教师为：

120ha=1atd=2Pd，tT0，d1,2,3,…，50

3）情况1的监考教师需满足条件监考场数不超过2场，即

T050atdht=1d=110 2，a1,2,3,…，4）情况2的监考教师需满足条件监考场数不超过3场，即

T050atdht=1d=120 3，a11,12,13,…，综上所述，我们建立监考教师安排的模型如下：

T0minmaxat=150T0d=1hatd-minat=1hatd d=15050s.t.

hd=1adt80 1，tT0，a1,2,3,…，80ha=1atd=2Pd，tT0，d1,2,3,…，50

T050atdht=1d=1T05010 2，a1,2,3,…，ht=1d=1atd20 3，a11,12,13,…，hatd0,1，tT0，a1,2,3,…，120，d1,2,3,…，50

2.2模型求解

2.2.1时间安排模型求解

用LINGO求解，程序见附录一，结果显示分别采用考试模式2的考试天数为

2.5。

2.2.2期末考试考场安排

此外，我们发现存在两个时间段一场考试可以安排40个考场进行考试，有一个时间段一场考试可以安排35个考场考试结合人工安排考场。由于我们假设未对有特殊情况的教师安排监考，并且未将剩余20个考场安排考试，即具有975人考场容量。采用人工安排考场，充分利用剩余的考场容量，将考试时间缩短至2天。

用LINGO求解，具体结果见下表。以下给出部分结果：

期末考试考场安排（部分）

考试课程 考试教室 B81 D1,D16 B82 D2,D17 B83 D3,D18 B84 D4，D19 B85 D5，D20 B91 D41，D42 B93 D43，D44 B94 D45，D46 7月1日 8：00-9:30 B95 D47，D48 早上 考试时间 专业 C1，C21 C2，C22 C3，C23 C4，C24 C5，C25 C11，C31 C13，C33 C14，C34 C15，C35 人数 75 75 75 75 75 110 110 110 110 监考老师 A21-A24 A25-A28 A29-A32 A33-A36 A37-A40 A41-A44 A45-A48 A49-A52 A53-A56 四、 评价

我们对这种排课安排进行了评价，用平均考场容量利用率来评价各时间段考场安排的合理程度。平均考场容量利用率P:一天内各时间段内所有考场容量的利用率的平均值。以7月1日为例，可以证明：

100Pt=

Rb150d1bybdt，P=

ddtP1P2P3P4P55

PZ用编程算法得模型一P=83.37%，模型二P=93.089%

（1） 由于模型二的平均考场容量利用率远大于模型一，因此模型二所得监考方

案比较合理，考场利用率均大于90%，对于学校而言是满意的，同时考场利用率高后，老师需要监考的场次数就相对减少了，有利于学校对于监考

老师的安排。

（2） 模型一、二，无法满足监考老师不足的突发状况。

（3） 同时我们发现模型二仅仅为了缩短时间来完成考试，但是现实中我们无法以此来安

排，一味的追求最短化导致监考教师没有时间休息，并且学生没有时间复习与休息。对于这一点正是模型一的优点。

参考文献

[1] 黄勇，苏守宝.一种新的高校自动排考算法[J].计算机技术与发展，2007,17（12）：210-212.

[2] 马慧彬，张忠武，何丽丽.智能型考试安排系统的监考及教室安排算法[J].佳木斯大学学报（自然科学版），2004,22（3）：74-76.

附录：

附录一

表一 合理考试时间模式表

时间段 模式1 模式2 模式3 模式4 附录二

min=x1+x2+x3+x4;

1500*(4*x1+3*(x2+x3+x4))>=8000; 1500*(x2+x3+x4)>=3500; 0上午/min 90；90 90；90 90；120 90；120 下午/min 90；90 90；120 90；90 90；120

Global optimal solution found.

Objective value: 2.333333 Infeasibilities: 0.000000 Total solver iterations: 0

Variable X1 X2 X3 X4

Row 1 2 3 4 Value 0.000000 2.333333 0.000000 0.000000 2.333333 2500.000 0.000000 2.333333 1.000000 0.000000 0.000000 0.000000 Dual Price -1.000000 0.000000 -0.6666667E-03 0.000000

Reduced Cost Slack or Surplus