lingo编程学习.doc

启航系列之数学建模培训资料专题2：Lingo编程介绍Lingo产品介绍Lindo 和 Lingo 是美国 Lindo 系统公司开发的一套专门用于求解最优化问题的软件包。Lindo 用于求解线性规划和二次规划问题,Lingo 除了具有 Lindo 的全部功能外,还可以用于求解非线性规划问题,也可以用于一些线性和非线性方程(组)的求解,等等。Lindo 和 Lingo 软件的最大特色在于可以允许优化模型中的决策变量是整数（即整数规划）,而且执行速度很快。 Lingo 实际上还是最优化问题的一种建模语言,包括许多常用的函数可供使用者建立优化模型时调用,并提供与其他数据文件（如文本文件、Excel电子表格文件、数据库文件等）的接口,易于方便地输入、求解和分析大规模最优化问题。由于这些特点,Lindo系统公司的线性、非线性和整数规划求解程序已经被全世界数千万的公司用来做最大化利润和最小化成本的分析。应用的范围包含生产线规划、运输、财务金融、投资分配、资本预算、混合排程、库存管理、资源配置等等. Lindo/Lingo 软件作为著名的专业优化软件，其功能比较强、计算效果比较好，与那些包含部分优化功能的非专业软件相比，通常具有明显的优势。此外，Lindo/Lingo 软件使用起来非常简便，很容易学会，在优化软件（尤其是运行于个人电脑上的优化软件）市场占有很大份额，在国外运筹学类的教科书中也被广泛用做教学软件。Lingo的程序规范1. Lingo能求解的优化模型优化模型连续优化整数规划优化模型二次规划非线性规划2. 编写一个简单的lingo程序例1 用Lingo解决一个二次规划问题解：在lingo命令行中输入如下代码，x1+x2=100;!一个简单例子;max=98*x1+277*X2-x1*x1-0.3*X1*x2-2*X2*x2;x1-2*x2=0;gin(x1);gin(x2);按求解键得到结果如下， Global optimal solution found. Objective value: 11077.50 Extended solver steps: 0 Total solver iterations: 44 Variable Value Reduced Cost X1 35.00000 -8.500002 X2 65.00000 -6.500004在这个例子里要注意如下一些细节：每一行语句结尾要有分号;注释行以!号开头，;号结尾Lingo中的变量不区分字母大小写系数和变量之间要有运算符相连“max=”或“min=”表示目标函数Lingo的语句顺序并不重要以开头的语句表示调用Lingo自带的函数，本例中gin(x1)表示x1为整数Lingo中以默认了所有变量都非负对本例结果的解释:找到全局最优解，使得目标函数值为，对应变量，的值分别为和，对应变量，的影子价格分别为，。所谓的影子价格，就是指对应的变量增加1单位，其他变量无变化时目标函数改变的单位数。3. 建立Lingo优化模型需要注意的几个基本问题(1)、尽量使用实数优化模型，尽量减少整数变量和整数约束；(2)、尽量使用光滑优化模型，尽量避免使用非光滑函数。比如应尽量避免使用绝对值函数，符号函数，求最大最小值函数，取整函数等；(3)、尽量使用线性优化模型，尽量减少非线性约束和非线性变量的个数；(4)、合理设定变量的上下界，尽可能给出变量的初始值；(5)、模型中使用的单位的数量级要适当。系数最大数和最小数的绝对值超过1000倍以上会弹出警告信息。4. 在Lingo中使用集合4.1 集合的基本用法和lingo模型的基本要素Lingo虽然使用方便，但是如果要解决几万个，几十万个变量的优化问题时，我们总不能一个一个地列出x1,x2,x1000来解决，而这样的问题在实际企业的应用中也是经常遇到的。好在Lingo中设计了集合语言来表示大规模变量的输入，只需一行文字就可以建立起含有大规模变量的目标函数和成千上万条约束。而Lingo的早期版本软件Lindo却不包含这样的功能。现通过下例来对Lingo的集合、属性概念进行介绍。例2 SAILCO公司需要决定决定下四个季度的帆船生产量。下四个季度的帆船需求量分别为40条，60条，75条，25条，这些需求必须按时满足。每个季度正常的生产能力是40条帆船，每条帆船的生产费用为400美元。如果加班生产，每条船的生产费用为450美元。每个季度末，每条船的库存费用为20美元。假定生产提前期为0，初始库存为10条船。如何安排生产可使总费用最小？分析与解：用DEM、RP、OP、INV分别表示需求量，正常生产的产量，加班生产的产量，库存量。则DEM、RP、OP、INV对每个季度都应有一个对应的值，也就是说他们都应该是一个由4个元素组成的数组，其中DEM已知，而RP，OP，INV未知。现在我们可以写出该问题的模型：此外还有各变量非负的约束。记4个季度组成的集合，他们就是DEM、RP、OP、INV等变量的下标集合，对于，都有值与之对应。LINGO正是充分利用这种数组及其下标的关系，引入了“集合”与“属性”的概念。本例中我们把称之为集合，DEM、RP、OP、INV称为集合具有的属性(即定义在该集合上的属性)。下图表示了这种集合与属性的关系。集合QUARTERS的属性DEMRPOPINV集合QUARTERS1234集合QUARTERS的元素1234定义在集合QUARTERS上的属性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)下面我们看看Lingo中具体如何定义集合及其属性。下面是例2的Lingo代码：Model:Sets:QUARTERS/1,2,3,4/:DEM,RP,OP,INV;EndsetsMin=sum(QUARTERS:400*RP+450*OP+20*INV);for(QUARTERS(I):RP(I)=40;);for(QUARTERS(I)|I#GT#1:INV(I)=INV(I-1)+RP(I)+OP(I)-DEM(I););INV(1)=10+RP(1)+OP(1)-DEM(1);DATA:DEM=40,60,75,25;EnddataEnd我们总结一下上面代码的特点：（1）、模型以“MODEL：”开始，以“END”结束。它们之间由语句组成，可以分成三步分。（2）、集合定义部分以“SETS：”开始，以“ENDSETS”结束。中间定义了集合和相应属性。语句“QUARTERS/1,2,3,4/:DEM,RP,OP,INV;”定义了集合QUARTERS，以及该集合的属性DEM、RP、OP、INV，其结果正是上表里面的16个变量名。可以定义空集合，比如“Empty set/1，2，3，4/;”空集合的用法将在派生集中讲述。（3）、数据输入部分以“DATA：”开始，以“ENDDATA”结束，语句“DEM=40,60,75,25;”给出了常量DEM的值，即DEM(1)=40,DEM(2)=60，DEM(3)=75,DEM(4)=25. 语句“DEM=40,60,75,25;”也可以写成语句“DEM=40 60 75 25;”即数据之间可以用逗号或空格分开。（4）、其他部分，给出了目标函数和约束。其中目标函数（“min=”后面所接的表达式）是用求和函数“sum=(集合（下标）：关于集合的属性的表达式)”的方式定义的，这个函数的功能是对语句冒号“：”后面的表达式，按照“：”前面的集合指定的下标元素进行求和。本例中目标函数也可以写成“Min=sum(QUARTERS(i):400*RP(i)+450*OP(i)+20*INV(i)”这里“sum”相当于求和符号,而“QUARTERS(i)”相当于“”，而由于本例中已默认对所有的QUARTERS的元素求和，所以实例中可以将下标i省略。约束是用循环函数“for(集合（下标）：关于集合的属性的约束关系式)”的方式定义的，意思是对于“：”前面的集合的每个元素(下标)，冒号“：”后面的约束关系式都要成立。但对于这个约束，实际上I=1时要用到变量，但我们定义属性变量的时候是从I=1开始的，即是一个常数，为了区别I=1和I=2，3，4，我们要将I=1的约束单独列出来，而对I=2，3，4的约束我们对集合下标做了的约束，即用了“#GT#1”（这个限制条件与集合之间有一个竖线“|”分开，称为过滤条件），“I#GT#1”就表示，“#GT#”是lingo中的逻辑表达式。小结一下lingo模型最基本的组成要素：（1） 集合段：以“SETS：”开始，以“ENDSETS”结束。作用在于定义必要的集合和属性。注意一个细节，我们可以定义QUARTERS/1,2,3,4/,若QUARTERS有1000个元素，我们也不必将其一一列出，而可以简写为QUARTERS/1.1000/.（2） 目标和约束段：这部分不像其他部分，没有段的开始和结束的标记。因此是除去其他段以外的所有语句。（3） 数据段：以“DATA：”开始，以“ENDDATA”结束，作用在于对集合的属性输入必要的常数数据，格式为: 属性=常数列表;常数列表中的常数或以逗号“，”分开，或以空格分开“ ”.（4） 初始段：以“INIT：”开始，以“ENDINIT”结束。作用在于对集合的属性定义初值。因为求解算法是迭代算法，所以一个好的初值可以让程序更快解决。定义初值的格式为： 属性=常数列表;（5） 计算段：以“CALC：”开始，以“ENDCALC”结束，作用在于对一些原始数据进行计算处理，这种处理是在输入数据后，求解模型前进行的。例如，对上面的例子，如果我们希望可以得到全年的总需求和季度平均需求，可以增加这个段：CALC:T_DEM=sum(QUARTERS:DEM);!总需求;A_DEM=T_DEM/size(QUARTERS);!平均需求;ENDCALC要注意的是计算段中语句是按顺序执行的，故上面的两个语句不能调换。4.2 基本集合与派生集合例3 建筑工地的位置(用平面坐标a，b表示，单位：km)及水泥日用量d(单位：t)用下表给出。目前两个临时料厂位于P(5,1),Q(2,7),日储量各有20t。求从A，B两料厂分别向各工地运送多少水泥，使总的吨公里数最小。两个新的料场应建在何处，节省的吨公里数有多大？ 工地编号123456a1.258.750.55.7537.25b1.250.754.7556.57.75d3547611解：记工地的位置为水泥日用量为，料场位置为，日储量为，从料场j向工地i的运送量为，这个优化问题的解为：尝试将这个模型输入lingo时，利用前面介绍的集合概念，显然可以定义需求点demand和供应点supply两个集合，分别有6个和2个元素。但是决策变量是同时与supply和demand相关的属性，这该如何定义呢？其实我们可以定义一个由二元对组成的新的集合，然后将定义为该集合的属性。具体代码如下：model:sets:demand/1.6/:a,b,d;supply/1.2/:x,y,e;link(demand,supply):c;endsetsdata:a=1.25,8.75,0.5,5.75,3,7.25;b=1.25,0.75,4.75,5,6.5,7.75;d=3,5,4,7,6,11;e=20,20;enddatainit:x,y=5,1,2,7;endinitmin=sum(link(i,j):c(i,j)*(x(j)-a(i)2+(y(j)-b(i)2)(1/2);for(demand(i):sum(supply(j):c(i,j)=d(i););for(supply(i):sum(demand(j):c(j,i)=e(i););for(supply:free(x);free(y););End我们在集合段定义了三个集合，其中link是在前两个集合demand和supply的基础上定义的集合。语句link(demand,supply):c;表示集合link中的元素就是集合demand和supply的元素合成的有序二元组。从数学上看就是因此其属性c也就是6*2的矩阵。像link这样基于其他集合而派生出来的二维或多维集合我们称之为派生集合。本模型初始段中的语句“x,y=5,1,2,7”实际的赋值顺序是，也就是说lingo对数据是按列赋值的，这点要注意了，当然也可以写成“x=5,2;y=1,7”4.3 稠密集合与稀疏集合我们已经介绍了基本集合和派生集合。例3中我们把派生集合link的元素定义为demand和supply的笛卡尔积，即包含了两个基本集合构成的所有的二元有序对。这种派生集称为稠密集合，有时候一些属性肯能只在某些有序对上有意义，我们只要定义有意义的集合，这就产生了稀疏集合的概念。例4 求下图中城市S至T的最短路径。6SA1A2A3B1B2C1C2T63365874678956解：用lingo解决最短路问题，代码如下。集合段定义的cities是基本集合，L是对应的属性变量。Roads是由cities派生的集合，由于只有一部分城市之间有路相连，所以不应该把它定义为稠密集合，只能通过枚举定义成一个稀疏集合。model:sets:cities/s,a1,a2,a3,b1,b2,c1,c2,t/:L; !L表示最优行驶路线的线长;roads(cities,cities)/s,a1 s,a2 s,a3a1,b1 a1,b2 a2,b1 a2,b2 a3,b1 a3,b2b1,c1 b1,c2 b2,c1 b2,c2c1,t c2,t/:D;!D表示两城市间的直接距离;endsetsdata:D=6 3 3 6 5 8 6 7 4 6 7 8 9 5 6;L=0,;enddatafor(cities(i)|i#GT#index(s):L(i)=min(roads(j,i):L(j)+D(j,i););end从本例可以看出，lingo程序可以没有目标函数。因此lingo可以用来解方程组和不等式组。此外在数据段我们对L进行赋值，但只有L(S)=0是已知的，所以后面的值为空(但位置必须留下来，逗号“，”一个也不能少)。虽然集合cities中的元素不是数字，但当它以cities(i)的形式出现在循环中时，引用下标i实际上仍是一个整数。也就是说，i指的正是元素在集合中的位置，一般称为元素的索引。我们用index(i)来返回元素i的索引。从上例可以看出定义稀疏集合时用枚举其元素的方法给出的。但当元素比较多时，这就麻烦了。我们可以用“元素过滤法”来定义稀疏集合。例5 某班8名同学准备分成4个调查队（每队两人）前往4个地区进行社会调查。假设这8名同学两两之间组队的效率如下图所示，问如何组队效率最高？学生S1S2S3S4S5S6S7S8S19342156S2173521S344292S41552S5876S623S74解：本例的数学模型如下model:sets:students/s1.s8/;pairs(students,students)|&2#GT#&1:benefit,match;endsetsdata:benefit=9 3 4 2 1 5 6 1 7 3 5 2 1 4 4 2 9 2 1 5 5 2 8 7 6 2 3 4;enddatamax=sum(pairs(i,j):benefit(i,j)*match(i,j);for(students(i):sum(pairs(j,k)|j#EQ#i#OR#k#EQ#i:match(j,k)=1);for(pairs(i,j):bin(match(i,j);End上面代码中逻辑关系式“&2#GT#&1”表示第二个父集合的元素的缩索引值大于第一个元素的索引值。这样pairs中的元素刚好对应于上面表中的严格上三角部分的二维下标了。读者还应该注意数据段对benefit的赋值方式，体会lingo是按照列的顺序对变量元素进行赋值的。4.4 集合的使用小结小结一下集合的用法（1）、集合的不同类型和关系集合派生集合基本集合稀疏集合稠密集合元素列表法元素过滤法直接列举法隐式列举法（2）、集合的定义方法（中的内容是可选项）基本集合： setname/member_list/:attribute_list;派生集合： setname(parent_set_list)/member_list/:attribute_list;5. Lingo中的运算符与函数5.1 运算符与优先级算术运算符： (求幂)逻辑运算符：（1）#AND#（与），#OR#（或），#NOT#（非）（2）#EQ#（等于），#NE#（不等于），#GT#（大于），#GE#（大于等于），#LT#（小于），#LE#（小于等于）关系运算符：运算符的优先级优先级运算符最高#NOT# -(负号）* /+ -#EQ#,#NE#,#GT#,#GE#,#LT#,#LE#AND#,#OR#最低5.2 Lingo函数（1）、基本数学函数abs(x):绝对值函数cos(x):余弦函数exp(x):指数函数，返回floor(x):取整函数LGM(x):返回x的伽玛函数的自然对数值LOG(x):自然对数函数MOD(x,y)：模函数，返回x对y取模的结果，即x除以y的余数pow(x,y):指数函数，返回sign(x):符号函数sin(x)：正弦函数smax(list)：最大值函数，返回一列数list的最大值smin(list)：最小值函数sqr(x)：平方函数sqrt(x)：平方根函数tan(x)：正切函数（2）、集合循环函数集合循环函数一般调用格式为：function(setname(set_index_list)|condition:expression_list);其中function是函数名，setname是集合名，set_index_list是集合索引列表，condition是逻辑表达式的过滤条件。expression_list是一个表达式。集合循环函数有如下5个：for()：对集合的每个元素独立地生成表达式max()：返回集合上的表达式的最大值min()：返回集合上的表达式的最小值prod()：返回集合上的表达式的积sum()：返回集合上的表达式的和（3）、