最小费用流问题的研究.docxVIP

最小费用流问题的研究摘要 本文主要研究的是最小费用流问题。在给出一些定义定理的基础上进一步求解最小费用流问题从而得到更好的算法。关键字 最小费用流问题 剩余网络 容许网络 算法 复杂度1最小费用流问题的概述给定一个有向网络。其中表示顶点集合，表示中的所有弧构成的一个集合。任意的弧，用表示弧上单位流量的费用，用表示弧上的最大流量，任意的用表示在这一点处所提供的流量或所需要的流量。当时，表示在这一点处所提供的流量为，当时，表示在这一点处所需要的流量为。最小费用流问题是指在有容量约束的网络中，当网络容量带有费用约束的时候，我们希望一定的流量在通过网络的时候的费用最小，这就形成了最小费用流模型。模型如下： Min Subject to for all , for all 2.cycle-canceling algorithm定义2.1 给定一个有向网络,给定一个流，我们来构造一个网络：对于中任意的一条弧,我们用弧和来表示，弧的费用用来表示，弧的剩余容量用来表示，弧费用用来表示，，弧的剩余容量用来表示。去掉剩余容量为非正的弧后所构成的图形用表示。我们把叫做剩余网络。定理2.1（Negative Cycle Optimality Conditions）设是最小费用流问题的一个可行解，那么是最小费用流问题的一个最优解当且仅当满足negative cycle optimality conditions:剩余网络中不存在负圈。根据负圈的最优条件，为了得到可行流，我们可以利用找最大流的算法建立一个可行流，再根据可行流构造剩余网络。在剩余网络中找负圈,取沿着上的弧增广个单位的流，消去负费用的圈。更新，再找负圈，重复上述过程，直到中不存在负圈为止。这样的算法称为cycle-canceling algorithm。2.1算法的具体步骤如下：algorithm cycle-canceling:begin establish a feasible flow in the network; while contains a negative cycle do begin use some algorithm to identify a negative cycle ; augment units of flow in the cycle and update ;end;end;2.2算法的复杂度分析在剩余网络中用标签法找负圈时，其时间复杂度为。算法的主要工作量在于连续寻找负圈并消去负圈。我们用表示弧上的费用中的最大者，用表示所有弧上的容量中的最大者，由于任何可行流的费用不可能超过，而每次消去一个负圈至少使得费用下降一个单位，一次消去负圈最多执行。由此可知，该算法的时间复杂度为3 successive shortest path algorthmi定义3.1 任意的顶点，我们用表示顶点的势，用向量表示图中所有顶点的势，用表示弧上的减少费用，且规定：。定理3.1（Reduced Cost Optimality Conditions）设是最小费用流问题的一个可行解，那么是最小费用流问题的一个最优解当且仅当表示顶点势的向量满足reduced cost optimality conditions：对于任意一条弧，都有成立。定义3.2 设是一个流，当满足容量的限制和非负的限制，但不满足点的平衡条件的限制时，我们把叫做pseudoflows。对于任意一个psedudoflows ，当是一个不平衡的点时，我们有对于任意的,当时，表示顶点为过剩的点；当时，表示顶点为不足的点；当时，表示顶点为平衡的点。所以有 故有 其中 。由上可知，一个有向网络中如果含有一个过剩点，那么在这个网络中至少含有一个不足点。推论3.2 假设pseudoflows 和顶点势的向量满足减少费用的最优条件。设向量表示剩余网路中从顶点到其它所有点的最短路的距离，用表示中弧的长度，则我们得到以下两条性质：pseudoflows 和顶点势的向量满足减少费用的最优条件；从顶点到其它任意一个顶点的一条最短路上的任意一条弧的减少用根据定理和推论，当我们遇到的流为pseudoflows时，我们要保证pseudoflows 和表示顶点势的向量满足减少费用的最优条件的情况下，把所有的不平衡的点转变成平衡的点，也就是说，要把pseudoflows 转变成可行流。3.3算法的具体步骤如下：algorithm successive shortest pathbegin for all ;initialize the sets ;while dobegin select a node and a node ; determine shortest path distance from node to