基于0-1规划的场地安排问题.docVIP

基于0-1规划的场地安排问题 摘要 一、问题的重述 2009年，我校城南校区共有3021名同学报名参加江苏省高等数学竞赛，其中，878人报名参加经贸类考试，1724人报名参加工科类考试，200人报名参加文科类考试，219人报名参加数学类考试。为此特向教务处申请了如下教室作为考场，详见附录一表一。 要根据考场的地理位置与容量，安排每个考场的考生人数以及监考教师数，在安排的过程中还要考虑如下几点：1、不同类型的考生不能分配在同一考场中；2、每个监考教师监考的考生人数要尽量相同；3、考场中会有一些突发状况，在安排考场时要尽量考虑周全；4、使用的教室要尽量少，以作备用教室及考务教 二、问题的分析 随着我国教育体制的改革的深入，学生人数的不断上升，手工安排考场易错难改、效率低的缺点就越来越突出。由于计算机具有速度快，处理能力强等特点，很自然的进入到这一领域中，用计算机进行考场安排能够快速的得到满足约束条件的可靠结果，具有考场安排时间短、人力省和质量高的优点，不但能使教务人员从繁杂的排考场任务中解脱出来，而且对于推动教学的发展出起了非常重要的作用。 分析题目可得，要保证考试的公平性和一些突发状况，每个教室就不能安排与教室容量相同数目的考生，即每个教室的考生数目要小于教室容量，按照常识推算，一般考生数目大概占教室容量的1/2到1/3，而且还要求尽量的少用教室，所以选取教室是很重要的一步。每个老师的监考人数可以根据考场的实际情况来进行安排调控，所以可以放在最后再考虑。 第一步就先单纯的选取部分教室作为考场，进行合理的选择安排，尽量使得选取的教室数量最少，以便空出足够教室作为备用考场和考务办公室。 先对教室的类型和数目进行分析，如下表所示： 表二 考场类型及数目 教室类型 可容学生数量 教室数量 教室类型 可容学生数量 教室数量 A 96 18 J 156 2 B 98 1 K 160 1 C 101 2 L 187 2 D 111 2 M 195 2 E 121 2 N 199 2 F 126 1 O 200 2 G 130 4 P 209 1 H 142 1 Q 215 1 I 144 5 R 216 1 在不考虑不同类考生坐在同一间教室的情况下，遵循选出最少的考场数原则，利用0-1规划模型，建立目标函数和约束条件，运用LINDO编程对所用考场进行选择。根据LINDO的运行结果选出教室作为考场。 第二步，再根据“不同类别的考生不能安排在同一考场中”这一条件，对选出的教室进行合理的安排。共四类考生，先进行排序，再根据每种排序的顺序，运用LINDO进行编程，依次对不同类型的考生选出最优的教室，分析比较选出最合理的那一种，确定每类考生所在的考场。然后再进行手排，确定具体每个考场中考生的数目。 最后，根据“每个监考教师监考的考生数目应尽量相同”这一条件，确定每个考场中所需安排的监考教师的数目，并计算每名教师监考的考生的数目。 三、基本假设 （1）假设容量为偶数的教室中的全部是双人课桌，容量为奇数的教室中只有一张单人桌，其他都为双人桌； （2）考生全部出席； （3）考试所需的硬件设施，教室都可以提供； （4）监考老师的数量足够，且每个监考老师都能准时出席。 四、符号说明 ：教室的编号。 ：所有选出的教室总量。 ：第i个教室相对应的实际考生容量。 ：每类考试所用教室总量。 ：所有教室最多能容纳的考生总数。 ：考生的实际总数。 五、模型的建立和求解 5.1模型一0-1规划模型的数据处理 在同一个考场中所需要的考场数量一定为大于或等于不同考生可以坐在同一个考场中所需要的考场数量，所以我们先按考不同考生可以坐在同一个考场中先选出教室，再根据不同类别考生不可以坐在同一考场中来安排考生。 为了方便书写与表达，我们先对题目所给出的表格进行新的编排和归类，考虑到考试的公平性再结合实际，我们提出考场的实际考生最大容量为考场本身最大容量的1/3和1/2两种方案，新建的表格见下表三和表四。 表三 教室编号 可容纳考生数（1/2容量） 可容考生数（1/3容量） 教室编号 可容纳考生数（1/2容量） 可容考数（1/3容量） 1 48 32 26 63 42 2 48 32 27 65 43 3 48 32 28 65 43 4 48 32 29 65 43 5 48 32 30 65 43 6 48 32 31 71 47 7 48 32 32 72 48 8 48 32 33 72 48 9 48 32 34 72 48 10 48 32 35 72 48 11 48 32 36 72 48 12 48 32 37 78 52 13 48 32 38 78 52 14 48 32 39 80 53 15 48 32 40