《第三章线性规划及LINGO求解课件》由会员分享，可在线阅读，更多相关《第三章线性规划及LINGO求解课件（73页珍藏版）》请在金锄头文库上搜索。
1、1,第三章 线性规划及LINGO求解,在工程技术、经济管理、科学研究和日常生活等诸多领域，人们常常遇到这样的问题，就是在一系列客观或主观条件的限制之下，寻求使所关注的某个指标达到最大或最小，这类决策问题通常称为优化建模或最优化问题解决最优化问题的一般方法是建立优化模型、求解最优决策,2,一般地，优化模型包括目标函数与约束条件当目标函数与约束条件中出现的解析表达式均为线性表达式时，则称之为线性规划(LP) 本章主要内容是线性规划模型的建立、二维决策变量情形下的图象解法以及较复杂线性规划模型的LINGO求解,3,3-1 线性规划模型的建立 及二维决策变量的图解3-1-1 线性规划模型的建立,例1
2、某工厂在计划期内要安排生产、两种产品，这两种产品分别需要在A、B、C、D四种不同的设备上加工按工艺设计要求，产品与产品在四种设备中所需要的加工台时（一台设备工作一小时称为一台时）见后表，,4,5,已知设备A、B、C、D在计划期内有效台时分别是12、8、16、12，产品与产品的单位利润分别是2、3（单位：百元）问如何安排生产，才能使利润最大？,6,假设x1，x2分别表示在计划期内产品与产品的产量，z表示所获得的利润，则有 这就是目标函数根据设备A、B、C、D在计划期内有效台时、产品与产品在四种设备中所需要的加工台时及的x1，x2非负性可得所谓的约束条件：,7,将该优化模型记为 Max ST.,8
3、,例2 要做100件钢架，每件钢架由长为2.9米，2.1米与1.5米的元钢各一根焊接而成已知原料长7.4米，应如何下料，使用的原料最省 最简单的做法是在每根原料上截取2.9米，2.1米与1.5米的棒料各一根，这样每根原料剩下0.9米的料头，那么100件钢架需要100根原料，料头累计总长为90米,9,现考虑合理套裁，可以节省原料，一般而言，料头长度小于0.9米的套裁方案均可考虑，列表如下,10,为了得到100件钢架，需要混合使用各种下料方案，记按第方案下料的原料根数为x1、方案为x2、方案为x3、方案为x4、方案为x5，以z表示料头累计总长，则建立优化模型如下 Min ST.,11,3-1-2
4、二维决策变量的图解法,对二维决策变量的线性规划模型，可用图解法求解，既简单又直观，这种解法在高中数学课程中已有涉及，下面以例1为例求解如下：,12,13,14,区域OQ1Q2Q3 Q4中的每一个点 (x1,x2) 包括边界点都是该线性规划问题的一个解，称为可行解，因而凸多边形区域 OQ1Q2Q3 Q4 又称为该线性规划问题的可行域,15,16,17,这说明该工厂的最优生产计划方案是：在计划期内生产产品4件，产品2件，可得到最大利润为14（百元）,18,根据约束条件所确定的可行域还可能有如下几种情形： 可行域是空集，这表明该问题的约束条件不相容，问题不可行； 可行域非空但无界，此时无最优解，这种
5、情况往往属于约束条件分析不全面所至； 在上图中，如果直线Q2Q3平行于直线束 则线段Q2Q3上所有点均是最优解,19,图解法虽然直观、简便，但在决策变量大于等于3，即在高维的情况下，图解法是无能为力的运筹学中基于迭代的单纯形法是专门解决线性规划问题的一般方法，但算法较为复杂，这里不作介绍，在下一小节将介绍如何利用专门的规划软件LINGO求解线性规划问题,20,3-2 线性规划模型的LINGO处理3-2-1线性规划模型的LINGO简介,美国芝加哥大学的Linus Schrage教授于1980年前后开发了一套专门用于求解最优化问题的软件包，后来又经过了多年的不断完善与扩充，并成立了LINDO系统公
6、司（LINDO Systems Inc.）进行商业化运作，取得了巨大成功这套软件包的主要产品有四种：LINDO，LINGO，LINDO API和Whats Best!,21,LINDO是英文 Linear Interactive and Discrete Optimizer 首字母的缩写，即“线性交互式和离散优化求解器”，可以用来解线性规划问题与二次规划问题. LINDO的最终版本是LINDO6.1,22,LINGO的主流版本是LINGO9.0，它除了具有LINDO软件的全部功能外，还可用于求解非线性规划问题，包括非线性整数规划问题，所以LINDO系统公司已将LINDO软件从其产品目录中删除，
7、自LINDO6.1后不再提供LINDO的新版本,23,3-2-2线性规划模型的LINGO的求解举例,例1 在上一小节例1 中，我们建立了如下的线性规划模型 Max ST.,24,在Windows操作系统下双击LINGO图标或从“开始|程序”菜单中选择LINGO软件运行，启动LINGO软件，程序界面如图所示,25,上图中最外层的窗口是LINGO软件的主窗口，所有其它窗口都在这个窗口之内当前光标所在的窗口上标有“LINGO Model LINGO1”，这就是模型窗口，用于输入LINGO优化模型,26,在模型窗口中输入上述优化模型,27,在输入模型时，应注意以下几点： （1）语句的顺序不重要，目标函
8、数可以出现在约束条件的下方或中间，系统会根据“max=”或“min=”寻找目标函数，但建议按顺序输入模型，保持模型的可读性，必要时可输入惊叹号引导的注释行 （2）每一语句须以分号结束 （3）乘号“*”不能省略，大于等于号写成大于号，小于等于号写成小于号 （4）非负约束是系统约定，不必指明,28,执行菜单命令“LINGO|Solve”则得模型状态窗口,29,可能由于LINGO软件对中文Windows系统的兼容性不太好，所以图中有些显示字符和单词被截掉了，下面给出部分解释,30,在Solver Status框中 “Model LP”表示模型是线性模型 “State Global Opt”表示是全局
9、最优解 “Objective 10”表示当前解的目标函数值 “Iterations 1”表示迭代次数,31,在Variables框中 “Total 2”表示模型中变量总数为2 “Nonlinear 0”表示非线性变量个数为0 “Integers 0”表示整数变量为0,32,在Constraints框中 “Total 5”表示模型中约束总数为5 “Nonlinear 0”表示非线性约束个数为0 在Nonzeros框中 “Total 8”表示模型中非零系数为8 “Nonlinear 0”表示非线性项的系数个数为0,33,在Generator Memory Used（K）框中显示的内存使用量为16K
10、 在Elapsed Runtime（hh:mm:ss）框中显示的是求解花费的时间，显示为0是因为所花时间太短,34,解答报告窗口,35,在解答报告窗口中，很容易观察得最优解(4,2)及目标函数最优值14. 其中“Slack or Surplus”表示松驰或剩余值，如第5行的值为4，表示当决策变量取最优解时，模型中第5行即第四约束中的松驰或剩余值为4，不是紧约束,36,例2 在上一小节的例2中，我们建立了如下的模型 Min ST.,37,启动LINDO，输入模型，如图所示,38,执行菜单命令“LINGO|Solve”则可得到如图所示的模型状态窗口,39,解答报告窗口,40,状态窗口显示，经过3次
11、迭代，求得全局最优解，相应的目标函数值为16，解答报告窗口显示，按方案下料30根，方案下料10根，方案下料50根，共下料90根，可做成100件钢架，并使料头累计最小，最小值为16米,41,3-2-3 在LINGO中使用集合,理解LINGO建模语言最重要的是理解集合（set）及其属性（attribute）的概念什么是集合，下面通过一个简单的例子开始来进行介绍,42,例3 某公司需要决定下一年度四个季度的生产量已知下一年度四个季度的订单分别是40件、60件、75件、25件，每个季度的正常的生产的能力是40件，每件产品的生产成本为4000元，如果加班生产，则每件产品的生产成本为4500元每个季度末，
12、每件产品的库存费用为200元，假定生产提前期为0，初始库存为10件问如何生产可使总成本最小,43,现用dem，rp，op，inv分别表示需求量、正常生产量、加班生产量，库存量，则每一个季度都有一个对应的值，换言之，他们都是一个由4个元素构成的数组，其中dem是已知的，则后三个数组则是未知的,44,45,该例的集合及其属性详见表,46,该模型的目标函数是 约束条件有两个 生产能力约束： 产品数量平衡约束： 非负约束是默认的,47,在LINGO中输入上述模型，如图,48,从图中可以看出，该模型以“model:”开始，以“end”结束，中间由LINGO语句组成，可以分成三个部分.,49,（1）集合定
13、义部分 从“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#
14、”是大于号， “#lt#”是小于号 “#eq#”是等于号， “#ne#”是不等于号 “#ge#”是大于等于号， “#le#”是小于号,52,执行命令“LINGO|Solve”，则可得到全局最优解是 rp = ( 40 40 40 25 ) ，op = ( 0 10 35 0 ) 最小成本是784500元. 解答报告窗口见下页,53,54,执行命令 LINGO|Generate|Disply Model 得到如图所示完整模型,55,最后小结一下LINGO模型的基本组成要素除了前文提及的集合定义，数据输入，模型主体外，LINGO模型还有初值设定与计算两部分,56,（1）集合段（sets） 这部分以
15、“sets:”开始，以“endsets”结束，用于定义必要的集合变量（set）及其元素（member）和属性（attribute）需要指出的是，在例3模型中，如果不是4个季度，而是1000个季度，则可如下定义： seasons/ 1.1000/:dem,rp,op,inv:,57,（2）目标与约束段 用于定义目标函数与约束条件，这部分没有开始与结束标记，在模型中除了其它四个段外的其余部分都属于这一段,58,（3）数据段（data） 这部分以“data:”开始，以“enddata”结束，用于输入必要的常数数据，格式为： attribute（属性）= value_list（常数列表） 如上例中的
16、dem=40,60,75,25;,59,（4）初始段（init） 以“init:”开始，以“endinit”结束，用于给集合的属性定义初值因为求解算法一般是迭代算法，对规模较大的问题，如果有一个接近最优解的初值，求模型的求解是有帮助的,60,（5）计算段（calc） 以“calc:”开始，以“endcalc”结束，用于对原始数据作初步的计算处理,61,3-3 派生集合 非线性规划模型简介,本小节主要通过一个实例，简单介绍一下LINGO的派生集合和非线性规划，有关优化模型的其它问题，请参考有关资料，因为篇幅所限，这里不再过多涉及,62,例1 现有6个工场的位置（用平面坐标a，b表示，距离单位：km）及原料日需量d（单位：t）由下表给出,63,现建两个最大日供量均为20t的原料供应地，向6个工场运送原料，问如何选址与
