高校排课方案简单方法

本文档针对高校排课难的问题,采用数学建模的方法,结合matlab、lingo软件解决了该问题,方案简单易于操作。

承 诺 书

我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.

我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 中南民族大学 参赛队员 (打印并签名) ：1. 指导教师或指导教师组负责人 (打印并签名)：

日期： 年 月 日

赛区评阅编号（由赛区组委会评阅前进行编号）：

本文档针对高校排课难的问题,采用数学建模的方法,结合matlab、lingo软件解决了该问题,方案简单易于操作。

编 号 专 用 页

赛区评阅编号（由赛区组委会评阅前进行编号）：

全国统一编号（由赛区组委会送交全国前编号）：

全国评阅编号（由全国组委会评阅前进行编号）：

本文档针对高校排课难的问题,采用数学建模的方法,结合matlab、lingo软件解决了该问题,方案简单易于操作。

课堂教学时间表的制定

摘 要

本文是针对学校食堂拥挤，排课不完善等实际情况，来研究并确定一个比较好的排课方案,用以解决包括食堂拥挤一系列的问题。给出了在符合实际情况的假设下，重点研究了3个比较关键的因素:食堂拥挤度,教室利用率,单个教室利用率，并对这3个因素建立了多目标的0-1规划模型。

整个建模过程分为三步。第一步是产生随机课表，在此我们分步采用蒙特卡洛模拟技术(随机模拟)，随机产生再派生了多张课表，并且分课程优先级和课时段优先级把课表安排完成；第二步是根据第一步中所排出的课表建立多目标0-1规划模型，由于多目标问题比较难以解决，于是我们就采用移动加权平均值的方法构建了综合评价函数，将多目标问题转化为单目标的线性规划问题，各因子间的权重采用层次分析法得到，通过了一致性检验，权重向量为：

w1

w2

w3 (0.6870

0.1865

0.1265)；第三步是根据第二步的模型求解目标

函数数和各因子的值，本题中的值为：

f 0.06055, 1=12.2%, 2=25.0%, 3=18.46%

再结合实际情况进行分析知：据统

计一般食堂拥挤度在20%以上时，学生会觉得拥挤，本题中我们的解

=12.2%<20%,故，本方案可以解决食堂拥挤度过高的问题；教室利用率只有

1

25%，与实际比有些偏低；另外单个教室的利用率较低，有利于教室设备的维修。

本模型极大结合了我校的实际情况，所做的模型是以我校的情况为例的，由于情况较多，我们给出方法并给出了一种结果，能很好的适应类似的情况，具有很强的现实意义。

关键词：蒙特卡洛模拟 多目标0-1规划 移动加权平均值 层次分析法

本文档针对高校排课难的问题,采用数学建模的方法,结合matlab、lingo软件解决了该问题,方案简单易于操作。

一 问题重述

大学校园是一个人口相对比较集中的地方,学生就餐，上课，基本上都集中在食堂，教学楼，在坐落于南湖之畔的我们的校园里，当你遇见一个似曾相识的面孔，也许你们曾经在同一个食堂的同一张桌子上吃饭，也许你们曾一同赶往同一栋教学楼的同一层教室上课，也许……那时候的你，会不会觉得很挤，很忙呢？这时，学校课程的合理化安排，便显得尤为重要。通过对学校现有设施和学生课程情况的综合分析，结合实际，以使学生方便，令校方满意，让资源得到充分利用为原则，设计一份合理可行的排课方案。 现有资源：

1.三个学生食堂:中午12：00—12：30为学生就餐高峰期。 2.教学楼

3.图书馆:主要用于学生自习。（不在教学楼内） 学生课程情况：

1.每个学生都有各自的公共必修课，学科基础必修课，学科基础选修课，专业必修课，专业选修课，公共选修课等。

2.只有公共选修课和重修课才可以安排在周末。 我们建立的数学模型，需达到以下几个目标： 1.缓解学生食堂的就餐压力。（主要是中午）

2.大量减少上课时间冲突问题，为学生选课提供方便。 3.减少星期六、星期日的排课。 4.提高现有教室的利用率。

5.能有效缓解目前教室管理员普遍反映的因教室排课过于饱满而无法进行的教室设备的维护维修问题。

6.保证学生课外自学以及期末复习时间更加宽松。

二 问题假设

1.将每两小节课划分为一堂课，假设每天上课时间段的优先级为：上午的课（2堂） 下午的课（2堂） 晚上的课（1堂）。

2.课程性质优先级：必修 选修；专业 基础 公共课；基础选修课 公选必修。 3.由于英语课的特殊性（小班上课，专用教室），我们将它独立出来，与其它六门课并列，又由于四六级考试，在此定为英语最重要，即优先级最高。 4.由于题目中未给出老师的任何信息，我们默认为老师的资源足够。 5.假设教室有三种属性：大教室20个（一次可上4个班），中等教室130个（一次最多可上2个班），小教室50个（一次最多上一个班）。

6.假设每个年级有120个班，每班50人，可大概将其分为六大类，每类20个班级，其课程性质及数目基本一致，故可共用一张课表。 7.由于大四学生在校上课人数实际上很少，所以我们的排课上基本忽略大四学生对我们目标的影响。 几个原则：

本文档针对高校排课难的问题,采用数学建模的方法,结合matlab、lingo软件解决了该问题,方案简单易于操作。

1.默认教师属性与课程属性对应，如英语课用小教室，选修课和公共必修课用大教室，其它必修课用中等教室。

2.同一时间上课所占用的教室数不可多于可用的教室数。

3.根据学校的实际情况：大一只开设了：S0 S1 S2 S4（已排好优先级）；

大二开设立：S0 S3 S1 S4 S5 S6； 大三只开设了：S3 S5。

4.同一天内不可排2堂及以上相同的课程，这里的相同指同性质的同一门课程。

5.从食堂的拥挤度和时间段的优先级考虑，公共课最好放在3~5堂上。 6．课程连上时，尽量不要换教室，即使换也不要隔太远

三 符号说明

14

1.设第i个年级每周的平均课时数Si 15

12

i 1i 2 i 3

2.在一周内设第i个年级第j天第k个课堂上课的情况为Aijk，则

1Aijk

0

20

3.设第m类教室有Bm个，则Bm 130

50

0 n 6,n N

*

上课不上课

1 i 3;1 j 5;1 k 25 k为按先行后列的顺序对一周内25堂课进行的编号

m 1m 2 m 3

4.设Sn为课程的编号，Sna为Sn的第a门课程

S0:英语；S1:基础必修课（简称基必）；S2:基础选修课（简称基选）；S3:专业必修课（简称专必）；S4:公共必修课（简称公必）；S5:专业选修课（简称专选）；S6:公共选修课（简称公选）

5.Nin为第i个年级的Sn

6.设 1表示中午食堂的拥挤度， 2表示教室的利用率，

3表示单个教室的利用率；wl分别为其权重(l=1,2,3)

四 问题分析

高校排课问题要考虑很多因素，现在大部分的高校依然采用机械加手动的方式去解决问题，这样就无可避免的产生了各类问题，比如题目中所叙述的选课冲突、教室利用率过低，教室设备维修不方便等问题。

本文档针对高校排课难的问题,采用数学建模的方法,结合matlab、lingo软件解决了该问题,方案简单易于操作。

本文在结合我校实际情况后建立了多目标决策模型，采用计算机模拟，层次分析等方法确定了一个比较完善的排课方案具体思路分为三步： 第一步 产生随机课表

根据我校的实际情况，我们对个年级分别排课，大一大二大三每周上课的平均次数分别为14,15,12堂（两小节课为一堂，晚上只安排一堂课），每周学校安排25堂课，据此，可以通过matlab编程随机产生一系列符合该初始条件的上课时间点，得到初级课表；再根据所确立的优先级原则，结合计算机模拟，在时间点上排上相应的课程，得到次级课表；最后按教室类型为课堂安排教室，随机分配，此时得到的课表为还未进行优化的原始课表。

第二步 由产生的课表建立0-1多目标规划模型，构建课表的综合评价函数 在第一步的基础上我们再根据题目要求建立 0-1多目标决策模型，对题目出 的六个因素进行排序，选出其中三个比较重要的因素，并引入各自的权重（层次分析法）建立一个课表的综合评价指标函数f,作为我们的优化模型，最后将排好的课表根据我们的多目标决策模型的f函数和各因素产生的原因微调，比较各自的f值，当f取值比较合理时就认为我们的次级课表已经排好了； 根据实际情况，我们学校的教室比较多，利用率不高，于是在次级课表的基础上我们继续采用计算机模拟，按课堂性质的要求将教室分配好，接着根据我们之前设定的几个原则，对排好的教室进行微调，最后我们就可以得到全校大一大二大三的三张课表

第三步 对综合评价函数进行求解分析，回代到课表再优化之前随机产生的课表

只要每次产生了课表就会有一个对应的最佳f值，每一个f值都会对应一组因素值(如 1, 2, 3),每次在解出一组值时都做分析，当我们的因素值和综合评价值都比较合理时就认为课表已经在题目中的约束条件下排好了。 如下图就是我们整个分析的循环简略图

五 模型建立与求解

5.1 步骤一 产生初级课表（只含上课时间）

首先，我们结合实际情况，对各年级的课程情况进行估算，得到以下数据表：

本文档针对高校排课难的问题,采用数学建模的方法,结合matlab、lingo软件解决了该问题,方案简单易于操作。

其中，除N11=4，N14=3，N23=2，N24=4，N26=3，N33=4，N35=2外，其余Nin=0。 接着，我们利用计算机模拟的方法，随机产生了大一，大二，大三的各一张初级课表(见表5.1.2)：

然后，再分时间段（为了保证同类课表的同时间段内课堂数相等）进行计算机模拟，分别得到各年级的另外5张平行课表，故现有3 6=18张初级课表。 5.2 步骤二 产生次级课表（含有上课时间和相应课程）

在初级课表的基础上，按照课程性质和上课时间段的优先级，在上课时间段上安排合适的课程，由于有18张课表需要排，工作量较大，这里，我们只给出排课方法和一个排课结果，依次类推可排出其它17张次级课表，具体排课方式如下：（以大一第一类班级，即表5.1.2a为例）

图一

过程①表示将S0的2堂课随机排入上午5堂课，故上午剩余3堂课； 过程②表示在S1中随机选3堂课随机排入上午剩余的3堂课中；

过程③表示将S1中剩余的5堂课随机排入下午的6堂课中，故下午剩余1堂课；

本文档针对高校排课难的问题,采用数学建模的方法,结合matlab、lingo软件解决了该问题,方案简单易于操作。

过程④表示将S2的1堂课排入下午剩余的1堂课中；

过程⑤表示将S4的3堂课随机排入晚上的3堂课中。

此次排课过程中，每当出现与原则4相违背的情况时，即对课表进行微调至符合。

由此得到的次级课表为：(见表5.2.1)

5.3 步骤三 产生原始课表（含有上课时间，课程及教室） 首先将所有教室按类型进行编号：

20个大教室分别编号为：C1~C20; 130个中等教室分别编号为：D1~D130; 50个英语小教室分别编号为：E1~E50。

接着，再按照原则1，在18张次级课表的基础上，将同一时间段同种教室上课的课程，随机分配在相应的教室类型中，由于各个类型教室硬件设施没有差别，故教室可以按原则1随机安排，在此就不具体列出了

至此，我们的18张课表已经全部排完。 步骤四 优化课表模型

以上课表只是我们根据实际情况及一些基本原则随机排出的，并未考虑到题目的要求，因此，接下来我们根据题目要求，建立多目标的0-1模型，对课表进行优化：

5.3.1 模型建立： ① 食堂拥挤度η1

一周内上第二堂课的次数一周内上课的总次数

代入我们的符号系统有：

3

6

10

ijk

3

6

10

20 η

1

A

j 1k 66

25

i 13

j 1k 66

25

Aijk

i 13

Aijk

⑴

20

i 1

A

j 1k 1

ijk

i 1

j 1k 1

本文档针对高校排课难的问题,采用数学建模的方法,结合matlab、lingo软件解决了该问题,方案简单易于操作。

② 教室利用率η2=

每周中用到的教室总次数每周能用的教室总次数

3

6

25

ijk

20 A

j 1k 1

η2=

i 1

(20 130 50) 25

⑵

③ 单个教室的利用率η3=

某个教室一周内使用的次数某个教室一周内能用的次数

单个教室的使用率我们在此用使用到的教室的平均利用率乘以一个使用系数η来表示，即：

η

3

2

一周内使用教室的总次数（使用教室的个数） 25

3625

ijk

20 A

j 1k

1

η3=

3

i 1

2

⑶

25 s

设s

r

m 1

3m 1

m

am

m

⑷

a

其中使用教室的个数我们采用加权平均值的模型来解决，而各类教室的使用次数我们再次借助计算机模拟的方法得到：利用计算机模拟技术，模拟100次，我们得到了各类教室一周的使用次数表，见表5.11

表5.11

由此我们建立了如下的模型[1]：

本文档针对高校排课难的问题,采用数学建模的方法,结合matlab、lingo软件解决了该问题,方案简单易于操作。

3610

Aijk

η1 i 1j 1k 6

3625

Aijk

i 1j 1k 1

3625

20 Aijk

i 1j 1k 1

η=2 (20 130 50) 25 3625 20 Aijk i 1j 1k 1

2 η3=

25 s 3 rmam m 1s 3 am

m 1

A=0,1ijk

5.3.2 模型求解：

根据我们所列出的课表，现在对η1，η2，η3进行分析，确定可行域。 根据计算机模拟可知：

①大一一周每天的第二堂课最多可上5次，大三一周每天的第二堂课最多可上3次，于是每天第二堂课最大的总数为5+5+3=13，最小的总次数为1，故可得

114+15+12

141

1341

η

1

1314+15+12

，

⑸

即：

η

1

3

m 1

amrm

3

② 针对η2，我们可以对公式进行转换，η2=用matlab编程可以得到

0.2481 η

2

a

m 1

m

200 25

，根据表5.11的结果，利

0.2508 ⑹

③ 在模型建立的过程中，我们已经分析过使用教室个数的计算方法（见式⑷ ），在此，我们就直接给出结果，每周教室的使用个数为26~33; 于是有：

0.2982η

2

η

3

0.3785η

2

⑺

本文档针对高校排课难的问题,采用数学建模的方法,结合matlab、lingo软件解决了该问题,方案简单易于操作。

根据题目的要求，需要在全局情况下η2尽量的大，η1,η3尽量的小，大小不一，比较难以求得，于是我们引入权重，构建了了综合评价函数f即：

w2η minf wη11

3

wl 1 l 1

2

[2]

作为目标函数，

w3η

3

⑻

下面我们采用层次分析法[2]取wl： 如下图建立层次结构图

层次分析法是一种定性分析和定量计算相结合的方法，首先构造因素间的成对比较阵Q，

1 1Q

5 1 4

4 2 1

5112

一般情况下,Q并不是完全一致的，T.L.Saaty等人认为：对于n 3的成对比较阵Q，将它的一致性指标CI与同阶的随机一致性指标RI(一般查表，见附录3,这里取0.58)之比称为一致性比率CR，若CR 0.1，则认为Q的不一致性程度在容许范围内，可以用其特征向量作为权向量。否则就要调整Q，使之具有满意的一致性

本文档针对高校排课难的问题,采用数学建模的方法,结合matlab、lingo软件解决了该问题,方案简单易于操作。

用matlab编程[3]可得到Q的特征向量(程序代码见附录3)，归一化后为：

wp

(0.68700.1865

0.1265)

0.047

最大特征根为： max 3.094 于是 CI 对其进行一致性检验CR

CIRI

max n

n 1

0.081 0.1，符合一致性目标即表明w

p可以作

为各指标的权重向量，即：

w1

w2

w3 (0.6870

0.18650.1265)

于是，minf 0.6870 1 0.1865 2 0.1265 3，至此，问题转化为一个简单的线性规划问题：

minf 0.6870 1 0.1865 2 0.1265 3 113 η1

41 41

0.2481 η 0.2508

2

0.2982η2 η3 0.3785η2

六 模型的结果及分析

针对以上规划模型，用lingo软件可解得,minf 0.06055,且此时

1=12.2%

2=25.0% =18.46% 3

据统计一般食堂拥挤度在20%以上时，学生会觉得拥挤，本题中我们的解

=12.2%<20%,故，本方案可以解决食堂拥挤度过高的问题；教室利用率只有

1

25%，我们觉得有些偏低；另外单个教室的利用率比较低，利于我们教室的维修。

七 模型的评价与改进

本模型大量使用蒙特卡洛模拟技术，很方便产生课表，然后进行一些计算就

本文档针对高校排课难的问题,采用数学建模的方法,结合matlab、lingo软件解决了该问题,方案简单易于操作。

可以评估所产生课表的适用度，很利于教务工作者执行编排。

但不可避免，本模型考虑的问题不全，可能会使课表的某些属性的参数不太恰当。比如由于教室大小分类不太详尽，以及实际情况下某些课程属性和教室属性的不一致性导致我们得到的教室利用率偏低等问题。

我们在用随机数产生课表的时候，如果最后算出的 过高，我们就可以回代

1

到原来产生的随机课表上对每天的三四节课重新模拟，反复迭代（一般10就足够了）就可以得到一个比较令人满意的结果；如果教室利用率 2偏低或者 3偏高，那我们就可以在模拟时加一些限制条件使得上课的教室尽量分散（但是尽量不要违背原则6）

八 模型的推广

本方案采用随机数的方法很容易产生大量满足条件的课表，再稍加修改就可以在很多教务安排、公交车调度或者产品分配等复杂的运筹学问题上，这将大大减少人脑对这些复杂问题的编排还容易出纰漏的问题

本文档针对高校排课难的问题,采用数学建模的方法,结合matlab、lingo软件解决了该问题,方案简单易于操作。

参考文献

[1] 姜启源等，数学模型（第三版），北京：高等教育出版社，2003 [2] 汪晓银 周保平等 《数学建模与数学实验》第一版 2010年 [3] 肖华勇《实用数学建模与软件应用》 第一版 2008年

附录

附录1(15张课表) 附录2

随机模拟的一致性指标RI值

附录3

计算机模拟的程序代码1: clear;clc; for i=1:5

A=randperm(5); B=A(:,1:3); C=sort(B) end

本文档针对高校排课难的问题,采用数学建模的方法,结合matlab、lingo软件解决了该问题,方案简单易于操作。

计算机模拟的程序代码2: clear;clc;

a=randint(5,5,[0,1]); if sum(sum(a)')==12 a

else continue end

计算机模拟的程序代码3:

clear;clc;

a=randint(5,5,[0,1]); if sum(sum(a)')==12 a

else continue end

计算机模拟的程序代码4:

clear;clc;m1=480;m2=375;m3=630; for i=1:100

A1=randint(1,m1,[1,500]); B1=randint(1,m2,[1,500]);

C1=randint(1,m3,[1,2600]);

n1=1;n2=1;n3=1;A=sort(A1);B=sort(B1);C=sort(C1); for i=(2):m1

if A(1)~=A(i) n=n+1;

A(1)=A(i) ; % else n=n; end end

for k=(2):m2

if B(1)~=B(k) n2=n2+1;

B(1)=B(k) ; % else n2=n2; end

for j=(2):m3 if C(1)~=C(j)

本文档针对高校排课难的问题,采用数学建模的方法,结合matlab、lingo软件解决了该问题,方案简单易于操作。

n3=n+1; C(1)=C(j) ; % else n3=n3; end end

n1;n2;n3;(n1+n2+n3)/30 end

层次分析法代码：

clear;clc;%成对矩阵Q Q=[1 5 4;1/5 1 2;1/4 1/2 1] [V,D]=eig(Q) eng=diag(D) lamda=max(eng)

cil=(lamda-3)/2 crl=cil/0.58

W_guiyihua=V(1:3)./sum(V(:,1))

!lingo求解的代码:

model:

min=0.6870*a-0.1865*b+0.1265*c; a>1/41;a<13/41; b>0.2481;b<0.2508; c<=0.3785*b;c>=0.2982*b; end

本文来源：https://www.bwwdw.com/article/ght1.html