数学建模课表安排

宝鸡文理学院新校区课表安排问题编号：J4004摘要：每学期的开学初，总有许多老师对新校区的课程安排很有意见，本文选取宝鸡文理学院某系某专业的师生情况、课程、教室间数为研究对象，以课程与上课时间之间的关系矩阵为目标矩阵，通过用各影响矩阵优化目标矩阵的方法，对新校区各系各专业的课表进行了重排。在具体模型建立过程中采用了0-1矩阵法，矩阵的乘法等数学方法，建立优化类数学模型来求解有效矩阵，根据有效矩阵初排课表，结合多方面因素建立修正矩阵，对初排课表逐层修改，得出最优排课表，最后通过lingo软件加以实现。运用我们建立的数学模型，对宝鸡文理学院数学系08级信息与计算科学专业的课表进行重排，将所得新课表与现有的课表进行比较，显然新排的课表更加合理化、人性化。根据新课表中每节课对应的相关因素（课程名称、教室、老师、班级）进行分析整合，可衍生出新的安排表（如通过对不同时间段上课老师人数的研究安排校车的接送）。我们以学校、教师和学生对所排课表满意度作为衡量标准，以宝鸡文理学院数学系08级信息与计算科学专业的课表为例，可得学校、教师和学生对我们所排课表的满意度主因素分别为校车接送次数、在新区逗留时间、专业课排在早上，计算得评价指标分别为0.88、1、1，可见对本模型使三方的满意度基本均衡且都超过80%，即做到了三者兼顾的满意最大化。最后，通过我们建立的模型，我们给教务处排课表问题给处了一些合理的、可行性的建议。关键字：排课问题0-1矩阵矩阵的乘法优化目标矩阵满意度一．问题重述每学期的开学初，总有许多老师对对新校区的课程安排进行抱怨，还有许多老师要求调课，教务处对这一问题很是头疼。根据宝鸡文理学院院的实际情况，用数学建模的方法解决这一问题，既要让老师满意，又要让同学和学校满意。让老师满意，就是要让每位老师在一周内前往新校区上课的乘车次数尽可能少，同时还要使每位老师在新校区逗留的时间尽可能少，比如安排尽量少出现像同一天同一位老师上1-2节，7-8节；让同学们满意，可从以下几方面考虑，比如，同一班级同一门课程，至少应隔一天上一次，另外对学生感到比较难学的课程尽量安排在最好的时段；同时为避免下课楼道拥挤，对于上午有四节课的班级，在教室功能允许的情况下，应尽量避免更换教室；让学校满意，就是要节约支出，每周派往新校区的车次尽可能的少。从学院的实际情况出发，收集相关数据，用数学建模的方法解决以下问题：1)建立排课表的数学模型，并研制出排课表的软件包；2)利用建立模型及软件对本学期新校区的课表进行重排，并与现有的课表进行比较；3)给出评价指标评价你的模型，特别要指出模型的优点与不足之处；4)对学校教务处排课表问题给出你的建议二．问题分析问题一：通过对多张课表的研究，发现排课表过程中的主要影响因素间关系如下图课程时间教室老师BDACE分别以单箭头左边的为行右边的为列建立两关系间的有效矩阵A、B、D，由AB得矩阵C，再由CD得矩阵E,确定其中的时间课程矩阵B为目标矩阵,以A、C、D影响矩阵为约束对目标矩阵进行修改即可得所求的最优目标矩阵B，以最优目标矩阵B初排课表，再根据修正矩阵E对初排课表进行修正即可得最优排课表。问题二:运用我们建立的模型，以宝鸡文理学院数学系08级信息与计算科学专业为例，对该专业的课表进行了重排，并和现有的该专业的课表进行了对比分析；问题三：首先，找出与和学校、教师、学生的满意度有关的因素，已知对学生而言，希望尽量把重点难学的课程安排在黄金时间上午且连着上课时不要换教室；对老师而言，要求尽量安排一天内能连续上课，避免出现早上1-2节，下午7-8节课的情况，使得老师在学校的逗留时间尽可能的少；对学校而言，希望尽可能减少每周派往新区的车次，为学校节省开支。其次，对这些因素进行综合分析，找出主影响因素。最后以在主影响因素下各方的满意概率为评价指标，对本模型的优缺点进行评价，在继承优点的同时改进缺点。问题四：通过我们建立的排课模型，综合优缺点分析，对学校教务处排课表问题中出现的问题给出合理的、可行性的建议。三．模型假设1，假设专业课一周上3次，公共课一周上2次，选修课一周上1次；2，假设一位老师只能带一门课程；3，假设教室只有大小两种类型；4，假设晚上不排课；5，假设小教室一次最多上1个班，大教室一次最多上2个班；四．符号说明h：表示班级数；l：表示教室数；x：表示单用教室；y：表示公用教室；m：表示课堂数；a：表示专业课门数；b：表示公共课门数；c：表示选修课门数；n：表示有代课老师数；p：专业课老师数；q：公共课老师数；r：选修课老师数；iG：表示课堂序号，1,,im；uvJ：表示上课时间序号，1,,;1,,20uhv；kT：表示老师序号；iW：教室序号；A:表示老师和课堂之间的关系矩阵；B：表示课堂和上课时间之间的关系矩阵；C：表示老师和上课时间之间的关系矩阵；D：表示上课时间和教室之间的关系矩阵；E：表示老师和教室之间的关系矩阵；1p：学校满意度2p：老师满意度3p：学生满意度五．模型建立求解问题一：假设某系某专业有h个班，n位代课老师，每个班每周m堂课（一堂课为两小节），l间教室。1.建立老师与课程之间的有效矩阵A1.1将一周内的所有课按专业课（a门），公共课（b门），选修课（c门）依次排序，记为iG（1,1,2,21,3,31,3,31,32,iaaaaaaababab321,,32ababc）其中32mabc，则1,,im.依此顺序对h个班的课进行排序可得此专业课堂序号为iG，1,,,1,,2,,immmhm，1.2将n位代课老师按专业课（p位），公共课（q位）选修课（r位）依次排序，记为kT（1,,,1,,,,1,,kpppqpqpqr），其中pqrn，则1kn，1.3以老师序号kT为行，以课堂序号iG为列，做老师与课堂之间的关系矩阵,1,,;1,,nhmkiAaknihm.其中1k0kiika老师上i课老师不上课则所得的矩阵nhmkiAa为老师与课堂之间的有效矩阵。2.建立课程与时间之间的有效矩阵B2.1给一周内的所有上课时间赋值(表一)星期一星期二星期三星期四星期五1、2节123453、4节1098765、6节11121314157、8节2019181716通过上表可得课时向量(1,2,,20)v，依此可得h个班的课时向量排序为(1,,20,21,,40,,20(1)1,,20)uvJhh.(1,,;1,,20)uhv2.2以课堂序号iG为行，以课时序号uvJ为列，做课堂与上课时间之间的关系矩阵20,1,,;1,,20hmhijBbihmjh.其中10iijjbj时间上i课时间不上课2.3以满足学生要求尽量把课程安排在每天你的最优时段列目标函数：minijbJ再以下列要求作约束条件；（1）一个班在一个时间对应一堂课，则有：2011hijjb星课时（2）本专业仅有l个教室，则有：2011hmhijijbhl（3）每班所有的20堂课必须在20个课时内上完，则有：20220201111(1)11,,,mhmhhmhijijijijimjihmjbmbmbm（4）专业课放在最优时间，则有：(1)1030201011121(1)120(1)1,,,hmaamahijijijiJimJihmJhbJJbJJbJJ依此建立一个优化类的数学模型，在lingo软件[1]中编程，运行后可得课堂与上课时间之间的效矩阵20hmhijBb（具体的程序见附录一）.3,老师与时间之间的有效矩阵从1中老师与课程间的有效矩阵nhmA中任选一个，从2中课程与上课时间之间的有效矩阵20hmhB任选一个，两矩阵做乘积可得；2020nhnhmhmhCAB,显然20nhC表示老师与课程和时间之间的关系矩阵。若所得矩阵201,,;1,,20nhkjCcknjh，其中12hmk0kkjjcj，老师在时间上课满意指数老师在时间不上课，满足：1)老师逗留是假尽可能的少即：201{21,23,25,27,29,31,,39,,20(1)1,20(1)3,,20(1)9}hkjjcjhhh;2)所有非0的ijc为相同的常数。则以此矩阵为修正矩阵对B矩阵中相关元素作修改，根据B矩阵排出课表，此时课表中每一项中包括科目、代课老师。4.建立上课时间与教室的有效矩阵D已知l间教室中有单用教室（x间），公用教室（y间）对教室按由小到大依次排序，即为iW（1,1,ixxxy）其中lxy，则1,,il.以课时序号uvJ为行，以教室iW为列，做上课时间与教室之间的关系矩阵201,,20;1,,hlijDdihjl，其中10ijidi时间在j教室上课时间不在j教室上课，（1）小教室上专业课，则：103020101121120(1)113,3,,3xxhxijijijijijhjdadada（2）大教室上非专业课，一次两个班，则：2011(3)2hlijijxhmad5.从3中所得老师与时间的有效矩阵20nhkjCc中任取一个，从4中所得的关系矩阵20hlijDd中任取一个，两个矩阵做乘积可得：2020nlnhhlECD，显然nlE表示老师和教室之间的关系矩阵。若所得矩阵1,,;1,,nlijEeinjl，其中1220ij0ijijhe，，老师在教室上课满意指数老师不在教室上课，满足：1）113pxijijea；2)所有非0的ije均为一个相等的常数。则结合此矩阵在依据B矩阵排出的课表中加入相应的教室，即此时课表中每一项包括科目、代课老师、上课教室。6.根据y间公用教室中包括不同班级间的公用，不同专业间的公用，不同年级间的公用，不同系间的公用对所排课表作微调，得出最优排课表。问题二：以宝鸡文理学院数学系08级信息与计算科学专业为例，则可知：h=2，（信1，信2）n=8（p=（焦建民、冯录祥），q=4（李建卓、田慧芳、杨蕾、周晨立、），r=2（王红生、龚明）），m=16（a=2（数学分析、高等代数），b=4（数据结构、大学英语、毛邓三、大学物理），c=2（大学语文、大学体育）），l=（x=2，y=3）带入模型可得课表如下：表1：数学系08级信息与计算科学专业1班一二三四五1、2数学分析焦建民思贤楼323高等代数冯录祥思贤楼323数据结构李建卓思贤楼328数学分析焦建民思贤楼3233、4高等代数冯录祥思贤楼323数据结构李建卓思贤楼328数学分析焦建民思贤楼323高等代数冯录祥思贤楼3235、6大学英语田慧芳思贤楼325毛邓三杨蕾思贤楼328大学体育龚明大学物理周晨立思贤楼325大学语文王红生思贤楼3267、8大学物理周晨立思贤楼325大学英语田慧芳思贤楼325毛邓三杨蕾思贤楼328表2：数学系08级信息与计算科学专业2班一二三四五1、2高等代数冯录祥思贤楼324数据结构李建卓思贤楼328数学分析焦建民思贤楼324高等代数冯录祥思贤楼324星期课时期3、4数学分析焦建民思贤楼324高等代数冯录祥思贤楼324数据结构李建卓思贤楼328数学分析焦建民思贤楼3245、6大学英语田慧芳思贤楼325毛邓三杨蕾思贤楼328大学体育龚明大学物理周晨立思贤楼325大学语文王红生思贤楼3267、8大学物理周晨立思贤楼325大学英语田慧芳思贤楼325毛邓三杨蕾思贤楼328原课表【2】参照附录2，可将新旧课表各相关元素分别作对比研究，通过多方位考虑得出新旧课表的