文档介绍：题目:基于二部图及组合规划编程分别求解排课问题摘要排课问题是一个多因索、多吋间、多空间、模糊性极强等优化决策问题,组合规划屮的典型问题,属于NP完全类问题。在本题主要根据现有的教室资源、教师资源和课程要求进行排课。模型一:利用二部图和图着色的结合来构建排课模型,通过偶图匹配实现排课四要素的组合,利用图着色控制寻优方向能满足更多排课约束的二部图关系模型二:基于此种原因,我们先对各个元素间的冲突做预处理,进行约束条件的规划,再通过matlab软件将教室、教师、课程和时间间的约束条件统一化,构成R-T-C表(详见附表),再将各个元素进行优先级的计算,从而根据排课的优化模型,求出最优解。经过对数据的综合研究,不难发现教师资源稀缺。课程要求160个课时,而现有教师可供的课吋为116个。故先不考虑教师,而是向教室屮安排课程。同类课不安排在一起,隔一天上同一课。排出一个按教室上课的课表。通过对其分析,发现很多课没老师和老师没课上的情况,然后进行合理调整。最后发现需要外聘14为老师。关键字NP完全类问题、组合规划、数量化、多H标函数、优先级、matlab软件、图论、二部图、着色法。问题分析排课问题是根据教学计划和任务安排,根据教室与教师资源、吋间及课程需求,为课程安排教师及教室,从而得到对于每个课程、教室及教师的完备、正确及合理的课表。对于课表,有要求如下:1、 完备原则1)所有课已排完2、 正确性原则1) 同一吋间同一教室只能有一个教师授同一门课。2) 同一时间同一教师只能在同一教室上同一门课。3) 每门课程的教室应符合其特定的类型。4) 每个教师必须承担其能胜任的课程。5) 教室座位数必须大于或等于上课的学生数。3、 合理性原则1) 尽可能是同学在连续两堂课Z间更换教室所用的吋间少。2) 尽可能让同一门课的不同课次安排在同一个教室。3) 尽可能按照课程要求按排上课吋间。4) 尽可能按照教师的要求安排其上课吋间。模型假设:1、 学校的教师和教室资源及学生班结构在一个学期内不会有的变动。2、 所有的教室都在同一•个校区,且1〜2节课的教室到3〜4节课的教室的路程不超过lOmirio3、 在一学期内,任课教师身体都非常健康,不存在因病因事缺课的情况。4、 各种教学资源(课桌、多媒体、机房电脑)在一学期内都不会发生故障,影响上课。5、 在上课期间,老师、学生都不迟到,不影响上课质量。6、 半有3个课吋吋,我们半做2个课吋处理,及3节连堂上。变量假设心教室编号”1,2,3•…18C”课程类别n=l,2,3・・・.4OA教师编号 n=1,2,3••…25YTn外聘教师编号n=l,2,3•.…k根据教室属性不同分成JI、KI、L1:J1表示普通教室B1表示多媒体教室L1表示机房教室利用根据教室容纳量不同分成J2、K2、:J2表示能容纳100人的大型教室K2表示能容纳60人的屮型教室L2表示能容纳50人的11«小型教室M2表示能容纳40人的小型教室根据教室上课的时间分成J3、K3、L3:J3表示时间为上午K3表示时间为下午L3表示吋间不限P(TRC)T老师在/?教室上C课X】教室利用率X3教师满意度D优化级的量度值%权衡教室利用率参数也权衡教师满意度参数Q安排课程的最优值为充分利用教室资源,我们定义:教室利用率二上课总人数教室最大容纳量模型建立及求解模型一用二部图G(V,E)的方法,将课程分配到教室屮。排岀一个按教室排课的课表。一、二部图的定义定义:设无向图G=(V,E),如果存在7的一个分划使得冷的每一条边的两个端点分属人和仏,则称G为二部图(或偶图)。人和仏称为互补结点子集,此时可将G记为G=(Vl9E9V2)显然,二部图没有自环,在互补结点子集VI和V2内各结点互不邻接。定义:在二部图G=(V;,EV2)小,如果%的每个结点与%的每个结点有且仅有一条边相关联,则称Q为完全二部图,记为Kmn,其屮加二旳山=|V2|・e匹配问题:设G=(V^E,V2)是二部图,若MuE,且%小任何两条边均不相邻,贝IJ称掰是&的一个匹配;具有最大边数的匹配称为最大匹配;若最大匹配必满足|M|=min{|^|,|^2|},则称力是G的一个完备匹配,此时若|叫|勻匕|,则称擀为人到%的一个完备匹配;若忆|=|匕|=|必|,则称力是&的一个完美匹配.©0最大匹配,无完备匹配,更无完美匹配{e^e^ej}为完备匹配,但无完美匹配{^i,e2,e3}为完备匹配,也是完美匹配二、图与图着色及其在课表编制小的应用许多问题如资源分配、存贮、货物的装载和运算及课表编排调度,,(A、B、C、D、E)和7条边(AB、BC、、CD、CE、DE)•两个顶点