《数学建模3的论文.doc》由会员分享，可在线阅读，更多相关《数学建模3的论文.doc（31页珍藏版）》请在金锄头文库上搜索。
1、题目：基于二部图及组合规划编程分别求解排课问题摘要排课问题是一个多因素、多时间、多空间、模糊性极强等优化决策问题，组合规划中的典型问题，属于NP完全类问题。在本题主要根据现有的教室资源、教师资源和课程要求进行排课。模型一：利用二部图和图着色的结合来构建排课模型，通过偶图匹配实现排课四要素的组合，利用图着色控制寻优方向能满足更多排课约束的二部图关系模型二：基于此种原因，我们先对各个元素间的冲突做预处理，进行约束条件的规划，再通过matlab软件将教室、教师、课程和时间间的约束条件统一化，构成R-T-C表（详见附表），再将各个元素进行优先级的计算，从而根据排课的优化模型，求出最优解。经过对数据的综
2、合研究，不难发现教师资源稀缺。课程要求160个课时，而现有教师可供的课时为116个。故先不考虑教师，而是向教室中安排课程。同类课不安排在一起，隔一天上同一课。排出一个按教室上课的课表。通过对其分析，发现很多课没老师和老师没课上的情况，然后进行合理调整。最后发现需要外聘14为老师。关键字NP完全类问题、组合规划、数量化、多目标函数、优先级、matlab软件、图论、二部图、着色法。问题分析排课问题是根据教学计划和任务安排，根据教室与教师资源、时间及课程需求，为课程安排教师及教室，从而得到对于每个课程、教室及教师的完备、正确及合理的课表。对于课表，有要求如下：1、完备原则1) 所有课已排完2、 正确
3、性原则1) 同一时间同一教室只能有一个教师授同一门课。2) 同一时间同一教师只能在同一教室上同一门课。3) 每门课程的教室应符合其特定的类型。4) 每个教师必须承担其能胜任的课程。5) 教室座位数必须大于或等于上课的学生数。3、 合理性原则1) 尽可能是同学在连续两堂课之间更换教室所用的时间少。2) 尽可能让同一门课的不同课次安排在同一个教室。3) 尽可能按照课程要求按排上课时间。4) 尽可能按照教师的要求安排其上课时间。模型假设：1、 学校的教师和教室资源及学生班结构在一个学期内不会有的变动。2、 所有的教室都在同一个校区，且12节课的教室到34节课的教室的路程不超过10min。3、 在一学
4、期内，任课教师身体都非常健康，不存在因病因事缺课的情况。4、 各种教学资源（课桌、多媒体、机房电脑）在一学期内都不会发生故障，影响上课。5、 在上课期间，老师、学生都不迟到，不影响上课质量。6、 当有3个课时时，我们当做2个课时处理，及3节连堂上。变量假设教室编号 n=1,2,3.18课程类别 n=1,2,3.40教师编号 n=1,2,3.25外聘教师编号 n=1,2,3.根据教室属性不同分成J1、K1、L1：J1表示普通教室B1表示多媒体教室L1表示机房根据教室容纳量不同分成J2、K2、L2、M2： J2表示能容纳100人的大型教室K2表示能容纳60人的中型教室L2表示能容纳50人的中小型教
5、室M2表示能容纳40人的小型教室根据教室上课的时间分成J3、K3、L3：J3表示时间为上午K3表示时间为下午L3表示时间不限老师在教室上课教室利用率教师满意度优化级的量度值权衡教室利用率参数权衡教师满意度参数安排课程的最优值 bc ade教室利用率：为充分利用教室资源，我们定义：教室利用率=。模型建立及求解模型一用二部图的方法，将课程分配到教室中。排出一个按教室排课的课表。1、 二部图的定义定义 ：设无向图，如果存在V的一个分划，使得G的每一条边的两个端点分属V1和V2，则称G为二部图(或偶图)。V1和V2称为互补结点子集，此时可将G记为 显然，二部图没有自环，在互补结点子集V1和V2内各结点
6、互不邻接。 bc ade例如：下图中b、c 和a、d、e的关系。badec定义：在二部图中, 如果V1的每个结点与V2的每个结点有且仅有一条边相关联，则称G为完全二部图,记为,其中匹配问题：设是二部图，若，且M中任何两条边均不相邻，则称M是G的一个匹配；具有最大边数的匹配称为最大匹配；若最大匹配M满足，则称M是G的一个完备匹配，此时若，则称M为V1到V2的一个完备匹配；若，则称M是G的一个完美匹配2、 图与图着色及其在课表编制中的应用许多问题如资源分配、存贮、货物的装载和运算及课表编排调度，都可在图论里用着色问题来表示在图论中，图可以表示为一组顶点的非空有限集和一组连接某些顶点的边的集合图l中
7、的图有5个顶点（A 、B、C、D、E )和7条边 （AB、BC、BD、BE、CD、CE、DE)两个顶点用一条公共边相连，则说明这两个顶点为邻接点，否则为非邻接点在图l中，顶点A和顶点B是邻接的，而A和E是非邻接的图1 （具有5顶点和7条边的图） 图2 （表明有各顶点着色的图） 图中某个顶点的度指的是与该顶点相关联的边的数目图l中A、BC、D、E 各顶点的度分别为l、4、3、3、3一个图中的顶点着色涉及以这样一种方式来着色该图的顶点即不相邻的两个顶点着色相同图l所表示的图可以用4种颜色来着色，如图2所示图2中的1，2，3，4表示为不同的颜色当然也可以每个顶点都用一种不同的颜色来着色，但是颜色数却
8、增多-在顶点着色中，主要的原则是用最少数量的颜色对图进行着色，这个最少数称为该图的颜色数。如果限定时间表问题是课次只涉及一节课仅一个教师对一个班级，则可以简单地用着色问题每节课在图里用一个顶点表示，然后它可以加入到任何包括相同班级和(或)老师的其它的课次顶点考虑表1中d个老师和3个班级的时间表要求它可以用图3表示用两种颜色着色依次加入的课次顶点为同一班级和(或)老师，它们不能保留在一起它们是互相冲突的，在顶点着色里，给它们分配不同的颜色在第一个题目中，我们不用考虑教师的聘任情况，所以只用考虑一下几个元素：课程编号，对教室座位最大要求数，对教室类别要求，时间。我们首先对教室的类型，把他们划归为J
9、1,K1,L1 三类J1(普通教室) R02 R03 R05 R06 R07 R08 R09 R11 R17 R18K1（多媒体教室）R01 R04 R10 R16L1（机房） R12 R13 R14 R15然后再按照教室能容纳学生数目的多少，把他们划归为J2,K2,L2,M2 四类J2(能容纳100人的大型教室) R01 R02 R03K2(能容纳60人的中型教室) R08 R09 R10 R11 R12L2(能容纳50人的中小型教室)R04 R05 R06 R07 R17M2(能容纳40人的小型教室)R13 R14 R15 R16 R18按照时间分类，把他们化为J3,K3 L3三类。J3(
10、上午) C01 C04 C07 C10 C11 C12 C16 C18 C19 C20 C21 C23 C25 C29 C31 C34 C37 C38K3(下午) C02 C03 C05 C06 C08 C09 C13 C14 C15 C17 C22 C24 C26 C27 C28 C30 C32 C35 C39 L3（不限） C33 C36 C40根据40门课程的需要，我们排出了40门课对教室的要求情况课程教室种类教室容量（大于或等于）课程教室种类教室容量（大于或等于）C01K1L2C21J1M2C02L1M2C22K1M2C03LIM2C23J1M2C04K1M2C24J1K2C05L1K
11、2C25K1J2C06L1J1C26K1L2C07K1L2C27J1M2C08L1M2C28J1M2C09L1M2C29K1L2C10K1M2C30J1M2C11L1K2C31J1M2C12L1J1C32K1M2C13K1L2C33J1K2C14L1M2C34K1J2C15L1M2C35J1L2C16K1M2C36L1M2C17L1K2C37L1M2C18L1J1C38L1M2C19K1L2C39L1K2C20L1L2C40L1L2我们先分析最简单的情况，假设只有4门课程C01-C04,只有4个教室R01-RO4候选课程编号课程类别周课时数对教室座位最大要求数对教室类别要求时间要求C01145
12、0多媒体上午C021430普通教室下午C031640普通教室下午C041425多媒体上午表3教室属性教室编号最大座位数教室类别R01100多媒体教室R02100普通教室R03100普通教室R0450多媒体教室做出他们的二部图与匹配关系。C02 C03 C04(1) J教室总类和课程的匹配图C01R01 R02 R03 R04(2) 教室容量和课程的匹配图C01 C02 C03 C04 R01 R02 R03 R04（3） 对应时间和课程的匹配图由图可以很显然的看出他们的匹配和冲突关系根据3图即可简要做出4门课在某一个半天的课程表上课教室上课时间C01R01上午12节C02R03下午12节C03
13、R02下午12节C04R04上午12节三、模型一得改进与推广课程变为40门课，教室增加至18个，而对应的时间，也是由某一个半天增加至5天40个课时的安排。经过分析，我们需将所有课程尽量合理的安排在一个星期内。学校从周一到周五上课,每天上8 节课,上午4 节,下午4 节,每两节课为一个授课单元,所以每周共有20 个授课单元. 这里每个授课单元从周一上午(1 ,2) 节到周五下午(3 ,4) 节,分别由课时1 ,2 ,，20 来表示,例如:课时10 表示周三上午(3 ,4) 节。不考虑教室和教学设备的因素,即认为教室和教学设备总是可以使用的用边着色理论分配课时根据图论的边着色理论,边着色是指种颜色1 , 2 , ,对于图中各边的一种分配方案,着色时若没有相邻的两条边颜色相同,则
