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

2012河南科技大学大学生数学建模竞赛承诺书我们认真阅读了中国大学生数学建模竞赛和2012河南科技大学大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。姓名学号学院队员一曹航10102060801材料学院队员二李言10102060806材料学院队员三宋婉景10102060808材料学院编号期末考试监考安排摘要本文讨论了期末考试监考安排问题，通过使考场容量最大化来取得时间最短。首先，提出合理假设优先考虑一般情况，由要求写出约束条件，从考试时间安排、监考教师安排、考场安排三个方面，用0-1规划和整数规划建立数学模型，然后用lingo求得其最优解，特殊情况通过人工排考实现。对于问题一，首先，根据考试时间列举出18种合理的阶段安排（见表一），其次，根据附件数据整合出各门课程参加考试的人数（见表二），假设只考虑60位无限制监考的教师，则需30个考场，选择使考场容量最大化为1500，建立相应的监考教师和考场安排模型，再结合人工排考安排有特殊要求的教师，求出最短考试时间是2天，及考场安排表（见表三）。对于问题二允许出现合考，在问题一的基础上加上约束条件即可解，得出最短考试时间为2天，及考场安排表（见表四）。对于问题三，是优化问题，即使考试时间安排尽可能均衡，建立优化目标函数，求解得最短考试时间为6天，及考场安排表（见表五）。另外，我们建立平均考场容量利用率的评价模型来评价考场安排的合理程度，得出本文所建模式的平均考场容量利用率约为93%，此利用率对于一整天而言考场利用率已经较大，但也存在数个考场利用率低于90%的情况，对延长考试总天数产生影响。关键词：列举法 0-1规划模型 整数规划模型一、问题重述1.背景每学期期末,各院系教务人员都要针对学校教务处下达的考试任务进行监考教师安排,但由于学生众多，所在专业不同，所学课程不同，教室资源以及教师能否监考等众多实际问题存在，使考试安排成为一个综合性很强的工作，传统的手工安排方式效率低且容易出错。我们想从数学方面分析该问题，以期能给各院系教务人员有所帮助。 现一天有三个时间段可以考试，上午 8：0011:45，下午 14:2017:30，晚上 19:4521:20。并且一个教室前后2门课程的考试时间间隔不能少于20分钟。周一到周日都可以安排考试。有80位监考老师，其中10位最多能监考两场，10位最多能监考三场，其余60位可以监考无限次。每个考场需要2位老师监考，每位老师的监考次数尽可能的均衡。来自50个专业的学生参加此次考试，总共靠100门课程。其中考试时间为60分钟和120分钟的课程分别有20门，考试时间为90分钟的课程有60门。50个教室可以作为考场，其中15个考场能容纳30名考生，25个能容纳45名考生，10个能容纳60名考生。2.问题1、 假设不能出现合考的情况，即不能把2门不同的课程放在同一考 场一起考试。学校想要在最短的时间内考完所有课程，求出期末考试的最短 时间。并做出期末考试的考场安排表。2、如果允许合考的情况，及可以把不同的课程放到同一考场考试，其他条件不变，求出期末考试的最短时间。3、为了便于学生的期末复习，学校规定每个专业一天只能考试一门课程，并且老师一天最多监考2场，2场考试不能在同一时间段，其他条件不变，求出期末考试的最短时间。并做出期末考试的考场安排表。4、请给各院系教务人员安排期末监考的一些建议，评价一下你的模型的优缺点。二、问题分析 经过分析，监考老师的数量不能使每个考场都能使用，又因为有几位特殊的老师，所以有两次考试是40个考场，一次35个考场，30个考场无限制。对于问题一，在不能合考的情况下，要求考试时间最短。每天的考试可分为了三个大的阶段上午、下午和晚上，其时间经过计算分别为225分钟、190分钟、和95分钟。各个学科的考试时间又可分为60分钟，90分钟，120分钟，为了使考试时间最短，就要将各个时间的课程考试合理的安排到这三个时间段里，共有18种安排情况。对于考场的安排，从如何将每个考场利用率达最大的角度解决该问题，要使每个考场的利用率达到最大，就要使课程占用考场的总容量与该课程的学生差最大的达到最小。对于老师的安排，由于有特殊老师的存在，不容易安排，故将情况简化，先考虑无特殊情况的60名老师，尽量使他们的监考情况均衡，然后再人工安排有特殊情况的另外20名老师，使监考情况更加合理。对于问题二，在问题一的基础上，允许考试合考，这样在安排考场时只需要将相同考试时间的学生安排在一起就可以了。对于问题三，每个专业一天只能考试一门课程，并且老师一天最多监考两场，也就是对于一个专业，不同考试课程最小的时间间隔尽可能大。三、模型假设1. 假设符合各自要求的监考教师都能按时到场。2. 假设安排有考试的考生均能按时到场。3. 假设安排有考试的考场都能正常使用。四、符号说明：表示教师编号（）；：表示课程编号（）；：表示专业编号（）；：表示考场编号（）；：表示某种考试模式（）；:表示安排所有考试的时间段集合，；：表示采用第种考试模式所需天数（）；：表示第门课程在时间是否考试（取1表示是，取0表示否）；：表示第个考场的容量；：表示时间；：表示考第门课程的人数；：表示第考场采用模式；：表示第门课程是否在第个考场考试（取1表示是，取0表示否）；：表示第位教师是否监考第个考场（取1表示是，取0表示否）；：在时间考场是否使用（取1表示有，取0表示否）；：表示第个专业是否有门考试课程（取1表示有，取0表示否）；：表示安排考试的时间段，=1,2,3，12.五、模型建立与求解1. 问题一：在不合考的前提下求出期末考试的最短时间1.1 模型建立1.1.1 考试时间安排考试时间安排的目标是使期末考试时间最短。提出合理假设后，要求有两个：考场容量最大化；考试人数不超过考场容量。因为无特殊要求限制的监考老师为60人，每个考场需用2名监考老师，则可假设使用考场数量为30，使考场容量最大化，选择采用D21-D50，每场考试所有考场可容纳1500人。为满足各个考试时限的考生人数要求，即要求考试人数不超过考场容量。用表示采取第种考试模式（=1,2，18）所用的天数，是非负整数。以采取某些合理考试模式所需的考试天数最少为目标，得到目标函数：，由此得以下约束条件：1）采取某些合理考试模式下，考试时间为60min的考试总人数不超过考场总容量：，2）采取某些合理考试模式下，考试时间为90min的考试总人数不超过考场总容量：，3）采取某些合理考试模式下，考试时间为120min的考试总人数不超过考场总容量：，综上所述，建立模型：， ， ，1.1.2 考场安排考场安排的目标是使考场利用率达到最大。要求有两个：每门课程都有考场；参加考试的考生数不得超过安排的考场容量。引进0-1变量表示第门课程是否在第个考场考试，取1表示是，取0表示否，其中：，。考场安排的目标是每个考场的利用率应尽可能高，即每个考场的余量尽可能少，则得目标函数：要满足的约束条件为：1）保证每门课程都有考场：；2）时间段考场内的考生总数不超过考场容量，即： 综上所述，建立如下整数规划模型：， ,1.1.3 监考教师安排监考教师安排的主要目的是：使监考老师安排尽量平均。主要考虑3个因素：有特殊要求的监考老师监考场数的限制；每个考场需两名监考老师；每个老师在某个时间段内之多在一个考场监考。引进0-1变量，表示第位教师是否监考第个考场，取1表示是，取0表示否。目标是让监考教师的监考场数尽量平均，即监考次数最多的老师与监考次数最少的老师的差值最小，即：需要满足的约束条件有：1）在时间段，第位教师至多在一个考场监考，即， 2）每个考场的监考教师为2人，每个考场的容量为，第个考场的安排的监考教师为：， ， ，1.2 模型求解1.2.1 时间安排模型求解用LINGO求解，程序见附录一，结果显示分别采用考试模式4、16、18的考试天数为1.242、0.125 、0.685 ，共计2.052天。1.2.2 期末考试考场安排此外，我们发现存在两个时间段一场考试可以安排40个考场进行考试，有一个时间段一场考试可以安排35个考场考试结合人工安排考场。由于我们假设未对有特殊情况的教师安排监考，并且未将剩余20个考场安排考试，即具有975人考场容量。采用人工安排考场，充分利用剩余的考场容量，将考试时间缩短至2天。用LINGO求解，具体结果见附录表四。2.问题二 在问题一的基础上允许合考求最短考试时间2.1模型建立与题目一相比，题目二的限制性条件变得更为宽松，不用考虑课程不同考场就不同的问题，只需考虑将不同考试时间的科目安排在不同的考试阶段即可，而问题一已经解决了不同课程不能在同一考场考试的问题，按照问题一的解决模式，将问题分为三个子问题。由于监考教师的限制，在时间段采用30个考场考试的情况最多，只能进行两次40场的考试，一次35场的考试，因此在允许合考的情况下，应充分利用考场D16-D50，以使考场容量最大化。因而，在问题一的基础上，加之如下约束条件：2.1.1时间安排在问题一的基础上，为充分利用监考教师资源，将有特殊情况的教师安排监考。由于考试时间为90分钟的课程所占人数最多，因而将监考教师A1-A20安排于课程B21-B80，从而增加每场考试的考试容量，以缩短考试时间，即有以下约束条件：综上所述，以1.1.1的模型为基础，建立以下优化模型：， ，2.1.2 考场安排在1.1.2的基础上，建立如下整数规划模型：， ， ， 2.1.3 监考教师安排在1.1.3的基础上，我们建立一般情况的监考教师安排的模型如下： ， ， 2.2 模型求解 用LINGO求解，程序见附件二，由结果可见， 采用模式4、16、18的天数分别为1.241667、0.1250000、0.5229167，共计1.889583天。我们得出考试时间共用2天，具体结果如表五所示。3.问题三 优化考试安排3.1 模型建立3.1.1 考试时间安排设为第个专业第门课程的考试时间，其中目标是期末考试时间安排尽可能均衡，以有利于学生复习和水平的发挥，也就是对于一个专业，不同考试课程最小的时间间隔尽可能大，建立目标函数，其约束条件为：1） 每个专业一天至多考一门，即：，2） 对于相同课程不同专业的考试时间相同，即：，综上所述，建立如下模型： ，取整数，3.1.2 考场安排、监考教师安排: 所采用模型同1.1.2与1.1.3。3.2 模型求解 用LINGO求解，具体安排见表六。六、模型评价1、由于监考教师分为三类，本模型仅就一般情况的老师给予编程，余下特殊的两类老师给予人工安排监考，增加了工作量。2、就一二两问题，考虑理想化模型，追求时间最短化，从而增加老师工作量，使学生备考紧张，故不宜在实际中采用。而问题三解决了此问题，使模型更具应用价值。3、由于我们模型严格的容量控制，使得整个考试过程中，考场利用率较大，从而减少考场数，使监考老师监考次数相应减少，有利于对监考老师的安排。4、同时有单独时间段其考场利用率低于90%，例如在复合段内上一时间段到下一时间段人数相差大，例如其中7月2日下午部分考场出现利用率为81.19%的情况。虽然对于一整天而言考场利用率已经较大，但是存在这种利用率低于90%的情况会增加考试总天数。参考文献1 薛毅，数学建模基础，北京：北京工业大学出版社，2005年2 姜启源，数学模型，北京：高等教育出版社，2003年附录：附录一min=x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15+x16+x17+x18;1500*(4*x1+3*(x2+x3)+2*(x4+x5)+x6+5*(x8+x9)+4*(x10+x11)+3*(x12+x13)+2*(x14+x15)+x17)=3725;1500*(x2+x3+2*x4+x6+x8+x9+2*x10+x12+2*x13+3*(x14+x15)+4*x16+2*x17+3*x18)=8400;1500*(x1+x2+x3+x4+2*(x5+x6)+x11+x12+x17+x18)=2050;0=3725;1500*(x2+x3+2*x4+x6+x8+x9+2*x10+x12+2*x13+3*(x14+x15)+4*x16+2*x17+3*x18)+975=8400;1500*(x1+x2+x3+x4+2*(x5+x6)+x11+x12+x17+x18)=2050;0=1);for(course(i):sum(place(j):y(i,j)*d(j)b(i);for(course(i):for(place(j):gin(y(i,j);data:d=30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,45,45,45,45,45,45,45,45,45,45,45,45,45,45,45,45,45,45,45,45,45,45 45,45,45,60,60,60,60,60,60,60,60,60,60;b=205,175,175,175,175,205,220,220,220,220,155,160,160,160,160,180,190,190,190,190,145,145,145,145,145,145,145,145,145,145,145,145,145,145,145,175,175,175,175,175,175,175,175,175,175,175,175,175,175,175,110,110,110,110,110,110,110,110,110,110,110,110,110,110,110,130,130,130,130,130,130,130,130,130,130,130,130,130,130,130,75,75,75,75,75,95,95,95,95,95,110,110,110,110,110,130,130,130,130,130;enddataend附录四：model:sets:teacher/1.60/:a;place/1.50/:d;matrix(teacher,place):h;endsetsmin=sum(teacher(i):sum(place(j):h(i,j)-5,2);for(teacher(i):sum(place(j):h(i,j)=1);for(place(j):sum(tcacher(i):h(i,j)=2);for(teacher(i):for(place(j):gin(h(i,j);end 附录五：表一 合理考试时间模式表时间段上午/min下午/min晚上/min模式1120；6060；6060模式2120；6060；6090模式3120；6060；9060模式4120；6060；9090模式5120；6012060模式6120；6012090模式760；60；6060；6060模式860；60；6060；6090模式960；60；6060；9060模式1060；60；6060；9090模式1160；60；6012060模式1260；60；6012090模式1390；9060；6060模式1490；9060；6090模式1590；9060；9060模式1690；9060；9090模式1790；9012060模式1890；9012090表二 每门课程的考试人数课程B1B2-B5B6B7-B10B11B12-B15B16B17-B20人数/课程205175205220155160180190容30人/课程76764465容45人/课程00011101课程B21-B35B36-B50B51-B65B66-B80B81-B85B86-B90B91-B95B96-B100人数/课程1451751101307595110130容30人/课程56401243容45人/课程00031101表三 期末考试考场安排表考试时间考试课程考试教室专业人数监考老师7月1日 早上8：00-10:00B81D1,D16C1，C2175A21-A24B82D2,D17C2，C2275A25-A28B83D3,D18C3，C2375A29-A32B84D4，D19C4，C2475A33-A36B85D5，D20C5，C2575A37-A40B91D41，D42C11，C31110A41-A44B93D43，D44C13，C33110A45-A48B94D45，D46C14，C34110A49-A52B95D47，D48C15，C35110A53-A56B97D21，D22，D23C17，C37130A57-A62B98D24，D25，D26C18，C38130A63-A68B99D27，D28，D29C19，C39130A69-A74B100D30，D31，D32C20，C40130A75-A8010:20-11:20B1D1,D41,D42,D43C1,C20,C21,C41205A21-A28B7D16，D17，D18, D19, D20C6,C7,C27,C47220A29-A38B9D21, D22, D23, D24, D25C8,C9,C29,C49220A39-A48B5D29，D30，D31，D32C5,C25，C45175A49-A56B13D26,D45,D46C12,C13,C33160A57-A62B19D27,D47,D48，D2C14,C15,C35190A63-A70B17D3,D28,D49,D50C16,C17,C37190A71-A78下午14:20-15:50B21D1,D41,D42C1,C21,C41145A21-A26B24D2,D43,D44C2,C22,C42145A27-A32B27D3,D45,D46C3,C23,C43145A33-A38B30D4,D47,D48C4,C24,C44145A39-A44B33D5,D49,D50 C5,C25,C45145A45-A50B36D16,D17,D18,D19C6,C26,C46175A51-A58B39D20,D21,D22,D23C7,C27,C47175A59-A66B42D24,D25,D26,D27C8,C28,C48175A67-A74B78D28,D29,D30C20,C40130A75-A8016:10-17:10B6D1,D41,D42，D4，D5C5,C6,C26,C46205A21-A30，B8D16，D17，D18, D19, D20C7,C8,C28,C48220A31-A40B10D21, D22, D23, D24, D25C9,C10,C30,C50220A41-A50B12D26,D43,D44C11,C12,C32160A51-A56B14D27,D45,D46C13,C14,C34160A57-A62B18D2,D28,D47，D48C17,C18,C38190A63-A70B20D3,D29,D49，D50C19,C20,C40190A71-A78晚上19:45-21:15B45D16,D17,D18,D19C9,C29,C49175A21-A28B48D20,D21,D22,D23C10,C3O,C50175A29-A36B51D41，D42C11,C31110A37-A40B54D43，D44C12，C32110A41-A44B57D45，D46C13，C33110A45-A48B60D47，D48C14，C34110A49-A52B63D49, D50C15，C35110A53-A56B66D24，D25，D26C16,C36130A57-A62B69D27，D28，D29C17，C37130A63-A68B72D30，D31，D32C18，C38130A69-A74B75D33, D34, D35C19，C39130A75-A80B80D36,D37,D38C20，C40130A11-A167月2日 早上8:00-9:30B22D1,D41,D42C1,C21,C41145A21-A26B25D2,D43,D44C2,C22,C42145A27-A32B28D3,D45,D46C3,C23,C43145A33-A38B31D4,D47,D48C4,C24,C44145A39-A44B34D5,D49,D50 C5,C25,C45145A45-A50B37D16,D17,D18,D19C6,C26,C46175A51-A58B40D20,D21,D22,D23C7,C27,C47175A59-A66B43D24,D25,D26,D27C8,C28,C48175A67-A74B67D28,D29,D30C16,C36130A75-A809:50-11:20B46D16,D17,D18,D19C9,C29,C49175A21-A28B49D20,D21,D22,D23C10,C3O,C50175A29-A36B52D41，D42C11,C31110A37-A40B55D43，D44C12，C32110A41-A44B58D45，D46C13，C33110A45-A48B61D47，D48C14，C34110A49-A52B64D49, D50C15，C35110A53-A56B70D24，D25，D26C16,C36130A57-A62B73D27，D28，D29C17，C37130A63-A68B76D30，D31，D32C18，C38130A69-A74B79D33, D34, D35C19，C39130A75-A80下午14:20-16:20B86D16,D41C6,C2695A1-A4B87D17,D42C7,C2795A5-A8B88D1,D2,D18C8,C2895A9-A14B89D3,D4,D19C9,C2995A15-A20B90D5,D6,D20C10,C3095A21-A26B92D43，D44C12,C32110A27-A30B96D21，D22，D23C16,C36130A31-A3614:20-15:50B23D7,D45,D46C1,C21,C41145A37-A42B56D8,D24,D25C12，C32110A43-A48B59D47,D48C13，C33110A49-A52B68D26,D27,D28C16,C36130A53-A5814:20-15:20B11D9，D10,D29,D30C10,C11,C31155A59-A66B15D49，D50，D31C14,C15,C35160A67-A72B3D32，D33，D34，D35C3,C23,C43175A73-A8015:40-17:10B29D9,D49,D50C23，C43145A59-A64B74D32,D33,D34C18，C38130A65-A70B77D10,D11,D35,D36C19，C39130A71-A7816:10-17:10B2D45,D46C2,C22,C42175A37-A40B4D47,D48C4,C24,C44175A41-A44B16D24,D25,D26,D27C16,C36180A45-A52晚上19:45-21:15B26D1，D41，D42C2,C22,C42145A1-A6B32D2，D45，D46C4,C24,C44145A7-A12B35D4，D47，D48C5,C25,C45145A13-A18B38D16,D17,D18,D19C6,C26,C46175A19-A26B41D20,D21,D22,D23C7,C27,C47175A27-A34B44D24,D25,D26,D27C8,C28,C48175A35-A42B47D28,D29,D30,D31C9,C29,C49175A43-A50B50D32,D33,D34,D35C10,C3O,C50175A51-A58B53D49,D50C11,C31110A59-A62B62D43,D44C14，C34110A63-A66B65D36,D37,D3C15，C35110A67-A72B71D38，D39，D40C17，C37130A73-A78表四 期末考试考场安排表考试时间考试课程考试教室专业人数监考老师7月1日 上午8:00-10:00B81D20-D50C1，C2175A21-A80B82C2，C2275B83C3，C2375B84C4，C2475B86C6，C2695B87C7，C2795B88C8，C2895B89C9，C2995B91C11，C31110B92C12，C32110B93C13，C33110B94C14，C34110B95C15，C35110B96C16，C36130B97C17，C3713010:20-11:20B2D20-D50C1，C2，C22，C42175A21-A80B4C3，C4，C24，C44175B6C5，C6，C26，C46205B8C7，C8，C28，C48220B10C9，C10，C30，C50220B12C11，C12，C32160B14C13，C14，C34160B16C15，C16，C36180 14:20-15:20B1D20-D50C1，C20，C21，C41205A21-A80B3C2，C3，C23，C43175B5C4，C5，C25，C45175B7C6，C7，C27，C47220B9C8，C9，C29，C49220B11C10，C11，C31155B13C12，C13，C33160B19C19，C19，C3919015:40-17:10B24D20-D50C2，C22，C42145A21-A80B27C3，C23，C43145B30C4，C24，C44145B33C5，C25，C45145B39C7，C27，C47175B42C8，C28，C48175B45C9，C29，C49175B48C10，C30，C50175B51C11，C31110B54C12，C32110晚上19:45-21:15B43D15-D50C8，C28，C48175A11-A80B46C9，C29，C49175B49C10，C30，C50175B52C11，C31110B55C12，C32110B58C13，C33110B61C14，C34110B64C15，C35110B67C16，C36130B70C17，C37130B73C18，C38130B76C19，C39130B79C20，C401307月2日 上午8:00-9:30B21D20-D50C1，C21,C41145A21-A80B26C2，C22，C42145B31C4，C24，C44145B34C5，C25，C45145B38C6，C26，C46175B41C7，C27，C47175B47C9，C29，C49175B66C16，C36130B71C17，C37130B74C18，C381309:50-11:20B23D16-D50C1，C21,C41145A1-A80B29C3，C23，C43145B32C4，C24，C44145B35C5，C25，C45145B36C6，C26，C46175B50C10，C30，C50175B53C11，C31110B56C12，C32110B59C13，C33110B62C14，C34110B65C15，C35110B68C16，C36130B77C19，C39130B80C20，C40130下午14:20-16:20B85D41，D16-D27C5，C2575A1-A26B90C10，C3095B98C18，C38130B99C19，C39130B100C20，C4013014:20-15:20B17D1，D28，D42-D43C17，C37190A27-A3414:20-15：50B22D2-D5,D29-D50C1，C21,C41145A35-A80B25C2，C22，C42145B28C3，C23，C43145B37C6，C26，C46175B40C7，C27，C47175B57C13，C33110B60C14，C3411015:40-17:10B44D1，D28，D42-D43C8，C28，C48175A27-A3416:10-17：10B15D29-D50C14，C15，C35160A35-A58B18C17，C18，C38190B20C19，C20，C40190晚上19:45-21:15B63D41-D50,D1C15，C35110A21-A42B69C17，C37130B72C18，C38130B75C19，C39130B78C20，C40130表五 期末考场安排考试时间 考试课程考试教室专业人数监考老师7月1日上午8：00-9:00B2D41,D42,D43C1,C2,C22,C42175A1-A6B12D44,D45,D16C11,C12,C32160A7-A129:20-10:50B27D41,D42,D16C3,C23,C43145A13-A18B30D43,D44,D17C4,C24,C44145A19-A24B35D45,D46,D18C5,C25,C45145A25-A30B37D47,D48,D49C6,C26,C46175A31-A36B60D19,D20,D21C14,C34110A37-A42B64D22,D23,D24C15,C35110A43-A48B79D50,D25,D26C20,C40130A49-A54下午14:20-15:55B40D41,D42,D43C7,C27,C47175A