lingo处理实例(多目标问题)(课堂PPT).ppt

数学建模辅导,2012,年,07,月,19,日,常见的问题,1,分析题目以及选题,2,方法的选择,3,模型的体现,4,对问题求解和软件使用,5,论文写作和格式、排版,6,其他,1,分析题目以及选题,越熟悉的领域越好？,X,（,学经济的就一定要选择*题？）,觉得越简单越好？,X,（*题感觉太难。）,感兴趣很重要,挖掘内部的数学问题（,A,题中的数学,）,抓住主要问题（,不要跑题,减速带的设计、不是分析特定类型,）,要有独到的见解和创新的思路（,只要讨论量与量的关系就回归、拟合,）,要能够根据问题合理安排时间（,无法完成题目,）,2,方法的选择,对问题进行数学描述。（,比如,A,题,）,要有大致方向，不要直接去查题目的关键词，,比如直接搜索“股指预测”等等,。,平时要积累，比赛时要多查资料多思考。,组内讨论。,完整学习已有方法，关键步骤要知道为什么（,一些特殊的回归模型,）。,要结合自身条件选择方法，要可求解（,偏微,）。,对以有方法，要能够结合问题特点进行修正（,规划问题、最短路等等，东三省,D,题,）。,3,模型的体现,要有完整的建模过程，达到让人看懂（,看不懂,则白做,）,细致的问题分析（,由此给出建立模型的依据，数学建模绝不简单的是用计算机进行数据分析，比如,C,题,）,精确的提炼出所需变量,(,A,题中需要分析的量,),问题内在机理（,变量之间的关系,）,选择特定方法的原因（,比如一般的统计方法的使用都依赖于强烈的问题的背景和已知的统计学信息,）,模型的数学表达（,便于下文中应用数学技巧处理和求解,）,必要的解释,(,补充一些说明使问题叙述更清晰,),4,模型求解和软件使用,模型的求解要能够完整的回答题目中问题。,要检验结果的合理性（,不一定要体现在论文中,）。,要有结果分析。,常见软件的使用（,C,，,Matlab,，,Lingo,，,Mathematica,等等,）。,学会使用可以查到的程序（,读懂很重要,）。,会修改和改正他人的程序（,包括改正错误,）。,结果的表述（,不要罗列大量的数据表格,）。,5,论文写作和排版,写些什么内容（说明文？）,正文层次,段落设置,公式,/Mathtype,（,与文字混排要注意行距、标号、对齐,）,提要式语句和结论性语句,图、表（,各种软件图的保存、图名、表头、边框,）,引用的工作要明示、参考文献,6,其他,如何查资料,队友间合作讨论问题（,达成一致意见,）,良好的写作和编程习惯,任务分配,（不易完全分块、建模要共同完成）,LINGO,软件的基本使用方法,内容提要,LINGO,入门,2.,在,LINGO,中使用集合,3.,运算符和函数,4.,LINGO,的主要菜单命令,5.,LINGO,命令窗口,6.,习题,1.LINGO,入门,LINGO,入门,2.,在,LINGO,中使用集合,3.,运算符和函数,4.,LINGO,的主要菜单命令,5.,LINGO,命令窗口,LINGO,软件的主要特色,两种命令模式,Windows模式,：,通过下拉式菜单命令驱动LINGO运行（多数菜单命令有快捷键，常用的菜单命令有快捷按钮），图形界面，使用方便；,命令行 模式：仅在命令窗口,(Command Window),下操作，通过输入行命令驱动,LINGO,运行。,(,这里主要介绍这种模式,),从,LINDO,到,LINGO,如今,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”,文件外，另外几种格式的文件都是普通的文本文件，可以用任何文本编辑器打开和编辑。,运行状态窗口,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,程序,例,直接用,LINGO,来解如下二次规划问题：,输入窗口如下：,程序语句输入的备注：,LINGO,总是根据“,MAX=”,或“,MIN=”,寻找目标函数，而除注释语句和,TITLE,语句外的其他语句都是约束条件，因此语句的顺序并不重要。,限定变量取整数值的语句为“,GIN(X1)”,和“,GIN(X2)”,，不可以写成“,GIN(2)”,，否则,LINGO,将把这个模型看成没有整数变量。,LINGO,中函数一律需要以“,”,开头，其中整型变量函数（,BIN,、,GIN,）和上下界限定函数（,FREE,、,BND(L,X,U),）。而且,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,或,BND,另行说明,),。,变量可以放在约束条件的右端,(,同时数字也可放在约束条件的左端,),。但为了提高,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,省去。,约束的定义方式,循环函数,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,（常数列表）；,”,这与数据段中的用法是类似的。,上例中没有初始化部分，我们将在下一个例子中举例说明。,基本集合与派生集合,例,3.4,建筑工地的位置,(,用平面坐标,a,b,表示，距离单位：公里,),及水泥日用量,d,(,吨,),下表给出。有两个临时料场位于,A(5,1),B(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,命令窗口,6.,习题,运算符及其优先级,算术运算符,加、减、乘、除、乘方等数学运算,(,即数与数之间的运算，运算结果也是数,),。,LINGO,中的算术运算符有以下,5,种：,+,（加法），,（减法或负号），,*（乘法），,/,（除法），,(,求幂,),。,逻辑运算符,运算结果只有“真”,(TRUE),和“假”,(FALSE),两个值,(,称为“逻辑值”,),，,LINGO,中用数字,1,代表,TRUE,，其他值,(,典型的值是,0),都是,FALSE,。,在,LINGO,中，逻辑运算,(,表达式,),通常作为过滤条件使用,逻辑运算符有,9,种，可以分成两类：,#AND#(,与,),#OR#(,或,),#NOT#(,非,),：逻辑值之间的运算，它们操作的对象本身已经是逻辑值或逻辑表达式，计算结果也是逻辑值。,#EQ#(,等于,),#NE#(,不等于,),#GT#(,大于,),#GE#(,大于等于,),#LT#(,小于,),