课表编排问题-数学建模

1、精选优质文档-倾情为你奉上精选优质文档-倾情为你奉上专心-专注-专业专心-专注-专业精选优质文档-倾情为你奉上专心-专注-专业魅力数模 美丽力建力建学院第六届数学建模竞赛自信 坚强 团结 创新 论文题目 课表编排0-1规划模型 参赛编号 2008tj0804 监 制：力建学院团委 数学建模协会（2010年11月）力建学院第六届数学建模竞赛承 诺 书我们仔细阅读了第六届建工数学建模竟赛的竞赛规则。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与本队以外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的

2、成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们愿意承担由此引起的一切后果。我们的参赛编号为： 2008tj0804 参赛队员 (签名) ：队员1： 叶 庆队员2： 靳小龙队员3： 胡传鹏课表编排问题第一部分摘要： 本文根据制定课表时需考虑的问题,建立了冲突最少的0-1规划模型； 求解得课表，并根据所得结果对教师聘用,教室的配置,来做出合理的建议。考虑目标函数时，分析课表编排要符合的条件为：课程要求、教师课程编排尽量分散、同课程编排尽量分散、教师超

3、出工作量尽量少。则我们目标函数冲突最少分解为：各门课程各自不符合程度总和最少、各教师各自课程编排分散程度总和最大、各门课程编排分散程度总和最大、各教师超出工作量程度总和最少。考虑约束条件时，分析附录中的相关数据,得到课程编排的影响因素有,时间,教室,课程等，则可以根据此来约束目标函数。根据以上考虑因素建立系统递阶图,使目标更清晰。建立空间向量，已知数据与空间向量一一对应。根据课程要求与实际编排差距最少原理，建立目标函数。加上课表编的约束条件,进行优化,用Matlab求解课表.再根据求解得课表与相关系数指标为教师聘用,教室的配置,来做出合理建议.关键词：课表编排 系统递阶图 空间向量第二部分一、

4、问题重述某高校现有课程40门，编号为C01C40；教师共有25名，编号为T01T25；教室18间，编号为R01R18。具体属性及要求见表1，表2，表3：课表编排规则：每周以5天为单位进行编排；每天最多只能编排8节课，上午4节，下午4节，特殊情况下可以编排10节课，每门课程以2节课为单位进行编排，同类课程尽可能不安排在同一时间。 你所要解决的问题：请你结合实际情况给出较为合理的课表编排方案，分析你所给出的方案的合理性。对教师聘用，教室配置给出合理化建议。二、问题的分析问题分析为先建立合理的课表编排方案，再从课表编排方案中分析对教师聘用，教室配置给出合理化建议。针对问题一：1、该问题要求给出合理的

5、课表编排方案，分析如下：（1）、总体上尽量使每门课程符合要求，即求各门课程各自不符合程度总和最低；（2）、总体上使同一老师的课程尽量分散，即求其总各教师各自课程编排分散程度总和最大；（3）、总体上使每门课程的编排尽量分散，即求各门课程编排分散程度总和表达式最大；（4）、总体上使同一老师相对超出的工作量尽量少，各教师超出工作量程度总和最少。2、针对编排方案约束条件如下：（1）、同一时间段同一教室不能同时上两门或两门以上的课程；（2）、在任一教室上课的人数不能超过最大座位数；（3）、同一时间段同一教室不能同时上两门或两门以上的课程；（4）、在安排课程与老师授课类别要符合课程类别，不要造成混乱；利用

6、层次分析法，求出表示不同程度的权重表达式，把以上各点要达到的目标整合成为单目标的总目标0-1规划问题。针对问题二：1、根据教师聘用则要求分析出哪一类课程需要的教师越少，则越要聘用教那一类课程的教师。各类教师少的程度可用各类教师补课程度系数（各类教师周最大课时数之和与各教师实际课时数之和的比值）来作分析参考，系数越大则该类教师越少，应尽量聘用能胜任该类课程的教师。2、针对教室配置给出合理化则要求分析出：（1）对各类教室配置座位数量应为多少才合理；（2）各教室类别（机房，多媒体教室，通教室）数量的应为多少才合理；则可以从应配置座位系数（数量与实际座位数量之差，再比上实际座位数量）和配置类别系数（课

7、程要求与实际类别数量之差，再比上实际类别数量）分析可得：座位系数越大，则对各类教室配置座位数量需求越大，则越要配置多一点座位，反之越小；配置类别系数越大，则各教室类别（机房，多媒体教室，通教室）数量需求越大，则越要配置多一点该类别教室，反之则越小。三、模型假设假设机房、多媒体教室和普通教室三者的重要性系数之比为321； （机房可以当作多媒体教室用，而多媒体教室也可以当普通教室用）假设课程类别、课时数、座位数、教师类别、时间段的重要性之比为；假设每位教师都不会生病请假而能正常上课；假设每个教室的设备都能正常运作，桌凳等不会损坏，学生不会去旁听而导致桌椅不够使用；要求的最佳课表是唯一的；假设在星期

8、一到星期五内没有节假日、法定假期，课程能按时上课。建立模型的流程图如下：各门课程各自不符合程度总和表达式课程编排求得最优解单门不符合程度表达式单教师课程编排分散程度表达式单门课程编排分散程度表达式各教师各自课程编排分散程度总和表达式表达式各门课程编排分散程度总和表达式总不满意程度表达式课程表编排约束原则非线性规划各教师超出工作量程度总和表达式单教师超出工作量程度各类教师补课程度系数配置座位系数教室配置类别系数四、符号及变量说明符号符号说明rcjt第几个教室的序号第几个课程的序号第几个时间段的序号，每门课程以2节课为单位进行编排，把一个星期分为二十个时间段，=1.20第几个教师的序号课程空间向量

9、，即第c个课程在第j个时间段下课程安排教室空间向量，即在第r个教室第j个时间段下的教室符号符号说明 教师空间向量，即第t个教师第j个时间段下的教师为决策变量，可以取1或0（1为真，0 为假）为决策变量，可以取1或0（1为真，0 为假）为决策变量，可以取1或0（1为真，0 为假）第c个课程的类别第c个课程的学时数第c个课程的对教室座位最大要求数；第c个课程的对教室要求的类别；第c个课程的时间要求；第r个教室的最大座位数；第r个教室的教室类别；第t个教师能胜任课程的类别；第t个教师的周最大学时；第t个教师增加的课时数第t教师的时间段： 第t个教师在第j个时间段上课 c个课程的不符合程度第t个教师课

10、程编排分散程度；第c门课程编排分散程度第t个教师超出工作量程度总不满意程度各类教师补课程度系数配置座位系数配置类别系数一组数的集合的平方差五、模型的建立与求解5.1 课程的系统系统递阶层次结构的建立 针对课程各因素之间的关系，建立如下系统的递阶图： 课程课程课程课程课程；课程类别课时数座位数教师类别时间段机房多媒体教室普通教室上午下午 5.2 五维空间向量的确立 用层次分析法的原理和表1，表2，表3中的数据构建五维空间向量集=（，） ， =（0，0，0） ，=（，0，0，），则把个数据与向量一一对应起来。其中规定如下： eq oac(,1) l的值为1，2，3，4，5，6，7，8 分别对应课程

11、类别为1，2，3，4，5，6，7，8； eq oac(,2) x的值1，2，3 分别对应周课时数为1或2，3或4，5或6； eq oac(,3) n的值分别对应其座位数； eq oac(,4) m是值为2，1，0分别对应数据中机房，多媒体教室，普通教室； eq oac(,5) h的值为1，0，0或1 分别对应，其数据中的上午，下午。则得出实际的课程向量，实际的教师向量和实际的教室向量的对应关系式为： 5.3 求第c个课程不符合程度表达式实际课程向量与要求课程向量差距越大，则越大；根据层次分析法原理来求出对应的权重为该不符合程度的值。 .5.4求单教师课程编排分散程度根据“课程编排分散程度越大，

12、则对应的时间段分散程度越大，即其值分散程度越大”的原理，以该时间段的值的平方差为该单教师课程编排分散程度的值.5.5求单课程编排分散程度同理根据“课程编排分散程度越大，则对应的时间段分散程度越大，即其值分散程度越大”的原理，以该时间段的值的平方差为该单课程编排分散程度的值 5.6 求单教师超出工作量程度 ：以为单教师超出工作量程度的值. 5.7求目标函数总不满意程度 ： 根据假设3（课表总不满意程度与各门课程各自不符合程度总和成正比，与各教师各自课程编排分散程度总和成反比，与各门课程编排分散程度总和成反比，与各教师超出工作量程度总和成反比），用 为总不满意程度 的值.5.8课程表编排约束原则

13、5.8.1同一时间段同一教室不能同时上两门或两门以上的课程； 5.8.2在任一教室上课的人数不能超过最大座位数； 5.8.3同一时间段同一教室不能同时上两门或两门以上的课程； 5.8.4在安排课程与老师配对时要符合课程类别，不能乱； 5.9 非线性规划模型最终确定（整合上述公式）5.10补课程度系数=各类教师周最大课时数之和与各教师实际课时数之和的比值5.11配置座位系数=课程要求数量与实际座位数量之差，再比上实际座位数量5.12配置系数 =课程要求与实际类别数量之差，再比上实际类别数量（二）模型的求解假使课程类别、课时数、座位数、教室类别、时间段的重要性之比=9：7：7：6：4，代入上式，再

14、利用Matlab对上述非线性规划问题进行，具体程序代码见附录1求解得到个决策变量，对应如下表（其中的序号为课程类号）： 表1.单周课表星期一星期二星期三星期四星期五12节课(C01_T01_R04)(C11_T07_R08) = 4 * GB3 (C18_T12_R02)(C37_T24_R13) = 2 * GB3 (C07_T04_R04) = 4 * GB3 (C16_T13_R16)(C34_T22_R01)(C01_T01_R04)(C11_T07_R08) = 4 * GB3 (C18_T12_R02)(C21_T14_R18) = 2 * GB3 (C07_T04_R04) =

15、4 * GB3 (C16_T13_R16)(C34_T22_R01)(C37_T24_R13) = 2 * GB3 (C08_T06_R18)(C11_T07_R08) = 4 * GB3 (C18_T12_R02)(C21_T14_R17)34节课(C04_T01_R04)(C12_T09_R02)(C31_T20_R07)(C38_T25_R13) = 2 * GB3 (C10_T04_R16) = 4 * GB3 (C19_T13_R04)(C25_T16_R01)(C33_T21_R08)(C04_T01_R04)(C12_T09_R02)(C23_T14_R18)(C29_T19_R

16、10)(C31_T20_R07) = 2 * GB3 (C10_T04_R16) = 4 * GB3 (C19_T13_R04)(C25_T16_R01)(C36_T23_R13) = 4 * GB3 (C20_T11_R02)(C29_T19_R04)(C31_T20_R07)56节课(C03_T02_R18)(C13_T10_R04)(C27_T17_R06)(C39_T25_R12)(C02_T03_R18) = 2 * GB3 (C09_T06_R17)(C22_T16_R16)(C26_T19_R10)(C36_T08_R13)(C03_T02_R18)(C13_T10_R04)(C

17、27_T17_R06)(C32_T22_R16)(C02_T03_R18) = 2 * GB3 (C09_T06_R17)(C22_T16_R16)(C39_T25_R12)(C03_T02_R18)(C13_T10_R04)(C28_T17_R06)(C36_T08_R13)78节课(C14_T09_R18) = 4 * GB3 (C17_T11_R08)(C24_T15_R09)(C28_T18_R06)(C05_T03_R08) = 2 * GB3 (C06_T05_R02)(C35_T21_R07)(C40_T23_R12)(C15_T08_R18) = 4 * GB3 (C17_T1

18、1_R08)(C24_T15_R09)(C30_T18_R06)(C05_T03_R08) = 2 * GB3 (C06_T05_R02)(C35_T21_R07)(C40_T23_R12)(C15_T08_R18)(C24_T15_R09)(C30_T18_R06)表2.双周课表星期一星期二星期三星期四星期五12节课(C01_T01_R04)(C11_T07_R08) = 4 * GB3 (C18_T12_R02)(C37_T24_R13) = 2 * GB3 (C07_T04_R04) = 4 * GB3 (C16_T13_R16)(C34_T22_R01)(C01_T01_R04)(C1

19、1_T07_R08) = 4 * GB3 (C18_T12_R02)(C21_T14_R18) = 2 * GB3 (C07_T04_R04) = 4 * GB3 (C16_T13_R16)(C34_T22_R01)(C37_T24_R13) = 2 * GB3 (C08_T06_R18)(C11_T07_R08) = 4 * GB3 (C18_T12_R02)(C21_T14_R17)34节课(C04_T01_R04)(C12_T09_R02)(C31_T20_R07)(C38_T25_R13) = 2 * GB3 (C10_T04_R16) = 4 * GB3 (C19_T13_R04)(

20、C25_T16_R01)(C33_T21_R08)(C04_T01_R04)(C12_T09_R02)(C23_T14_R18)(C29_T19_R10)(C31_T20_R07) = 4 * GB3 (C19_T13_R04)(C25_T16_R01)(C36_T23_R13)(C33_T21_R08) = 4 * GB3 (C20_T11_R02)(C29_T19_R04)(C31_T20_R07)(C23_T14_R18)56节课(C03_T02_R18)(C13_T10_R04)(C27_T17_R06)(C39_T25_R12)(C02_T03_R18) = 2 * GB3 (C09

21、_T06_R17)(C22_T16_R16)(C26_T19_R10)(C36_T08_R13)(C03_T02_R18)(C13_T10_R04)(C27_T17_R06)(C32_T22_R16)(C02_T03_R18) = 2 * GB3 (C09_T06_R17)(C22_T16_R16)(C39_T25_R12)(C26_T19_R10)(C03_T02_R18)(C13_T10_R04)(C28_T17_R06)(C36_T08_R13)78节课(C14_T09_R18) = 4 * GB3 (C17_T11_R08)(C24_T15_R09)(C28_T18_R06)(C05_

22、T03_R08) = 2 * GB3 (C06_T05_R02)(C35_T21_R07)(C40_T23_R12) = 4 * GB3 (C17_T11_R08)(C24_T15_R09)(C30_T18_R06) = 2 * GB3 (C06_T05_R02)(C35_T21_R07)(C40_T23_R12)(C15_T08_R18)(C24_T15_R09)(C30_T18_R06) 表3.教师任课检验教师编号能胜任课程类别周最大课时数对教室类别要求实际上课数需要补课数需要补课数超出周最大课时数的比例T011，84多媒体教室或机房840.5T0214普通教室62T0316普通教室71T

23、0424多媒体教室730.T0524普通教室40T0626普通教室60T0734普通教室620.T083，83普通教室或机房3+44T0934普通教室62T1036多媒体教室60T1148普通教室800.T1244普通教室40T1346多媒体教室82T1452普通教室751.T155，83普通教室或机房63T1654普通教室84T1764普通教室620.T1866普通教室60T1964多媒体教室73T2074普通教室620.3125T2176普通教室71T2276多媒体教室82T233，84普通教室或机房0+620.T244，86普通教室或机房0+60T256，84普通教室或机房0+62总体的

24、比为 0.因为总体的超出约为0.4,所以大概需46个学时.若教师的周均最大的课时数为6,则需要在聘请8位教师.则由上的比例可算出,课程类别1,2,3,4,5,6,7,8,分别需在请1,1,1,0,2,1,1,1.位教师,聘请后,每类课程所需的教师的课时基本满足.(三)模型的优化 重排原理我们看到对于许多问题，在进行搜索试探时选取集合si的顺序是任意的这就提示我们：在其他条件相当的前提下，让元素个数最少的si优先将更为有效从图1所示的同一问题的2棵不同的状态空间树，可以体会这种策略的潜力在图1(a)中，若从第1层消去1个结点，则从所有应当考虑的3元组中一次消去l2个3元组对于图1(b)，若同样是

25、从第1层消去1个结点，却只从应当考虑的3元组中消去8个3元组前者的效果明显比后者好 动态约束函数在大多数的回溯算法中，约束条件是随着搜索过程的深入而逐渐加强的我们希望将约束条件的变化也加以考虑，以此提高算法的效率图1 同一问题的2个不同状态空间树六、模型的检验 把附录中编号为COI到C40四十门课程，编号为T01到T25的二十五名教师，编号为R01到R18的十八间教室代入模块五所建立的模型中，得到结果如上述表1、2、3所示，基本符合题目中教师聘用、教室配置合理、学生上课课程安排合理等要求。 七、模型的应用与推广本模型实用性强，可根据学校不同的教学层次要求选择相应的模型，只需改变课时约束条件就可

26、求解。学校可利用此模型，快速的设计出较好的课程表。排课模型的建立很好地减少了教务系统排课的工作量，提高了工作效率。对教师资源做到最合理的应用。适合于在不同层次级别的学校推广。八、模型的评价与改进本模型的优缺点：本模型先通过分析构建出五维空间向量和列出线性方程，利用matlab模拟求解结果，使得结果的正确性和可信度高；通过构建五维的数组，使得问题的分析简单清晰；模型的建立虽然综合考虑了很多因素，但为了建立模型，理想化了许多影响因素，这使得模型具有一定的局限性，得到的最优化方案可能与实际情况有一定的出入。本模型可以推广到考虑多个老师，多个教师，多个课程，多个班的时候的情况。在解题过程中变量多，条件

27、多，过程比较麻烦，对于数据量大的实际问题解决起来繁琐。九、参考文献1 姜启源、谢金星、叶俊，数学模型，北京：高等教育出版社，2003.82 薛定宇、陈阳泉，高等应用数学问题的MATLAB求解，北京：清华大学出版社，2004.83 赵静、但 琦,数学建模与数学实验, 北京：高等教育出版社,2008.14 吴金荣关于大学课程表问题的研究J运筹与管理。2002(6)5 吴金荣求解课程表问题的分支定界法J运筹与管理，2002(1) 6 邵维忠, 杨芙清 面向对象的系统分析M . 北京: 清华大学出版社, 1998 7 周建新, 王科俊, 王文武 课表编排专家系统 J . 计算机应用, 2000( 5)

28、 : 76- 78 8 魏平, 熊伟清. 计算机辅助课表编排技术的研究 J . 甘肃工业大学学报, 1997, 23( 4) : 7681. 9 王祜民, 赵致格. 排课表问题中的分组优化决策算法 J . 控制与决策, 1999, 14( 2) : 109114. 10 王祜民, 赵致格. 时间表问题中的定额匹配算法 J . 清华大学学报, 1998, 38( 6) : 811.11 李明. 一个基于智能化搜索的排课表演算法及其client/ ser ver 实现 J . 现代计算机, 1997, 59: 2122. 12 洪力奋. 基于人工智能原理的大学课表编排模型 J . 合肥工业大学学报

29、( 自然科学版) , 1999, 22( 4) , 101104. 13 陈洁. 学校教务部门排课问题的数学模型及算法 J . 管理信息系统, 1999, 3: 5356. 14 Coad P, Yourdon E. ObjectOriented Analysis. 2nded M .Englewood Cliffs, NJ: PrenticeHall, 1991 15 Coad P, Yourdon E. ObjectOriented Design M . EnglewoodCliffs, NJ: PrenticeHall, 1991第三部分附件表1：课程属性及要求：课程编号课程类别周课时数对教室座位最大要求数对教室类别要求时间要求C011450多媒体教室上午C021430普通教室下午C031640普通教室下午C041425多媒体教室上午C051360普通教室下午C0624