选课问题、数学建模

2013-2014第一学期

数学建模课程设计

题目姓名：班级： 学生选课

*** 网络工程\\

2014年1月6日—1月10日

第 1 页 共 12 页

：

数学建模课程设计

一．模型摘要

摘要：对于习惯了中小学课程（所有的课程由学校统一安排，而且科目从小学

到高中有连续性）的大学新生来说，大学的课程多得令他们眼花缭乱，课程分类也比较复杂，因此选课对他们而言还是一件新鲜而陌生的事物。但大学的学习与选课有莫大的关系，必须了解它，才能掌握主动权。而要了解选课制，首先要对大学的课程设置有所认识。

大学的课程按大类来说一般分为必修课和选修课。必修一般指学校或院系规定学生必须修习某课程，学校对必修课程一般有统一的要求和安排。选修是指根据学生个人兴趣或专业需要自由选择修习某课程。简言之，必修就是必须修读，选修就是选择性修读。一般来说，基础性的知识都作为必修课程。有些知识不是基础性的，与兴趣和研究方向有关，这部分知识可以选择。这是大学与中学最大的不同之处。

本文针对关于大学生选课时所需要考虑到的问题，根据学校规定的要求达到

的学分与每门课的学分多少，运用排列组合的知识建立模型，通过分析输出各种情况下所需的选课方案

关键字：matlab，矩阵，排列组合

二． 问题重述

某同学考虑下学期的选课，其中必修课只有一门（2学分），可供选修的限定选修课（限选课）有8门，任意选修课（任选课）有10门。由于有些课程之间相互关联，所以可能在选修某门课程时必须同时选修其他某门课程，课程信息见表 学分 同时选修要求 任选课课号 学分 限选课课号 同时选修要求 5 9 3 1 8 5 10 3 2 6 4 11 3 3 4 4 12 2 4 5 3 1 13 2 5 7 3 14 2 6 6 3 2 15 1 7 2 16 1 8 17 1 18 1 按学校规定，学生每个学期选修的总学分数不能少于20学分，因此该同学必须在上述18门课中至少选修18个学分，学校还规定学生每学期选修任选课的比例

第 2 页 共 12 页

数学建模课程设计

不能少于所修总学分（包括2个必修学分）的1/6,也不能超过所修总学分的1/3。学院也规定，课号为5，6，7，8的课程必须至少选一门。

1）为了达到学校和院系的规定，该同学下学期最少应该选几门课？应该选哪几门课？

2）若考虑在选修最少学分的情况下，该同学最多可以选修几门课？选哪几门？

三．模型假设

（1）学生选修任何课程都是随机的，不存在主观意图。实际生活中选课程是有主观意图的，但是本问题中不考虑这一点。

（2）学生只要选修某门课程，就认为他能够获得该门课程的学分，不考虑实际生活中的考试不及格得不到学分的情况。

（3）学校所给的课程，不管任何课程，都应当是做过调研，一般情况下学生只要选择，就能选上，而不会出现连选几门都选不上的局面。也就是说选课所给的限制人数应当是合理的限制。

四．问题分析

根据提出的问题，学生要选修的课程必须同时满足下列四条： （a）任何学生每个学期选修的总学分数不能少于20学分（包括2个必修学分），所以除了必修课程外，任何学生必须在上述18门课中至少选修18个学分 （b）学校规定，课号为5，6，7，8的课程必须至少选一门。

（c）同时选修的课必须同时选修，不能不选修。例如某学生选9号课，那么他

5791011121314也必须同时选修8号课。同时选修的矩阵是

12864576（d）学校规定学生每学期选修任选课的比例不能少于所修总学分（包括2个必修学分）的1/6,也不能超过所修总学分的1/3。即总修学分任选课学分总修学分。

63注意，总修学分包括必修课的2学分。

两个个问题都需要选课方案。比如第一个问题，“为了达到学校和院系的规定，该同学下学期最少应该选几门课？应该选哪几门课？”学校规定最少学分是20分，去掉2分的必修学分，那么要从剩下18门课程中选择至少18个学分。问题问的是“最少应选几门课？”按照最少18分的限制，从1门、2门、3门、4门、5门……收入来思考，发现至少应该选5门课，因为如果选4门课，要达到最少学分势必需要选那些学分值大的课，只能选1、2、3、4这四门课，这四门课的学分加了起来正好是18分，但虽然学分数满足了，可是并不满足其余的三

第 3 页 共 12 页

数学建模课程设计

条，所以这种选法是不对的。选5门课就能得到要求。例如选1、2 、3 、6 、10 、14就其中一种选课方案，它满足上述4条。

四条规定相互制约，错综复杂，单靠人力来一组一组的确定是不可能完成的。

五．模型建立

本问题的解答模型就是排列组合的知识。首先说明一点，因为课程号码有的与学分值的数目相同，为了避免在计算机上处理过程中出现紊乱，我们统一把课程号码加上10，课号1-18，就变成了11-28。

假设这个同学在符合学校规定要求的前提下要选n门课，5n18：

n第一步，首先把11-28门课程抽出n门课进行组合，共有C18种。利用Matlab

的命令就是combntns([11:28],n)，这个命令产生的结果是一个矩阵，每一行就是n门课的一个组合。令选课组合xkzuhe=combntns([11:28],n) 第二步 以下分四个模块，每个模块使用一个矩阵来存储该模块筛选合格的数据。

（a）第一个模块是判断每个n门课组合的学分总和是否大于18分，如果大于等于18分，就保留，并且把该条n门课组合添加到矩阵a中。矩阵a用来存储满足了大于18分的n门课的组合。

（b）第二个模块是判断矩阵a中每个n门课的组合是否是含有5，6，7，8至少一门课。如果是至少含有5，6，7，8至少一门课，就把该行记录添加到b矩阵里，矩阵b用来存储满足了含有5，6，7，8至少一门课的组合

（c）第三个模块是c模块，用来存放满足同时选修要求的n门课的组合数

1517192021221324据。同时选修的矩阵是。先分析以下同时选1112181614151716修的要求，在一个n门课的组合中，比如有15号课，就必须有11号课；有17号课，就必须有12号课；有19号课，就必须有18号课等等。一方面，要判断任意一个n门课组合是不是符合上述要求，比如它含有15号课，又同时含有11号课，那么就保留这个n门课组合；另一方面，经过上述的判断保留，b矩阵就删除了一部分不符合要求的，但是保留的却也不是都适合，比如一个记录，含有15号课且含有11号课，保留下来了，但是如果这个记录同时含有17号课且不含有12号课，那么这个记录就不适合，需要再次删除。因此，第三个模块需要分成两个子模块来判断，就是上面的两个方面。第一个子模块先大范围的保留基本适合的，8对同时选修课，只要含有至少一对就保留。第二个模块是分别对每对选修课进行检验，含有15号课不含有11号课的或者含有17号课不含有12号课的或者含有19号课不含有18号课的或者含有20号课不含有16号课的……等等，都全部删除。经过这两个子模块的判断，剩下的数据给c矩阵。

（d）第四个模块是判断上述c矩阵内的数据是否适合

总修学分总修学分的规定。注意，总修学分包括必修课的任选课学分632学分。适

合的就保留下来给d矩阵。

最后的d矩阵就是符合要求的n门课的组合。

第 4 页 共 12 页

数学建模课程设计

六．模型求解

一、 第一个问题“为了达到学校和院系的规定，该同学下学期最少应该选几门课？应该选哪几门课？”

答：应该选5门课，在筛选程序内给定n=5,可得到应该选的5门的组合： 1 2 6 10 14 1 4 6 10 11 2 4 6 10 11

选修最少学分的情况下，该同学最多可以选修几门课？选哪几门？

把程序里面的s>=18改成s=18，然后依次把选课门数改成5、6、7、8等，可以看出最多选8门课，8门课的组合是：

1 3 5 12 15 16 17 18 1 3 6 14 15 16 17 18 1 4 5 12 15 16 17 18 1 4 6 14 15 16 17 18 1 5 6 8 12 15 16 17 1 5 6 8 12 15 16 18 1 5 6 8 12 15 17 18 1 5 6 8 12 16 17 18 1 5 6 8 14 15 16 17 1 5 6 8 14 15 16 18 1 5 6 8 14 15 17 18 1 5 6 8 14 16 17 18 2 3 6 14 15 16 17 18 2 3 7 8 15 16 17 18 2 3 7 13 15 16 17 18 2 4 6 14 15 16 17 18 2 4 7 8 15 16 17 18 2 4 7 13 15 16 17 18 2 6 7 8 13 15 16 17 2 6 7 8 13 15 16 18 2 6 7 8 13 15 17 18 2 6 7 8 13 16 17 18 2 6 7 8 14 15 16 17 2 6 7 8 14 15 16 18 2 6 7 8 14 15 17 18 2 6 7 8 14 16 17 18 3 4 6 8 14 15 16 17 3 4 6 8 14 15 16 18 3 4 6 8 14 15 17 18 3 4 6 8 14 16 17 18

第 5 页 共 12 页

数学建模课程设计

七．模型分析与改进

1． 模型分析与检验:

本题主要采用的是排列组合的方法，首先把11-28门课程抽出n门课进行

n组合，共有C18种。利用Matlab的命令就是combntns([11:28],n)，这个命令产

生的结果是一个矩阵，每一行就是n门课的一个组合。令选课组合xkzuhe=combntns([11:28],n)。再将其分四个模块，每个模块使用一个矩阵来存储该模块筛选合格的数据。不断筛选满足要求的矩阵，最后剩余的矩阵即为符合要求的n门课的组合。

2． 模型评价

2.1 模型优点：能够很快的解决简单的筛选问题。

2.2 模型缺点：对于条件比较多的筛选问题则很难快速的解决。

3 模型改进和推广：

1.还可以参照最小费用最大流算法适当地进行建模。

2.也可以使用多次背包算法，先把给出的图用拓扑排序算法构建成树，在树里面的每个结点使用背包算法，计算出当前点以下用一定时间能得到的最大学分，多个背包向父亲结点背包。

3.本文建立的模型可推广到各种复杂的筛选问题。

八．建模心得

数学建模，对于我们专业的大二学生来说是一个完全陌生的课程，然而在本学期末的课程设计中却开设了数学模型，这才使我们初步了解了什么叫做数学建模。使我们在学习之中，锻炼了我们的能力，获益非浅。真正用到了数学的理论知识去解决我们在实际生活上的一些问题。从最初的“建模”简介，我们了解到数学在实际生活中的应用之广、之深、之切。小到日常的衣食住行，大到科技进步，人类生存。庞大的数学知识体系良好地规范我们的生活，与我们每个人都

第 6 页 共 12 页

数学建模课程设计

息息相关，并随着科技的进步，数学与我们的关系也越来越密切。终于明白了，为什么数学是真正的科学工具，是人类发展进步的基础学科，它既能规范现在，又能预测未来。

在这次实践中，我们组选择的是关于学生选课模型 ，这个模型说说简单也简单，说难也难，关键看如何灵活的建立模型，并借助计算机软件的优势，巧妙的解决此问题。在确立了题目之后，我们两个就开始着手分头行动，经过多天的努力模型基本建成。通过这次合作完成任务，我们感觉到团队精神是数学建模是否取得好成绩的最重要的因素，只有将大家的智慧集中到一起，才能做出更加完美的成果！

参考文献：

[1]费浦生 数学建模及其基础知识详解 ， 武汉大学出版社 [2周义仓 数学建模实验 西安交通大学出版社 1999年 [3]韩明 数学实验（Matlab） 同济大学出版社 2009年

附录：

Matlab筛选程序如下：

n=input('请输入选课的门数：','s');

xk=[11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28;5 5 4 4 3 3 3 2 3 3 3 2 2 2 1 1 1 1]; xkzuhe=combntns([11:28],n); [hang,lie]=size(xkzuhe); a=zeros(1,lie); for i=1:hang s=0;

for j=1:lie

[xkhang,xklie]=find(xk==xkzuhe(i,j)); s=s+xk(2,xklie); end; if s>=18

a=[a;xkzuhe(i,:)]; end; end;

[ahang,alie]=size(a); a=a(2:1:ahang,:);

*************以上第一模块 [ahang,alie]=size(a); b=zeros(1,alie);

第 7 页 共 12 页

数学建模课程设计

for i=1:ahang p=0;

for j=1:alie

if a(i,j)==15||a(i,j)==16||a(i,j)==17||a(i,j)==18 p=p+1; end; end; if p>=1

b=[b;a(i,:)]; end; end;

[bhang,blie]=size(b); b=b(2:1:bhang,:);

*************以上第二模块[bhang,blie]=size(b); c=zeros(1,blie); for i=1:bhang p1=-1;p2=-2; p3=-1;p4=-2; p5=-1;p6=-2; p7=-1;p8=-2; p9=-1;p10=-2; p11=-1;p12=-2; p13=-1;p14=-2; p15=-1;p16=-2; p17=-1;p18=-2; for j=1:blie if b(i,j)==15 p1=1; end;

if b(i,j)==10 p2=1; end;

if b(i,j)==17 p3=1; end;

if b(i,j)==12 p4=1; end;

if b(i,j)==19 p5=1; end;

第 8 页 共 12 页

数学建模课程设计

if b(i,j)==18 p6=1; end;

if b(i,j)==20 p7=1; end;

if b(i,j)==16 p8=1; end;

if b(i,j)==21 p9=1; end;

if b(i,j)==14 p10=1; end;

if b(i,j)==22 p11=1; end;

if b(i,j)==15 p12=1; end;

if b(i,j)==23 p13=1; end;

if b(i,j)==17 p14=1; end;

if b(i,j)==24 p15=1; end;

if b(i,j)==16 p16=1; end; end;

if p1==p2||p3==p4||p5==p6||p7==p8||p9==p10||p11==p12||p13==p14||p15==p16 c=[c;b(i,:)]; end; end;

[chang,clie]=size(c);

第 9 页 共 12 页

数学建模课程设计

c=c(2:1:chang,:);

…………..以上第三模块的第一子模块 [chang,clie]=size(c); i=1;

while i<=chang p1=0;p2=0; p3=0;p4=0; p5=0;p6=0; p7=0;p8=0; p9=0;p10=0; p11=0;p12=0; p13=0;p14=0; p15=0;p16=0; p17=0;p18=0; for j=1:clie if c(i,j)==15 p1=1; end;

if c(i,j)==11 p2=1; end;

if c(i,j)==17 p3=1; end;

if c(i,j)==12 p4=1; end;

if c(i,j)==19 p5=1; end;

if c(i,j)==18 p6=1; end;

if c(i,j)==20 p7=1; end;

if c(i,j)==16 p8=1; end;

if c(i,j)==21 p9=1;

第 10 页 共 12 页

数学建模课程设计

end;

if c(i,j)==14 p10=1; end;

if c(i,j)==22 p11=1; end;

if c(i,j)==15 p12=1; end;

if c(i,j)==23 p13=1; end;

if c(i,j)==17 p14=1; end;

if c(i,j)==24 p15=1; end;

if c(i,j)==16 p16=1; end; end; if

(p1==1&p2==0)||(p3==1&p4==0)||(p5==1&p6==0)||(p7==1&p8==0)||(p9==1&p10==0)||(p11==1&p12==0)||(p13==1&p14==0)||(p15==1&p16==0) c(i,:)=[];

[chang,clie]=size(c); i=i-1; end; i=i+1; end;

****************以上第三模块的第二子模块 [chang,clie]=size(c); d=zeros(1,clie); for i=1:chang zxf=0;zrxf=0; for j=1:clie

[h,l]=find(xk==c(i,j)); zxf=zxf+xk(2,l); if c(i,j)>=19

第 11 页 共 12 页

数学建模课程设计

zrxf=zrxf+xk(2,l); end; end;

if zrxf>=(zxf+2)/6&&zrxf<=(zxf+2)/3 d=[d;c(i,:)]; end; end;

[dhang,dlie]=size(d); d=d(2:1:dhang,:); f=ones(size(d)); zh=d-f*10

第 12 页 共 12 页