《优化模型与LINDOLINGO优化软件研究报告》由会员分享，可在线阅读，更多相关《优化模型与LINDOLINGO优化软件研究报告（68页珍藏版）》请在金锄头文库上搜索。
1、优化模型与LINDO/LINGO优化软件,温罗生 重庆大学数理学院 Tel:13594173719 Email:,1，从Lindo到Lingo,线性规划是优化方法中最基本，也是最重要的方法，最根本的原因是模型的规范性以及求解的高效率。其最基本的形式如下：,当问题比较简单是，利用Lindo可以方便的求解。比如下面的问题 max 2x1+3x2 s.t. x1+x2 2 x1-2x21/2 x1,x2非负 按照Lindo的语法，写成 max 2x1+3x2 s.t. x1+x2 2 x1-2x21/2 end,更多的例子可以参见程序部分,使用LINDO的一些注意事项,“”（或“=”（或“=”）功能
2、相同 变量与系数间可有空格(甚至回车), 但无运算符 变量名以字母开头，不能超过8个字符 变量名不区分大小写（包括LINDO中的关键字） 目标函数所在行是第一行，第二行起为约束条件 行号(行名)自动产生或人为定义。行名以“）”结束 行中注有“!”符号的后面部分为注释。如: ! Its Comment. 在模型的任何地方都可以用“TITLE” 对模型命名（最多72个字符），如： TITLE This Model is only an Example,状态窗口（LINDO Solver Status）,当前状态：已达最优解 迭代次数：18次 约束不满足的“量”(不是“约束个数”)：0 当前的目标值
3、：94 最好的整数解：94 整数规划的界：93.5 分枝数：1 所用时间：0.00秒（太快了，还不到0.005秒） 刷新本界面的间隔:1(秒),选项设置,Preprocess：预处理(生成割平面)； Preferred Branch：优先的分枝方式： “Default”（缺省方式）、 “Up”（向上取整优先）、 “Down”（向下取整优先）； IP Optimality Tol：IP最优值允许的误差上限（一个百分数，如5%即0.05）； IP Objective Hurdle：IP目标函数的篱笆值，即只寻找比这个值更优最优解（如当知道当前模型的某个整数可行解时，就可以设置这个值）； IP Va
4、r Fixing Tol：固定一个整数变量取值所依据的一个上限（如果一个整数变量的判别数（REDUCED COST）的值很大，超过该上限，则以后求解中把该整数变量固定下来）。,Nonzero Limit： 非零系数的个数上限； Iteration Limit： 最大迭代步数； Initial Contraint Tol： 约束的初始误差上限； Final Contraint Tol： 约束的最后误差上限； Entering Var Tol： 进基变量的REDUCED COST的误差限； Pivot Size Tol： 旋转元的误差限,Report/Statistics,第一行：模型有5行（约束
5、4行），4个变量，两个整数变量（没有0-1变量），从第4行开始是二次规划的实际约束。 第二行：非零系数19个，约束中非零系数12个(其中6个为1或-1)，模型密度为0.760(密度=非零系数/行数(变量数) 。 第三行的意思：按绝对值看，系数最小、最大分别为0.3和277。 第四行的意思：模型目标为极小化；小于等于、等于、大于等于约束分别有、个；广义上界约束（GUBS）不超过个；变量上界约束（VUBS）不少于个。所谓GUBS，是指一组不含有相同变量的约束；所谓VUBS，是指一个蕴涵变量上界的约束，如从约束X1+X2-X3=0可以看出，若X3=0，则X1=0，X2=0（因为有非负限制），因此X1
6、+X2-X3=0是一个VUBS约束。 第五行的意思：只含个变量的约束个数=个；冗余的列数=个,ROWS= 5 VARS= 4 INTEGER VARS= 2( 0 = 0/1) QCP= 4 NONZEROS= 19 CONSTRAINT NONZ= 12( 6 = +-1) DENSITY=0.760 SMALLEST AND LARGEST ELEMENTS IN ABSOLUTE VALUE= 0.300000 277.000 OBJ=MIN, NO. : 2 0 2, GUBS = 0 SINGLE COLS= 0 REDUNDANT COLS= 0,但是当问题的规模扩大时，前面的方法
7、显得非常不方便甚至是致命的。主要的原因是所含的变量和约束个数太多。另一方面，规划问题本身很有规律，所以我们希望使用循环来实现。引入如下的两个数组（或者向量）， C=(c1,c2,cn), X=(x1,x2,xn), b=(b1,b2,bm)，,我们可以得到下面的对应关系,c1x2+c2x2+cnxn,s=0 for i=1:n s=s+c(i)*x(i) end,a11x1+a12x2+a1nxnb1 a21x1+a22x2+a2nxnb2 。 。 am1x1+am2x2+amnxnbm,for i=1:m for j=1:n s(i)=s(i)+a(i,j)*x(j) end s(i)b(i
8、) end,右边是程序语言的一个比喻写法，为实现循环结构，Lingo中引入了几个循环语句：for(),sum(),min(),max.,为此，需要定义一个数组（向量）的结构，在Lindo中称之为集合。表征数组的维数的量在循环中有非常重要的作用。在Lindo中如下定义数组。 sets: setname/下标起数.下标止数/:数组名； endsets 比如，要实现前面例子的目标函数部分，只要写如下的代码： 集合段部分： sets: cargo/1.2/:c,x; endsets 目标函数段： max=sum(cargo(i):c(i)*x(i); 其中i为循环变量，cargo指出循环变量变化的范围
9、。,对于约束，可以类似的处理如下： 集合部分： sets: cargo/1.n/:c,x,a1,a2,am; rhs/1.m/:b; endsets 程序部分： sum(cargo(i):a1(i)*x(i)b(1); sum(cargo(i):a2(i)*x(i)b(2); sum(cargo(i):am(i)*x(i)b(m);,可以看到，当m的值比较大时，书写还是感到麻烦，所有，可以考虑在利用循环实现。 要实现二重循环，并且其中可以将系数作出一个矩阵（二维数组），所有定义,这是矩阵A的行列数是m和n,可以看成由向量X和b派生。,于是为得到约束条件，可以如下的定义集合段和约束部分。 集合部
10、分： sets: cargo/1.n/:c,x; rhs/1.m/:b; mat(rhs,cargo):a; endsets 程序部分： for(rhs(j):sum(cargo(i):a(j,i)*x(i)b(j);,j为循环变量，rhs指出需要循环的次数。,从上面的例子大家看出引入集合的作用以及基本的用法，下面的部分给出Lingo的整体结构和更复杂的例子。,2，Lingo程序的结构和语法,一个规划问题，包括下面的一些内容：变量、常量、目标、约束。还是以前面的例子，说明最基本的程序构成。 model: linear programming sets: cargo/1.n/:c,x; rhs/
11、1.m/:b; mat(rhs,cargo):a; endsets data c=2,3; b=2,1/2; A=1,1,1,-2; enddata max=sum(cargo(i):c(i)*x(i); for(rhs(j):sum(cargo(i):a(j,i)*x(i)b(j);,前面是两个循环语句的用法，函数以“”开头，里面是循环变量以及界定循环变量的变化范围，后面是循环体。还有另外的两个循环函数：min和max，其用法相类似。 从一维数组派生二维数组在数学上是常用的，比如运输问题，由顶点集可以派生边，大家可以使用本方法产生标准的运输问题的Lingo程序。可以参考例子。,LINGO模型
12、 例：选址问题,某公司有6个建筑工地，位置坐标为(ai, bi) (单位：公里),水泥日用量di (单位：吨）,假设：料场和工地之间有直线道路,用例中数据计算，最优解为,总吨公里数为136.2,线性规划模型,决策变量：ci j (料场j到工地i的运量）12维,选址问题：NLP,2）改建两个新料场，需要确定新料场位置(xj,yj)和运量cij ，在其它条件不变下使总吨公里数最小。,决策变量： ci j，(xj,yj)16维,非线性规划模型,location,LINGO模型的构成：4个段,集合段（SETS ENDSETS）,数据段（DATA ENDDATA）,初始段（INIT ENDINIT）,目
13、标与 约束段,局部最优：89.8835(吨公里 ),LP：移到数据段,边界,上面讲到图的问题，但是实际中的图往往是稀疏图，这样的问题尽管可以用前面的方法处理，但是计算量往往非常的大，是不实际的。下面讲由顶点集派生边集的例子。,前图是有九个顶点组成的图，连线代表顶点之间的边，其上的数字代表边的长度。要求得到所有顶点到顶点T的最短距离。分析Lingo程序。 从这个例子得到的知识有：顶点的编号；产生边集（稀疏图）；动态规划的思想；循环语句的使用。 程序中出现了“i #GT# 1:”在循环语句中，这实际上是常见的，也就是我们希望对满足条件的执行循环，否则不执行，称之为逻辑语句。,运算符的优先级,三类运
14、算符： 算术运算符 逻辑运算符 关系运算符,匹配问题的例子（说明逻辑运算符） 某班8名同学准备分成4个调查队（每队两人）前往四个地区进行社会调查，假设这8位同学两两之间组队的效率如表所示（由于对称性，只列出严格上三角部分），问如何组队可以使总效率最高？,将效率矩阵记为benefit,用match(si,sj)=1表示同学si和同学sj组成一个队，而match(si,sj)=0表示不组队，由对称性，只考虑ij共28个01变量。 目标函数为：benefit(si,sj)*match(si,sj)对I,j求和；约束条件为每个同学只能在某一组。得到规划问题：,ABS( X) This returns
15、the absolute value of X. COS( X) This returns the cosine of X, where X is an angle in radians. EXP( X) This returns e (2.718281.) raised to the power X. FLOOR( X) This returns the integer part of X. To be specific, if X ?0, FLOOR returns the largest integer, I, such that I ?X. If X is negative, FLOOR returns the most negative integer, I, such that I ?X. LGM( X) This returns the natural (base e) logarithm of the gamma function of X (i.e., log of (X - 1)!). It is extended to noninteger values of X by linear interpolation. LOG( X) This returns the natural loga
