课表编排问题-数学建模

魅魅魅力力力数数数模模模美美美丽丽丽力力力建建建力建学院第六届数学建模竞赛自信坚强团结创新论文题目课表编排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、根据教师聘用则要求分析出哪一类课程需要的教师越少，则越要聘用教那一类课程的教师。各类教师少的程度可用各类教师补课程度系数lBB（各类教师周最大课时数之和与各教师实际课时数之和的比值）来作分析参考，系数lBB越大则该类教师越少，应尽量聘用能胜任该类课程的教师。2、针对教室配置给出合理化则要求分析出：（1）对各类教室配置座位数量应为多少才合理；（2）各教室类别（机房，多媒体教室，通教室）数量的应为多少才合理；则可以从应配置座位系数lCC（数量与实际座位数量之差，再比上实际座位数量）和配置类别系数lDD（课程要求与实际类别数量之差，再比上实际类别数量）分析可得：座位系数lCC越大，则对各类教室配置座位数量需求越大，则越要配置多一点座位，反之越小；配置类别系数lDD越大，则各教室类别（机房，多媒体教室，通教室）数量需求越大，则越要配置多一点该类别教室，反之则越小。三、模型假设1、假设机房、多媒体教室和普通教室三者的重要性系数之比为3︰2︰1；（机房可以当作多媒体教室用，而多媒体教室也可以当普通教室用）2、假设课程类别、课时数、座位数、教师类别、时间段的重要性之比为1a︰2a︰3a︰4a︰5a；3、假设每位教师都不会生病请假而能正常上课；4、假设每个教室的设备都能正常运作，桌凳等不会损坏，学生不会去旁听而导致桌椅不够使用；5、要求的最佳课表是唯一的；6、假设在星期一到星期五内没有节假日、法定假期，课程能按时上课。建立模型的流程图如下：四、符号及变量说明符号符号说明rcjtcjcrjR第几个教室的序号第几个课程的序号第几个时间段的序号，每门课程以2节课为单位进行编排，把一个星期分为二十个时间段，j=1….20第几个教师的序号课程空间向量，即第c个课程在第j个时间段下课程安排教室空间向量，即在第r个教室第j个时间段下的教室各门课程各自不符合程度总和表达式课程编排求得最优解单门不符合程度表达式单教师课程编排分散程度表达式单门课程编排分散程度表达式各教师各自课程编排分散程度总和表达式表达式各门课程编排分散程度总和表达式总不满意程度表达式课程表编排约束原则非线性规划各教师超出工作量程度总和表达式单教师超出工作量程度各类教师补课程度系数lBB配置座位系数lCC教室配置类别系数lDD符号符号说明tjTcjwrjwtjwclcxcncmchrnrmtltxtzthtjhtjHcvtvcvtvVVlBBlCClDDXS教师空间向量，即第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=（cl，cx，cn，cm，ch），rR=（0，0，rn，rm，0），tT=（tl，tx，0，0，th），则把个数据与向量一一对应起来。其中规定如下：○1l的值为1，2，3，4，5，6，7，8分别对应课程类别为1，2，3，4，5，6，7，8；○2x的值1，2，3分别对应周课时数为1或2，3或4，5或6；○3n的值分别对应其座位数；○4m是值为2，1，0分别对应数据中机房，多媒体教室，普通教室；○5h的值为1，0，0或1分别对应，其数据中的上午，下午。则得出实际的课程向量cjc，实际的教师向量rjR和实际的教室向量tjT的对应关系式为：课程课程1课程2………课程c课程40；；；课程类别课时数座位数教师类别时间段8...216...32100...3025机房多媒体教室普通教室上午下午的余数整除的余数整除22),0,0,,()0,,,0,0(),,,,(tjtjcjcjtjtjtjtjtjtjrjrjrjrjcjcjcjcjcjcjcjHhHhhzxlTwmnRwhmnxlcw5.3求第c个课程不符合程度cv表达式实际课程向量cjc与要求课程向量cc差距越大，则cv越大；根据层次分析法原理来求出对应的权重为该不符合程度cv的值。ccrjccrjccrjctjtchhhammmannnaxxczxav5432)(……………….①5.4求单教师课程编排分散程度tv根据“课程编排分散程度越大，则对应的时间段分散程度越大，即其值分散程度越大”的原理，以该时间段的值的平方差为该单教师课程编排分散程度tv的值20....1,)(jSvtjrjHwt………………………………………………………………………………..②5.5求单课程编排分散程度cv同理根据“课程编排分散程度越大，则对应的时间段分散程度越大，即其值分散程度越大”的原理，以该时间段的值的平方差为该单课程编排分散程度cv的值20...1,)(jSvcjcjHwc………………………………………………………………………………③5.6求单教师超出工作量程度tv：以该教师超出的学时数表中对应该教师最大学时数为单教师超出工作量程度tv的值tttzvx…………………………………………………………………………………………..④5.7求目标函数总不满意程度VV：7、根据假设3（课表总不满意程度与各门课程各自不符合程度总和成正比，与各教师各自课程编排分散程度总和成反比，与各门课程编排分散程度总和成反比，与各教师超出工作量程度总和成反比），用各门课程各自不符合程度总和各教师各自课程编排分散程度总和各门课程编排分散程度总和各教师超出工作量程度总和为总不满意程度VV的值401251251401cttcttccvvvvVV…………………………………………………………………….⑤5.8课程表编排约束原则5.8.1同一时间段同一教室不能同时上两门或两门以上的课程；20...1,1401jWccj5.8.2在任一教室上课的人数不能超过最大座位数；20...1,jmmrcj5.8.3同一时间段同一教室不能同时上两门或两门以上的课程；20...1,1401jWctj5.8.4在安排课程与老师配对时要符合课程类别，不能乱；40....1,20...1,cjlclcj5.9非线性规划模型最终确定（整合上述公式）401251251401mincttcttccvvvvVV目标函数40....1,20...1,20...1,120...1,20...1,120...1,20....1,)(22),0,0,,()0,,,0,0(),,,,(.401401251)()(5432cjlcljWjmmjWxzvjSvjSvhhhammmannnaxxczxavHhHhhzxlTwmnRwhmnxlcwstcjctjrcjccjtjtitHwcHwtccrjccrjccrjctjtctjtjcjcjtjtjtjtjtjtjrjrjrjrjcjcjcjcjcjcjcjcjcjtjrj的余数整除的余数整除5.10补课程度系数lBBlBB=各类教师周最大课时数之和与各教师实际课时数之和的比值5.11配置座位系数lCClCC=课程要求数量与实际座位数量之差，再比上实际座位数量5.12配置系数lDDlDD=课程要求与实际类别数量之差，再比上实际类别数量（二）模型的求解假使课程类别、课时数、座位数、教室类别、时间段的重要性之比54321::::aaaaa=9：7：7：6：4，代入上式，再利用Matlab对上述非线性规划问题进行，具体程序代码见附录1求解得到个决策变量c