基于多目标规划的学生选课问题探索

基于多目标规划的学生选课问题探索Xxx，xxx，xxx摘要学生选课问题属于一类整数线性优化问题，为了不同的学生需求需要设计相应的选课策略。针对第一问，本文在学校和院系的规定条件下建立了满足同学选课最少的0-1整数优化模型，并利用LINGO软件对其进行了求解，得到了选课最少是选五门，选择方案是选择课程1，2，6，10，14。针对第二问，本文综合考虑了在满足选修学分最少的条件下同学可以选最多选修课程，于是建立了双目标优化模型，并引入偏好系数把双目标优化问题转化为单目标优化问题，并再次利用LINGO软件对其进行了求解，得到了所选的课程是1，3，6，8，15，16，17，18。针对第三问，本文考虑了在选修课程限选人数不同的情况下，针对不同的学生类型，利用对不同目标加权的方法对问题进行优化求解，设计了不同的选课方案。最后本文对问题进行了进一步的讨论和模型的改进，并对模型进行了评价和推广，使得问题得到了圆满的解决。关键词：0-1整数优化模型LINGO双目标优化模型偏好系数0：背景分析某同学考虑下学期的选课，其中必修课只有一门（2学分），可供选修的限定选修课（限选课）有8门，任意选修课（任选课）有10门。由于有些课程之间相互关联，所以可能在选修某门课程时必须同时选修其他某门课程，课程信息见下表1：表1：课程信息表按学校规定，学生每个学期选修的总学分数不能少于20学分，因此该同学必须在上述18门课中至少选修18个学分，学校还规定学生每学期选修任选课的比例不能少于所修总学分（包括2个必修学分）的1/6,也不能超过所修总学分的1/3。学院也规定，课号为5，6，7，8的课程必须至少选一门。试问：1）为了达到学校和院系的规定，该同学下学期最少应该选几门课？应该选哪几门?2）若考虑在选修最少学分的情况下，该同学最多可以选修几门课？选哪几门？3）若考虑到选修时课程能否如愿选上的问题，请多准备几套选择方案。已知课程限选人数为1，2，3，4限选人数最多，5，6，7，8次之，13、17、18限选人数最少。请考虑选课时的先后顺序（先选者先录，人满停选）。1.问题提出对于问题一,我们必须考虑在学校和院系的规定的条件下对同学选课最少进行求解。所以我们先从已知条件入手，把他们转化为约束条件，然后建立0-1整数优化模型，利用LINGO软件对其进行求解。对于问题二，我们同样考虑在选修学分最少的情况下对同学选课最多进行求解。但两者不能同时都满足，所以我们必须把这个双优化模型转化为单优化模型，然后再利用LINGO对其进行求解。问题三则是考虑了选修课程限选人数的问题，所以必须针对不同的学生类型设计相应的选择方案。同时考虑到选修的课程能否如愿选上，需要在已只知不同课程限选人数的情况下，利用对不同目标加权的方法对问题进行优化。2符号说明与模型假设2．1符号说明表2:符号说明表注：其它符号在文中另加说明2．2模型假设（1）：各个同学在选修课程时不受其他因素影响，只受学分和选修课程门数影响。（2）：学生选课是独立的，相互之间不影响。（3）：选课的学生有两种类型，一类是对这门课真正感兴趣的，另一类是“混学分”的，且这两类各占选课学生人数的一半。（4）：学生的信息是不公开的。（5）：问题三中没有提到的课程表示人数没有限制。3模型建立和求解3.1问题一的解决3.1.1模型的建立用xi表示选修表中按照编号顺序的18门课程的选择（i=1,2,…18），其中xi取值为1或者0。其定义如下：采用目标规划的方法，考虑到学校的各种约束条件，将约束条件用数学表达式表示为一下几点：1：要使选修课程的总学分数不少于18，既有下面的不等式：2：任选课程的比例不能少于所修总学分的1/6，也不能超过1/3：3：课程号为5、6、7、8的课程必须至少选一门：4：选修某些课程必须同时选修其他课程，可以表示为：在达到以上要求的情况下，只考虑选修课程最少的情况,相应的目标函数为：在Lingo[1]中可以对该目标函数进行优化，其中约束条件为①②③④，由于上述条件中有大于关系，可以在两边乘以—1将约束条件全部转换成小于关系，这样便于在Lingo中求解.最后本文建立了如下的优化模型3.1.2模型的求解利用LINGO软件求解可以得到3.1.3问题一的结果最后本文得到了在学校和院系的要求下选课最少是选五门，选择方案是选择课程1，2，6，10，14。3.2问题二的解决3.2.1模型的建立对上述两个目标函数进行向量优化[2]，其中将乘以－1，即得到了双目标规划：T=(minS,-maxZ)。如下：3.2.2模型的求解在求解双线性规划问题时，我们引入偏好系数[3]的概念，即学生在选择学分最少和课程最多时的偏向趋势。设λ1为学生偏向选择学分最少的趋势，λ2为学生偏向选择课程最多的趋势。则最后的最优目标化为：如果只考虑学分最少，而不管课程多少。即考虑时，λ1=1,λ2=0用LINGO解得应该选择课程：3，4，6，8，9，14。如果只考虑课程最多，而不管学分多少。即考虑λ1=0,λ2=1时，用LINGO求解得到：应该选择课程：1，2，3，4，5，6，7，8，13，15，16，17，18在选修学分最少的情况下，我们可以把和结合起来，把双优化问题转化为单优化问题，得到如下优化模型。利用LINGO软件对其进行求解得到如下结果:应该选择课程：2,6,7,8,14,16,17,18.下面对学分和课程数进行加权形成一个新的目标计算，本文采用三七分于是问题转化为所以应该选择课程：1，3，6，8，15，16，17，183.2.3问题二的结果最后本文得到了在学分和课程三七分的情况下，所选的课程是1，3，6，8，15，16，17，18。3.3问题三的解决为了解题的方便，对课程感兴趣的学生用G(Good)型表示和不感兴趣的学生用B(Bad)表示。设某一课程的人数要求是N，用p1表示课程1，2，3，4的权重，用p2表示课程5，6，7，8的权重，用p3表示课程13，17，18的权重。因为课程1，2，3，4的限选人数比课程5，6，7，8多，而课程5，6，7，8限选人数比13，17，18多，所以也可以用pi(i=1,2,3),来表示学生选上相应课程的概率。首先我们针对G学生设计相应的选课方案，由之前分析知道G学生希望是在学生少的情况下多选一些课程，所以有第二问得到了他们所选的课程是：1，3，6，8，15，16，17，18。因为p1p2p3，所以G学生选课的顺序是：1，3，6，8，17，18，15，16。再针对B学生，也由之间的分析知道B学生希望在满足学分要求内所选课程越少越好，根据第一问得到了他们所选的课程是：1，2，6，10，14。因为p1p2p3，所以B学生选课的顺序是：1，2，6，10，14。4模型的检验我们从LINGO软件求解的结果可以看出问题一中的ReducedCost全部是正的，它表明如果改变任何一变量xi，的结果将变大，同样问题二中的ReducedCost全部是负的，它表明如果改变任何一变量xi，的结果将变小，所以验证了模型的正确性。5模型的进一步讨论和改进问题二在解决的时候考虑了三七分这种情况，我们也可以分别对其他情况进行研究，得到了如下表3的结果：表3:学分与课程数其他情况分类表同时本文针对不同的问题建立不同条件下的优化模型，本文只使用了LINGO对其进行了求解。针对优化问题求解的方法多种多样，还可以使用木箱原理、单纯形法，线性规划对其进行求解，然后针对不同的结果进行比较，可以得到更好的结果。还有针对问题三，我们可以建立带有权值的优化问题，使得问题解决的更加完美。6结语（一）选课问题的一些背景[4]:改革开放以来，随着高等教育改革的深入，我国的各高校纷纷推出各类“公共选修课”、“素质教育通选课”、“任选课”等选修课，让学生在学好本专业课程之余，能够自由选择感兴趣的选修课。这些课程的设置与现代社会对知识广博、有创新和实践能力的高素质人才的要求是相适应的，也是我国高等教育与国际接轨、向素质教育转变的必由之路。这类选修课的涌现，给高校学生提供了培养学习兴趣、拓展知识面的宝贵机会。然而由于选修课不同于专业课，考核方式通常比较宽松。因此出现了部分同学把这些课作为“捞分课”，平时不认真上课，只为“混学分”，这完全违背了高校开设这类课的初衷。由于教室座位数量有限或其他限制因素，任何课程提供的选课机会并不总是能够满足所有选课同学的需要。“混学分”的学生占用了某门课程的教学资源，必然造成另外一些对该课程真正感兴趣的学生无法选课。产生这个现象我们认为主要是因为学校校选修课现行选课机制还不够完善，因此我们提出一些建议，希望能起到些许作用。（二）具体的情况：总的来说选修课程的学生有混学分和真正对课程感兴趣两类。我们学校是通过“先到先学分与课程数的分类21:λλ选课结果得”机制供学生选课，但事实上这并不能很好地区分学生类型，例如混学分的学生可能会挤掉真正感兴趣的学生的选课机会，导致高校教学资源不能被有效利用。教师可以采取两种考核方式：严厉的考核方式和宽松的考核方式［5］。为了剔出混学分的学生，教师可以采取严厉的考核方式。然而,信息是不完全的，学生的类型属于私人信息。通常选课时，教师拿到的选课单上只有姓名、学号和院系年级等信息，无法获知学生的类型，由于学生类型为私人信息，严厉的考核方式下仍存在一定的效率损失。起初学生往往会想着一定要选择自己喜欢的选修课程，但经历过几次选课后都会产生“能选上就好”的心理。实际上这是有悖与学校的初衷的。因此解决这个问题十分重要。（三）具体措施［6］：（1）可以增加选修课的数量和种类，例如很多学生都反应文化修养类课程还是比较少，学生比较期望一种欢快轻松的课堂环境，因为学生平时上专业课往往会有些劳累，他们希望能在选修课上得到放松，所以我们应该适量的并且有针对性的增加选修课的种类。同时，我们也要增加选修课的数量，这样同类的选修课的总体容量就会增加，这样就让大家有更多的机会，并且可以满足大多数人的需求。（2）采取严厉考核方式，那些混学分的同学都是深知选修课情况的，他们知道平常的选修课很容易就能拿到学分，所以也不必认真的学，只要挂着选上的名，最后去考试，甚至都不用考试就能通过。如果采用严厉的考核方式，就是让那些不好好学的同学不好通过这样可以打消那些混学分的同学的想法，让他们在选课时尽量去选择他们喜欢的，每个人都选择自己喜欢的这样就可以避免资源的浪费。（3）高校应该鼓励更多教师开设选修课，可以更多的专业的老师都开设选修课，这样也是增加选修课种类的一种方法，适当条件下还可请外校老师跨校开课，丰富选修课的种类和数量，使学生有更大的选择空间，从而找到自己感兴趣的选修课，可以在一定程度上避免了混学分现象的出现。（4）高校还应加强对学生选课的指导和教育工作，例如可以在学生选课前给他们传达一下学校开设选修课的思想，让学生从思想意识上明确选修课的目的和意义，他们也会意思到选修课对他们的重要性，他们也会自觉地选择自己喜欢的课程，这样可以杜绝混学分现象的存在。（5）教师可以采取在选课时让来选课的学生递交选课申请的方法，让他们写明选此课的原因。老师可据此粗略地对学生类型进行区分。老师还可在退换课结束前把课讲得很难，让“混学分”的学生知难而退，能坚持选课的必然都是对该课真正感兴趣的学生。（四）总结学校的每一种教育体制的推出都是为了学生更好的发展的，学校的每一部教育体制的改革也是为了学生考虑的。我们很幸运很接受到如此好的教育，因此我们应该好好的珍惜，认真的对待每一门课程，相信只要认真对待，选修课也会成为大学课堂中非常精彩的一个部分。参考文献[1]谢金星,薛毅.优化建模与LINDO/LINGO软件.北京:清华大学出版社,2005[2]陈光亚.多目标（向量）优化理论*的现状和展望.[EB/OL][3]陶菊春,吴建民.综合加权评分法的综合权重确定新探[J]系统工程理论与实践.2001年8月第8期[4]王欢,李华.实施学分制需要解决一些深层次问题.[EB/OL]