HITCHCOCK TRANSPORTATION PROBLEM
IP.com Disclosure Number: IPCOM000128834D

Publication Date: 09Jul1956 
Publishing Venue
Software Patent Institute
Related People
Fulkerson, D.R.  Author
[+2]
Rand Corporation  Owner
B.A. Galler
Abstract
Language
English (United States)
Country
United States
Document File
11 pages / 115.7 KB
THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.
HITCHCOCK TRANSPORTATION PROBLEM
D. R. Fulkerson
P89O
July 9, 1956
The RAND Corporation 1700 MAIN St., SANTA MONICA, CALIFORNIA
SUMMARY
An exposition of the simplex computation for transportation type problems.
CONTENTS
SUMMARY.....11
Section
1. SIMPLEX METHOD.....6
2. OPTIMAL ASSIGNMENT PROBLEM.....19
3. UPPER BOUNDS ON VARIABLES.....20
4. THE TRANSSHIPMENT PROBLEM.....21
REFERENCES.....26
HITCHCOCK TRANSPORTATION PROBLEM
D. R. Fulkerson
The transportation problem was first formulated by F. L. Hitchcock ^{1} in 1941; he also gave a computational procedure, much akin to the general simplex method, for solving the problem. Independently, during World War II, T. C. Koopmans arrived at the same problem in connection with his work as a member of the Joint Shipping Board. The problem is thus frequently referred to as the HitchcockKoopmans problem.
Mathematically the problem has the form ( [ Equation no. ] 1) [ Equation omitted ]
^{1} Hitchcock, F. L., "The distribution of a product from several sources to numerous localities," Jour. Math. Phys., vol. 20, 1941.
Rand Corporation Page 1 Jul 09, 1956
HITCHCOCK TRANSPORTATION PROBLEM
subject to the constraints ( [ Equation no. ] 2) [ Equation omitted ] where a_{i}, b_{j}, a_{ij} are given. Feasibility is assured by assuming a_{i} ≥ 0, b_{j} ≥ 0, and Σ_{i}a_{i} = Σ_{j}b_{j}. A particular realization of the problem appears if we think of m sources of a commodity, the ith one possessing a_{i} units, and n sinks, the jth one requiring b_{j} units, and interpret a_{ij} as the unit transportation cost from source i to sink j. Thus the linear form (1) becomes the total transportation bill, to be minimized subject to fulfilling demands at the sinks from supplies at the sources. This interpretation is a paraphrase of Hitchcock's original statement of the problem.
To give some idea of the diverse applications of the transportation problem, we have compiled
the following list (by no means exhaustive) of problems which can be successfully attacked,
either directly as transportation problems or by subsequent developments of the theory:
(1) Suppose n men are to be assigned to n jobs, where man i in job j has a "score" a_{ij}; (a) find
an assignment of men to jobs which maximizes the sum of the scores ^{2}; (b) find an assignment
which maximizes the least score ^{3}.
(2) Considera network consisting of N points and inter connecting links. Let a_{i} ≥ 0 denote the
supply of a commodity at the ith point, b_{i} ≥ 0 the demand at the point, where a_{i}b_{i} ~ 0, and a_{ij} ≥ 0
the unit cost of shipping from i to j. Assuming that Σa_{i} = Σb_{i}, and that any point can act as a
transshipment point, find a minimal cost transportation program ^{4}.
(3) Given a network, let a_{ij} denote the length of the link from i to j. Find a chain of minimal length
connecting two given points ^{5}.
(4) Suppose B = (b_{ij}), i = 1, ..., m, j = 1, ..., n, is a given matrix. By a "walk through B from mn to
ln" we wil...