一类有增益网络的最大流模型

一般带容量限制的网络图中流出源点与流入汇点的流量相等,但在实际应用中,存在一类流量经过弧发生变化的网络,使得流出源点与流入汇点的流量不相等。针对此类问题,建立了增益网络最大流模型,并通过增设虚弧将增益网络转换成循环网络,利用循环网络中汇点流量瞬间平衡的优点简化了模型。最后,结合实例进行分析,编写程序对实例进行了计算,计算结果验证了该模型的有效性。

Maximum flow model for network with gain

Generally,the amount of the flow which runs out of the source equals that of the flow which runs into the sink in a network with capacity constraint.But in practice,there is a sort of network in which the amount of flow is alterable via arc.So the amount of flow running out of the source doesn′t equal that of flow running into the sink.With respect to this problem,a new maximum flow model for the network with gain was established.The network with gain was transferred into a circle network through adding a supposed arc to it.Then by the flux instantaneous equilibriums for the sink,the model was simplified.Finally,through the analysis,programming and calculation of an example,the result proves that the model is efficient.