第三章线性规划及LINGO求解

1第三章线性规划及LINGO求解在工程技术、经济管理、科学研究和日常生活等诸多领域，人们常常遇到这样的问题，就是在一系列客观或主观条件的限制之下，寻求使所关注的某个指标达到最大或最小，这类决策问题通常称为优化建模或最优化问题．解决最优化问题的一般方法是建立优化模型、求解最优决策．2一般地，优化模型包括目标函数与约束条件．当目标函数与约束条件中出现的解析表达式均为线性表达式时，则称之为线性规划(LP)．本章主要内容是线性规划模型的建立、二维决策变量情形下的图象解法以及较复杂线性规划模型的LINGO求解．33-1线性规划模型的建立及二维决策变量的图解3-1-1线性规划模型的建立例1某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，这两种产品分别需要在A、B、C、D四种不同的设备上加工．按工艺设计要求，产品Ⅰ与产品Ⅱ在四种设备中所需要的加工台时（一台设备工作一小时称为一台时）见后表，4产品设备ABCD产品Ⅰ2140产品Ⅱ22045已知设备A、B、C、D在计划期内有效台时分别是12、8、16、12，产品Ⅰ与产品Ⅱ的单位利润分别是2、3（单位：百元）．问如何安排生产，才能使利润最大？6假设x1，x2分别表示在计划期内产品Ⅰ与产品Ⅱ的产量，z表示所获得的利润，则有这就是目标函数．根据设备A、B、C、D在计划期内有效台时、产品Ⅰ与产品Ⅱ在四种设备中所需要的加工台时及的x1，x2非负性可得所谓的约束条件：2132xxz122221xx8221xx1641x1242x01x02x7将该优化模型记为MaxST.2132xxz0,12416482122221212121xxxxxxxx8例2要做100件钢架，每件钢架由长为2.9米，2.1米与1.5米的元钢各一根焊接而成．已知原料长7.4米，应如何下料，使用的原料最省．最简单的做法是在每根原料上截取2.9米，2.1米与1.5米的棒料各一根，这样每根原料剩下0.9米的料头，那么100件钢架需要100根原料，料头累计总长为90米．9现考虑合理套裁，可以节省原料，一般而言，料头长度小于0.9米的套裁方案均可考虑，列表如下下料长度方案ⅠⅡⅢⅣⅤ2.9米1212.1米2211.5米3123合计7.47.37.27.16.6料头00.10.20.30.810为了得到100件钢架，需要混合使用各种下料方案，记按第Ⅰ方案下料的原料根数为x1、方案Ⅱ为x2、方案Ⅲ为x3、方案Ⅳ为x4、方案Ⅴ为x5，以z表示料头累计总长，则建立优化模型如下MinST.54328.03.02.01.0xxxxz0,,,,100323100221002543215321543421xxxxxxxxxxxxxxx113-1-2二维决策变量的图解法对二维决策变量的线性规划模型，可用图解法求解，既简单又直观，这种解法在高中数学课程中已有涉及，下面以例1为例求解如下：121314区域OQ1Q2Q3Q4中的每一个点(x1,x2)包括边界点都是该线性规划问题的一个解，称为可行解，因而凸多边形区域OQ1Q2Q3Q4又称为该线性规划问题的可行域．151617这说明该工厂的最优生产计划方案是：在计划期内生产产品4件，产品2件，可得到最大利润为14（百元）．18根据约束条件所确定的可行域还可能有如下几种情形：•可行域是空集，这表明该问题的约束条件不相容，问题不可行；•可行域非空但无界，此时无最优解，这种情况往往属于约束条件分析不全面所至；•在上图中，如果直线Q2Q3平行于直线束则线段Q2Q3上所有点均是最优解．33212zxx19图解法虽然直观、简便，但在决策变量大于等于3，即在高维的情况下，图解法是无能为力的．运筹学中基于迭代的单纯形法是专门解决线性规划问题的一般方法，但算法较为复杂，这里不作介绍，在下一小节将介绍如何利用专门的规划软件LINGO求解线性规划问题．203-2线性规划模型的LINGO处理3-2-1线性规划模型的LINGO简介美国芝加哥大学的LinusSchrage教授于1980年前后开发了一套专门用于求解最优化问题的软件包，后来又经过了多年的不断完善与扩充，并成立了LINDO系统公司（LINDOSystemsInc.）进行商业化运作，取得了巨大成功．这套软件包的主要产品有四种：LINDO，LINGO，LINDOAPI和What’sBest!．21LINDO是英文LinearInteractiveandDiscreteOptimizer首字母的缩写，即“线性交互式和离散优化求解器”，可以用来解线性规划问题与二次规划问题.LINDO的最终版本是LINDO6.1．22LINGO的主流版本是LINGO9.0，它除了具有LINDO软件的全部功能外，还可用于求解非线性规划问题，包括非线性整数规划问题，所以LINDO系统公司已将LINDO软件从其产品目录中删除，自LINDO6.1后不再提供LINDO的新版本．233-2-2线性规划模型的LINGO的求解举例例1在上一小节例1中，我们建立了如下的线性规划模型MaxST.2132xxz0,12416482122221212121xxxxxxxx24在Windows操作系统下双击LINGO图标或从“开始|程序”菜单中选择LINGO软件运行，启动LINGO软件，程序界面如图所示25上图中最外层的窗口是LINGO软件的主窗口，所有其它窗口都在这个窗口之内．当前光标所在的窗口上标有“LINGOModel–LINGO1”，这就是模型窗口，用于输入LINGO优化模型．26在模型窗口中输入上述优化模型27在输入模型时，应注意以下几点：（1）语句的顺序不重要，目标函数可以出现在约束条件的下方或中间，系统会根据“max=”或“min=”寻找目标函数，但建议按顺序输入模型，保持模型的可读性，必要时可输入惊叹号引导的注释行．（2）每一语句须以分号结束．（3）乘号“*”不能省略，大于等于号写成大于号，小于等于号写成小于号．（4）非负约束是系统约定，不必指明．28执行菜单命令“LINGO|Solve”则得模型状态窗口．29可能由于LINGO软件对中文Windows系统的兼容性不太好，所以图中有些显示字符和单词被截掉了，下面给出部分解释．30在SolverStatus框中“ModelLP”表示模型是线性模型“StateGlobalOpt”表示是全局最优解“Objective10”表示当前解的目标函数值“Iterations1”表示迭代次数．31在Variables框中“Total2”表示模型中变量总数为2“Nonlinear0”表示非线性变量个数为0“Integers0”表示整数变量为0．32在Constraints框中“Total5”表示模型中约束总数为5“Nonlinear0”表示非线性约束个数为0．在Nonzeros框中“Total8”表示模型中非零系数为8“Nonlinear0”表示非线性项的系数个数为0．33在GeneratorMemoryUsed（K）框中显示的内存使用量为16K．在ElapsedRuntime（hh:mm:ss）框中显示的是求解花费的时间，显示为0是因为所花时间太短．34解答报告窗口35在解答报告窗口中，很容易观察得最优解(4,2)及目标函数最优值14.其中“SlackorSurplus”表示松驰或剩余值，如第5行的值为4，表示当决策变量取最优解时，模型中第5行即第四约束中的松驰或剩余值为4，不是紧约束．36例2在上一小节的例2中，我们建立了如下的模型MinST.54328.03.02.01.0xxxxz0,,,,100323100221002543215321543421xxxxxxxxxxxxxxx37启动LINDO，输入模型，如图所示38执行菜单命令“LINGO|Solve”则可得到如图所示的模型状态窗口39解答报告窗口40状态窗口显示，经过3次迭代，求得全局最优解，相应的目标函数值为16，解答报告窗口显示，按Ⅰ方案下料30根，Ⅱ方案下料10根，Ⅳ方案下料50根，共下料90根，可做成100件钢架，并使料头累计最小，最小值为16米．413-2-3在LINGO中使用集合理解LINGO建模语言最重要的是理解集合（set）及其属性（attribute）的概念．什么是集合，下面通过一个简单的例子开始来进行介绍．42例3某公司需要决定下一年度四个季度的生产量．已知下一年度四个季度的订单分别是40件、60件、75件、25件，每个季度的正常的生产的能力是40件，每件产品的生产成本为4000元，如果加班生产，则每件产品的生产成本为4500元．每个季度末，每件产品的库存费用为200元，假定生产提前期为0，初始库存为10件．问如何生产可使总成本最小．43现用dem，rp，op，inv分别表示需求量、正常生产量、加班生产量，库存量，则每一个季度都有一个对应的值，换言之，他们都是一个由4个元素构成的数组，其中dem是已知的，则后三个数组则是未知的．4445该例的集合及其属性详见表集合seasons的元素1234集合seasons的属性demdem（1）dem（2）dem（3）dem（4）rprp（1）rp（2）rp（3）rp（4）opop（1）op（2）op（3）op（4）invinv（1）inv（2）inv（3）inv（4）46该模型的目标函数是约束条件有两个生产能力约束：产品数量平衡约束：非负约束是默认的．4,3,2,1)}(*200)(*4500)(*4000{miniiinviopirp4,3,2,140)(iirp)()()()1()(idemiopirpiinviinv4,3,2,1i10)0(inv47在LINGO中输入上述模型，如图48从图中可以看出，该模型以“model:”开始，以“end”结束，中间由LINGO语句组成，可以分成三个部分.49（1）集合定义部分从“sets:”到“endsets”，用于定义集合及其属性，其中seasons/1,2,3,4/:dem,rp,op,inv定义了前文所说的集合及定义在其上的属性dem，rp，op，inv，也就是定义了16个变量，这16个变量并不都是决策变量，比如dem所对应的四个变量是已知的．50（2）数据输入部分从“data:”到“enddata”，用于输入常量dem的值．51（3）其它部分给出目标函数与约束条件．其中@sum是求和函数，使用格式是：@sum（集合（下标）：关于集合属性的表达式）@for是遍历函数，使用格式是：@for（集合（下标）：关于集合属性的表达式）另外“#gt#”是大于号，“#lt#”是小于号“#eq#”是等于号，“#ne#”是不等于号“#ge#”是大于等于号，“#le#”是小于号52执行命令“LINGO|Solve”，则可得到全局最优解是rp=(40404025)，op=(010350)最小成本是784500元.解答报告窗口见下页5354执行命令LINGO|Generate|DisplyModel得到如图所示完整模型．55最后小结一下LINGO模型的基本组成要素．除了前文提及的集合定义，数据输入，模型主体外，LINGO模型还有初值设定与计算两部分．56（1）集合段（sets）这部分以“sets:”开始，以“endsets”结束，用于定义必要的集合变量（set）及其元素（member）和属性（attribute）．需要指出的是，在例3模型中，如果不是4个季度，而是1000个季度，则可如下定义：seasons/1..1000/:dem,rp,op,inv:57（2）目标与约束段用于定义目标函数与约束条件，这部分没有开始与结束标记，在模型中除了其它四个段外的其余部分都属于这一段．58（3）数据段（data）这部分以“data:”开始，以“enddata”结束，用于输入必要的常数数据，格式为：attribute（属性）=value