Constructing Maximal Dynamic Flows from Static Flows

L. R. Ford and D. R. Fulkerson
Additional contact information
L. R. Ford: The Rand Corporation, Santa Monica, California
D. R. Fulkerson: The Rand Corporation, Santa Monica, California

Operations Research, 1958, vol. 6, issue 3, 419-433

Abstract: A network, in which two integers t ıj (the traversal time) and c ıj (the capacity) are associated with each arc P ı P j , is considered with respect to the following question. What is the maximal amount of goods that can be transported from one node to another in a given number T of time periods, and how does one ship in order to achieve this maximum? A computationally efficient algorithm for solving this dynamic linear-programming problem is presented. The algorithm has the following features ( a ) The only arithmetic operations required are addition and subtraction ( b ) In solving for a given time period T , optimal solutions for all lesser time periods are a by-product ( c ) The constructed optimal solution for a given T is presented as a relatively small number of activities (chain-flows) which are repeated over and over until the end of the T periods. Hence, in particular, hold-overs at intermediate nodes are not required ( d ) Arcs which serve as bottlenecks for the flow are singled out, as well as the time periods in which they act as such ( e ) In solving the problem for successive values of T , stabilization on a set of chain-flows ( see ( c ) above) eventually occurs, and an a priori bound on when stabilization occurs can be established. The fact that there exist solutions to this problem which have the simple form described in ( c ) is remarkable, since other dynamic linear-programming problems that have been studied do not enjoy this property.

Date: 1958
References: Add references at CitEc
Citations: View citations in EconPapers (51)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.6.3.419 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:6:y:1958:i:3:p:419-433

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().