【摘要】 以油气收集系统设计为背景,研究如下的网络优化问题,在一个加权有向图G中,根点r代表收集中心,其他顶点代表具有给定容量的油井,每条边的权表示运输距离。问题是求G的一个支撑树,满足容量约束,使得到r的传输半径最小。主要结果是问题的NP-困难性证明及等容量情形的多项式时间算法。同时,讨论一般情形的精确算法及启发式算法。更多还原

【Abstract】 Motivated by the design of gas-oil collection systems,this paper studies a network optimization problem as follows.In a weighted graph G,a root r stands for the collection center and the other vertices represent the oil wells with given capacities,and the weight of each edge means the transportation distance.The problem is to find a spanning tree of G satisfying the capacity constraints so that the transportation radius from r is minimized.The main results are the proof of NP-hardness and a polynomial-time algorithm for the case of equal capacity.Exact and heuristic algorithms are also discussed.更多还原