LINGO软件的基本使用方法

LINGO,教 程,152,LINGO,软件的基本使用方法,内容提要,LINGO,入门,2.,在,LINGO,中使用集合,3.,运算符和函数,4.,LINGO,的主要菜单命令,5.,LINGO,命令窗口,1. LINGO,入门,LINGO,入门,2.,在,LINGO,中使用集合,3.,运算符和函数,4.,LINGO,的主要菜单命令,5.,LINGO,命令窗口,安装文件,20M,多一点，需要接受安装协议、选择安装目录（缺省,C:LINGO9,）。,LINGO,软件的安装,安装过程,:,与,LINDO for Windows,类似,.,安装完成前，在出现的对话框,(,如图,),中选择缺省的建模,(,即编程,),语言，系统推荐的是采用,LINGO,。安装后可通过“,LINGO|Options|File,Format”,命令修改缺省的建模（即编程）语言。,第一次运行时提示输入授权密码，如图：,LINGO,软件的主要特色,两种命令模式,Windows模式,：,通过下拉式菜单命令驱动LINGO运行（多数菜单命令有快捷键，常用的菜单命令有快捷按钮），图形界面，使用方便；,命令行 模式：仅在命令窗口,(Command Window),下操作，通过输入行命令驱动,LINGO,运行 。,(,这里主要介绍这种模式,),从,LINDO,到,LINGO,LINGO 9.0功能增强，性能稳定，解答结果可靠。与LINDO相比，LINGO 软件主要具有两大优点,:,内置建模语言，允许以简练、直观的方式描述较大规模的优化问题，所需的数据可以以一定格式保存在独立的文件中。,除具有,LINDO,的全部功能外，还可用于求解非线性规划问题，包括非线性整数规划问题,;,在LINGO中使用LINDO模型,LINGO,的界面,LINGO,软件的主窗口（用户界面），所有其他窗口都在这个窗口之内。,模型窗口（,Model Window,），用于输入,LINGO,优化模型（即,LINGO,程序）。,状态行（最左边显示“,Ready”,，表示 “准备就绪”）,当前时间,当前光标的位置,LINGO,的文件类型,.LG4,：,LINGO,格式的模型文件，保存了模型窗口中所能够看到的所有文本和其他对象及其格式信息；,.LNG,：文本格式的模型文件，不保存模型中的格式信息（如字体、颜色、嵌入对象等）；,.LDT,：,LINGO,数据文件；,.LTF,：,LINGO,命令脚本文件；,.LGR,：,LINGO,报告文件；,.LTX,：,LINDO,格式的模型文件；,.MPS,：示,MPS,（数学规划系统）格式的模型文件。,除“,LG4”,文件外，另外几种格式的文件都是普通的文本文件，可以用任何文本编辑器打开和编辑。,在,LINGO,中使用,LINDO,模型,选择菜单命令“,File|Open(F3)”,，可以看到 “打开文件”对话框。 （如图）,在,LINGO,中可以直接使用,LINDO,语法编写的优化模型（即优化程序）。作为一个最简单的例子，在名为,EXAM0201.LTX,的模型文件中保存了一个,LINDO,模型，我们现在看看如何用,LINGO,把它打开。,在,LINGO,中使用,LINDO,模型,打开“,EXAM0201.LTX”,文件 （如下图）,选择“,LINGO|Solve,（,Ctrl+S,）”来运行这个程序（运行状态窗口如右图）,运行程序的,LINGO,报告窗口（如下图）,在,LINGO,中使用,LINDO,模型,注：,LINGO,不询问是否进行敏感性分析，敏感性分析需要将来通过修改系统选项启动敏感性分析后，再调用“,REPORT|RANGE”,菜单命令来实现。现在同样可以把模型和结果报告保存在文件中。,运行状态窗口,Variables,（变量数量）：,变量总数（,Total,）、,非线性变量数（,Nonlinear,）、,整数变量数（,Integer,）。,Constraints,（约束数量）：,约束总数（,Total,）、,非线性约束个数,(Nonlinear),。,Nonzeros,（非零系数数量）：,总数（,Total,）、,非线性项系数个数,(Nonlinear),。,Generator Memory Used (K) (,内存使用量,),Elapsed Runtime (,hh:mm:ss,),（求解花费的时间）,运行状态窗口,求解器,(,求解程序,),状态框,当前模型的类型,:LP,，,QP,，,ILP,，,IQP,，,PILP,，,PIQP,，,NLP,，,INLP,，,PINLP,（以,I,开头表示,IP,，以,PI,开头表示,PIP,）,当前解的状态,: Global Optimum, Local Optimum, Feasible, Infeasible“(,不可行,), Unbounded“(,无界,), Interrupted“(,中断,), Undetermined“(,未确定,),解的目标函数值,当前约束不满足的总量,(,不是不满足的约束的个数,):,实数（即使该值,=0,，当前解也可能不可行，因为这个量中没有考虑用上下界命令形式给出的约束）,目前为止的迭代次数,运行状态窗口,扩展的求解器,(,求解程序,),状态框,使用的特殊求解程序,:,B-and-B (,分枝定界算法,),Global (,全局最优求解程序,),Multistart,(,用多个初始点求解的程序,),目前为止找到的可行解的最佳目标函数值,目标函数值的界,特殊求解程序当前运行步数：,分枝数,(,对,B-and-B,程序,),；,子问题数,(,对,Global,程序,),；,初始点数,(,对,Multistart,程序,),有效步数,注：凡是可以从一个约束直接解出变量取值时，这个变量就不认为是决策变量而是固定变量，不列入统计中；只含有固定变量的约束也不列入约束统计中。,运行状态窗口,LINGO,早期版本对,LINDO,的兼容问题,在,LINGO 9.0,以前的版本中不能直接用,File|Open,命令打开,LINDO,模型，但由,FILE | IMPORT LINDO FILE (F12),命令可以直接把,LINDO,的模型文件转化成,LINGO,模型。运行后屏幕上会显示一个标准的“打开文件”的对话框，打开,EXAM0201.LTX,，在,LINGO,主窗口中又打开了命令窗口,(Command Window),显示原始文件，名为“,exam0201”,的模型窗口显示的是等价的,LINGO,模型。当前光标位于命令窗口。,从,LINDO,模型到,LINGO,模型的实质性转化工作主要在于以下几个方面,(,这也是,LINGO,模型的最基本特征,),：,将目标函数的表示方式从“,MAX”,变成了“,MAX=”;,“,ST”(SubjectTo,),在,LINGO,模型中不需要，被删除；,在系数与变量之间增加运算符“*”,(,即乘号不能省略,);,每行,(,目标、约束和说明语句,),后面增加一个分号“,;”,；,约束的名字被放到 “, ”,中，不放在右半括号“,)”,前；,LINGO,中模型以“,MODEL,：”开始，以“,END”,结束。对简单的模型，这两个语句也可以省略。,LINGO,早期版本对,LINDO,的兼容问题,一个简单的LINGO程序,例,直接用,LINGO,来解如下二次规划问题：,输入窗口如下：,程序语句输入的备注：,LINGO,总是根据“,MAX=”,或“,MIN=”,寻找目标函数，而除注释语句和,TITLE,语句外的其他语句都是约束条件，因此语句的顺序并不重要 。,限定变量取整数值的语句为“,GIN(X1)”,和“,GIN(X2)”,，不可以写成“,GIN(2)”,，否则,LINGO,将把这个模型看成没有整数变量。,LINGO,中函数一律需要以“,”,开头，其中整型变量函数（,BIN,、,GIN,）和上下界限定函数（,FREE,、,SUB,、,SLB,）与,LINDO,中的命令类似。而且,0/1,变量函数是,BIN,函数。,输出结果：,运行菜单命令“,LINGO|Solve,”,最优整数解,X=(35,，,65),最大利润,=11077.5,输出结果备注：,通过菜单 “,WINDOW| Status Window”,看到状态窗口，可看到最佳目标值“,Best,Obj,”,与问题的上界“,Obj,Bound”,已经是一样的，当前解的最大利润与这两个值非常接近，是计算误差引起的。如果采用全局最优求解程序,(,后面介绍,),，可以验证它就是全局最优解。,LINGO,是将它作为,PINLP(,纯整数非线性规划,),来求解，因此找到的是局部最优解。,一个简单的LINGO程序,LINGO,的基本用法的几点注意事项,LINGO,中不区分大小写字母；变量和行名可以超过,8,个字符，但不能超过,32,个字符，且必须以字母开头。,用,LINGO,解优化模型时已假定所有变量非负,(,除非用限定变量取值范围的函数,free,或,sub,或,slb,另行说明,),。,变量可以放在约束条件的右端,(,同时数字也可放在约束条件的左端,),。但为了提高,LINGO,求解时的效率，应尽可能采用线性表达式定义目标和约束,(,如果可能的话,),。,语句是组成,LINGO,模型的基本单位,每个语句都以分号结尾，编写程序时应注意模型的可读性。例如：一行只写一个语句，按照语句之间的嵌套关系对语句安排适当的缩进，增强层次感。,以感叹号开始的是说明语句,(,说明语句也需要以分号结束,),）。,2.,在,LINGO,中使用集合,LINGO,入门,2.,在,LINGO,中使用集合,3.,运算符和函数,4.,LINGO,的主要菜单命令,5.,LINGO,命令窗口,6.,习题,集合的基本用法和LINGO模型的基本要素,理解,LINGO,建模语言最重要的是理解集合（,Set,）及其属性（,Attribute,）的概念。,例,SAILCO,公司需要决定下四个季度的帆船生产量。下四个季度的帆船需求量分别是,40,条，,60,条，,75,条，,25,条，这些需求必须按时满足。每个季度正常的生产能力是,40,条帆船，每条船的生产费用为,400,美元。如果加班生产，每条船的生产费用为,450,美元。每个季度末，每条船的库存费用为,20,美元。假定生产提前期为,0,，初始库存为,10,条船。如何安排生产可使总费用最小？,用,DEM,RP,OP,INV,分别表示需求量、正常生产的产量、加班生产的产量、库存量，则,DEM,RP,OP,INV,对每个季度都应该有一个对应的值，也就说他们都应该是一个由,4,个元素组成的数组，其中,DEM,是已知的，而,RP,OP,INV,是未知数。,问题的模型,(,可以看出是,LP,模型,),目标函数是所有费用的和,约束条件主要有两个：,1,）能力限制：,2,）产品数量的平衡方程：,加上变量的非负约束,注：,LINDO,中没有数组，只能对每个季度分别定义变量，如正常产量就要有,RP1,，,RP2,，,RP3,，,RP4 4,个变量等。写起来就比较麻烦，尤其是更多,(,如,1000,个季度,),的时候。,记四个季度组成的集合,QUARTERS=1,，,2,，,3,，,4,，它们就是上面数组的下标集合，而数组,DEM,RP,OP, INV,对集合,QUARTERS,中的每个元素,1,，,2,，,3,，,4,分别对应于一个值。,LINGO,正是充分利用了这种数组及其下标的关系，引入了“集合”及其“属性”的概念，把,QUARTERS=1,，,2,，,3,，,4,称为集合，把,DEM,RP,OP, INV,称为该集合的属性,(,即定义在该集合上的属性,),。,QUARTERS,集合的属性,DEM,RP,OP,INV,QUARTERS,集合,2,3,4,1,集合及其属性,集合元素及集合的属性确定的所有变量,集合,QUARTERS,的元素,1,2,3,4,定义在集合,QUARTERS,上的属性,DEM,DEM(1),DEM(2),DEM(3),DEM(4),RP,RP(1),RP(2),RP(3),RP(4),OP,OP(1),OP(2),OP(3),OP(4),INV,INV(1),INV(2),INV(3),INV(4),LINGO,中定义集合及其属性,LP,模型在,LINGO,中的一个典型输入方式,以“,MODEL,：”开始,以“,END”,结束,集合定义部分从,(“SETS,：”到“,ENDSETS” ),：定义集合及其属性,集合定义部分从,(“DATA,：”到“,ENDDATA”,),给出优化目标和约束,目标函数的定义方式,SUM(,集合（下标）：关于集合的属性的表达式,),对语句中冒号“：”后面的表达式，按照“：”前面的集合指定的下标（元素）进行求和。,本例中目标函数也可以等价地写成,SUM(QUARTERS(i,): 400*,RP(i,) +450*,OP(i,) +20*,INV(i,) ),，,“,SUM”,相当于求和符号“,”,，,“,QUARTERS(i,)”,相当于“,iQUARTERS,”,的含义。,由于本例中目标函数对集合,QUARTERS,的所有元素,(,下标,),都要求和，所以可以将下标,i,省去。,约束的定义方式,循环函数,FOR(,集合,(,下标,),：关于集合的属性的约束关系式,),对冒号“：”前面的集合的每个元素（下标），冒号“：”后面的约束关系式都要成立,本例中，每个季度正常的生产能力是,40,条帆船，这正是语句“,FOR(QUARTERS(I):RP(I)40);”,的含义。,由于对所有元素,(,下标,I),约束的形式是一样的，所以也可以像上面定义目标函数时一样，将下标,i,省去，,这个语句可以简化成“,FOR(QUARTERS:RP1,；“,#GT#”,是逻辑运算符号，意思是“大于（,Greater Than,的字首字母缩写）” 。,约束的定义方式,问题的求解：运行菜单命令“,LINGO|Solve,”,全局最优解,RP=(40,40,40,25),OP=(0,10,35,0),最小成本,=78450,注：,由于输入中没有给出行名，所以行名是系统自动按照行号,1-9,生成的。,选择菜单命令“,LINGO|Generate|Disply,model,（,Ctrl+G,）”，可以得到展开形式的模型,(,如图,),，可以看到完整的模型，也能确定行号,(,行号放在方括号“, ”,中，且数字前面带有下划线“,_”),。,最好在输入模型时用户主动设定约束的行名,(,即约束名,),，使程序清晰些。单一约束的行名设置方法就是将行名放在方括号“, ”,中，置于约束之前。,后面将结合具体例子介绍在使用集合的情况下如何设置行名。,小结,:LINGO,模型最基本的组成要素,一般来说，,LINGO,中建立的优化模型可以由五个部分组成，或称为五“段”（,SECTION,）：,（,1,）集合段（,SETS,）：,以“,SETS:”,开始， “,ENDSETS”,结束，定义必要的集合变量（,SET,）及其元素（,MEMBER,，含义类似于数组的下标）和属性（,ATTRIBUTE,，含义类似于数组）。,如上例中定义了集合,quarters(,含义是季节,),，它包含四个元素即四个季节指标,(1,2,3,4),，每个季节都有需求,(DEM),、正常生产量,(RP),、加班生产量,(OP),、库存量,(INV),等属性,(,相当于数组，数组下标由,quarters,元素决定,),。一旦这样的定义建立起来，如果,quarters,的数量不是,4,而是,1000,只需扩展其元素为,1,2,.,1000,每个季节仍然都有,DEM,RP,OP,INV,这样的属性,(,这些量的具体数值如果是常量，则可在数据段输入；如果是未知数，则可在初始段输入初值,),。当,quarters,的数量不是,4,而是,1000,时，没有必要把,1,2,，,.,1000,全部一个一个列出来，而是可以如下定义,quarters,集合：,“,quarters/1.1000/:DEM,RP,OP,INV,;” ,“1.1000”,的意思就是从,1,到,1000,的所有整数。,（,2,）目标与约束段,：目标函数、约束条件等，没有段的开始和结束标记，因此实际上就是除其它四个段,(,都有明确的段标记,),外的,LINGO,模型。,这里一般要用到,LINGO,的内部函数，尤其是与集合相关的求和函数,SUM,和循环函数,FOR,等。,上例中定义的目标函数与,quarters,的元素数目是,4,或,1000,并无具体的关系。约束的表示也类似。,（,3,）数据段,(DATA),：以 “,DATA:”,开始, “ENDDATA”,结束，对集合的属性,(,数组,),输入必要的常数数据。,格式为：“,attribute(,属性,) =,value_list,(,常数列表,);,”,常数列表,(,value_list,),中数据之间可以用逗号“,”,分开，也可以用空格分开,(,回车等价于一个空格,),如上面对,DEM,的赋值也可以写成“,DEM=40 60 75 25,；”。,在,LINGO,模型中，如果想在运行时才对参数赋值，可以在数据段使用输入语句。但这仅能用于对单个变量赋值，输入语句格式为：“,变量名,=,？；,”。例如，上例中如果需要在求解模型时才给出初始库存量,(,记为,A),，则可以在模型中数据段写上语句：,”,A = ?,；,”,在求解时,LINDO,系统给出提示界面，等待用户输入变量,A,的数值。当然，此时的约束语句,INV(1)=10+RP(1)+OP(1)-DEM(1);,也应该改写成,INV(1)=A+RP(1)+OP(1)-DEM(1);,这样，模型就可以计算任意初始库存量,(,而不仅仅只能计算初始库存量为,10),的情况了。,（,4,）初始段,(INIT),：以“,INIT: ”,开始， “,ENDINIT”,结束，对集合的属性,(,数组,),定义初值,(,因为求解算法一般是迭代算法，所以用户如果能给出一个比较好的迭代初值，对提高算法的计算效果是有益的,),。,如果有一个接近最优解的初值，对,LINGO,求解模型是有帮助的。定义初值的格式为：,“,attribute,（属性）,=,value_list,（常数列表）；,”,这与数据段中的用法是类似的。,上例中没有初始化部分，我们将在下一个例子中举例说明。,（,5,）计算段,(CALC),：以“,CALC: ”,开始， “,ENDCALC”,结束，对一些原始数据进行计算处理。,在实际问题中，输入的数据通常是原始数据，不一定能在模型中直接使用，可以在这个段对这些原始数据进行一定的“预处理”，得到模型中真正需要的数据。,例如上例，如果希望得到全年的总需求和季度平均需求，可以增加这个段：,CALC:,T_DEM = ,SUM(quarters,: DEM); !,总需求,;,A_DEM = T_DEM / size(quarters); !,平均需求,;,ENDCALC,在计算段中也可以使用集合函数（其中函数,size(quarters,),表示集合,quarters,的元素个数，这里也就是,4,）。这时，变量,T_DEM,的值就是总需求，,A_DEM,的值就是平均需求（如果需要的话，这两个变量就可以在程序的其它地方作为常数使用了）。,注：上面的两个语句不能交换顺序，因为计算,A_DEM,必须要用到,T_DEM,的值。此外，在计算段中只能直接使用赋值语句，而不能包含需要经过解方程或经过求解优化问题以后才能决定的变量。,基本集合与派生集合,例,建筑工地的位置,(,用平面坐标,a,b,表示，距离单位：公里,),及水泥日用量,d,(,吨,),下表给出。有两个临时料场位于,P (5,1), Q (2, 7),日储量各有,20,吨。从,A, B,两料场分别向各工地运送多少吨水泥，使总的吨公里数最小。两个新的料场应建在何处，节省的吨公里数有多大？,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,建立模型,记工地的位置为 ，水泥日用量为 ；料场位置为 ，日储量为 ；从料场 向工地 的运送量为 。,使用现有临时料场时，决策变量只有 （非负），所以这是,LP,模型；当为新建料场选址时决策变量为 和 ，由于目标函数 对 是非线性的，所以在新建料场时是,NLP,模型。先解,NLP,模型，而把现有临时料场的位置作为初始解告诉,LINGO,。,本例中集合的概念,利用集合的概念，可以定义需求点,DEMAND,和供应点,SUPPLY,两个集合，分别有,6,个和,2,个元素,(,下标,),。但决策变量,(,运送量,),与集合,DEMAND,和集合,SUPPLY,都有关系的。该如何定义这样的属性？,集合的属性相当于以集合的元素为下标的数组。这里的 相当于二维数组。它的两个下标分别来自集合,DEMAND,和,SUPPLY,，因此可以定义一个由二元对组成的新的集合，然后将 定义成这个新集合的属性。,输入程序,定义了三个集合，其中,LINK,在前两个集合,DEMAND,和,SUPPLY,的基础上定义,表示集合,LINK,中的元素就是集合,DEMAND,和,SUPPLY,的元素组合成的有序二元组，,从数学上看,LINK,是,DEMAND,和,SUPPLY,的笛卡儿积，也就是说,LINK=,（,S,，,T,）,|SDEMAND,，,TSUPPLY,因此，其属性,C,也就是一个,6*2,的矩阵（或者说是含有,12,个元素的二维数组）。,LINGO,建模语言也称为矩阵生成器（,MATRIX GENERATOR,）。类似,DEMAND,和,SUPPLY,直接把元素列举出来的集合，称为,基本集合,(primary set),而把,LINK,这种基于其它集合而派生出来的二维或多维集合称为,派生集合,(derived set),。由于是,DEMAND,和,SUPPLY,生成了派生集合,LINK,，所以,DEMAND,和,SUPPLY,称为,LINK,的,父集合,。,输入程序,初始段,INGO,对数据是按列赋值的,语句的实际赋值顺序是,X=(5,2), Y=(1,7),而不是,X=(5,1), Y=,（,2,7),等价写法：,“,X=5,2,；,Y=1,7,；”,同理，数据段中对常数数组,A,，,B,的赋值语句也可以写成,A, B=1.25,1.25,8.75 0.75 0.5 4.75 5.75 5 3 6.5 7.25 7.75,；,输入程序,定义目标和约束，与前例的方法是类似,(,这里包含了派生集合,),，请特别注意进一步体会集合函数,SUM,和,FOR,的用法。,由于新建料场的位置理论上讲可以是任意的，所以在约束的最后,(,模型的“,END”,语句上面的一行,),用,free,函数取消了变量,X,、,Y,的非负限制,在程序开头用,TITLE,语句对这个模型取了一个标题“,LOCATION PROBLEM,；并且对目标行（,OBJ,）和两类约束（,DEMAND_CON,、,SUPPLY_CON,）分别进行了命名,(,请特别注意这里约束命名的特点,),。,解答,:,运行菜单命令“,LINGO|Solve,”,局部最优解,X(1)=7.249997,，,X(2)=5.695940,，,Y(1)=7.749998,，,Y(2)=4.928524,，,C,（略），,最小运量,=89.8835(,吨公里,),。,问题,:,最小运量,89.8835,是不是全局最优,是用“,LINGO|Options,”,菜单命令打开选项对话框，在“,Global Solver”,选项卡上选择“,Use Global Solver”,激活全局最优求解程序。,问题,:,最小运量,89.8835,是不是全局最优,为减少计算工作量，对,X,，,Y,的取值再做一些限制。虽然理论上新建料场的位置可以是任意的，但显然最佳的料场位置不应该离工地太远，至少不应该超出现在,6,个工地所决定的坐标的最大、最小值决定的矩形之外，即,: 0.5=x=8.75,0.75=y=7.75.,可以用,bnd,函数加上这个条件取代模型,END,上面的行，运行,NLP,模型，全局最优求解程序花费的时间仍然很长，运行,27,分,35,秒时人为终止求解,(,按下“,Interrupt Solver”,按钮,),得到左边模型窗口和全局求解器的状态窗口,此时目标函数值的下界（,Obj,Bound=85.2638,）与目前得到的最好的可行解的目标函数值（,Best,Obj,=85.2661,）相差已经非常小，可以认为已经得到了全局最优解。,计算结果,工地与料场示意图,: “*”,表示料场，“,+”,表示工地,可以认为是模型的最后结果,附注：如果要把料厂,P(5, 1), Q (2, 7),的位置看成是已知并且固定的，这时是,LP,模型。只需要把初始段的“,X Y =5,，,1,，,2,，,7,；”语句移到数据段就可以了。此时，运行结果告诉我们得到全局最优解（变量,C,的取值这里略去），最小运量,136.2275(,吨公里,),。,稠密集合与稀疏集合,包含了两个基本集合构成的所有二元有序对的派生集合称为,稠密集合,(,简称稠集,),。有时候，在实际问题中，一些属性,(,数组,),只在笛卡儿积的一个真子集合上定义，这种派生集合称为,稀疏集合,(,简称疏集,),。,例,(,最短路问题,),在纵横交错的公路网中，货车司机希望找到一条从一个城市到另一个城市的最短路,.,下图表示的是公路网,节点表示货车可以停靠的城市,弧上的权表示两个城市之间的距离,(,百公里,).,那么,货车从城市,S,出发到达城市,T,如何选择行驶路线,使所经过的路程最短,?,S,T,A,1,A,2,A,3,B,1,B,2,C,1,C,2,6,3,3,6,6,5,8,7,4,6,7,8,9,5,6,S,T,A,1,A,2,A,3,B,1,B,2,C,1,C,2,6,3,3,6,6,5,8,7,4,6,7,8,9,5,6,分析,假设从,S,到,T,的最优行驶路线,P,经过城市,C,1,则,P,中从,S,到,C,1,的子路也一定是从,S,到,C,1,的最优行驶路线,;,假设,P,经过城市,C,2,则,P,中从,S,到,C,2,的子路也一定是从,S,到,C,2,的最优行驶路线,.,因此,为得到从,S,到,T,的最优行驶路线,只需要先求出从,S,到,C,k,(,k,=1,2),的最优行驶路线,就可以方便地得到从,S,到,T,的最优行驶路线,.,同样,为了求出从,S,到,C,k,(,k,=1,2),的最优行驶路线,只需要先求出从,S,到,B,j,(,j,=1,2),的最优行驶路线,;,为了求出从,S,到,B,j,(,j,=1,2),的最优行驶路线,只需要先求出从,S,到,A,i,(,i,=1,2,3),的最优行驶路线,.,而,S,到,A,i,(,i,=1,2,3),的最优行驶路线是很容易得到的,(,实际上,此例中,S,到,A,i,(,i,=,1,2,3),只有唯一的道路,),分析,S,T,A,1,A,2,A,3,B,1,B,2,C,1,C,2,6,3,3,6,6,5,8,7,4,6,7,8,9,5,6,此例中可把从,S,到,T,的行驶过程分成,4,个阶段,即,SA,i,(,i,=1,2,或,3), A,i,B,j,(,j,=1,或,2),B,j,C,k,(,k,=1,或,2), C,k, T.,记,d,(,Y,X,),为城市,Y,与城市,X,之间的直接距离,(,若这两个城市之间没有道路直接相连，则可以认为直接距离为,),，用,L,(X),表示城市,S,到城市,X,的最优行驶路线的路长,:,本例的计算,S,T,A,1,A,2,A,3,B,1,B,2,C,1,C,2,6,3,3,6,6,5,8,7,4,6,7,8,9,5,6,所以,从,S,到,T,的最优行驶路线的路长为,20.,进一步分析以上求解过程,可以得到从,S,到,T,的最优行驶路线为,S A,3, B,2, C,1, T.,这种计算方法在数学上称为,动态规划,(Dynamic Programming),本例的,LINGO,求解,“,CITIES”(,城市,):,一个基本集合,(,元素通过枚举给出,),L:CITIES,对应的属性变量,(,我们要求的最短路长,),“,ROADS”(,道路,):,由,CITIES,导出的一个派生集合,(,请特别注意其用法,),由于只有一部分城市之间有道路相连，所以不应该把它定义成稠密集合，将其元素通过枚举给出，这就是一个稀疏集合。,D:,稀疏集合,ROADS,对应的属性变量,(,给定的距离,),本例的,LINGO,求解,从模型中还可以看出：这个,LINGO,程序可以没有目标函数，这在,LINGO,中，可以用来找可行解,(,解方程组和不等式组,),。,在数据段对,L,进行赋值，只有,L(S)=0,已知，后面的值为空,(,但位置必须留出来，即逗号“，”一个也不能少，否则会出错,),。如果这个语句直接写成“,L=0,；”，语法上看也是对的，但其含义是,L,所有元素的取值全部为,0,，所以也会与题意不符。,本例的,LINGO,求解,虽然集合,CITIES,中的元素不是数字，但当它以,CITIES(I),的形式出现在循环中时，引用下标,I,却实际上仍是正整数，也就是说,I,指的正是元素在集合中的位置,(,顺序,),，一般称为元素的索引,(INDEX),。,在,for,循环中的过滤条件里用了一个函数“,index”,其作用是返回一个元素在集合中的索引值，这里,index(S,)=1(,即元素,S,在集合中的索引值为,1),，所以逻辑关系式“,I#GT#index(S,)”,可以可以直接等价地写成“,I#GT#1”,。这里,index(S,),实际上还是,index(CITIES,S,),的简写，即返回,S,在集合,CITIES,中的索引值。,本例的,LINGO,求解结果,从,S,到,T,的最优行驶路线的路长为,20(,进一步分析，可以得到最优行驶路线为,S A3 B2 C1 T),。,本例中定义稀疏集合,ROADS,的方法是将其元素通过枚举给出，有时如果元素比较多，用起来不方便。另一种定义稀疏集合的方法是“元素过滤”法，能够从笛卡儿积中系统地过滤下来一些真正的元素。,例,某班,8,名同学准备分成,4,个调查队,(,每队两人,),前往,4,个地区进行社会调查。这,8,名同学两两之间组队的效率如下表所示,(,由于对称性，只列出了严格上三角部分,),，问如何组队可以使总效率最高？,学生,S1,S2,S3,S4,S5,S6,S7,S8,S1,-,9,3,4,2,1,5,6,S2,-,-,1,7,3,5,2,1,S3,-,-,-,4,4,2,9,2,S4,-,-,-,-,1,5,5,2,S5,-,-,-,-,-,8,7,6,S6,-,-,-,-,-,-,2,3,S7,-,-,-,-,-,-,-,4,分析,这是一个匹配（,MATCHING,）问题。把上表的效率矩阵记为,BENEFIT(,由于对称性，这个矩阵只有严格上三角部分共,28,个数取非零值,),。,用,MATCH,（,Si,，,Sj,）,=1,表示同学,Si,，,Sj,组成一队 ，而,MATCH,（,Si,，,Sj,）,=0,表示,Si,，,Sj,不组队。由于对称性，只需考虑,ij,共,28,个,0-1,变量,(,而不是全部,32,个变量,),。,显然,目标函数正好是,BENEFIT(Si,Sj,)*,MATCH(Si,Sj,),对,I,j,之和。,约束条件是每个同学只能,(,而且必须在,),某一组，即对于任意,i,有,:,只要属性,MATCH,的某个下标为,i,就加起来，此和应该等于,1,。,由上面的分析，因此，完整的数学模型如下,(,显然，这是一个,0-1,线性规划,),：,问题的,LINGO,求解,“,S1.S8”,等价于写成“,S1 S2 S3 S4 S5 S6 S7 S8”,它没有相关的属性列表，只用于表示是一个下标集合,在派生集合,PAIRS,定义中增加了过滤条件 “,&2#GT#&1”,意思是第,2,个父集合的元素的索引值,(,用“,&2”,表示,),大于第,1,个父集合的元素的索引值,(,用“,&1”,表示,),。,PAIRS,中的元素对应于上表中的严格上三角部分的二维下标,(,共,28,个元素,),。,BENEFIT,和,MATCH,是,PAIRS,的属性。,注意数据段对,BENEFIT,的赋值方式，“,LINGO,按照列的顺序对属性变量的元素进行赋值。在约束部分，过滤条件“,J #EQ# I #OR# K #EQ# I”,是由逻辑运算符“,#OR#,（或者）”连接的一个复合的逻辑关系式，连接由“,#EQ#,（等于）”表示的两个逻辑关系。由于“,#OR#”,的运算级别低于“,#EQ#”,，所以这个逻辑式中没有必要使用括号指定运算次序。,LINGO,求解结果,“,LINGO|SOLVE”,运行这个程序，可以得到全局最优值为,30,MATCH,变量中多数为,0,，可以更清晰地浏览最优解解。,选择菜单命令“,LINGO|SOLUTION”,，可以看到图示对话框。,选择属性,MATCH(,变量,),选择,Text(,文本格式,),选择,Nonzeros,Only(,只显示非零值,),点击“,OK”,按钮，得到关于最优解的非零分量的报告,学生最佳的组队方式是,(1,8),(2,4),(3,7),(5,6).,集合的使用小结,集合的不同类型及其关系,集合,派生集合,稀疏集合,稠密集合,基本集合,元素列表法,元素过滤法,直接列举法,隐式列举法,基本集合的定义语法,基本集合的定义格式为,(,方括号“, ”,中的内容是可选项,可以没有,):,setname,/,member_list,/ :,attribute_list,;,其中,setname,为定义的集合名，,member_list,为元素列表，,attribute_list,为属性列表。元素列表可以采用显式列举法,(,即直接将所有元素全部列出,元素之间用逗号或空格分开,),也可以采用隐式列举法。隐式列举法可以有几种不同格式，,类型,隐式列举格式,示例,示例集合表示的元素,数字型,1.n,1.5,1, 2, 3, 4, 5,字符,-,数字型,stringM.stringN,Car101.car208,Car101, car102, , car208,日期（星期）型,dayM.dayN,MON.FRI,MON, TUE, WED, THU, FRI,月份型,monthM.monthN,OCT.JAN,OCT, NOV, DEC, JAN,年份,-,月份型,monthYearM.monthYearN,OCT2001.JAN2002,OCT2001, NOV2001, DEC2001, JAN2002,元素列表和属性列表都是可选的。,当属性列表不在集合定义中出现时，这样的集合往往只是为了将来在程序中作为一个循环变量来使用,或者作为构造更复杂的派生集合的父集合使用,(,匹配问题中的集合,STUDENTS,没有属性列表,),。,而当元素列表不在基本集合的定义中出现时,则必须在程序的数据段以赋值语句的方式直接给出元素列表。,例如，前例中,SAILCO,公司决定四个季度的帆船生产量模型的集合段和数据段可以分别改为：,SETS:,QUARTERS:DEM,RP,OP,INV; !,注意没有给出集合的元素列表,;,ENDSETS,DATA:,QUARTERS DEM=1 40 2 60 3 75 4 25; !,注意,LINGO,按列赋值的特点,;,ENDDATA,基本集合的定义语法,帆船生产量模型的源程序,匹配问题的源程序,派生集合的定义语法,派生集合的定义格式为,(,方括号“, ”,中的内容是可选项,可以没有,):,setname(parent_set_list,) /,member_list,/ :,attribute_list,;,与基本集合的定义相比较多了一个,parent_set_list,(,父集合列表,),。,父集合列表中的集合,(,如,set1,，,set2,，,，等,),称为派生集合,setname,的父集合，它们本身也可以是派生集合。,当元素列表,(,member_list,),不在集合定义中出现时，还可以在程序的数据段以赋值语句的方式给出元素列表；,若在程序的数据段也不以赋值语句的方式给出元素列表，则认为定义的是稠密集合，即父集合中所有元素的有序组合,(,笛卡儿积,),都是,setname,的元素。,当元素列表在集合定义中出现时，又有“元素列表法”,(,直接列出元素,),和“元素过滤法”,(,利用过滤条件,),两种不同方式。,3.,运算符和函数,LINGO,入门,2.,在,LINGO,中使用集合,3.,运算符和函数,4.,LINGO,的主要菜单命令,5.,LINGO,命令窗口,运算符及其优先级,算术运算符,加、减、乘、除、乘方等数学运算,(,即数与数之间的运算，运算结果也是数,),。,LINGO,中的算术运算符有以下,5,种：,+,（加法），,（减法或负号），,*（乘法），,/,（除法），, (,求幂,),。,逻辑运算符,运算结果只有“真”,(TRUE),和“假”,(FALSE),两个值,(,称为“逻辑值”,),，,LINGO,中用数字,1,代表,TRUE,，其他值,(,典型的值是,0),都是,FALSE,。,在,LINGO,中，逻辑运算,(,表达式,),通常作为过滤条件使用,逻辑运算符有,9,种，可以分成两类：,#AND#(,与,),#OR#(,或,),#NOT#(,非,),：逻辑值之间的运算，它们操作的对象本身已经是逻辑值或逻辑表达式，计算结果也是逻辑值。,#EQ#(,等于,),#NE#(,不等于,),#GT#(,大于,),#GE#(,大于等于,),#LT#(,小于,),#LE#(,小于等于,),：是“数与数之间”的比较,也就是它们操作的对象本身必须是两个数,计算得到的结果是逻辑值。,关系运算符,表示是“数与数之间”的大小关系，在,LINGO,中用来表示优化模型的约束条件。,LINGO,中关系运算符有,3,种：,(,即,(,即,=,，大于等于,),(,在优化模型中,约束一般没有严格小于、严格大于关系,),运算符的优先级,优先级,最高,最低,运算符,#NOT#,(,负号,),*,/,+,(,减法,),#EQ# #NE# #GT# #GE# #LT# #LE#,#AND# #OR#,基本的数学函数,在,LINGO,中建立优化模型时可以引用大量的内部函数,这些函数以”,”,打头。,LINGO,中包括相当丰富的数学函数,这些函数的用法非常简单,下面一一列出。,ABS(X),：绝对值函数，返回,X,的绝对值。,COS(X),：余弦函数，返回,X,的余弦值（,X,的单位是弧度）。,EXP(X),：指数函数，返回,FLOOR(X),：取整函数，返回,X,的整数部分,(,向最靠近,0,的方向取整,),。,LGM(X),：返回,X,的伽玛,(,gamma),函数的自然对数值,(,当,X,为整数时,LGM(X) = LOG(X-1),！；当,X,不为整数时，采用线性插值得到结果,),。,LOG(X),：自然对数函数，返回,X,的自然对数值。,的值,(,其中,e=,2.718281.),。,基本的数学函数,MOD(X,Y),：模函数，返回,X,对,Y,取模的结果，即,X,除以,Y,的余数，这里,X,和,Y,应该是整数。,POW(X,Y),：指数函数，返回,XY,的值。,SIGN(X),：符号函数，返回,X,的符号值（,X = 0,时返回,+1,）。,SIN(X),：正弦函数，返回,X,的正弦值（,X,的单位是弧度）。,SMAX(list,),：最大值函数，返回一列数,(list),的最大值。,SMIN(list,),：最小值函数，返回一列数,(list),的最小值。,SQR(X),：平方函数，返回,X,的平方（即,X*X,）的值。,SQRT(X),：开平方函数，返回,X,的正的平方根的值。,TAN(X),：正切函数，返回,X,的正切值（,X,的单位是弧度）。,集合循环函数,集合上的元素,(,下标,),进行循环操作的函数,一般用法如下,:,function(setname, (,set_index_list,) | condition :,expression_list,);,其中：,function,集合函数名,FOR,、,MAX,、,MIN,、,PROD,、,SUM,之一；,Setname,集合名；,set_index_list,集合索引列表,(,不需使用索引时可以省略,),；,Condition,用逻辑表达式描述的过滤条件,(,通常含有索引，无条件时可以省略,),；,expression_list,一个表达式,(,对,FOR,函数，可以是一组表达式。,集合循环函数,五个集合函数名的含义,:,FOR(,集合元素的循环函数,),： 对集合,setname,的每个元素独立地生成表达式，表达式由,expression_list,描述（通常是优化问题的约束）。,MAX,（集合属性的最大值函数）：返回集合,setname,上的表达式的最大值。,MIN,（集合属性的最小值函数）：返回集合,setname,上的表达式的最小值。,PROD,（集合属性的乘积函数）： 返回集合,setname,上的表达式的积。,SUM(,集合属性的求和函数,):,返回集合,setname,上的表达式的和。,集合操作函数,INDEX( ,set_name,primitive_set_element,),给出元素,primitive_set_element,在集合,set_name,中的索引值,(,即按定义集合时元素出现顺序的位置编号,),。省略,set_name,，,LINGO,按模型中定义的集合顺序找到第一个含有该元素的集合，并返回索引值。如果没有找到该元素，则出错。,注,:,Set_name,的索引值是正整数且只能位于,1,和元素个数之间。例,:,定义一个女孩姓名集合,(GIRLS),和男孩姓名集合,(BOYS),：,SETS:,GIRLS /DEBBIE, SUE, ALICE/;,BOYS /BOB, JOE, SUE, FRED/;,ENDSETS,都有,SUE, GIRLS,在,BOYS,前定义,调用,INDEX(SUE),将返,2,，相当于,INDEX(GIRLS,SUE),。要找男孩中名为,SUE,的小孩的索引，应该使用,INDEX(BOYS, SUE),，返,3,。,集合操作函数,IN(,set_name, primitive_index_1 , primitive_index_2 .),判断一个集合中是否含有某个索引值。如果集合,set_name,中包含由索引,primitive_index_1 , primitive_index_2 .,所对应元素，则返回,1(,逻辑值“真”,),，否则返回,0(,逻辑值“假”,),。索引用“,&1”,、“,&2”,或,INDEX,函数等形式给出，这里“,&1”,表示对应于第,1,个父集合的元素的索引值，“,&2”,表示对应于第,2,个父集合的元素的索引值。,例,:,定义一个集合,STUDENTS(,基本集合,),，派生出集合,PASSED,和,FAILED,，定义：,SETS:,STUDENTS / ZHAO, QIAN, SUN, LI/:;,PASSED( STUDENTS) /QIAN,，,SUN/:;,FAILED( STUDENTS) | #NOT# IN( PASSED, ,ENDSETS,如果集合,C,是由集合,A,，,B,派生的，例如：,SETS:,A / 1.3/:;,B / X Y Z/:;,C( A, B) / 1,X 1,Z 2,Y 3,X/:;,ENDSETS,判断,C,中是否包含元素（,2,，,Y,），则可以利用以下语句：,X = IN( C, INDEX( A, 2), INDEX( B, Y);,对本例，结果是,X=1,（真）。,注：,X,既是集合,B,的元素，又对,X,赋值,1,，在,LINGO,中这种表达是允许的，因为前者是集合的元素，后者是变量，逻辑上没有关系,(,除了同名外,),所以不会出现混淆。,集合操作函数,IN(,set_name, primitive_index_1 , primitive_index_2 .),WRAP(I,N),此函数对,N1,无定义,当,I,位于区间,1, N,内时直接返回,I,；一般地，返回,J = I - K *N ,其中,J,位于区间,1, N ,，,K,为整数。,即,WRAP(I,N)= MOD,（,I,，,N,）。,但当,MOD(I,N)=0,时,WRAP(I,N)=N.,此函数可以用来防止集合的索引值越界。,用户在编写,LINGO,程序时，应注意避免,LINGO,模型求解时出现集合的索引值越界的错误。,集合操作函数,SIZE (,set_name,),返回数据集,set_name