Optimal Capacity Expansion in a Flow Network
Abstract
The capacity expansion problem for flow networks, first studied by D. R. Fulkerson, is reexamined. In the case where no free initial capacity is available, it is shown that the optimal expansion takes place on the arcs of the cheapest chain in the sense of unit expansion costs through the network. The proof makes use of Dantzig's decomposition principle of linear programming. In the case where some free initial capacity is available, an algorithm based on the topological dual is presented. This algorithm does not require that the flow network be planar and can be easily extended to problems having positive lower bound restrictions on arc flows, problems having bounds on individual arc expansion or nonlinear convex expansion costs, and capacity reduction problems.
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 12, 1972
- Accession Number
- AD0754376
Entities
People
- Alan W. Mcmasters
Organizations
- Naval Postgraduate School