Optimal capacity expansion in a flow network
By: by Alan W. McMasters
Contributors: Naval Postgraduate School (U.S.)
Publisher: Naval Postgraduate School
Published: 1972
Place of publication: Monterey, California
Language: eng
Number of pages: 35
Subjects: Mathematical optimization; Network analysis (Planning); Graph theory
Description: 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.
Notes: Title from cover.

"12 September 1972"--Cover.

"NPS55MG72091A"--Cover.

DTIC Identifiers: Network flows, decomposition method, duality theory.

Author(s) key words: Network flows, graph theory, optimization, duality theory.

Includes bibliographical references (p. 31).

"Approved for public release; distribution unlimited"--Cover.

Technical report; 1972.

ck/ 9/23/09.