基于大学生选课问题的线性规划模型

王茜

【摘要】本文针对大学生选课问题，分别以选课门数最少及所得学分最多为目标，建立双目标线性规划模型，采用不同方法分别利用lingo软件进行求解，获得最优方案.

【关键词】线性规划；双目标；权重；大学生选课

随着我国高校教学改革的推进，大学生选修课逐步增多，纷繁复杂的选修课令他们眼花缭乱.如何选择课程，既要满足课程间的前后顺序和学校的要求，又要符合自己的兴趣且达到门数最少.本文利用线性规划，针对选修门数最少和学分最多，研究了两种不同的选课模型，利用lingo程序求解，获得了最优方案.

一、问题的提出

某大三学生，第一学期的必修课只有一门（2个学分）；可供限定选修的课程有8门，任意选修课程有10门.由于有些课程之间有联系，所以可能在选修某门课程时必须同时选修其他课程，这18门课程的学分数和要求以及相应信息如下表所示.

按学校规定，每名学生每学期所修总分不能少于21学分，因此学生必须在上述18门课程中至少选修19学分，学校同时还规定学生每学期选修任意选修课的学分不能少于3学分，也不能超过6学分.为了达到学校的要求，请为该学生确定一种选课方案.

二、问题分析

由题意可知，我们首先要确定选哪门课的问题，每门课都有选与不选两种情况.可引入0-1变量xi，即xi=1，选修第i门课，0，不选第i门课，ci表示第i门课的学分.学生选择选修课时，考虑选修的门数越少越好，修得的学分越多越好.故考虑分别以选修门数和学分为目标建立模型.

三、模型建立与求解

设Z表示选修门数，W表示所修得总学分.

1.建立模型一

得到结果x1=1，x2=1，x3=1，x4=1，x11=1，minZ=5，即最小需要选择5门课程，编号为1，2，3，4，11.

方案二：由方案1得知，最少选修5门课程.当选修课程门数最少时，所修得学分越多越好，则以学分总数最大为目标，则lingo程序如下：

model：

sets：

kehao/1..18/：x，a；

endsets

data：

a=5，5，4，4，3，3，3，2，3，3，3，2，2，2，1，1，1，1；

enddata

max=@sum（kehao（i）：a*x）；

@sum（kehao（i）：x）=5；

@sum（kehao（i）|i#gt#8：a*x）>=3；

@sum（kehao（i）|i#gt#8：a*x）<=6；

x（1）>=x（5）；x（2）>=x（7）；x（8）>=x（9）；x（6）>=x（10）；

x（4）>=x（11）；x（5）>=x（12）；x（7）>=x（13）；x（6）>=x（14）；

@for（kehao（i）：@bin（x））；

end

得到结果 x1=1，x2=1，x3=1，x4=1，x11=1，max W=21，即在选修5门课程的基础上，最多可获得21学分，所选课程编号为1，2，3，4，11.

2.建立模型二

由于学生的偏好不同，对选修课门数与学分重要性的认知不同，考虑对两者取权重，建立新的模型如下：

目标函数：minY=a·∑18i=1xi-b·∑18i-1cixi，

其中a，b为权重，约束条件同模型一.

利用lingo11.0进行求解，程序如下：

model：

sets：

kehao/1..18/：x，c；

endsets

data：

c=5，5，4，4，3，3，3，2，3，3，3，2，2，2，1，1，1，1；

enddata

z1=@sum（kehao（i）：x）；

z2=@sum（kehao（i）：c*x）；

min=a*z1-b*z2；

a=0.8；b=0.2；

@sum（kehao（i）：c*x）>=19；

@sum（kehao（i）|i#gt#8：c*x）>=3；

@sum（kehao（i）|i#gt#8：c*x）<=6；

x（1）>=x（5）；x（2）>=x（7）；x（8）>=x（9）；x（6）>=x（10）；

x（4）>=x（11）；x（5）>=x（12）；x（7）>=x（13）；x（6）>=x（14）；

@for（kehao（i）：@bin（x））；

end

分取权重（0.7，0.3；0.8，0.2；0.9，0.1）进行比较，取权重a=0.8，b=0.2及a=0.9，b=0.1时，运行结果x1=1，x2=1，x3=1，x4=1，x11=1，最少选5门课程，最大学分21分.

四、结束语

对比上面两个模型，本文针对大学生选课问题，设置0-1变量，以选课门数最少及所得学分最多为目标，从不同角度，通过设置双目标以及引入权重将双目标转化为单目标的方法，建立线性规划模型，利用lingo软件进行求解，所得结果相同，即为最优方案.双目标模型在生活中的应用较为常见，但求解往往较为复杂，本文引入权重的思想对双目标模型进行转化，为双目标模型的求解提供了新的思路.

【参考文献】

[1]韩中庚.数学建模方法及其应用[M].北京：高等教育出版社，2009.

[2]姜启源，谢金星，叶俊.数学模型[M].北京：高等教育出版社，2003.

[3]肖华勇.实用数学建模与软件应用[M].西安：西北工业大学出版社，2008.