Maximizing Flow Through a Network with Node and Arc Capacities

by Richard D. Wollmer

Download

Full Document

FormatFile SizeNotes
PDF file 0.8 MB

Use Adobe Acrobat Reader version 10 or higher for the best experience.

Purchase

Purchase Print Copy

 FormatList Price Price
Add to Cart Paperback42 pages $23.00 $18.40 20% Web Discount

A method for maximizing the flow from source to destination along a transportation network whose nodes and arcs have limited capacities. An algorithm is derived that eliminates the need for artificial arcs and nodes used in the flow-augmenting method of Fulkerson and Ford. This simplification should provide a substantial savings in computer time and core storage. The problem is formulated as a linear program. For all nodes other than the source and sink, the node capacity may be expressed as the flow either into or out of the node, since these two quantities are equal. For the source and sink, the node capacity must be expressed in terms of the greater of the two quantities. Thus, the source node capacity limits flow out of the source, while the sink capacity limits flow into the sink. The solution method used, a cut set approach, is a generalization of Ford and Fulkerson's labeling method.

This report is part of the RAND Corporation Research memorandum series. The Research Memorandum was a product of the RAND Corporation from 1948 to 1973 that represented working papers meant to report current results of RAND research to appropriate audiences.

Permission is given to duplicate this electronic document for personal use only, as long as it is unaltered and complete. Copies may not be duplicated for commercial purposes. Unauthorized posting of RAND PDFs to a non-RAND Web site is prohibited. RAND PDFs are protected under copyright law. For information on reprint and linking permissions, please visit the RAND Permissions page.

The RAND Corporation is a nonprofit institution that helps improve policy and decisionmaking through research and analysis. RAND's publications do not necessarily reflect the opinions of its research clients and sponsors.