【研讨会专题报道】第四期

厚积薄发

Lingo中的集合

madio（数学中国站长）

Lindo 和 Lingo 是美国 Lindo 系统公司开发的一套专门用于求解最优化问题的软件包。Lindo 用于求解线性规划和二次规划问题,Lingo 除了具有 Lindo 的全部功能外,还可以用于求解非线性规划问题,也可以用于一些线性和非线性方程（组）的求解,等等。Lindo 和 Lingo 软件的最大特色在于可以允许优化模型中的决策变量是整数（即整数规划）,而且执行速度很快。据lindo公司人员介绍最新的12..0版本可以轻松解决2亿个变量的整数规划问题。由于很多现实问题都可以在一定程度上化为优化问题，且大部分都是整数规划问题，因此Lingo在现实应用中非常重要。应用的范围包含生产线规划、运输、财务金融、投资分配、资本预算、混合排程、库存管理、资源配置等等。

Lingo不仅仅是一个软件工具，而且是一种建模语言，我们可以用Lingo的语言来描述优化模型。在LINGO语言的模型中,集合及其属性的使用占据了相当重要的作用。集合能够实现只输入少数几行文字就能建立起含有大规模变量的目标函数或成千上万条约束条件的数学模型。我觉得这个是Lingo最大的特色，所以专门拿出来和大家讨论一下！

二、集合的定义和基本用法

(一)集合的定义

集合(set)是一组相关对象的全体,一个集合可以由一系列产品、任务或时间组成。集合的定义包含以下几个部分:集合的名字(setname);集合的成员(member_list);集合中成员的属性(attribute_list)。其表达式为以“SETS:”开始,以“ENDSETS”结束,各字母不区分大小写,集合成员之间可以以逗号或空格分开,各属性之间也以逗号分开。

一般形式为(以下语法中凡是在方括号“[]”中的内容,表示是可选项,即该项可以有也可以没有):

SETS:

setname[/member_list/][:attribute_list];

ENDSETS

当隐式罗列成员时，不必罗列出每个集成员。可采用如下语法：

setname/member1..memberN/[: attribute_list];

这里的member1是集的第一个成员名，memberN是集的最末一个成员名。LINGO将自动产生中间的所有成员名。LINGO也接受一些特定的首成员名和末成员名，用于创建一些特殊的集。

可以把集、集成员和集属性同C语言中的结构体作个类比。如下图：

集 ←→ 结构体

集成员 ←→ 结构体的域

集属性 ←→ 结构体实例

(二)LINGO软件的数据段

在集合的使用过程中,通常需要事先给出集合中的某些属性赋值以便LINGO求解,这些赋值构成LINGO的数据段。因此,LINGO中的数据段一般与集合搭配使用。数据段的表达式以“DATA:”开始,以“ENDDATA”结束。常数列表(value_list)中的数据之间以逗号或空格分开,一般形式为

DATA:

attribute=value_list(常数列表);

ENDDATA

集成员不放在集定义中，而在随后的数据部分来定义。

例2.2

!集部分;

sets:

students:**,age;

endsets

!数据部分;

data:

students,**,age= John 1 16

Jill 0 14

Rose 0 17

Mike 1 13;

Enddata

注意：开头用感叹号（!），末尾用分号（;）表示注释，可跨多行。

在集部分只定义了一个集students，并未指定成员。在数据部分罗列了集成员John、Jill、Rose和Mike，并对属性**和age分别给出了值。

(三)集合循环函数

集合循环函数是指对集合上的元素(一般指下标)进行循环操作的函数。常见循环函数有以下几个:

1.@SUM(集合属性的求和函数):返回集合上的表达式的和

基本格式为:@SUM(集合(下标):关于集合属性的表达式)。该函数的功能是对语句中冒号“:”后面的表达式,按照“:”前面的集合指定的下标进行求和。

2.@FOR(集合元素的循环函数)

基本格式为:@FOR(集合(下标)[|逻辑关系式]:关于集合属性的约束关系式)。

在上述基本格式中,“逻辑关系式”是可选项,使用时在逻辑关系式前要加“|”;该函数的功能是对冒号“:”前面集合的每个元素(下标),冒号“:”后面的约束关系式都要成立。

3..
@in(set_name,primitive_index_1 [,primitive_index_2,…])

如果元素在指定集中，返回1；否则返回0。

4.
@index([set_name,] primitive_set_element)

该函数返回在集set_name中原始集成员primitive_set_element的索引。如果set_name被忽略，那么LINGO将返回与primitive_set_element匹配的第一个原始集成员的索引。如果找不到，则产生一个错误。

5.
@wrap(index,limit)

该函数返回j=index-k*limit，其中k是一个整数，取适当值保证j落在区间[1，limit]

该函数相当于index模limit再加1。该函数在循环、多阶段计划编制中特别有用.

三、集合的分类

(一)基本集合与派生集合

LINGO软件中可以定义和使用的集合有两种:基本集合和派生集合。我们前面定义的集合都是基本集合;而由其他集合派生出来的二维或**集合称为派生集合。派生集合的一般定义格式为:

setname(parent_set_list)[/member_list/][:attribute_list];

其中与基本集合的定义相比较只是多一个parent_set_list(父集合列表).父集合列表中的集合(如set1,set2,…)称为派生集合setname的父集合,这些父集合本身可以是基本集合也可以是派生集合。派生集合又分为稠密集合和稀疏集合两种。

(二)稠密集合

包含了个基本集合构成的所有元有序对,这种派生集合称为稠密集合(简称稠集),它的一般定义形式为

setname(parent_set_list)[:attribute_list];

(三)稀疏集合

如果派生集合中的元素并没有包含基本集合构成的有序对的所有元素,或者说派生集合中的元素是有序对的真子集,这种派生集合称为稀疏集合(简称疏集)。
它的一般定义形式为

setname(parent_set_list)/explicit_list/[:attribute_list];

例:(最短路问题)已知图中各城市之间的连线及连线上的距离,问应选择哪一条路线,使从A到E的总的路程为最短?

sets:

CITIES/A,B1,B2,B3,C1,C2,C3,D1,D2,E/:L;

ROADS(CITIES,CITIES)/A,B1 A,B2 A,B3 B1,C1 B1,C2 B1,C3 B2,C1 B2,C2 B2,C3

B3,C1 B3,C2 B3,C3 C1,D1 C1,D2 C2,D1,C2,D2 C3,D1 C3,D2 D1,E D2,E/:D;

ENDSETS

DATA:

D=2 5 3 7 5 6 3 2 4 5 1 5 1 4 6 3 3 3 3 4;

L=0, , , , , , , , ,;

ENDDATA

@FOR(CITIES(I)|I#GT#1:L(I)=@MIN(ROADS(J,I):L(J)+D(J,I)););

END

Feasible solution found.

Total solver iterations:
0

Variable
Value

L( A)
0.000000

L( B1)
2.000000

L( B2)
5.000000

L( B3)
3.000000

L( C1)
8.000000

L( C2)
4.000000

L( C3)
8.000000

L( D1)
9.000000

L( D2)
7.000000

L( E)
11.00000

D( A, B1)
2.000000

D( A, B2)
5.000000

D( A, B3)
3.000000

D( B1, C1)
7.000000

D( B1, C2)
5.000000

D( B1, C3)
6.000000

D( B2, C1)
3.000000

D( B2, C2)
2.000000

D( B2, C3)
4.000000

D( B3, C1)
5.000000

D( B3, C2)
1.000000

D( B3, C3)
5.000000

D( C1, D1)
1.000000

D( C1, D2)
4.000000

D( C2, D1)
6.000000

D( C2, D2)
3.000000

D( C3, D1)
3.000000

D( C3, D2)
3.000000

D( D1, E)
3.000000

D( D2, E)
4.000000

Row
Slack or Surplus

1
0.000000

2
0.000000

3
0.000000

4
0.000000

5
0.000000

6
0.000000

7
0.000000

8
0.000000

9
0.000000

在上述程序中,基本集合为CITIES,共有十个元素,代表十个城市,属性L(I)表示城市A到城市I的最优路线的长度。派生集合ROADS代表的是上面图形中的道路(弧),其元素是任意连线的两城市。由于并非所有城市都有道路相连,即派生集合中的元素并没有包含基本集合构成的有序对的所有元素,所以该派生集合是稀疏集合。属性D(I,J)是城市I到城市J的直接距离。 LINGO求解得到A到E的最短路线为A→B3→C2→D2→E,最短距离为11。