资源描述
^`
2012高教社杯全国大学生数学建模竞赛
承 诺 书
我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.
我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。
我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。
我们参赛选择的题号是（从A/B/C/D中选择一项填写）： A
我们的参赛报名号为（如果赛区设置报名号的话）：
所属学校（请填写完整的全名）： 河南科技大学
参赛队员 (打印并签名) ：1. 刘亚军
2. 冯雪玲
3. 高森祺
指导教师或指导教师组负责人 (打印并签名)：
日期： 2012 年 8 月 18 日
赛区评阅编号（由赛区组委会评阅前进行编号）：
2010高教社杯全国大学生数学建模竞赛
编 号 专 用 页
赛区评阅编号（由赛区组委会评阅前进行编号）：
赛区评阅记录（可供赛区评阅时使用）：
评
阅
人
评
分
备
注
全国统一编号（由赛区组委会送交全国前编号）：
全国评阅编号（由全国组委会评阅前进行编号）：
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、95min
i：专业编号，i=1~50
J：课程编号，j=1~100
Ak：监考老师，其中k=1~80
Bj：第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=D1~D15
b：第二类考场，即可容纳45人的教室，b=D16~D40
c：第三类考场，即可容纳60人的教室，c=D41~D50
模型建立及求解
问题一：
要研究在不出现合考的情况下，使得在最短的时间内完成所有的考试课程。即最充分的利用时间，时间浪费最少。同时需要考虑同一课不同专业的学生必须在同一时间段考试，又不能出现考试冲突，即杜绝某一考生需要在同一时间点进行不同的考试。为了讨论的需要，这里认为每天考试科目越多时间利用率越大，考完全部科目所需要的时间越短。可以以课程为变量对时间优化，因此需要先求每门课程参加考试的人数。根据题中附表的数据整理得出各个课程要考核的人数如下（此处只挑部分展出，具体的表格见附录）：
课程
专业
人数
B1
C1
C21
C41
C20
205
B2
C2
C22
C42
C1
175
B91
C31
C11
110
B92
C32
C12
110
B93
C33
C13
110
B94
C34
C14
110
B95
C35
C15
110
B96
C36
C16
130
B97
C37
C17
130
B98
C38
C18
130
B99
C39
C19
130
B100
C40
C20
130
根据表格以及数据，考虑到要避免考试冲突，将课程按专业要求分类，并进行优化，得出不同课程的数据，进行整理得出：
课程
人数
a（30）
b（45）
c（60）
剩余座位
B1、B6
205
1
0
3
5
B17-B20
190
1
1
2
5
B2-B5
175
0
0
3
5
B7-B10
220
0
1
3
5
B11
155
0
1
2
10
B12-B15
160
0
1
2
5
B16
180
0
0
3
0
B21-B35
145
1
0
2
5
B36-B50
175
0
0
3
5
B51-B65
B91-B95
110
0
0
2
10
B96-B100
B66-B80
130
1
1
1
5
B81-B85
75
1
1
0
0
B86-B90
95
0
1
1
10
下面建立优化模型：
为了使得考试总共所需时间最短，即每天进行的考试课程最多，其中={（i,j）|Aji=1，i=1,2…50，j=1,2…100}，即
Max Xm1+Xm2+Xm3
需要满足约束为：
1） 每天每个时间段的考试时间不得超过规定的时间，即
2） 对于课程j，不同专业考试时间应相同，即
=，，,
3） 对于同一专业，不同课程不能同时考试，即
，，
综上所述，建立如下优化模型：
Max Xm1+Xm2+Xm3
=，，,
，，
Xm1、Xm2、Xm3取整数，
利用所给数据，应用lingo软件进行编程求解（编程见附录）。
得出结果为：
Objective value: 6.
Extended solver steps: 0
Total solver iterations: 0
Variable Value Reduced Cost
X1 3. -1.
X2 2. -1.
X3 0. -1.
X4 0. -1.
X5 0. -1.
X6 1. -1.
X7 0. -1.
X8 0. -1.
X9 0. -1.
Row Slack or Surplus Dual Price
1 6. 1.
2 5. 0.
3 50.00000 0.
4 5. 0.
由所求的结果可知对于上午的时间段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. 30.00000
YB2 0. 45.00000
ZB2 0. 60.00000
XB4 0. 30.00000
YB4 0. 45.00000
ZB4 3. 60.00000
XB7 0. 30.00000
YB7 1. 45.00000
ZB7 3. 60.00000
XB11 0. 30.00000
YB11 1. 45.00000
ZB11 2. 60.00000
XB13 4. 30.00000
YB13 1. 45.00000
ZB13 0. 60.00000
XB15 0. 30.00000
YB15 1. 45.00000
ZB15 2. 60.00000
XB18 5. 30.00000
YB18 1. 45.00000
ZB18 0. 60.00000
a 15.00000 0.
b 5. 0.
c 10.00000 0.
根据结果可以得知M1组所需a类考场为15间，b类考场5间，c类考场10间。同M1再分别对M2,和M3组的考场最优化分配，整理可得：
课程小组
考场类别
a
b
c
M1
15
5
10
M2
12
16
8
M3
15
13
9
由所得的结果可知在第一天上午考完编号为前20科目的同时，可以在上午的考试中还可以进行其它考试时间的课程，以使得教室得到充分利用，以减少考试时间，为了避免教室冲突，通过对所得结果的分析整理可以看出当以M3组所需教室的最优分配为主时，可以同时满足M1、M2组所需教室的用量。
根据结果可以看出课程B2需要教室数目为：0,0,3。即需要3个C类教室。其他的课程根据此进行优化求解，并且依据老师的要求安排老师，（具体编程见附录），对结果整理得出：
分组类别
考试时间
包含课程
教室
监考教师
a类
b类
c类
M1
8:00 ～9:00
B2
D41、D42、D43
A21-A26
B4
D44、D45、D46
A27-A32
B7
D16
D47、D48、D49
A33-A40
B11
D1、D2、D3、D4
D17
A41-A50
B13
D5、D6、D7、D8
D18
A51-A60
B15
D9、D10、D11、D12
D19
A61-A70
B18
D13
D20、D21、D22、D23、D24
A71-A80、A11-A12
M2
B3
D41、D42、D43
A21-A26
9:20～10:20
B5
D44、D45、D46
A27-A32
B9
D16
D47、D48、D49
A33-A40
B12
D1、D2、D3、D4
D17
A41-A50
B14
D5、D6、D7、D8
D18
A51-A60
B16
D9、D10、D11、D12、D13、D14
A61-A72
B20
D15
D19、D20、D21、D22、D23
A73-A80、A13-A16
M3
10:40 ～11:40
B1
D1
D41、D42、D43
A21-A28
B6
D2、D3、D4、D5、D6、D7、D8
A29-A42
B8
D16
D44、D45、D46
A43-A50
B10
D9、D10、D11、D12、D13、D14
D17
A51-A64
B17
D18、D19、D20
D47
A65-A72
B19
D15
D21
D48、D49
A73-A80
对于第一天下午的考试安排与上午类似，进行最优规划，整理得到：
课程程
考试
时间
教室类别
a
b
c
教师
B81-B85
14:20
～
16:20
D1、D2、D3、D4、D5
D16、D17、D18、D19、D20
A21-A40
B86-B90
D21、D22、D23、D24、D25
D41、D42、D43、D44、D45
A41-A60
B91
D6
D26、D27
A61-A66
B96-B100
D7、D8、D9、D10、D11
D28、D29、D30、D31
D46、D47、D48、D49、D50
A67-A80、A11-A20、A1-A4
根据前面的规律以及规划得到后期考试的安排如下：
课程
时间
教师
教室
a
b
c
教师
B24
19:45
～
21:15
（第一天）
D1
D41、D42
A21-A26
B30
D16、D17、D18、D19
A27-A34
B36
D43、D44、D45
A35-A40
B42
D46、D47、D48
A41-A46
B48
D20、D21、D22
A47-A52
B54
D49、D50
A53-A56
B60
D23、D24、D25
A57-A62
B66
D26、D27、D28
A63-A68
B72
D29、D30、D31
A69-A74
B78
D32、D33、D34
A75-A80
B21
8：00
～
9：30
(第二天)
D16、D17
D41
A21-A26
B27
D18、D19、D20、D21
A27-A34
B33
D22、D23
D42
A35-A40
B39
D43、D44、D45
A41-A46
B45
D46、D47、D48
A47-A52
B51
D24、D25、D26
A53-A58
B57
D49、D50
A59-A62
B63
D27、D28、D29
A63-A68
B69
D30、D31、D32
A69-A74
B75
D33、D34、D35
A75-A80
B22
9：50
～
11：20
（第二天）
D16、D17
D41
A21-A26
B28
D18、D19、D20、D21
A27-A34
B34
D22、D23
D42
A35-A40
B40
D43、D44、D45
A41-A46
B46
D46、D47、D48
A47-A52
B52
D24、D25、D26
A53-A58
B58
D49、D50
A59-A62
B64
D27、D28、D29
A63-A68
B70
D30、D31、D32
A69-A74
B76
D33、D34、D35
A75-A80
B92
8:00
～
10:00
（第二天）
D1
D36、D37
A17-A20、A5-A6
B93
D2
D38、D39
A7-A10、A1-A2
B23
14:20
～
15:50
（第二天）
D1
D41、D42
A21-A26
B29
D16、D17、D18、D19
A27-A34
B35
D20、D21、D22、D23
A35-A42
B41
D43、D44、D45
A43-A48
B47
D46、D47、D48
A49-A54
B53
D24、D25、D26
A55-A60
B59
D49、D50
A61-A64
B65
D27、D28、D29
A65-A70
B71
D30、D31、D32
A71-A76
B77
D33、D34、D35
A77-A80、A3-A4
B94
14:20
～
16:20
(第二天)
D1
D36、D37
A5-A10
B95
D2
D38、D39
A11-A16
B25
19:45
～
21:15
(第二天)
D1
D41、D42
A21-A26
B31
D16、D17、D18、D19
A27-A34
B37
D20、D21、D22、D23
A35-A42
B43
D43、D44、D45
A43-A48
B49
D46、D47、D48
A49-A54
B55
D24、D25、D26
A55-A60
B61
D49、D50
A61-A64
B67
D27、D28、D29
A65-A70
B73
D30、D31、D32
A71-A76
B79
D33、D34、D35
A77-A80、A17-A18
B26
8:00
～
9;30
(第三天)
D1
D41、D42
A21-A26
B32
D16、D17、D18、D19
A27-A34
B38
D20、D21、D22、D23
A35-A42
B44
D43、D44、D45
A43-A48
B50
D46、D47、D48
A49-A54
B56
D24、D25、D26
A55-A60
B62
D49、D50
A61-A64
B68
D27、D28、D29
A65-A70
B74
D30、D31、D32
A71-A76
B80
D33、D34、D35
A77-A80、A19-A20
根据模型结果看出在不合考的情况下，为了满足所有的限制条件，并使得考试在最短时间内进行，至少需要进行2天半，时间等具体排列如上表所示。
问题二
在允许合考的情况下，依据问题一的思路求出最短时间。因为允许合考，所以应充分利用D16——D50，使考场容量最大化，进而达到考试时间最短的目的。
在前面求解过程中，已将考试时间为60min的课程分为3类：M1、M2、M3。
为了更好地利用教室资源，运用Lingo 对M1，M2，M3进行最优规划 （在此只对M1进行举例，M2、M3详见附录）。
对M1建立优化模型：
Min a+b+c
M1编程如下：
min=a+b+c;
30*a+45*b+60*c-1235>=0;
a+b+c<=40;
@bnd(0,a,15);
@bnd(0,b,25);
@bnd(0,c,10);
@gin(a);@gin(b);@gin(c);
结果：
Global optimal solution found.
Objective value: 25.00000
Extended solver steps: 0
Total solver iterations: 3
Variable Value Reduced Cost
A 0. 1.
B 15.00000 1.
C 10.00000 1.
Row Slack or Surplus Dual Price
1 25.00000 -1.
2 40.00000 0.
3 15.00000 0.
在前面求解过程中，已经将考试时间为90min的课程分为6类，其中前三类总人数为1375，后三类人数为1425，对前三类进行教室规划，编程如下：
min=a+b+c;
30*a+45*b+60*c-1375>=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. 1.
B 18.00000 1.
C 10.00000 1.
Row Slack or Surplus Dual Price
1 28.00000 -1.
2 35.00000 0.
从结果可以看出，60人的教室得到了充分的利用，由于现在可以合考，进而所需时间大大减少。通过lingo求解以及人工排考得知只需要两天时间就能考完，可以充分利用每天的各个时间段，即同一时间段进行不同的科目考试，此时时间利用率将达到最高。由第一题的分析得到课程的分类，在此基础上进行不同类型课程的合理排布，使得教室利用率最高，进而使得时间最短，通过lingo以及人工排考方式求出最佳排列方式，整理得出表格:
课程
时间
考场
教室
a
b
c
教师
B82-B90、B92-B100
8:00
～
10:00
D1～D4
D16～D40
D41～D50
A1-A80
B2、B4、B7、 B11、B13、B15、B18
10:20
～
11:20
D16～D30
D41～D50
A21-A70
B24、B30、B36、B42、B48、B54、B60、B66、B72、B78
14:20
～
15:50
D16～D34
D41～D50
A21-A78
B3、B5、B9、B12、B14、B16、B20
16:10
～
17:10
D16～D29
D41～D50
A21-A68
B81、B91
14:20
～
16:20
D35～D38
A79-A80、A1-A5
B25、B31、B37、B13、B19、B55、B61、B67、B73、B79
19:45
～
21:15
D16～D34
D41～D50
A21-A78
B26、B32、B38、B44、B50、B56、B62、B68、B74、B80
8:00
～
9:30
D16～D34
D41～D50
A21-A78
B21、B27、B33、B39、B45、B51、B57、B63、B69、B7
展开阅读全文
相关搜索