Browse Prior Art Database

NETWORK FLOW THEORY

IP.com Disclosure Number: IPCOM000128835D
Original Publication Date: 1956-Aug-14
Included in the Prior Art Database: 2005-Sep-19
Document File: 7 page(s) / 95K

Publishing Venue

Software Patent Institute

Related People

Ford, Jr., L.R.: AUTHOR [+3]

Abstract

A network (or linear graph) is a collection of points or nodes, some of which may be joined together by arcs. We shall denote the points by P i , i = 0, 1, 2, ..., N. and denote the arc joining P i to P j in that order by A ij . (Note that there may also be an arc A ji joining P j to P i .) We may also have associated with the arc A ij a capacity c ij and a length (or cost) l ij . We shall assume these to be positive integers. We shall also distinguish two points in the network, P O , the origin, and P N , the terminal. One may think of this system as a rail network, in which the origin represents a factory or a warehouse at which goods enter the system, and the terminal represents a consumer for these goods who removes them from the system. The c ij then represent upper bounds on the shipping capacity from P i to P j and the l ij may represent variously the distance from P i to P j or the time required to ship from P i to P j or the unit cost of shipping from P i to P j . (We shall agree that if c ij = 0 then l ij = &infty; and that l ij &neq; 0.) Evidently many different problems may be posed with this framework. We shall discuss primarily the following three problems, stated verbally below. A. To find a maximal steady state flow of goods from the origin to the terminal, independent of cost consideration (i.e. of l ij ). B. To find the cheapest route from origin to terminal independent of capacity constraints (i.e. of c ij ). C. To find the maximal amount of goods that can be shipped from origin to terminal in a given time, T (here interpreting l ij as the time required to ship from P i to P j ). We shall discuss A first as being by far the richest in applications. It appears as a subproblem in a very large number of transportation-type problems, and from the theory which we shall develop one may obtain a large number of combinatorial results as well.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 22% of the total text.

Page 1 of 7

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

NETWORK FLOW THEORY

L. R. Ford, Jr.

P-923 August 14, 1956
The RAND Corporation 1700 MAIN ST. SANTA MONICA CALIFORNIA

SUMMARY

The labeling algorithm for the solution of maximal network flow problems and its application to various problems of the transportation type are discussed.

NETWORK FLOW THEORY [ title ]

L. R. Ford, Jr.

1. INTRODUCTION

A network (or linear graph) is a collection of points or nodes, some of which may be joined together by arcs. We shall denote the points by Pi, i = 0, 1, 2, ..., N. and denote the arc joining Pi to Pj in that order by Aij. (Note that there may also be an arc Aji joining Pj to Pi.) We may also have associated with the arc Aij a capacity cij and a length (or cost) lij. We shall assume these to be positive integers. We shall also distinguish two points in the network, PO, the origin, and PN, the terminal. One may think of this system as a rail network, in which the origin represents a factory or a warehouse at which goods enter the system, and the terminal represents a consumer for these goods who removes them from the system. The cij then represent upper bounds on the shipping capacity from Pi to Pjand the lij may represent variously the distance from Pi to Pj or the time required to ship from Pi to Pj or the unit cost of shipping from Pi to Pj. (We shall agree that if cij = 0 then lij = ∞ and that lij ≠ 0.)

Evidently many different problems may be posed with this framework. We shall discuss primarily the following three problems, stated verbally below.
A. To find a maximal steady state flow of goods from the origin to the terminal, independent of cost consideration (i.e. of lij). B. To find the cheapest route from origin to terminal independent of capacity constraints (i.e. of cij).

C. To find the maximal amount of goods that can be shipped from origin to terminal in a given time, T (here interpreting lij as the time required to ship from Pi to Pj).

Rand Corporation Page 1 Aug 14, 1956

Page 2 of 7

NETWORK FLOW THEORY

We shall discuss A first as being by far the richest in applications. It appears as a subproblem in a very large number of transportation-type problems, and from the theory which we shall develop one may obtain a large number of combinatorial results as well.

2. FORMAL STATEMENT OF PROBLEM A

A steady state flow of goods from origin to terminal is required to have the following properties:
(a) the amount flowing into Pi must equal the amount flowing out of Pi for i ≠ 0, N;
(b) the amount flowing along Aij must be less than or equal to Cij.

Subject to these restrictions, it is desired to maximize xF, the amount flowing out of P0, or equivalently, the amount flowing into PN. This may be presented as a linear programming problem as follows. Denote by xij ≥ 0 the flow from Pi to Pj. Then [ Equation omitted ]

Thus Problem A could be solved by a direct application of the simplex method to the above system.

3. SOLUTION O...