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

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

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.