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

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

2、 8 月 19 日2011年河南科技大学数学建模竞赛选拔编 号 专 用 页评阅编号（评阅前进行编号）：评阅记录（评阅时使用）：评阅人评分备注题目：期末考试监考安排摘要本文就期末考试监考考场安排问题，提出一般性的假设，确定合适的约束条件，建立了相应的数学规划模型，并结合人工排考方法，进一步优化排考问题。并分别从时间安排，考场安排、监考安排三个方面建立相应的数学模型，以解决考试时间，考场，考试专业以及监考教师安排的问题。针对问题一、二，我们假设具有同一门课程的专业同时考试，建立考场安排与监考教师安排模型时，仅安排无限制的教师监考，再结合人工排考方法将具有特殊情况的教师安排监考。利用excel等数据

3、处理工具统计出各课程考试的人数（见表二）。并通过排列组合，用枚举法列出所有的考试时间模式，从中筛选出合理的考试时间模式（见表一）。再分别结合考试时间、考场情况、监考老师等约束条件建立线性规划模型，经lingo求解得最短考试时间为2天。进而得到相应的考场安排表分别见表四、表五。针对问题三，假设考试课程最多的专业每天均考一门，则最短考试时间为6天，每场考试采用30个考场，因而我们得出共有12个考试时间段，建立数学优化模型，来求出每门课程考试的时间间隔，而对部分考场安排结合人工排考，可得具体考试安排见表六。针对第四问，在建立完数学模型后，我们建立平均考场容量利用率的评价模型来评价各时间段考场安排的合

4、理程度，得出本文所建模式的平均考场容量利用率约为93%，此利用率对于一整天而言考场利用率已经较大，但也存在数个考场利用率低于90%的情况，对延长考试总天数产生影响。关键词：线性规划模型；整数规划模型；数学优化模型；枚举法一、问题重述1.背景每学期期末,各院系教务人员都要针对学校教务处下达的考试任务进行监考教师安排,传统的手工安排方式效率低且容易出错。我们从数学方面分析该问题，以期能给各院系教务人员有所帮助。假设某学院期末考试开始时间为2013年1月6日，每天（周一到周日均可）可分为三个考试时间段即：上午8:0011:45；下午14:2017:30；晚上19:4521:20。现有80位监考教师(

5、a1a80)，其中a1a10、a11a20监考场数分别不能超过两场，三场。a21-a80监考场数没有限制。要求每2个老师监考一个考场，并保证各种情况下的教师监考场数尽量平均。学院共有100门考试(b1-b100)，其中b1b20、b21b80、b81-b100所需的考试时间分别是60分钟、90分钟、120分钟。参加考试的共有50个专业，各专业的人数，参加考试的课程见附表一的excel表格，同时假设每个专业内的学生所选的课程一致。目前共有50个教室(d1-d50)可供选择，其中,d1d15可以容纳30人考试；d16d40可以容纳45人考试；d41d50可以容纳60人考试。 一个教室前后2门课程的

6、考试时间间隔不能少于20分钟。2.问题（1）、假设不能出现合考的情况，即不能把2门不同的课程放在同一考场一起考试。求出期末考试的最短时间，并做出期末考试的考场安排表。（2）、如果允许合考的情况，其他条件不变，求出期末考试的最短时间，并做出期末考试的考场安排表。（3）、为了便于学生的期末复习，学校规定每个专业一天只能考试一门课程，并且老师一天最多监考2场，2场考试不能在同一时间段，其他条件不变，求出期末考试的最短时间，并做出期末考试的考场安排表。（4）、请给各院系教务人员安排期末监考的一些建议，并评价一下模型的优缺点。二、问题分析首先，应当确定出考试时间段的划分的所有可能的组合模式，即在上午、下

7、午、晚上各个考试时间段中，可以安排60min,90min,120min3种情况不同的组合模式。其次从中挑选出合理的时间组合模式，合理的考试时间组合模式是在每个考试时间段中除去在该时间段中考试时间后所剩余的时间应小于每场考试的时间。因而通过筛选利用枚举法得出18种组合模式，如表一所示。再通过约束条件用lingo求解得出采用某种模式以及其采用该模式的天数，最终得出考试时间的具体情况。监考教师的安排属于指派问题。受监考教师的具体情况限制，每场考试最多采用40个考场考试，因此对于问题二在允许合考的情况下，应充分利用考场容量,对各考场进行合理的安排,即整个考试过程中存在两个d10-d50，一个d16-d

8、50，其余全为d20-d50,进而缩短考试时间。对于问题三，提出假设有最多门考试课程的专业每天都只能考一门，若每场考试采用30个考场，则每场考试的最大考场容量可为1500人。则符合若每天在两个时间段共进行两场考试，所有专业每天参加考试的考生人数不超过其考场总容量3000。同时有最多考试课程的专业要考试的课程有六门,因此，我们得出最多有12个时间段。最后,建立模型求解并结合人工排考优化考场安排。对于问题四，目前需要考虑的有监考老师，考试总时间和考场三个因素。一个合理的考场安排不仅仅追求考试总时间最小，还要给教师、学生一定的休息时间，因此我们应使考场的利用率最大，即用平均考场容量利用率来评价各时间

9、段考场安排的合理程度。三 模型假设1.假设具有相同课程的专业同时参加考试；2.每场考试需参加考试的学生均到场；3.每个安排有考试的考场均能正常进行考试。四 符号说明：表示监考老师编号，：表示考试课程编号，：表示考试专业编号，：表示考场教室编号，：表示第种考场安排模式，：表示第个考场的容量，：表示第门课程在时间是否考试（取1表示是，0表示否）；：表示参加第门课程考试的人数；：表示采用第种考试模式所需的天数；：表示第考场采用第种考试模式；：表示安排所有考试的时间段集合，；：表示第位监考老师在时间段是否监考第个考场（取0表示是，0表示否）；：表示时间考场是否使用（取1表示是，0表示否）；：表示时间课

10、程在考场考试；：表示第个专业是否有第门考试课程（取1表示是，0表示否）；：表示安排考试的时间段,；五 模型建立与求解1.问题一1.1 模型建立1.1.1考试时间安排用表示采用第种考试模式（=1,2，18）所用的天数，是非负整数。由此以采用某些合理的考试模式所需的考试天数最少为目标，得到目标函数：，由于无特殊情况的监考教师为60人，因此我们假设给定的考场数量为30个，为使考场容量最大化，假设采用的考场为d21-d50，因此每场考试所有考场可容纳1500（）人考试。为满足60min,90min,120min各个考试时间段的考试人数要求，即考试人数不超过考场容量，有以下约束条件：1)采取某些合理考试

11、模式下，考试时间为60min的考试总人数不应超过其所用考场的总容量：,2）采取某些合理考试模式下，考试时间为90min的考试总人数不应超过其所用考场容量：，3）采取某些合理考试模式下，考试时间为120min的考试总人数不应超过考场容量：，综上所述，建立模型：， ，1.1.2考场安排 在完成考试时间段安排后，我们引进0-1变量表示时间课程在第考场是否考试，取1表示是，取0表示否。其中：，在时间考场可能用也可能不用，用0-1变量表示，取1表示是，0表示否，。目标是在每个考试时间段，考场的利用率应尽可能高，即所有考场余量尽可能少，即。要满足的约束条件为：1）保证每门课程都有考场，；2）时间考场内的考

12、生总数不超过考场容量，即，综上所述，建立如下整数规划模型：， ， 1.1.3监考教师安排监考教师的安排属于指派问题。第位教师在时间段是否监考第个考场，引进0-1变量用表示，取1表示监考，取0表示否。目标是要保证各种情况下的教师监考场数尽量平均，也就是监考次数最多的教师与监考次数最少的教师的差值最小，即需要满足的约束条件为：1）在时间段，第位教师至多在一个考场监考，即，2）每个考场的监考教师为2人，每个考场的容量为，则在第时间段，第个考场的安排的监考教师为：，3）情况1的监考教师需满足条件监考场数不超过2场，即，4）情况2的监考教师需满足条件监考场数不超过3场，即，综上所述，我们建立监考教师安排

13、的模型如下： ，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天。用lin

14、go求解，具体结果见表四。以下给出部分结果：考试时间考试课程考试教室专业人数监考老师1月6日 早上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-a56期末考试考场安排（部分）2

15、.问题二 允许合考，在问题一的基础上求出最短考试时间2.1模型建立受监考教师限制，在时间段至多采用40个考场考试，因此在允许合考的情况下，应充分利用考场d16-d50，以使考场容量最大化。因而，在问题一的基础上，加之如下约束条件：，2.1.1时间安排在问题一的基础上，为充分利用监考教师资源，将有特殊情况的教师安排监考。由于考试时间为90分钟的课程所占人数最多，因而将监考教师a1-a20安排于课程b21-b80，从而增加每场考试的考试容量，以缩短考试时间，即有以下约束条件：综上所述，以1.1.1的模型为基础，建立以下优化模型：， ，2.1.2 考场安排在1.1.2的基础上，建立如下整数规划模型：

16、， ， ，2.1.3 监考教师安排在1.1.3的基础上，我们建立监考教师安排的模型如下： ， ，2.2 模型求解用lingo求解，程序见附录二，由附录二中的结果可见应采用模式4、16、18，其对应的天数为1.241667、0.1250000、0.5229167，共计1.889583天。由此我们得出考试时间共用2天，具体结果如表五所示。以下给出部分结果：期末考试考场安排表（部分）考试时间考试课程考试教室专业人数监考老师1月6日 上午8:00-10:00b81d20-d50c1，c2175a21-a80b82c2，c2275b83c3，c2375b84c4，c2475b86c6，c2695b87c

17、7，c2795b88c8，c2895b89c9，c2995b91c11，c31110b92c12，c32110b93c13，c33110b94c14，c34110b95c15，c35110b96c16，c36130b97c17，c371303.问题三 优化考试安排3.1 模型建立3.1.1 考试时间安排设为第个专业第门课程的考试时间，其中 目标是期末考试时间安排尽可能均衡，以有利于学生复习和水平的发挥，也就是对于一个专业，不同考试课程最小的时间间隔尽可能大，建立目标函数，其约束条件为：1） 每个专业一天至多考一门，即：，2） 对于相同课程不同专业的考试时间相同，即：，综上所述，建立如下模型：

18、，取整数，3.1.2 考场安排、监考教师安排所采用模型同1.1.2与1.1.3。3.2 模型求解 用lingo求解，具体监考情况安排见表六。以下给出部分结果：期末考场安排（部分） 考试时间 考试课程考试教室专业人数监考老师1月6日上午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,c45145a

19、25-a30b37d47,d48,d49c6,c26,c46175a31-a36b60d19,d20,d21c14,c34110a37-a42b64d22,d23,d24c15,c35110a43-a48b79d50,d25,d26c20,c40130a49-a54六 评价与建议我们对这种排课安排进行了评价，用平均考场容量利用率来评价各时间段考场安排的合理程度。平均考场容量利用率:一天内各时间段内所有考场容量的利用率的平均值。以1月6日为例，可以证明：=，=经计算得题一=93.37%，题二=93.089%优点：由于我们对模型严格的容量控制，使得整个考试过程中，考场利用率均大于90%，对于学校而

20、言是满意的，同时考场利用率高后，老师需要监考的场次数就相对减少了，有利于学校对于监考老师的安排。不足：有单独时间段其考场利用率低于90%，例如在复合段内上一时间段到下一时间段人数相差大。虽然对于一整天而言考场利用率已经较大，但是存在这种利用率低于90%的情况会增加考试总天数。并且我们发现仅仅为了缩短时间来完成考试，一味的追求最短化导致监考教师没有时间休息，并且学生没有时间复习与休息。建议：为了便于学生的期末复习，学校应尽量安排每个专业一天只能考试一门课程，并且老师一天最多监考2场，以增加学生的复习与休息时间以及老师的休息时间。参考文献7-302-10214/f1041 运筹学 教材编写组，运筹

21、学，清华大学出版社，2005年6月第三版。9787302111801 谢金星、薛毅，优化建模与lindo/lingo软件，清华大学出版社，2005年7月第一版。1007-9599（2010）10-000-02 黄键耿，用建模思想实现高校排考的优化配置，/d149680530.htm ,2012年八月十八日附录：附录一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)+

22、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

23、;0x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15+x16+x17+x18;global optimal solution found. objective value: 1.889583 total solver iterations: 3 variable value reduced cost x1 0.000000 0.2500000 x2 0.000000 0.1250000 x3 0.000000 0.1250000 x4 1.241667 0.000000 x5 0.000000 0.2500000 x6 0.000000 0.

24、1250000 x7 0.000000 1.000000 x8 0.000000 0.1250000 x9 0.000000 0.1250000 x10 0.000000 0.000000 x11 0.000000 0.2500000 x12 0.000000 0.1250000 x13 0.000000 0.1250000 x14 0.000000 0.000000 x15 0.000000 0.000000 x16 0.5229167 0.000000 x17 0.000000 0.1250000 x18 0.1250000 0.000000 row slack or surplus du

25、al price 1 1.889583 -1.000000 2 0.000000 -0.8333333e-04 3 0.000000 -0.1666667e-03 4 0.000000 -0.1666667e-03 5 1.889583 0.000000附录三：表一 合理考试时间模式表时间段上午/min下午/min晚上/min60分钟场数90分钟场数120分钟场数模式1120；6060；6060401模式2120；6060；6090311模式3120；6060；9060311模式4120；6060；9090221模式5120；6012060202模式6120；6012090122模式760；6

26、0；6060；6060600模式860；60；6060；6090510模式960；60；6060；9060510模式1060；60；6060；9090420模式1160；60；6012060401模式1260；60；6012090311模式1390；9060；6060320模式1490；9060；6090230模式1590；9060；9060230模式1690；9060；9090140模式1790；9012060121模式1890；9012090031表二 每门课程的考试人数课程b1b2-b5b6b7-b10b11b12-b15b16b17-b20人数/课程205175205220155160

27、180190容30人/课程76764465容45人/课程00011101课程b21-b35b36-b50b51-b65b66-b80b81-b85b86-b90b91-b95b96-b100人数/课程1451751101307595110130容30人/课程56401243容45人/课程00031101 表四 期末考试考场安排表考试时间考试课程考试教室专业人数监考老师1月6日 上午8：00-10:00b81d1,d16c1，c2175a21-a24b82d2,d17c2，c2275a25-a28b83d3,d18c3，c2375a29-a32b84d4，d19c4，c2475a33-a36b8

28、5d5，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,c41205a

29、21-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,

30、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，d

31、5c5,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

32、,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, d

33、35c19，c39130a75-a80b80d36,d37,d38c20，c40130a11-a161月7日 上午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,c4717

34、5a59-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-a56

35、b70d24，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，

36、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,d5

37、0c23，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-a18b38

38、d16,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表五 期末考试考场安排表考试时间考试课程考试教室专业人数监考老师1月6日 上午8:00-10:00b81d20-d50c1，c2175a21-a80b82c2，c2275b83c3，c2375b84c4，c2475b8