《期末考试安排问题分析—》由会员分享，可在线阅读，更多相关《期末考试安排问题分析—（20页珍藏版）》请在金锄头文库上搜索。
1、期末考试安排问题分析问题分析由于考试分为上午、下午、晚上三个时间段，考试课程的考试时间又分为 60 分钟、90 分钟、120 分钟三种情况，所以首先应该确定在各个时间段的考试课程的分配情况，合理的考试时间方案应满足除考试时间剩余时间不能超过某门课程的考试时间，且对于一个教室前后 2 门课程的考试时间间隔不能少于 20 分钟，应用枚举法列出所有的合理考试时间方案是为了考试时间最短，选择以下十八种合理的方案，如下表一所示：（A 代表 60 分钟、B 代表 90 分钟、C代表 120 分钟）时间段上午 中午 晚上 方案1AAAABB 2AAAABA 3AAACB 4AAACA 5AAAAAB 6AA
2、AAAA 7CAABB 8CAABA 9CACB 10CACA 11CAAA B 12CAAAA 13BBABB 14BBABA 15BBCB 16BBCA 17BBAAB 18BBAAA 19ACA 20ACB 21ABA 22AB B 23AABA假设未对有特殊限制的监考教师分配监考任务，因为没有特殊限制的监考教师有 60 人，每个考场需要两位监考教师，所以同一个时间段最多有 30 个考场进行考试，为了保证参加考试的人数尽可能的多，这 30 个考场我们取容量大的教室优先作为考场，考场的选择方案分别有：D1-D15 可容纳三十人的教室、D21-D40 可容纳四十五人的教室和 D41-D50
3、可容纳六十人的教室，由于我们要在最短时间内考完所有课程，所以我们选择后两种教师作为考场，即每场考试最多可同时容纳 1500 人进行考试，分别根据 60 分钟、90 分钟、120 分钟总人数不能超过考场容纳人数的限制，可得如下线性规划模型： 在这十八种合理的方案中考 60 分钟的总人数要小于等于该课程为 60 分钟的总人数。需要考 60 分钟的总人数：30 1045 1050 1060 105 455 5070 105 803725 需要考 90 分钟的总人数：15 302 15 452 15 502 15 6070 30 15 808400 需要考 120 分钟的总人数： 5 305 455
4、506 505 4050 55 6070 52050 问题一：球不和考情况下期末考试的最短时间模型建立考试时间按排考试时间按排：根据题目要求，设采用考试时间区间组合方案i 的天数为，可得考试总天数,其中1,2,3,40iix in x f f18, 1z0ii ix xn 为考试时间区间组合方案总数，由上表可得 n=18。规划目标是采用某些较合理考试时间区间组合方案使考试总天数最少，目标函数为：有以下约束函数：18, 1minz0ii ix x采取某些合理考试模式下，考试时间为 60min 的考试总人数不应超过其所用考场总容量：123456789101112131415171815002345
5、6223234223725xxxxxxxxxxxxxxxxx采取某些合理考试模式下，考试时间为 90min 的考试总人数不应超过其所用考场总容量：12345678910111314151718150023462433328400xxxxxxxxxxxxxxxx采取某些合理考试模式下，考试时间为 120min 的考试总人数不应超过其所用考场总容量：3478910111215161500222050xxxxxxxxxx考试考场安排考试考场安排：考场安排的目标是使考场利用率最大。要求有两个：每门课程都有考场；参加考试的考生数不得超过安排的考场容量。这里我们需要引进 0-1 变量 ybd表示第 b 门
6、课程能否在第 c 个考场考试，取 1 表示是，取 0 表示否，下一式表示在 t 时间段内 b 课程能在 c 考场正常考试：0,1,1,2,3100 ,1,2,350tbt bBt b BtT bc 0,0,1,2,3,100 ,1,2,3,50tbt bBt b BtT bc由于目标是使在 t 时间段考场的利用率尽可能的高，也即所有考场的余量尽可能的少，所以目标函数为:0501minbtctcdtbc t Tcybv zP y 有题目要求需要满足的约束条件如下： 501010,10,11,2,50,bt Btbc cbtbccztc ytbctcyR yP zYzctT监考教师的安排：监考老师
7、的安排属于随机分配问题。第 a 位教师在 t 时间段是否监考第 D 个考场，要引进 0-1 变量用表示，取 1 为表示监考，atdE取 0 表示否。目标是要保证各种情况下的教师监考场数尽量平均，也就是监考次数最多的教师与监考次数最少的教室的差值最小，即0050501111minmaxminTTatcatcatctc aEE 要满足的约束条件为：i 在 t 段时间内，第 a 位教师至多在一个考场监考，即500, 11,1,2,3,80atc cEtT aii 每个考场的监考教师为 2 人，每个考场的容量为，在 t 段dR时间内，第 D 个考场的安排的监考教师为：800 12,1,2,3,50at
8、cd aER tT ciii 情况 1 监考老师需要满足条件监考场数不超过 2 场，即050112,1,2,3,10Tatc tcEaiv 情况 2 的监考教师需满足条件监考场数不超过 3 场，即050113,11 12 1320Tatc tcEa，综上所述，我们建立监考教师的模型如下：0050501111minmaxminTTatcatcatctc aEE . .st500, 11,1,2,3,80atc cEtT a800 12,1,2,3,50atcd aER tT c050112,1,2,3,10Tatc tcEa050113,11 12 1320Tatc tcEa， 00,1 ,1,
9、2,3,80 ,1,2,3,50atcEtT ac问题二：载运和考的情况下，在问题一的基础之上求出期末考试的最短时间。1. 模型的建立由于受监考教师的人数的限制，在同一个时间段最多可以有40 个考场考试，因此在允许和考的情况下应充分利用考场D16-D50，使考场容量尽可能的大。因此在问题一的基础之上加上以下条件即可：0F0,1,2,.15tctT da 在问题一的基础之上，为充分利用监考教师资源，将有特殊情况的教师安排监考。由于考试时间为 90 分钟的课程所占人数最多，因而将监考教师 A1-A20 安排与课程 B21-B80,从而增加每场考试的考试容量，以缩短考试时间，即有以下约束条件：123
10、45678910111314151718150023462433328400xxxxxxxxxxxxxxxx综上所述， ；以函数的模型为基础建立以下优18, 1minz0ii ix x化模型：18, 1minz0ii ix x. .st1234567891011121314151718150023456223234223725xxxxxxxxxxxxxxxxx，0ix 12345678910111314151718150023462433328400xxxxxxxxxxxxxxxx，0ix ，3478910111215161500222050xxxxxxxxxx0ix 18, 1minz0ii
11、 ix xb 考场安排在函数的基础上建立以下整数规0501minbtctcdtbc t TcyBv zP y 划模型： 500 10001,1,2,3,50 ,0,1 ,1,2,3,500,1 ,1,2,3,50bt Btbc cbtbccztc ytbctcytTt bBR yP zctTYtTt bB cztT c ，F0,1,2,.15tcd0tTc 监考教师安排在函数的基础之上我们建0050501111minmaxminTTatcatcatctc aEE 立教考教师安排的模型如下：0050501111minmaxminTTatcatcatctc aEE 500, 11,1,2,3,80
12、atc cEtT a800 12,1,2,3,50atcd aER tT c050112,1,2,3,10Tatc tcEa050113,11 12 1320Tatc tcEa， 00,1 ,1,2,3,80 ,1,2,3,50atcEtT acF0,1,2,.15tcd问题三，为了便于学生的期末复习，学校规定每个专业一天只能考试一门课程，并且老师一天最多监考 2 场，2 场考试不能在同一时间段，其他条件不变，求出期末考试的最短时间，并作出期末考试的考场安排表。I 考试时间安排模型建立设为第 c 个专业第 b 门课程的考试时间，其中cbt,1,1,2,50,1,2,100cbc bIc b A
13、cb 目标是期末考试时间按排尽可能均衡，以有利益学生复习和水平的发挥，也就是对于一个专业，不同考试课程最小的时间间隔尽可能大，建立目标函数，, 2, 22 21maxmin, 1,c bc b bbttc bIc bI其约束条件为：1 每个专业一天至多考一门，即：2121122,cbcbttbbc bIc bI2 对于相同课程不同专业的考试时间相同即：1212,21,I,Ic bc bttccc bc b，综上所述，建立如下模型：, 2, 22 21maxmin, 1,c bc b bbttc bIc bI. .st2121122,cbcbttbbc bIc bI1212,21,I,Ic bc bttccc bc b，II 考场安排模型的建立0501minbtctcdtbc t TcyBv zP y . .st 500 10001,1,2,3,50 ,0,1 ,1,2,3,500,1 ,1,2,3,50bt Btbc cbtbccztc ytbctcytTt bBR yP zctTYtTt bB cztT c III 监考教师安排模型的建立0050501111minmaxminTTatcatcatctc aEE . .st500, 11,1,2,3,80atc cEtT a800 12,1,2,3,50atcd aER tT c050112,1,2,3,10Tatc tcE
