In this paper we presen algorithms for the solution of the general assignment and transportation problems. In Section 1, a statement of the algorithm for the assignment problem appears, along with a proof for the correctness of the algorithm. The remarks which constitute the proof are incorporated parenthetically into the statement of the algorithm. Following this appears a discussion of certain theoretical aspects of the problem. In Section 2, the algorithm is generalized to one for the transportation problem. The algorithm of that section is stated as concisely as possible, with theoretical remarks omitted. 1. THE ASSIGNMENT PROBLEM. The personnel-assignment problem is the problem of choosing an optimal assignment of n men to n jobs, assuming that numerical ratings are given for each man's performance on each job. An optimal assignment is one which makes the sum of the men's ratings for their assigned jobs a maximum. There are n! possible assignments (of which several may be optimal), so that it is physically impossible, except for very small n, to consider all the different assignments one-by-one. The problem is to find a reasonably efficient algorithm for obtaining an optimal assignment. Such an algorithm has been given by H. Kuhn [3] ; another algorithm, which is a variant of Kuhn's, appears in the present paper. A mathematical statement, of the problem follows: Let r. be the performance rating of man M for job Jj. A set of elements of a matrix are said to be independent if no two of them lie in the same line (the word "line" applies both to the rows and to the columns of a matrix). One wishes to choose a set of n independent elements of the matrix (r.) so that the sum of these elements is maximum. Let r max,, r., and let x r r. An equivalent problem is to choose a set of n independent elements of the matrix A (x.) such that the sum of these elements is minimum. This is the problem we consider. We assume for the present that the elements of A are integers. Two
Another example is the Hungarian algorithm for the assignment problem REF .
ALGORITHMS FOR THE ASSIGNMENT AND TRANSPORTATION PROBLEMS
Journal of The Society for Industrial and Applied Mathematics
Mathematics