期末考试监考安排数学建模论文

2012

年河南科技大学数学建模竞赛选拔承

诺

书我们仔细阅读了数学建模竞赛选拔的规则.我们完全明白，在做题期间不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人研究、讨论与选拔题有关的问题。我们知道袭别人的成果是违反选拔规则的如果引用别人的成果或其他公开的资料（包括网上查到的资料须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺严格遵守选拔规则以保证选拔的公正、公平性。如有违反选拔规则的行为，我们将受到严肃处理。我们选择的题号是（从A/B/C中选择一项填写A队员签名：1.2.3.

谷胜辉高健人任娟日期：2012

年8月16日

2012年南技学学模赛拔编专用页期末考试监考安排摘要期末考试安排是教务管理中一项重要而复杂的工作。传统的手工安排方式效率低，现考虑利用建立数学模型与人工相结合的方法来分析研究监考问题。从已给问题的布局，构思出以下方案：首先采用枚举法分析得出十八种合理的时间分配方案，利用Lingo软件优化得出最优时间分配组合。鉴于考场容量有限和考试安排时间最短的考虑，在考试时间与考试课程之间建立一个线性规划模型，并利用软件进行优化求解，得出考试时间的最优分配方案。另以最大考场利用率为目标，在有限的考场容量基础上，在考试课程与考场之间建立一个规划模型，利用Lingo软件进行优化求解，得出考场分配的优化方案。其次以每位监考老师监考场数尽量平均为目标，在监考老师监考场数的限制的基础上在监考老师的分配问题上建立一个规划模型，利用Lingo软件优化求解，得出教师的优化分配方案。最后依据平均考场容量的利用率来判断模型的好坏模型检验得出平均考场容量的利用率均达到以上但针对于实际情况来讲平均考场容量利用率高并不一定最优，同时需要对模型求得的结果进行一定的人工改进，建议各院系的教务人员在监考安排中采用数学模型与实际相结合的方法。本文对问题的解决原则：在合理简化的基础上，对题目的每个要求，都做到“有数学依据，有理论支撑，力求完善关键词：枚举法、线性规划模型、0-1规划模型、软件1.背景每学期期末，各院系教务人员都要针对学校教务处下达的考试任务进行监考教师的安排，传统的手工安排方式效率低且容易出错。我们想从数学方面分析该问题，以期能给各院系教务人员有所帮助，假设某学院期末考试现有的监考教师、考试课程、各专业及人数、教室情况如下：（1）考试时间一天分三个时间段：上午8：00——11:45下午14:20——17:30晚上19:45——21:20一个教室前后2门课程的考试时间间隔不能少于分钟。周一——周日都可以安排考试。期末考试开始时间为2013年1月6日。

（2）监考教师共有80为监考教师分别是A1……A80监考教师分为3种情况情况1：A1——A10是教授，学校规定教授监考不能超过场；情况2：A11——A20是有特殊情况的教师，其监考不能超过场；情况3：A21——A80教师的监考场数没有限制。每个考场需要2位监考教师。在安排监考的时候要保证各种情况下的教师监考场数尽量平均。（3）考试课程共有100门考试课程，分别是B1，B2，……B100，考试课程分为3种情况。情况1：B1——B20，考试时间需要60分钟；情况2：B21——B80，考试时间需要90分钟；情况3：B81——B100，考试时间需要120分钟。（4）参加考试各专业，人数，所学课程共有50个专业，分别是，C2，……C50。各专业的人数，参加考试的课程见附件1的excel格。假设每个专业内的学生所选的课程一致。（5）能够作为考场的教室情况共有50个教室可供选择，分别是D1，D2，D3……D50，教室分为3种情况。情况1：D1——D15，可以容纳30人考试；情况2：D16——D40，可以容纳45人考试；情况3：D41——D50，可以容纳60人考试。2.问题：（1）假设不能出现合考的情况，即不能2门不同的课程放在同一考场一起考试。学校想要在最短的时间内考完所有课程，求出期末考试的最短时间。并做出期末考试的考场安排表，表格可以为excel者word格式。（2）如果允许合考的情况，及可以把不同的课程放到同一考场考试，其他条件不变，求出期末考试的最短时间。并做出期末考试的考场安排表。（3）为了便于学生的期末复习，学校规定每个专业一天只能考试一门课程，并且老师一天最多监考2场场考试不能在同一时间段他条件不变出期末考试的最短时间。并做出期末考试的考场安排表。（4）请给各院系教务人员安排期末监考的一些建议，评价一下你的模型的优缺点。由于考试分为上午、下午、晚上三个时间段，考试课程的考试时间又分为分钟、90分钟、120分钟三种情况，所以首先应该确定在各个时间段的考试课程的分配情况，合理的考试时间方案应满足除考试时间剩余时间不能超过某门课程的考试时间，且对于一个教室前后2门课程的考试时间间隔不能少于20分钟应用枚举法列出所有的合理考试时间方案，共十八种，如下表一所示：表一合理考试时间方案表时间段

上午/分钟下午/分钟晚上/分钟方案一方案二方案三方案四

60,60,6060,60,6060,60,6060,60,60

60,9060,90120120

90609060

方案五方案六方案七方案八方案九方案十方案十一方案十二方案十三方案十四方案十五方案十六方案十七方案十八

60,60,6060,60,60120,60120,60120,60120,60120,60120,6090,9090,9090,9090,9090,9090,90

60,6060,6060,9060,9012012060,6060,6060,9060,9012012060,6060,60

9060906090609060906090609060之后再考虑监考老师的分配问题，受监考老师人数的限制每场考试最多安排四十个考场进行考试，对于问题二，在允许合考的情况下应充分利用考场的资源，从而使考试时间尽可能的短。对于问题三，由于学校规定每个专业一天只能考试一门课程，所以应让考试课程最多的专业每天都能考一门，这样才能尽早的考完。1.假设对于含有同一门课程的专业，在该课程考试时含有该课程的专业同时考试；2.所有考生都按时到场考试；3.所有考场的考试都正常进行；b：表示课程编号，a=1,2…，100；c：表示专业编号，c=1,2…，50；d：表示教室编号，也即考场编号，，…，50；i：表示考试模式编号，i=1,2…，18；v：表示第d个考场的容量；dB：表示第b门课程是否在t时间段考试（是为，否为0btR：表示第b门课程的人数；bx：表示采用第i种考试模式所用的天数；iD：表示第d个考场采用第i种考试模式；diT:表示安排所有考试的时间段集合，T；0T：表示第a位教师在t时间段是否监考d考场（是为1，否为0atdz：表示在t时间段d考场是否使用（是为1，否为0tdy：表示在t时间段课程b是否在d考场考试（是为1，否为0tbdA：表示第c个专业是否有课程b（是为1，否为0cbT：表示安排考试的时间段，T=1,2，…，12；

5050050050050500500500问题一在不能出现合考的情况下求解：1.模型建立（1）考试时间的分配假设未对有特殊限制的监考教师分配监考任务，因为没有特殊限制的监考教师有人，每个考场需要两位监考教师，所以同一个时间段最多30个考场进行考试，为了保证参加考试的人数尽可能的多，30个考场我们取为D21-D50（其中D21-D40容量为45人，D41-D50容量为60人），即每场考试可同时容纳人进行考试，分别根据60分钟、90分钟、120分钟总人数不能超过考场容纳人数的限制，可得如下线性规划模型：其中目标函数min（2）考场安排

i

x,i

i

Nx表示采用第i种考试模式所用的天数。iy首先引进0-1变量tbd表示在t时间段课b是否在d考场考试（是取1，否取0d=1,2，…50。再引0-1变B表示第b门课程是否在t时间段考试（是1，否为bt0令yB{y|BT,b1,2,...,100}。由于t时间段d考场可bt0能用也可能不用，于是再引进变z表示在t时间段d考场是否使用（是为，否为0中Td1,2,...,50。由于目标是使在t时间段考场的利用率尽可能的高，也即所有考场的余量尽可能的少，所以目标函数

vd

Ryb

。tdy0bt因为每门课程都要有考场时间段t考场d内的考生总数不能超过考场的总容量，所以可以建立如下整数线性规划模型：其中目标函数

vd

Ryb

)td（3）监考教师的安排

ybt监考教师的安排是一个分配问题了解决该问题先引入变量师在t时间段是否监考d场（是为1，否为0

表示第a位教atd由于一个监考教师在一个时间段至多只能在一个考场监考，所以在时间段第a位教师至多只能在一个考场监考，

atd

1。d因为情况一的监考教师要求监考的场数不能超过场，所以

T

2,1,2,...,10td因为情况二的监考教师要求监考的场数不能超过场，所以

T

3,a11,12,...,20。td因为每个考场的监考教师为2人z表示在t时间段d考场是否使用（是为，否为0在t时间段第d个考场安排的监考教师应满足

Tatd

ztTd1,2,...,50。tda

要保证各种情况下的教师监考场数尽可能平均，只需使监考次数最多的教师与监考

50505050500bt505050505050500bt5050次数最少的教师的差值最小即可，

T

min

T}于是监考教师安排的数学模型如下：

td0

td0目标函数

T

min

T}2.模型求解

td0

td0（1）考试时间的分配模型求解用lingo求解，程序见附录一，结果显示分别采用考试模式、13的考试天数为、，共计天。（2）考场安排模型求解由于我们上述假设未对有特殊限制的监考教师分配监考任务并且未将剩余的个考场安排考试。再采用人工安排考场，充分利用剩余的考场容量合理分配将1）的结果整数化2天即可。用lingo求解，编写的程序如下附录三所示由于运行结果过于庞杂在此不再显示，考试安排详细结果见附表一。问题二在允许合考的情况下，在问题一的基础之上求出期末考试的最短时间1.模型的建立由于受监考教师人数的限制，在同一个时间段最多可以40个考场考试，因此在允许合考的情况下应充分利用考场考场容量尽可能的大因而在问题一的基础之上加上下述条件即可：（1）考试时间的分配在问题一的基础之上，为了尽可能充分的利用监考教师资源，有特殊情况的监考教师也要进行监考，由于考试时间90分钟的课程较多，为了尽可能的增加每场考试的容量将监考教师A1-A20分配给课程进行监考，以缩短考试时间，约束条件如下：综上可建立如下优化模型：其目标函数min

18

x,xi

i

（2）考场安排

i在问题一考场安排的基础上建立如下的模型：其目标函数为

vzdtd

yb

)td（3）监考教师的安排

y在问题一监考教师的安排的基础上建立如下的模型：其目标函数

T

min

T}3.模型求解

td0

td0（1）考试时间的分配模型求解用lingo求解，程序见附录二，结果显示分别采用考试模式、13的考试天数为、、，共计天。我们得出考试时间共2天，根据问题一的解法求解，在此不再赘述，具体结果见附表二。问题三规定每个专业一天只能考试一门课程，并且老师一天最多监考场，2场考试不能在同一时间段，其他条件不变，求期末考试的最短时间1.模型的建立

bb（1）考试时间的分配bbt为第c个专业第b门课程的考试时间，其中cbMI{M|Ac1,2,...,50,b了使期末考试时间安排cb尽可能平衡，以便使学生可以更好地发挥，只要使同一专业不同考试课程最小的时间间隔尽可能的大即可，于是建立如下目标函数：因为每个专业一天至多考一门所,I,MIcb21cb2112因为对于相同课程不同专业的考试时间相同，cMIM。cbcb12cbcb1212综上所述可以建立如下模型：目标函数maxt),M2121（2）考场安排、监考教师安排

1

I,M

2

I考场安排、监考教师安排模型同问题一中的考场安排、监考教师安排。2.模型求解用lingo求解，方法同问题一，在此不再赘述，具体结果见附表三。对于本问题，我们采用平均考场利用率来对模型进行评价，平均考场的利用率越高_说明模型越好。设平均考场利用率p平均值，则计算方法如下：

表示一天内各个时间段所有考场容量的利用率的经过对问题一到三的考试安排进行计算可知平均考场的利用率都在上不再一一计算。虽然模型都是按照在最短时间内考完所有的课程进行计算的，但其计算结果仅是个理论值，在实际的期末考试监考安排时上述模型得出的结果并不一定为最优，在实际的期末考试监考安排时应该将模型与实际情况相结合，这样才能达到最优的效果。各院系的工作人员在对期末考试监考安排时，为了达到良好的效果应先根据模型进行计算再在得出的结果的基础上进一步根据实际情况做必要的改动，这样势必会减少工作人员的工作量，而且可以达到良好的效果，使考试安排更为合理。这样教师和同学都会对考试的安排感到满意，使考试可以顺利圆满的进行。[1]谢金星，薛毅.优化建模与软件，天津大学出版社，2005[2]数学建模与应用，国防工业出版社[3]姜启源，叶俊.数学模型（第三版），高等教育出版社附录一min=x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15+x16+x17+x18;1500*(4*x1+5*x2+3*x3+4*x4+5*x5+6*x6+2*x7+3*x8+x9+2*x10+3*x11+4*x12+x13+2*x14+x16+2*x17+3*x18)>=3725;1500*(2*x1+x2+x3+x5+2*x7+x8+x9+x11+4*x13+3*x14+3*x15+2*x16+3*x17+2*x18)>=8400;1500*(x3+x4+x7+x8+2*x9+2*x10+x11+x12+x15+x16)>=2050;x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15+x16+x17+x18>0;Globaloptimalsolutionfound.Objectivevalue:Infeasibilities:

Totalsolveriterations:3ModelClass:LPTotalvariables:18Nonlinearvariables:0Integervariables:0Totalconstraints:5Nonlinearconstraints:0Totalnonzeros:77Nonlinearnonzeros:0VariableValueReducedCostX1X2X3X4X5X6X7X8X9X10X11X12X13X14X15X16X17X18RowSlackorSurplusDualPrice12345附录二min=x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15+x16+x17+x18;1500*(4*x1+5*x2+3*x3+4*x4+5*x5+6*x6+2*x7+3*x8+x9+2*x10+3*x11+4*x12+x13+2*x14+x16+2*x17+3*x18)>=3725;1500*(2*x1+x2+x3+x5+2*x7+x8+x9+x11+4*x13+3*x14+3*x15+2*x16+3*x17+2*x18)+975>=8400;1500*(x3+x4+x7+x8+2*x9+2*x10+x11+x12+x15+x16)>=2050;x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15+x16+x17+x18>0;Globaloptimalsolutionfound.Objectivevalue:Infeasibilities:

Totalsolveriterations:3ModelClass:Totalvariables:18Nonlinearvariables:0Integervariables:0Totalconstraints:5Nonlinearconstraints:0Totalnonzeros:77Nonlinearnonzeros:0

LPVariableValueReducedCostX1X2X3X4X5X6X7X8X9X10X11X12X13X14X15X16X17X18RowSlackorSurplusDualPrice12345附录三Lingo求解程序如下：model:se