数学建模
附录B Lingo软件初步
实践中很多问题可归结为如下决策问题：在若干个可行方案中选择一个最优方案，称为最优化问题.最优化问题中，方案用n维向量x?(x1,x2,?,xn)T表示，可行方案集合用?表示，方案x的优劣用指标f(x)衡量.xk(k?1,2,?,n)称为决策变量，f(x)称为目标函数，?称为可行域，常用一组等式或不等式进行界定，这些等式或不等式称为约束条件.
最优化问题的一般形式为：
maxf(x)x??gi(x)?0 i?1,2,...,m （Ⅰ） s..t?h(x)?0 j?1,2,...,l??jx?D?Rn其中如果f(x),gi(x),hj(x)均为线性函数，则问题（Ⅰ）称为线性规划（简称LP）；如果f(x)为二次函数，gi(x),hj(x)为线性函数，则问题（Ⅰ）称为二次规划（QP）；如果决策变量xk（全部或部分）为整数，则问题（Ⅰ）称为整数规划(IP)；如果f(x),gi(x),hj(x)中至少存在一个为非线性函数，则问题（Ⅰ）称为非线性规划（NLP），上述问题通称为数学规划问题.
问题（Ⅰ）中满足约束条件的解称为可行解，使目标函数达到最优的可行解称为最优解，最优解对应的目标函数值称为最优值.
Lingo软件由美国Lindo系统公司研制开发，主要用于求解上述各类数学规划问题.该软件执行速度快，易于输入、修改、求解和分析最优化问题.其详细信息可查阅网站http://www.Lindo.com. B1 Lingo环境
运行Lingo软件时，可得Lingo系统窗口见附图2.1.该窗口的外层是主框架窗口，包含各种菜单命令和工具条，其它所有窗口都被包含在主窗口之下.在主窗口内有一个标题为LINGO Model – LINGO1的窗口，称为Lingo模型窗，所建的模型需在该窗口内编码实现.
248
数学建模
附图2.1 Lingo软件的系统窗口
例B1 求解下面整数规划问题
max z?5x1?10x2?6x3?6x4?x1?4x2?2x3?x4?20?3x?x?3x?5x?30 ?1234s.. t??4x1?2x2?3x3?x4?25?x,x,x,x?{0,Z?}?1234在Lingo1窗口中输入下面指令：
model:
max=5*x1+10*x2+6*x3+6*x4; x1+4*x2+2*x3+x4<=20;
3*x1+x2+3*x3+5*x4<=30; 4*x1+2*x2+3*x3+x4<=25;
@gin(x1);@gin(x2);@gin(x3);@gin(x4);
end
然后点击工具条上的Solve按钮或使用Ctrl+S快捷键便可运行上述Lingo模型，得求解结果如附图2.2所示.
附图2.2 Lingo模型的求解结果窗口
由附图2.2可知，Lingo软件求得了问题的最优值69，相应最优解为(3,3,1,3)，其余信息见B5.1节.此外，求解还给出了关于求解器状态的一个窗口，该窗口列出了所用求解器的状态，扩展求解器的状态，问题所含决策变量和约束条件的统计数据，占用的内存和时间等信息.
应用Lingo软件求解数学规划问题非常方便，但使用时还需注意下面事项：
（1）Lingo中的模型以“model：”开始，以“end”结束，由一系列语句组成，每个语句都以分号“；”结尾.
（2）Lingo中模型的目标函数用“MAX=…；”或“MIN=…；”给出. （3）Lingo中模型的系数与变量之间的乘号不能省略，用“*”表示.
（4）Lingo中的符号不区分大小写，但其变量名不能超过32个字符，且必须以字母开头.
（5）求解数学规划模型时总假定所有变量非负（此假定可以用函数@free取消）. （6）Lingo中所有的函数均以“@”符号开始，如约束中@gin(x1)表示x1为整数.
249
数学建模
（7）Lingo中以感叹号“！”开始的是注释语句，注释语句也必须以分号“；”结尾.
（8）与MATLAB软件相同，Lingo软件也提供了5种算术运算符，分别为：+（加法），-（减法或负号），*（乘法），/（除法）和^（求幂）.
B2 Lingo模型的集
在B1节的例1中，问题的决策变量和约束条件的个数较少，指令输入较为方便，但实际建模时，总会遇到含有大量决策变量或约束条件的问题，难以逐条输入指令，而如果只用较少Lingo指令便可以描述含有较多变量和大量约束条件的数学规划问题，对于求解较大规模问题非常有利，Lingo软件借助集这个概念很好地实现了这一目标.
B2.1 集的定义
集是Lingo建模语言的基础.借助于集，Lingo软件能够用一个单一的、长的、简明的复合公式表示一系列相似的约束，从而可以快速方便地描述规模较大的模型.
集（set）是一组相关对象的集合.集中的每个元素可以有一个或多个相关的特征，称为属性.属性可以已知，也可以是未知待求解.
一个集一般需包含集的名字（set_name）、集的成员（number_list）以及集中成员的属性（attribute_list）三几部分，其形式为：
sets:
Set_name/number_list/:attribute_list； endsets
定义一个集一般有两种方法，一种需要给出成员的命名，称为直接列举法，如：一个名为Student的集，它具有成员John、Mary和Mike，属性有性别sex和年龄age，可定义为：
sets:
Student/John,Mary,Mike/:sex,age; endsets
还有一种称为隐式列举法，它不需要为每个成员命名，只需定义n个成员的序号即可，如：对一个名为col的三维向量b，可作如下定义：
sets:
col/1..3/:b; endsets
?在线性规划中，决策变量和给定数据(如目标函数和线性等式(或不等式)约束中决策变量的系数以及右端自由项)都可以表示为一个向量，因此可以应用隐式列举法将其定义为一个集.
例B2 将例B1中整数规划的决策变量向量和给定数据向量分别定义为集.
?1421???TT解 令c?(5,10,6,6),x?(x1,x2,x3,x4),b?(20,30,25),A?3135，则得
????4231??给定整数规划的矩阵形式如下：
250
数学建模
max z?c?x?Ax?b s.. t???xi?{0,Z},i?1,2,3,4由于问题涉及两个4维向量和一个3维向量，所以定义其Lingo模型的集如下:
sets:
col/1..4/:c,x; var/1..3/:b; endsets
B2.2 基本集与派生集
Lingo软件定义了两类集，一类直接枚举集中的各个成员，称为基本集（primary set），
如B2.1节例B2中定义的两个集col和var；另一类由基本集的成员进行笛卡儿积运算派生得到，称为派生集（derived set），其定义格式如下：
set_name(parent_set_list)[/member_list/][:attribute_list];
其中parent_set_list为派生集set_name的父集，如（set1，set2，…），它们一般是基本集，有时也可以是派生集，member_list为成员列表，attribute_list为属性列表.
在Lingo模型中，所有集(包括基本集和派生集)的定义，其整体为Lingo模型的一个基本要素，称为集段.该基本要素以“sets:”开始，以“endsets”终止，定义Lingo模型的集及其属性.
例B3 写出例B1中整数规划的Lingo模型的集段.
解 根据例B2中整数规划的矩阵形式，可得Lingo模型的集定义部分如下:
sets:
col/1..4/:c,x; var/1..3/:b; mat(var,col):A; endsets
其中集mat为派生集，它由集var和集col派生得到，其成员是上述两个基本集的成员组合成的有序二元组，即
mat?{(s,t)|s?var,t?col}
B2.3 稠密集与稀疏集
在B2.2节例B3中，派生集mat的成员定义为基本集var和col的笛卡儿积，包含了两个基本集构成的所有二元有序对.这种派生集又称为稠密集.
除了稠密集，Lingo软件还定义了一种派生集，其成员为两个基本集构成的部分二元有序对，称为稀疏集，其定义格式为：
set_name（parent_sets）/explicit_list/[：attributes]；
例B4 附图2.3为一个单行线交通网，图中v1,?,v8称为节点；两节点的单行线称为边，边旁边的数字表示通过这条单行线所需的费用，称为权值；此单行线交通网中的边没有方向且带有权值，在图论中称其为无向赋权图.
现在某人要从v1出发，通过此交通网到达v8，请帮其选择一条总费用最小的旅
251
数学建模
行路线.此问题为图论中经典的最短路径问题.
2v2v4v367152v51v63v1189634v8
9v7 附图2.3 交通网路图
图中共有8个节点，可用一个基本集描述；利用所定义的基本集派生可得含有64条边的派生集.然而图中只给出15条边，多引入的边会增加计算资源，所以在派生集中只需含这15条边的信息即可.由此得最短路径问题Lingo模型的集段如下：
sets:
cities/v1..v8/:L; roads(cities,cities)/ v1,v2 v1,v3 v1,v4
v2,v4 v2,v5 v3,v4 v3,v7 v4,v5 v4,v6 v4,v7 v5,v6 v5,v8 v6,v7 v6,v8 v7,v8/:d;
endsets
在上述集段中，基本集“cities”描述图中的各节点，其成员通过枚举给出，L为该集的一个属性，表示各节点到节点v1的最短距离；派生集“roads”由基本集cities和cities派生得到，但只含部分节点之间的边，所以为一个稀疏集，其成员也通过枚举给出，d为派生集roads的一个属性，表示给定各边的费用.
当成员较少时，使用枚举法生成派生集较为方便，但当成员较多时则较为困难，此时可利用“成员过滤法”定义稀疏集，即根据所定义的过滤条件系统的从父集中保留所需的成员，其定义格式如下：
set_name（parent_sets）|condition[：attributes]；
其中condition为过滤条件，一般为逻辑运算（见B3.2），如：“pair（obj，obj）|&2#LT#&1：c，x；”，其过滤条件为&2#LT#&1，表示第2个父集元素的索引值(&2)大于第1个父集元素的索引值(&1)，满足该过滤条件的成员得以保留.
引入概念集后，Lingo软件可将数学规划问题的抽象模型和数据进行分离.在Lingo模型中，问题的所有数据集中在一起，构成Lingo模型的第2个基本要素，称为数据段.该基本要素以“data:”开始，以“enddata”终止，给出各常量的值.
此外，在Lingo模型中有时需在运行时才对某个参数赋值，此时可在数据输入部分用语句“变量名=?”实现.求解时，Lingo系统会给出提示界面，等待用户输入该变量的数值后，再继续执行程序.
例B5 写出例B1中整数规划的Lingo模型的数据段.
data:
c=5 10 6 6;b=20,30,25; A=1 4 2 1 3 1 3 5 4 2 3 1;
enddata
252