解决最小开销流问题,我们仅仅需要构造一个流网络图,并且保证满足之前讨论过的那些限制条件:容量限制、流量守恒以及反对称。而且还要保证如下两个条件。
供应满足
对每个源点si∈S,所有边(si,v)∈E的f(si,v)之和(流出si的流)减去所有边(u,si)∈E的f(u,si)之和(流入si的流)必须小于等于sup(si),也就是说,每个源点供应的商品的上限是sup(si)。
需求满足
对于每个汇点tj∈T,所有边(u,tj)∈E的f(u,tj)之和(流入tj的流)减去所有边(tj,v)∈E的f(tj,v)之和(流出tj的流)必须小于等于dem(tj)。也就是说,每个汇点需要的商品上限是dem(tj)。
为了简化算法的实现,我们将会限制流网络只有一个源点和一个汇点。通过向现存的多源多汇点的流网络图添加两个新顶点,这种流网络可以轻易得到。首先,添加一个新的顶点(s0)成为流网络的源点,然后对每个源点si∈S,添加一条容量c(s0,si)=sup(si)以及开销d(s0,si)=0的边(s0,si)。然后,添加一个新的顶点(tj,tgt)成为流网络的汇点,然后对每个源点tj∈T,添加一条容量c(tj,tgt)=dem(tj)以及开销d(t0,tj)=0的边(tj,tgt)。你可以看到,添加这些顶点和边不会增加原始流网络的开销,但是也不会减少最后计算出的流。
供应sup(si),需求dem(tj)以及容量c(u,v)都大于0。每条边的航运开销d(u,v)可能大于等于0。计算出结果之后,所有的f(u,v)都会大于等于0。
我们现在准备来解决图8-1中剩下的流网络问题。对于每个问题,我们都会描述如何归约成最小开销流问题。