网络最大流Pareto扩充研究

将网络容量定义为最大s-t流的流量,建立了带有时间和费用双重限制下的网络容量扩充问题模型。通过网络变换,将该问题转化为可利用成熟算法求解的线性最小费用流问题。研究了给定网络容量扩充目标要求下,求解所有关于时间和费用的Pareto优化解问题并提供了相应算法。研究内容不仅适用于各种情形的容量扩充问题,而且还可应用于网络规划。最后通过具体例子的求解,说明了算法的正确性和有效性。

Research on Network Max-flow Pareto Expansion Problem

The network capacity is defined as the value of the maximum s-t flow, and a unified model is introduced for the network capacity expansion with the time and cost constraints. By the transformation of the underlying network, the network capacity is converted to a minimum cost flow problem instead. Also developed are the algorithm to find all pareto optimal solutions about time and cost with given expanded network max-flow. The model and algorithm are proven to be valid with an example, and they not only allow capturing various types of capacity expansion, but also are useful in network programming.