ENGINEERING RESEARCH INSTITUTE THE UNIVERSITY OF MICHIGAN ANN ARBOR Final Report DEVELOPMENT OF MATHEMATICAL PROCEDURES AND MULTIPLE CRITERIA FOR ASSEMBLY OF LARGE WORK GROUPS Paul So. Dwyer Project 2413 U. S. AIR FORCE AIR FORCE PERSONNEL AND TRAINING RESEARCH CENTER AIR RESEARCH AND DEVELOPMENT COMMAAD CONTRACT NO. AF 41(657)-9 December 1936

Ue(\ wj/ 1 ut Nk caL (

The University of Michigan ~ Engineering Research Institute RESEARCH SUMMARY Dwyer, Paul S. "Mathematical Procedures and Multiple Criteria for Large Work Groups." Air Force Personnel and Training Research Center. Report Number 7, Contract No. AF 41(657)-9, December, 1956. A. Problem The Development of Mathematical Procedures and Multiple Criteria for Assembly of Large Work Groups. B. Method, Study of: 1. The mathematical solution of the group assembly problem with the method of reduced matrices. 2. The approximate solution of the group assembly problem using deviates. 3. The adaptation of the solutions to electronic digital computers. 4. The use of these methods in handling problems with multiple criteria, assembly scores subject to error, and related problems. Co. Conclusions 1. The method of reduced matrices is now available for the solution of the group assembly problem for large work groups with group score matrices. Machine versions of this method are available for IBM Type 650 and IBM Type 704 machines. 2. An approximate solution method based on deviates is also available, This method is also programmed for the Type 650 and the Type 704. 3. The method of reduced matrices is especially useful in handling the several problems which arise when the group scores are based on alternate criteria, and to modifications of the problem which feature incomplete groups errors in group scores, etc. 4o When the number of subgroups is large and the group scores do not lend themselves to further grouping without the introduction of large errors, it is better to use the approximate method rather than to force the grouping. D o Recommendations 1. The use of the method of reduced matrices as a solution for the general problem 111

The University of Michigan ~ Engineering Research Institute RESEARCH SUMMARY (Concluded) 2. The use of the method of reduced matrices in integrating the results when there are multiple criteria. 3. The use of the approximate solution based on deviates when an approximate answer is needed quickly. 4. The use of the approximate method (a) when the group scores are subject to large errors and (b) as an alternative to forced grouping. E. This study was conducted under Project 7713, Task 77232 in accordance with (TR, OSR, Ltr, etco). Qualified requestors may obtain copies of this report from ASTIA Document Service Center, Dayton 2, Ohio. Department of Defense Contractors must be established for ASTIA services, or have their "need-to-know" certified by the cognizant military agency of their project or contract, Unclassified reports are usually available to the public at nominal cost through the Office of Technical Services, Department of Commerce, Washington 25, D. C. iv

The University of Michigan ~ Engineering Research Institute Contract No.: AF 41(657)-9 Budget Project No.: 7-7713 Contract Title: Development of Mathematical Procedures and Multiple Criteria for Assembly of Large Work Groups Issuing Office: The Air Research and Development Command Contractor: The Regents of The University of Michigan Monitoring Agency: Operator Laboratory Field Unit No. 1 Attn: Dr. Robert L. French, Air Force Personnel and Training Research Center, Lackland Air Force Base, San Antonio, Texas Report Title: Mathematical Procedures and Multiple Criteria for Assembly of Large Work Groups Prepared by: Dr. Paul S. Dwyer December 1956 v

The University of Michigan ~ Engineering Research Institute ACKNOWLEDGMENTS The author of this report wishes to acknowledge the valuable contributions of several persons who have worked with him. He is particularly appreciative of the work done earlier by Mr. Glenn Graves and more recently by Dr. Bernard Galler in planning and working out the adjustments of the method needed for application to electronic digital computers. Mrs. Patricia Graves has helped write the material and has made many valuable suggestions regarding the development of the theory and the presentation. Several experts in linear pro-| gramming throughout the country have read previous versions of the material, particularly for the k = 2 case, and have made pertinent suggestions. The author finally wishes to acknowledge the contribution of Dr. Thornton B. Roby, who discerned the fundamental nature of the group assembly problem, made excellent suggestions as to the proper direction of the study, and acted as a consultant throughout most of its development. vi

The University of Michigan ~ Engineering Research Institute FOREWORD This report is a final report on the work on the Air Force Personnel and Training Research Center contract, "Development of Mathematical Procedures and Multiple Criteria for Assembly of Large Work Groups."' It is composed of two parts: A. Summary of Research Findings B. Administrative and Fiscal Information The work on this contract is closely related to, and in a sense is a continuation of and a supplement to, work on the contract, "Generalized Mathematical Procedures for the Optimal Assembly of Potentially Effective Combat Crews. "vt The work and results of this previous contract are described in a 14 chapter report,`Maximum Group Assembly Sums," prepared during the term of the earlier contract, and in a final summary report on the contract, dated June, 1955, entitled "Development of Generalized Mathematical Procedures for Optimal Assembly of Potentially Effective Crews, which is being prepared for release as an AFPTRC Research Report. The objectives of the contract, as stated in the contract itself and as amplified in a conference with Dr. Roby, are indicated next. The general objectives are the development of mat:lhematical procedures for assembling individuals in large work units and employing multiple criteria for assemblyo More specific objectives are listed below. I. The extension of results obtained for 3- to D5-man group assemblies so as to secure the optlmal assignment of individuals to groups of larger sizes. 2. The development of economiclal means of accomplishing data transformations and practical simplifications of the problem encountered in reducing grouped matrices. 35 The translation of these procedures into programs suitable for use with electronic digital computers. 40 The use of appropriate approximate solutions when the criteria for assembly are based on fallible scores and consideration should be given to errors in group scores. 5. The feasibility of simultaneously employing multiple criteria of clasvii

The University of Michigan ~ Engineering Research Institute FOREWORD (Continued) sification such as may be desirable if both technical qualifications and social factors are to be considered in forming work groups. Additional specific objectives were agreed on during the July, 1955, conference with Dr. Robyo These include: 6. A revision of substantial portions of the 14-chapter report of the previous contract, necessitated by the development of improved techniques and theory in the later periods of the contract, which were not incorporated in the draft presented. 7. Additional work directed toward the further analysis and improvement of the reduced grouped matrix transformations. 8. The identification of the basic mathematical problem in group assembly with the basic mathematical problem of other applied problems such as the general transportation problem. 9. The determination of the extent of the relationship existing between the group-assembly problem and other related problems in linear programming. 10. An investigation of the effects of coarser groupings. Part A of this report presents the summary of findings of six reports which have been prepared during the term of the contract. In these research reports the work and results of the 10 objectives of the contract are described in much more detail, both theoretical and illustrative. The titles and dates of these research reports are: Report Number 1. "The Solution of the General Assembly Problem with a Method of Reduced Matrices,"- March, 1956, and December, 1956.~ Report Number 2. "Economical Means of Accomplishing Data Transformations and Practical Simplifications of the Problems Encountered in the Problem of Reducing Grouped Matrices," April, 1956, and December, 1956. Report Number 3. "Adaptation of the Method of Reduced Matrices to Electronic Digital Computers," April, 1956, and revised December, 1956. Report Number 4. "The Solution of Problems Mathematically Equivalent to or Related to the Group Assembly Problem," October, 1956, and December, 1956. vTiii

The University of Michigan ~ Engineering Research Institute FOREWORD (Concluded) Report Number 5. "The Use of Multiple Criteria of Classification," October, 1956. Report Number 6. "The Use of Appropriate Approximate Solutions when the Group Assembly Matrix Consists of Fallible Group Scores," November, 1956. These six reports describe, for the most part, the results of the work on the contract. In addition, there was a revision of the 14chapter report described in objective 6. Correction sheets were sent for chapters 1-9, 12 and 14. The material in chapters 10, 11, and 13, and to some extent that of 8, may be considered to be superseded by the material in reports 1, 2, and 3 of the present contract. Also, there was an additional extension of contract time to December 15, 1956, to permit the development of programs for the IBM Type 704 and for a study of the implications of workable machine solutving such problems as those raised by objectives 4 and 5. These results are included in the six reports and, indeed, Research Report Number 3 was rewritten so as to include the latest results using machine methods, The purpose of Part A, then, is to present concisely the research findings of the study. The purpose of Part B is to present such basic administrative and fiscal information as should be made available to the Air Research and Development Command. ix

The University of Michigan ~ Engineering Research Institute ABSTRACT FOR PART A This report describes the present solution of the general group assembly problem with the method of reduced matrices. It provides methods by which the method of reduced matrices nay be extended to apply to problems with crews of more than three to five men and indicates improvements in the details of solution. With slight qualification, the details have now been worked out so that it is possible to solve the general group assembly problem quickly on a- first class digital computer such as the IBM Type 704. Modifications of the method permit the solution of less extensive problems on a less complicated electronic computer such as the IBM Type 650. Methods have also been perfected, and codes are available for the IBM Type 650 and the IBM Type 704, for obtaining good approximate solutions to the group assembly problem in a relatively short time. The general method of reduced matrices is immediately applicable to the general Hitchcock transportation problem and to several other problems in linear programmingo With modifications it can be made applicable to a wider class of problems. A slight adaptation makes it possible to find a permutation subset with maximum sum and to solve the general group assembly problem in which one or more of the men trained for some position may be unavailable. The method of reduced matrices seems to be ideal for handling the various types of problems when there are multiple criteria, since the finally reduced matrix provides essential information for comparing the effectiveness of alternate solutions. Also, the method can be modified to give some possible solution in a shorter time when the group scores are subject to error. When the errors of the group scores are large, an approximate solution based on the kdimensional deviates seems particularly useful. x

The University of Michigan ~ Engineering Research Institute TABLE OF CONTENTS Page PART A. SUMMARY OF RESEARCH FINDINGS 1 Section I. A Method of Reduced Matrices 2 Introduction 2 Mathematical Statement of the Problem 3 The k-Dimensional Supermatrix 4 Subtraction of Constants 4 Transformation to a Minimization Problem 4 The Conditions of Solution 5 Methods of Reduced Matrices 5 Extreme Transformations and the Reduced Matrix 7 Further Reduction of the Matrix 8 Determination of Inconsistent Linear Forms 8 Determination of Reduced Matrix Transformations 9 The Elimination of Negative Solutions 9 The Elimination of Fractional Solutions 10 Multiple Solutions 11 Summary of Research Findings 12 Section II. Economical Means of Accomplishing Transformations and Approximate Solutions 13 Determination of Inconsistencies Without Formal Reduction 13 Compact Presentation of the Elimination of Algebraic Incon sistencies 13 Compact Presentation of the Elimination of Negative Solutions 14 Solutions with Large k 14 Approximate Solutions Using Deviates 14 Summary of Research Findings 15 Section IIIo Adaptation of the Method of Reduced Matrices to Electronic Digital Computers 16 Introduction 16 The Use of the Homogeneous Transpose System in Determining Algebraically Inconsistent Linear Forms 16 Reduction to Echelon Form 16 The Use of the MIDAC and IBM Type 650 17 Applications 17 The General Program for the IBM Type 704 18 Approxiamate Solutions 19 Summary of Research Findings 19 xi

The University of Michigan ~ Engineering Research Institute TABLE OF CONTENTS (Continued) Page Section IVo Problems Equivalent to or Related to the Group Assembly Problem 21 Introduction 21 Equivalent Mathematical Problems 21 The Solution of the General Transportation Problem 22 The Determination of Permutation SubsetS Having Optimal Sums 23 The Group Assembly Problem with Incomplete Crew Assignments 23 The Group Assembly Problem with One or More Men Unavailable 23 Problems Mathematically Related to the Group Assembly Problem 24 An Extended Method of Reduced Matrices 24 The Solution of Transportation Problems with Additional Equality Conditions 24 The Symmetric Reduction of Symmetric Matrices 25 The Solution of Certain Types of Traveling-Salesman Problems 25 Summary of Research Findings 25 Section V. The Use of Multiple Criteria of Classification 27 Introduction 27 The Reduction of the Alternative Group Score Matrices 27 Use of Correlation of Criteria 28 Measures of Adequacy with a Preferred Criterion 28 The Determination of a Most-Representative Criterion 28 The Determination of a Composite Criterion 29 Joint Use of Multiple Criteria 29 Summary of Research Findings 29 Section VI. The Use of Appropriate Approximate Solutions When the Group Assembly Matrix Consists of Fallible Group Scores 31 Introduction 31 Modified Matrices 32 Fallible Group Scores with Small Errors 32 Possible Optimal Solutions 33 Modifications of the Method ofo Reduced Matrices in Order to Obtain Some Possible Optimal Solution 33 Use of Approximate Solutions Based on Deviates 33 Effects of Grouping and the Use of IBM Type 704 34 Summary of Research Results 35 PART Bo ADMINISTRATIVE AND FISCAL JINFORMATION 37 Personnel 38 Fund Utilization 39 xii

The University of Michigan * Engineering Research Institute TABLE OF CONTENTS (Concluded) Page General Accounting 39 Research Salaries 40 References 41 xlll

The University of Michigan * Engineering Research Institute PART A. SUMMARY OF RESEARCH FIDINGS

The University of Michigan ~ Engineering Research Institute SECTION Io A METHOD OF REDUCED MATRICES Introduction Reports on the work of a previous contract have presented the general features of a method which uses successive matrix reduction in the solution of the group assembly problem. These reports include the final report of the previous contract, entitled "Generalized Mathematical Procedures for the Optimal Assembly of Potentially Effective Crews,1l and the more detailed 14-chapter extended report, entitled "Maximum Group Assembly Sums."2 Although the research described in these reports was directed toward the general assembly problem, the notation, the techniques, and most of the illustrations featured the solution of the, problem with small k' (the number of different positions represented by the group). The research necessary to attain the objective of generality has led to improvements in several aspects of the method and to the extension of the theory on which the method is based since some of the techniques which are quite satisfactory for problems with small k are inadequate for the more general problems. The nature of the general assembly problem is discussed in the earlier reports,l 2 which also contain references to previous material, and especially in a report by Rob;y22 The nature of the problem of optimum group assembly and a description of the method of reduced matrices is presented in a nontechnical report, tIThe Problem of Optimum Group Assembly, "9 which was prepared in Augu;t, 1955, for inclusion in Proceedings National Research Council Symposium. on Personnel, Trai ing and Human Engineering, held at Washington, D. C., November 14-16, 1955. In the earlier work, the specia1 case with k - 2, equivalent to thepersonnel-classification problem,l 52 seemed both simple and important, so that special applications of the method of reduced matrices have been designed for it, These are described in Chapter VIII:of the extended report of the previous contract. The methods are also applicable to a corresponding problem in applied economics, the Hitchcock transportation (distribution) problemo17,18 A paper, entitled "The Solution of the Hitchcock Transportation Problem with a Method of Reduced Matrices,"' was written in June, 1955, and submitted to Econometrica, After consultation with Dr. Roby, copies of the paper were sent to experts throughout the country who were interested in this problem. The com.menets of these people, and eventually the comments of the editors of Econanetrica indicated that the material was not yet ready for publication. In particular, additional specific techniques were needed for the detemnination of the specific| reduced grouped matrix transformations. 2

The University of Michigan ~ Engineering Research Institute The determination of suitable specific techniques for determining these transformations was a major topic in the improvement of the method of reduced matrices during the first two quarters of this contract. In December, 1955, a revised version of the paper "The Solution of the Hitchcock Transportation Problem with a Method of Reduced Matrices" was made which met the objections previously raised. This revised version was not submitted to Econometrica since the specific techniques worked out for solving the k = 2 case are essentially the same as those used in handling the general case, although copies of the revision were sent to some of the experts who had made earlier comments, Thus, the work of the first part of this contract established formal methods which are applicable to problems with both large k and small k. No special treatment is given to the k 2 case in the reports of this contract since this case is covered by the general case. This remark holds for both hand and machine solutions. The determination of these specific techniques for determination of the reduced grouped matrix transformations has other effects on the solutions of k - 2 and k = 3 problems. Since these techniques can be applied to the reduced matrix and the matrix resulting from the extreme transformations, as well as to the reduced grouped matrix, the transformations described in Chapters VIII X, and XI of the extended report of the previous contract, which transform a reduced matrix to a reduced grouped matrix, need not be applied. The elimination of this type of transformation does, in many cases, cause the introduction of negative solutions, but the method of reduced matrices, as improved during the term of this contract, utilizes negative solutions in obtaining the additional transformations necessary to complete the reduction process. The remainder of this section is, in a sense, a brief nontechnical description of the results described in Draft Research Report Number 1, "The Solution of the General Group Assembly Problem with a Method of Reduced Matrices, 3 which was prepared in March, 1956. The research findings in this report (and the later reports) are essentially of a mathematical nature, so any nontechnical description cannot be, in one sense, adequate. The full impact of these results can be fully understood only with the study of the earlier reports The remainder of Part A of this report is devoted to an attempt to indi cate the nature and implications of the research f indings in nontechnical form. The section sub-headings generally parallel the section headings of the research reports. Mathematical Statement of the Problem The extension to problems with large k requires a more precise notattion than that required for problems with small ko Accordingly, Draft Research Report Nuber 1 features the introductioi, description, and illustatinof such a notation. The notation covers not only the case of unit frequencies but also 3

The University of Michigan ~ Engineering Research Institute the grouped problems and the use of nonzero x, as well as the more general X, the use of subsets of x having associated reduced matrix scores of zero,'etc. The k-Dimensional Supermatrix The extension to problems with large k implies the formation of a supermatrix in many dimensions. For hand solution, and also for machine solution, it is essential that the elements and subdimensions be ordered in such a way that the results may appear in some two-dimensional form. A form of this type was worked out and is illustrated in the report. For machine computation, it is essential that the elements of the supermatrix be ordered in some onedimensional form. This is accomplished by using the collected subscripts as a digital number. Subtraction of Constants The fact that any constant may be subtracted from all elements of some subdimension without changing the solution (although the solution sum is changed thereby), demonstrated in Chapter II of the extended report of the previous contract, is basic to the method of reduced matrices. If ji represents the ij group in dimension j, then we may subtract the constant uji from all the elements in this subdimension without changing the solution. Suitable positions are utilized for the location of these constants in the two-dimensional display, so that the calculations are readily made. In a sense, the method of reduced matrices consists of successive subtractions of these constants, so as to obtain a finally reduced matrix. Transformation to a Minimization Problem The method of reduced matrices is immediately applicable to minimization problems since an objective is the reduction of the supermatrix by subtraction of constants from the rows, columns, layers, etc., to a finally reduced matrix consisting of positive and zero terms, in which the elements of the solution correspond to zero terms. Maximization problems can be reduced to minimization problems by multiplication of all the elements by -1 The transformation of a maximization problem to a minimization problem is incorporated in the reduction process. Subtractions of the smallest value in each row transform the matrix to one with nonnegative elements. 4I

The University of Michigan ~ Engineering Research Institute The Conditions of SolutionWe wish to minimize, subject to the equations of condition which specify that the sum of the assignments in any subdimension m-ust equal the fre. quency,associated with that subdimension, the following quantityo T(~) Z X(il o ik) O) (i.ooi.), where G(O)(il..ik) is a supermatrix with nonnegative elements. Using Lagrange multipliers. we arrive at the necessary conditions. The necessary conditions are that there exist constants, uil,. u i2, Uik, such that G(O)(ili2...ik) (uil + ui2 + + uik) = O for X(ilio...ik) > O, and |G(iO)(1i2..i) (uil + + + Ik) U 0 always These conditions are known as the conditions of solution. A solution consists of a subset, S, of values of i i2ooik with the associated X(iliai...ik) > 0, which satisfy the equations of condition and the conditions of solution. However, there is no specification in the derivation that X(iii2.,ik) must be integral. Since an integral solution is required, a method based on the conditions of solution and the equations of condition opens up the possibility of obtainiing solutions which are not acceptable. In this case, further steps must be taken in order to obtain acceptable solutions. In minimization problems, the conditions of solution are expressed in ~terms of the G matrix. Methods of Reduced Matrices Methods of reduced matrices, designed to perform certain reductions of the matrix, are accomplished by subtracting constants from the dimensional subsets of- Gi(O) values, so that finally a matrix results which has no negative elements and enough zero elements so that the XVs associated with them satisfy the equations of cordition When such a matrix results, the va lue of the transformed assembly sum is zero, and there can be no smatller transfonrmed assembly sum, Hence,. there can be no larger untransformed assembly sum than that associated with this solution, 5

The University of Michigan ~ Engineering Research Institute The real questions in any method of reduced matrices are how to determine the subset of elements from which the subtractions are to be made and how to determine the values of the constants to be subtracted so as to produce an efficient computational process. Special methods of reduced matrices have been worked out for special problems. We consider a method of reduced matrices to be one in which the operational objective of the method is either the explicit or implicit determination of a finally reduced matrix of nonnegative terms, where the zero terms of the matrix identify the solution regardless of whether the finally reduced matrix is given explicitly or not. Thus, there is the method of optimal regions for the implicit determination of the completely reduced matrix 14 and the detailed method of optimal regions for the explicit determination of the completely reduced matrix,15 which are methods for solving the personnel-classification problem. Also, there is the Kuhn-Egervary method for handling the assignment problem,19 the Mnkres method..' and the FordFulkerson method, closely related to the Kuhn-Egervary method for the solution of the two-dimensional transportation problem,* and the Dantzig-Ford-Fulkerson generalization,* The spirit of each of these methods is similar to that of the method of reduced matrices described here. Thee othese o methods build up partial solutions consisting of partial assignments to the problem, and the iterative steps provide for the addition and replacement of elements of the solution. The method of reduced matrices of this report is a general algebraic method in which the solution is obtained by applying the al ebraic equations of condition at each step to all p.ossible terms indicated by the conditions of solution. This algebraic method may feature negative solutions in the solution process and, in this respect, differs funldamentally from the other known methods of reduced matrices which avoid negative frequencies. The method of reduced mar trices described here is a simple general algebraic method, applicable not only to the special problems for which the methods described above are designed, but to a general class of problems with k of any size, in which a linear function of the G"s is to be maximized or minimized subject to the equations of condition. The method develops a systexmatic way for introduclng additional zero terms in the rows and columns of the reduced matrices. After applying the extreme transformations, which result in a matrix having at least one zero in *Formal references to the Ford-Fulkerson method and the Dantzig-Ford-Fulkerson generalization are not available, For the present, this material may be found in the working papers of the RANID Corporation: Fulkerson, D. R., and Ford, L. R., "A simple algorithm for finding maximal network flows and an application to the Hitchcock problem."' The RAND Corporation, Paper P-743, September 26, 1955. Ford, Lo R)o, and Fulkerson, D. Ro., "Solving the transportation problem." The RAND Corporation, Paper RM-1736, June 20, 1956o Dantzig, Go Bo, Ford, L. R., and Fulkersonn Do RI "A primal-dual algorithm.'t The RAND Corporation, Paper RM-1709, May 9, 1956.. ~~~~~~~~6

The University of Michigan ~ Engineering Research Institute every subset of every dimension, it applies the equations of'condition to the prospective elements of the solution. Either an algebraic solution. results or a series of indecompos able linear'combinations of inconsistent equations of condition result. These reveal the amount of the inconsistency, the subset of val-N ues of ji from which the subtractions are to be made, and the constants to be subtracted. The final stages' in determining a solution of integral values often deal with the elimination of negative and fractional values from the algebraic solution Once the solution is determined.the value of the minimum sum is obtained by applying the solution values to the G(O) terms and summing, or from the weighted sum of the constants subtracted. An alternate interpretation.of the method of reduced matrices should be stated, This is made for minimization problemns with nonnegative elements, since maximization problems are reduced to these. At each reduction the net sum of the subtractions Z u.jif U ji ji is to be positive. The acumulation of these subtractions Z Z uji(t)fji t ii.may be called a (lover) bounding set set um. This bounding set'sum increases and eventually becomes the minimum G when the solution.s reached. This solution does- not include negative values, sin ee a transformation may always be found which increases the bounding set sum in. such a.case, but it may be fractional when k > 2 The alternative interpretation then is that we maximize the bounding:set sum rather than minimise the transformed group assembly sum. If a positive- fractional solution results, an additional step is necessary beyond the at-0 tainment of the maximum bounding set sum. Etreme Transformations and the Reduced Matrix We first subtract corinstants from the various subsets of each dimension, so that at least one zero appears in each -subset. This may be done in -kt different orders.'With -fully' automatic machines some arbitrary order, such as 1, 2, 35,, k, is selected for these $subtractions, but when working by hand it seem wise to select at each step that subtraction which makes maximum contribution to the bounding set s;um. In maximization problems, the reduction to a minimization roblem mayT be incorporated in the margina. transformation process, These mar7

The University of Michigan ~ Engineering Research Institute ginal transformations continue until there is at least one zero in every subdimension. When this point is reached, the marginal transformations are completed and the (super) matrix is said to be reducedo In minimization problems the reduction is performed directly by the extreme transformations. The preliminary transformation resulting in G(0) is not needed, Further Reduction.of the Matrix Occasionally a reduced matrix has enough zero terms to satisfy the equations of condition.'Usually,. however, this is not -the case, and additional reduction of the matrix is indicated. This is accomplished through the use of transformations which introduce additional zero terms without disturbing the zero terms previously present. In the case of special problems, such as those with k = 2, additional simple transformations are available for further reduction of the matrix. These become more complicated with increasing k, however, so they are not featured here. We next examine the general reduced matrix transformations, deters mined from a study of the equations of condition as applied to the zero terms of the reduced -matrix. The resulting general transformations are applicable to specific, as well as general, cases. Two basic problems involved in the determination of these transformations are (a) the determination of the.particular dimension subsets from which the subtractions are to be made, together with the sign of the quantity to be subtracted from each subset, and (b) the determination of the absolute values of the amounts to be subtracted. These are discussed below. Determination of Inconsistent Linear Forms Methods are described in Section 9 of the first research reports for determining specific inconsistent linear forms of the equations of condition if such forms exist. For hand work the forms result from the reduction of the equations to essentially triangular form. For machine work the forms result from the reduction of the equations to echelon form. The formal determination of these inconsistent linear forms, together with the establishment of the fact that each provides the basis for the auto8

The University of Michigan ~ Engineering Research Institute matic determination ofs a transformation needed in the further reduction of the matrlx, is one of the most important research results of the work on this con - tract Determination of Reduced Matrix Transformations As suggested above, any inconsistent form of the equations of condition may be uied to determine a transformation which preserves all the zero elemeints of the set S and adds at least one new zero element to the set. Thus, the process 18 designed to introduce an additional term in S at each step, to replace the selected inconsistent form by consistency, and to produce an incre~ ment to the bounding set sum.'If there are m inconsistent forms, then the process necessarily converges- to an algebraic, solution after m (or less) steps, since at least one inconsistency i-s eliminated at -each step. Thi:s solution may not be acceptable, however, sinee it may contain negative or fractional values. ModifSications of the method appropriate to these situations, essential to the use of the metlod in general problems) are described below. The Elimination of Negative Solutions Firmt we -assume thatthe particular solutioen is the only -solution resulting from the reduction method, i.e. that there are no elements of S which play the role of parameters~ Then, the existence of a solution with -at least one negative x shows that there is at least one inconsistency (in the desired sense) Now a linear form of the equations of condition leads to the relation (ii o 9orik) D where D > 0 This irnconsistent linear form serves as the basis of the next transformation, as before~ There is always a finite positive incrEement to the bounding set sum, which guarantees that the process converges, and there always is a new zero inutroduced into the reduced matrix, but there is no guarantee that all the zero terms, remain zero e.der this transformation. As a matter of fact, it is guaranteed that the term G(h)(il...ik) O, corresponding to the negative x(i1i -.ik), beomes positive. The process continues until all negative X-ts have been elimineated and the bounding set sum attains its maximum value. The resulting matrix is said to be "finally reducedi'~ If the solu-w. tions of the equations of condition, as applied to this matrix are integral, a final solution is obtained and the matrix ifs "completely reducedo' Othaerwise, a fractional solution is avraiab=Le and further teps are necessary.. ~~~9

The University of Michigan ~ Engineering Research Institute The Elimination.of Fractional Solutions The techniques described above lead us to the place where we have a particular solution with nonnegative, but not necessarily integral, elements These elements, if not integral, must at least be fractional. This results from the fact that a solution of Ax = b, if it exists, is also a solution of the equation ATAx = ATb, in which the number of equations is equal to the number of unknowns and the elements of ATA and ATb are expressed in digital form. Now, by Cramerts rule, every element of x can be expressed as the ratio of two determinants, each of which is composed of elements of ATA and/or ATb, Hence, the values of x can be expressed in fractional form. Moreover, there is always a problem, whose solution is integral, which has the same finally reduced. ma trix~ For, if we form a problem by multiplying every frequency in -every subdimiension by the lowest common denominator of all the denominators of all the x terms, we have a problem with an integral solution which has the same finally reduced matrix as the problem with the fractional solution. Hence, the finally reduced matrix of the original problem is a completely reduced matrix for the problem with amplified frequencies. The bounding set sum attains its maximum value, and no further reduction of the matrix, in the sense described above, is possible. We are hence faced with a new combinatorial problem, since the reduction process described above cannot be carried further. Given a fractional solution, how can we obtain an integral solution having the smallest sum? We might resort to combinatorial methods and select for the new terms of S the smallest nonzero elements of the finally redlueued matrix. In many practical problems this solution is quite satisfactory and leads to the desired solution quickly. For theoretical purposes, however, this type of solution is not satisfactory. Accordingly, we have devised a method in which the new combinatorial problem is cons idered to be an exten ion of the previous combinatorial problem, so that the results of the first problem may be used in answering the second. We consider the fractional solution to be a first approximation to the- integral solution and. modify it with the addition of elements of S, in which the new elements play the role of parameterso These parameters must be such that they lead to fractional contributions to the solution which are complementary to the particular fractional solution. Necessary conditions for meeting this requirement are determined from the relations resulting from the reduction process used in the fractional solutions. The elements to be used as possible parameters are those satisfying these necessary conditions., This problem is of theoretical interest In case there are several subsets of elements of the solution having denominators which-do not have common integral factors, it is possible to use the relations resultin from the 10

The University of Michigan * Engineering Research Institute reduction process to reduce the solution of this general problem to the solu tion of modified elemental problems. This result is described in the paper "'A Theorem on the Multi-Index Transportation Problem" (preliminary report) which was presented by title at the October 27, 1956, meeting of the American Mathematical Society at Cambridge, Massachusetts. We feel that additional study iS appropriate to this question of fractional solutions and that, if additional questions arising from the results of the work on this contract were to be studied, this is the topic of most general and theoretical interest.* On the other hand, for the type of data available for group scores in Air Force group assembly problems, we feel that the methods described in Section 12 of Research Report Number 1 are quite satisfactory, In adapting the method of reduced matrices to IBM Type 704 the time available and the complicat..ions of the programs have permitted only the programming- through the determination of the fractional solution. An integral solution which is either optimal or is very nearly optimal can then be obtained quickly by hand by rounding off the fractions subject to the equations of con — dition The programing of the elimination of the fractional solution is the next step indicated in the mechanization of the process ** Multiple Sollutions The teehniques for the elimination of negative solutions and the elimination of fractional solutions des ribed above deal with the case in which there are no superfluous zeros in S' This is generally true for practical problemsn where the original group scores are determined with proper precision, but it is easy to construct problems in which this iS not the case. In general, a multiplicity of zero elements in S' idicates a multiplicity of olutions. In a sense, the multiple zeros associated with the different solutions interfere with the process of the determination of a single solution. Therefore, it seems w.-s to coneentrate. on the "ttermim ion of a single solution first by'replacing su-* perfluous zeros by small positive numbers which have an upper bound which is small enough so that the accumuLatioln cannot change the va.lue of the group assembly sum when it is rounded off to the appropriate digits. This elimination of superf luous zero "is accomplished by the random introduction of very $mall constants. In hand methods these may be introduced at the stage of the reduction process in which. itt s eviden.t that there is a *DrC Dwyer expect$s to makfe additional studies on this topic even though the research is not supported by contract fundSo |**Dr~ Galler expects to contirxee with this programming evenl though the re~search | is not supported with conrtract fulnds~ 11

The University of Michigan ~ Engineering Research Institute surplus of zeros. With machine methods it seems appropriate to subject every original element to a perturbation of this sort. Any resulting solution will be some one of the many possible solutions. In many cases a single solution, which is as good as any other solution, is satisfactory. If the full set of solutions is indicated, and in problems with many surplus zeros this set may be very, very large, it is recommended that the particular solution be supplemented with a parametric solution, where there is a parameter corresponding to each surplus zero term. Summary of Research Findings The method of reduced matrices is perfected to the place where it is an efficient method for solving the group assembly problem (given the group scores), no matter what the number of positions in the crew. 12

The University of Michigan ~ Engineering Research Institute SECTION IIo ECONOMICAL MEANS OF ACCOMPLISHING TRANSFORMATIONS AND APPROXIMATE SOLUTIONS Determination of Inconsistencies Without Formal Reduction The formal reduction process described in Section I is designed for application after the use of the marginal transformations, ioe.o as soon as the matrix is reduced, and for all following transformations. However, in many problems it is at once apparent, without formal reduction, that certain inconsistencies exist. It seems wise to recognize these inconsistencies and to remove them before' starting on the formal reduction process. This device is not "only' recommended for hand computation problems, but it is built into the machine program for the IBM Type 7040 It is clear that the use of these easSily determined inconsistencies may not give, at each step, the largest increment to. the bounding set sum. However, we know that all the m inconsisterncies will be removed after at least m steps, and the important thing is the eventual elimination of all inconsistencies and not necessarily the.use at each step of the ilconsistency which permits maximum increment to the bounding set sum. The sort of inconsistencies discovered informally are those in which certain equations of condition are obviously not satisfied. For example, consider a k = 2 problem with row frequencies fi and column frequencies fjo Suppose that the value of G(ij) 0 and that there is no other zero term in row i and column jo Then if fi' fj. an inconsistency is indicated at once, since the application of the equations of condition for row i and column- j gives xij; f i and xij = fj so that x -xi = 0 = fi - fj # 0. A number of "obvious" inconsistencies of this kind can frequently be spotted easily in hand problems, and certain types can be identified by machines. Compact Presentation of the Elimination of Algebraic Inconsistencies After the elimination of obvious inconsistencies, as described above, the solution is directed toward the formal reduction process. Here a considerable simplification o.~ the reduction process is attained by the simple device of adding the new information to the previous reduction form. A column at the right is used for the new element of So The inconsistency used in the se13

The University of Michigan ~ Engineering Research Institute lection of the new element of S is shown to reduce to a consistency, and additional rows are inserted at the bottom of the computing form to show the transformations of the inconsistencies which result from the introduction of the new element in S, One of these inconsistencies serves as the basis of a new transformation, and the process continues, using a single reduction form, until all algebraic inconsistencies are removed. This process is described and illustrated in Section 4 of Research Report Number 2.4 This process also has been incorporated in the program for the IBM Type 704 and greatly facilitates the machine solution. Compact Presentation of the Elimination of Negative Solutions The idea described above can be modified so as to make it applicable to the elimination of negative solutions. The theory and illustrations for this are presented in Section 5 of Research Report Number 2, Solutions with Large k The research findings resulting from the work on this contract, described in Research Report Number 1 and Research Report Number 2, make possible the practical solution of problems in which k is much larger than 2 or 3. As an illustration, the process was applied, in Section 6 of the second research report, to a k = 7 problem. The solution was satisfactory and has since been obtained on the IBM Type 650 and the IBM Type 704 electronic digital computers. Approximate Solutions Using Deviates The approximate solution based on deviates in all dimensions, as discussed in Chapter XII of the report of the previous contract, seems especially appropriate to the use with problems with large k in which an approximate answer is desired quickly. This method is available for hand computation and has now been programmed for the IBM Type 650 and the IBM Type 704. These approximate solutions can be obtained very quickly, once the material is available for the machineo The efficiency of the approximate solution ranges from 89* to 100o in the problems we have run. The efficiency, defined in Chapter XII of the report of the previous contract, is essentially the percentage of distance from the mean of all assembly sums to the optimal sum, -14

The University of Michigan ~ Engineering Research Institute which is covered by the distance from the mean of all assembly sums to the assembly sum corresponding to the approximate solution. Summary of Research Findings Additional improvements in the method of reduced matrices make the method more useful as a practical method, Also, an approximate method based on deviates provides quite satisfactory approximate answers when these are neede.d quickly.'5

The University of Michigan ~ Engineering Research Institute SECTION III o ADAPTATION OF THE METHOD OF REDUCED MATRICES TO ELECTRONIC DIGITAL COMPUTERS Introduction The improvements of the method of reduced matrices, described above, make possible the complete mechanization of this method so that it can be adapted to electronic digital computers. However, certain possible adjustments in the method were studied in order to make it more suitable to machine computation. These possible adjustments involved the use of the homogeneous transpose system in determining algebraically inconsistent forms, and the reduction of the equations to echelon form rather than triangular form. The Use of the Homogeneous Transpose System in Determining Algebraically Inconsistent Linear Forms During the earlier phases of the project it was felt advantageous to make use of the homogeneous transpose system of equations ATx = 0 (where A is the original matrix of the system Ax = b) in order to decide whether or not there was a solution at hand and to determine a transformation in case no solution was yet availableo24 This method was used successfully in the programs for MIDAC and the IBM Type 650, but it soon became apparent that the process could be even more efficient with the method of linear forms, described in Section 9 of Research Report Number 1. This latter method is used, in modified form, in the program for the IBM Type 704~ Reduction to Echelon Form Although the reduction to triangular form seems quite satisfactory for hand solutions, the further reduction to echelon form is preferable for theoretical purposes. With machine solutions in which the many -numerical operations are performed automatically, it seems wise to concentrate on the reduction to echelon form. From the theoretical standpoint this use of echelon form rather than triangular form is the major adjustmenrt in adapting the method of reduced 16

The University of Michigan ~ Engineering Research Institute matrices to machines.5 The argument, on which the method is based, takes on some different form, so that it has seemed wise to carry through the complete argument (for the —reduced matrix transformations) in a notation more suited to machine techniques. This is done in the paper "Translating the Method of Reduced Matrices to Machine Compilation,"1l which is included as an appendix to the third research report. The Use of the MIDAC and IBM Type 650 The adaptation of the method of reduced matrices to the MIDAC and the IBM Type 650 is described in Section 4 of Research Report Number 3. The specific description of the 650 programs' is included as an appendix to this report. Applications The above pr'ocedure was used for several k = 2 problems on the MIDAC. With the availability of the Type 650, emphasis shifted to the use of this machine. (The MIDAC was undergoing changes in storage capacity and has not- been, during the past few months, reliable enough for work on the contract.) The results described here were obtained prior to the writing of the original Research Report Number 3 in April, 1956. The frequency, f, indicates a problem with groupings. Nature of Problem Freue Solution Time 3 x 4 f 1 min 45 sec 6 x 6 1 2 min 5 sec 4 x 5 f 2 min 30 sec 3 x 5 f 2 min 30 sec 10 x 10 f 10 min 23 sec A program which is not fully automatic, in the sense that partial results on cards must be reintroduced into the machine, was worked out for the IBM Type 650 in the spring of 1956. Due to the limited storage capacity of the 650 computer, the size of the problem which can be handled is limited by the condition: s(s - k + 1) _ 235 17

.The University -of; M:ichigan!; ~ Engineering Researchl Institute where s = n1+ n+... + nk and nj is the number of rows in the jth dimension. If the 650 were equipped with tape units, this program could be modified so as to handle larger problems. It is to be emphasized that this program is a general program for k _ 7. No special program is needed for the case with k = 2. Summary information about each solution is presented, Size of Problem Frequency Time Maximum or Minimum 3 x 4 f 10 min minimum 6 x 6 f 15 min minimum k = 7 (nj = 2) f 45 min maximum As indicated above, the problems which can be worked with this program on the 650 are limited in scope, although many grouped. problems meet these specifica. t ions. The program is presented for those who have access to IBM Type 650 machines and who have problems of this size. The use of the IBM Type 704 is recommended if available,for problems of any size. The General Program for the IBM Type 704 When the method of reduced matrices was sufficiently developed to be adapted to large-scale computation, arrangements were made with General Motors Corporation to use the IBM Type 704. located at the General Motors Technical Center. A general program with k 4 20 has been written for this machine. A copy of this program is included as Appendix B of the revised Research Report Number 3. Problems have been worked on this machine. The results are summarized below. k Size Freque ncy Maximum or Minimum Time for Solution 2 3 x 4 f minimum 45 sec 3 4 x x 5 f minimum 2o 3 mrl 7 2 x 2 x 2 x 2 x 2 x 2 x 2 f rmaximum 2 4 min 2 10 x 10 f maximum 4~8 min 4 3 x 3 x 3 x 3 - maximum lo2 min. Although no problems have as yet been solved for which times are available on a similar machine with the simplex method, the evidence inrdi.cates that the method of reduced matrices is superior to the simpIlex method even for i k = 2 and especially for k > 2. 18

The University of Michigan ~ Engineering Research Institute Approximate Solut ions The approximate solution based on deviates was first obtained using the IBM Type 650, then the 704. The 650 programs are described in Appendix A to the revised third research report, while the 704 programs are described in Appendix C. Several runs have been made on the 704 with the program described in Appendix C. The results of these runs are presented below. In each case, both the maximization and the minimization problems were run and took the same time. This is to be expected with this method of approximate solution based on deviates. The efficiency is based on either a maximization problem or a minimization problem, as indicated, for which the optimal solution has been computed by the method of reduced matrices, k Size Frequency Time Maximum or Minimum Eff ieieny, 2 3 x 4 f 12 sec maximum 100 2 10 x 10 f. 25 sec minimum 93.5 2 10 x 10 f 25 sec minimum 99.3 4 nj = 3 f 30 sec maximum 89g 3 7 n j 2 f 30 sec maximum 89 3 2 15 x 186 f 19.5 min minimum 97.8 With reference to the last problem in the above table, considering the relatively small amount of time required to obtain the approximate solution and the high efficiency of the solution, the results are especially noteworthy. Summary of Research Findings The method of reduced matrices, at least through the determination of a positive fractional solution, is now available for machine use and is programmed for the IBM Type 650 and the IBM Type 704. This method is recommended for the solution of the group assembly problem, once the group scores are available. The evidence indicates to us that the method is superior to any other available method. An approximate method based on deviates, which usually gives a good approximation to the optimal solution in a relatively short time, is also

The University of Michigan * Engineering Research Institute available and programmed for' the IBM Type 650 and the IBM Type 704. This method is recommended when such an approximate solution is considered useful. 20

The University of Michigan ~ Engineering Research Institute SECTION IVo PROBLEMS EQUIVALENT TO OR RELATED TO THE GROUP ASSEMBLY PROBLEM Introduction There are many problems in linear programming which reduce to the same mathematical problem as the group assembly problem, particularly if minimization as well as maximization is accepted, both for the special case with k = 2 and for the case with general ko Also, there are several other problems which are related to the group assembly problem, in one way or another, although the methods of solution of the group assembly problem are not adequate for their solution, at least not without modification -These matters are discussed in the fourth research reporto6 Eguivalent Mathematical Problems The identification of the group assembly problem as a mathematical problem in which it is desired to obtain a permutation set or grouped permuta-i tion set having an optimal sum makes possible its immediate mathematical identification with many other problems. For example, the Hitchcock transportation (distribution) problem,l7,18 with k = 2, can be interpreted as the determination of a (grouped) permutation set having a minimum sum. The personnel classification problem,l4,26 also with k = 2, essentially calls for the determination of a (grouped) permutation set having a maximum sum. The so-called assignment probleml9,21 is an ungrouped form of this problem which calls for the determination of an (ungrouped) permutation set of zeros. It has been shown, too, that the problem of finding maximum network flows can be reduced. to this mathematical problem. There are many variations or interpretations of these basic problems, particularly when k = 2. Some of these have been described by Flood.16 Many variations of the problems and modified techniques are available in the series "Notes on Linear Programming" and-other papers published as Research Memoranda of Project RAND during recent years. The mathematical equivalence of many of these. problems with k = 2, to all of which the method of reduced matrices is directly applicable, is well known. It is not so generally recognized that the group assembly prpblem22 is identical with a general transportation problem,20,23 since each may be 21

The University of Michigan ~ Engineering Research Institute interpreted as the determination of the permutation set (or grouped permutation set) having optimal sum in the space of k dimensions. The problem is illustrated with a case with k = 3. Let Gijh be the known cost of transporting a unit item at origin i to destination h through intermediate point j o Denote the number of items at i by f i, those to be delivered to h by fh, and the capacity of the intermediate point by fj. It is understood that the capacities of the intermediate points are adequate, i.eo, that nl, n2 n3 Z fi = j f f h = N i=l j =1h=l where n1, n2, and n3 are the respective numbers of origins, intermediate points, and destinations. If we let Xijh be the number of units, zero or positive, which are assigned to route ijh, we wish to minimize the transportation cost T = Z Xijh Gijh The problem above can be generalized immediately to the case with k - 2 types of intermediate facilities. The notation and methods of Research Reports 1, 2, and 3, modified for minimization rather than maximization, are immediately available,. The method of reduced matrices appears to be an available and practical method for ~solving these problems. This basic problem arises in a variety of situations in which a large organization with multiple sets of facilities wishes to accomplish some specific objective at minimum cost. Schell23 has proposed several generalizations of the distribution (transportation) problem. Of these, the generalization described above corresponds to his Case IV. Additional conditions are specified for the other cases he described~ In the language of this report, these additional conditions amount to modifications of the basic problem -They are treated in the later sections of the fourth research report6 after the extended method of reduced matrices, suitable for the solution of these modified problems is presented. The Solution of the General Transportation Problem The solution of the general transportation problem by using the metho of reduced matrices is presented in Section 3 of the fourth research report. 22

The University of Michigan ~ Engineering Research Institute The Determination of Permutation Subsets Having Optimal Sums An interesting mathematical problem is that of finding permutation subsets of an order less than N which have optimal sums. Thus, suppose N is five with k = 2 and it is desired to find the permutation subset of order 4 which has optimal sum. This problem can immediately be rewritten as a grouped problem with k 3=, and the method of reduced matrices is immediately applicable. In general, the permutation Subsets of order m<N having optimal sum can be found, as well as those of order N, for any ko The problem can be written immediately as a problem in k + 1 dimensionsi The solution of this more general problem in permutation sets is thus provided by the method of reduced matrices. The Group Assembly Problem with Incomplete Crew Assignments The results are immediately adaptable to grouped problems and to general ko Suppose the men for forming N crews are available, but it is decided that only m crews are necessary. These m crews are to be determined so that this group assembly sum is to be a maximuM. Ehen a new problem is cone structed in k + 1 dimensions in which the frequencies of all the k dimensions are as before, and a new dimension is added with frequency m, as is a new matrix consisting of 0 values with frequency N m ThMen the groups selected from the matrix in k + 1 dimensions with frequency m constitute the solution of the problem. This variation of the problem, the solution of which is made possible by the method of reduced matrices, is very useful in selecting subsets of crews The Group Assembly Problem with One or More Men Unavailable Suppose that N men are trained for each of the k crew positions, but at the time of the crew assignments one man is unavailableo This means that every crew in which this man is potentially a member cannot be formed. We may consider each unavailable crew to be replaced by a dummy crew with group score 0 and obtain the group assembly having maximum sum with the method of reduced matrices The assignment indicating the group assembly with maximum sum will contain one assignment %to a dumy crew~ The assigned dummy crew indicates the k 1 men which, though each is available for one of k I crew positions, cannot be used because one man is unavailable for the kth crew position. The remaining N = 1 assignments in the solution indicate te N - 1 crews making up the assembly with maxia m um -su 25

The University of Michigan ~ Engineering Research Institute It is possible that more than one man may not be available. We simply replace every crew score which involves a missing man by zero and complete the solution. This general method is available for more complex problems. It is only necessary that every unavailable group score be replaced by zero. In some cases it might even be possible, because of personality or other conditions, that a man might be available for some crews and unavailable for other crews. In this case, the group score can be used where he is available and the zero score can be used where he is not available. In grouped problems, it may sometimes be necessary to add additional dimensions in order to make an explicit representation of the groups having zero scores~ Problems Mathematically Related to the Group Assembly Problem There are certain problems which are mathematically related to the basic mathematical problem. In general, these problems have the specifications (equivalent to the demand for a permutation set having optimal properties) of the group assembly problem, but they also have additional specifications which must be met. The extended method of reduced matrices is commonly useful in solving problems in which these additional specifications, involving subsets of the matrix, take the form of equalities. An Extended Method of Reduced Matrices The method of reduced matrices is extended in Section 8 of the fourth research report6 to certain problems in which there are additional equality relations, in addition to the equations of condition. The Solution of Transportation Problems with Additional Equality Conditions The extended method of reduced matrices is shown in Section 9 of the fourth research report to be immediately applicable to several generalizations of the transportation problem, some of which were proposed by Schell. 24

The University of Michigan ~ Engineering Research institute The Symmetric Reduction of Symmetric Matrices In the case with k = 2 and the Gij matrix symmetric, we may wish to preserve the property of symmetry as we make the transformations. It is not difficult to do this~ For example, in the traveling-salesman problem,13 we may wish to keep the syummetry so that the direct route of the solution and the reverse route both result. Professor Flood16 has utilized. transformations which preserve symmetry in that preliminary treatment of the traveling-salesmar problem which amounts to a solution of the assignment problem0 Symmetry can be maintained if the reduction is made by subtracting the same constants from the colums as from the rows..'ometimes the matrix re mains symmetric under a transformation' which is not itsblf symmetric. But, in the early stages of the reduction process, at least, it seems wise to use transformations which are symmetric. -Thus, we determine a transformation as though the matrix were not symmetric and apply half of it to the rows and half to the columns. The Solution of Certain Types of T-ravelingSalesman Problems The methods of Section 11 of the fourth research report -enable us to solve certain special cases of the t.avelingsalesma n problem 16 The travel ing-salesman problem calls for the route with.minimum total distance which includes all the cities to be canvassed by a salesman. The top row and left.column indicate the cities and G = GT is the matrix of distances between cities0 While this problem has the form of an assignment problem, additional specifications that. all cities must be Pincluded irn a single route in the solution must be satisfised The extended method of reduced matrices make' possible the Solution of certain special cases of the traveling salesman probltm in which.:the symmetric reduced matrices assume a certain form. Summary of Research Findings Several alternate problems are considered, which are mathematically equivalent to the group assembly problem0 It is shown how the determination of a permutation subset having optimal su reduces to a group assembly problem. -Application is made to the problem of obtaining the optimal assignment of crews where the number of crews to be assigned'is less'than the number of crews available~ The theorJy developed here also makes possible the'solution of certain types of traveling$salesman problemso

The University of Michigan - Engineering Research Institute The method of reduced matrices is extended in this report to apply to more general types of problems involving conditions relating subsets of elements~ This extended method of reduced matrices is especially useful in solving more general types of transportation problems~ 26

The University of Michigan ~ Engineering Research Institute SECTION V. THE USE OF MULTIPLE CRITERIA OF CLASSIFICATION Introduction The methods explained in the earlier reports enable us to obtain answers to the question of the optimum assignment of crews when the (unique) values, G(i1i o2 oik), are known. In many situations, however, there may be several alternative and not necessarily consistent criteria which are used in determining the measures of group effectiveness. For example, we might wish to consider, simultaneously, criteria involving technical qualifications and criteria involving social factors and their effects in forming work groups having optimal efficiency. One method of approach, of course, is to give he group sco.re associated with each criterion an approprdate weig;ht, to form the suffis for every group, and to make the. analysis using the resulting composite criterion. The techniques are avaiable fpor th.is analy is, but we afre not always in a -position to provide the appropriate weighting factors, or a sensible interpretation of the composite criterion, and hence the solution based on it.'The question of a composite criterion is discussed in the Research Report Number 57 as are the simultaneous treatment and the joint treatment of the alternative criterion,matrices. There are several variations of the problem~ In one case we have one criterion which is preferued (because of -the nature of the information on which it is based), but we also have alternative criteria and wi.sh to know how satisfactory the solution resulting from the, preferred criterion matrix is as a solution of the alternative criterion matrices - Again we may wish to determi e, on the basis of the results, some criterion which may serve as a ~mostrepresentative criterion. Then there is the question of the determination of a suitable composite criterion, mentioned above, and finally the possibility of the Joint use of the different criterion matrices by interpreting the problem as one in k + 1 dimensionso The Reduction of the Alternative Group Score Matrices The~ fi~nally reduc~ed mat~~x, wshich mesult~' from -the me~t~hod'of reduced mat'rices, serves as an excellent basis for making the comparisons involved in 27

The University of Michigan ~ Engineering Research Institute the consideration of the various criteria, Accordingly, we suggest that the answer to the questions involving multiple criteria can be based on the solution (or on the finally reduced matrix) when each criterion is treated separately. By this device the various criterion matrices are reduced to substantially the same form with the zero terms locating the solutions and the nonzero terms indicating the extent to which the solutions are not in agreement. However, in order to utilize this device fully, it is essential that the alternative criterion scores be comparable estimates, expressed in terms of a common metric, so that the group scores may have comparable meaning. Use of Correlation of Criteria The general notation is similar to that used earlier with the particular criterion indicated by a presuperscript. -The postsuperscript, t, is used with parentheses to indicate the finally reduced matrix. Thus, 1G('t) and 2G(t) represents these matrices for different criteria, It is shown in Section 3:of the fifth research report7 that the use of the Pearsonian coefficient of correlation as a partial measure of the extent of equivalence of the two criterion matrices should be applied to the finally reduced matrices rather than to the original mnatriceso Measures of- Adequacy with a Preferred Criterion In many applications there is definitely a preferred criterion. In such a case, we sometimes wish to know the extent to which the solution resulting from the preferred criterion matrix is fully adequate for the matrices corresponding to the alternative criteria, or vice versa.. These solutions may be compared by examining the error which results from the application of the preferred criterion matrix to the other ones -This error is available from the finally reduced matrices. Alternatively, the efficiency of the solution resulting from the preferred criterion matrix, as applied to the alternate criterion matrices, may be used as a measure of adequacy of the solution resulting from the preferred criterion. The Determination of a Most-Representative Criterion The situation sometimes arises in which there is no criterion preferred on a priori grounds. If the criterion scores are comparable, we may use the finally reduced matrix to produce a solution having minimum sum of errors 28

The University of Michigan ~ Engineering Research Institute for the other criteria. Alternatively, we may select as the most-representative solution the one having the largest average efficiency. The Determination of a Composite Criterion In some problems, it may be that no one criterion is preferred on a priori grounds, and yet some composite criterion, which utilizes the information in all the criterion matrices, is preferred to the selection of a representative criterion. Such a composite criterion may be obtained by applying appropriate weights to the various criterion matrices and by forming the weighted sum for each element, If the weights are known, as is suggested above, then thehe problem with the matrix of weighted criterion values can be treated by the usual methods used in treating any single criterion problemo Methods of determining suitable weights are presented in Section 6 of the fifth research report. Joint Use of Multiple Criteria A final procedure for integrating the results, using different criteria, features an enlarged problem with the different criterion matrices comprising the different dimensional subsets of an additional dimension. The frequency of the criterion matrices in the new dimension must total N. If there are N criteria, each criterion matrix can be given a frequency of unityo If the number of criteria is less than N, some frequencies must be greater than unity. The idea is to select the groups so as to maximize the assembly sum when the group score for any one of the criteria may- be used, subject to a specified number of selections from any one criterion matrix. Once the formal solution of the problem in k + 1 dimensions is available, the optimal group assembly is obtained by disregarding the elements in the k + 1 st dimension. This method of integration of the results should be used only when all the group scores for all the different criteria are expressed as comparable measures of group effectiveness. Summary of Research Findings Methods of solution for several alternative probulems using multiple criteria are now available. Probably the most important problem is that in 29

The University of Michigan * Engineering Research Institute which there is a preferred criterion and it is desired to know how well the solution resulting from this criterion matrix can serve as a suitable solution to the alternative criterion matrices. The finally reduced matrix and the concept of efficiency of an approximate solution are used in studying this question. The finally reduced matrix and the concept of efficiency of an approximate solution are also useful in determining a most-representative criterion and in determining acceptable weights for the criterion matrices. A method featuring the joint use of multiple criteria requires the solution of a problem in k + 1 dimensions. The finally reduced matrix (for each criterion) resulting from the method of reduced matrices, plays a dominant role in the treatment of most of these problems. This is also true in the use of the correlation coefficient in studying the extent of linear relationship between alternative criteria. The conditions should be applied to the finally reduced matrix rather than to the original matrix-. 30

The University of Michigan ~ Engineering Research Institute SECTION VIo T.E USE OF APPROPRIATE APPROXIMATE SOLUTIONS WHEN TEE GROUP ASSEMBLY MATRIX CONSISTS OF FALLIBLE GROUP SCORES Introducti on The mathematical model for the group assembly problem assumes that the group scores are known exactly, so that there are no inherent errors in the group assembly matrix. In many practical problems this assumption is not very realistic, for it is evident that the group scores are not without erroro In such a case, a further study of the solution bf the problem is indicated in order to determine the effect, if any, of the errors on the solution. Since the:exact solution for a G matrix consisting of group scores subject to error is only an approximate solution for the GI matrix (in most cases theoretical) consisting of the "actual" group scores, we wish to determine a method for obtaining an appropriate solution to the problems Several variations of this general problem arise. These variations include cases in which:| 1.o The errors in the group scores are known, and hence the G' Vmatrix is known. This type of' situation arises when mistakes have been discovered in the calculati;on of one -or more group scores after the exact soluation has been obtained, so that the solution must be modified to account for the mistakes. 2. -The errors of the group scores are not known: but bounds for the absolute values of the errors are known. a. The bounds may be very small, as is the case when the elements of a matrix are subjected to perturbation in order that a unique permutation set of zeros may be obtained. bto The bounds may be of the:order of the units in which the: group scores are expressed. c. The bounds may be relatively large. 35 No bound for the errors is known. Since the exact solution for a matrix of group scores subject to error is in fact only an approximate solution for the matrix of "actual" group scores and since an approximate solution for a given matrix can frequently be obtained more readily than an exact solution, we may consider: 31

The University of Michigan ~ Engineering Research Institute 1. Approximate and exact solutions for the given matrix when the errors are known. 2. A representative solution for the given matrix when the errors have known bounds. 3. Approximate solutions which are almost optimal for the given matrix when the errors have known bounds. 4. Exact solutions for the various possible matrices when the errors of the given matrix have known bounds. 5. Use of approximate solutions based on the matrix of deviates.o One further remark should be made. The error of an approximate solution should be measured by the error of the assembly sum associated with it, since the problem is to maximize (minimize) the assembly sum. The solution is simply the assignment which yields a maximum (minimum) sum. Two approximate solutions may differ appreciably but yet have the same assembly sum and hence be equally satisfactory as approximate solutions. Modified Matrices The simplest of the situations discussed in Research Report Number 68 is that in which the errors of the group scores are known. These errors can then be applied to the finally reduced matrix, or they may be applied directly to the original matrix and a new solution obtained. The availability of efficient machine solutions makes the latter suggestion very practical. Fallible Group Scores with Small Errors If the bounds for the errors are small enough, all possible solutions may be the same, and the representative solution is the exact solution with the problem with all error terms zero. The size of the error bound for the group scores for which this is true is provided in Section 4 of the sixth research report. The above result is the basis of the practice, useful both with machine and hand methods, of introducing perturbations of the elements of a matrix in order to avoid the introduction of superfluous zeros in the reduction process. While the above condition on the size of the error guarantees no change in the solution, it is commonly true, as is illustrated in Section 4, 32

The University of Michigan ~ Engineering Research Institute that much larger values of the error have little or slight effect on the solutiono. It is shown that the finally reduced matrix, which results from the method of reduced matrices, is frequently very helpful in determining the size of the error which has small effect -on the solution. Possible Optimal Solutions The method of reduced matrices is adjusted in Section 5 to include transformations of the errors of the group scores, as well as transformations of the scoreso In this way possible solutions may be determined from transformed group scores which are zero to within the errors of allotted size. Modifications of the Method of Reduced Matrices in Order to Obtain Some Possible Optimal Solution Modifications of the method of reduced matrices, which utilize all terms which might be zero if errors were considered, are described and illustrated in Section 6. In'a sense, thee resulting possible solutions may be considered to be approximate solutions to the problem in which the errors are discarded. Use of Approximate Solutions Based on Deviates These approximate solutions, described a'bove, are either related to a modified form of the method of reduced mtrices or'.related to a modification of the finally reduced matrix resulting from the application of the method of reduced matrices. An alternative approximate solution, based on the results of the deviate trans:ormation described in Section 2.3 of the report, "Generalized Mathematical Procedures for the Optimal Assembly of Potentially Efl fective Crews,"1 seems especially appropriate to the problem in which the ele ments of the group assembly matrix are subject to errors. The deviate transformation leads to a matrix of deviates in which the weighted mean in every subdimension is zero. The assignments are then made to the largest available values of the deviates (for maximization problems), in order, until the assignment is complete. The assignments must be made subject'to the designated frequenci-es of all the subdimensions which cover the deviate. A deviate is not available if it is covered by a subdimension which has all i-ts frequencies assigned. With the use of electronic computers, as described in Research Report Number 3,5 the computation of the deviates and the assignment of the 53

The University of Michigan ~ Engineering Research Institute frequencies, subject to the equations of condition, can be performed in a very short time. For example, in the k = 2 problem with n, = 186, n2 = 15, and N = 3077, the 2790 deviates were calculated and the assignments were made by the IBM Type 704 in less than 20 minutes. Four additional minutes were needed for.input and five minutes for output. A variation of this approximation method uses one application ~of the equations of condition to the nsj - (k - 1) largest deviate terms in order to J obtain a better approximate solution. This general approximation method, either with or without the application of the equations of condition to the largest deviate terms, is applicable to situations in which the bounds for the errors are unknown, as well as to situations in which the bounds for the errors are knowno The method is especially suited to problems in which the group scores have large relative error, for then the additional precision introduced by the exact but more time consuming method of reduced matrices, is hardly warranted. Effects of Grouping and the Use of IBM Type 704 The question arises as to the feasibility of the use of grouping in reducing the magnitude of the problem. The logical basis of grouping is discussed in Section 5 of the report, "Development of Generalized Mathematical Procedures for the Optimum Assembly of Combat Crews,"1 and in more detail in Chapter V of the extended report of the previous project.2 It is assumed that grouping has been accomplished in all cases in which such groupings can be made without the introduction of appreciable error. The problem then is the extent to which we should combine subdimensions when such combinations cannot-be made without introducing appreciable error. For example, should we combine New York and Philadelphia as an origi and San Francisco and Los Angeles as a destination in a transportation problem To do so would presumably introduce errors of appreciable size in the elements of the cij matrix. In order to reduce the problem appreciably in magnitude, it is not only necessary to combine certain origins, certain destinations, etc., but groups of origins and groups of destinations. Then the resulting solution, even though it is an exact solution for the problem with these forced groupings, is at best an approximate solution to the ungrouped or naturally grouped problem. Like the transportation problem, the group assembly problem, after all possible groupings resulting from identical or nearly identical scores hav been made, is not one which commonly lends itself to additional grouping without introduction of appreciable error.

The University of Michigan ~ Engineering Research Institute It is at this point that the machine solution of the problem, made possible by the programs for the IBM Type 704, indicates the path to follow.'Since methods, both exact and approximate, are available for solving problems of considerable magnitude in a reasonably short time, it appears preferable, if a machine is available, to rely on these methods rather than to introduce errors of appreciable size through forced grouping. With the techniques now available we can disregard the less satisfactory possible optimal solution and even the almost representative solution in favor of the more satisfactory repr sentative solution. If the errors are known to be large, it seems much more practical to obtain an approximate answer quickly by using the approximate method based on deviates rather than to force the grouping and use an exact method on the grouped problem. This problem may also be faced by one who does not have access to an IBM Type 704 and yet must solve a problem of such magnitude that he is forced to make considerable concessions in accuracy in order to obtain an approximate answer. -Again the use of an approximation method, such as that based on de viates (even on unweighted deviates if an immediate answer is required), is recommended rather than the use of forced groupings. Summary of Research Results Modifications. in technique are in order when the group assembly man trix is composed of group scores which are Rubject to error. If the errors are,small, there is little effect onw the solution and on the group assembly sum, but large errors may change the solution appreciably, It is shown in this sixth research report how the method of reduced. matrices may be modified to obtain a possible optimal solution or a solution which is almost optimal. When the errors of the group scores are large, there seems little -point in straining to get an exact solution since a good approximate solution seems quite satisfactory. Such an approximate solution can be obtained with the use of deviates with speed and relative ease. These results are pertinent to the question of grouping. Naturally, one should group his subdimensions, as much as is possible, if this can be done without introducing large grouping errors. If one is forced, because of inadequate facilities or resources, to limit his solution to one which may have large errors, it seems preferables from a practical standpoint, to use the approximate method on the larger problem with the elements subject to small errors rather than to use an exact method on the smaller problem with elements subject to large errors. The use of the programs and codes for the IBM Type 704, provided as a result of the work on this contract, makes possible sensLbae $1ree commendations 35

The University of Michigan ~ Engineering Research Institute for the treatment of this problem by grouping when such a machine is available. Use the method of reduced matrices in obtaining the representative solution if the errors are small. If the errors are large, or if an approximate solution is required in less time than that required to obtain the representative solution, use the approximate solution based on deviates. 36

The University of Michigan ~ Engineering Research Institute PART B. ADMINISTRATIVE AND FISCAL INFORMATION

The University of Michigan ~ Engineering Research Institute PERSONNEL Portion of Name Title Time Devoted to Contract Work Dwyer, Paul S. Professor of Mathematics Variable1 Consultant in Statistical Research Laboratory Galler, Bernard A. Instructor in- Mathematics Variable2 Mathematics Consultant 3 Carr, John Assistant Professor of Mathematics Mathematics Consultant Graves, Glenn Assistant in Research Variable4 Graves, Patricia Assistant in Research Half Time5 Locker, John Assistant in Research 14 hours per week6 1Dr, Dwyer worked up to 40 hours per month on the contract during the term of the contract. During the summer of 1956 (June 15 to September 15), he worked full time on the contract. He served as supervisor of the contract work, directed the research, and prepared the reports. 2Dr. Galler worked up to 40 hours per month on the contract beginning November 2, 1955. During the summer of 1956 (June 15 to September 15), he worked full time on the contract. His work was devoted to the translation of the methods to computation with electronic digital machines and the preparation of the revised Research Report Number 3. 3Dr. Carr has served as a consultant for the numerical work on the contract. No charges against the contract funds have been made for his advice. 4Mr. Graves worked a total of 31 hours during the first month of the contract in writing programs for MIDAC 5Mrs. Graves has been working half time throughout the term of the contract. She has been of great service in assisting with the research and in the preparation and revision of all the reports of the contract o 6Mr. Locker has assisted n the preparation and revision of the final contract reports. He began work on the contract on October 8, 1956.

The University of Michigan ~ Engineering Research Institute FUND UT ILIZAT I ON The utilization of the funds of the contract is shown below. This information is obtained from reports available to the supervisor at the end of the contract (December 15, 1956). At this time he does not have access to the official record of expenses for the months of November and December of 1956. For these months he has used estimates based on his present knowledge of the prospective expenses. The estimates of the expenses for these two months are liberal, so that there is every indication that there will be a balance of a few hundred dollars in the contract funds when all charges against it have been made. General Accounting Funds Available Funds indicated by initial contract $25,729.00 Additional funds in extended contract 7,83 0 Total contract funds $33, 559.00 Utilization Salaries I $18, 795~ 50 Clerical and staff services 2 206.16 Overhead 7 92. 92 Supplies and reports2 1,312,29 Travel3 206.57 Use of electronic digital computers4 2,718.09 Postage, telephone, and miscellaneous 98.57 Estimated balance 2960 90 Total $33, 559.00 -these salaries cover the salary paymaents to the research members of the contract personnel indicated above. A more detailed analysis is shown in the table for research salaries below. There are some additional nonresearch salaries (wages) included in the item, "Supplies and reports." This covers the cost of reports prepared by the Reports Office of the Engineering Research Institute. 2This item covers supplies used in the research, as well as all materials and services used in the reproduction of the reports. 3No major trips were taken during the term of the contract. The item for travel results from the transportation of Dr. Galler to and from General Motors Technical Center daily during the summer and weekly since the opening of school in September. 4The charges here are for the use of MIDAC and the IBM Type 650. As a result of an arrangement with General Motors, the project was fortunate in not being charged for time used on the General Motors IBM Type 704l 39

The University of Michigan ~ Engineering Research Institute Research Salaries The Air Force Resident Auditor has a complete breakdown of the personel employed in Air Force Projects at The University of Michigan and of their salaries. At the time of the preparation of this report, this itemized listing is not available to the project supervisor. The following analysis of the total research salaries paid, approximately $18,800, is obtained from unofficial records of time spent and is rounded to the nearest $100. Figures for this last portion of the contract are based on estimates. Dr, P. S. Dwyer $10,500 Dr. B. A. Galler 4.500 Mrs. Graves 3,600 Glenn Graves 100 John Locker 100 Total $18, 800 40

The University of Michigan ~ Engineering Research Institute REFERENCES A. Reports on the work of the previous contract 1. "Generalized mathematical procedures for the optimal assembly of potentially effective crews."' 2. "'Maximum group assembly sumw." Bo Reports on the work of this contract 5. Research Report No. 11. "The olution of the general group assembly problem with a method of reduced matrices.'" I, Research Report No, 2 "Econonmical means of accomplishing data transformations and practical simplifications of the problem encountered in reducing grouped matrices'" Research Report No.o 3,'"Adaptation of the method of reduced matrices to electronic digital computers~." 6. Research Report No. 4I "The solaution of problems mathematically equivalent to or related to the group assembly probleml." 70'Research Report No. 5, "The use of multiple criteria of classification. "8. Research Report No. 6, "'The use of appropriate approximate solutions when the group assembly matrix consists of fallible group scoresO" 9. Dwyer, P. So "'The problem of optimum group assembly." To be published in Proceedings National Research Council Symposium on Personnel, Training and Human Engineering, held at Washington, D. C., November 14-16, 1955. lO.. Dwyer, P. S., and Galler, B. A. "'The method of reduced matrices for a genertal transportation problem." Presented to meeting of Association for Computing Machinery, Los Angeles, August, 1956o II Galler, B, A., and Dwyer P. S. "-Translating the method of reduced matrices to machine computation." To be published in Naval Review Logistics Quarterly..-,.. a... e.......... S. a..

The University of Michigan ~ Engineering Research Institute 12. Dwyer, P SO. "A Theorem on the multi-index transportation problem.-" Presented by title to the meeting of the American Mathematical Society held at Cambridge, Massachusetts, October 27, 1956. Co Other references 13o Dantzig, G., Fulkerson, R., and Johnson, S. "Solution of a large-scale travelling-salesman problem," Jour. O pnso Res. Soc Amo., 2, 293-410 (1954). 14. Dwyer, P. So. "Solution of the personnel-classification problem with the method of optimal regions Psychometika, 18 1126 (1954). 15. Dwyer, PO SO "The detailed method of optimal regions."' Accepted for publication in Psychometrika. 16. Flood, M. M. "The travelling-salesman problem."' Jouro Opns. Res. Soc. Am., 4, 60-75 (1956). 17. Flood, M. M. irOn the Hitchcock distribution problem,' Paco Jouro Math., 3, 369-386 (1953). 18. Hitchcock, Fo L. "The distribution of a product from several sources to numerous localities," 1Jour. Math. PhysO 20, 224-230 (1941). 19. Kuhn, H. Wo. -The Hungarian method for the assignment problem"8 Naval Research Logistics Quarterly, 1955,1 83-98o 20. Motzkin, T. S. "The multi-index transportation problem," Bull..o Am Math. Soc., 58, 494 (1952), 21. Munkres, J. "'Algorithms for the assigrment and transportation problems," Accepted for publication in Jour. Soc.o Indo and Applied Math., March, 1957. 22. Roby, T. B. "Problemns of rational group assembly exemplified in the medium bomber crew," Research Bulletin 53-18, Human Resources Research Center, Lackland Air Force Base, July, 1953. 23. Schell, E o D. "'Distribution of a product of several properties." Presented to Linear Programming Symposium, National Bureau of Standards, Washington, D. C. January 29, 1955. 24. Stoll, RB R o Linear Algebra and Matrix Theoryo Hew York: McGraw-Hill Book Co, Inc., 1952, pp. 1-22. 42

The University of Michigan ~ Engineering Research Institute 25. Votaw, D. F., Jr. "Methods of solving some personnel-classification problems," PSychometrika 17_, 255-266 (1952). 26. Votaw_, D. F., Jr., and Dailey, J.o T.'"Assignment of personnmel to jobs," Research Bulletin 52.24, Air Training Command, Human Resources Research Center, Lackland Air Force Base, August, 1952. 43

UNIVERSITY OF MICHIGAN 3 9015 02656 7175