網(wǎng)絡(luò)最大流Pareto擴充研究

將網(wǎng)絡(luò)容量定義為最大s-t流的流量，建立了帶有時間和費用雙重限制下的網(wǎng)絡(luò)容量擴充問題模型。通過網(wǎng)絡(luò)變換，將該問題轉(zhuǎn)化為可利用成熟算法求解的線性最小費用流問題。研究了給定網(wǎng)絡(luò)容量擴充目標要求下，求解所有關(guān)于時間和費用的Pareto優(yōu)化解問題并提供了相應(yīng)算法。研究內(nèi)容不僅適用于各種情形的容量擴充問題，而且還可應(yīng)用于網(wǎng)絡(luò)規(guī)劃。最后通過具體例子的求解，說明了算法的正確性和有效性。

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.