资源描述：
《【精品】ly论文zuixin》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、第一章最小费用流问题的基本理论知识1.1预备知识一个图是由一些点及一些点Z间的连线（不带箭头或带箭头）所组成的。不带箭头的连线称为边，带箭头的称为弧。如果一个图D是由点及弧所构成的，就称为有向图。记作D二（V,A）,式中V,A分别表示D的点集合和弧集合。一条方向是从岭指向勺的弧记为（v,vy.）o给一个有向图D=（V,A）,在V中指定了一点称为发点（记为匕），而另一点称为收点（记为片），其余的点叫做中间点。对于每一个弧（v,vy）eA,对应有一个c（v;v.）＞0（或简写为©）,称为弧的容量。通常我们把这样的一个D叫作一个网络，记为D二（V,A,C）。流量：表示某时间内通过弧（匕匕）的
2、物质数量，记为厶。网络中的总流量用v（f）表示。容量C”就是弧的最大允许流通量。可行流：在实际的网络中，网络流应满足卜•面两个条件：（1）容量限制条件：对于每一个弧{v,v;}eA,A为弧集來说，05厶＜5。即通过每条弧的流量不能超过该弧的容量。（2）平衡条件：对于始点叫，流入始点的流量等于网络屮的总流量，即SA-EAs"）（匕与）"（vjV^eA对于终点岭，流出终点的流量等于网络中的总流量，即》人-工fjl=_v（/）（vtVj）eA（VjVt）eA对于任一中间的顶点,流进某中间顶点的流量等于流出该顶点的流量。即ZA-Z九"（vfv7）€/4（VyVf）eA在网络分析中，满足上面两个
3、条件的流称为可行流。饱和弧和非饱和弧：网络中流量等于容量（即，4=c,）的弧称为饱和弧。流量小于容量（即厶vc»）的弧称为非饱和弧。正向弧和反向弧：设“是网络中从始点人到终点片的一条链。凡与链走向一致的弧称为正向弧/?,逆向弧的称为反向弧“一。增广链：从始点匕到终点％的一条链上的各弧，若对于某一可行流厶来说，满足下面两个条件，则称该链是对于可行流厶•的增广链：（1）对于正向弧,满足条件z7＜c..o（2）对于反向弧，满足条件九＞0。这就是说，在增广链上的正向弧都是非饱和弧，反向弧都是非零流弧。1.2模型理论分析1.2.1模型提出给定网络N二(V,A,c,b),c是每条弧的容量，b是在每
4、条弧上通过单位流量要花的费用。所谓最小费用流问题就是对于每一个给定的流f,使流的总费用取最小值。如果f是最人流，那么总费用最小的最人流就是最小费用最人流。1.2.2模型求解(赋权图法)求解最小费用流的算法很多，其中易于理解的一种流行算法是用最短路算法求最小费用的增广链。这种方法的思路是：从零流量开始，在始点到终点的所有可能增加流量的壇广链中寻求总费用最小的链，并首先在这条链上增加流量，得到流量为/⑴的最小费用流。再对/⑴寻求所冇可能增加流量的增广链，并在其中总费用最小的增广链上继续增加流量，得到流量为/⑵的最小费用流。依此类推，重复以上步骤，直到网络中不再存在壇广链，不能再增加流量为止
5、。依上面步骤所得到的最大流就是最小费用最大流。依据上述原理的具体求解步骤是：在每一次迭代时，先根据网络中各弧构成壇广链的条件，构造一个新的赋权图W(f),它的顶点是原网络的顶点，而把图中的每一条弧匕片都变成两个相反方向的弧岭专和v-V,.o假定原网络中各弧的单位费用是给，则令赋权图中各弧的权比为[b..如果f..0W=JJJJ，[+oo如果fjj=0(权为+00的弧可以从赋权图中略去)不难看岀，在这样构成的赋权图中，从始点到终点的每条通路都是对某一当前流的増广链。求出从始点到终点的最短路就找到了最小费用的增广链。1.3实例求
6、解下面用一个具体例子來说明用赋权图法求解最小费用流的具体步骤。在图(A)所示的冇向网络中，弧旁的数字(厶,©,%)代表流量，容量，单位流量费用。现在用赋权图法求其最小费用流。(0,10^4)(0,5,1)V1V(0,8,1)s(032,6)(0,10,3)(0,4,2)J(A)/(O)=Oi.取f®=o,这时，每条弧中的流量厶=0,因此它们都是非饱和弧。因为z7=o,所以在赋权图W(/(0))中各边无需加反向弧，即原图就是对于f⑹=0的赋权图，见图(B)。由赋权图VV(/(0)),可以找到最小费用增广链是s^v^v^t总费用为4,可以增加流量值为〃=min[&5,5]=5,在这条增广链
7、上的每条弧中增加5个单位流量后，可以得到新的可行流f⑴=5,其图为(C),其费用累计值为5x4=20o(B)W(严))(C)/•⑴=52.构造可行流f⑴的赋权图,见图(D),可以很容易找到费用最小的增广链是$T冬T冬T/，总费用为6。从图(C)知道可以增加的流量值为0=min[3,10,4]=3。在这条增广链上的毎条正向弧中增加3个单位流量后，可以得到新的可行流严)=严)+3=8,见图(E)o其费用累计值为20+3x6=38。(D)W(/⑴)（
