搜索
Lingo与最优化---艾鑫最优化模型是数学建模中应用最广泛的模型。它主要是用数学方法研究各种系统和实际问题的优化设计，控制和管理的途径以及策略，使某一目标最大化或最小化。大家在中学阶段肯定接触过简单的只有几个变量的线性规划模型（最优化的一种）求解也一般用图解法，但是实际生活中的最优化问题一般要复杂得多。在某些经济模型中变量的数目可能达到成百上千，这时候一般的图解法就不太现实了，所以这时候一般是利用计算机求解。最优化的种类有很多，每一种的算法都又不太一样，我们现在去学习各种各样的算法，然后自己编程是不太现实的。幸运的是，现在已经有许多软件已经内置了针对各种规划模型的求解器，我们只需要将数学模型通过相应的计算机语言表示出来就可以了，至于内部具体如何求解的，我们目前并不关心。Lingo就是这样一种软件，只要你把相应的模型通过它能识别的语言输入进去，它会自动判断模型类型，并用相应的求解器求解。下面我们首先打开Lingo。双击桌面上的图标就可以打开。打开后可以看到这样的界面：其中程序代码就写在“LINGOModel”窗口里面。下面介绍一个简单的最优化模型，看看怎么用Lingo来求解。例例例例1111：（生产安排问题）某工厂生产A、B两种产品，工厂能够使用的劳动力最多有3500人，原料最多有4000kg，电力最多有2000kW时，每生产1kg的产品A、成品B，所需要的劳动力、原料、电力和经济效益如下表所示，问如何安排产品A和产品B的生产，可使经济效益最大？劳动力原料电力经济效益A7526B5857首先建立起相应的数学模型。设生产产品A和产品B的产品分别为kgx1和kgx2时，可使经济效益最大，这里的x1和x2分别代表有待决策生产的产品A和产品B的数量，故称x1和x2为决策变量。那么产品A生产的经济效益为6x1(元)，产品B生产的经济效益为7x2(元)，产品A和产品B的生产共同产生的经济效益（设为Z）为：2176xxZ+=要使此经济效益最大，其数学表达式为：2176maxxxZ+=但是，产品A和产品B的生产又要受到劳动力、原料、电力的限制，因此需要用数学表达式描述这些限制，使生产这两种产品不得超过劳动力、原料、电力的限制。对劳动力的限制因素可表示为：35005721≤+xx对原料的限制因素可表示为：4000852≤+xxx对电力的限制因素可表示为：20005221≤+xx此外还有一个隐含的限制因素，即NxNx∈∈21,。这样就可以得到问题的完整的数学模型为：(5),(4)200052(3)400085(2)350057t.s.(1)76max212122121NxNxxxxxxxxxZx∈∈≤+≤+≤++=在上述表达式中，max表示求最大值，一般称为极大化（min表示求最小，称为极小化）；s.t.是“subjectto”，意思是“受约束与”或“受限制于”。上述模型的意思就是求函数式（1）的最大值，其中决策变量x1和x2受约束于(2)-(5)式。通常称函数式（1）为目标函数（ObjectiveObjectiveObjectiveObjectiveFunctionFunctionFunctionFunction），称表达式（1）至（5）为约束条件（ConstraintConstraintConstraintConstraintConditionConditionConditionCondition）。那么怎么用Lingo求解上述模型呢？一般分为这几个步骤：1.1.1.1.问题的输入其实对于这类简单的最优化模型，Lingo的输入其实相当傻瓜化。Lingo代码如下：max=6*x1+7*x2;7*x1+5*x2=3500;5*x1+8*x2=4000;2*x1+5*x2=2000;@gin(x1);@gin(x2);提醒一下，在计算机语言中表达式的输入跟我们平时习惯的写法有点区别，两个数相乘中间一定要有“*”号，不能省略。另外在LINGO中每一句语句的后面要加“;”号，表示此语句结束。解释一下上面语句的意思：max=6*x1+7*x2;是目标函数。如果是最小化则写成：min=...;LINGO总是根据“max=”或“min=”寻找目标函数，而其他语句默认都是约束条件。因此语句的顺序并不重要。接下来的三句话很简单就是约束条件。最后一行有点特殊，它是用来约束x1和x2为整数的。其中@gin()为整数约束函数。LINGO里面还有其他类似的变量界定函数如下：@bin(x)限制x为0或1@bnd(L,x,U)限制L=x=U@free(x)取消对变量x的默认下界为0的限制，即x可以取任意实数@gin(x)限制x为整数注意这里我仅仅限制了x1和x2为整数并没有限制它们非负。这是因为在LINGO里面默认限制所有的变量非负。@free取消了默认的下界为0的限制，使变量也可以取负值。@bnd用于设定一个变量的上下界,它也可以取消默认下界为0的约束。另外顺便提一下，LINGO是大小写不敏感的，也就是说在LINGO里面大写字母和小写字母没有任何区别，x1和X1是同一个变量。2.问题求解当模型输入后，用鼠标单击工具栏上面的按钮或LINGO菜单下的Solve选项，或按Ctrl+S组合键，LINGO软件开始求解所输入的模型。点击“求解”后一般会弹出两个窗口，一个是“SolverStatus”(求解器状态)窗口，一个是“结果报告框”(SolutionReport)，如下图所示（图示中的版本为汉化版）：先谈谈求解器状态窗口，求解器状态窗口显示了当前求解器的状态、以及模型的相关信息。由于这个模型太过简单，当你看到这个窗口的时候问题已经解决了，所以我们看到是求解后的状态。求解器状态窗口中提供了一个“中断求解器”选项，当一个模型的求解需要较长时间时，点击它会导致LINGO在下一次迭代时停止求解。通常情况下我们不希望这样的情况发生，因为中断求解器后得到的解可能根本不是最优解、也可能不是可行解，或者是局部最优解。但是有些情况下中断求解器是可以的，要解释这一点，先要解释这个窗口的几个参数的含义。先来看左下角“求解器状态”这一栏。里面的“目标边界”的意思是说此模型目标的上界或者下界。对于求最大值问题，目标边界就是指的目标的上界，即目标的最大值一定小于或等于目标边界，对于求最小值问题则正好相反。在来看“最优对象”，它的含义是目前的最佳解。对于求最大值模型，“最优对象”当然就是目前的最大值，对于求最小值模型，“最优对象”就是目前的最小值。在这里我们发现“最优对象”和“目标边界”的值相等都是3760，很显然这意味这我们已经找到最优解。这当然是理想情况，但是对于有些问题求解时间过长，这个时候我们就可以观察“最优对象”和“目标边界”的差值。若两者之间差距不是很大，而且过了很长时间“最优对象”也没有变化，这时候就可以考虑中断求解器得到一个“近似最优解”。再来看一下左上角的“求解器状态”。第一个是“模型类别”（ModelClass），它显示的是当前模型的类型。最优化模型有很多种，不同的模型求解的难易程度不一样，下表基本上按照从简单到困难列举了各种可能的模型。缩写模型说明LP线性规划(LinearProgram)所有表达式都是线性的，并且没有整数约束QP二次规划(QuadraticProgram)所有表达式都是线性或二次的，并且没有整数约束ILP混合型整数线性规划(IntegerLinearProgram)所有表达式都是线性的，并且一部分变量有整数约束IQP混合型整数二次规划(IntegerQuadraticProgram)所有表达式都是线性或者二次的，并且一部分变量有整数约束从上面可以看出，我们之前的模型是纯整数线性规划模型(PILP)，因为它所有的表达式都是线性的，并且两个变量都有整数约束，线性的意思是说变量之间的关系是一次的，在数学上可以理解为一阶导数为常数的函数。非线性则指不成比例、不成直线的关系，一阶导数不为常数。一般来说，如果涉及到两个或多个变量相乘、除，或者含有某个变量的二次或更高次方的模型一般都是非线性规划模型。从上表可以看出求解非线性规划问题要比线性规划问题困难得多。这是因为线性规划已经有非常成熟的算法，使绝大部分线性规划问题都能瞬间秒杀。而非线性规划问题则要复杂得多，虽然一直有人在做这方面的研究，但是非线性规划的求解时间一般情况下要慢许多，当问题规模过大时，找到最优解几乎是不可能的。所以在建模时尽量建立成线性规划模型，对于非线性规划模型要多想想看能不能转换成线性规划问题。这里有人可能会问，一个问题是非线性的就是非线性的，是线性的就是线性的，难道一个问题可以既是线性规划问题又是非线性规划问题吗？但是事实是，对于一个特定的问题，所建立的模型并不是唯一的，可能一种思路建出的模型是线性规划另一种思路建出来的是非线性规划模型。如何将非线性规划转换成线性规划，有一定的技巧，但是这种技巧只能在实践中积累经验慢慢掌握。再来看一下“求解器状态”中的“状态”一栏。“状态”显示了当前解的状态。主要有一下几种状态：“GlobalOptimum”(全局最优)、“LocalOptimum”(局部最优)、“Feasible”(可行)、“Infeasible”(不可行)、“Unbounded”(无界的)、“Interrupted”(被中断)、“Undetermined”(待定的)。“全局最优”的意思是当前解是最优解，而“局部最优”却不一定是最优解，它们两者的关系有点像最大值点与极值点的关系。其他的几个意思比较明确，在这里就不再啰嗦了。3.3.3.3.结果分析最后在说一下“求解结果报告框”(SolutionReport)。结果报告框共有三个部分。第一部分在最前面几行。如下图：一般第一行是当前求得的解的情况。就我们例题来说是这样一句话：Globaloptimalsolutionfound.意思是找到全局最优解。PILP纯整数线性规划(PureIntegerLinearProgram)所有表达式都是线性的，并且所有变量都有整数约束PIQP纯整数二次规划(PureIntegerQuadraticProgram)所有表达式都是线性或者二次的，并且所有变量都有整数约束NLP非线性规划(NonlinearProgram)至少有一个表达式是非线性的INLP整数非线性规划(IntegerNonlinearProgram)至少有一个表达式是非线性的，并且一部分变量有整数约束(一般情况下，这类模型非常难解)PINLP纯整数非线性规划(PureIntegerNonlinearProgram)至少有一个表达式是非线性的，并且全部变量都有整数约束(一般情况下，这类模型非常难解)接下来几行分别是“目标函数值”（Objectivevalue）、“目标边界值”(Objectivebound)、“不可行性”(Infeasibilities)、“拓展求解器步骤”(Extendedsolversteps)、“迭代次数”(Totalsolveriterations)。第二部分由三列组成，描述最优解的情况：VariableValueReducedCostX1300.0000-6.000000X2280.0000-7.000000第一列，“Variable”表示变量名；第二列，“Value”表示变量在最优点出取的值；第三列，“ReducedCost”表示简约成本，它本质上是线性规划问题的检验数（与检验数相差一个负号），因此也称为判别数。第三部分也由三列组成，描述达到最优解的情况下问题约束的状况。第一列，“Row”表示约束的行号，其中第一行表示目标行（LINGO将目标也看成是一个约束）；第二列，“SlackorSurplus”表示松弛变量或剩余变量，当松弛变量或剩余变量值为0时，表示该行的约束是“紧”约束，也就是有效约束；第三列“DualPrice”表示问题的对偶价格（影子价格）。（我们暂不考虑对偶价格，有兴趣的同学可以自己下去了解下）4.4.4.4.文件的存储与调用当模型（程序）运行完成后，需要将模型进行存储，以便下次使用。单击模型窗口“