1、 优优 化化 建建 模模 LP QP NLP IP 全局优化全局优化(选选)ILP IQP INLP LINGOLINGO软件的求解过程软件的求解过程 LINGO预处理程序预处理程序线性优化求解程序线性优化求解程序非线性优化求解程序非线性优化求解程序分枝定界管理程序分枝定界管理程序1.确定常数确定常数2.识别类型识别类型1.单纯形算法单纯形算法2.内点算法内点算法(选选)1、顺序线性规划法、顺序线性规划法(SLP)2、广义既约梯度法、广义既约梯度法(GRG)(选选)3、多点搜索、多点搜索(Multistart)(选选)优优 化化 建建 模模三、三、LINGO软件的基本使用方法软件的基本使用方法
2、1、Lingo入门入门2、在、在Lingo中使用集合中使用集合3、运算符和函数、运算符和函数4、Lingo的主要菜单命令的主要菜单命令 优优 化化 建建 模模1、Lingo入门入门LINGOLINGO的界面的界面LINGO软件的主窗口（用户界面），软件的主窗口（用户界面），所有其他窗口都在这个窗口之内。所有其他窗口都在这个窗口之内。模型窗口（模型窗口（Model Window），），用于输入用于输入LINGO优化模型优化模型（即（即LINGO程序）。程序）。状态行（最左边显示状态行（最左边显示“Ready”，表示，表示“准备准备就绪就绪”）当前时间当前时间 当前光标的当前光标的位置位置 优优
3、化化 建建 模模简单程序举例：简单程序举例：Lindo程序:max 2x+3yst4x+3y103x+5y12endLingo 程序:MODEL:max=2*x+3*y;4*x+3*y10;3*x+5*y12;end请大家仔细区分它们的不同。请大家仔细区分它们的不同。求求z=2x+3y在约束条件在约束条件4x+3y=10,3x+5y=12下的最大值下的最大值这是这是lingo程序最基本的格式之一程序最基本的格式之一在在lingo模型窗口中输入右框中的程序，并保存为模型窗口中输入右框中的程序，并保存为LG4 格式文件，格式文件，这是这是LINGO格式的模型文件，保存了模型窗口中所能够看到的格式的
4、模型文件，保存了模型窗口中所能够看到的所有文本和其他对象及其格式信息；所有文本和其他对象及其格式信息；在在LINGOLINGO中使用中使用LINDOLINDO模型模型 优优 化化 建建 模模 运行程序运行程序:点点“LINGO菜单菜单Solve 命令命令”或或 按按ctrl+s运行运行 或或 用鼠标点用鼠标点在在LINGOLINGO中使用中使用LINDOLINDO模型模型 优优 化化 建建 模模运行状态窗口运行状态窗口求解器求解器(求解程求解程序序)状态状态框框当前解的状态当前解的状态:Global Optimum,Local Optimum,Feasible,Infeasible“(不可行不
5、可行),Unbounded“(无界无界),Interrupted“(中断中断),Undetermined“(未确定未确定)解的目标函数值解的目标函数值 优优 化化 建建 模模 运行程序的运行程序的LINGO报告窗口（如下图）报告窗口（如下图）在在LINGOLINGO中使用中使用LINDOLINDO模型模型注：注：LINGO不询问是否进行敏感性分析，敏感性分析需要将来通过修改系统选项启动敏感性分析后，不询问是否进行敏感性分析，敏感性分析需要将来通过修改系统选项启动敏感性分析后，再调用再调用“REPORT|RANGE”菜单命令来实现。现在同样可以把模型和结果报告保存在文件中。菜单命令来实现。现在同
6、样可以把模型和结果报告保存在文件中。优优 化化 建建 模模一个简单的一个简单的LINGO程序程序例例 直接用LINGO来解如下二次规划问题：40,322100.123.02779821212122212121为整数xxxxxxtsxxxxxxMax输入窗口如下：输入窗口如下：优优 化化 建建 模模程序语句输入的备注：程序语句输入的备注：max=98*x1+277*x2-x12-0.3*x1*x2-2*x22;LINGO总是根据总是根据“MAX=”或或“MIN=”寻找目标函数。寻找目标函数。gin(x1);gin(x2);限定变量取整数值的语句为限定变量取整数值的语句为“GIN(X1)”和和“G
7、IN(X2)”LINGO中函数一律需要以中函数一律需要以“”开头。开头。BIN(x)限定变量限定变量x为为0/1变量函数变量函数FREE(x)设定变量设定变量x的取值范围为实数。的取值范围为实数。注意：如果注意：如果0/1变量的个数很多，还可以采用循环语句设定。变量的个数很多，还可以采用循环语句设定。优优 化化 建建 模模选择全局求解的方法：点 Lindo菜单optionsGlobal Solver,在use Global Solver前打钩。点 save,应用，ok.然后运行这个程序 优优 化化 建建 模模输出结果：输出结果：最优整数解最优整数解X=(35，65)最大利润最大利润=11077
8、.5 优优 化化 建建 模模一个简单的一个简单的LINGO程序程序LINGO的基本用法的几点注意事项的基本用法的几点注意事项 LINGO中不区分大小写字母；变量和行名可以超过8个字符，但不能超过32个字符，且必须以字母开头。用LINGO解优化模型时已假定所有变量非负(除非用限定变量取值范围的函数free或sub或slb另行说明)。变量可以放在约束条件的右端(同时数字也可放在约束条件的左端)。但为了提高LINGO求解时的效率，应尽可能采用线性表达式定义目标和约束(如果可能的话)。语句是组成LINGO模型的基本单位,每个语句都以分号结尾，编写程序时应注意模型的可读性。例如：一行只写一个语句，按照语
9、句之间的嵌套关系对语句安排适当的缩进，增强层次感。以感叹号开始的是说明语句(说明语句也需要以分号结束)）。优优 化化 建建 模模课堂练习：求解下列模型且为整数,0,;2054;62;max21212121xxxxxxxxz22121222121212min (,)(3)(2)50 240 ,0f x xxxstxxxxx x22121222122min (,)(1)(1)20 10f x xxxstxxx 优优 化化 建建 模模二、集合的基本用法和二、集合的基本用法和LINGO模型的基本要素模型的基本要素 理解理解LINGO建模语言最重要的是理解集合（建模语言最重要的是理解集合（Set）及其属
10、性（）及其属性（Attribute）的概念。）的概念。优优 化化 建建 模模例例 SAILCO公司需要决定下四个季度的帆船生产量。下四个季度的帆船需求量分别是公司需要决定下四个季度的帆船生产量。下四个季度的帆船需求量分别是40条，条，60条，条，75条，条，25条，这些需求必须按时满足。每个季度正常的生产能力是条，这些需求必须按时满足。每个季度正常的生产能力是40条帆船，每条船的生产费用为条帆船，每条船的生产费用为400美元。美元。如果加班生产，每条船的生产费用为如果加班生产，每条船的生产费用为450美元。每个季度末，每条船的库存费用为美元。每个季度末，每条船的库存费用为20美元。假定生产提美
11、元。假定生产提前期为前期为0，初始库存为，初始库存为10条船。如何安排生产可使总费用最小？条船。如何安排生产可使总费用最小？DEM,RP,OP,INV对每个季度都应该有一个对应的值，也就说他们都应该是一个由对每个季度都应该有一个对应的值，也就说他们都应该是一个由4个元素组成的数组，个元素组成的数组，其中其中DEM是已知的，而是已知的，而RP,OP,INV是未知数。是未知数。第一季度第一季度 第二季度第二季度 第三季度第三季度 第四季度第四季度DEM:需求量需求量(为已知为已知)40 60 75 25RP:正常生产的产量正常生产的产量 OP:加班生产的产量加班生产的产量 INV:库存量库存量总费
12、用：四个季度的（生产费用总费用：四个季度的（生产费用+加班费用加班费用+库存费用）库存费用）设设 优优 化化 建建 模模问题的模型问题的模型(可以看出是可以看出是LP模型模型)目标函数是所有费用的和目标函数是所有费用的和4,3,2,1)(20)(450)(400MINIIINVIOPIRP 约束条件主要有两个：约束条件主要有两个：1）能力限制：）能力限制：RP()40,1,2,3,4II2）产品数量的平衡方程：）产品数量的平衡方程：()(1)()()(),1,2,3,4INV IINV IRP IOP IDEM II10)0(INV加上变量的非负约束加上变量的非负约束正常生产的产量正常生产的产
13、量加班产量加班产量库存量库存量 优优 化化 建建 模模注：注：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称为该集合的属性(即定义在该集合上的属
14、性)。优优 化化 建建 模模QUARTERS集合的属性DEM RPOP INVQUARTERS集合2341 集合及其属性集合及其属性 优优 化化 建建 模模集合元素及集合的属性确定的所有变量集合元素及集合的属性确定的所有变量集合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中定义集合及其属性中定义集合及其属性 LP模型在模型在LINGO中的一个典型输入
15、方式中的一个典型输入方式 以以“MODEL：”开始开始 以以“END”结束结束集合定义部分从集合定义部分从(“SETS：”到到“ENDSETS”)：定义集合及其：定义集合及其属性属性集合定义部分从集合定义部分从(“DATA：”到到“ENDDATA”)给出优化目标和约束给出优化目标和约束 优优 化化 建建 模模目标函数的定义方式目标函数的定义方式对语句中冒号对语句中冒号“：”后面的表达式，按照后面的表达式，按照“：”前面的集合指定的下标（元素）进行求和。前面的集合指定的下标（元素）进行求和。本例中目标函数也可以等价地写成本例中目标函数也可以等价地写成SUM(QUARTERS(i):400*RP(
16、i)+450*OP(i)+20*INV(i)，“SUM”相当于求和符号相当于求和符号“”，由于本例中目标函数对集合由于本例中目标函数对集合QUARTERS的所有元素的所有元素(下标下标)都要求和，所以可以将下标都要求和，所以可以将下标i省去。省去。min=sum(Quarters:400*RP+450*OP+20*INV);SUM(集合（下标）：关于集合的属性的表达式集合（下标）：关于集合的属性的表达式)优优 化化 建建 模模约束的定义方式约束的定义方式循环函数循环函数FOR(集合集合(下标下标)：关于集合的属性的约束关系式：关于集合的属性的约束关系式)对冒号对冒号“：”前面的集合的每个元素（
17、下标），冒号前面的集合的每个元素（下标），冒号“：”后面的约束关系式都要成立后面的约束关系式都要成立 本例中，每个季度正常的生产能力是本例中，每个季度正常的生产能力是40条帆船，这正是语句条帆船，这正是语句“FOR(QUARTERS(I):RP(I)40);”的含的含义。义。这个语句可以简化成这个语句可以简化成“FOR(QUARTERS:RP40);”。for(quarters(I):RP(I)1；“#GT#”是逻辑运算符号，意思是是逻辑运算符号，意思是“大于大于（Greater Than的字首字母缩写）的字首字母缩写）”。约束的定义方式约束的定义方式()(1)()()(),1,2,3,4IN
18、V IINV IRP IOP IDEM II10)0(INV 优优 化化 建建 模模问题的求解：运行菜单命令问题的求解：运行菜单命令“LINGO|Solve”全局最优解全局最优解RP=(40,40,40,25),OP=(0,10,35,0)最小成本最小成本=78450 优优 化化 建建 模模Lingo模型的基本结构模型的基本结构（1）集合段（）集合段（SETS）：）：sets:Quarters/1,2,3,4/:DEM,RP,OP,INV,I;endsets或者或者 sets:Quarters/1.4/:DEM,RP,OP,INV,I;endsets（2）目标与约束段：）目标与约束段：min=
19、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);优优 化化 建建 模模（3）数据段）数据段(DATA)：DATA:DEM=40,60,75,25;（或写成（或写成DEM=40 60 75 25；）；）Enddata 优优 化化 建建 模模（4 4）初始段）初始段(INIT)(INIT)：以：以“INIT:”开始，开始，“ENDINIT”结束，对集合
20、的属性结束，对集合的属性(数组数组)定义初值定义初值(因为求解因为求解算法一般是迭代算法，所以用户如果能给出一个比较好的迭代初值，对提高算法的计算效果是有益的算法一般是迭代算法，所以用户如果能给出一个比较好的迭代初值，对提高算法的计算效果是有益的)。如果有一个接近最优解的初值，对如果有一个接近最优解的初值，对LINGO求解模型是有帮助的。定义初值的格式为：求解模型是有帮助的。定义初值的格式为：“attribute（属性）（属性）=value_list（常数列表）；（常数列表）；”这与数据段中的用法是类似的。这与数据段中的用法是类似的。上例中没有初始化部分，我们将在下一个例子中举例说明。上例中没
21、有初始化部分，我们将在下一个例子中举例说明。优优 化化 建建 模模（5 5）计算段）计算段(CALC)(CALC)：以：以“CALC:”开始，开始，“ENDCALC”结束，对一些原始数据进行计算处理。结束，对一些原始数据进行计算处理。在实际问题中，输入的数据通常是原始数据，不一定能在模型中直接使用，可以在这个段对这些原在实际问题中，输入的数据通常是原始数据，不一定能在模型中直接使用，可以在这个段对这些原始数据进行一定的始数据进行一定的“预处理预处理”，得到模型中真正需要的数据。，得到模型中真正需要的数据。例如上例，如果希望得到全年的总需求和季度平均需求，可以增加这个段：例如上例，如果希望得到全
22、年的总需求和季度平均需求，可以增加这个段：CALC:T_DEM=SUM(quarters:DEM);!总需求总需求;A_DEM=T_DEM/size(quarters);!平均需求平均需求;ENDCALC在计算段中也可以使用集合函数（其中函数在计算段中也可以使用集合函数（其中函数size(quarters)表示集合表示集合quarters的元素个数，这里也就是的元素个数，这里也就是4）。这时，变量）。这时，变量T_DEM的值就是总需求，的值就是总需求，A_DEM的值就是平均需求（如果需要的话，这两个变的值就是平均需求（如果需要的话，这两个变量就可以在程序的其它地方作为常数使用了）。量就可以在程
23、序的其它地方作为常数使用了）。注：上面的两个语句不能交换顺序，因为计算注：上面的两个语句不能交换顺序，因为计算A_DEM必须要用到必须要用到T_DEM的值。此外，在计算段中只能的值。此外，在计算段中只能直接使用赋值语句，而不能包含需要经过解方程或经过求解优化问题以后才能决定的变量。直接使用赋值语句，而不能包含需要经过解方程或经过求解优化问题以后才能决定的变量。优优 化化 建建 模模基本集合与派生集合基本集合与派生集合 例例3.4 建筑工地的位置建筑工地的位置(用平面坐标用平面坐标a,b表示，距离单位：公里表示，距离单位：公里)及水泥日用量及水泥日用量d(吨吨)下表给出。有两个临时下表给出。有两
24、个临时料场位于料场位于P(5,1),Q(2,7),日储量各有日储量各有20吨。从吨。从A,B两料场分别向各工地运送多少吨水泥，使总的吨公里两料场分别向各工地运送多少吨水泥，使总的吨公里数最小。两个新的料场应建在何处，节省的吨公里数有多大？数最小。两个新的料场应建在何处，节省的吨公里数有多大？a1.258.750.55.7537.25b1.250.754.7556.57.75d3547611 优优 化化 建建 模模建立模型建立模型记工地的位置为记工地的位置为 ，水泥日用量为，水泥日用量为 ；料场位置为；料场位置为 ，日储量为，日储量为 ；从料场；从料场 向工向工地地 的运送量为的运送量为 。),
25、(iiba6,1,idi),(jjyx2,1,jejjiijc 2622112161MIN1s.t.,1,2,62,1,23ijjijijiijijijjifcxayacdicej使用现有临时料场时，决策变量只有使用现有临时料场时，决策变量只有 （非负），所以这是（非负），所以这是LP模型；当为新建料场选址时决策变量为模型；当为新建料场选址时决策变量为 和和 ，由于目标函数，由于目标函数 对对 是非线性的，所以在新建料场时是是非线性的，所以在新建料场时是NLP模型。先解模型。先解NLP模型，而把现模型，而把现有临时料场的位置作为初始解告诉有临时料场的位置作为初始解告诉LINGO。ijcijcj
26、jyx,fjjyx,优优 化化 建建 模模输入程序输入程序 定义了三个集合，其中定义了三个集合，其中LINK在前两个集合在前两个集合DEMAND 和和SUPPLY的基础上定义的基础上定义表示集合表示集合LINK中的元素就是集合中的元素就是集合DEMAND 和和SUPPLY的元的元素组合成的有序二元组，素组合成的有序二元组，从数学上看从数学上看LINK是是DEMAND 和和SUPPLY的笛卡儿积，也就的笛卡儿积，也就是说是说LINK=（S，T）|SDEMAND，TSUPPLY因此，其属性因此，其属性C也就是一个也就是一个6*2的矩阵（或者说是含有的矩阵（或者说是含有12个元个元素的二维数组）。素
27、的二维数组）。LINGO建模语言也称为矩阵生成器（建模语言也称为矩阵生成器（MATRIX GENERATOR）。类似）。类似DEMAND 和和SUPPLY直接把元直接把元素列举出来的集合，称为基本集合素列举出来的集合，称为基本集合(primary set),而把而把LINK这种基于其它集合而派生出来的二维或多维这种基于其它集合而派生出来的二维或多维集合称为派生集合集合称为派生集合(derived set)。由于是。由于是DEMAND 和和SUPPLY生成了派生集合生成了派生集合LINK，所以，所以DEMAND 和和SUPPLY 称为称为LINK的父集合。的父集合。优优 化化 建建 模模输入程序
28、输入程序 初始段 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；优优 化化 建建 模模输入程序输入程序 优优 化化 建建 模模解答解答:运行菜单命令运行菜单命令“LINGO|Solve”局部最优解局部最优解X(1)=7.249997，X(2)=5.695940，Y(1)=7.749998，Y(2)=4.928524，C（略），（
29、略），最小运量最小运量=89.8835(吨公里吨公里)。问题问题:最小运量最小运量89.8835是不是全局最优是不是全局最优 是用是用“LINGO|Options”菜单命令打开选项对话框，在菜单命令打开选项对话框，在“Global Solver”选项卡上选择选项卡上选择“Use Global Solver”,激活全局最优求解程序。激活全局最优求解程序。优优 化化 建建 模模稠密集合与稀疏集合稠密集合与稀疏集合 包含了两个基本集合构成的所有二元有序对的派生集合称为稠密集合包含了两个基本集合构成的所有二元有序对的派生集合称为稠密集合(简称稠集简称稠集)。有时候，在实际问题中，。有时候，在实际问题中
30、，一些属性一些属性(数组数组)只在笛卡儿积的一个真子集合上定义，这种派生集合称为稀疏集合只在笛卡儿积的一个真子集合上定义，这种派生集合称为稀疏集合(简称疏集简称疏集)。例例(最短路问题最短路问题)在纵横交错的公路网中，货车司机希望找到一条从一个城市到另一个城市的最短路在纵横交错的公路网中，货车司机希望找到一条从一个城市到另一个城市的最短路.下图下图表示的是公路网表示的是公路网,节点表示货车可以停靠的城市节点表示货车可以停靠的城市,弧上的权表示两个城市之间的距离弧上的权表示两个城市之间的距离(百公里百公里).那么那么,货车从货车从城市城市S出发到达城市出发到达城市T,如何选择行驶路线如何选择行驶
31、路线,使所经过的路程最短使所经过的路程最短?STA1 A2 A3 B1 B2 C1 C2 633665874678956 优优 化化 建建 模模STA1 A2 A3 B1 B2 C1 C2 633665874678956分析分析 假设从假设从S到到T的最优行驶路线的最优行驶路线 P 经过城市经过城市C1,则则P中从中从S到到C1的子路也一定是从的子路也一定是从S到到C1的最优行驶路线的最优行驶路线;假设假设 P 经过城市经过城市C2,则则P中从中从S到到C2的子路也一定是从的子路也一定是从S到到C2的最优行驶路线的最优行驶路线.因此因此,为得到从为得到从S到到T的最优行驶路线的最优行驶路线,只
32、需要先求出从只需要先求出从S到到Ck(k=1,2)的最优行驶路线的最优行驶路线,就可以方便地得到从就可以方便地得到从S到到T的最优行驶路线的最优行驶路线.同样同样,为了求出从为了求出从S到到Ck(k=1,2)的最优行驶路线的最优行驶路线,只需要先求出从只需要先求出从S到到Bj(j=1,2)的最优行驶路线的最优行驶路线;为了求出从为了求出从S到到Bj(j=1,2)的最优行驶路线的最优行驶路线,只需要先求出从只需要先求出从S到到Ai(i=1,2,3)的最优行驶路线的最优行驶路线.而而S到到Ai(i=1,2,3)的最优行驶路线是很容易得到的的最优行驶路线是很容易得到的(实际上实际上,此例中此例中S到
33、到Ai(i=1,2,3)只有唯一的道路只有唯一的道路)优优 化化 建建 模模分析分析 STA1 A2 A3 B1 B2 C1 C2 633665874678956此例中可把从S到T的行驶过程分成4个阶段,即 SAi(i=1,2或3),Ai Bj(j=1或2),Bj Ck(k=1或2),Ck T.记d(Y,X)为城市Y与城市X之间的直接距离(若这两个城市之间没有道路直接相连，则可以认为直接距离为)，用L(X)表示城市S到城市X的最优行驶路线的路长:0;1min,.2YXL SL XL Yd Y XXS 优优 化化 建建 模模本例的计算本例的计算 1231123321233112221221216
34、,3,3;min6,8,7107;min5,6,474;min6,8158;min7,9169;min5,6205.L AL AL AL BL AL AL AL AL BL AL AL AL AL CL BL BL BL CL BL BL BL TL CL CL CSTA1 A2 A3 B1 B2 C1 C2 633665874678956所以,从S到T的最优行驶路线的路长为20.进一步分析以上求解过程,可以得到从S到T的最优行驶路线为S A3 B2 C1 T.这种计算方法在数学上称为动态规划(Dynamic Programming)优优 化化 建建 模模本例的本例的LINGO求解求解“CIT
35、IES”(城市城市):一个基本集合一个基本集合(元素通过枚举给出元素通过枚举给出)L:CITIES对应的属性变量对应的属性变量(我们要求的最短路长我们要求的最短路长)“ROADS”(道路):由CITIES导出的一个派生集合(请特别注意其用法),由于只有一部分城市之间有道路相连，所以不应该把它定义成稠密集合，将其元素通过枚举给出，这就是一个稀疏集合。D:稀疏集合ROADS对应的属性变量(给定的距离)优优 化化 建建 模模本例的本例的LINGO求解求解从模型中还可以看出：这个从模型中还可以看出：这个LINGO程序可以没有目标函数，这在程序可以没有目标函数，这在LINGO中，可以用来找可行解中，可以
36、用来找可行解(解方程解方程组和不等式组组和不等式组)。在数据段对在数据段对L进行赋值，只有进行赋值，只有L(S)=0已知，后面的值已知，后面的值为空为空(但位置必须留出来，即逗号但位置必须留出来，即逗号“，”一个也不能一个也不能少，否则会出错少，否则会出错)。如果这个语句直接写成。如果这个语句直接写成“L=0；”，语法上看也是对的，但其含义是语法上看也是对的，但其含义是L所有元素的取值全所有元素的取值全部为部为0，所以也会与题意不符。，所以也会与题意不符。优优 化化 建建 模模本例的本例的LINGO求解求解虽然集合虽然集合CITIES中的元素不是数字，但当它以中的元素不是数字，但当它以CITI
37、ES(I)的形式出现在循环中时，引用下标的形式出现在循环中时，引用下标I却实际上仍是正整数，却实际上仍是正整数，也就是说也就是说I指的正是元素在集合中的位置指的正是元素在集合中的位置(顺序顺序)，一般称为，一般称为元素的索引元素的索引(INDEX)。在在for循环中的过滤条件里用了一个函数循环中的过滤条件里用了一个函数“index”,其其作用是返回一个元素在集合中的索引值，这里作用是返回一个元素在集合中的索引值，这里index(S)=1(即元素即元素S在集合中的索引值为在集合中的索引值为1)，所以逻辑，所以逻辑关系式关系式“I#GT#index(S)”可以可以直接等价地写成可以可以直接等价地写
38、成“I#GT#1”。这里。这里index(S)实际上还是实际上还是index(CITIES,S)的简写，即返回的简写，即返回S在集合在集合CITIES中的索中的索引值。引值。优优 化化 建建 模模本例的本例的LINGO求解结果求解结果从S到T的最优行驶路线的路长为20(进一步分析，可以得到最优行驶路线为S A3 B2 C1 T)。本例中定义稀疏集合本例中定义稀疏集合ROADS的方法是将其元素通过枚举给出，有时如果元素比较多，用起来不方便。另的方法是将其元素通过枚举给出，有时如果元素比较多，用起来不方便。另一种定义稀疏集合的方法是一种定义稀疏集合的方法是“元素过滤元素过滤”法，能够从笛卡儿积中系
39、统地过滤下来一些真正的元素。法，能够从笛卡儿积中系统地过滤下来一些真正的元素。优优 化化 建建 模模例例 某班某班8名同学准备分成名同学准备分成4个调查队个调查队(每队两人每队两人)前往前往4个地区进行社会调查。这个地区进行社会调查。这8名同学两两之间组队的名同学两两之间组队的效率如下表所示效率如下表所示(由于对称性，只列出了严格上三角部分由于对称性，只列出了严格上三角部分)，问如何组队可以使总效率最高？，问如何组队可以使总效率最高？学生S1S2S3S4S5S6S7S8S1-9342156S2-173521S3-44292S4-1552S5-876S6-23S7-4 优优 化化 建建 模模分析
40、分析 这是一个匹配（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线性规划)：31
41、.0)(21,2,3,4,I 1,)(.1),(),(II，或J,KMATCHJ,KMATCHtsJI*MATCHJIBENEFITMinKJJI 优优 化化 建建 模模问题的问题的LINGO求解求解“S1.S8”等价于写成“S1 S2 S3 S4 S5 S6 S7 S8”,它没有相关的属性列表，只用于表示是一个下标集合 在派生集合PAIRS定义中增加了过滤条件“&2#GT#&1”,意思是第2个父集合的元素的索引值(用“&2”表示)大于第1个父集合的元素的索引值(用“&1”表示)。PAIRS中的元素对应于上表中的严格上三角部分的二维下标(共28个元素)。BENEFIT和MATCH是PAIRS的
42、属性。注意数据段对BENEFIT的赋值方式，“LINGO按照列的顺序对属性变量的元素进行赋值。在约束部分，过滤条件“J#EQ#I#OR#K#EQ#I”是由逻辑运算符“#OR#（或者）”连接的一个复合的逻辑关系式，连接由“#EQ#（等于）”表示的两个逻辑关系。由于“#OR#”的运算级别低于“#EQ#”，所以这个逻辑式中没有必要使用括号指定运算次序。优优 化化 建建 模模LINGO求解结果求解结果“LINGO|SOLVE”运行这个程序，可以得到全局最优值为30 MATCH变量中多数为0，可以更清晰地浏览最优解解。选择菜单命令“LINGO|SOLUTION”，可以看到图示对话框。选择属性MATCH(
43、变量)选择Text(文本格式)选择Nonzeros Only(只显示非零值)点击“OK”按钮，得到关于最优解的非零分量的报告学生最佳的组队方式是学生最佳的组队方式是(1,8),(2,4),(3,7),(5,6).优优 化化 建建 模模集合的使用小结集合的使用小结 集合的不同类型及其关系集合的不同类型及其关系 集合集合派生集合派生集合稀疏集合稀疏集合稠密集合稠密集合基本集合基本集合元素列表法元素列表法 元素过滤法元素过滤法 直接列举法直接列举法 隐式列举法隐式列举法 优优 化化 建建 模模基本集合的定义语法基本集合的定义语法 基本集合的定义格式为(方括号“”中的内容是可选项,可以没有):setn
44、ame/member_list/:attribute_list;其中setname为定义的集合名，member_list为元素列表，attribute_list为属性列表。元素列表可以采用显式列举法(即直接将所有元素全部列出,元素之间用逗号或空格分开),也可以采用隐式列举法。隐式列举法可以有几种不同格式，类型隐式列举格式示例示例集合表示的元素数字型1.n1.51,2,3,4,5字符-数字型stringM.stringNCar101.car208Car101,car102,car208日期（星期）型dayM.dayNMON.FRIMON,TUE,WED,THU,FRI月份型monthM.mont
45、hNOCT.JANOCT,NOV,DEC,JAN年份-月份型monthYearM.monthYearNOCT2001.JAN2002OCT2001,NOV2001,DEC2001,JAN2002 优优 化化 建建 模模 元素列表和属性列表都是可选的。当属性列表不在集合定义中出现时，这样的集合往往只是为了将来在程序中作为一个循环变量来使用,或者作为构造更复杂的派生集合的父集合使用(匹配问题中的集合STUDENTS没有属性列表)。而当元素列表不在基本集合的定义中出现时,则必须在程序的数据段以赋值语句的方式直接给出元素列表。例如，前例中SAILCO公司决定四个季度的帆船生产量模型的集合段和数据段可以
46、分别改为：SETS:QUARTERS:DEM,RP,OP,INV;!注意没有给出集合的元素列表;ENDSETSDATA:QUARTERS DEM=1 40 2 60 3 75 4 25;!注意LINGO按列赋值的特点;ENDDATA基本集合的定义语法基本集合的定义语法 帆船生产量模型的源程序匹配问题的源程序 优优 化化 建建 模模派生集合的定义语法派生集合的定义语法 派生集合的定义格式为(方括号“”中的内容是可选项,可以没有):setname(parent_set_list)/member_list/:attribute_list;与基本集合的定义相比较多了一个parent_set_list(
47、父集合列表)。父集合列表中的集合(如 set1，set2，等)称为派生集合setname的父集合，它们本身也可以是派生集合。当元素列表(member_list)不在集合定义中出现时，还可以在程序的数据段以赋值语句的方式给出元素列表；若在程序的数据段也不以赋值语句的方式给出元素列表，则认为定义的是稠密集合，即父集合中所有元素的有序组合(笛卡儿积)都是setname的元素。当元素列表在集合定义中出现时，又有“元素列表法”(直接列出元素)和“元素过滤法”(利用过滤条件)两种不同方式。优优 化化 建建 模模3.运算符和函数运算符和函数 LINGO入门入门2.在在LINGO中使用集合中使用集合3.运算符
48、和函数运算符和函数4.LINGO的主要菜单命令的主要菜单命令5.LINGO命令窗口命令窗口 6.习题 优优 化化 建建 模模运算符及其优先级运算符及其优先级 算术运算符算术运算符加、减、乘、除、乘方等数学运算(即数与数之间的运算，运算结果也是数)。LINGO中的算术运算符有以下5种：+（加法），（减法或负号），*（乘法），/（除法），(求幂)。优优 化化 建建 模模逻辑运算符逻辑运算符运算结果只有“真”(TRUE)和“假”(FALSE)两个值(称为“逻辑值”)，LINGO中用数字1代表TRUE，其他值(典型的值是0)都是FALSE。在LINGO中，逻辑运算(表达式)通常作为过滤条件使用,逻辑运
49、算符有9种，可以分成两类：#AND#(与),#OR#(或),#NOT#(非)：逻辑值之间的运算，它们操作的对象本身已经是逻辑值或逻辑表达式，计算结果也是逻辑值。#EQ#(等于),#NE#(不等于),#GT#(大于),#GE#(大于等于),#LT#(小于),#LE#(小于等于)：是“数与数之间”的比较,也就是它们操作的对象本身必须是两个数,计算得到的结果是逻辑值。优优 化化 建建 模模关系运算符关系运算符表示是“数与数之间”的大小关系，在LINGO中用来表示优化模型的约束条件。LINGO中关系运算符有3种：(即(即=，大于等于)(在优化模型中约束一般没有严格小于、严格大于关系)运算符的优先级运算
50、符的优先级 优先级最高 最低运算符#NOT#(负号)*/+(减法)#EQ#NE#GT#GE#LT#LE#AND#OR#优优 化化 建建 模模基本的数学函数基本的数学函数 在LINGO中建立优化模型时可以引用大量的内部函数,这些函数以”打头。LINGO中包括相当丰富的数学函数,这些函数的用法非常简单,下面一一列出。ABS(X)：绝对值函数，返回X的绝对值。COS(X)：余弦函数，返回X的余弦值（X的单位是弧度）。EXP(X)：指数函数，返回eXFLOOR(X)：取整函数，返回X的整数部分(向最靠近0的方向取整)。LGM(X)：返回X的伽玛(gamma)函数的自然对数值(当X为整数时LGM(X)=
