Accession Number:

AD0754376

Title:

Optimal Capacity Expansion in a Flow Network

Descriptive Note:

Technical rept.

Corporate Author:

NAVAL POSTGRADUATE SCHOOL MONTEREY CA

Personal Author(s):

Report Date:

1972-09-12

Pagination or Media Count:

37.0

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 Dantzigs 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.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE