LINDO_LINGO应用.ppt

1、暑期基础强化训练：,优化求解软件LINDO/LINGO的应用,陈建华 博士、副教授 TEL.:E-mail: ,Application of LINGO,2,Introduction,应用运筹学处理问题的两个重要特征： 一是从全局的观点出发； 二是通过建立模型如数学模型或模拟模型，对于要求解的问题得到最合理的决策。,如何得到？,工具？,Application of LINGO,3,实际问题中 的优化模型,x决策变量,f(x)目标函数,gi(x)0约束条件,数学规划,线性规划(LP) 二次规划(QP) 非线性规划(NLP),纯整数规划(PIP) 混合整数规划(MIP),

2、整数规划(IP),0-1整数规划 一般整数规划,连续规划,关于优化模型：,Application of LINGO,4,工具软件？,一个LINDO模型至少需要具备三个要素：目标、决策变量和约束条件。 Max 10X + 15Y Subject to X =0,ST(大写或写subject to),不区分大小写,LINDO默认所有变量非负,Application of LINGO,5,输出结果报告：,最优目标函数值,决策变量取值,Application of LINGO,6,1、认识 LINDO/LINGO,LINDO和LINGO是美国LINDO系统公司开发的一套专门用于求解最优化问题的软件包

3、LINDO软件包的特点是程序执行速度快，易于方便的输入、修改、求解和分析一个数学规划(优化问题)。LINDO主要用于求解线性规划（LP）、二次规划、整数规划问题。 LINGO除了具有LINDO的全部功能外，还可以用于求解非线性规划问题（NLP），也可以用于一些线性和非线性方程(组)的求解，等等。 目前版本：lindo6.1 Lingo 9.0。 官方网站： ,Application of LINGO,7,LINGO,LINDO,优化模型,线性规划 (LP),非线性规划 (NLP),二次规划 (QP),连续优化,整数规划(IP),LINDO和LINGO软件能求解的优化模型,Application

4、 of LINGO,8,About LINDO,LINDO (Linear, INteractive, and Discrete Optimizer)是一个解决二次线性整数规划问题的方便而强大的工具。这些问题主要出现在商业、工业、研究和政府等领域。 已被证实LINDO能在其中发挥巨大作用的具体事务包括：产品分销（如运输问题）、生产与个人事务安排、存货管理,Application of LINGO,9,LINDO 界面,模型窗口 Model Window,工具栏,主窗口,Application of LINGO,10,LINDO的三种基本使用模式：,对于一些中小规模的问题，LINDO只要通过键盘

5、输入就可以方便地实现交互性良好的操作与使用，如输入一个模型是相当简单方便的事情。 LINDO也可以对外建文件进行处理，只要这些文件里包含有必要的命令代码和输入数据，处理后就可以生成用于报告目的的文档。 可以自建子程序，然后直接与LINDO相结合形成一个包括你自己的代码和LINDO本身的优化库的综合程序。,Application of LINGO,11,2、LINDO应用：求解线性规划问题（LP）,例1：汽油混合问题,一种汽油的特性可用两个指标描述：其点火性用“辛烷数”描述，其挥发性用“蒸汽压力”描述。某炼油厂有四种标准汽油，设其标号分别为，。其特性及库存量列于下表中，将上述标准汽油适量混合，可

6、得两种飞机汽油，其标号为，。这两种飞机汽油的性能指标及产量需求列于表中。 ？问：应如何根据库存情况适量混合各种标准汽油，使既满足飞机汽油的性能指标，而产量又为最高。,Application of LINGO,12,表1,(1 g/cm2=98Pa),表2,Application of LINGO,13,数学建模：,Objective：max z=x1+x2+x3+x4 S.T.： x5+x6+x7+x8=250000 x1+x5=0 2.85x5-1.42x6+4.27x7-18.49x8=0 16.5x1+2.0 x2-4.0 x3+17x4=0 7.5x5-7.0 x6-13.0 x7+8

7、.0 x8=0 xj=0 (j=1,2.,8),Application of LINGO,14,LINDO求解过程：,运行求解,Application of LINGO,15,输出结果：,Application of LINGO,16,Notes：,目标函数及各约束条件之间要用Subject to (ST) 分开 变量名以字母开头，不能超过个字符 变量名不区分大小写（包括LINDO中的关键字） 变量与其系数间可以有空格（甚至回车），但不能有任何运算符号（如乘号“”等） 要输入=约束，相应以代替即可 目标函数所在行是第一行，第二行起为约束条件 一般LINDO中不能接受括号“（）“和逗号“，”。例

8、：400(X1+X2) 需写成400X1+400X2；10,000需写成10000 表达式应当经过简化。不能出现 2X1+3X2-4X1，而应写成 -2X1+3X2,Application of LINGO,17,Notes：,行中注有“!”符号的后面部分为注释。如: ! Its Comment. 在模型的任何地方都可以用“TITLE” 对模型命名（最多72个字符），如： 缺省假定所有变量非负；可在模型的“END”语句后用“FREE name”将变量name的非负假定取消 TITLE This Model is only an Example 可在“END”后用“SUB”或“SLB”设定变量上

9、下界 例如：“sub x1 10”的作用等价于“x1=10”。但用“SUB”和“SLB”表示的上下界约束不计入模型的约束，也不能给出其松紧判断和敏感性分析。 “END”后对0-1变量说明：INT n 或 INT name “END”后对整数变量说明：GIN n 或 GIN name,Application of LINGO,18,2、LINDO应用：求解整数规划问题（IP）,例2：指派问题,有四个工人，要分别指派他们完成四项不同的工作，每个人做各项工作所消耗的时间如表。问应该如何指派，才能使总的消耗时间为最小？,Application of LINGO,19,建模及LINDO求解过程：,Xij

10、：工人i负责工作j，0-1变量 注意到每人只能做一项工作，每项工作一人做。,在用LINDO解整数规划（IP）问题时，只要在END后加上标识即可，其中解0-1规划的用命令： INT name 或 INT n (n 指前n 个变量标识为0-1型)解混合型整数规划则用GIN来标识。,Application of LINGO,20,输出结果：,Application of LINGO,21,2、LINDO应用：求解二次规划问题（QP）,例3：,LINDO虽亦可求解二次规划问题。（但它在输入时不如用LINGO方便，用LINDO输入时要先作偏导数计算不如LINGO那样可直接输入。 min f(x)=(x1

11、-1)2+(x2-2)2 x2-x1=1 x1+x2=0,x2=0,建议用LINGO求解二次规划问题,Application of LINGO,22,3、LINGO应用,状态栏,工具栏,模型窗口 Model Window,主窗口,Application of LINGO,23,从LINDO到LINGO的转化实质：,1）将目标函数的表达式从 MAX 变成了 MAX= 2）ST在LINGO中不再需要 3）在每个系数与变量之间增加了运算符* 4）每行(目标、约束和说明语句)后面增加了一个分; 5）约束的名字被放到了一对方括号 中，而不是放在右半括号之前 6）LINGO中模型以MODEL:开始，以EN

12、D结束，对简单的模型，这两个语句也可以省略,Application of LINGO,24,Lingo语言：,需要根据优化模型的简单或复杂的情况，选用两种语言之一来进行描述和求解： 标量语言：十分贴近数学语言，符合人们的习惯，简单易学。适用于输入量较小的小型优化问题。 集合语言：适用于输入量较大的大型优化问题。,LINGO标量语言,求解小型优化问题举例,Application of LINGO,26,Lingo标量语言：语法规则,（1）在Lingo中输入的英文字母不区分大小写。 （2）变量名均以字母开头，不能超过32个字符。 （3）每条语句（包括注释语句）都以分号“;”结束。 （4）自变量非负

13、约束x0不必输入，系统默认所有变量非负；但如果x为自由变量，则必须用“free(x);”申明。 （5）Lingo中的注释语句：语法是“!注释内容;”。 （6）约束中的与号，可分别用与号代替。 （7）函数名均以开头。常用函数表 （8）每行允许写多条语句，但最好一行一条语句，以增强程序的可读性。,Application of LINGO,27,Lingo中的运算符：,（1）算术运算符：+（加法）、-（减法或负号）、*（乘法）、/（除法）、（乘方） （2）关系运算符：（小于等于，即）、=（等于）、（大于等于，即） （3）逻辑运算符：#OR#（逻辑或）、#AND#（逻辑与）、#NOT#（逻辑非）,Ap

14、plication of LINGO,28,Lingo常用函数：,Application of LINGO,29,标量语言描述方法举例：,Application of LINGO,30,例2：求解非线性规划,例1：求解线性规划,Application of LINGO,31,最优目标函数值,迭代次数,决策变量值,Application of LINGO,32,Application of LINGO,33,例4：求解无约束非线性规划,例3：求解二次规划,Application of LINGO,34,例6：求解线性整数规划,例5：求解有约束非线性规划,Application of LINGO,

15、35,例7：求解线性混合整数规划,例8：求解0-1规划,Application of LINGO,36,例9：求解分段函数的优化问题,IF函数语法规则：IF(logical_condition,true_result,false_result);,Application of LINGO,37,LINGO应用：求解二次规划问题（QP）,例：产量问题,某厂生产的一种产品有甲、乙两个品牌，讨论在产销平衡的情况下如何确定各自的产量，使总的利润最大。所谓产销平衡指工厂的产量等于市场上的销量，没有卖不出去的产品的情况。显然，销售总利润既取决于两种产品的销量和（单件）价格，也依赖于产量和（单件）成本，按照

16、市场经济规律，甲的价格p1固然会随其销量x1的增长而降低，同时乙的销量x2的增长也会使甲的价格有稍微的下降，可以简单地假设价格与销量成线性关系，即p1=b1a11x1a12x2，b1,a11,a120，a11a12；类似地，乙的价格p2遵循同样的规律，即有p2=b2a21x1a22x2，b2,a21,a220，a22a21.例如，假定实际中b1=100，a11=1，a12=0.1，b2=280；a21=0.2，a22=2。此外，假设工厂的生产能力有限，两种牌号产品的产量之和不可能超过100件，且甲的产量不可能超过乙的产量的两倍，甲乙的单件生产成本分别是q1=2和q2=3(假定为常数)。求甲、乙

17、的产量 x1，x2使总利润最大。,Application of LINGO,38,决策变量：甲、乙的产量（也是销量）x1，x2 目标函数：总利润z(x1，x2)，即 z(x1，x2)（p1-q1）x1（p2-q2）x2 （100-x1-0.1x2-）x1（280-0.2x1-2x2-3）x2 98 x1+277 x2-x12-0.3 x1 x2-2x22 约束条件：题中假设工厂的生产能力有限，两种产品的产量之和不可能超过100件，且产品甲的产量不可能超过乙的产量的两倍。写成数学表达式，就是 x1x2100, x12x2,优化模型：,Application of LINGO,39,求解过程：,L

18、INGO中的变量名由字母和数字组成，但必须以字母开头，长度不能超过32个字符（只能是英文字符，不能含有中文字符） 行号、“TITLE”语句和注释语句是LINGO中唯一可以使用汉字字符的地方行号必须以字母或下划线开头； LINGO中不区分大小写字母 LINGO中已假定所有变量非负,Application of LINGO,40,通过“LINGO | Generate | Display Model (Ctrl +G)”命令可以看到完整的模型以及每行语句对应的行号了。,Application of LINGO,41,输出结果：,LINGO集合语言（后期自学）,求解大型优化问题举例,Applicat

19、ion of LINGO,43,LINGO语言描述与运算的主要对象： 向量 矩阵 需要在使用前对向量、矩阵等集合进行定义,Application of LINGO,44,Lingo集合语言规则：,使用Lingo集合语言描述优化模型时，必须从MODEL开始，以END结束。通常包括4部分： （1）集合部分：以“SETS”开始，以“ENDSETS”结束。作用在于定义集合及其元素和属性。 （2）数据部分：以“DATA”开始，以“ENDDATA”结束。作用在于给出模型中的数据，主要是向量和矩阵的元素。 （3）目标函数和约束部分：作用在于给出目标函数和约束条件，可充分利用Lingo的内部函数来生成。 （4

20、）初始化部分：以“INIT”开始，以“ENDINIT”结束，作用在于给出非线性规划中的初始条件。,Application of LINGO,45,Lingo集合部分,基本格式： SETS: setname (parent_set_list)member_list/:attribute_list; ENDSETS,例如：要定义三个4维向量c,x,b,一个34阶矩阵A。 SETS: vector/1.4/:c, x, b row/1.3/; col/1.4/; matrix (row, col) A; ENDSETS,Application of LINGO,46,Lingo目标函数和约束部分,使

21、用方法： function (setname(set_index_list)|conditional_qualifier: expression_list);,Lingo集合语言中的主要函数： For 循环函数（通常用来描述约束条件） Sum 求和函数 Prod 求积函数 min 最小分量函数 max 最大分量函数,Application of LINGO,47,Lingo集合语言描述举例：,例10：将下面线性规划用集合语言描述并求解。,Application of LINGO,48,1）将上面线性规划的坐标形式改写成矩阵形式，有：,Application of LINGO,49,2）Ling

22、o集合语言描述：,model: !程序开始； sets: !集合定义开始；,Application of LINGO,50,Application of LINGO,51,LINGO应用：集合语言,例1：生产产量安排问题,SAILCO公司需要决定下四个季度的帆船生产量。下四个季度的帆船需求量分别是40条，60条，75条，25条，这些需求必须按时满足。每个季度正常的生产能力是40条帆船，每条船的生产费用为400美元。如果加班生产，每条船的生产费用为450美元。每个季度末，每条船的库存费用为20美元，假定生产提前期为0，初始库存为10条船。如何安排生产可使总费用最小？,Application of

23、 LINGO,52,约束条件： 能力限制 RP(I)40，I=1，2，3，4 产品数量的平衡方程 INV（I）INV（I1）RP（I）OP（I）DEM（I） ， INV（0） 10； 变量的非负约束,DEM需求量，RP正常生产的产量，OP加班生产的产量，INV库存量 目标函数：,Application of LINGO,53,Lingo优化模型,集合,属性,集合的属性相当于以集合的元素为下标的数组,Application of LINGO,54,（1）集合段（SETS） （2）目标与约束段 （3）数据段（DATA）：作用在于对集合的属性（数 组）输入必要的常数数据。格式为： attribute

24、(属性)=value _list(常数列表); 常数列表（value _list）中数据之间可以用逗号“,”分开，也可以用空格分开（回车的作用也等价于一个空格） “变量名=?;” 运行时赋值 （4）初始段（INIT）赋初值 （5）计算段（CALC）预处理,Lingo模型的基本要素,Application of LINGO,55,LINGO应用：集合语言,例2：生产产量安排问题,建筑工地的位置（用平面坐标a，b表示，距离单位：km）及水泥日用量d（单位：t）如下表。目前有两个临时料场位于P（5，1），Q（2，7），日储量各有20t，求从A，B两料场分别向各工地运送多少吨水泥，使总的吨公里数最小。

25、两个新的料场应建在何处，节省的吨公里数有多大？,工地的位置（a，b）及水泥日用量d,Application of LINGO,56,记工地的位置为（ai，bi），水泥日用量为di，i=1,2,6；料场位置为（xj，yj），日储量为ej，j=1,2；从料场j向工地i的运送量为cij。 决策变量：在问题（1）中，决策变量就是料场j向工地i的运送量cij，该问题是个LP问题；在问题（2）中，决策变量除了料场j向工地i的运送量cij，新建料场位置（xj，yj）也是决策变量，该问题是个NLP问题。 目标函数：f是总吨公里数（运量乘以运输距离）,优化模型：,Application of LINGO,57,约束条件： 各工地的日用量必须满足，所以 各料场的运送量不能超过日储量，所以 Cij非负,Application of LINGO,58,该问题的数学规划模型是：,Application of LINGO,59,demand，supply：这种直接把元素列