数学建模实验四

《数学建模》实验四(共7页)

--本页仅作为文档封面，使用时请直接删除即可-- --内页可以根据需求调整合适字体及大小--

《数学建模》实验报告

实验序号： 实验四 日期： 2015年6月3日 班级 遥感1402班 姓名 郑永杰 学号 3 实验名称 整数规划与lingo程序设计 选课策略 实验目的： 1）学会lingo软件的基本使用方法。 2）加强学生对0-1变量的认识和理解；培养学生建模的能力。 3）了解多目标规划模型求解基本原理。 实验内容及要求： 1 、以选课门数最少为目标建立选课策略数学规划模型。 2 、在选课门数最少的前提下，以学分最多为目标建立选课策略数学规划模型。 3 、既要选课门数少，又要学分多，建立2个目标的多目标规划模型，并用线性加权组合的方式将多个目标处理成一个新目标, 化为单目标规划进行求解。 问题分析与假设： 上述问题为数学规划中的多目标规划问题，可以建立0-1规划模型进行求解，设变量Xi表示课号，令Xi=1表示选课，Xi=0表示不选，然后根据题目建立目标函数和约束条件，最后用lingo软件求解。 对于第一个问题: 以选课门数最少为目标建立选课策略数学规划模型,可以直接列目标函数记为最小值求解； 对于第二个问题：在选课门数最少的前提下，以学分最多为目标建立选课策略数学规划模型，可以把问题一选课最少求解结果作为已知量再去建立学分最多目标函数记为最大值； 对于第三个问题：既要选课门数少，又要学分多，就通过建立2个目标的多目标规划模型，并用线性加权组合的方式将多个目标处理成一个新目标, 化为单目标规划进行求解。 2

模型的建立和求解： 用Xi=1表示选修表中按编号顺序的9门课程（Xi=0表示不选；i=1,2…，9）。问题的目标为选修的课程总数最少，即 minz1Xi i19约束条件包括两个方面： 第一， 每人最少要学习2门数学课，3门运筹课和2门计算机课，根据表中对每门课程所属x1x2x3x4x52类别的划分，这一约束可以表示为：x3x5x6x8x93 x4x6x7x92第二， 某些课程要有先修的要求，例如“数据结构”的先修课程“计算机编程”，意味着如果x4=1必须x7=1，可以表示为x4 x7，同里其他先修课程亦是如此。其中x1 x3，x2 x3可以用一个约束表示为2x3-x2-x1 0，故所有课程的先修课程要求可以表示为以下约束： 2x3x1x20x4x702x5x1x20 x6x70x8x502x9x1x20将以上目标函数和约束条件所建立的模型输入到lingo中求解（注意加上xi为0-1约束） 对于第二个问题，在选课最少的前提下，即选课门数为6，使得学分最高。目标函数即：maxz25x14x24x33x44x53x62x72x83x9 约束条件除问题一以上约束外再增加选课门数约束,即： x1x2x3x4x5x6x7x8x96 再次输入lingo求解 对于第三个问题，既要选课门数少，又要学分多，建立2个目标的多目标规划模型，并用线性加权组合的方式将多个目标处理成一个新目标, 化为单目标规划进行求解。所以建立目标函数为 maxzmaxz2maxz1 4x13x23x32x43x52x6x7x82x9约束条件如问题一，此处略。输入lingo后求解。 结果分析与检验： 问题一求解结果为x1=x2=x3=x6=x9=1，其他变量为0.对照编号，若使选课最少，可选择微积分，线性代数，最优化方法，计算机模拟，计算机编程，数学实验，共6门课程，总学分21. 问题二得到结果为：在选课门数最少的前提下，学分最高为22，此处6门课程分别是x1=x2=x3=x5=x7=x9=1，其余为零。 问题三求解结果为目标函数值是16，此处6门课程分别是x1=x2=x3=x5=x7=x9=1，其余为零，学分最高为22，答案同问题二。 3

附录： 问题一程序 model: min=x1+x2+x3+x4+x5+x6+x7+x8+x9; x1+x2+x3+x4+x5>2; x3+x5+x6+x8+x9>3; x4+x6+x7+x9>2; 2*x3-x1-x2<0; x4-x7<0; 2*x5-x1-x2<0; x6-x7<0; x8-x5<0; 2*x9-x1-x2<0; @bin(x1);@bin(x2);@bin(x3);@bin(x4);@bin(x5);@bin(x6);@bin(x7);@bin(x8);@bin(x9); end 程序结果 Global optimal solution found. Objective value: Objective bound: Infeasibilities: Extended solver steps: 0 Total solver iterations: 0 Model Class: PILP Total variables: 9 Nonlinear variables: 0 Integer variables: 9 Total constraints: 10 Nonlinear constraints: 0 Total nonzeros: 38 Nonlinear nonzeros: 0 Variable Value Reduced Cost X1 X2 X3 X4 X5 X6 X7 X8 X9 4

Row Slack or Surplus Dual Price 1 2 3 4 5 6 7 8 9 10 问题二程序： model: max=5*x1+4*x2+4*x3+3*x4+4*x5+3*x6+2*x7+2*x8+3*x9; x1+x2+x3+x4+x5>2; x3+x5+x6+x8+x9>3; x4+x6+x7+x9>2; 2*x3-x1-x2<0; x4-x7<0; 2*x5-x1-x2<0; x6-x7<0; x8-x5<0; 2*x9-x1-x2<0; x1+x2+x3+x4+x5+x6+x7+x8+x9<6; @bin(x1);@bin(x2);@bin(x3);@bin(x4);@bin(x5);@bin(x6);@bin(x7);@bin(x8);@bin(x9); end 程序结果： Global optimal solution found. Objective value: Objective bound: Infeasibilities: Extended solver steps: 0 Total solver iterations: 0 Elapsed runtime seconds: Model Class: PILP Total variables: 9 Nonlinear variables: 0 Integer variables: 9 Total constraints: 11 Nonlinear constraints: 0 Total nonzeros: 47 Nonlinear nonzeros: 0 Variable Value Reduced Cost X1 X2 X3 X4 X5 X6 X7 X8 X9 5

Row Slack or Surplus Dual Price 1 2 3 4 5 6 7 8 9 10 11 3 4 5 6 7 8 9 10 11 问题三程序： model: max=4*x1+3*x2+3*x3+2*x4+3*x5+2*x6+1*x7+1*x8+2*x9; x1+x2+x3+x4+x5>2; x3+x5+x6+x8+x9>3; x4+x6+x7+x9>2; 2*x3-x1-x2<0; x4-x7<0; 2*x5-x1-x2<0; x6-x7<0; x8-x5<0; 2*x9-x1-x2<0; x1+x2+x3+x4+x5+x6+x7+x8+x9<6; @bin(x1);@bin(x2);@bin(x3);@bin(x4);@bin(x5);@bin(x6);@bin(x7);@bin(x8);@bin(x9); end 程序结果： Global optimal solution found. Objective value: Objective bound: Infeasibilities: Extended solver steps: 0 Total solver iterations: 0 Elapsed runtime seconds: Model Class: PILP Total variables: 9 Nonlinear variables: 0 Integer variables: 9 Total constraints: 11 Nonlinear constraints: 0 Total nonzeros: 47 Nonlinear nonzeros: 0 6

Variable Value Reduced Cost X1 X2 X3 X4 X5 X6 X7 X8 X9 Row Slack or Surplus Dual Price 1 2 3 4 5 6 7 8 9 10 11 7