利用lingo程序求最小费用最大流.docx

利用lingo程序求最小费用最大流通常求最小费用最大流问题是分两个阶段：1， 先求最大流。2， 再在最大流的基础上求最小费用流。以下图为例。其中如（5，8）=（容量，费用）。求从S到T的最小费用最大流。1， 先求最大流，lingo程序为：MODEL:sets:nodes/s,1,2,3,t/;arcs(nodes,nodes)/ s,1 s,2 1,t,1,3 2,1 2,3 3,t/:c,f;endsetsdata: c= 5 8 4 3 2 10 8;enddatamax = flow;for(nodes(i)|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)|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,1 s,2 1,t,1,3 2,1 2,3 3,t/:b,c,f;endsetsdata:flow=12;b=8 7 9 2 5 9 4 ;c=5 8 4 3 2 10 8;enddatamin=sum(arcs:b*f);for(nodes(i)|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)|i #eq# 1: f(i,j) = flow;for(arcs:bnd(0,f,c);END结果是: Global optimal solution found. Objective value: 218.0000 Infeasibilities: 0.000000 Total solver iterations: 0 Variable Value Reduced Cost F( S, 1) 5.000000 -6.000000 F( S, 2) 7.000000 0.000000 F( 1, T) 4.000000 0.000000 F( 1, 3) 3.000000 0.000000 F( 2, 1) 2.000000 -2.000000 F( 2, 3) 5.000000 0.000000 F( 3, T) 8.000000 -3.000000现利用lingo的子模型功能，将2个程序合二为一，可直接算出最小费用流。model: !最小费用最大流问题的子模型形式;sets:nodes/s,1,2,3,t/: ; !定义端点代号;arcs(nodes,nodes)/s,1 s,2 1,t,1,3 2,1 2,3 3,t/:b,c,f; !定义弧代号;Endsetsdata:b=8 7 9 2 5 9 4 ; !定义各弧的费用值;c=5 8 4 3 2 10 8; !定义各弧的容量;enddataSUBMODEL maxflow: !最大流的目标函数子模型;max = flow; !求最大流; endsubmodelsubmodel minfy: !最小费用流的目标函数子模型;min=sum(arcs:b*f); !求最小费用流; endsubmodelsubmodel con: !约束条件;for(nodes(i)|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)|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结果同上，最小费用为218 Global optimal solution found. Objective value: 218.0000 Infeasibilities: 0.000000 Total solver iterations: 0 Variable Value Reduced Cost F( S, 1) 5.000000 -6.000000 F( S, 2) 7.000000 0.000000 F( 1, T) 4.000000 0.000000 F(