资源描述：
《利用lingo程序求最小费用最大流.docx》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、利用lingo程序求最小费用最大流通常求最小费用最大流问题是分两个阶段：1，先求最大流。2，再在最大流的基础上求最小费用流。以下图为例。其中如（5，8）=（容量，费用）。求从S到T的最小费用最大流。1，先求最大流，lingo程序为：MODEL:sets:nodes/s,1,2,3,t/;arcs(nodes,nodes)/s,1s,21,t,1,32,12,33,t/:c,f;endsetsdata:c=58432108;enddatamax=flow;@for(nodes(i)
2、i#ne#1#and#i#ne#@size(nodes):@sum(ar
3、cs(i,j):f(i,j))-@sum(arcs(j,i):f(j,i))=0);@sum(arcs(i,j)
4、i#eq#1:f(i,j))=flow;@for(arcs:@bnd(0,f,c));END结果是，最大流为12，2，再在最大流的基础上求最小费用流。程序为：MODEL:sets:nodes/s,1,2,3,t/:;arcs(nodes,nodes)/s,1s,21,t,1,32,12,33,t/:b,c,f;endsetsdata:flow=12;b=8792594;c=58432108;enddatamin=@sum(arcs:b*f)
5、;@for(nodes(i)
6、i#ne#1#and#i#ne#@size(nodes):@sum(arcs(i,j):f(i,j))-@sum(arcs(j,i):f(j,i))=0);@sum(arcs(i,j)
7、i#eq#1:f(i,j))=flow;@for(arcs:@bnd(0,f,c));END结果是:Globaloptimalsolutionfound.Objectivevalue:218.0000Infeasibilities:0.000000Totalsolveriterations:0VariableValueReducedCost
8、F(S,1)5.000000-6.000000F(S,2)7.0000000.000000F(1,T)4.0000000.000000F(1,3)3.0000000.000000F(2,1)2.000000-2.000000F(2,3)5.0000000.000000F(3,T)8.000000-3.000000现利用lingo的子模型功能，将2个程序合二为一，可直接算出最小费用流。model:!最小费用最大流问题的子模型形式;sets:nodes/s,1,2,3,t/:;!定义端点代号;arcs(nodes,nodes)/s,1s,21,t,1,32
9、,12,33,t/:b,c,f;!定义弧代号;Endsetsdata:b=8792594;!定义各弧的费用值;c=58432108;!定义各弧的容量;enddataSUBMODELmaxflow:!最大流的目标函数子模型;max=flow;!求最大流;endsubmodelsubmodelminfy:!最小费用流的目标函数子模型;min=@sum(arcs:b*f);!求最小费用流;endsubmodelsubmodelcon:!约束条件;@for(nodes(i)
10、i#ne#1#and#i#ne#@size(nodes):@sum(arcs(i,j)
11、:f(i,j))-@sum(arcs(j,i):f(j,i))=0);!中间点是进出相等;@sum(arcs(i,j)
12、i#eq#1:f(i,j))=flow;!发点是流量;@for(arcs:@bnd(0,f,c));!流量应小于容量;endsubmodelCALC:!程序段，顺序执行;@SOLVE(maxflow,con);!先求最大流，注意加约束条件;flow=flow;!保留flow值，便于第2个程序使用;@solve(minfy,con);!再求最大流下的最小费用流;endcalcEND结果同上，最小费用为218Globaloptimalso
13、lutionfound.Objectivevalue:218.0000Infeasibilities:0.000000Totalsolveriterations:0VariableValueReducedCostF(S,1)5.000000-6.000000F(S,2)7.0000000.000000F(1,T)4.0000000.000000F(1,3)3.0000000.000000F(2,1)2.000000-2.000000F(2,3)5.0000000.000000F(3,T)8.000000-3.000000
