选课策略模型论文

绍兴文理学院数学建模题目:选课策略数学模型数学系数学与应用数学专业081班学生徐贝贝姚慧张楚指导老师胡金杰摘要为解决学生选课问题最优解，本文利用0-1规划模型先找出目标函数，再列出约束条件，分三步骤对最终问题逐层分析化多目标规划为单目标规划，分别建立不同的模型，运用LINGO软件求解。从而解决学生既希望选修课程的数量少，又希望所获得的学分多的问题。特点：根据以上分析，特将模型分为以下四个(1)只考虑尽可能多的学分，而不管所修课程的多少，可建立单目标规划模型。显然，这个问题不必计算就知道最优解是选修全部课程。(2)在考虑课程最少的情况下，使学分最多；模型一，选修课的课程最少，不考虑学分多少；约束条件只有，每人至少学习5门数学，2门运筹学，2门计算机，1门物理学，1门经济学，2门艺术类和先修课的要求建立模型一。模型二：在科目最少的基本前提下，使获得的学分尽可能得多，约束条件没变，化单目标为多目标求解。（3）同时考虑学分最多和选修科目最少，并且假设所占比例三七分。在此假设情况下对模型二稍加调整形成新的目标函数，最终计算出结果。模型三：同时考虑课程最少和所获得的学分最多，并按3:7的重要性建立模型。关键词0-1规划选修课要求单目标规划多目标规划一．问题的重述某学校规定，运筹学专业的学生毕业时必须至少学过五门数学课，两门运筹学课,两门计算机，一门物理学，一门经济学和两门艺术类。这些课程的编号，名称，学分，所属类别和选修课的要求如表所示。那么，毕业时最少可以学习这些课程中的哪些课程。如果某个学生即希望选修课程的数量最少，又希望所获得的学分最多，他可以选修哪些课程？课程编号课程名称学分所属类别先修课要求1微积分5数学2数学分析5数学3实变函数4数学4泛函分析3数学数学分析；实变函数5线性代数4数学6最优化方法4数学；运筹学微积分；线性代数7应用统计4数学；运筹学微积分；线性代数8数据结构3数学；计算机计算机编程9操作系统4数学；计算机10信号与系统3数学；物理学数学分析11风险投资管理2运筹学12预测理论4运筹学应用统计13计算机模拟3运筹学：计算机计算机编程14数学实验3运筹学；计算机微积分；线性代数15西方经济学3运筹学；经济学16计算机编程2计算机17VB4计算机计算机编程18大学物理5物理学19物理实验3物理学；大学物理20固体物理学3物理学21会计学4经济学；22电影艺术赏析3艺术23青春期生理卫生2艺术24汉语言文化3艺术25体育舞蹈3艺术二符号说明符号说明1)xi:表示选修的课程（xi=0表示不选，xi=1表示选i=1,2,3,4,5,6,7,8,9…25）；三模型的假设1)学生只要选修就能获得学分；2）每个学生都必须遵守规定选修课程；四问题分析。模型一：只考虑课程最少，不考虑学分，计算求出结果。模型二：既考虑课程最少，又使学分最多，计算求出结果。模型三：同时考虑两者，并考虑二者的权重,计算求出结果。五模型的建立与求解模型一：用xi=1表示选修表中按编号顺序的25门课程（xi=0表示不选；i=1,2,…,25）.问题的目标为选修的课程总数最少，既minz=x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15+x16+x17+x18+x19+x20+x21+x22+x23+x24+x25（1）约束条件包括两个方面：第一，每个人每人至少学习5门数学，2门运筹学，2门计算机，1门物理学1门经济学，2门艺术类。根据表中对每门课程所属类别的划分，这一约束可以表示为x1+x2+x3+x4+x5+x6+x7+x8+x9+x10=5（2）x6+x7+x11+x12+x13+x14+x15=2（3）x8+x9+x13+x14+x16+x17=2（4）x10+x18+x19+x20=1（5）x15+x21=1（6）x22+x23+x24+x25=2（7）第二，某些课程有先修课程的要求。例如“数据结构”的先修课是“计算机编程”，这意味着如果x8=1,必须想x16=1，这个可以表示为x8=x16(注意x8=0对x16没有影响)“泛函分析”先修课是“数学分析”和“实变函数”的条件可以表示为x4=x2,x4=x3.而这两个不等式可以用一个约束表示为2x4-x2-x3=0.这样，所有课程的先修课要求可表示为如下的约束：2x4-x2-x3=0（8）2x6-x1-x5=0（9）2x7-x1-x5=0（10）x8-x16=0（11）x10-x2=0（12）x12-x7=0（13）x13-x16=0（14）x14-x1-x5=0（15）x17-x16=0（16）x19-x18=0（17）由上得到以（1）为目标函数、以（2）~（17）为约束条件的0-1规划模型。将这一模型输入LINGO软件（见附录1），求解得到结果为x1=x2=x5=x9=x10=x14=x15=x22=x23=1,其他变量为0.对照课程编号它们是微积分,数学分析,线性代数,操作系统,信号与系统,数学实验,西方经济学,电影艺术赏析,青春期生理卫生,共9门课程，总学分为32.下面我们会看到，这个解并不是唯一的，还可以找到与以上不完全相同的9门课也满足所给的约束条件。模型二：如果一个学生既希望选修课程少，又希望所得的学分尽可能的多，则除了目标一还可以根据已知数据写出另一个目标函数，即MaxW=5*x1+5*x2+4*x3+3*x4+4*x5+4*x6+4*x7+3*x8+4*x9+3*x10+2*x11+4*x12+3*x13+3*x14+3*x15+2*x16+4*x17+5*x18+3*x19+3*x20+4*x21+3*x22+2*x23+3*x24+3*x25（18）如果模型一得到的结果是唯一的，则他别无选择，只能选修上面的9门课，总学分为32.但是LINGO无法告诉我们一个优化问题的解是否唯一，所以还可能在选修9们课的条件下，使总学分多于32。为探索这种可能，应在上面的规划问题中增加约束x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15+x16+x17+x18+x19+x20+x21+x22+x23+x24+x25=9（19）得到以（18）为目标函数、以（2）~（17）和（19）为约束条件的另一个0-1规划模型（见附录2）。求解后发现会得到不同于前面9门课程的最优解x1=x2=x5=x9=x10=x14=x15=x22=x24=1,其他变量为0，其中2学分的“青春期生理卫生”换成了3学分的“汉语言文化”，总学分由32增至33.注意这个模型的解任然不是唯一的，如x1=x2=x5=x9=x10=x14=x15=x22=x25=1，其他变量为0，也是最优解。模型三：不像模型一模型二那样，只考虑课程最少或学分最多，而是觉得学分和课程这两个目标大致应该三七开。这时可以将目标函数Z和-W分别乘以0.7和0.3，组成一个新的目标函数Y，有MinY=0.7Z-0.3W=(x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15+x16+x17+x18+x19+x20+x21+x22+x23+x24+x25)*0.7-(5*x1+5*x2+4*x3+3*x4+4*x5+4*x6+4*x7+3*x8+4*x9+3*x10+2*x11+4*x12+3*x13+3*x14+3*x15+2*x16+4*x17+5*x18+3*x19+3*x20+4*x21+3*x22+2*x23+3*x24+3*x25)*0.3=-0.8*x1-0.8*x2-0.5*x3-0.2*x4-0.5*x5-0.5*x6-0.5*x7-0.2*x8-0.5*x9-0.2*x10+0.1*x11-0.5*x12-0.2*x13-0.2*x14-0.2*x15+0.1*x16-0.5*x17-0.8*x18-0.2*x19-0.2*x20-0.5*x21-0.2*x22+0.1*x23-0.2*x24-0.2*x25(20)得到以（20）为目标、以（2）~（17）为约束的0-1规划模型。输入LINGO求解（见附录3）。得到为x1=x2=x3=x4=x5=x6=x7=x8=x9=x10=x12=x13=x14=x15=x16=x17=x18=x19=x20=x22=x24=x25=1,即只有“风险投资管理”“青春期生理卫生”没有选修，共82学分。六．结果的检验与分析经过检验输入式子正确，结果多次验证一样。结果分析：模型一分析：模型一的结果为x1=x2=x5=x9=x10=x14=x15=x22=x23=1即选修编号为1，2,5,9，10,14,15,22,23的选修课时达到了，在选修课的课程最少。最少为9门。模型二分析：模型二的结果为x1=x2=x5=x9=x10=x14=x15=x22=x24=1即选修编号为1，2,5,9，10,14,15,22,24的选修课时达到了，在选修课程最少的情况下，尽可能的分数最多，最多为33学分。模型三分析：课程数与学分数按权重三七分，结果为x1=x2=x3=x4=x5=x6=x7=x8=x9=x10=x12=x13=x14=x15=x16=x17=x18=x19=x20=x22=x24=x25=1,即只有“风险投资管理”“青春期生理卫生”没有选修，共82学分。六．模型的评价与推广本文运用了0-1规划解决了学修课选择的难题，但是还没有建立满足不同需要的学生，还需要进一步的建立模型和计算。如建立以学分最多为目标的模型，或建立以课程数和学分数等权重的模型。解决不同的问题。七．参考文献【1】姜启源谢金星叶俊，数学模型，高等教育出版社，2003年8月第3版附录1.模型一的求解本文运用LINGO软件求解输入：min=x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15+x16+x17+x18+x19+x20+x21+x22+x23+x24+x25;x1+x2+x3+x4+x5+x6+x7+x8+x9+x10=5;x6+x7+x11+x12+x13+x14+x15=2;x8+x9+x13+x14+x16+x17=2;x10+x18+x19+x20=1;x15+x21=1;x22+x23+x24+x25=2;2*x4-x2-x3=0;2*x6-x1-x5=0;2*x7-x1-x5=0;x8-x16=0;x10-x2=0;x12-x7=0;x13-x16=0;2*x14-x1-x5=0;x17-x16=0;x19-x18=0;@bin(x1);@bin(x2);@bin(x3);@bin(x4);@bin(x5);@bin(x6);@bin(x7);@bin(x8);@bin(x9);@bin(x10);@bin(x11);@bin(x12);@bin(x13);@bin(x14);@bin(x15);@bin(x16);@bin(x17);@bin(x18);@bin(x19);@bin(x20);@bin(x21);@bin(x22);@bin(x23);@bin(x24);@bin(x25);输出：Globaloptimalsolutionfound.Objectivevalue:9.000000Extendedsolversteps:0Totalsolveriterations:0VariableValueReducedCostX11.0000001.000000X21.0000001.000000X30.0000001.000000X40.0000001.000000X51.0000001.000000X60.0000001.000000X70.0000001.000000X80.0000001.000000X91.0000001.000000X101.0000001.000000X110.0000001.000000X120.0000001.00