一类网络容量扩充问题

A Class of Capacity Expansion Problem on Networks

给定一个连通网络,找两点之间的最短路,作为两点之间的流量路径。每条路径都有一定的需求,网络中每条边的容量至少为经过该边的所有路径的需求之和,若某条边的容量小于经过该边的所有路径的需求之和,则需要对其容量进行扩充。每种扩充方案的扩充费用是关于扩充容量的函数。本文给出解决该问题的一个多项式时间算法,使得各边容量达到需求,且总的扩充费用最小。

Suppose that a connected network is given, finding out the shortest path between two vertexes of the network as the flow path between them. Every flow path has a flow demand. The capacity of every arc in the network is at least the total demands of the entire flow paths which include this arc. If onearc＇s capacity is less than the total demands of the entire flow paths which include this arc, then the capacity needs to be expanded. The cost of every expanding way is a function about the expanding capacity. The authors give a polynomial solution algorithm to make the arc＇s capacity in the network meet the total demands and have the minimum cost.