lingo基础入门Day 8
lingo：稠密集合与稀疏集合
派生集合分为两种：
稠密集合：
如果一个派生集合在定义时省略了元素列表，那么意味着他的元素是全部父级元素的所有组合构成的，这样的集合被称为稠密集合。
稀疏集合：
如果派生集合的元素只是稠密集合中的一部分（子集），那么这样的派生集合就被成为稀疏集合。
派生集合的构造方法：
语法格式：
派生集合的名字（父集合，...，父集合N)[/元素列表/][：属性元素];
稀疏集合的定义方法
直接罗列法：
factory/A1..A3/;
shop/B1..B4/;
link(factory,shop)
/A1 B1,A1 B2,,
A2 B3,A2 B4,
A3 B1,A3 B2,A3 B3/;
元素过滤法:
factory/A1..A3/;
shop/B1..B4/;
link(factory,shop)|&1 #LE# &2；
最短路径的建模与求解：
求从一条城市A出道到G的最短路线
引入决策变量Xij：
如果Xij=1，表示最终A到G的最短路径经过弧（i，j）；
如果Xij=0，表示最终A到G的最短路径不经过弧（i，j）；
最短路径问题的整数规划模型
模型的建立：
MODEL:
SETS:
CITY/A B C D E F G/;
ROAD(CITY,CITY)
/A B,A C,
B D,B E,B F,
C D,C E,C F,
D G,
E G,
F G/:W,X;
ENDSETS
DATA:
W=
2 4
3 5 1
2 3 6
4
3
5;
ENDDATA
MIN = @SUM(ROAD: W*X);
@SUM(ROAD(I,J)|I #EQ# A: X(I,J))=1;
@SUM(ROAD(I,J)|J #EQ# G: X(I,J))=1;
@FOR(CITY(I)|I #NE# A #AND# I #NE# G:
@SUM(ROAD(I,J):X(I,J))=@SUM(ROAD(K,J):X(K,I))
);
@FOR(ROAD: @BIN(X));
END
网络最大流问题的建模与求解
- 网络最大流问题是人们生活中许多问题的抽象，例如：交通中有车流，运输系统中有物资流，地铁车站有旅客流等等
- 在每一网格中每一条弧（i，j）都有实际的流量限制，也就是通过这一条弧的实际流量必须在[0,cij]之间。
- 求出网络中从顶点1-7最大流量。
- 引入决策变量Fij和Fmax
- fij是达到最大流是，弧（i，j）上的实际流量，fmax就是网络的最大流量，它等于顶点1的全部出射弧上的流量之和，也等于顶点7的全部入射弧的流量之和。
完整模型：
MODEL:
SETS:
Vertex/1..7/;
Arc(Vertex,Vertex)
/1 2,1 3,1 4,
2 3,2 5,
3 4,3 5,3 6,
4 6,
5 6,5 7,
6 7/:C,F;
ENDSETS
DATA:
C=
8 10 12
3 6
4 4 7
8
9 8
10;
ENDDATA
N = @SIZE(Vertex);
MAX = FMAX;
@SUM(ARC(I,J)|I #EQ# 1: F(I,J))=FMAX;
@SUM(ARC(I,J)|J #EQ# N: F(I,J))=FAMX;
@FOR(Vertex(I)|I #GT# 1 #AND# I #LT# N:
@SUM(ARC(K,I):F(K,I))=@SUM(ARC(I,J):F(I,J))
);
@FOR(ARC(I,J): F(I,J)<=C(I,J));
END
实现结果：
Global optimal solution found.
Objective value: 18.00000
Infeasibilities: 0.000000
Total solver iterations: 8
Variable Value Reduced Cost
N 7.000000 0.000000
FMAX 18.00000 0.000000
FAMX 18.00000 0.000000
C( 1, 2) 8.000000 0.000000
C( 1, 3) 10.00000 0.000000
C( 1, 4) 12.00000 0.000000
C( 2, 3) 3.000000 0.000000
C( 2, 5) 6.000000 0.000000
C( 3, 4) 4.000000 0.000000
C( 3, 5) 4.000000 0.000000
C( 3, 6) 7.000000 0.000000
C( 4, 6) 8.000000 0.000000
C( 5, 6) 9.000000 0.000000
C( 5, 7) 8.000000 0.000000
C( 6, 7) 10.00000 0.000000
F( 1, 2) 4.000000 0.000000
F( 1, 3) 6.000000 0.000000
F( 1, 4) 8.000000 0.000000
F( 2, 3) 0.000000 0.000000
F( 2, 5) 4.000000 0.000000
F( 3, 4) 0.000000 0.000000
F( 3, 5) 4.000000 0.000000
F( 3, 6) 2.000000 0.000000
F( 4, 6) 8.000000 0.000000
F( 5, 6) 0.000000 0.000000
F( 5, 7) 8.000000 0.000000
F( 6, 7) 10.00000 0.000000
集合操作函数
| 函数名 | 返回值 |
|---|---|
| @IN(s:e) | 如果元素e在集合s中，返回1，否则返回0. |
| @SIZE | 返回集合s中的成员个数 |
| @INDEX(s:ek) | 返回成员ek在集合s中的顺序号，顺序号从1开始，最大为s中的元素个数 |
| @WRAP(I,N) | 用来转换集合两端的索引，到达集合最后一个元素，再从第一个元素开始索引 |
总结
本小节主要讲了lingo的稠密集合与系稀疏集合，还有稀疏集合的两种定义方法，直接列举法与条件过滤法，最短的路径规划以及网络最大流派，最后还讲了有关集合操作函数。