摘要
课表编排是一个充满冲突的过程，所开课程的上课时间、上课班级、上课地点、任课教师等多方面因素限制教学资源分配。为了提升高校的办学效率，更好地完成教学任务，本文以教室数目作为目标，建立了以教室数目最少的目标决策模型。 在问题一中，我们以教室数目最少作为目标，对各种情况做了详细定义，巧妙地引入了0-1变量，将问题转换为以教室数目总和最少为目标的整数规划模型：
Min Z=∑x i
在模型的求解中，我们使用matlab，使用数据库快速插入算法，得到了完整的课程表以及结果：最小教室数目为9个，A类6间，B、C、E类各一间。
在问题二中，我们考虑到必修课的约束条件，增加了对问题一中的约束，利用问题一中类似的方法得出了结果。
对于问题三，为了使教室数目保持不变，我们将问题一、二所使用的目标函数转换为第三问的约束条件，建立了将必修课在4、5时间段出现以及周五4、5时间段出现的课时作为目标函数的模型：
MIN Z=∑x s,c,l,r,t+∑x s,c,l,r,t
D={5}∩Q={4,5}
Q={4，5}∩LB={1}
对于问题四，我们从教室（包括机房）的利用率、开课对象的上课强度、问题3的不满足率这三个方面来对问题三的结果进行了评价，并提出了一定的建议。
关键词：整数规划；目标函数；约束条件；Matlab.
一、问题重述
在国家对高等教育大力发展政策的激励下，高等教育事业得到了迅速发展，由于在校学生人数急剧增加，教学硬件设施增长缓慢、教师资源短缺，如何利用有限的资源，以最优形式满足教学需求成为目前急需解决的问题。
课表编排是一个充满冲突的过程，所开课程的上课时间、上课班级、上课地点、任课教师等多方面因素限制教学资源分配。为了提升高校的办学效率，更好地完成教学任务，如何应用现代信息化技术在时间上和空间上合理分配教学资源成为亟待解决的问题。
本问题假定在某一学期18教学周内安排教学任务，每个教学周星期一至星期五安排课程，每天分为上午2个时间段（时间段1和时间段2），下午2个时间段（时间段3和时间段4），晚上1个时间段（时间段5），每个时间段2学时安排同一门课程，同一班级的不同课程不考虑课程内容之间的前后逻辑关系。开课对象由6位数字表示，如040101等。第一二位04表示学院，第三位0表示专业，第四五位10表示年级，第六位1表示班级。教室、机房规格分类见附件1。
请你们依据附件1-附件3提供的数据解决以下问题。
1.根据附件1-附件2的数据，建立所需各类教室（包括机房）数目最少的数学模型，给出求解算法和每个教室（包括机房）、每个班级、每位教师的课程安排结果。
2.根据附件1和附件3的数据，要求必修课程不安排在时间段4和时间段5，建立所需各类教室（包括机房）数目最少的数学模型，给出求解算法和每个教室（包括机房）、每个班级、每位教师的课程安排结果。
3.根据附件1和附件3的数据，在问题2中满足教学需求的各类教室（包括机房）数量不变的基础上，要求必修课程尽量少安排在时间段4和时间段5，带*的课程尽量少安排在时间段1和时间段5，每周星期五的时间段4和时间段5尽量少安排课程。建立问题的数学模型，给出求解算法和每个教室（包括机房）、每个班级、每位教师的课程安排结果。
4.建立合理的指标体系，例如教室（包括机房）的利用率、开课对象的上课强度、问题3的不满足率等，对于你们给出问题3的结果进行评价，并给出解决对策。
二、模型假设
1.假设同一课程的所有学时不安排在同一天；
2.为了简化问题，我们假设每一课程占用的教室都是一整学期的，即不考虑教
室的再利用；
3.假设非机房教室不能使用机房；
潍坊市政坛地震
三、变量及符号说明
3.1 符号说明
符号 说明
D Q C CC L R S q LB M
D 表示日集合
Q 表示时间段集合
C 表示班级集合
CC 表示合班集合武士道精神
L 表示课程集合
R 表示教师空课集合
S 表示班级空课集合国税31号文
q 表示对应的班级人数
LB 表示课程类别
M 表示教室类别 3.2 定义[1]
3.2.1 日集合的定义
D={1,2,3,4,5}，其中1表示周一，2表示周二，以此类推。
3.2.2 时间段集合的定义
Q 表示时间段集合，Q={1,2,3,4,5}，1表示第一个时间段，即上午第1、2节课，2表示第二个时间段，即上午第3、4节课。实际上，我们通过时间片的这种定义方式，避免了在整数规划模型中考虑课程连续安排的约束条件，而对于这种约束条件的求解是非常困难的。
3.2.3 班级集合C 的定义
需要上课的班级集合C ，C 中的基本元素是班级代码c ；合班集合CC ，CC 中的基本元素为合班代码cc 。一个合班代码对应多个班级代码。因此可以认为每个合班代码cc 均是班级集合C 的子集。
3.2.4 其他变量
根据排课问题的约束条件和衡量标准，引入0-1型变量：t r l c s x ,,,，其中s ∈S ，c ∈CC ，l ∈L ，r ∈R ，t ∈T 。当由教师t 对班级c 所授的课程1，被安排在时间片s 和教室r 的时候，变量t r l c s x ,,,，取值为1，其他情况变量t r l c s x ,,,，取值为0。
四、问题分析
寄存器传输级4.1 问题一的分析
对于问题一，需要建立所需教室数目最少的数学模型，为了达成目标，我们
考虑将目标函数MIN设为教室数目总和，将教师，学生在同一时间段不能重复上课作为约束条件，建立一个整数规划问题对其进行求解。
考虑到每堂课每周的课时不同，我们先将课程附件进行处理得到一个更为明确的表格信息，通过对每堂课的次数的添加，从而将所有课程的权重统一化。考虑到课程不可能一次性学完，对于每两次课的间隔时间定义了一个阈值，以保证每两堂课不可能同一天出现。
对于机房和教室类别，我们首先考虑每个教室容量足够大（即都使用最大容量的教室）以便求出总教室数目。之后通过得到的结果以及对应的人数，再进一步分析教室类别。
4.2 问题二的分析
对于问题二，在问题一的基础上，考虑对必修课程的时间段条件进行约束，即增加∀s∈S,∀t∈T,∀cc∈CC,∀r∈R ∑x s,c,l,r,t=0
的约束条件，并
Q={4，5}
使用问题一中建立的目标函数进行求解。
4.3 问题三的分析
关于加快推进生态文明建设的意见对于问题三，我们使用问题二中安排好的教室的基础上，将必修课程在时间段4、5出现的次数给定一个阈值，将原目标函数改为约束条件，建立新的
，通过原有方法得目标函数MIN=∑x s,c,l,r,t+∑x s,c,l,r,t
D={5}∩Q={4,5}
Q={4，5}∩LB={1}
到新的结果。
4.4 问题四的分析
对于第三问的评价，我们从教室（包括机房）的利用率、开课对象的上课强度、问题3的不满足率这三个方面来对问题三的结果进行评价。
对于教室（包括机房）的利用率，首先我们计算每间教室本学期在该间教室上课的总学时占本学期所
有学时的百分比，百分比越大说明教室的整体利用率越大；其次我们通过计算分析每门课的上课的人数占教室总座位数的百分比，百分比越大，说明教室的局部利用率越大。
对于开课对象的上课强度我们采用每个班级每周的学时占总周学时的百分比，百分比越大，开课对象强度越大。每门课每次上课相隔的时间段的学时占每周总学时的百分比，百分比越小，开课对象的上课强度越小。
在数据的解决中，往往难以达到问题的百分之百的解决，就会出现不满足。问题3是基于问题2的条件下，提出新的条件，常常由于条件的变化而产生不满足。基于存在这样的情况，我们在解决问题2的情况下，计算出符合问题2的教室数目最优解。
对于这样存在一定几率的有待解决的问题，我们需要分析计算教室在课程要求提升后，教室的安排出现不满足，不够用，或者其他意外的情况，以计算出其不满足率。
五、模型的建立与求解
5.1 问题一的模型建立与求解
经过对问题的分析，我们将问题转换为整数规划问题，通过对目标函数的求解来得到问题一的结果。
5.1.1整数规划的定义
一般认为非线性的整数规划可分成线性部分和整数部分，因此常常把整数规划作为线性规划的特殊部分。在线性规划问题中，有些最优解可能是分数或小数，但对于某些具体问题，常要求解答必须是整数。例如，所求解是机器的台数，工作的人数或装货的车数等。为了满足整数的要求，初看起来似乎只要把已得的非整数解舍入化整就可以了。实际上化整后的数不见得是可行解和最优解，所以应该有特殊的方法来求解整数规划。在整数规划中，如果所有变量都限制为整数，则称为纯整数规划；如果仅一部分变量限制为整数，则称为混合整数规划。整数规划的一种特殊情形是0-1规划，它的变数仅限于0或1。
华大影院5.1.2模型的建立
5.1.2.1 目标函数的确立
由题设可知目标即为使得教室总数达到最小，即：
Min Z =∑x i
x i 表示每种教室类别使用个数，i =1,2,3,4,5,6.
而对于x i ，我们可以用x i =∑x s,c,l,r,t D=i||Q=j 来表示，即每占用教室的一个时间段，将教室个数加1。
5.1.2.2 约束条件的确定
我们对排课问题的详细分析中提出的（1）至（8）条约束条件进行详细的讨论，并给出数学表达式。一下各方程中出现的s ，d ，q ，c ，CC ，l ，lr ，lp ，lc ，le ，r ，cp ，rc ，rt ，ttt ，t ，tw 均为常数。
第（1）条约束要求在任意一个时间片，同属于任意一个合班的所有班级，至多只能被安排一门课程。此约束可以通过式（2-1）表达：
∑∑∈∈≤∈∀∈∀cc c L
l t r l c s x CC cc S s 1,,,,,,,（2-1）
第（2）条约束要求在任意一个时间片，任意一名教师至多只能被安排一门课程。此约束可以通过式（2-2）表达：
∑≤∈∀∈∀1,,,,,,t r l c s x T t S s （2-2）
第（3）条约束要求在任意一个时间片，任意一间教室至多只能被安排一门课程。此约束可以通过式（2-3）表达：
1,,,,,,≤∈∀∈∀∑∈cg
L l t r l c s x R r S s （2-3）
第（4）条约束要求对课程安排的总课时必须满足课程的学时要求。此条约束已经通过教学计划中指定周学时以及起止周满足。
第（5）条约束要求任意一门课程都必须安排一个时间片和一件教室。由以上的唯一性约束可以推出：任意一门课程，对所有时间片的变量x s,c,l,r,t 求和结果小鱼等于1；对所有教室的变量x s,c,l,r,t 求和结果也小于等于1。因此，任意一门课程，如果对所有时间片以及所有教室的变量x s,c,l,r,t 求和，其结果等于1，那么该课程被安排了一个时间片和一间教室。此约束可以通过式（2-4）表达：
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议