小菜鸡学习笔记

✈数学建模之网络最大流问题
1.网络最大流是什么？
对于这样的一张图片，求解从X1和X2出发，到Y1和Y2的最大流？

2. 该怎么进行求解?
这里假设起点为S，终点为T；S运向X1,X2的限制量分别为6+10、5+10…同理，Y1,Y2运向T的限制量也可以这样计算。为简便起见，都设为20.

model:
sets:
cities/s,x1,v2,y1,v1,v5,v3,x2,v4,y2,t/;
rodes(cities,cities)/
s,x1 s,x2
x1,x2 x1,v1
v2,y1
y1,t
v1,v5
v5,v2 v5,v3 v5,v4
v3,y1 v3,y2
x2,v1 x2,v4
v4,y2
y2,t
/:FR,FL;
!FR表示各路径实际的流量，FL表示各路径限制的流量;
endsets
data:
FL= 20 20
10 6
11
20
20
6 8 5
6 5
5 10
11
20
;
enddata
max=@sum(rodes(i,j)|i#EQ#1:FR(i,j));
@for(rodes(m,n):FR(m,n)<FL(m,n););
!各路径实际流量小于等于限制流量;
@for(cities(i)|i#GT#@index(s) #and# i#LT#@size(cities):
@sum(rodes(i,g):FR(i,g))=@sum(rodes(g,i):FR(g,i));
);
end

这里FR表示各路径实际的流量，FL表示各路径限制的流量;
结果为

  Objective value:                              21.00000
  Infeasibilities:                              0.000000
  Total solver iterations:                             0

网络最大流为21.
备注：代码来源书本????