魅力数模美丽力建力建学院第六届数学建模竞赛自信坚强团结创新论文题目课表编排0-1规划模型参赛编号 2008tj0804 监制：力建学院团委数学建模协会（2010年11月）力建学院第六届数学建模竞赛承诺书我们仔细阅读了第六届建工数学建模竟赛的竞赛规则。
我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与本队以外的任何人（包括指导教师）研究、讨论与赛题有关的问题。
我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。
如有违反竞赛规则的行为，我们愿意承担由此引起的一切后果。
我们的参赛编号为：2008tj0804参赛队员(签名) ：队员1：叶庆队员2：靳小龙队员3：胡传鹏课表编排问题第一部分摘要：本文根据制定课表时需考虑的问题,建立了冲突最少的0-1规划模型；求解得课表，并根据所得结果对教师聘用,教室的配置,来做出合理的建议。
考虑目标函数时，分析课表编排要符合的条件为：课程要求、教师课程编排尽量分散、同课程编排尽量分散、教师超出工作量尽量少。
则我们目标函数冲突最少分解为：各门课程各自不符合程度总和最少、各教师各自课程编排分散程度总和最大、各门课程编排分散程度总和最大、各教师超出工作量程度总和最少。
考虑约束条件时，分析附录中的相关数据,得到课程编排的影响因素有,时间,教室,课程等，则可以根据此来约束目标函数。
根据以上考虑因素建立系统递阶图,使目标更清晰。
建立空间向量，已知数据与空间向量一一对应。
根据课程要求与实际编排差距最少原理，建立目标函数。
加上课表编的约束条件,进行优化,用Matlab求解课表.再根据求解得课表与相关系数指标为教师聘用,教室的配置,来做出合理建议.关键词：课表编排系统递阶图空间向量第二部分一、问题重述某高校现有课程40门，编号为C01～C40；教师共有25名，编号为T01～T25；教室18间，编号为R01～R18。
具体属性及要求见表1，表2，表3：课表编排规则：每周以5天为单位进行编排；每天最多只能编排8节课，上午4节，下午4节，特殊情况下可以编排10节课，每门课程以2节课为单位进行编排，同类课程尽可能不安排在同一时间。
你所要解决的问题：请你结合实际情况给出较为合理的课表编排方案，分析你所给出的方案的合理性。
对教师聘用，教室配置给出合理化建议。
二、问题的分析问题分析为先建立合理的课表编排方案，再从课表编排方案中分析对教师聘用，教室配置给出合理化建议。
针对问题一：1、该问题要求给出合理的课表编排方案，分析如下：（1）、总体上尽量使每门课程符合要求，即求各门课程各自不符合程度总和最低；（2）、总体上使同一老师的课程尽量分散，即求其总各教师各自课程编排分散程度总和最大；（3）、总体上使每门课程的编排尽量分散，即求各门课程编排分散程度总和表达式最大；（4）、总体上使同一老师相对超出的工作量尽量少，各教师超出工作量程度总和最少。
2、针对编排方案约束条件如下： （1）、同一时间段同一教室不能同时上两门或两门以上的课程； （2）、在任一教室上课的人数不能超过最大座位数； （3）、同一时间段同一教室不能同时上两门或两门以上的课程； （4）、在安排课程与老师授课类别要符合课程类别，不要造成混乱；利用层次分析法，求出表示不同程度的权重表达式，把以上各点要达到的目标整合成为单目标的总目标0-1规划问题。
针对问题二：1、根据教师聘用则要求分析出哪一类课程需要的教师越少，则越要聘用教那一类课程的教师。
各类教师少的程度可用各类教师补课程度系数l BB （各类教师周最大课时数之和与各教师实际课时数之和的比值）来作分析参考，系数l BB 越大则该类教师越少，应尽量聘用能胜任该类课程的教师。
2、针对教室配置给出合理化则要求分析出：（1）对各类教室配置座位数量应为多少才合理；（2）各教室类别（机房，多媒体教室，通教室）数量的应为多少才合理； 则可以从应配置座位系数l CC （数量与实际座位数量之差，再比上实际座位数量）和配置类别系数l DD （课程要求与实际类别数量之差，再比上实际类别数量）分析可得：座位系数l CC 越大，则对各类教室配置座位数量需求越大，则越要配置多一点座位，反之越小；配置类别系数l DD 越大，则各教室类别（机房，多媒体教室，通教室）数量需求越大，则越要配置多一点该类别教室，反之则越小。
三、模型假设1、假设机房、多媒体教室和普通教室三者的重要性系数之比为3︰2︰1； （机房可以当作多媒体教室用，而多媒体教室也可以当普通教室用）2、假设课程类别、课时数、座位数、教师类别、时间段的重要性之比为1a ︰2a ︰3a ︰4a ︰5a ；3、假设每位教师都不会生病请假而能正常上课；4、假设每个教室的设备都能正常运作，桌凳等不会损坏，学生不会去旁听而导致桌椅不够使用；5、要求的最佳课表是唯一的；6、假设在星期一到星期五内没有节假日、法定假期，课程能按时上课。
建立模型的流程图如下：四、符号及变量说明符号 符号说明r c jtcj c rj R第几个教室的序号 第几个课程的序号第几个时间段的序号，每门课程以2节课为单位进行编排，把一个星期分为二十个时间段，j =1 (20)第几个教师的序号课程空间向量，即第c 个课程在第j 个时间段下课程安排教室空间向量，即在第r 个教室第j 个时间段下的教室符号符号说明tj Tcj w rj wtj wc lc xc n c m c hr n r mt lt xtz thtj htj Hc vt v ' cv '' t v ''' VVl BB l CCl DD X S教师空间向量，即第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 个教师课程编排分散程度； 第c 门课程编排分散程度 第t 个教师超出工作量程度总不满意程度各类教师补课程度系数配置座位系数 配置类别系数 一组数的集合X 的平方差五、模型的建立与求解5.1 课程的系统系统递阶层次结构的建立针对课程各因素之间的关系，建立如下系统的递阶图：5.2 五维空间向量的确立用层次分析法的原理和表1，表2，表3中的数据构建五维空间向量集c =（c l ，c x ，c n ，c m ，c h ） ， r R=（0，0，r n ，r m ，0） ， t T=（t l ，t x ，0，0，t h ），则把个数据与向量一一对应起来。
其中规定如下：○1 l 的值为1，2，3，4，5，6，7，8 分别对应课程类别为1，2，3，4，5，6，7，8；○2 x 的值1，2，3 分别对应周课时数为1或2，3或4，5或6； ○3 n 的值分别对应其座位数； ○4 m 是值为2，1，0分别对应数据中机房，多媒体教室，普通教室； ○5 h 的值为1，0，0或1 分别对应，其数据中的上午，下午。
则得出实际的课程向量cj c ，实际的教师向量rj R 和实际的教室向量tj T 的对应关系式为：⎪⎪⎩⎪⎪⎨⎧==++=的余数整除的余数整除22),0,0,,()0,,,0,0(),,,,(tj tj cj cj tj tj tj tj tj tj rj rj rj rj cj cj cj cj cj cj cj H h H h h z x l T w m n R w h m n x l c w5.3 求第c 个课程不符合程度c v 表达式实际课程向量cj c 与要求课程向量c c 差距越大，则c v 越大；根据层次分析法原理来求出对应的权重为该不符合程度c v 的值。
()()()cc rj c c rj c c rj ctj t c h h h a m m m a n n n a x xc z x a v ----+=5432)(……………….①5.4求单教师课程编排分散程度t v '根据“课程编排分散程度越大，则对应的时间段分散程度越大，即其值分散程度越大”的原理，以该时间段的值的平方差为该单教师课程编排分散程度t v '的值20....1,)(=='j S v tj rj H w t ………………………………………………………………………………..②5.5求单课程编排分散程度c v ''同理根据“课程编排分散程度越大，则对应的时间段分散程度越大，即其值分散程度越大”的原理，以该时间段的值的平方差为该单课程编排分散程度cv ''的值20...1,)(==''j S v cj cj H w c……………………………………………………………………………… ③5.6 求单教师超出工作量程度t v ''：以该教师超出的学时数表中对应该教师最大学时数为单教师超出工作量程度t v ''的值tt tz v x '''=………………………………………………………………………………………….. ④5.7求目标函数总不满意程度VV：7、根据假设3（课表总不满意程度与各门课程各自不符合程度总和成正比，与各教师各自课程编排分散程度总和成反比，与各门课程编排分散程度总和成反比，与各教师超出工作量程度总和成反比），用⨯⨯各门课程各自不符合程度总和各教师各自课程编排分散程度总和各门课程编排分散程度总和各教师超出工作量程度总和为总不满意程度VV的值∑∑∑∑===='''''''=401251251401c t t ct t c c v v v vVV …………………………………………………………………….⑤5.8课程表编排约束原则5.8.1同一时间段同一教室不能同时上两门或两门以上的课程；20...1,1401==∑=j Wc cj5.8.2在任一教室上课的人数不能超过最大座位数；20...1,=≤j m m r cj5.8.3同一时间段同一教室不能同时上两门或两门以上的课程；20...1,1401==∑=j Wc tj5.8.4在安排课程与老师配对时要符合课程类别，不能乱； 40....1,20...1,===c j lc l cj5.9 非线性规划模型最终确定（整合上述公式）∑∑∑∑===='''''''=401251251401min c t tc t t c c v v v vVV 目标函数()()()⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎧======≤==='''==''=='----+===++=∑∑∑===40....1,20...1,20...1,120...1,20...1,120...1,20....1,)(22),0,0,,()0,,,0,0(),,,,(.401401251)()(5432c j lc l j W j m m j W x z v j S v j Sv h h h a m m m a n n n a x xc z x a v H h H h h z x l T w m n R w h m n x l c w st cj c tj rcjc cj t j ti t H w c H w tc c rj c c rj c c rj c tj tc tjtj cj cj tj tj tj tj tj tj rj rj rj rj cj cj cj cj cj cj cj cj cj tj rj 的余数整除的余数整除5.10补课程度系数l BBl BB =各类教师周最大课时数之和与各教师实际课时数之和的比值 5.11配置座位系数l CCl CC =课程要求数量与实际座位数量之差，再比上实际座位数量 5.12配置系数l DDl DD =课程要求与实际类别数量之差，再比上实际类别数量 （二）模型的求解假使课程类别、课时数、座位数、教室类别、时间段的重要性之比54321::::a a a a a =9：7：7：6：4，代入上式，再利用Matlab 对上述非线性规划问题进行，具体程序代码见附录1 求解得到个决策变量cj w rj w tj w ，对应如下表（其中的序号为课程类号）：表2.双周课表因为总体的超出约为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)，若同样是从第1层消去1个结点，却只从应当考虑的3元组中消去8个3元组．前者的效果明显比后者好．②动态约束函数在大多数的回溯算法中，约束条件是随着搜索过程的深入而逐渐加强的．我们希望将约束条件的变化也加以考虑，以此提高算法的效率．图1 同一问题的2个不同状态空间树六、模型的检验把附录中编号为COI到C40四十门课程，编号为T01到T25的二十五名教师，编号为R01到R18的十八间教室代入模块五所建立的模型中，得到结果如上述表1、2、3所示，基本符合题目中教师聘用、教室配置合理、学生上课课程安排合理等要求。