THE COMPUTATIONAL COMPLEXITY OF THE PROBLEM OF DETERMINING LEAST CAPITAL COST DESIGNS FOR WATER SUPPLY NETWORKS
THE COMPUTATIONAL COMPLEXITY OF THE PROBLEM OF DETERMINING LEAST CAPITAL COST DESIGNS FOR WATER SUPPLY NETWORKS
复制标题
确定供水管网最低资本成本设计问题的计算复杂性
DOI：
--
复制
发表时间：
1984
期刊：
影响因子：
--
通讯作者：
T. B. Boffey
中科院分区：
文献类型：
--
作者：
D. Yates;A. Templeman;T. B. Boffey
用于供水的管道以一组离散尺寸的直径制造。这种情况给设计用于选择管径以构成最小资本成本的供水网络的算法的问题带来了重大困难。在本文中，它表明，即使是最简单的类型的分支网络，问题是一个数学类称为NP-难的，结果，这意味着，适用于更复杂的类型的网络包含循环。这一结果表明，旨在设计这样一个算法的研究很可能是不成功的，并会更好地发展良好的近似解方法。
Pipes for water supply are manufactured in a set of discrete-sized diameters. This situation introduces significant difficulties to the problem of devising an algorithm for selecting pipe diameters to constitute a water supply network of least capital cost. In this paper, it is shown that, even for the very simplest type of branching network, the problem is one of a mathematical class known as NP-hard; a result which, by implication, applies to the more complex type of network containing loops. This result suggests that research aimed at devising such an algorithm is likely to be unsuccessful, and would be better directed towards developing good approximate solution methods.