应用LINGO和MATLAB软件求解线性规划

应用LINGO、MATLAB软件求解线性规划一、LINGO使用简介LINGO软件是美国的LINDO系统公司（LindoSystemInc）开发的一套用于求解最优化问题的软件包。LINGO除了能用于求解线性规划和二次规划外，还可以用于非线性规划求解以及一些线性和非线性方程（组）的求解等。LINGO软件的最大特色在于它允许优化模型中的决策变量为整数，而且执行速度快。LINGO内置了一种建立最优化模型的语言，可以简便地表达大规模问题，利用LINGO高效的求解器可快速求解并分析结果，这里简单介绍LINGO的使用方法。LINGO可以求解线性规划、二次规划、非线性规划、整数规划、图论及网络优化和排队论模型中的最优化问题等。一个LINGO程序一般会包含集合段、数据输入段、优化目标和约束段、初始段和数据预处理段等部分，每一部分有其独特的作用和语法规则，读者可以通过查阅相关的参考书或者LINGO的HELP文件详细了解，这里就不展开介绍了。LINGO的主要功能特色为：1、既能求解线性规划问题，也有较强的求解非线性规划问题的能力；2、输入模型简练直观；3、运算速度快、计算能力强；4、内置建模语言，提供几十个内部函数，从而能以较少语句，较直观的方式描述大规模的优化模型；5、将集合的概念引入编程语言，很容易将实际问题转换为LINGO模型；并且能方便地与Excel、数据库等其他软件交换数据。LINGO的语法规定：（1）求目标函数的最大值或最小值分别用MAX=…或MIN=…来表示；（2）每个语句必须以分号“；”结束，每行可以有许多语句，语句可以跨行；（3）变量名称必须以字母(A~Z)开头，由字母、数字(0~9)和下划线所组成，长度不超过32个字符，不区分大小写；（4）可以给语句加上标号，例如[OBJ]MAX=200*X1+300*X2；（5）以惊叹号“！”开头，以分号“；”结束的语句是注释语句;（6）如果对变量的取值范围没有作特殊说明，则默认所有决策变量都非负；（7）LINGO模型以语句“MODEL：”开头，以“END”结束，对于比较简单的模型，这两个语句可以省略。0,12416482.32max21212121xxxxxxtsxxS在LINGO的MODEL窗口内输入如下模型：model:max=2*x1+3*x2;x1+2*x2=8;4*x1=16;4*x2=12;End例1.1用LINGO求解线性规划问题：选菜单Lingo|Solve(或按Ctrl+U),或用鼠标点击“求解”按纽，如果模型有语法错误，则弹出一个标题为“LINGOErrorMessage”(错误信息)的窗口，指出在哪一行有怎样的错误，每一种错误都有一个编号（具体含义可查阅相关文献或LINGO的Help）。改正错误以后再求解，如果语法通过,LINGO用内部所带的求解程序求出模型的解,然后弹出一个标题为“LINGOSolverStatus”(求解状态)的窗口,其内容为变量个数、约束条件个数、优化状态、耗费内存、所花时间等信息,点击Close关闭窗口,屏幕上出现标题为“SolutionReport”(解的报告)的信息窗口,显示优化计算(线性规划中换基迭代)的步数、优化后的目标函数值、列出各变量的计算结果。本例的具体内容如下：Globaloptimalsolutionfoundatiteration:5Objectivevalue:14.00000VariableValueReducedCostX14.0000000.000000X22.0000000.000000RowSlackorSurplusDualPrice114.000001.00000020.0000001.50000030.0000000.125000044.0000000.000000124,2xx该报告说明：运行5步找到全局最优解，目标函数值为14，变量值分别为。“ReducedCost”的含义是需缩减成本系数或需增加利润系数（最优解中取值非零的决策变量的ReducedCost值等于零）。“Row”是输入模型中的行号，目标函数是第一行；“SlackorSurplus”的意思是松弛或剩余，即约束条件左边与右边的差值，对于“”的不等式，右边减左边的差值为Slack（松弛），对于“”的不等式，左边减的右边差值为Surplus（剩余），当约束条件两边相等时，松弛或剩余的值等于零。“DualPrice”的意思是对偶价格（或称为影子价格），上述报告中Row2的松弛值为0，表明生产甲产品4单位、乙产品2单位，所需设备8台时已经饱和，对偶价格1.5的含义是：如果设备增加1台时，能使目标函数值增加1.5。报告中Row4的松弛值为4，表明生产甲产品4单位、乙产品2单位，所需原材料乙8公斤还剩余4公斤，因此增加原材料乙不会使目标函数值增加，所以对偶价格为0。123451234512345123451234512345min0.20.70.40.30.50.320.61.8600.10.050.020.20.0530.050.10.020.20.088.52,,,,0Sxxxxxxxxxxxxxxxxxxxxstxxxxxxxxxx在LINGO的MODEL窗口内输入如下模型：Min=0.2*x1+0.7*x2+0.4*x3+0.3*x4+0.5*x5;0.3*x1+2*x2+x3+0.6*x4+1.8*x560;0.1*x1+0.05*x2+0.02*x3+0.2*x4+0.05*x53;0.05*x1+0.1*x2+0.02*x3+0.2*x4+0.08*x58;X1+x2+x3+x4+x552;例1.2用LINGO求解如下问题求解输出结果如下:Globaloptimalsolutionfoundatiteration:4Objectivevalue:22.40000VariableValueReducedCostX10.0000000.7000000X212.000000.000000X30.0000000.6166667X430.000000.000000X510.000000.000000RowSlackorSurplusDualPrice122.40000-1.00000020.000000-0.583333334.1000000.00000040.000000-4.16666750.0000000.883333311minzs.t.CXAXbAXblbXub(1.1)1.2应用MATLAB求解线性规划•MATLAB（MATrixLABoratory）的基本含义是矩阵实验室，它是由美国MathWorks公司研制开发的一套高性能的集数值计算、信息处理、图形显示等于一体的可视化数学工具软件。它是建立在向量、数组和矩阵基础之上的，除了基本的数值计算、数据处理、图形显示等功能之外，还包含功能强大的多个“工具箱”，如优化工具箱（optimizationtoolbox）、统计工具箱、样条函数工具箱和数据拟合工具箱等都是优化计算的有力工具。在这里仅介绍用MATLAB6.5优化工具箱求解线性规划问题。•一般线性规划问题的数学模型为•其中C是目标函数的系数行向量（常数）,X是n维列向量（决策变量），A,A1是常数矩阵，b,b1是常数向量，lb,ub是n维列向量分别表示决策变量X的下界与上界。•在Matlab优化工具箱（OptimizationToolbox）中，求解线性规划的程序如下：[x，fval，exitflag，output，lambda]=linprog(c，A，b，Aeq，beq，lb，ub，x0，options)，具体说明见下页。说明：(1)A是不等式约束的系数矩阵，b是相应的常数列向量，若没有不等式约束，则均用[]代替；(2)Aeq是等式约束的系数矩阵，beq是相应的常数列向量，若没有等式约束，则均用[]代替；(3)如果某个变量无下界，则用-inf表示；如果某个变量无上界，则用inf表示，若决策变量无下界，则lb用[]代替；若决策变量无上界，则ub用[]代替；(4)x0是线性规划的初始解，这种设计仅对中规模算法有效，通常可以缺省。(5)输出x是最优解，fval是最优值。(6)输出exitflag描述了程序的运行情况，若其值大于零，表示程序收敛到最优解；若其值等于零，表示计算达到了最大次数；若其值小于零，表示问题无可行解，或程序运行失败。(7)输出output表示程序运行的某些信息，如迭代次数(iterations)、所用算法(algorithm)、共轭梯度(cgiterations)等。(8)lambda表示解处的拉格朗日乘子，其中lower，upper，ineqlin，eqlin分别对应于下界、上界、不等式约束与等式约束。例1.3用MATLAB解线性规划问题123123123123123226442212005minzxxxxxxxxxs.t.xxxx,x,x（1.2）解Matlab程序如下:c=[-2,-1,1];A=[1,4,-1;2,-2,1];b=[4;12];Aeq=[1,1,2];beq=6;lb=[0,0,-inf];ub=[inf,inf,5];[x,z]=linprog(c,A,b,Aeq,beq,lb,ub)运行后得到输出Optimizationterminatedsuccessfully.x=4.66670.00000.6667z=-8.6667例1.4用MATLAB求解线性规划问题123123123max2357..25100,1,2,3izxxxxxxstxxxxi（1.3）解首先转化为求最小值问题123123123min2357..25100,1,2,3izSxxxxxxstxxxxiMatlab程序如下c=[-2,-3,5];A=[-2,5,-1];b=-10;Aeq=[1,1,1];beq=[7];lb=[0,0,0];[x,z]=linprog(c,A,b,Aeq,beq,lb)运行后得到输出x=6.42860.57140.0000z=-14.5714键入s=-z运行后得到原问题的目标函数最大值s=14.5714用MATLAB求解例1.2的程序与输出结果为：c=[0.2,0.7,0.4,0.3,0.5];A=[-0.3,-2,-1,-0.6,-1.8;-0.1,-0.05,-0.02,-0.2,-0.05;-0.05,-0.1,-0.02,-0.2,-0.08;1,1,1,1,1];b=[-60;-3;-8;52];lb=[0,0,0,0,0];[x,z]=linprog(c,A,b,[],[],lb)Optimizationterminatedsuccessfully.x=0.000012.00000.000030.000010.0000z=22.4000习题建立下列线性规划问题的数学模型并求解。（1）某工厂生产A、B、C三种产品，三种产品对于材料费用、劳动力和电力的单位消耗系数，资源限量和单位产品价格如表1.1所示。问应如何确定生产计划可使得总产值达到最大？建立线性规划问题的数学模型。表1.1生产计划问题的数据产品资源ABC资源限量材料费用（元）22.54320劳动力（人天）618640电力（度）5510750单位价格（百元）6410（2）某疗养院营养师要为某类病人拟订一周的菜单。可供选择的蔬菜及其费用和所含营养成分的数量以及这类病人每周所需各种营养成分的最低数量如表1.2所示。另外，为了口味的需要，规定一周内所用卷心菜不多于2份，其他蔬菜不多于4份。若病人每周需要14份蔬菜，问选用每种蔬菜各多少份，可使生活费用最小。建立线性规划问题的数学模型。表1.2食谱问题的数据蔬菜每份蔬菜所含营养成分费用（元/份）铁(mg)磷(mg)VA(单