《优化模型与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