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

2012高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： A 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 河南科技大学 参赛队员 (打印并签名) ：1. 刘亚军 2. 冯雪玲 3. 高森祺 指导教师或指导教师组负责人 (打印并签名)： 日期： 2012 年 8 月 18 日赛区评阅编号（由赛区组委会评阅前进行编号）：302010高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：A题:期末考试监考安排摘要 本文从数学方面分析考场安排的问题，通过分析考场要求，设置一些基本假设，确立约束条件。再通过对附表数据的分析计算，找出课程、专业之间的一些规律并结合人工排考，从时间安排，考场安排，监考安排三个方面建立数学模型，进而逐步解决考试时间，考试课程，考试教室及监考老师的问题，使资源更合理利用。对于问题一、二，根据条件得知同一考试科目不同专业要在同一时间进行考试，再对所要考试的课程分析可知：所有考试课程总体上可根据考试所需时间分为三大类。为了使得考试时间最短，可以合理分配三大类课程的时间，使时间利用率和考场利用率在满足监考考试的要求的情况下最大化。通过利用Lingo软件优化再结合手工排考得出对于问题一的最短考完时间为两天半，对于问题二的最短考试时间为两天。具体安排见正文表格。针对问题三，为了便于期末考试复习，每个专业一天只能考试一门课程，并且老师一天最多监考2场，2场考试不能在同一时间段，让拥有最多类课程的专业每天都正好考试一门课，则考完全部课程最少需要六天时间，由问题一及问题二的结果可推知，利用六天时间考完所有课程时间基本上充足。在课程考试安排分配相对均匀的情况下，教室的数量及教师的安排可应满足每天内部最优化，使其在满足学校规定的要求前提下，最大化合理利用。因此对于问题三的解决的核心应放在如何合理安排每天所考的课程以避免任一专业的考生在一天内考试两门课。通过对附表一的研究对课程分组及利用Lingo规划求解再结合手工安排出具体的考试时间场地及监考老师安排表。关键字：约束条件 规律 分析计算 时间利用率 考场利用率 人工排考 课程分组 lingo优化规划问题重述 每学期期末,各院系教务人员都要针对学校教务处下达的考试任务进行监考教师安排,传统的手工安排方式效率低且容易出错。现在要从数学方面分析该问题，以期能给各院系教务人员有所帮助，已知某学院期末考试现有的监考教师为80人，并且老师分为三种不同的情况，一共有100门考试课程，他们所需时间基本分为三种类型，即60min、90min、120min，该校一共有50个专业，人数以及各专业所学课程已经统计出来，供考试用的一共为50个教室，每个考场最多容纳人数都已调查清楚，并且每天可以进行三时间段的考试，上午的时间为8:00-11:45，下午的时间为14:20-17:30，晚上的时间为19:45-21:20。为了使得考试效率最高，因此，可以根据这些数据建立一个最优模型从而能准确快速的分配考场以及监考教师，使得考试时间最短。要探讨在这些条件下建立一个合理模型使得考试在最短时间内结束，我们需要完成以下问题：1、在假设不能出现合考的情况下，即不能把2门不同的课程放在同一考场一起考试，采用Lingo软件，运用规划的方法合理的规划处模型，使得在最短的时间内考完所有课程，并算出最短的时间。2、现在如果允许合考，及可以把不同的课程放到同一考场考试，在其他条件不变的情况下，运用Lingo最优化模型作出最优模型，并做出期末考试的考场安排表。3、在掌握了前面的模型后，考虑到便于学生的期末复习，学校规定每个专业一天只能考试一门课程，并且老师一天最多监考2场，2场考试不能在同一时间段，在其他情况不变的情况下，建立规划，讨论求解，做出规划，求出考场安排。4、根据建立的最优模型，以及自己模型的特点，和各院系教务人员进行交流，并给与他们安排期末监考的一些建议，最后根据实际情况以及模型的特点评价一下自己的模型的优缺点，便于教务人员更好地改进。问题分析考试安排问题是一个复杂的问题，从题目所给的条件以及表格可以看出：1、不同的专业所学习的课程基本呈规律排布；2、夜晚考试的课程是所需时间是60min或90min的课程；3、每个监考老师监考次数应在满足条件限制的前提下尽量平均；4、同一专业不能同时进行不同的考试，以避免冲突;5、选有同一课程的不同专业必须同一时间考试。第一步：进行考试课程的分配，以使得课程考试在最短的时间内结束。为了使得考试尽快结束，可以规划使得每个时间段考试课程最大化，使时间利用率最高。为了避免课程的冲突进行条件约束，条件要求：1、不同的专业相同的课程要同一时间考试；2、相同的专业不同的课程不能同时进行考试；3、考试时间不能与规定的时间违背。根据这些条件进行最优化规划，运用lingo编程求解，可以计算出最优考试科目的安排。第二步：在课程得到合理分配以后，进行考场最优分配。在第一步的基础上根据考场的容纳人数进行分配，尽量使得每个教室的空位最少，即每个教室的空位率最少，使得考场在满足条件的前提下占用最少，避免教室不够用这一情况。即每组所用的考场数目的容量大于考试人数。根据老师的数目限制可以看出最多只能安排40个考场，定义目标函数，提出约束条件，进行最优化分析，利用lingo软件进行求解，得到最优解。第三步：考场以及科目都安排合理的情况下合理安排监考教师。在前两步的基础上进行教师的安排，教师安排时依据教师的特殊要求进行合理分布，使得在满足教师特点要求的情况下，教师的监考场数基本持平，避免分歧。以上面的三步为基础对问题一、二、三进行逐步分析，可以看出问题二是在问题一的基础上进行改进，三是在一、二的基础上提出更为为合理的要求，对三个不同的问题分别进行条件分析，建立合理模型，安排好考试。对模型提出合理的假设，分析模型的特点以及实际情并提出意见，进而完善模型。模型假设1、假设考场数量以及老师都没用变动，学生没用缺考等现象2、假设考试都是从每个时间段的最早开始，没用推迟等问题的出现3、假设所用的学生都服从安排，老师都按指定的分配任务执行4、假设教室桌位是隔开的，即题目给出的容纳人数为按考试座位的人数5、假设所有考场都能进行考试，没有不能用的教室符号说明t：考试时间段，t=1，2，3分别表示225min、190min、95mini：专业编号，i=150J：课程编号，j=1100Ak：监考老师，其中k=180Bj：第j门考试课程Pi：第i专业的人数Rj：学习第j门课程的人数Dl：表示第l个教室Xm：第m类课程出现的次数，即将所有专业分为m类，m=1,2,3分别表示考试所需时间为60min、90min、120min）Aji：第i个专业是否有第j门考试课程（取1时表示有，取0时表示没有）Tji：第i各专业第j门课程考试时间 a：第一类考场，即可容纳30人的教室，a=D1D15b：第二类考场，即可容纳45人的教室，b=D16D40c：第三类考场，即可容纳60人的教室，c=D41D50模型建立及求解问题一：要研究在不出现合考的情况下，使得在最短的时间内完成所有的考试课程。即最充分的利用时间，时间浪费最少。同时需要考虑同一课不同专业的学生必须在同一时间段考试，又不能出现考试冲突，即杜绝某一考生需要在同一时间点进行不同的考试。为了讨论的需要，这里认为每天考试科目越多时间利用率越大，考完全部科目所需要的时间越短。可以以课程为变量对时间优化，因此需要先求每门课程参加考试的人数。根据题中附表的数据整理得出各个课程要考核的人数如下（此处只挑部分展出，具体的表格见附录）：课程专业人数B1C1C21C41C20205B2C2C22C42C1175B91C31C11110B92C32C12110B93C33C13110B94C34C14110B95C35C15110B96C36C16130B97C37C17130B98C38C18130B99C39C19130B100C40C20130 根据表格以及数据，考虑到要避免考试冲突，将课程按专业要求分类，并进行优化，得出不同课程的数据，进行整理得出：课程人数a（30）b（45）c（60）剩余座位B1、B62051035B17-B201901125B2-B51750035B7-B102200135B1115501210B12-B151600125B161800030B21-B351451025B36-B501750035B51-B65B91-B9511000210B96-B100B66-B801301115B81-B85751100B86-B909501110下面建立优化模型： 为了使得考试总共所需时间最短，即每天进行的考试课程最多，其中=（i,j）|Aji=1，i=1,250，j=1,2100，即Max Xm1+Xm2+Xm3 需要满足约束为：1） 每天每个时间段的考试时间不得超过规定的时间，即 2） 对于课程j，不同专业考试时间应相同，即 =，,3） 对于同一专业，不同课程不能同时考试，即 ， 综上所述，建立如下优化模型： Max Xm1+Xm2+Xm3 =，, ， Xm1、Xm2、Xm3取整数，利用所给数据，应用lingo软件进行编程求解（编程见附录）。得出结果为：Objective value: 6.000000 Extended solver steps: 0 Total solver iterations: 0 Variable Value Reduced Cost X1 3.000000 -1.000000 X2 2.000000 -1.000000 X3 0.000000 -1.000000 X4 0.000000 -1.000000 X5 0.000000 -1.000000 X6 1.000000 -1.000000 X7 0.000000 -1.000000 X8 0.000000 -1.000000 X9 0.000000 -1.000000 Row Slack or Surplus Dual Price 1 6.000000 1.000000 2 5.000000 0.000000 3 50.00000 0.000000 4 5.000000 0.000000由所求的结果可知对于上午的时间段t1：全部进行考试时间为60分钟的课由程考试，此时可以使在单位时间内考的科目最多。根据所得数据决定先对考试时间为60分钟的课程进行优先安排，考虑到不能出现考试冲突，通过观察附件一的数据得出结论，即对于编号为前20的课程要想避免考试冲突只需要在安排考试的时候不要将编号相邻的课程排在同一时间段即可，同时由分析可知对于第一天上午的考试可先对编号为前20的课程分为三个时间点考试，利用模糊聚类的方法分为M1 ，M2，M3三个小组的考试，运用lingo编程求解得出（见附录）：其中M1组所考课程包括：B2 、B4 、B7 、B11 、B13 、B15 、B18 ；M2组所包括考科目为：B3、 B5 、B9 、B12、 B14 、B16、 B20；M3组科目为：B1 、B6 、B8 、B10 、B17 、B19。可以使所分的课程满足考试不冲突的前提下，每组所参加考试的人数接近相等。这样可以使考场的占有最小，节省出来的考场可以用作考其他小组的课程考试，从而使教室的利用率最大，进而尽快结束考试。建立优化模型：min 由Lingo进行编程规划（编程见附录），得出结果为： Variable Value Reduced Cost XB2 6.000000 30.00000 YB2 0.000000 45.00000 ZB2 0.000000 60.00000 XB4 0.000000 30.00000 YB4 0.000000 45.00000 ZB4 3.000000 60.00000 XB7 0.000000 30.00000 YB7 1.000000 45.00000 ZB7 3.000000 60.00000 XB11 0.000000 30.00000 YB11 1.000000 45.00000 ZB11 2.000000 60.00000 XB13 4.000000 30.00000 YB13 1.000000 45.00000 ZB13 0.000000 60.00000 XB15 0.000000 30.00000 YB15 1.000000 45.00000 ZB15 2.000000 60.00000 XB18 5.000000 30.00000 YB18 1.000000 45.00000 ZB18 0.000000 60.00000 a 15.00000 0.000000 b 5.000000 0.000000 c 10.00000 0.000000根据结果可以得知M1组所需a类考场为15间，b类考场5间，c类考场10间。同M1再分别对M2,和M3组的考场最优化分配，整理可得：课程小组考场类别abcM115510M212168M315139 由所得的结果可知在第一天上午考完编号为前20科目的同时，可以在上午的考试中还可以进行其它考试时间的课程，以使得教室得到充分利用，以减少考试时间，为了避免教室冲突，通过对所得结果的分析整理可以看出当以M3组所需教室的最优分配为主时，可以同时满足M1、M2组所需教室的用量。 根据结果可以看出课程B2需要教室数目为：0,0,3。即需要3个C类教室。其他的课程根据此进行优化求解，并且依据老师的要求安排老师，（具体编程见附录），对结果整理得出：分组类别考试时间包含课程教室监考教师a类b类c类M1 8:00 9:00B2D41、D42、D43A21-A26B4D44、D45、D46A27-A32B7D16D47、D48、D49A33-A40B11D1、D2、D3、D4D17A41-A50B13D5、D6、D7、D8D18A51-A60B15D9、D10、D11、D12D19A61-A70B18D13D20、D21、D22、D23、D24 A71-A80、A11-A12M2B3D41、D42、D43A21-A269:2010:20B5D44、D45、D46A27-A32B9D16D47、D48、D49A33-A40B12D1、D2、D3、D4D17A41-A50B14D5、D6、D7、D8D18A51-A60B16D9、D10、D11、D12、D13、D14A61-A72B20D15D19、D20、D21、D22、D23 A73-A80、A13-A16M310:40 11:40B1D1D41、D42、D43A21-A28B6D2、D3、D4、D5、D6、D7、D8A29-A42B8D16D44、D45、D46A43-A50B10D9、D10、D11、D12、D13、D14D17A51-A64B17D18、D19、D20D47A65-A72B19D15D21D48、D49A73-A80对于第一天下午的考试安排与上午类似，进行最优规划，整理得到：课程程考试时间教室类别abc教师 B81-B8514:2016:20D1、D2、D3、D4、D5D16、D17、D18、D19、D20A21-A40B86-B90D21、D22、D23、D24、D25D41、D42、D43、D44、D45A41-A60B91D6D26、D27A61-A66B96-B100D7、D8、D9、D10、D11D28、D29、D30、D31D46、D47、D48、D49、D50A67-A80、A11-A20、A1-A4根据前面的规律以及规划得到后期考试的安排如下：课程时间教师教室abc教师B2419:4521:15（第一天）D1D41、D42A21-A26B30D16、D17、D18、D19A27-A34B36D43、D44、D45A35-A40B42D46、D47、D48A41-A46B48D20、D21、D22A47-A52B54D49、D50A53-A56B60D23、D24、D25A57-A62B66D26、D27、D28A63-A68B72D29、D30、D31A69-A74B78D32、D33、D34A75-A80B218：009：30(第二天)D16、D17D41A21-A26B27D18、D19、D20、D21A27-A34B33D22、D23D42A35-A40B39D43、D44、D45A41-A46B45D46、D47、D48A47-A52B51D24、D25、D26A53-A58B57D49、D50A59-A62B63D27、D28、D29A63-A68B69D30、D31、D32A69-A74B75D33、D34、D35A75-A80B229：5011：20（第二天）D16、D17D41A21-A26B28D18、D19、D20、D21A27-A34B34D22、D23D42A35-A40B40D43、D44、D45A41-A46B46D46、D47、D48A47-A52B52D24、D25、D26A53-A58B58D49、D50A59-A62B64D27、D28、D29A63-A68B70D30、D31、D32A69-A74B76D33、D34、D35A75-A80B928:0010:00（第二天）D1D36、D37 A17-A20、A5-A6B93D2D38、D39 A7-A10、A1-A2B2314:2015:50（第二天）D1D41、D42A21-A26B29D16、D17、D18、D19A27-A34B35D20、D21、D22、D23A35-A42B41D43、D44、D45A43-A48B47D46、D47、D48A49-A54B53D24、D25、D26A55-A60B59D49、D50A61-A64B65D27、D28、D29A65-A70B71D30、D31、D32A71-A76B77D33、D34、D35 A77-A80、A3-A4B9414:2016:20(第二天)D1D36、D37 A5-A10B95D2D38、D39A11-A16B2519:4521:15(第二天)D1D41、D42A21-A26B31D16、D17、D18、D19A27-A34B37D20、D21、D22、D23A35-A42B43D43、D44、D45A43-A48B49D46、D47、D48A49-A54B55D24、D25、D26A55-A60B61D49、D50A61-A64B67D27、D28、D29A65-A70B73D30、D31、D32A71-A76B79D33、D34、D35 A77-A80、A17-A18B268:009;30(第三天)D1D41、D42A21-A26B32D16、D17、D18、D19A27-A34B38D20、D21、D22、D23A35-A42B44D43、D44、D45A43-A48B50D46、D47、D48A49-A54B56D24、D25、D26A55-A60B62D49、D50A61-A64B68D27、D28、D29A65-A70B74D30、D31、D32A71-A76B80D33、D34、D35 A77-A80、A19-A20根据模型结果看出在不合考的情况下，为了满足所有的限制条件，并使得考试在最短时间内进行，至少需要进行2天半，时间等具体排列如上表所示。问题二 在允许合考的情况下，依据问题一的思路求出最短时间。因为允许合考，所以应充分利用D16D50，使考场容量最大化，进而达到考试时间最短的目的。 在前面求解过程中，已将考试时间为60min的课程分为3类：M1、M2、M3。为了更好地利用教室资源，运用Lingo 对M1，M2，M3进行最优规划 （在此只对M1进行举例，M2、M3详见附录）。对M1建立优化模型：Min a+b+cM1编程如下：min=a+b+c;30*a+45*b+60*c-1235=0;a+b+c=0;bnd(0,a,15);bnd(0,b,25);bnd(0,c,10);gin(a);gin(b);gin(c);结果：Global optimal solution found. Objective value: 28.00000 Extended solver steps: 0 Total solver iterations: 3 Variable Value Reduced Cost A 0.000000 1.000000 B 18.00000 1.000000 C 10.00000 1.000000 Row Slack or Surplus Dual Price 1 28.00000 -1.000000 2 35.00000 0.000000 从结果可以看出，60人的教室得到了充分的利用，由于现在可以合考，进而所需时间大大减少。通过lingo求解以及人工排考得知只需要两天时间就能考完，可以充分利用每天的各个时间段，即同一时间段进行不同的科目考试，此时时间利用率将达到最高。由第一题的分析得到课程的分类，在此基础上进行不同类型课程的合理排布，使得教室利用率最高，进而使得时间最短，通过lingo以及人工排考方式求出最佳排列方式，整理得出表格:课程时间考场教室abc教师 B82-B90、B92-B1008:0010:00D1D4D16D40D41D50A1-A80B2、B4、B7、 B11、B13、B15、B1810:2011:20D16D30D41D50A21-A70B24、B30、B36、B42、B48、B54、B60、B66、B72、B7814:2015:50D16D34D41D50A21-A78B3、B5、B9、B12、B14、B16、B2016:1017:10D16D29D41D50A21-A68B81、B9114:2016:20D35D38A79-A80、A1-A5B25、B31、B37、B13、B19、B55、B61、B67、B73、B7919:4521:15D16D34D41D50A21-A78B26、B32、B38、B44、B50、B56、B62、B68、B74、B808:009:30D16D34D41D50A21-A78B21、B27、B33、B39、B45、B51、B57、B63、B69、B759:5011:20D16D33D41D50A21-A76B22、B28、B34、B40、B46、B52、B58、B64、B70、B7614:2015:50D16D33D41D50A21-A76B1、B6、B8、B120、B17、B1916:1017:10D16D29D41D50A21-A68;B23、B29、B35、B41、B47、B53、B59、B65、B71、B7719:4521:15D16D33D41D50A21-A76根据表格可以看出最快需要两天的时间，并且老师监考次数满足要求，教室利用率保持在尽可能的最大状态，所以该模型合理的描述了考试的安排。问题三：为了便于期末考试复习，每个专业一天只能考试一门课程，并且老师一天最多监考2场，2场考试不能在同一时间段，优化考试安排。由表中数据以及题目要求，让拥有最多类课程的专业每天都进行一场考试，则考完全部课程最少需要六天时间，由问题一及问题二的模型以及所得结果可推知，利用六天时间考完所有课程时间基本上充足。在课程考试安排分配相对均匀的情况下，教室的数量及教师的安排可以在每一天内得到内部优化，使其满足学校规定的要求。因此对于问题三的解决的核心应放在如何合理安排每天所考的课程以避免任一专业的考生在一天内考试两门课。通过对附表一的研究对课程分组及利用Lingo规划求解出具体安排课，最终得出表格：考试时间考试科目考试时间abc监考教师第一天218:009:30D16D41、D42A21-A2624D17D43、D44A27-A3233D18D45、D46A33-A3836D47、D48、D49A39-A4451D19、D20D50A45-A50399:5011:20D41、D42、D43A51-A5654D16、D17D44A57-A6263D18、D19D45A63-A6866D20、D21D46A69-A7475D22、D23D47A75-A8078D24、D25D48A15-A208314:2016:20D16D41A27-A3084D17D42A31-A3488D18D43A35-A3889D19D44A39-A4290D20D45A43-A4693D21、D22D46A47-A5294D23、D24D47A53-A5897D25、D26D48A59-A6498D27、D28D49A65-A70第二天14 8:009:00D16D41、D42A71-A7616D43、D44、D45A77-A80、A21-A2218D17D46、D47、D48A23-A3020D18、D19D49、D50A31-A38239:2010:50D16D41、D42A39-A4426D17D43、D44A45-A5029D18D45、D46A51-A5632D19D47、D48A57-A6253D22D49、D50A63-A68858:0010:00D20、D21A69-A723814:2015:50D41、D42、D43A73-7841D44、D45、D46A79-A80、A21-A2444D47、D48、D49A25-A304719:4521:15D41、D42、D43A31-A3650D44、D45、D46A37-A4256D16、D17D47A43-A48第三天288:009:30D16D41、D42A49-A5431D17D43、D44A55-A6034D18D45、D46A61-A6643D47、D48、D49A67-A7258D19、D20D50A73-A78469:5011:20D41、D42、D43A79-A80、A7-A1049D44、D45、D46A1-A561D16、D17D47A11-A1670D18、D19D48A17-A2273D20、D21D49A23-A288114:2016:20D16、D17A29-A3282D18、D19A33-A3686D20D41A37-A4087D21D42A41-A4491D22、D23D43A45-A4892D24、D25D44A49-A5495D26、D27D45A55-A6096D28、D29D46A61-A6799D30、D31D47A68-A73100D32、D33D48A74-A79第四天28:009:00D41、D42、D43A80、A21-A2512D16D44、D45A26-A3127 9:2010：50D16D41、D42A32-A3730D17D43