利用lingo程序求最小費(fèi)用最大流[行業(yè)材料]

1、利用lingo程序求最小費(fèi)用最大流通常求最小費(fèi)用最大流問題是分兩個(gè)階段：1， 先求最大流。2， 再在最大流的基礎(chǔ)上求最小費(fèi)用流。以下圖為例。其中如（5，8）=（容量，費(fèi)用）。求從S到T的最小費(fèi)用最大流。1， 先求最大流，lingo程序?yàn)椋篗ODEL: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(

2、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結(jié)果是，最大流為12，2， 再在最大流的基礎(chǔ)上求最小費(fèi)用流。程序?yàn)椋篗ODEL: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);fo

3、r(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結(jié)果是: Global optimal solution found. Objective value: 218.0000 Infeasibilities: 0.000000 Total solver iterations: 0 Variable Value Reduced Cost F( S,

4、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現(xiàn)利用lingo的子模型功能，將2個(gè)程序合二為一，可直接算出最小費(fèi)用流。model: !最小費(fèi)用最大流問題的子模型形式;sets:nodes/s,1,2,3,t/: ; !定義端點(diǎn)代號(hào);arcs(nodes,nodes)/s,1

5、s,2 1,t,1,3 2,1 2,3 3,t/:b,c,f; !定義弧代號(hào);Endsetsdata:b=8 7 9 2 5 9 4 ; !定義各弧的費(fèi)用值;c=5 8 4 3 2 10 8; !定義各弧的容量;enddataSUBMODEL maxflow: !最大流的目標(biāo)函數(shù)子模型;max = flow; !求最大流; endsubmodelsubmodel minfy: !最小費(fèi)用流的目標(biāo)函數(shù)子模型;min=sum(arcs:b*f); !求最小費(fèi)用流; endsubmodelsubmodel con: !約束條件;for(nodes(i)|i #ne# 1 #and# i #ne# s

6、ize(nodes): sum(arcs(i,j):f(i,j)-sum(arcs(j,i):f(j,i)=0); !中間點(diǎn)是進(jìn)出相等;sum(arcs(i,j)|i #eq# 1: f(i,j) = flow; !發(fā)點(diǎn)是流量; for(arcs:bnd(0,f,c); !流量應(yīng)小于容量;endsubmodelCALC: !程序段，順序執(zhí)行;SOLVE( maxflow,con); !先求最大流，注意加約束條件;flow=flow; !保留flow值，便于第2個(gè)程序使用;solve(minfy,con); !再求最大流下的最小費(fèi)用流;endcalcEND結(jié)果同上，最小費(fèi)用為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( 1,