优化建模软件在运筹学整数规划教学中的应用
来源:用户上传
作者:
摘 要
运筹学是一本应用性很强，与实践结合很紧密的课程。本文分析了运筹学（整数规划）教学存在的不足，简要介绍了几种常用的优化建模软件，通过几个典型示例，分别阐述了EXCEL规划求解工具、LINGO、MATLAB等优化软件在运筹学（整数规划）教学中的应用。通过引入优化软件，有助于提高学生的学习兴趣，提高学生的动手实践能力。
关键词
运筹学;整数规划;教学;EXCEL;LINGO;MATLAB
中图分类号： 022;G642.0 文献标识码： A
DOI：10.19694/j.cnki.issn2095-2457.2020.09.010
整数规划是运筹学中的典型问题，应用于解决生产实践、经济管理、国防军事领域的诸多问题，有着广泛的应用前景和重要意义。整数规划问题大部分是线性的，传统的线性规划问题中，部分可行解或者最优解可能是分数或小数，但是对于某些特定问题，常要求可行解、最优解必须是整数（称为整数解）。例如， 所求的解是开设工厂的台数、完成工作的人数或运送货物的车数等，分数或小数解答就不满足要求[1]。因此，需要在线性规划模型中强制要求决策变量或部分决策变量为整数，即得到整数规划（integer programming，IP）或者混合整数规划（mixed integer programming，MIP）模型[2]。针对整数规划或混合整数规划问题，学者们已提出了相应的求解方法，例如分枝定界法、穷举法、割平面算法等，但是算法普遍计算量大、步骤非常烦琐，难以手工完成，需要借助计算机建模求解工具实现。因此，运筹学（整数规划）教学中引入优化建模工具的应用，对于激发学生的学习兴趣，鼓励学生解决实际问题，提高实践能力具有重要意义[3]。
1 整数规划模型
整数规划（混合整数规划）要求所有变量（部分变量）取整数，其标准形式如下所示。
2 常用优化建模软件简介
目前常用的优化应用软件有LINGO、MATLAB、MATHEM ATIC、CPLEX等，其中MATHEMATIC和CPLEX专业性太强，操作复杂，不便于在教学中使用。此外，EXCEL具有强大的数据处理功能，其规划求解工具也可用于整数规划问题的建模和求解，并且操作简便，适合在课堂教学中使用。因此，本文主要介绍EXCEL、LINGO和MATLAB三类优化建模软件在整数规划教学中的应用。
2.1 EXCEL规划求解工具
如前所述，现实中整数规划问题通常是线性问题，适合利用EXCEL强大的表格计算处理能力进行建模求解，因此人们开发了基于EXCEL的规划求解工具。EXCEL规划求解工具求解算法包括单纯形法、非线性GRG算法和演化算法，整数规划可采用非线性GRG算法求解，该方法由Leon Lasdon和AIlan Waren共同開发[4]。规划求解工具是EXCEL中的一个加载项，使用前需要加载，打开“工具/选项/加载项”菜单栏，在打开的“加载项”对话框中选中“规划求解加载项”，点击确定，就将“规划求解”工具添加到“数据”菜单栏中了。
2.2 LINGO
LINGO（Linear Interactive and General Optimizer）是一个交互式的优化求解器，可以求解线性规划问题，也可以求解非线性规划规划问题和非线性方程组。它最初是由美国芝加哥大学的Linus Schrage教授开发的，通过不断完善和扩充，并成立了Lindo公司进行商业化运作[5]。其特色在于可以允许决策变量是整数（即可求解整数规划），操作简便，求解速度快。
优化软件LINGO可以求解整数规划活混合整数规划问题，首先需要根据实际问题，建立问题一般数学模型;然后通过LINGO软件编辑框，采用优化建模语言对数学模型进行描述，使得计算机能够理解，最后调用LINGO软件后台算法求解模型。
2.3 MATLAB
MATLAB是美国MathWorks公司推出的高性能数值计算和可视化软件，主要功能包括数值分析、矩阵计算、信号处理、图形显示、算法开发和模拟仿真等，广泛地应用于数值计算、程序开发、数据采集、系统建模与仿真、数据分析和可视化等领域，是一个功能强大的商业数学软件[6]。MATLAB还是一个开放的开发平台，可以根据需求自己开发相应的功能模块，例如运筹优化常用的YALMIP等[7]。由于具有强大的矩阵计算能力，MATLAB也可用于求解运筹学中的线性规划和整数规划问题。
3 运筹学（整数规划）教学存在的问题
目前，运筹学（整数规划）教学过程中存在一些问题，导致教学效果不佳，主要表现在以下两点：
（1）运筹学被当作数学理论课程，重理论轻实践
运学学课程数学知识、数学理论较多，课程教学过程中存在大量的数学模型，以及相关数学定理的证明及推导，因此运筹学通常被学生们误认为纯数学理论课程。特别是整数规划教学，涉及凸包理论、解空间分解、上下界证明、对偶理论等诸多相对深奥、复杂的数学理论。如果不介绍相关数学理论，则导致学生理解不深入，只知其然不知其所以然，但是如果单纯大量的理论学习，又可能使学生产生畏惧心理，降低学习兴趣。因此，学习过程应当理论指导实践，加深理论基础的同时，注重培养动手实践能力。
（2）整数规划动手实践能力，软件应用能力需要加强
整数规划通常属于NP难问题，运算量大，求解过程极为复杂，即使简单的小规模问题也很难通过手工计算求解，更不用说现实中复杂的大规模问题。因此，如果学生不能熟练使用优化求解软件，就不便于求解大规模问题，进而学生动手能力不足，学习兴趣下降。 4 优化建模软件应用实例
4.1 EXCEL规划求解工具应用实例
例1.某工厂计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时及A、B 两种原材料的消耗，如表1所示[1]。
该工厂每生产一件产品Ⅰ可获利2元， 每生产一件产品Ⅱ可获利3元， 请问应如何安排计划使该工厂获利最多？
第一步，设生产Ⅰ、Ⅱ两种产品的数量分别为x1，x2，建立数学模型，如下所示：
第二步，建立整数规划问题的电子表格模型，如图1所示。
第三步，设置可变单元格和目标单元格，确定决策变量、目标函数和约束条件。设置可变单元格，表示决策变量，记录问题的最优解，令单元格B7和C7作为可变单元格（分别记录变量x1，x2的值）。在可变单元格中输入任意初值，此处都输入0。设置目标单元格，记录目标函数值，即当问题求解完成时，该单元格将显示最优的目标函数值。令D6作为目标单元格（记录目标z的值），输入目标函数公式为D6=SUMPRODUCT（B6：C6，B7：C7），其中SUMPRODUCT表示数组乘积之和，即D5=B6×B7+C6×C7。输入约束条件。选定单元格D3、D4、D5分别表示问题的3个约束条件。利用数组乘积函数SUMPRODUCT，分别输入D3=SUMPRODUCT（B3：C3，B7：C7），D4=SUMPROD UCT（B4：C4，B7：C7），D5=SUMPRODUCT（B5：C5，B7：C7），如图2所示。
第四步，设置规划求解参数。单击菜单栏“数据”中的“规划求解”命令，弹出“规划求解参数”对话框，在“设置目标”选项中输入“$D$6”，“通过更改可变单元格”中输入“$B$7：$C$7”，目标类型选择最大值。设置需要遵守约束条件，单击“添加”按钮，出现“添加约束”对话框，“单元格引用”中输入“$D$3：$D$5”，“约束”输入“$F$3：$F$5”，符号选择“”。本题要求变量为整数，需再输入整数约束，“单元格引用”输入$B$7$C$7，“约束”选择“int整数”。如图3所示。
第五步，调用算法，计算得到规划求解结果。完成求解参数设置后，选择求解方法为“非线性GRG”，勾选“使无约束变量为非负数”，点击“求解”，弹出规划求解结果对话框，如图4所示。
点击确定，就得到相应的求解结果，如图5所示。图中的单元格B7和C7里的数据就是得到的最优解。D6中的数据是z的最大值，即z=14元。
4.2 LINGO应用实例
例1.某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如表2 所示。问两种货物各托运多少箱， 可使获得利润为最大[1]？
第一步，设x1，x2分别为甲、乙两种货物的托运箱数（非负整数），建立数学模型，如下所示：
第二步，在LINGO窗口中输入以下代码：
model：
max=20*x1+10* x2;
5*x1+4* x2 <= 24;
2* x1+5* x2<= 13;
@gin（ x1）;
@gin（ x2 ）;
第三步，點击LINGO 界面的运行按钮，就得到最优值为90，其中x1=4，x2=1，如图6所示。
4.3 MATLAB应用实例
以4.1节例1为例，介绍MATLAB如何求解整数规划问题，首先建立问题数学模型，如4.1节所示，此处省略。然后，采用MATLAB脚本文件编制如下程序
f=[-2，-3];
A=[1，2;4，0;0，4];
b=[8;16;12];
C=[];
d=[];
xm=[0;0];
xM=1e+10*[1;1];
[x，y，flag]=intlinprog（f，[1，2]，A，b，C，d，xm，xM）;
此处，需要注意的是MATLAB默认求解最小化问题，而本问题是最大化问题，需转化为最小化问题，因此目标函数系数f为负数。程序编写完成后，点击运行，即可得到问题的解为x1=4，x2=2，目标函数为-14（真实目标为14）元。
5 结语
运筹学是一门紧贴实际应用的学科，运筹学教学不仅要向学生传授理论知识，介绍模型和算法，也要培养学生的实践能力，指导学生运用运筹学知识解决实际问题。传统教学过程中，学生普遍沉迷于数学推导和解题，动手实践能力普遍不足。在教学过程中引入优化建模软件，能够促进学生运用所学知识解决实际问题，提高学生的学习兴趣，实现更好的学习效果。
参考文献
[1]运筹教材编写组.运筹学[M].北京： 清华大学出版社，2012.
[2]Jünger，M.，Liebling，T.M.，Naddef，D.，Nemhauser，G.L.，Pulleyblank，W.R.，Reinelt，G.，...& Wolsey，L.A.（Eds.）.50 Years of integer programming 1958-2008：From the early years to the state-of-the-art[M]. Springer Science & Business Media，2009.
[3]陈候炎，徐玉娥，陈其嶙.整数规划模型EXCEL求解的简化方法[J].科学与财富， 2011（12）：116-116.
[4]于瑛英.EXCEL在运筹学规划论教学中的应用[J].教育教学论坛，（10）：285-287.
[5]管梅.LINGO在运筹学实践教学中的应用[J].科技视界， 2015（12）：21-22+24.
[6]张明，王文文.MATLAB在经管类运筹学教学中的探索与实践[J].大学教育， 2012（07）：83-84+91.
[7]俞武扬.YALMIP工具箱在运筹学实验教学中的应用[J].实验室研究与探索， 2017（8）.
转载注明来源:https://www.xzbu.com/8/view-15205492.htm
