有关课表排序-食堂就餐问题的数模论文(完成)

1课堂教学时间表的制定摘要本文根据题目的条件和要求，综合考虑了时间、课程、教学区域、教室、院系、班级等因素对课表编排的影响，在合理的假设之下，采用逐级优化、0-1规划的方法，考虑多重约束条件，引入了偏好系数，建立了一个针对排课的数学模型。通过MATLAB编程，对模型加以求解，对所解结果进行相关地合理性分析后，最终得出了可行的合乎方案的课表。为缓解食堂就餐压力，采用控制人流量的方法来解决问题。基于我校实际情况，通过对部分课表时间的调整，错开各楼栋放学时间，以达到分散人流量的效果。对比分析了调整前后，中午放学后人流量对食堂就餐的压力的影响，证明了新课表的合理性和有效性，对学校教务部门来说有一定的参考价值。文中对模型做了一定的理论分析，具有较广泛的适应性。此外，本文将一些实际问题抽象简化为数学问题来解决，从方法上具有一定的启发性。最后，在分析所得结果的基础上，指出了模型的优缺点，并对模型的改进方向作了进一步探讨。关键字：课程编排、0-1规划、偏好系数、就餐压力21、问题重述为使学校的教学组织安排更加合理，请你综合考虑以下情况，并结合我校实际为教务处安排课堂时间提供一份合理可行的方案。每个学院，每个专业，每个年级，每个学生都有各自的公共必修课，学科基础必修课，学科基础选修课，专业必修课，专业选修课，公共选修课等。目前，学生就餐主要集中于三个学生食堂，特别是中午就餐排队等候时间很长。据后勤集团饮食中心反映和实际调查结果显示，12：00—12：30为学生就餐高峰期，短时间大量学生的涌入导致食堂的售餐窗口相对不足以及餐位少，无法满足学生同时进餐。学生主要自习地点在图书馆，不在教学楼内。只有公共选修课和重修课才可以安排在周末，学生根据学分要求和兴趣爱好，课程开设情况自己确定选修。你的方案中至少达到以下目标：1、缓解学生食堂的就餐压力。（主要是中午）2、大量减少上课时间冲突问题，为学生选课提供方便。3、减少星期六、星期日的排课，为学校组织各种大型考试及学生活动提供便利。4、提高现有教室的利用率。5、能有效缓解目前教室管理员普遍反映的因教室排课过于饱满而无法进行的教室设备的维护维修问题。6、保证学生课外自学以及期末复习时间更加宽松。2、模型假设1.假设学校的目标是将课程全部编排；2.假设所编排的课程表是学生自选型，不考虑班级或上课人数；3.假设在课程要求中的各项均为强制要求，即“硬约束”；4.假设在教师属性中，能胜任课程类别、周最大课时数为强制要求，即“约束”；对教室类别要求、上课时间要求用偏好程度衡量，为“软约束”；5.假设课表内容由上课时间、教师、教室、课程组成。6.假设中午去食堂就餐的人数与时间的函数关系符合正态分布，但上课的人与不上课的人的函数关系是不同的。3、符号说明54321AAAAA表示效用矩阵；TK表示教师编号；RU表示教室编号；CI表示课程编号；表示偏好系数，表示教师对教室、教师对上课时间的偏好系数；is表示课程表上时间段的编号；3kst表示ic课程的要求课时数；isc表示kt教师的要求课时数；ukijirtys,,表示课程表上某一时间段的课程-教师-教室组。4、问题的分析4.1课表的编排排课需要考虑时间、课程、教学区域、教室、院系、班级、教师等等因素，经优化的排课，可以在任意一段时间内，教师不冲突，授课不冲突，授课的班级不冲突，教室占用不冲突，且综合衡量全校课表在宏观上是合理的。如何利用有限的师资力量和有限教学资源，排出一个合理的课程安排结果，对稳定教学秩序、提高教学质量有着积极的意义。对于课表的编排，我们仅以一个院为例。假设某院现有课程40门，编号为C01—C40：教师共有25名，编号为T01—T25；教室18间，编号为R01—R18。课表编排规则：每周以5天为单位进行编排；每天最多只能编排8节课，上午4节，下午4节，特殊情况下可以编排11节课(此题暂不考虑)，每门课程以2节课为单位进行编排，同类课程尽可能不安排在同一时间。比如安排尽量少出现像同一天同一位老师上1-2节，7-8节；同一班级同一门课程，至少应隔一天上一次，另外对学生感到比较难学的课程尽量安排在最好的时段。本题的目标是将现有课程按照一定的约束条件安排到时间表中。假设规定总周课时数为160，最少需要4张时间表。根据假设，学校要将其全部编排，则目标是排出4张课程表。假设4张表同时上课，那么要求教师不冲突、教室不冲突、课程全部排完以及所有软、硬约束。由于目标是将所有课程排完，可以先将不同课程按照其时间要求随机分配至时间表中，形成“时间段-课程”组合；再建立该组合对教师的约束，通过“0-1规划”确定最优的“时间段-课程-教师”组合；同理，确定出“时间段-课程-教师-教室”的最优组合，最终得到所求课表。4.2食堂就餐压力4.2.1实际分析由于我校上课的人主要集中在10、11、15栋这三栋教学楼，所以以这三栋为例。我们对这三栋楼做出这样的调整：15栋采用新的调整后的教学时间，10、11栋采用原来的教学时间。每节课的上课时间不变为45分钟，小节课课间间隔由10分钟缩短为5分钟，大节课课间间隔由原来的20分钟缩短为15分钟。4.2.2调整教学时间前我校食堂餐桌按2500个餐位来进行计算，据估计，在11：40放学的人大约有10000人，每个人吃饭的速度按15分钟计算，则12：00到13：00最多满足10000人吃饭。据学校食堂反映，12：00到12：30为就餐高峰期，短时间涌入大量的人群，导致就餐拥挤，学生排队时间长，无法满足学生同时就餐。4.2.3调整教学时间后以10000人同时在三栋教学楼上第三四节课为例。15栋上课人数为4000人，10、11栋一起上课的人数为6000人。15栋的同学比10、11栋的学生先放学15分钟，即实现了将就餐人数分散开来，达到缓解就餐压力的目的。4修改时间表后经计算与分析，人流量得以分散，从而使食堂就餐的压力得到了很好的缓解。5、模型的建立与求解5.1课表的编排5.1.1模型的准备5.1.1.1因素分析根据分析，关联关系有教师—教室、教师—课程、教师—上课时间、课程—教室、课程—上课时间一共五个。图1关联关系示意图（实线表示“硬约束”，虚线表示“软约束”）依次建立1A2A3A4A四个效用矩阵。其中，为强制约束的有,42,AA.1A矩阵：ijaA1（刻画i教师上j教室的偏好效果指标）其中：10aij;2A矩阵：ijaA2（刻画i教师上j课程时的效果指标）其中：1,0aij3A矩阵：ijaA3（刻画i教师上j时间段上课时的偏好效果指标）其中:10aij54A矩阵：ijaA4（刻画i课程在j教室上时的效果指标）其中：1,0aij偏好约束有1A、3A。5.1.1.2时间段is的编号:每一张课表上有星期一到星期五，每天有5个时间段（每两个课时算一个时间段）。根据假设，假设题目需要同时排四张课程表，需要对四张课程表上的时间段都进行编号:星期节次星期一星期五星期一星期五星期五上午1、2节S1S5S6S10S20上午3、4节S21S25S26S30S40下午5、6节S41S45S46S50S60下午7、8节S61S65S66S70S80表1时间段编号5.1.1.3对课程的处理对所有课程的课时数进行调整，新的课时数为ik（i=1,2,…25,即为25位教师），原课程编号为C01（i=01,02,…28），ijy（i表示原课程的编号，,2,1j），待排课程集合为ijy.5.1.2模型的建立与求解建立课表编排模型的具体步骤如下：步骤一：随机分配课程到各个时间段。当课程的上课时间（上下午）要求为强制性约束时，分别选出上下午的课程集合ijyyB11上午,ijyyB21下午..我们随机给上午B中的每一个元素抽取一个上午的时间段，其中满足的条件是，给下午B中的每一个元素抽取一个下午的时间段。6组成时间段—课程ijiys组合。此时，ijiys（某一时间段对应的某一课程）。如此，完成随机分配，使得每个时间段编号都有一个课程赋值。步骤二：根据教师kt对is时间段上的课程所要求的教室的偏好1A矩阵，对is进行次赋值，ijiiass.最终得到kikikisssss1111步骤三：0-1规划(1)目标是将kt教师分配到不同的时间段上，约束条件是分配结果必须满足教师的课时数要求。因此，问题转化为求有约束条件的0-1规划问题。目标函数：kinknikixsZ11max约束条件：1,02/2/11kinkcikinikkixsxSTx所得解为：kikkiixxxxxxxxxX212222111211将教师安排到最优的时间段，此时kijiTYs,若无最优解，重回步骤一。（2）为每一个时间段安排教室果指标该时段课程对教室的效偏好该时段的老师对教室的这一时间段的效果指标教室对iuSR7（3）结合效用矩阵A4的Si根据is时段课程ic对教室uR的效果矩阵4A，对is进行第一次赋值，若1ija,则1is，否则，0is。（4）结合效用矩阵A1的Si根据is时段教师kT对教室uR的效用矩阵1A，对is进行第二次赋值，ijiiass最终得到：uiuisssss1111步骤四再次使用0-1规划目标是将uR教师分配到不同的时间段上，约束条件是分配结果必须满足同一间教室在四张课表的同一时间段不重复。因此，问题转化为求有约束条件的0-1规划问题。目标函数：uinuniuixsZ11max约束条件：1,0111565146413631262116111611uixxxxxxxxxxxxx所得解为：uiu2u12222111211xxxxxxxxxXii将教室安排到最优的时间段，此时uR,，kijiTYs若无最优解，重回步骤一。8步骤五安排课程表将每个is的组合按照其编号读入到表1中，得到最后的课程表。具体课表见附录一。充分考虑课程的时间要求（上午或下午），随机分配课程，得到“时间段-课程”组合。利用0-1规划求解，构造效用矩阵时，要考虑的是，教师对这一事件的偏好，每位老师在一周内前往上课的天数尽可能少，同时还要使每位老师在学校逗留的时间尽可能少，同一班级同一门课程，至少应隔一天上一次，另外对学生感到比较难学的课程尽量安排在最好的时段等因素，利用EXCEL构造出效用矩阵。用LINGO软件求解线性规划模型的过程详见附录二。5.2食堂就餐问题为简化模型我们约定：以10：50作为t=0（分）时刻，在学校就餐的学生有22000人。5.2.1对新课表的分析第二大节没有课的学生有12000人，有课的学生有10000人。（1）第二大节课没课的学生到食堂吃饭的概率与时间的函数关系记为f1(t)，M1=12000，则：从10：50到11：40第一批第二大节有课的学生到食堂吃饭中间有50分钟，我们将其分为两个时间段0t2020t50f1(t)=21212)10(e21t(0t20)f1(t)=22222)35(e21t(20t50)为简化模型，根据实际情况，我们令：4.0)(f2001dtt查表得：1=18.950201)(fdtt=0.6查表得：2=17.6将21、分别带入f1(t)中，用Matlab画图得下图2：9051015202530354045500.0150.0160.0170.0180.0190.020.0210.0220.023图2（2）第二大节课约有10000人放学，其中4000人在15栋，即提前15分钟放学的人数为4000人，即M2=4000。设这些人到食堂吃饭的概率与时间的关系为f2(t),则：f2(t)=23232)65(e21t(50