A discussion of the importance of a direct method in obtaining all the solu- tions of a transportation problem, and in obtaining solutions of more general problems, is followed by a discussion of methods of reduced matrices in which the transportation matrix is reduced, by a series of subtractions from rows and columns, to a transformed matrix to which the orthogonality condition is applicable. The direct method proceeds in a series of simple steps to the determination of zero terms having associated Xij values which eventually satisfy the row and column equations. Formal and informal versions are presented and a,pplication is made to several general problems.
Introduction
We seek methods which produce all the solutions of a transportation problem and which are applicable to more complex transportation problems. It is argued that direct methods should be considered. While the purest direct method is not practical, a modification substitutes some simple techniques for the minimization condition. With the methods of reduced matrices, we make subtractions from the rows and columns of the transportation matrix to produce a transformed matrix with all elements non-negative such that the non-negative integral Xij can be assigned toX the zero terms so as to satisfy the specifications for origins, i, and destinations, j. This work is a revised and extended version of an unpublished paper of 1955 [61. It is related to published work on (and machines programs for) more general problems published in 1956 [7] and 1957 [9] and [171.
The Problem
The transportation matrix, C = 11 cij 11, is an mnxn matrix with associated integral xj ? 0 to be determined according to the specifications
(1) M=1 xij = bj; Z=1 Xij = a; at = Z=, bj - N
such that (2) T = i xijci; is as small as possible.
General Solutions and Solutions of More General Problems
For most purposes it would seem that an important property of a proposed method for solving a problem is that it produces all the solutions, and not just one of them. For some purposes it may even be desirable that the solution may
* Received August 1965 and revised April 1966. Research supported in part by National Science Foundation Grant GP-4308.