课程表安排地优化模型

1、一类课表安排的优化模型XXX（XXX大学理学院应数班贵阳 550025 ）摘 要：本文采用逐级优化、0-1规划的方法，考虑多重约束条件，引入了偏 好系数，建立了一个良好的排课模型，并根据题目给的数据，通过MATLA B编程，进行模型验证，求出了所需课表。且在方案合理性分析中用计算机模拟的方 法分析了偏好系数的变化、教室的种类对排课结果的影响。 最后给出了教师、教 室的最优配置方案。关键词：逐级优化；0-1规划；多重约束条件；排课模型1问题提出用数学建模的方法安排我们峨眉校区合理的课表，做到让老师的教学效率达到 最好和学生最有效率地学习，同时做到老师和学生的双向满意。为了提高老师满意 度，就是要

2、让每位家住贵阳和花溪的老师在一周内前往上课的天数尽可能少（家住 民院的老师前往学院的次数尽可能少），同时还要使每位老师在学校逗留的时间尽可 能少（家住贵阳和花溪的老师每天最多往返学校一次），比如安排尽量少出现像同一 天同一位老师上1-2节，7-8节；让同学们满意，可从以下几方面考虑，比如，同 一班级同一门课程，至少应隔一天上一次，另外对学生感到比较难学的课程尽量安 排在最好的时段。用数学建模的方法解决以下问题：1）建立排课表的一般数学模型；2）利用你的模型对本学期我院课表进行重排，并与现有的课表进行比较；3）给出评价指标评价你的模型，特别要指出你的模型的优点与不足之处；4）对学院教务处排课表问

3、题给出你的建议。2问题分析在学校的教务管理工作中，课程表的编排是一项十分复杂、 棘手的工作。排课需要考虑时间、课程、教学区域、教室、院系、班级、教师等等因素。经优化 的排课，可以在任意一段时间内，教师不冲突，授课不冲突，授课的班级不冲突， 教室占用不冲突，且综合衡量全校课表在宏观上是合理的。 如何利用有限的师资 力量和有限教学资源，排出一个合理的课程安排结果，对稳定教学秩序、提高教 学质量有着积极的意义。某高校现有课程50门，编号为C01 C50 ；教师共有48名，编号为toi t48 ；教室28间，编号为roi 26。具体属性及要求见附录1 ； 课表编排规则：每周以5天为单位进行编排；每天最

4、多只能编排 10节课，上午 4节，下午4节，特殊情况下可以编排10节课，每门课程以2节课为单位进行 编排，同类课程尽可能不安排在同一时间。 比如安排尽量少出现像同一天同一位 老师上1-2节，7-8节；让同学们满意，可从以下几方面考虑，比如，同一班级 同一门课程，至少应隔一天上一次，另外对学生感到比较难学的课程尽量安排在 最好的时段。本题的目标是将所有课程按照一定的约束条件安排到时间表中。由于总周课时数为700,最少需要14张时间表。根据假设，学校要将其全部编排，则目 标是排出14张课程表。假设14张表同时上课，那么要求教师不冲突、教室不 冲突、课程全部排完以及所有软、硬约束。由于目标是将所有课

5、程排完，可以先将不同课程按照其时间要求随机分配至时间表中，形成“时间段-课程”组合;再建立该组合对教师的约束，通过“0-1规划”确定最优的“时间段-课程-教师” 组合；同理，确定出“时间段-课程-教师-教室”的最优组合，最终得到所求课 表。3.模型的建立3.1模型假设1假设学校的目标是将课程全部编排；2假设所编排的课程表是学生自选型，不考虑班级或上课人数；3. 假设在课程要求中的各项均为强制要求，即“硬约束”；4. 假设在教师属性中，能胜任课程类别、周最大课时数为强制要求，即“约束”；对教室类别要求、上课时间要求用偏好程度衡量，为“软约束”；5假设所得14张课表中2张同时上课，上完后另外2张课

6、表开始上课；6.假设课表内容由上课时间、教师、教室、课程组成。3. 2符号说明AA2A3A4A5 :效用矩阵；tk :教师编号；U ：教室编号；Ci :课程编号；:偏好系数，表示教师对教室、教师对上课时间的偏好系数 ；Si :课程表上时间段的编号；Stk ：为Ci课程的要求课时数；SCi :为tk教师的要求课时数；S yj,tk，u :课程表上某一时间段的课程-教师-教室组合；3. 3模型的准备与初步建立：3 . 3.1模型的准备1根据分析，关联关系有教师一教室、教师一课程、教师一上课时间、课程一教 室、课程一上课时间一共五个。拘谍时时间教室图1关联关系示意图（实线表示"硬约束”，虚

7、线表示"软约束”）依次建立Al, A2, A七个效用矩阵。其中，为强制约束的有 业、.A矩阵：A aj （刻画i教师上j教室的偏好效果指标）其中：0 aij 1;A矩阵：A2 aj （刻画i教师上j课程时的效果指标）其中：aij 0,1A矩阵：A3 aj （刻画i教师上j时间段上课时的偏好效果指标）其中：0 aij 1A矩阵：A4 aj （刻画i课程在j教室上时的效果指标）其中：aij 0,1偏好约束有A、A3。2.时间段Si的编号：每一张课表上有星期一到星期五，每天有5个时间段（每两个课时算一个时间段）0根据假设，假设题目需要同时排十四张课程表，需要对十四张课程表上的时间段都进行编

8、号：星期一星期五星期一星期五星期五上午1、2节S5S6S10习0上午3、4节S71S75S76s80S140下午5、6节S141S145S146S150S210下午7、8节S211S215S216S220S280晚上9、10S281S285S286S290S350表1时间段编号3.对课程的处理当某一课程的课时数为奇数时，取大于他的最小偶数。对所有课程的课时数进行 调整。新的课时数为ki （ i 1,2,48,即为48位教师），原课程编号为q（i 1,2, 50），yj（ i表示原课程的编号，j 1,2,），待排课程集合为yj3 . 3.2模型的初步建立第一步：随机分配课程到各个时间段当课程的上

9、课时间（上下午）要求为强制性约束时，分别选出上下午的课程集合 B上午y； yj , B下午y： yj .我们随机给B上午中的每一个元素抽取一个上午的时间段，其中满足的条件是，给B下午中的每一个元素抽取一个下午的时间段。 组成时间段一课程syj组合。此时，Siyj （某一时间段对应的某一课程）。如此，完成随机分配，使得每个时间段编号都有一个课程赋值。第二步：根据教师tk对Si时间段上的课程所要求的教室的偏好 Al矩阵，对Si 进行次赋值，Si Si aij .S11S1i最终得到SkiSk1Ski第三步：0-1规划1 .目标是将tk教师分配到不同的时间段上，约束条件是分配结果必须满足 教师的课时

10、数要求。因此，问题转化为求有约束条件的0-1规划问题。目标函数：n nmax ZSki xkik 1 i 1约束条件：nxki STk / 2i 1nxki Sci / 2k 1Xki 0,1所得解为：X11 X12X1iX21 X22X2iXXki Xk2XkiSiYji,Tk若无最优解，重回步骤将教师安排到最优的时间段，此时。2 为每一个时间段安排教室该时段的老师对教室的偏好 该时段课程对教室的效果指标Ru教室对Si这一时间段的效果指标3 .结合效用矩阵A4的Si根据Si时段课程Ci对教室Ru的效果矩阵A4，对Si进行第一次赋值，若aij 1，则 si 1，否则，si0 o4.结合效用矩阵

11、Ai的S根据Si时段教师Tk对教室Ru的效用矩阵Ai，对s进行第二次赋值，S Si aij最终得到：S11S1iSSu1Sui第四步再次使用0-1规划目标是将Ru教师分配到不同的时间段上，约束条件是分配结果必须满足同一间教室在四张课表的同一时间段不重复。因此，问题转化为求有约束条件的0-1 规划问题。目标函数：n nmax Zsui Xuiu 1 i 1约束条件：X11X16X11X161X21X26X31X361X41X46X51X561Xui0,1所得解为:X11X12X1iXX21X22X2iXu1Xu2Xui将教室安排到最优的时间段，此时 Si Y；,Tk, Ru若无最优解，重回步骤安

12、排课程表将每个Si的组合按照其编号读入到表1中，得到最后的课程表。具体课表见附录二。4.模型的求解充分考虑课程的时间要求（上午，下午或晚上），随机分配课程，得到“时间段-课程”组合。分配示例见附录一。由于，题目所给数据中，教师的总课时数小于课程总课时数，又经过计算，设定目标是为做成十四张课表，其中两张先 行开课，上完后，另外再两两开课。利用0-1规划求解，构造要用矩阵时，要考 虑的是，教师对这一事件的偏好，每位家住贵阳和花溪的老师在一周内前往上课 的天数尽可能少，同时还要使每位老师在学校逗留的时间尽可能少，同一班级同一门课程，至少应隔一天上一次，另外对学生感到比较难学的课程尽量安排在最 好的时

13、段等因素，利用excel构造出效用矩阵。用LINGO软件求解线性规划模型 的过程详见见附录三。5模型的评价与分析5 . 1合理性分析：模型充分考虑了课程、教室、教师等的相互约束，建立了关系关联，并对约 束采用0-1规划，确定出“时间段-课程-教师-教室”组合。同时，我们也充分 考虑了教师对教室和上课时间的偏好，建立了一个偏好系数可调的模型，使所得 课表尽量满足课程、教室、教师的各种属性及要求，对教师聘用，教室配置给出 合理化建议。5 . 2模型的评价：第一.模型的优点：1引入了偏好系数B,能较大程度地满足教师、课程和教室的要求；2建立了关联关系，使模型建立更清晰、明确、具有条理性；3用0-1规

14、划解决相互约束问题，形成“时间段-课程-教师-教室”组合， 科学合理；4逐步优化，层层递进，思路清晰，简单易懂。5充分考虑各个教师、教室、课程的要求，具有良好实用性。以上总结的内容不可能是生产分配研究方法与策略的全部，但愿它能起到敲门砖的作用，带领更多的有志踏入研究之门第二模型的缺点：1当课时数为奇数时，将其近似为偶数计算，导致课表中所有时间未能充 分利用；2在随机给每个时间段安排课程时，未能确立完善的分配方式；参考文献：1姜启源、谢金星、叶俊，数学模型（第三版）M，北京：高等教育出版社，2003。2郭耀煌等，运筹学M，四川：西南交通大学出版社，2000。3薛秀谦、朱开永，运筹学 M，徐州：中

15、国矿业大学出版社，2002。4韩中庚，数学建模方法与应用 M，北京：高等教育出版社，2005。徐玖平、胡知能，中级运筹学M，北京：科学出版社， 2008。张小红、张建勋，数学软件与数学实验M，北京：清华大学出版社，2004。7邓集贤、杨维权、司徒荣、邓永录，概率论与数理统计（第四版）M，北京：高等教育出版社,2009。7刘卫国.MATLAB程序设计教程M.北京：中国水利水电出版社,2005.9欧阳光中、朱光炎、金福临、陈传璋，数学分析上册（第三版）M，北京：高等教育出版社，2007 。10王夏林，概率论与数理统计M，西安：西北工业大学出版社,2002。附录附录一：课程、教师、教室（C01 C5

16、0，t0i t48，01 26 ）分别为:C01 C50t01 t48r01 r261，保险学原理蔡静6-6062，常微分方程车克平6-6053，大学化学陈浩6-6044，大学物理陈远强6-6035，大学英语三储昌木6-6026，大学英语一代莉莉6-6017,大学语文范梦慧6-5058，电磁学高伟6-5049，电力电子学韩军6-50310,电子电路计算机辅助设计胡菊芳6-40511，泛函数分析黄成泉6-40412，复变函数黄国桢6-40313，复利数学姜晴琼6-40214，概率论蒋桂珍5-2楼15，概率论与数理统计金良琼15-31216，高等数学一李寒贫15-21517，咼级语言程序设计李荣1

17、5-21018，机械基础李伟民15-20219，机械制图及CAD初步李文力15-20120,计算机应用基础李燕八、13-60921，解析几何林玲13-60722，近世代数刘红梅13-60423，就业指导刘泓（李磊）13-60324，科技文献刘小华13-40725，离散数学骆最芬13-40126，理论力学聂思敏12-10227,量子力学潘仁龙28，毛邓齐新潮29，面向对象程序设计饶彦30,模拟电路任丽蓉31，模式识别与图像处理商德强32，热力学与统计物理施涛33，热学实验孙向荣34，实变函数索洪敏35，寿险精算原理田应福36，数分三王守财37，数据库系统应用王新锋38，数理统计王燕红1_ 八、3

18、9，数学模型吴兴玲40,数学物理方程熊宗洪41，数值分析杨昌仁42，算法与数据结构杨亚碧43，体育三叶一蔚44，体育一余芳琼45，图论张儒良46，微分几何张微微47,线性代数张伟48，原子物理学赵行知49 .证卷投资分析50,中国近代史纲要51 ,附录二：具体课表为：星期一：星期二；星期三;1-23-45-67-89-101-23-45-67-89-101-23-45-67-89-100C54C46C11C467T5T31T34T31应R13R13R8R13数0C39C31C34C317T5T45T43T45信R6R7R1R7计08应物C48T8R8C18T18R6C18T18R6C40T17

19、R6C9T30R13C32T42R13C27T8R708应数C9T25R6C39T5R6C22T24R12C12T31R12C14T15R12C9T25R608统计C4T25R8C41T4R11C35T13R11C13T1R11C35T13R11C4T25R8C49T8R7C49T8R708信计C29T11R8C2T31R8C38T22R13C22T24R10C2T31R8C29T11R8C29T11R9C41T4R1009应物C8T37R11C8T37R11C23T16R11C23T16R11C8T37R14C8T37R14C26T25R6C5T23R18C28T29R6C15T22R12C

20、30T22R6C28T9R609应数C37T23R9C37T23R9C36T41R3C23T16R4C2T31R3C5T23R18C4T12R3C28T9R6C37T23R9C36T41R3C28T9R609统计C36T41R10C17T11R10C28T28R6C36T41R10C14T15R5C23T6R10C23T6R10C28T28C17T11R10C5T3R4C3T47R837T11R10R60C5C36C17C28C17C25C4C2C36C5C23C239T46T41T28T28T28T36T128T41T46T14T14信R19R5R7R6R7R4R8T2R5R19R5R5计8

21、R61C47C50C7C7C16C6C20C44C19C19C3C30T17T44T10T10T30T2T2T18T18T19T19应R5R28R5R5R5R16R7R8R8R1R1物1C6C50C51C53C21C51C60T20T44T39T35T40T39T20应R25R26R2R2R2R2R25数1C53C6C50C51C20C44C6C51CC3C30T38T20T44T5T27T20T5T19T19统R4R25R26R4R8R25R4R1R1计1C20C53C6C50C51C44C51C20C60T45T38T20TYT5T5T45T20信R7R8R25R25R3RR9R25计星期四：星期五;1-23-45-67-89-101-23-45-67-807应C54C11数T5T34R13R807信C39C34C31计T5T43T45R6R1R708应C10C10C32C27物T33T33T42T8R8R8R13R708应C39C14C22C12数T5T15T24T31R6R12R12R1208统C13C35C41计T1T13T4R11R11R1108信C38C41C22计T22T4T24R13R10R1009应C15C4