资源描述：
《最小费用最大流课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、§6.5最小费用最大流问题§6.5.1最小费用最大流问题的数学模型设网络D=(V,A,W),每条弧除了容量以外，还给出单位流量的费用（简记为）。这样，D就成为一个带费用的网络，记为D=(V,A,W,C),其中,C称为费用函数。设X为D上的一个可行流，称（6.5.1）为可行流X的费用。最小费用最大流问题，即要求一个最大流X，使总运输费用（6.5.2）达到最小值，则有最小费用最大流问题的数学模型（6.5.3）§6.5.2最小费用最大流问题的算法寻求最大流的方法最小费用最小费用最大流从某个可行流出发，找到关于这个可行流的一条增广链，沿着该增广链调整X，对新的可行流试图寻求关于它的增广链
2、，如此反复直至最大流设想：当沿着一条关于可行流X的增广链以调整X，得到新的可行流且有这里第三个等式只是因为对之外的来说即费用均一样。记称是沿增广链当可行流增加单位流值时费用的增量，简称为增广链的单位费用增量。可以证明，若X是流量为f(X)的所有可行流中费用最小者，而是关于X的所有增广链中费用最小的增广链，则沿去调整X，得到的可行流就是流量为的所有可行流中的最小费用流，这样，当是最大流时，即为最小费用最大流。注意到故X=0必是流量为0的最小费用流。这样，总可以从X=0开始。一般地，若X是流量f(X)的最小费用流，为了寻求关于X的最小费用增广链，构造一个赋权有向图D(X)，它的顶点是
3、原网络D的顶点，而把D中的每一条弧变成两个相反方向的弧和定义D(X)中弧的权在D(X)中长度为的弧可以略去。故在网络D中寻找关于X的最小费用增广链就等价于在赋权有向图D(X)中，寻找从到的最短路。算法步骤：Step1:确定初始可行流令Step2:记为经过k次调整得到的最小费用流，构造Step3:求中到的最短路若不存在，则是最小费用最大流，算法终止；否则，转Step4；Step4:在D中找对应的增广链按式（6.4.4）调整流量，得可行流令转Step2。例6.5.1求图6.5.1的最小费用最大流，弧旁的数字为图6.5.1解:取见图6.4.7（a），图6.5.1（a）构造因没有负权弧，
4、故可用Dijkstra算法求得最短路为见图6.5.1（b）。图6.5.1（b）增广链调整后如图6.5.1（c）。图6.5.1（c）构造得到如图6.5.1（d）。图6.5.1（d）调整得如图6.5.1（e）。图6.5.1（e）构造如图6.5.1（f）。图6.5.1（f）显然，与关联的弧指向不存在到的最短路。故图6.5.1（e）所示的为最小费用最大流。费用流值三、最小费用最大流例6.8.3用LINGO软件求解例6.5.1。解：程序如下：model:sets:nodes/1,2,3,4,5/:d;arcs(nodes,nodes)/1,21,32,32,43,43,54,5/:c,u,
5、f;endsetsmin=@sum(arcs:c*f);@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))=d(i));@sum(arcs(i,j)
7、i#eq#1:f(i,j))=d(1);@for(arcs:@Bnd(0,f,u));data:u=2136234;c=1325113;d=3000-3;enddataend运行结果：Globaloptimalsolutionfoundatiteration:0Objectivevalue:12.00000V
8、ariableValueReducedCostD(1)3.0000000.000000D(2)0.0000000.000000D(3)0.0000000.000000D(4)0.0000000.000000D(5)-3.0000000.000000C(1,2)1.0000000.000000C(1,3)3.0000000.000000C(2,3)2.0000000.000000C(2,4)5.0000000.000000C(3,4)1.0000000.000000C(3,5)1.0000000.000000C(4,5)3.0000000.000000U(1,2)2.0000000
9、.000000U(1,3)1.0000000.000000U(2,3)3.0000000.000000U(2,4)6.0000000.000000U(3,4)2.0000000.000000U(3,5)3.0000000.000000U(4,5)4.0000000.000000F(1,2)2.0000000.000000F(1,3)1.0000000.000000F(2,3)2.0000000.000000F(2,4)0.0000005.000000F(3,4)0.0000003
