数学建模之Lingo基础知识与应用（二）

重光兰衣

数学建模之Lingo基础知识与应用（二）2. 在LINGO中使用集合

LP模型一个典型的输入方式:

1. @SUM(集合（下标）：关于集合的属性的表达式)
本例中目标函数也可以等价地写成
@SUM(QUARTERS(i): 400*RP(i) +450*OP(i) +20*INV(i) )，
“@SUM”相当于求和符号“∑”，
“QUARTERS(i)”相当于“iQUARTERS”的含义。
由于本例中目标函数对集合QUARTERS的所有元素(下标) 都要求和，所以可以将下标i省去。
2. @FOR(集合(下标)：关于集合的属性的约束关系式)
对冒号“：”前面的集合的每个元素（下标），冒号“：”后面的约束关系式都要成立
为了区别i=1和i=2，3，4，把i=1时的约束关系式单独写出，即“INV(1)=10+RP(1)+OP(1)-DEM(1);” ；
而对i=2，3，4对应的约束，对下标集合的元素（下标i）增加了一个逻辑关系式“i#GT#1”（这个限制条件与集合之间有一个竖线“|”分开，称为过滤条件）。
' _3 e" Q4 C  S" Y8 r限制条件“i#GT#1”是一个逻辑表达式，意思就是i>1；“#GT#”是逻辑运算符号，意思是“大于（Greater Than的字首字母缩写）” 。

+ I. }6 k; N' o; E6 X' Q3 m" R2.1 LINGO模型最基本的组成要素
一般来说，LINGO中建立的优化模型可以由五个部分组成，或称为五“段”（SECTION）：
, Y( `& Y  q- i8 D) f8 p6 `6 }（1）集合段（SETS）：以“ SETS:” 开始， “ENDSETS”结束，定义必要的集合变量（SET）及其元素（MEMBER，含义类似于数组的下标）和属性（ATTRIBUTE，含义类似于数组）。
（2）目标与约束段：目标函数、约束条件等，没有段的开始和结束标记，因此实际上就是除其它四个段(都有明确的段标记)外的LINGO模型。
& `7 X3 t+ ]7 K3 S+ G1 j# f这里一般要用到LINGO的内部函数，尤其是与集合相关的求和函数@SUM和循环函数@FOR等。
（3）数据段(DATA)：以 “DATA:” 开始, “ENDDATA”结束，对集合的属性(数组)输入必要的常数数据。
格式为：“attribute(属性) = value_list(常数列表);”
常数列表(value_list)中数据之间可以用逗号“,”分开，也可以用空格分开(回车等价于一个空格),如上面对DEM的赋值也可以写成“DEM=40 60 75 25；”。
（4）初始段(INIT)：以“INIT: ”开始， “ENDINIT”结束，对集合的属性(数组)定义初值(因为求解算法一般是迭代算法，所以用户如果能给出一个比较好的迭代初值，对提高算法的计算效果是有益的)。
; {% i4 D8 v" x4 ]/ P如果有一个接近最优解的初值，对LINGO求解模型是有帮助的。定义初值的格式为：
“attribute（属性） = value_list（常数列表）；”
+ a# f5 n' ?7 ?" u3 a（5）计算段(CALC)：以“CALC: ”开始， “ENDCALC”结束，对一些原始数据进行计算处理。
在实际问题中，输入的数据通常是原始数据，不一定能在模型中直接使用，可以在这个段对这些原始数据进行一定的“预处理”，得到模型中真正需要的数据。
例如上例，如果希望得到全年的总需求和季度平均需求，可以增加这个段：
CALC:   T_DEM = @SUM(quarters: DEM);      !总需求;   A_DEM = T_DEM / @size(quarters); !平均需求;ENDCALC
2.2 基本集合与派生集合
0 k0 G, X+ Q) u" m2 k; i: f7 M' A

' ~4 R, o6 j- m: k5 }% j1.定义了三个集合，其中LINK在前两个集合DEMAND 和SUPPLY的基础上定义
' v2 ~! R( N0 v( l: l0 @: r2.在程序开头用TITLE语句对这个模型取了一个标题“LOCATION PROBLEM；并且对目标行（[OBJ]）和两类约束（DEMAND_CON、SUPPLY_CON）分别进行了命名(请特别注意这里约束命名的特点)。
) R. i) j9 ?. r+ N1 Y3.INGO对数据是按列赋值的
4 F, m9 \! n2 P- d* x语句的实际赋值顺序是X=(5,2), Y=(1,7), 而不是X=(5,1), Y=（2,7)
等价写法：
" n& A9 M) |7 h4 l+ n. O1 U7 J* L“X=5,2； Y=1,7；”
: q2 K* S" p* g) Q8 R: ]解得:
+ [2 C9 a. E. I5 k: X  w2.3 稠密集合与稀疏集合
8 A. O# {0 M$ S# V: p2 M; r包含了两个基本集合构成的所有二元有序对的派生集合称为稠密集合(简称稠集)。有时候，在实际问题中，一些属性(数组) 只在笛卡儿积的一个真子集合上定义，这种派生集合称为稀疏集合(简称疏集)。
例 (最短路问题) 在纵横交错的公路网中，货车司机希望找到一条从一个城市到另一个城市的最短路. 下图表示的是公路网, 节点表示货车可以停靠的城市,弧上的权表示两个城市之间的距离(百公里). 那么,货车从城市S出发到达城市T,如何选择行驶路线,使所经过的路程最短?
7 K$ O* E6 O" z8 d

此例中可把从S到T的行驶过程分成4个阶段,即 S→Ai (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的最优行驶路线的路长:
( ~& ^  r$ M2 E9 z/ @
5 [! Q8 }# I" y  o
; @" \7 d3 K( g$ Z
  r; p, q# L( ]( d本例的LINGO求解:
9 o: Z, P, z( U" S: T4 Y9 s; {- A
3 D% p# L( b8 O/ o$ W  P, x
! i: ?# k" ]# V+ v

运行结果:
$ S7 X( n3 i0 u, @& V
0 i  Z1 T8 X6 w% E8 ?0 F1.“CITIES”(城市):一个基本集合(元素通过枚举给出)
2.“ROADS”(道路):由CITIES导出的一个派生集合(请特别注意其用法),由于只有一部分城市之间有道路相连，所以不应该把它定义成稠密集合，将其元素通过枚举给出，这就是一个稀疏集合。
3.从模型中还可以看出：这个LINGO程序可以没有目标函数，这在LINGO中，可以用来找可行解(解方程组和不等式组)。
/ O. s: u& w3 i2.4 集合的使用小结


0 T$ h7 c& u' T$ ^) T4 X1 r/ o4 Z1. 基本集合的定义格式为(方括号“[ ]”中的内容是可选项, 可以没有):
setname [/member_list/] [: attribute_list];
其中setname为定义的集合名，member_list为元素列表，attribute_list为属性列表。元素列表可以采用显式列举法(即直接将所有元素全部列出,元素之间用逗号或空格分开),也可以采用隐式列举法。
9 W& N) |( G2 Z4 f* J2. 派生集合的定义格式为(方括号“[ ]”中的内容是可选项, 可以没有):
+ V& n$ R$ ]0 k8 N/ A' Esetname(parent_set_list) [/member_list/] [: attribute_list];
与基本集合的定义相比较多了一个parent_set_list(父集合列表)。
1 O8 `- l3 P- Z. d" V: w$ }4 g父集合列表中的集合(如 set1，set2，…，等)称为派生集合setname的父集合，它们本身也可以是派生集合。

% D8 M& Q. p8 d/ Q2 c: q$ x