1、2012 高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料） ，必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从 A/B/C/D 中选择一项填写）： A 我们的参赛报名号为（如果
2、赛区设置报名号的话）： 所属学校（请填写完整的全名）： 河南科技大学 参赛队员 (打印并签名) ：1. 刘亚军 2. 冯雪玲 3. 高森祺 指导教师或指导教师组负责人 (打印并签名)： 日期： 2012 年 8 月 18 日赛区评阅编号（由赛区组委会评阅前进行编号）：2010 高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：1A 题:期末考试监考安排摘要本文从数学方面分析考场安排的问题，通过分析考场要求，设置一些基
3、本假设，确立约束条件。再通过对附表数据的分析计算，找出课程、专业之间的一些规律并结合人工排考，从时间安排，考场安排，监考安排三个方面建立数学模型，进而逐步解决考试时间，考试课程，考试教室及监考老师的问题，使资源更合理利用。对于问题一、二，根据条件得知同一考试科目不同专业要在同一时间进行考试，再对所要考试的课程分析可知：所有考试课程总体上可根据考试所需时间分为三大类。为了使得考试时间最短，可以合理分配三大类课程的时间，使时间利用率和考场利用率在满足监考考试的要求的情况下最大化。通过利用Lingo 软件优化再结合手工排考得出对于问题一的最短考完时间为两天半，对于问题二的最短考试时间为两天。具体安排
4、见正文表格。针对问题三，为了便于期末考试复习，每个专业一天只能考试一门课程，并且老师一天最多监考 2 场，2 场考试不能在同一时间段，让拥有最多类课程的专业每天都正好考试一门课，则考完全部课程最少需要六天时间，由问题一及问题二的结果可推知，利用六天时间考完所有课程时间基本上充足。在课程考试安排分配相对均匀的情况下，教室的数量及教师的安排可应满足每天内部最优化，使其在满足学校规定的要求前提下，最大化合理利用。因此对于问题三的解决的核心应放在如何合理安排每天所考的课程以避免任一专业的考生在一天内考试两门课。通过对附表一的研究对课程分组及利用 Lingo 规划求解再结合手工安排出具体的考试时间场地及
5、监考老师安排表。关键字：约束条件 规律 分析计算 时间利用率 考场利用率 人工排考 课程分组 lingo 优化规划2问题重述每学期期末,各院系教务人员都要针对学校教务处下达的考试任务进行监考教师安排,传统的手工安排方式效率低且容易出错。现在要从数学方面分析该问题，以期能给各院系教务人员有所帮助，已知某学院期末考试现有的监考教师为 80 人，并且老师分为三种不同的情况，一共有 100 门考试课程，他们所需时间基本分为三种类型，即 60min、90min、120min，该校一共有 50 个专业，人数以及各专业所学课程已经统计出来，供考试用的一共为 50 个教室，每个考场最多容纳人数都已调查清楚，并
6、且每天可以进行三时间段的考试，上午的时间为 8:00-11:45，下午的时间为 14:20-17:30，晚上的时间为 19:45-21:20。为了使得考试效率最高，因此，可以根据这些数据建立一个最优模型从而能准确快速的分配考场以及监考教师，使得考试时间最短。要探讨在这些条件下建立一个合理模型使得考试在最短时间内结束，我们需要完成以下问题：1、在假设不能出现合考的情况下，即不能把 2 门不同的课程放在同一考场一起考试，采用 Lingo 软件，运用规划的方法合理的规划处模型，使得在最短的时间内考完所有课程，并算出最短的时间。2、现在如果允许合考，及可以把不同的课程放到同一考场考试，在其他条件不变的
7、情况下，运用 Lingo 最优化模型作出最优模型，并做出期末考试的考场安排表。3、在掌握了前面的模型后，考虑到便于学生的期末复习，学校规定每个专业一天只能考试一门课程，并且老师一天最多监考 2 场，2 场考试不能在同一时间段，在其他情况不变的情况下，建立规划，讨论求解，做出规划，求出考场安排。4、根据建立的最优模型，以及自己模型的特点，和各院系教务人员进行交流，并给与他们安排期末监考的一些建议，最后根据实际情况以及模型的特点评价一下自己的模型的优缺点，便于教务人员更好地改进。问题分析考试安排问题是一个复杂的问题，从题目所给的条件以及表格可以看出：1、不同的专业所学习的课程基本呈规律排布；2、夜
8、晚考试的课程是所需时间是 60min 或 90min 的课程；3、每个监考老师监考次数应在满足条件限制的前提下尽量平均；4、同一专业不能同时进行不同的考试，以避免冲突;5、选有同一课程的不同专业必须同一时间考试。第一步：进行考试课程的分配，以使得课程考试在最短的时间内结束。为了使得考试尽快结束，可以规划使得每个时间段考试课程最大化，使时间利用率最高。为了避免课程的冲突进行条件约束，条件要求：1、不同的专业相同的课程要同一时间考试；2、相同的专业不同的课程不能同时进行考试；3、考试时间不能与规定的时间违背。根据这些条件进行最优化规划，运用lingo 编程求解，可以计算出最优考试科目的安排。第二步
9、：在课程得到合理分配以后，进行考场最优分配。在第一步的基础上根据考场的容纳人数进行分配，尽量使得每个教室的空位最少，即每个教室的空位率最少，使得考场在满足条件的前提下占用最少，避免教室不够用这一情况。即每组所用的考场数目的容量大于考试人数。根据老师的数目限制可以看出最多只能安排 40 个考场，定义目标函数，提出约束条3件，进行最优化分析，利用 lingo 软件进行求解，得到最优解。第三步：考场以及科目都安排合理的情况下合理安排监考教师。在前两步的基础上进行教师的安排，教师安排时依据教师的特殊要求进行合理分布，使得在满足教师特点要求的情况下，教师的监考场数基本持平，避免分歧。以上面的三步为基础对
10、问题一、二、三进行逐步分析，可以看出问题二是在问题一的基础上进行改进，三是在一、二的基础上提出更为为合理的要求，对三个不同的问题分别进行条件分析，建立合理模型，安排好考试。对模型提出合理的假设，分析模型的特点以及实际情并提出意见，进而完善模型。模型假设1、假设考场数量以及老师都没用变动，学生没用缺考等现象2、假设考试都是从每个时间段的最早开始，没用推迟等问题的出现3、假设所用的学生都服从安排，老师都按指定的分配任务执行4、假设教室桌位是隔开的，即题目给出的容纳人数为按考试座位的人数5、假设所有考场都能进行考试，没有不能用的教室符号说明t：考试时间段，t=1，2，3 分别表示 225min、19
11、0min、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=D 1D15b：第二类考场，即可容纳 45 人的教室，b=D 16D40c：第三类考
12、场，即可容纳 60 人的教室，c=D 41D50模型建立及求解问题一：要研究在不出现合考的情况下，使得在最短的时间内完成所有的考试课程。即最充分的利用时间，时间浪费最少。同时需要考虑同一课不同专业的学生必须在同一时间段考试，又不能出现考试冲突，即杜绝某一考生需要在同一时间点进行不同的考试。为了讨论的需要，这里认为每天考试科目越多时间利用率越大，考完全部科目所需要的时间越短。可以以课程为变量对时间优化，因此需要先求每门课程参加考试的人数。根据题中附表的数据整理得出各个课程要考核的人数如下（此处只挑部分展出，具体的表格见附录）：课程 专业 人数4B1 C1 C21 C41 C20 205B2 C2
13、 C22 C42 C1 175B91 C31 C11 110B92 C32 C12 110B93 C33 C13 110B94 C34 C14 110B95 C35 C15 110B96 C36 C16 130B97 C37 C17 130B98 C38 C18 130B99 C39 C19 130B100 C40 C20 130根据表格以及数据，考虑到要避免考试冲突，将课程按专业要求分类，并进行优化，得出不同课程的数据，进行整理得出：下面建立优化模型：为了使得考试总共所需时间最短，即每天进行的考试课程最多，其中=（i,j）|A ji=1，i=1,250 ，j=1,2100 ，即Iji),(M
14、ax Xm1+Xm2+Xm3 需要满足约束为：课程 人数 a（30）b（45）c（60）剩余座位B1、B6 205 1 0 3 5B17-B20 190 1 1 2 5B2-B5 175 0 0 3 5B7-B10 220 0 1 3 5B11 155 0 1 2 10B12-B15 160 0 1 2 5B16 180 0 0 3 0B21-B35 145 1 0 2 5B36-B50 175 0 0 3 5B51-B65B91-B95110 0 0 2 10B96-B100B66-B80130 1 1 1 5B81-B85 75 1 1 0 0B86-B90 95 0 1 1 1051）
15、每天每个时间段的考试时间不得超过规定的时间，即 1)-X20(-951X906 321332313 222） 对于课程 j，不同专业考试时间应相同，即= ， ， ,1jiT2ji21iIj),(1Iji)(23） 对于同一专业，不同课程不能同时考试，即， ，ijij2121j IijIi),(),(21综上所述，建立如下优化模型：Max Xm1+Xm2+Xm3 1)-X20(-951906 321332313 22= ， ， ,1jiT2jiiIj),(Iji)， ，ijij2121(21Xm1、X m2、X m3 取整数， Iji),利用所给数据，应用 lingo 软件进行编程求解（编程见附
16、录） 。得出结果为：Objective value: 6.000000Extended solver steps: 0Total solver iterations: 0Variable Value Reduced CostX1 3.000000 -1.000000X2 2.000000 -1.000000X3 0.000000 -1.000000X4 0.000000 -1.000000X5 0.000000 -1.000000X6 1.000000 -1.000000X7 0.000000 -1.000000X8 0.000000 -1.000000X9 0.000000 -1.00000
17、0Row Slack or Surplus Dual Price1 6.000000 1.00000062 5.000000 0.0000003 50.00000 0.0000004 5.000000 0.000000由所求的结果可知对于上午的时间段 t1：全部进行考试时间为 60 分钟的课由程考试，此时可以使在单位时间内考的科目最多。根据所得数据决定先对考试时间为 60 分钟的课程进行优先安排，考虑到不能出现考试冲突，通过观察附件一的数据得出结论，即对于编号为前 20 的课程要想避免考试冲突只需要在安排考试的时候不要将编号相邻的课程排在同一时间段即可，同时由分析可知对于第一天上午的考试可先对
18、编号为前 20 的课程分为三个时间点考试，利用模糊聚类的方法分为 M1 ，M 2，M 3三个小组的考试，运用 lingo 编程求解得出（见附录）：其中 M1组所考课程包括：B 2 、 B4 、 B7 、 B11 、 B13 、 B15 、 B18 ；M 2组所包括考科目为：B 3、 B5 、 B9 、 B12、 B14 、 B16、 B20；M 3组科目为：B 1 、 B6 、 B8 、 B10 、 B17 、 B19。可以使所分的课程满足考试不冲突的前提下，每组所参加考试的人数接近相等。这样可以使考场的占有最小，节省出来的考场可以用作考其他小组的课程考试，从而使教室的利用率最大，进而尽快结束
19、考试。建立优化模型：min 30*4560*i i iBBBXYZ222588811144417171720202017530*60*593*6*BBBBBBYZXYZ25811417202025811417BBBBaXXXbYcZ由Lingo 进行编程规划（编程见附录） ，得出结果为：Variable Value Reduced CostXB2 6.000000 30.00000YB2 0.000000 45.00000ZB2 0.000000 60.00000XB4 0.000000 30.00000YB4 0.000000 45.00000ZB4 3.000000 60.00000XB7
20、 0.000000 30.00000YB7 1.000000 45.00000ZB7 3.000000 60.00000XB11 0.000000 30.000007YB11 1.000000 45.00000ZB11 2.000000 60.00000XB13 4.000000 30.00000YB13 1.000000 45.00000ZB13 0.000000 60.00000XB15 0.000000 30.00000YB15 1.000000 45.00000ZB15 2.000000 60.00000XB18 5.000000 30.00000YB18 1.000000 45.00
21、000ZB18 0.000000 60.00000a 15.00000 0.000000b 5.000000 0.000000c 10.00000 0.000000根据结果可以得知M1组所需a类考场为15间，b类考场5间，c类考场10间。同M1再分别对M2,和M3组的考场最优化分配，整理可得：课程小组考场类别a b cM1 15 5 10M2 12 16 8M3 15 13 9由所得的结果可知在第一天上午考完编号为前20科目的同时，可以在上午的考试中还可以进行其它考试时间的课程，以使得教室得到充分利用，以减少考试时间，为了避免教室冲突，通过对所得结果的分析整理可以看出当以M3组所需教室的最优分
22、配为主时，可以同时满足M1、M2组所需教室的用量。根据结果可以看出课程B 2需要教室数目为：0,0,3。即需要3个C类教室。其他的课程根据此进行优化求解，并且依据老师的要求安排老师， （具体编程见附录） ，对结果整理得出：分组类别考试时间包含课程教室 监考教师a类 b类 c类B2 D41、 D42、 D43 A21-A26B4 D44、 D45、 D46 A27-A32B7 D16 D47、 D48、 D49 A33-A40B11 D1、 D2、 D3、 D4D17 A41-A50M18:00 9:00 B13 D5、 D6、 D7、 D D18 A51-A6088B15 D9、 D10、 D
23、11、D12D19 A61-A70B18 D13 D20、 D21、 D22、D23、 D24A71-A80、A11-A12B3 D41、 D42、 D43 A21-A26B5 D44、 D45、 D46 A27-A32B9 D16 D47、 D48、 D49 A33-A40B12 D1、 D2、 D3、 D4D17 A41-A50B14 D5、 D6、 D7、 D8D18 A51-A60B16 D9、 D10、 D11、D12、 D13、 D14A61-A72M29:2010:20B20 D15 D19、 D20、 D21、D22、 D23A73-A80、A13-A16B1 D1 D41、
24、D42、 D43 A21-A28B6 D2、 D3、 D4、 D5、 D6、 D7、 D8A29-A42B8 D16 D44、 D45、 D46 A43-A50B10 D9、 D10、 D11、D12、 D13、 D14D17 A51-A64B17 D18、 D19、 D20 D47 A65-A72M310:40 11:40B19 D15 D21 D48、 D49 A73-A80对于第一天下午的考试安排与上午类似，进行最优规划，整理得到：根据前面的规律以及规划得到后期考试的安排如下：课程时间教师教室a b c 教师课程程考试时间教室类别a b c 教师B81-B85 D1、 D2、 D3、 D4、D5D16、 D17、 D18、 D19、 D20A21-A40B86-B90 D21、 D22、 D23、 D24、 D25D41、 D42、 D43、 D44、 D45A41-A60B91 D6 D26、 D27 A61-A66B96-B10014:2016:20D7、 D8、 D9、 D10、 D11D28、 D29、 D30、 D31D46、 D47、 D48、 D49、 D50A67-A80、A11-A20、A1-A4
