补考日程安排优化模型

学生学号论文成绩武汉理工大学学生学号建模论文任课教师论文题目学院班级姓名2012——2013学年第二学期补考日程安排优化模型摘要：在高校教育工作中，经常会遇到补考课程的时间安排问题。本题告诉我们一名学生可能会有多门补考科目，但在每一个时间段内，每位学生只能参加一门考试，所以考试中，有些科目是不能安排在同一时间段内的。本题要求我们把11门课程考试在两天的8个时间段内安排好，并且尽量避免冲突，最好把考试安排在上午。我应用建模思想建立数学模型，根据对课程能同时进行考试和不能同时进行考试的分类思想，应用图解和0—1规划解题，运用LINGO软件进行计算，得出了需要在7个时间段内安排考试，有多种安排方式（例：周六上午8:00-9:35,K1,K4,K8,K9;9:55-11:30，K5;下午13:30-15:05,K7;15:25-17:00,K10.周日上午8:00-9:35,K2,K3;9:55-11:30，K6;下午13:30-15:05,K11）。关键词：补考，日程安排，0-1规划，数学建模一、问题重述各大高校通常都在开学前的周六、周日完成补考。现就北京工业大学某次开学前的补考进行安排，要求每天的考试时间分为4个时间段，分别为：8:00-9:35,9:55-11:30，13:30-15:05，15:25-17:00。由于有的学生有多门补考，因此，有些课程安排在一个时段补考会产生冲突（例如，学生张三要补考高等数学和普通物理，如果将这两门课安排在一个时段补考就产生冲突）。现有11门课程（K1，K2，..，K11）需要安排补考，表A给出11门课程的补考是否有冲突的情况。表A：11门课程补考有冲突的情况（X为有冲突，一为无冲突）课程K1K2K3K4K5K6K7K8K9K10K11K1—X——X—X——XXK2X———X—X——XXK3———XXXX—XXXK4——X—XXX——XXK5XXXX—XXXXXXK6——XXX—X—XXXK7XXXXXX—XXXXK8————X—X——XXK9——X—XXX——XXK10XXXXXXXXX-XK11XXXXXXXXXX-要求：就该问题建立相应的数学模型、求解，帮助教务处制定一份详细的补考时间表，使得每位学生在每个时段都只需参加一门考试；如果有可能，补考时间尽量安排在上午；如果无法解决冲突问题，尽量使重要的课程不冲突(课程编号越小越重要，例如，K1比K2重要)。二、问题分析根据要求，一名学生可能会有多门补考科目，而每一位学生每场考试只能参加一门，从而安排的考试次数应不小于2,有些课程又不能同时进行考试，应对课程进行分类，把能同时考的放在一起，在使考试不冲突的情况下，尽量把考试安排在上午。三、模型假设1、监考老师足够，没有缺旷的情况。2、学生没有缺考的情况。3、考场数量足够多，考场设施一切正常。4、学生可以连续参加几场考试。四、符号说明Xi0-1规划中的变量，取1或0•i对应变量中的第i门课程五、模型建立求解方法一：图论求解把11门课程作为11个结点，可以同时进行的课程之间用边连起来，如下图

由上图可以看出，K5,K7,K10,K11是四个孤立点。它们只能分别单独地安排在四个时间段。并且可以发现K2,K4,K8,K9或者K1，K4,K8,K9这四个结点可构成完全图，所以它们可以同时进行。（如下图）此种情况下，剩余的K1,K6同时进行，K3单独；或者K1,K3同时进行，K6单独。此时，剩余的K2,K6同时进行，K3单独；或者K2,K3同时进行，K6单独。方法二:0-1规划求解对考试的课程进行编号用Xi（i日1,11］）表示，我们可以做0-1规划模型进行求解。记Xi=1,表示第i门课程不可以同时进行考试；记Xi=0，表示第i门课程可以同时进行考试。在发现K5,K7,K10,K11需要单独安排考试后，对剩下的K1，K2，K3，K4，K6，K8，K9应用LINGO软件求解。目标函数1：MinZ=x1+x2+x3+x4+x6+x8+x9;s.t.x6=1;x3+x4+x6+x9>2;x4+x6+x9>2;x3+x6>2;用LINGO软件计算，具体计算结果见附录1可得，x3,x6,x9不能同时是进行考试。目标函数2：MinZ=x1+x2+x3+x4+x6+x8+x9;s.t.x4=1;x3+x4+x6>2;x4+x6+x9>2;x3+x4+x9>2;用LINGO软件计算，具体计算结果见附录2经分析可得，x3,x4,x6不能同时考试，但x4和x9可以同时考。对于x8，它和x1,x2,x3,x4,x6,x9都可以同时考；而对x1,除了x2夕卜，其它的也都可以一起考。所以，各场考试之间的组合可以用下表表示：共有3X2X3=18这种组合K3K1K8K6K2K9K4再结合题目要求，所安排的日程不仅要满足各门考试不冲突，还要尽量把考试安

排在上午，并且序号小的课程更重要一些，所以综合以上条件，将补考日程安排如下:日期周六上午周六下午周日上午周日下午8:00—9:359:55—11:3013:30—15:0515:25—17:008:00—9:359:55—17:0013：30—15:05考试课程K1K4K8K9K5K7K10K2K3K6K11六、模型的检验由上表可清楚的看出各个时间段的考试科目，在合理的假设前提下，满足了题目的要求，从而说明这个规划模型是正确的，确立这个模型也是解决该类问题的一种方法。七、I型的优缺点分析1、模型有点：七、I型的优缺点分析（1）该模型引用0-1变量是根据现有的数据资料条件和假设建立数学规划模型，该模型简单明确，容易接受。（2）模型体现了应用数学软件的优越性。（3）图论法也是解决这类问题的好方法，对数学软件不熟悉的人可以选该方法。2、模型不足：本模型虽有较多优点，但仍存在一些缺陷，要求对数学软件有一定的分析能力。比如：由于我对软件不熟悉，只能运用LINGO得到：（x3,x6,x9）不可以同时进行考试等，不能得到补考日程安排的完整方案。八、模型的推广在日常生活中，我们经常遇到工作日程安排、课程表规划、期末考试日程安排等问题，都可以结合实际条件建立这种采用0-1变量的简单的数学规划模型，然后采用常用的数学软件求解最优解，得出合理的方案。而对于不熟悉数学软件的人，可以首选图论法求解。

九、参考文献【1】姜启源谢金星叶俊，数学模型（第四版），高等教育出版社，2010【2】李德宜李明，数学建模，科学教育出版社，2009【3】马杰田径赛安排优化模型/view/9e9f6be4e009581b6bd9ebe3.html2013-05-26十、附录附录一model:min=x1+x2+x3+x4+x6+x8+x9;x6=1;x3+x4+x6+x9>2;x4+x6+x9>2;x3+x6>2;endint7Glob己J.optimalsolationfoand.3.0000000Objectivevalae3.0000000Totalsolveriterations:VariableV己laeReducedCostXI0.0000001.000000X20.0000001.000000X31.0000000.000000X40.0000000.000000X61.0000000.000000X80.0000001.000000X91.0000000.000000RowSlackorSaiplasDu己J.Price13.000000-1.0000000.0000001.00000031.0000000.00000040.000000-1.00000050.000000-1.000000附录二model:min=x1+x2+x3+x4+x6+x8+x9;x4=1;x3+x6+x4>2;x4+x3+x9>2;x4+x9+x6>2;endint7GlotaloptimalsolutionfoandObjectivevalae:Totalsolveriterations:2.5000003VariableVaiasReducedCostXI0.0000001.000000X20.0000001.000000X30.50000000.000000X41.0000000