THE UNIVERSITY OF MICHIGAN INDUSTRY PROGRAM OF THE COLLEGE OF ENGINEERING MITAB MICHIGAN TRANSPORTATION AND ASSIGNMENT BLACKBOARD Bruce R. Weinert James R. Munkres Gerald T. Cargo Operations Research Department June, 1958 IP-299

ACKNOWLEDGMENT The authors wish to acknowledge the invaluable assistance and contributions of the following: Dr. Merrill M. Flood, Mr. Harry H. Goode, Mr. Dean H. Wilson, Mr. Harvey L. Garner, Dr. Robert E. Machol, Dr. Harold M. Horwitz, Mr. J. E. Hoagbin, Dr. Jesse B. Wright, Mr. Richard R. Legault, Mr. Elmer H. Smith, Mr. Harold W. Sherman, Mr. August Antones, and Miss Shelia M. Coon. The authors are also indebted to Dr. Richard G. Folsom for making available research funds and some of the publication funds (the remainder of the latter were assumed by The College of Engineering Industry Program), and to the members of Engineering Services Department for constructing the machine. ii

FOREWORD Under a grant from the Engineering Research Institute, a special-purpose semi-automatic computer (hereafter called "mechanical blackboard") has been built to aid in the solution of certain types of linear programming problems. These are the problems which are usually called assignment and transportation problems; accordingly, we have named our mechanical blackboard MITAB (Michigan Transportation Assignment Blackboard). The purpose of this treatise is to provide (1) a general discussion of the assignment and transportation problems, (2) an operation manual for the MITAB, and (3) a set of instructions for the solution of assignment and transportation problems with the aid of the MITAB. One use for the MITAB is as a demonstration device to accompany lectures on these problems, to illustrate them, and to demonstrate some of the methods which may be used in their solution. The general discussion in Section I is meant to explain the background of the problem, both mathematical and practical, and to supply. information which a person planning to demonstrate the MITAB can use in preparing such a lecture demonstration. In Section II, a detailed description of the MITAB is given. In Section III, the algorithms for the assignment and transportation problems are presented. Section IV presents methods of solution for the various problems. The Appendix includes a comprehensive bibliography of works on these types of problems and a suggestion for programming the algorithm for the transportation problem for a high-speed digital computer. iii

TABLE OF CONTENTS Page ACKNOWLEDGEMENT........................... ii FOREWORD............................................................ iii LIST OF FIGURES...................................................... vii SECTION I - INTRODUCTION TO THE ASSIGNMENT AND TRANSPORTATION PROBLEMS................................... 3 Nature of the Assignment Problem............................... 5 Various Methods Available....................................... 10 I. Linear Programming.................................. 10 II. Other Methods........................................ 11 III. Our Solution............................................. 12 SECTION II - DESCRIPTION OF THE MTAB............................... 17 (For detailed contents see following page) SECTION III - ALGORITHMS FOR THE ASSIGNMENT AND TRANSPORTATION PROBLEMS............................................. 63 The Assignment Problem......................................... 65 The Transportation Problem.................................... 69 SECTION IV - SOLUTION OF ASSIGNMENT AND TRANSPORTATION PROBLEMS ON THE MITAB....................................... 73 The Mechanical Blackboard....................................... 75 Instructions for Setting Up a Problem on the Mechanical Blackboard............................................ 78 Methods for Solving the Problems................................ 80 BIBLIOGRAPHY......................................................... 95 APPENDIX - SUGGESTIONS FOR PROGRAMMING AN ALGORITHM FOR THE TRANSPORTATION PROBLEM FOR A HIGH-SPEED DIGITAL COMPUTER............................................ 101 iv

DETAILED CONTENTS OF SECTION II Page SECTION II - DESCRIPTION OF THE MITAB 1.0 THE BOARD.................................................. 17 19 1.1 The Cell..................... 1.1.1 The Light Cell.......... 1.1.2 The Teleregister Cell... 1.1.2.1 Adding......... 1.1.2.2 Subtracting.... 1.1.2.3 Homing......... 1.1.2.4 Schematic...... 1.2 Matrix......................... 1.2.1 Set-Up.................. 1.2.1.1 Procedure...... 1.2.1.2 Set-Up Switch.. 1.2.1.3 Push Buttons... 1.2.2 Clearing........................~ 19........a 21 a........ 21 0 0 0 0 0 0 ~~ 0 0 6 0 ~~ ~~ ~~~~~~~~~~~~~~~ * 0. 00 0 *. 0.0.. 0 0 00 0. 0 0.a 0 0 0 0 0.. 9. 0 00.. a 0.0...... 0 0. a..... a.0. 0. *... 23 23 23 23 24 24 25 25 25 25 29 29 29 29 29 29 33 1.2.2.1 1.2.2.2 1.2.2.3 Clear for Set-U Electrical Grou: Ten Pulses to C: p........ nr * a 0 6 1.2.2.4 Easy Clearing.. 1.2.3 Light-Cell Bus.......... 1.2.4 Bars.................... -,A. ~ ~...~~~~~~~~. ~~... ~. ~ lear................... ~ e eee. ee t*~. e e.ee~ eeee... eee............. ~ e e a e eee. a e e e e. * *.. 2.0 CONTROL................................................... 2.1 Control Panel on Face of Computer........ 2.1.1 Problem-Changeover Switch......... 2.1.2 Clear Switch...................... 2.1.3 Set-Up Switch..................... 2.1.4 Add Switch........................ 2.1.5 Telephone Dial.................... 2.1.6 Ten-Pulser Supervisory Lights..... 2.1.7 Column-Add and -Subtract Switch............... I 33............. 33............. 33............ 3 33............ 41............ 4 41............ 441.............. 41 2.1.8 Power Control.................................. 3.0 CONTROL SUB-CHASSIS........................................ 3.1 Description............................... 3.1.1 Subtract Circuit (Ten-Pulser)...... 3.1.1.1 Step-Switch Count......... 3.1.1.2 Start Relay............... 3.1.1.3 Stop Relay................ 43 43 43 43 43 v

DETAILED CONTENTS OF SECTION II (CONT'D) Page 3.1.1.4 Start-Relay Lock Circuit.............. 3.1.1.5 Step-Switch Cycle..................... 3.1.1.6 Ten-Pulse Output Flow................. 3.1.1.7 Step-Switch Reset..................... 3.1.2 Add Circuit................................... 3.1.2.1 Add Circuit and Lockup Functions...... 3.2 Electronic Circuits................................... 3.2.1 Step-Switch Circuits........................... 3.2.1.1 Thyratron Time Delay.................. 3.2.1.2 Integrator........................... 3.2.1.3 Plate Circuit....................... 3.2.1.4 Motor Magnet......................... 3.2.1.5 Step-Switch Contact Levels............ 3.2.1.6 Complete Circuit...................... 3.2.1.7 Adjustments........................... 3.2.2 Pulse-Limiting Circuit......................... 3.2.2.1 Pulse-Cycled Charging................. 3.2.2.2 Resetting State of Charge............. 3.2.2.3 Plate Circuit......................... 3.2.2.4 Complete Circuit and Adjustment....... 3.2.2.5 Wave Shapes........................... 3.3 Power Supplies........................................ 3.3.1 Dual-Voltage D.C. Supply....................... 3.3.2 12-Volt A.C. Supply............................ 3.3.3 Power Plugs.................................... 3.3.4 Tubes and Fuses................................ 46 46 46 46 48 48 48 48 48 50 50 50 50 50 54 54 54 54 54 56 56 56 56 56 62 62 vi

LIST OF FIGURES Figure Page 1 Two of the Authors Showing How Two Persons Set Up MITAB.... 1 2 The General Cell......................................... 19 2A General Cells in the Matrix........................ 20 3 Light Cell (Lij) Schematic.................................. 21 4 MITAB Teleregister......................................... 22 4A Teleregister Cell (Tij) Schematic.......................... 24 5 Teleregister Setup Circuit................................. 26 6 Basic Calculating Matrix................................... 27 7 Clear Circuit and Ground Return for Teleregisters......... 28 8 Power Feed System for Cell Lights.......................... 29 9 Front Layout of the Computer.............................. 34 9A Front View of Computer.................................... 35 9B Rear View Showing Wiring and Power Supply.................. 36 9C Left End View Showing Row Relays and Ten Pulser............ 37 10 Control Panel Section...................................... 38 10A View of Upper Control Panel Section....................... 39 10B View of Lower Control Panel Section........................ 40 11 Ten Pulser Sub Chassis Block Diagram....................... 44 12 Ten Pulser Sub Chassis Block Diagram....................... 45 13 Ten Pulser Time Sequence Diagram........................... 47 14A Cathode Bias Circuit....................................... 49 14B Time Delay Circuit (Integrator)........................... 49 vii

LIST OF FIGURES (CONT D) Figure Page 14C Thyratron Plate Circuit.................................... 51 14D Stepping Switch - Motor and Level Connections.............. 52 14E Thyratron Time Delay and Stepping Switch Circuit........... 53 15A Pulse Cycled Charging Circuit............................... 55 15B Plate Circuit of Pulse Limiting Thyratron.................. 55 15C Pulse Limiter Circuit...................................... 57 15D Front and Back View of Ten Pulser.......................... 58 16 Wave Shapes for Pulse Limiter Circuit...................... 59 17 Add Circuit Time Sequence Diagram.......................... 60 18 Two Voltage D.C. Power Supply.............................. 61 viii

Fing. 1.I. TIo of -the Authors Showing How Two Perrsons set Up METAB

SECTION I INTRODUCTION TO THE ASSIGNMENT AND TRANSPORTATION PROBLEMS

SECTION I INTRODUCTION TO THE ASSIGNMENT AND TRANSPORTATION PROBLEMS To become familiar with the "assignment problem," an attempt was made to survey the existing literature on the problem. Some articles were studied in detail; others were only scanned. An extensive (and, it is hoped, exhaustive) bibliography has been compiled. A significant improvement was made on one of the existing methods, thus setting the stage for the "engineering implementation" of an efficient technique for obtaining solutions to assignment problems. Just what is meant here by the term "engineering implementation" will be discussed later. Without becoming involved with the technicalities, we shall mention some of the methods available for solving the assignment problem. Mathematical details will occasionally be included in the exposition for greater clarity. Nature of the Assignment Problem The assignment problem can be viewed in the following setting: Suppose n men are available to work on n jobs and that each man is assigned a rating on each of the n jobs. For practical reasons let the ratings be given in terms of nonnegative integers. The assignment problem consists of finding those assignments of men to jobs which maximize the rating sum. For a particular assignment the rating sum is the sum of the men's ratings for the jobs to which they are assigned. A natural way of presenting the data is in the form of a rating matrix. For example: Job 1 Job 2 Job 3 Man 1 1 7 3 Man 2 5 4 5 Man 3 2 6 6 Examining the matrix, one sees that the rating of Man 1 on Job 2 is 7 (the element in the 1st row and the 2nd column). -5

-6 In general, the rating matrix will be n by n, and the rating of the ith man on the jth job will be given by the element in the ith row and the jth column. r* 11 r* 21 r* r* 12 13 r* r* 22 23... r*... r* lj 2n r*... r* 2j 2n rating of ith man on jth job. R* = r* r* r*... r*... r* il i2 i3 ij in r* r* r*... r*... r* nl n2 n3 nj nn Rating Matrix for General Problem (The reason for using "starred" rij's will become apparent below.) The use of the word "solution" in connection with the assignment problem warrants a word of caution. In one sense a solution always exists. All one has to do is consider the n! possible assignments and pick out those assignments whose rating sums are maximal. In the case of the 3by-3 matrix given above, viz., 1 5 2 7 3 4 5 66 the 3' = 6 possible assignments are 1 2 A1 = (1 2 1 2 A2= (1 3 A3 = (1 "3 - 2 1 3 3 3 2). 3), 3

-7 A4= ( 3 1 A6 = ( 2 3) (13 2 31 where (1 2 3 ) is the assignment where Man 1 is assigned to Job Jl, Jl J2 J3 Man 2 is assigned to Job j2, and Man 3 is assigned to Job j3. Referring to the rating matrix, it is easily seen that the rating sums for the various assignments are: ASSIGNMENT RATING SUM A1 1 + 4 + 6 = 11 A2 1+5+6=12 A3 7 + 5 + 6 = 18 A4 7 + 5 + 2 = 14 A5 3 + 5 + 6 = 14 A6 3+4+2=9 There is only one optimal assignment in this case, namely A3. It is quite possible that more than one assignment will be optimal for a given rating matrix. For example, the matrix 2 2 2 2 2 2 2 2 2 clearly has 6 optimal assignments associated with it. The significant conclusion to be drawn from the above remarks is that, given enough time and patience, the solution to an assignment problem can always be extracted by brute force. However, when one considers that a 10-by-10 rating matrix would involve 10! = 3,628,800 distinct assignments and a problem with a 20-by-20 rating matrix would involve 201 = 2,432,902,008,176,640,000 assignments, one sees the desirability of an algorithm that will yield a solution with the expenditure of only a reasonable amount of money and time. So what is really needed

-8 is a good solution rather than just a solution. One additional remark is in order here. In practice it usually suffices to find only one assignment that is optimal, rather than determining all the optimal assignments (or even determining if there actually is more than one optimal assignment). If one forms a constant matrix whose common element is equal to the maximum element contained in a rating matrix and subtracts the rating matrix (element by element) from the constant matrix, then searching for an assignment with a minimal rating sum for this new matrix is equivalent to searching for an assignment with a maximal rating sum for the original matrix. For theoretical reasons the assignment problem is usually thought of in terms of searching for an assignment with a minimal rating sum. One can think of the elements of the rating matrix as being measures of inefficiency in this case. For example, consider the matrix 1 R* = 5 2 7 3 4 5 66 The maximal element of this matrix 7 R= 7 7 77 77 77 matrix is 7. So we want to work with the 173 6 0 4 54 5 = 2 32 266 511 The rating sums for the six possible assignments now become: ASSIGNMENT A= (1 2 3) = ( 1 2 3 A2 = (1 2 1 3 A -(1 2 3) A4 =(1 2 3) 5 = 23 1 2 A6= (1 2 3 312 RATING SUM 6 + 3 + 1 = 10 6+2+1=9 0+2 + 1=3 0+2 + 5 = 7 4+2 + 1=7 4 + 3 + 5 = 12

-9 The minimum rating sum is associated with the assignment A3. Recall that the maximum rating sum for the original matrix was also associated with the assignment A3. A little algebraic manipulation shows that this situation holds in general. It might be worthwhile to look at a proof of this statement. Suppose A the rating matrix (1 2 3 jl j2 J3... n ) is' in an optimal assignment for R* = r* r* r* 11 12''' ln r* r*... r* 21 22 2n r* r*... r* nl n2 nn in the sense that S = zn r* is maximal. i i 2,., n) and i =l1, 2,... n; j = 1, 2,.., n)and Then, if m = max r*j (all iij m m m m m m... m.. m... m m m m one can form the difference m-r* m-r* 11 12 M - R* =... m-r* ln ~.. m-r* nn r r 11 12... r In = R. m-r* m-r* nl n2 r r nl n2 nn This new matrix, R = M - R*, has that the corresponding rating is A as an optimal assignment in the sense minimal. The reason for this is that Z r= A( r) = ii(m - i) = Zi m - i r ji = nm- i r A ij )i and Z, r* is maximal. i iji

Various Methods Available I. Linear Programming The assignment problem is a special linear programming problem. It can be formulated algebraically as follows: Given an N-by-N rating matrix, r* r* r*... r* 11 12 13 lN r* r* r* r* r21 r22 23 * 2N R* =... r~t~ ~. r~ r* r* r* r*...r Nl N2 N3 NN where the r*'s are nonnegative integers, find a set of values for the ij real variables xij, subject to the following conditions: i=1 xij = 1, Zj=1 xij = 1, xij > Zi,j xij rtj = maximum. At first thought, one would naturally think that the additional requirement x2 = Xij (i.e., xi = 0 or 1) should be added. However, it turns out that among the solutions of the problem stated above at lease one must satisfy the additional condition x2 = xi. A linear programming model can be couched in the following algebraic language: Find the values of X1, X2, Xn which maximize the linear form X1 c1 + X2 c2 +.. + Xn cn, subject to the conditions that X. > 0, j = 1, 2,... n, and lall + + knaln = b1 J) Xilaml + namn = bm where aij, bi, cj are constants (i = 1, 2, 3,... m; j = 1, 2,..., n).

-11 It is now a simple matter to identify the assignment problem as a special case of a linear programming policy. The following table shows the relation between the algebraic symbols in the two formulations: GENERAL ASSIGNMENT PROBLEM i j j n xi Ci m b. aij xij r* ij 2N 1 1 or 0 It follows that the method of solving linear programming problems can be applied to the assignment problem. In particular, the simplex method is available. High-speed computing machinery has been used in conjunction with a modification of the simplex method to solve assignment problems. II. Other Methods P. S. Dwyer has solved the assignment problem by a method of reduced matrices. Combinatorial algebra methods are concerned with various techniques of deciding upon the transformations to be made in order to obtain n independent O's. These are usually based in one form or another on Konig's theorem. This is the basis for H. W. Kuhn's solution. Other methods that have been proposed for the solution of the assignment problem (and a generalization thereof called the transportation problem) include the method of interchange, the method of optimal regions, the method of bounding sets, and the methods of transformation such as Easterfield's method and the detailed method of optimal regions. Any of these methods may be studied in more detail by consulting the references in the bibliography.

-12 III. Our Solution In the process of examining available methods some time was spent on trying to improve the various methods. J. R. Munkres devised a method for solving the assignment problem that is essentially an improved version of a method that has been described in the literature. It is Munkres' method that was incorporated in the man-machine device that is now known as MITAB. Munkres has generalized his method so that it can be used for solving a more general linear programming problem called the transportation problem. The transportation problem may be stated mathematically as follows: Given an n-by-m matrix D = (dij) and positive integers ri (i=l,...n) and cj (j=l,...m) such that =l ri = EjM cj = N, choose values for the integers xij which minimize the sum Z j xijdij, subject to the conditions x. >0O, Zm x x -c. (1) xij =1 = 1 ij = j The assignment problem is a special case of the transportation problem; it occurs when ri - 1 _ c.. The numbers xi_ are called quotas, and a choice of the variables Xij which satisfies conditions (1) above is called an assignment. An optimal assignment is an assignment which minimizes the form Z,j xijdi. The simplest physical interpretation of the problem is the following: One has a fleet of N ships distributed at various stations. One wishes to redistribute them in given proportions at a set of new stations at minimal cost. Here ri is the number of ships initially at old station i, and cj is the number of ships one wishes to have at new station j after the redistribution. The quota xij is the number of ships to be sent from old station i to new station j; and dij is the cost of sending a ship over this route. (D is then called the cost matrix. The numbers ri and cj are the capacities of various stations.) If one has a given assignment [i.e., a choice of the quotas xij satisfying (1)], this choice determines how the ships are to be redistributed, and the sum ij xijdij is the total cost of carrying out this redistribution. An optimal assignment is then one which minimizes the total cost. The basic method for solving such problems is similar to that for the assignment problem. The optimal assignments are not changed if we add to or subtract from the rows and columns of the matrix D. Hence we

-13 seek to alter the matrix D by means of such additions and or subtractions so the transformed matrix D' = (d.) has the following form: Every element dji is nonnegative, and there exists an assignment such that for each quota xij which is positive, the corresponding number dji is zero. Then Zi j xijdij = 0, and this assignment is necessarily an optimal one. The usual way of arranging the data in a transportation problem is as follows: New Stations 4 5 2 8 2 9 3.2 9 4 6 11 6 6 7.5 9 2 6 Old Stations 4 4 6 2 4 6 2 2.7 0 3 7 3 The numbers above the horizontal line are the numbers c; the numbers ri are written to the left of the vertical line. The matrix (dij) is written below and to the right of the lines. An assignment is given by a quota matrix (xij); for example, one assignment is the following: 4 0 1 4 0 O 0 0 4 2 0 3 1 0 0 0 2 0 0 0 Usually these two matrices are combined into one, as follows, with each quota xij being written above the corresponding element dij (quotas which equal zero being omitted): 4 5 2 8 2 9 Y 3.2 9 4 6 11 4 2 6 6 7.5 9 2 6 3 1, 4 4:/6 2 2 4 6 2 2.7 0 3 7 3 I I, I

-14 This means that of the nine ships at old station 1, four are sent to new station 1 (at a cost of $3.20 apiece), one is sent to new station 3 (at a cost of $4.00), and four are sent to new station 4 (at a cost of $6.00 apiece). Similarly for the other stations. For this particular assignment, the total cost of the redistribution is $80.80. If we transform this matrix by adding -5, -1, -2, and 4 to the respective rows, and 1.8, -4, 1, -1, and -4 to the respective columns, one brings the matrix into the following form. Here one may pick out an optimal assignment, which is indicated: 4 5 2 8 1 2 4 1 2 2 9 0 /0 / 0 /0 2 6 6 6.8 2.5 9 0/ 1 2 2/ 4 3.8 0 1 1 1 22 / 0 2 8.5 0 8 10 3 For this particular assignment, the total cost of the redistribution is $77.80 (relative to the original cost matrix, of course). It happens that in this case there is only one optimal solution, and that is the one indicated. There are many other physical interpretations of the transportation problem; let us consider a few of them. One is called the distribution problem, which is the problem of supplying warehouses (or wholesale outlets) from factories in the most efficient way. Here ri represents the output of factory i during a given time period, and c. represents the number of units of goods which warehouse (or outlet) j can absorb in the same period. The number di. represents the cost of producing a unit of goods at factory i and shipping it to warehouse j, and xij is the number of units of goods assigned to this production-shipping route. Let R ='i ri and let C = Zj cj. If R = C, this is just the transportation problem as stated previously; in this case the total capacity of the factories equals the total capacity of the outlets. It often happens, however, that the factories can produce more than the outlets can absorb, or vice versa. In such a case, R / C. If R < C, we introduce a fictitious factory whose output is C - R, defining the costs for all goods produced at the fictitious factory to be zero. This has the effect of adjoining a row of zeros to the matrix, and it

-15 reduces the problem to the previous one. If one finds an optimal assignment, and it states that a certain outlet is to receive goods from the fictitious factory, this means that this outlet does not in actuality receive these goods. Similarly, if C< R, one introduces a fictitious outlet with capacity R - C, defining the cost of shipping goods to this outlet to be always zero. This has the effect of adjoining a column of zeros to the matrix. If the optimal assignment states that a certain factory is to produce goods and ship them to the fictitious outlet, this means that the factory does not in actuality produce these goods. In this form, the distribution problem is given the special name of the scheduling problem. It is the problem of determining at what per cent of capacity various factories (or machines, etc.) are to be run if the total operation is to be as efficient as possible. Another name for the scheduling problem is the bid evaluation problem, in which a central agency requests bids from various manufacturers to supply goods to various depots. In a competitive situation, the amount of goods offered will exceed the amount required. The problem is to determine what quantity of goods to order from each manufacturer. Other variations of the transportation problem can occur. For example, it might be forbidden to send a ship from old station i to new station j, or it might be impossible to supply outlet j from factory i. In such a case, one sets dij = o. Another example: It might happen, in the scheduling problem, that one must maintain a certain output at factory i or else shut it down entirely. (Analogously, in the bid evaluation problem, a manufacturer may set a certain minimum on the bid which he is willing to accept.) Suppose that factory 1 must maintain an output of at least k units, or else shut down entirely. Then one proceeds as follows: Factory 1 is divided into two subfactories, one - section (a) - having output k, and the other - section (b) - having output r1 - k. These are treated as separate factories. This adds another row to the matrix which is identical with the first row. Then, we set the cost of shipping from section (a) to the fictitious outlet equal to oo (instead of 0). We obtain an optimal assignment for this matrix; this optimal assignment must assign all the output of section (a) to real outlets. Let the total cost associated with this assignment be T1. Now if R - r1 is less than the total capacity of the real outlets, we cannot shut down factory 1 entirely and still supply all the outlets. In such a case, the assignment associated with T1 is the best one. Otherwise, however, we remove factory 1 from consideration entirely (deleting the first row of the matrix D), adjusting the capacity

-16of the fictitious outlet accordingly. We obtain an optimal assignment for the resulting matrix; let the associated total cost be T2. The assignment associated with the smaller of the numbers T1 and T2 is then the best one. We mention this last variation to indicate how a single practical problem may require the solution of several transportation matrices. There are other variations (which we shall not discuss) which lead to a similar situation. As the number of such supplementary conditions increases, the number of matrices which must be solved may increase rapidly.

SECTION II DESCRIPTION OF THE MITAB

SECTION II DESCRIPTION OF THE MITAB 1.0. THE BOARD The mechanical blackboard that we wish to describe herein appears complex only because of the extensive duplication of its basic elements. It is logical therefore to study first some of these simple parts to try to gain an understanding of their operation before one tries to understand the operation of the whole. 1.1. The Cell The main body of the computer is made up of 400 identical cells which are arranged in a square array, twenty cells high by twenty cells wide. The cells in turn are made up of two parts. One part is built around a teleregister for doing the arithmetic operations and the other part is built around a pair of pilot lights to provide certain designations. We can label a general cell containing the teleregister Tij and the cell containing the lights as Lij. We should not forget, however, that both these subcells are a part of the general cell of the 400-cell matrix. TELEREGISTER TELEREGISTER SWITCH VERTICAL COVERING BAR LIGHT LIGHT SWITCH VERTICAL COVERING BAR Fig. 2 THE GENERAL CELL -19

-20o Fig. 2A. General Cells in the Matrix

-21 1.1.1. The Light Cell Let us now start with the simplest part, that of the light cell. The parts are arranged as seen in Figure 2. 12 VOLT A-C WHITE LIGHT ( [ GREEN LIGHT OFF 0 0 LEFT RIGHT SWITCH GROUND Fig. 3 LIGHT CELL (Lij) SCHEMATIC Figure 3 shows the functional schematic of the light cell. Now note in Figure 2 that there is a white light to the left and a green light to the right. Directly under these two lights is a switch which controls them. If the switch handle is thrown to the left the left-hand light will glow (white). If thrown to the right, the right-hand light will glow (green). If the switch is thrown to the center position neither light will glow, for this is the off position of the switch. The specific use of these two lights is explained in Section IV. 1.1.2. The Teleregister Cell Now let us discuss the heart of the cell or the teleregister. The teleregister is an electro-mechanical device which can position a vertically-mounted drum in any one of eleven positions (see Figure 4). One position is painted yellow to represent the number zero. The next nine positions have the numbers 1 to 9. The tenth position, which is just after the ninth and just before the zero, is painted black. It stands for the number 10; normally it is not used. The teleregister is seen from the front of the machine through a mask so that one number is displayed at a time.

3 Ct 2t): ^.. P0 ro 8:

-23 1.1.2.1. Adding. As mentioned above, this device is electrically positioned. If one applies a direct current of the proper potential (48 volt d.c.) to the appropriate terminals, the face of the drum will move one position to the right when the current is removed. This is the equivalent of adding one. As mentioned before, the drum has eleven positions. It can be seen, therefore, that if we should do this eleven times, we would be back on the same position. If we should do this only ten times, we would have the equivalent of subtracting one. 1.1.2.2. Subtracting. From the foregoing discussion it can be seen that addition is merely a matter of generating the exact number of electrical pulses that one wishes to add and applying them to the teleregister. To subtract, we merely take the number of positions on the drum (eleven) and find the difference between it and the number which one wishes to subtract. We then generate this number of pulses and add. What we are doing in effect is to add the complement of the number that we wish to subtract. 1.1.2.3. Homing. The teleregister is also provided with a home or cleared position. This is the position where the yellow or zero appears. If one sends pulses to a teleregister which has an open clear circuit, the teleregister will rotate until it comes to this zero or cleared position and then will stop. This feature is very important for setup since it is quite easy to clear the cells and then dial the proper numbers in without consciously having to take account of the residual reading of the teleregister. 1.1.2.4. Schematic. In Figure 2 we see the physical layout of cell Tij as one sees it from the front of the panel. Figure 4A shows a functional schematic of the same cell. In Figure 2 we can see that the teleregister is mounted in the upper left-hand corner of the cell. Right under it is a three-position switch of the same type that was used under the lights mentioned previously. If this switch is thrown to the left, the teleregister can be set individually for any desired number. If thrown to the right, the teleregister is available for arithmetic operation with other units of its same row or column. If it is thrown to the center position, which is the off position of the switch, the teleregister unit of that cell is disconnected from the rest of the matrix.

I r| I AG CLEAR SPRINGS -, COIL LEFT RIGHT 0 0 —-- SET UP ARITH. OFF Fig. 4A TELEREGISTER CELL (Tij) SCHEMATIC 1.2. Matrix To aid the reader's process of visualizing the whole 20-by-20 matrix of teleregisters and lights, we will show, in the following paragraphs, how one would construct a very simple version. 1.2.1. Set-Up Using the teleregisters as basic units let us conceive of a 3-by-3 array. Assume that all of the Tij cells are set on their zero position. We may now go to each cell, one at a time, and throw the teleregister switch to the left. If we then feed into this line a series of electrical pulses having the same number as the number which we wish to insert into the cell, we will cause the teleregister to rotate by steps to this position. This can be done with a standard telephone dial. After each number has been inserted the switches are thrown to the right, where they connect the teleregisters to the banks of row and column access relays. These row and column access relays are only electrical switches enabling us to add to, or subtract from, the rows and columns.

-25 1.2.1.1. Procedure. In Figure 5 we have a simplified schematic of the Teleregister setup circuit for the 3-by-3 array. The mechanism for directing the pulses to the desired teleregister is provided in each teleregister cell. If the switch which appears in Figures 3 and 4 is thrown to the left, that teleregister will follow the pulses that appear on the setup circuit bus. It can be readily seen that it is possible to have more than one teleregister connected to the bus at the same time by the use of these switches. The usual practice will be to connect one at a time to the bus and proceed to set the proper number into that cell or teleregister. When this operation is complete, one throws the switch back to either the off position or to the arithmetic position (on the right). One then proceeds to the next one and repeats the operation with the appropriate number. 1.2.1.2. Set-up Switch. Let us now examine the Set-up Switch. If this switch is thrown to the dial position, dial pulses can be placed on the set-up circuit bus and thus to any teleregister that is connected to the bus by its own switch. If the Set-up Switch is thrown downward to the battery position, the teleregisters can be stepped one step at a time by connecting and disconnecting the teleregister from the bus. The teleregister in this case will move one position each time it is disconnected from the bus. The Set-up Switch can be left in any position and used as desired by throwing the proper teleregister switch. 1.2.1.3. Push Buttons. In Figure 6 we have a flow diagram of a 3-by-3 array for the basic calculating matrix. This matrix is designed to show how the functions of addition and subtraction for rows and columns are accomplished. From the drawing it can be seen that access to the teleregisters in any row or column is obtained through the row and column access relays. The control of these relays plus the control of the add and subtract circuits is provided through the push buttons which are located on the figure above and to the left of their respective relays. It should be pointed out that this location on the drawing is not necessarily the same as the physical location of the devices on the machine that we have built. 1.2.2. Clearing In Figure 7 we have the Clear Circuit and ground return for the teleregisters of our 3-by-3 matrix. As mentioned in paragraph 1.1.2.3, there is a home or cleared position on the teleregister one position before the "1" position. This is painted yellow. This big yellow block also represents the zero position, so that it has considerable significance not only in the problem but in the setup of the problem.

SET-UP SWITCH DIAL PULSES DIAL - g Fig. 5 TELEREGISTER SET-UP CIRCUIT I I I\_ -I — I\_ I I\ I

SUB I CTRL:LAY CTRL SUB I r -.I I ft- I Ir I I *T I L1, L- — I I -'- I Fig. 6 BASIC CALCULATING MATRIX

Fig. 7 CLEAR CIRCUIT AND GROUND RETURN FOR TELEREGISTERS

-29 1.2.2.1. Clear for Set-Up. In the setup of the problem it is desirable to have all the teleregisters set to a common position. Further, it is best that this position be such that one can use a telephone dial and be able to have the dialed number appear on the teleregister. This will happen if the teleregisters are in the cleared position before one starts. 1.2.2.2. Electrical Ground. The electrical ground return is through the number-one pin of the teleregister bus (see.Figure 4A) during ten of the eleven positions of the teleregister drum. In the eleventh position, which is the zero or yellow position, the ground return must occur through the AG pin. If this electrical ground is not present, the teleregister will not rotate past this position no matter how many pulses it receives. In Figure 7 the "1" ground return line comes out of the upper left of the Tij block and the AG ground return line comes out of the upper right-hand corner of the same block, where it joins the clear bus which goes to the clear switch. 1.2.2.3. Ten Pulses to Clear. It can be imagined that there are a number of different means that one might use to clear the entire matrix. We can readily see that, no matter what position a teleregister may be in, it will never take more than ten pulses to bring it back to the zero or home position, since there are only eleven positions on the drum before it repeats itself. Therefore, if we can open the clear circuit on each teleregister and feed it ten pulses, each of the nine teleregisters in the case of our 3-by-3 device, or each of the four hundred in the case of our 20-by-20 mechanical blackboard, will then find its home position and would be showing zero (yellow position). 1.2.2.4. Easy Clearing. In our mechanical blackboard, the easiest way to do this is to throw the clear switch downward from the operate to the clear position, which opens the clear bus, and then push the row-subtract buttons (ten pulses) consecutively one at a time until all the teleregisters are cleared. The above operation is assuming that the teleregister switches are in the arithmetic condition. 1.2.3. Light-Cell Bus In Figure 8 we are merely trying to emphasize the simplicity of the cell light system. There is no interconnection between the cells Lij other than the bus which feeds 12 volt a.c. power to each one of the cells Lij. 1.2.4. Bars In addition to the electrical features, let us now add two-color bars (covering bars) to each row and column (see Figures 2 and 2A).

r — -r — r — -i - I' "'' |- 2, |'' | r~~ n n FL |"" A L 12VA-C [-t. I II I * I I 11; 12; 1: I I L__ J _ _ J __WER a'?:;; 1-2|;!;^; L22;!2'd; L.23 s'-; n —;-I 2- I. lJI ~^. I 00" } 12V.A-C L__J L J L.J POWER Fig. 8 POWER FEED SYSTEM FOR CELL LIGHTS

-31In the black position they are inactive. In the silver position they indicate that the row or column is covered. Some of the bars have a third color (red) to help set off the double rows used in the solution of the transportation problem. It can be seen that we can expand this 3-by-3 array into a 20-by-20 array with no change of theory or practice.

-33 2.0. CONTROL 2.1. Control Panel on Face of Computer In Figure 9 we see a diagram of the major features of the front of the mechanical blackboard. We see that the row-subtract push buttons are the first column to the right of the 20-by-20 matrix with its row and column covering bars. In the second column to the right are the row-add push buttons. In the first row below the matrix are the columnsubtract push buttons. To the extreme right of the mechanical blackboard, between the row-add push buttons and the edge of the mechanical blackboard, lies the control panel. 2.1.1. Problem-Changeover Switch In Figure 10 we have an enlarged view of the controlpanel section. If we start at the top, we see that the first control that we come to is the Problem-Changeover Switch. This mechanical blackboard was built to be able to work two types of problems. The first is the Assignment Problem and the second is the Transportation Problem. The function that this switch performs is to prevent automatically any arithmetic operation on the first row and column plus all the even rows during the solution of a Transportation Problem. It does this through relay 41 by disabling the control circuits of the proper row relays and the proper contacts of the column relays. In the Assignment position nothing is disabled. Each position of the switch is indicated by the pilot light: a green pilot light to the left for the Assignment Problem and a white pilot light to the right for the Transportation Problem. 2.1.2. Clear Switch The next control below the Problem-Changeover Switch is the Clear Switch. During the solution of the problem, the clear switch is left in the up position, called the operate position. In this position the upper pilot light comes on (green). When one wishes to erase the problem from the matrix, he throws this switch downward, as mentioned in paragraph 1.2.2.4, to the clear position, which is indicated by the lighting of a white pilot light underneath the switch. One then proceeds to push the row-subtract buttons to clear the teleregisters. 2.1.3. Set-Up Switch Next down from the Clear Switch we find two switches. The one on the left is called the Set-up Switch and the one on the right, the Add Switch. The Set-up Switch was described in paragraph 1.3.1.2; the dial position is indicated by the glowing of a white pilot light located above the switch. The downward position of the switch, which is

20 X 20 MATRIX WITH COVERING BARS u) z 0 U, Co m 0 0 Ir 0) z 0 Co m 0) 3 ao 0 z 0 0 w U, -J w z 4 a. -I 0 z 0 0 HANDLES -- CABINET BASE CASTERS S I I COLUMN SUBTRACT PUSHBUTTONS ACCESS lT ACCESS DOOR DOOR 4^ ^y~~~] -y fig. 9 FRONT LAYOUT OF COMPUTER

ma ndm- o jo D}JlnW O'Th0 A'v6',v6 tT Or......!I

.36-.. m. I. cft.04. id — I ANEW I...-...... - -.1-.........I........ - -..U.- ", FlA g. 9B.3 Rear View Showing Wiring andn Power Slupply

F:)g. 9C.0.f t End. Viw Showi ng Row!Relays and Te.n2, er

r~~~~~~~ PUSH1BUTTONS < L0- - - - ~ --.-. I I I i I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I _I _I ROW SUB ADD 0 0 0 0 0 0 0 0 0 0 0 0 O O 0 0 O O 0 O 0 0 0 0 O O O O O O O O O O O O O O O O -+ PROBLEM ASSIGN. TRANSP. CHANGEOVER SWITCH OPERATE ( CLEAR CLEAR ~E DIAL SETUP ( MANUAL O SUB. IN PROGRESS DIAL ( ADD PUSHBUT. TELEPHONE ~ ~ 24V DC 48V DC — FUSE -- -- Q-~~ —. FUE DC 0 —* FUSE-.-~* Supply 12 V AC ON (o (~ Power 0Q G Switch OFF F /ig. /0 CONTROL PANEL SECTION

. 39 Fig. IOA. View of Up)per Control Panel S(ect:i on

UQ 0 0) 6 er; 0 Ct 0 I O7" t

-41 called Battery, applies 48 volt d.c. to the set-up-bus in case one wishes to make his own pulses with the teleregister switches. 2.1.4. Add Switch The right-hand switch is called the "Add Switch;" it controls the mode of operation of the add circuitry. If the switch is downward in the battery position, the pushing of any of the row-add buttons will add one to that row. Throwing the switch upward puts the switch in the dial position and lights a white pilot light to designate this condition. In this position it is possible to push any one of the row-add buttons and then dial the number that one wishes to add to that particular row. In this way one can use the telephone dial to add and subtract any number from one to ten. 2.1.5. Telephone Dial The telephone dial that has been mentioned in the preceding paragraphs hangs on a hook just under the Set-up Switch and Add Switch. It is equipped with a spring cord so that one can remove it from the hook and use it at the other end of the computer. For shipping or moving purposes the cord is equipped with a telephone plug, so that the dial and cord may be disconnected completely. 2.1.6. Ten-Pulser Supervisory Lights Directly beneath the telephone dial are two supervisory lights for the ten-pulser. The white light on the left, labeled Subtract in Progress, indicates the duration of the subtracting process. During this time a second subtract button should not be pushed. It should be mentioned that the circuit is so designed that it is not necessary to hold one's finger on the subtract button during the subtracting process. Further, it is so designed that, if one does continue to hold one's finger on the subtract button even after the subtraction has taken place, no damage or malfunction will occur. Under these circumstances, one sees the particular row teleregisters subtract one by taking ten steps, the Subtractin-Progress light goes on at the beginning of subtraction and goes out at the end. The green Ten-Pulser Reset light on the right fails to light until one takes his finger off the subtract button. When the finger is removed, the ten-pulser resets and the reset light glows. This light should always be lit whenever the ten-pulser is not being used, which signifies that the ten-pulser is ready for subtraction. 2.1.7. Column-Add and -Subtract Switch Mounted externally on the right-hand edge of the mcchanical blackboard is a switch which can be used to convert the column

push buttons to either addition or subtraction. This switch is slightly above and to the right of the power controls. 2.1.8. Power Control At the extreme bottom of this panel is a section devoted to the control of the power used by the mechanical blackboard. The power switch is located in the lower right-hand corner of this group. The line fuses for the a.c. supply and for the d.c. supply are located just above the power switch. A pilot light for the a.c. supply is located just below it on the left. On the d.c. supply are two additional output fuses on the 24-# and 48-volt outputs. These are located above the line fuses, left to right, respectively, with their corresponding pilot lights located just above. It should be noted that, since the a.c. supply is merely a pair of transformers, we are only fusing the primary side in this case.

3.0. CONTROL SUB-CHASSIS Until now we have ignored the details of the control subassembly. We have referred to it as if it were a black box. However, it is really several black boxes, since the chassis is multifunctional. 3.1. Description We have on this unit a part which is used to generate ten pulses for our subtract "1" circuit. We also have the equipment for the add "1" circuit. Lastly, we have a part that is devoted to limiting the pulse length to the teleregisters. 3.1.1. Subtract Circuit (Ten-Pulser) In paragraph 1.1.2.2 it was pointed out that, if one wishes to subtract, it is only necessary to add the difference between the number that one wishes to subtract and the number of positions on the teleregister. If we wish to subtract "1," we must generate ten pulses. The following is a description of the device designed to generate these pulses automatically. 3.1.1.1. Step-Switch Count. If we look at Figure 11, we can find RY 46 (step switch) at the right-hand side. This is the heart of the ten-pulser. By proper treatment, this device can be made to count. In our circuit, we start it with RY 43 (start relay), and after it has counted to ten pulses, we arrange to have RY 44 (stop relay) stop the circuit. If one then removes his finger from the subtract button, the ten-pulser is ready to start all over again. 3.1.1.2. Start Relay. As an aid to understanding the tenpulser, we have drawn a time-sequence diagram (see Figure 13). The first thing that happens is that a ground is applied to the start line by pushing a subtract button. An instant later the start relay pulls up (RY 43A and B) and remains up until the finger is removed from the subtract button, which in this case is after the subtraction has taken place. It should be noted that two actions are directly connected to the duration of operation: the row-# and column-relay lock circuit and the reset ground. This means that the row or column relay will remain locked as long as the start relay is activated. It also means that the ten-pulser circuit will not reset as long.as one has his finger on the subtract button, even if the subtraction is finished. 3.1.1.3. Stop Relay. The stop relay halts the generation of pulses after the tenth pulse has been reached. The Subtract-inProgress light is lit by the pull-up of the start relay and is extinguished even before the start relay is released by the stop relay. The operating

RESET LIGHT GROUND 12V A-C +24V D-C +48V. D-C SUB. IN PROGRESS LIC ROW a COL. RELAY LOCK C START (10 PULSER),HT >- SUB.:KT. ur OPERA 4W STAR LO A-C " +48V. D-C FIL. 0 _L _) U 02 * J tL U a D TING GND RT RELAY IN PROG. w >OW Uo r 12 V. A-C +48V DI- a_> OPERATING GND I r- A -STOP AC FILOP STOP RELAY OPER. )CK CKT -C Ii OPPER ATE I-I INTERRUPTER -, SPRING U) CL w w cr wt-.4 w >~~~- Q Z5 W ~CLW co t- CL Cr + 48 V. D-C - + 24VV D-C L RESET GROUND 10 PULSES PULSE OUTPUT BUS START (ADD) BAT. OR DIAL LEAD,. -J _W a. 0 0 04 Fig. / TEN PULSER SUB CHASSIS BLOCK DIAGRAM

4I \J1 Ik' Fig. /2 TEN PULSER SUB CHASSIS BLOCK DIAGRAM

-46 ground for the step-switch system and the start-relay lock circuit have a similar relationship to the start and stop relays. They function while the Subtract-in-Progress light is lit. 3.1.1.4. Start-Relay Lock Circuit. As mentioned in the discussion of the control panel, the purpose of the Subtract-in-Progress light is to warn the operator that a second subtract button should not be pushed until the subtraction is complete. The start-relay lock circuit is to insure that the subtraction once started will be completed regardless of whether one keeps his finger on the subtract button or not. The operating ground is the ground that controls the operation of the step switch. 3.1.1.5. Step-Switch Cycle. When this ground is applied the step-switch system begins to step by itself from the home position at a rate set by the thryatron delay circuit, which controls the time delay between steps. The stepping continues until the switch reaches the 19th step, at which time the stop relay pulls up, ending the operation. During the travel from the home position to the 19th step, the action of the plate-circuit relay of the thyratron delay circuit (RY 45) and of the motor magnet of the step switch (RY 46) is as shown in the time-sequence diagram (Figure 13). 3.1.1.6. Ten-Pulse Output Flow. The action of the teleregister pulse relay (RY 47) is to pull in on the odd-numbered steps. The relay which controls the pulse-limiter circuit (RY 49) follows the action of the 48-volt pulses fed in by the teleregister pulse relay (RY 47) or the add relay (RY 48). The action of the pulse-limiter plate circuit relay is to break the circuit to the teleregisters in the case of a long pulse. Since the diagram (Figure 13) was made up under the assumption that the operator held his finger on the subtract button, the last (or tenth) pulse was a long pulse; therefore, the pulse limiter functioned and shortened the tenth pulse directly from the teleregister pulse relay (RY 47). It should be noted that the pulse limiter (RY 50) releases a lock circuit on the ten-pulser start relay. This circuit insures an adequate length for the tenth pulse. 3.1.1.7. Step-Switch Reset. When the operator finally takes his finger off the subtract button, the start relay falls out because there is an open lock circuit and an open start line. A reset ground is then provided and the step-switch system will take one step to the home (or twentieth) position, which is equivalent to the zero position. The ten-pulser is now ready for another subtraction operation. If the operator does not hold his finger on the button, as he did in the case just described, the start relay falls out as soon as the stop relay pulls up, and the system resets. This condition, as mentioned earlier, causes the reset pilot light to glow.

TIME START 10 PULSER START RELAY (RY 43) STOP RELAY (RY 44) START RELAY LOCK CKT. ZERO TIME ---- N\\N XX\NNXNNNXXNXX\ NXXX KXXXN Nzz\ ////////////////// ///////////// OPERATING GROUND k\\ \\\\\\\\\\\\\\\ RELAY 45 RELAY 46 RELAY 47 RELAY 49 RELAY 50 OUTPUT SUB. IN PROGRESS RESET GROUND RESET PILOT ROW AND COL RY. LOCK CKT I 2 3 4 5 6 7 8 9 10 II 12 13 14 15 16 17 18 19 i D D 0 E 00 00 0 D 0 O II!] 0 D 0 010 o 0 00 0 o oo [1 0 O O00 00 0 I 2 3 4 5 6 7 8 9 iZ 2 Za1 4 5 6 7 8 9 ES 1 E1S 1S I 1 E11 S E~112 1 20 0 0 10 10 z\\\\ VIIA 2 3 4 5 6 7 8 9 10 n\\\\\\\\\\\\\\~\\~~~~\\\\\\1 IRESET GROUND IRESET PILOT LIGHT V/ / F/////// T/// /// ////E S////E/// A Fig. /3 TEN PULSER TIME SEQUENCE DIAGRAM

3.1.2. Add Circuit The add circuit, which is also taken care of by the sub-chassis, works in the following manner. When one pushes an add button, one contact pulls in a row relay and the other contact puts a ground on the start add line. This ground will pull in the add relay (RY 48) which will place 48 volts d.c. on the teleregister bus going into the pulse-limiter circuit. The action is the same as that of the ten-pulser. As soon as the pulse is too long, the pulse-limiter circuit breaks the circuit. At this break the teleregisters will all move one position, which is the purpose of the circuit. 3.1.2.1. Add Circuit and Lockup Functions. The operation of the add circuit in several functional respects is very similar to that of the subtract circuit. First, the power to operate the teleregisters does not go through the push buttons, since they do not have the current-carrying capacity. Instead, a relay with heavy contacts is used. Further, the add relay will lock up just as does the start relay for the ten-pulser, insuring that the addition will take place independent of the duration of pushing the button. The lock circuit for the row relays is also connected to this locking function. Lastly, the add circuit is released at the end of one pulse when that pulse exceeds the pulse duration set into the pulse-limiter circuit. The diagrams of Figure 17 show the add-circuit functions. The first diagram shows the timing that occurs when one starts the add circuit with a short pulse. The second diagram shows how the circuit reacts when one pushes the add button and holds it. It can be seen that the length of the output pulse is the same in both cases. The only difference is that, when one holds his finger on the button, some of the relays are held up until the button is released, but no second pulse is produced; i.e., the end of the pulse is not dependent on the release of the add button. 3.2. Electronic Circuits 3.2.1. Step-Switch Circuits We have avoided in our previous discussions any detailed mention of several portions of the sub-chassis. These portions include the electronic circuits and the stepping switch. We will now treat the electronic circuits associated with the step switch of the ten-pulser. 3.2.1.1. Thyratron Time Delay. Let us now consider the Thyratron Time Delay which drives the stepping switch. Figure 14A is a diagram of cathode-bias circuit, which puts a positive voltage on the cathode with respect to the shield grid. This allows one to produce a critical grid voltage (firing voltage), which is twenty or thirty volts positive with respect to ground.

-49 SHIELD GRID CONTROL GRID Fig./4A CATHODE BIAS CIRCUIT CHARGING RESISTOR STORAGE CAPACITOR Fig. 1/48 TIME DELAY CIRCUIT (INTEGRATOR)

-50 3,2.1.2. Integrator. Figure 14B shows a typical time-delay circuit or integrator circuit. If a constant voltage is applied to the right end of this circuit, the voltage measured at the other end rises exponentially toward the applied voltage. If the charging resistor is made variable, it is possible to change the rate of rise of this voltage and so control the timing of the whole delay circuit. 3.2.1.3. Plate Circuit. In Figure 14C we have tried to show the essential elements of the anode or plate circuit. A plate dropping resistor is inserted in series with the plate relay to set the proper current for the relay and tube. The arc suppressor network, seen to the left, is an attempt to suppress the inductive kick of the relay when the circuit is broken. The plate relay (RY 45) performs two functions: it provides an operating ground for the motor magnet of the step switch and a discharge ground for the time-delay capacitor. 3.2.1.4. Motor Magnet. Figure 14D is a diagram of the stepping switch motor and level connections. On the left-hand side are connections to the motor magnet and the interrupter springs. If a ground is applied to point X, the motor magnet will pull up. This opens the interrupter contacts and compresses the wiper driving spring. When the motor magnet is released, the interrupter contacts reclose and the wiper driving spring. When the motor magnet is released, the interrupter contacts reclose and the wiper driving spring is allowed to advance the step switch to the next position. 3.2.1.5. Step-Switch Contact Levels. Figure 14D also shows that the first and second levels of the step switch are arranged to operate the stop relay on the nineteenth position and the reset pilot on the twentieth. The third and fourth levels have all the contacts, except the twentieth, strapped together and are used whenever the ten-pulser must be reset. The fifth and sixth levels have their odd-numbered contacts strapped together, so that they will feed one pulse for every two steps of step switch and ten pulses for 19 steps, or one-half revolution of the wiper assembly. 3.2.1.6. Complete Circuit. Now let us combine all these elements and see how they work together. In Figure 14E we see the combination. If an operating ground is supplied to the circuit, the voltage will begin to rise across the storage capacitor. During this rise time the tube will remain unconducting because of the cathode-bias voltage. As soon as the voltage across the capacitor, Cs, reaches the critical grid voltage as set by the cathode-bias resistor, Rls, the tube fires and the plate relay pulls up, applying a ground to the motor-magnet circuit and discharging the time delay capacitor Cls, so that it will be ready to start the next cycle. When the motor magnet pulls up, it breaks the plate circuit allowing the plate relay to release and the tube to extinguish.

TO MOTOR MAGNET OF STEP SWITCH TO DISCHARGE TIME DELAY CAPACITOR PLATE DROPPING RESISTOR ARC PLATE RELAY RELAY 45 r~Mw I \-7 I LIMITING RESISTOR THYRATRON PLATE CIRCUIT Fig. 14C

o00 0 O O0 0 0 0 0 0 0 0 0 0 O INTERRUPTER CONTACTS [ + 24V 0 Z Xo.-TO STOP RELAY j-'-'-TO RESET PILOT ~- - LEVEL Ia 2 ) x ARC SUPPRESSOR -4' — L — L 20 --- \ " LEVEL 3 a 4 l1 ro -- -- LEV- 05 -:. - LEVEL 5 & 6 TO TELEREGISTER RELAY RELAY 47 STEPPING SWITCH-MOTOR AND LEVEL CONNECTIONS Fig. /4D

+ 48V +48V ( RY. 46) R2S r" OPERATING GROUND O 0 o 0 O 0 Lo 0 — — LEVEL 2 LEVEL I 8 2 tcISI CI l s -- LEVEL 3 a8 4 RESET GROUND 9 0x - o-LEVE ** ~LEVEL 5 8 6 THYRATRON TIME DELAY AND STEPPING SWITCH CIRCUIT Fig. 14E

-54 This in turn will allow the motor magnet to release and step the stepping switch to the next position. Since the tube is extinguished and the time delay capacitor is discharged, the circuit is ready to repeat the cycle as long as there is a ground at the base of the cathode resistor. 3.2.1.7. Adjustments. The critical grid voltage is set by setting the circuit to its slowest speed (R4s, fully counterclockwise) and then noting the firing voltage with a vacuum-tube voltmeter at the control grid. A value of 25 to 30 volts is a good mean value. This is known as setting the sensitivity. After it is set, it is only necessary to turn the speed control for the desired speed of subtraction that still gives reliable operation of the teleregisters. 3.2.2. Pulse-Limiting Circuit Turning to Figure 15A, we take up the pulse-limiting circuit. Since this circuit is very similar to the thyratron delay circuit discussed above, we will only show the ways in which the circuit differs from it. 3.2.2.1. Pulse-Cycled Charging. In the pulse-limiting circuit there is a slightly different function to perform and a different cycle through which to go. The pulse limiter is supposed to work only when one of the pulses which passes through it is too long. However, unlike the former circuit we must recycle the storage capacitor after each pulse whether the tube fires or not. Only in this way can we properly sense the length of the individual pulses. In Figure 15A we see this pulse-cycled charging circuit. Note that in this circuit the charging path is closed only when the 48-volt pulse is applied to the pulse line, which in turn will pull up the relay (RY 49). Whe-n there is no pulse, the charging circuit is open. Also, when there is no pulse, a discharge path is connected across the storage capacitor. 3.2.2.2. Resetting State of Charge. It can be seen then, that the state of charge is brought back to zero after each pulse and that no series of pulses which are individually shorterthan the critical length, as set into the pulse limiter, will trip the circuit. 3.2.2.3. Plate Circuit. In Figure 15B we have a diagram of the anode circuit of the pulse limiter, showing the plate-dropping resistor, as before, as well as the plate-circuit relay. The functions of the two sets of break contacts are shown also. The top set breaks the outgoing pulse, and the bottom set of contacts breaks the locking circuit to the add relay (RY 48), releasing this circuit after one pulse has been terminated.

RELAY DROPPING RESISTOR < (RY 49) L & Iv DISCHARGE > CURRENT > LIMITING > RESISTOR TO CHARGING RESISTOR I I I I I I I I I I I I I I I I I I I I I I I I I OUTPUT TO - TELEREGISTERS (RY 50) TO LOCK CKT. OF (RY 43B) TO STORAGE CAPACITOR I i -at9,_ - - -.... v"',',,...... — I I I TO LOCK CIRCUIT OF ADD RELAY (RY 48) PULSE CYCLED CHARGING CIRCUIT PLATE CIRCUIT OF PULSE LIMITING THYRATRON Fig. /5A Fig. /58

-56 3.2.2.4. Complete Circuit and Adjustment. Figure 15C shows the final combination with the two circuits that feed pulses into the pulse limiter. It should be noted that one would set the critical firing voltage or sensitivity of the tube in the same way as described for the delay circuit. The potentiometer that constitutes the cathode-bias resistor increases the critical firing voltage as it is turned toward the clockwise end. The charging resistor is connected differently in this case, since it is the duration that one is interested in and not the speed of the step switch. Since we measure the time delay in a different way, the control is arranged to accept a longer pulse, when it is turned in the clockwise direction. 3.2.2.5. Wave Shapes. Figure 16 shows some of the wave shapes that one should expect to find in the pulse-limiter circuit for different-length pulses. This diagram is meant to show that during normal pulses there is no action in the pulse limiter. If a long pulse is received, however, the critical grid voltage is exceeded by the charge on the storage capacitor (integrator circuit) to the tube fires, limiting the pulse length. 3.3. Power Supplies 3.3.1. Dual-Voltage D.C. Supply The last item that we should cover is the dual-voltage power, supply. This supply is really two supplies in one. The single power transformer has two primary windings with the low-voltage taps at the ends of the windings tied together, so that the windings are in parallel. The two secondaries are connected individually to two full-wavebridge selenium rectifiers. The first rectifier feeds a single "L-Section" L-C filter. The output voltage of the first rectifier is also added in series to that of the second and then fed into a second filter which is identical with the first. The output voltage of this part of the supply is nominally 48 volts with respect to ground, while the output of the first part is nominally 24 volts with respect to ground. Two points should be noted at this time. The first is that the output capacitors are 15 working volts d.c. 2000 mfd. capacitors used in series with 25-ohm equalizing resistors across each. They also provide a minimum load. The second point is that the output capacitor for the 48-volt section is not independent of the output capacitor for the 24-volt section (see Figure 18). 3.3.2. 12-Volt A.C. Supply We might mention that there are two six-volt transformers with their secondaries tied in series to give twelve volts. These supply the power for the matrix pilot lights. The fusing is only in the primary circuit while the on-pilot light is only on the secondary 12-volt bus.

RY43 B - 48 V TO LEVELS 5 & 6 (RY 46) (RY 47) ) C13S +24v _ SUBTRACT CIRCUIT BATTERY OR DIAL Fig. /5C PULSE LIMITER CIRCUIT

IUI a V4 St: PP 5~Z10,~ 04 )A:z~ It.,'''':':': Vi

INPUT (RELAY 49) RC11 S (RELAY 50) OUTPUT CRIT GRD. VOLTAGE CRIT GRD. VOLTAGE — i V7mmA /nz T I 1o I L WAVE SHAPES FOR PULSE LIMITER CIRCUIT Fig. /6

SHORT START TIME ---- TIME ZERO START PULSE ///// ROW RELAY \\ ADD RELAY ///// DELAYED ADD RELAY \\ RELAY 49 RELAY 50 OUTPUT I///////!//////////////////// zz /// / /// / // / /n START PULSE ROW RELAY ADD RELAY DELAYED ADD RELAY RELAY 49 RELAY 50 OUTPUT K. s rz r, N ST. R T, LONG START I o 0 or//////l///////Z - 111/1111///// Fig. /7 ADD CIRCUIT TIME SEQUENCE DIAGRAM

L2 +48 R4 25..C3 20 W LID B AN 3102-16-IOP Fig. 18 TWO VOLTAGE D-C POWER SUPPLY

-62 3.3.3. Power Plugs When the mechanical blackboard is set up after it has been shipped or moved, a power cord must be plugged into the back of the mechanical blackboard. The plug is a Hubbel Twist-Lok plug, which should be inserted into the socket and turned to the right. Two other plugs may have been disconnected, namely, the input and output plugs on the d.c. power supply. The input plug is a standard two-pronged wall plug, while the output plug is a four-pin aircraft plug. In inserting the latter plug one should be careful to match the keyway and to screw in the knurled clamping nut on the body of the plug. These two plugs and sockets are located on one face of the supply, inside the case on the top of the wood cabinet. Since the sub-chassis is sometimes removed for maintenance and repair, one should check the Jones Plug, which connects it to the rest of the board. 3.3.4. Tubes and Fuses The electronic tubes used in the machine are 2D21 thyratrons. The fusing for the machine is done with Buss 3AG Little Fuses. The sizes are tabulated below. Main Power 3 amp. 24-Volt Output 1 amp. 48-Volt Output 3 amp. 12-Volt A.C..75-1 amp. The fusing is designed for proper adjustment and use. Some adjustments of the sub-chassis will blow the 48-volt fuse, and more than the designed load of 20 lights will blow the 12-volt a.c. fuse.

SECTION III ALGORITHMS FOR THE ASSIGNMENT AND TRANSPORTATION PROBLEMS

SECTION III ALGORITHMS FOR THE ASSIGNMENT AND TRANSPORTATION PROBLEMS The Assignment Problem The problem is that of choosing a set of m independent elements of the matrix A = (xij) such that the sum of these elements is minimum. We assume for the present that the elements of A are integers. Two remarks are in order: (1) There is a theorem of K6nig which states: If A is a matrix, and m is the maximum number of independent zero elements of A, then there are m lines which contain all the zero elements of A. (2) It is readily seen that the solution of our problem is not changed if we replace xij by Yij, where Yij = xij - ui - vj (ui and vj are arbitrary constants). These facts provide a basis for H. W. Kuhn's algorithm: M. M. Flood has outlined it in the following form: Step 1. Subtract the smallest element in A from each element of A, obtaining a matrix Al with nonnegative elements and at least one zero. Step 2. Find a minimal set S1 of lines, n1 in number, which contain all the zeros of Al. If nl = n, there is a set of n independent zeros, and the elements of A in these n positions constitute the required solution. Step 3. If n1 < n, let hi denote the smallest element of R1 which is not in any line of S1. Then hi > 0. Add hi to each element of A which is in a line of S1 and subtract hi from every element of Al. Call the resulting matrix A2; it will be nonnegative. Step 4. Repeat Steps 2 and 3, using A2 in place of Al. The sum of the elements of the matrix is decreased by n(n - nk)hk in each application of Step 3, so the process must terminate after a finite number of steps. To complete the algorithm, it is necessary to give a constructive procedure for carrying out Step 2, i.e., for finding (1) a minimal set of lines which contain all zeros and (2) a maximal set of independent zeros. The present algorithm differs from Kuhn's at this point. Our procedure follows. in the course of the problem, certain lines will be distinguished; we will speak of these lines as covered lines. An element of -65

-66 the matrix is said to be noncovered, once-covered, or twice-covered, depending whether it lies in precisely non-, once-, or twice-covered lines. We will distinguish some zero elements by means of asterisks, and some by means of primes. (We refer to "starred zeros" and "primed zeros," respectively). At the beginning, no lines are covered and no zeros starred or primed. Step 2a. Cover the row and column of each starred zero (if any); erase all primes (if any). Choose a non-covered zero element (if any); star it; cover its row and column. Repeat until all zeros are covered. [These starred zeros are independent.] Step 2b. Find a twice-covered starred zero Z and examine for the following possibilities: (I) If there is a once-covered zero C in Z's column and no once-covered zero in its row, prime C and uncover Z's row (leaving C and Z covered). If there is a once-covered zero R in Z's row and none in its column, prime R and uncover Z's column (leaving R and Z covered). (II) If there is a once-covered zero in Z's column and one in Z's row, prime both and go at once to Step 2c. (III) If there is no once-covered zero in Z's row and none in its column, do nothing. Repeat Step 2b for each twice-covered starred zero in turn. Continue repeating until either (II) holds, or there are no more twicecovered starred zeros, or each twice-covered starred zero has no oncecovered zero in its row and none in its column. In the first case, go to Step 2c. In the last two cases, certain starred zeros are once-covered; they will be called primary zeros. The covered lines containing them will also be called primary. The primary lines are characterized by the fact that they belong to every minimal set of covering lines for the zeros of A. Go to Step 2d. Step 2c. We begin this step at the point when (II) has just been applied to the starred zero Z. Let CO = Z. Let C1 denote the primed zero in Co's column. Let C2 denote the 0* in Clts row (if any). Repeat, using C2 in place of Co. Continue repeating until the sequence comes to a stop, at some 0', C2j+l, which has no 0* in its row. Then one has a sequence CO, C1,..., C2j+l of alternating starred and primed zeros. [We must prove that, given C2., C2i+l may be found; we must also prove that the chain is finite. Note first that no line contains more than one O* and no covered line more than one 0', so that the sequence is uniquely specified. We proceed by induction, assuming that C2i-l is a once-covered 0' whose column is covered. The row of C2i1_ is not covered, so that

the starred zero C2i in this row has only its column covered. Then (I) applies to C2i at some stage of the testing process, and there is a 0', C2i+l, in the column of C2i. Since C2i+l was once-covered at the moment it was primed, it is still once-covered. Hence the induction hypothesis is satisfied. Furthermore, C2i+l was primed previous to the priming of C2i-1. The row of C2i was not covered when C2il was primed (or C2il could not have been once-covered), so that the uncovering of C2i's row and the priming of C2i+l must have taken place previously. Hence the sequence is finite, and all the members of the sequence are distinct.] Let R = Z. Let R1 be the 0' in R0's row. Let R2 denote the 0* in Rl's column (if any). Repeat, using R2 in place of R0. Continue repeating until the sequence comes to a stop, at some 0', R2k+l, which has no 0* in its column. [A similar argument shows that this is always possible, and that each starred zero R2i has its row covered.] All the members of the sequence R2k+l, R2k,..., Rij Z, C1,., C2j, C2j+l are distinct elements of the matrix. [All the Ci lie in covered columns and the Ri in covered row, and each member of the sequence except Z is once-covered.] Unstar each starred zero of this sequence, and star each unstarred zero of the sequence. It is clear that after this starring and unstarring, the resulting set of starred zeros will be independent. [If two of the primed zeros of this sequence are in the same line, this line is uncovered. There must be a 0* in this line; then this 0* must appear twice in the sequence, which is a contradiction.] This set is larger by one than the previous set of independent zeros. Return to Step 2a. Step 2d. Uncover the column of each twice-covered 0* (if any). Then each 0* is covered exactly once (so that there are as many covered lines as starred zeros), and all zeros of the matrix are covered. [Each application of (I) or (III) leaves all zeros covered, and (II) does not occur, by hypothesis. Uncovering the column of each twice-covered 0* cannot make a non-covered zero appear, since no twice-covered 0* had a once-covered zero in its column at the beginning of this step.] Then the covered lines form the required minimal set S1 of lines containing all the zeros, and the starred zeros form a maximal set of independent zeros. [It is obvious that a set of lines containing all the zeros of a matrix cannot contain fewer lines than the largest number of independent zeros. Since here there are the same number of covered lines as starred zeros, the preceding statement holds.] Since Step 2c increases the number of starred zeros each time it occurs, it can repeat only a finite number of times. Hence we must complete Step 2d at last, and at this point we have the required set of covered lines.

-68 The following variations on this algorithm improve the efficiency of the operation: (1) In Step 1, one should subtract from each row its smallest element, and then subtract from each column of the resulting matrix its smallest element. (This will give many zeros immediately.) (2) At the end of Step 2, a certain maximal set of independent zeros are starred. After Step 3, each starred zero will still be zero (being once-covered). [Note: this shows that Step 3 cannot decrease the maximal number of independent zeros.] When one returns to the beginning of Step 2a, he should leave these zeros starred; they will form a good initial "trial set" of independent zeros. (3) For theoretical purposes, it does not matter, in Step 2a, in what order the starred zeros are tested. In hand computations much labor may be saved by an adroit choice of this order. As remarked previously, Step 3 decreases the sum of the elements of the matrix, so that the algorithm has only a finite number of steps. One may prove the following stronger result. Suppose that the application of Step 3 does not increase the maximal number of independent zeros. Then when one repeats Step 2, one arrives at the end of Step 2b with more primary covered lines than he had at the end of the preceding application of Step 2. [Since each once-covered zero remains zero after Step 3, one proves easily that those lines which were primary at the end of Step 2b before will be primary lines again. But Step 3 made a zero appear which was not in any primary covered line; this zero causes some previous secondary zero to become primary on the second round.] From this result it follows that our initial assumption that the elements of A were integers is not necessary to the operation of the algorithm. This assumption was used only to show that the algorithm had a finite number of steps. The result just proved shows that after at most n applications of Step 3, the maximal number of zeros in the matrix must be increased. The finiteness of the algorithm follows. We may also use this result to obtain an absolute maximum for the number of operations needed to solve completely any n-by-n assignment problem, using the present algorithm. We assume that variation (2) is incorporated into the algorithm. The operations considered are the following elementary ones: scan a line, cover or uncover a line, add to or subtract from a line, star or unstar a zero, prime or unprime a zero. The maximum is obtained as follows: suppose that we have a matrix with m starred independent zeros. We find a maximum for the number of operations necessary to obtain a matrix with m + 1 starred independent zeros, assuming the worst possible situation. Then Step 2a takes 3m operations.

-69 In Step 2b, one tests and retests the starred zeros a number of times; this takes at most m2 + 3m operations (of which m are "uncover a line," m are "prime a zero," and 2[m(m + 1)/2] are "scan a line"). In the worst case, (II) will not occur and we will apply Step 2d and Step 3. This requires at most 2m + 2n operations, and the number of primary starred zeros will be increased by one in the repetition of Step 2. Hence this process repeats at most m times, after which the maximal number of independent zeros must be at least m + 1. Steps 2a and 2b are applied again, and (II) must occur. This brings us to Step 2c, which requires at most 4m + 1 operations. Then after at most m[(3m) + (m2 + 3m) + (2m + 2n)] + (3m) + (m2 + 3m) + (4m + 1) operations, we obtain a matrix with m + 1 starred independent zeros. We sum this expression from m = 1 to m = n-l, and add the 2n+l operations required initially. The final maximum on the number of operations needed is (n4 + 14n3 - n2 - 2n)/4 This maximum is of theoretical interest, since it is so much smaller than the n! operations necessary in the most straightforward attack on the problem. Needless to say, in usual applications of our method, the number of operations is not nearly of this order of magnitude, especially if one incorporates variations (1) and (3) into his program as well as (2). The Transportation Problem Our algorithm for the assignment problem may be generalized to the transportation problem. The proof of the correctness of the generalized algorithm is much the same as the proof for the special one; we leave its construction to the reader. The transportation problem may be stated as follows: Let D = (dij) be an n-by-m matrix of nonnegative integers, and let rl (i=l,...,n) and cj (j=l,...,m) be positive integers such that Zri = Zcj = N. Determine the values of the variables xij which minimize the sum Zi,j xijdij, subject to the conditions Xij O~ =1 xij = c' and Fj=l j =i 1il xij = rj i

-70 One may think of the following physical situation: There are N ships placed at positions P1,... Pn, and ri denotes the number of ships at position Pi. One wishes to move these ships to new positions Pi',,... P', so that there will be cj ships at position Pj'. The number dij is the cost of moving a ship from position Pi to position P'. The number x stands for the number of ships to be moved from Pi to P.'; it will be called the quota assigned to d... The problem is to choose these quotas so that the total cost of moving the ships is as small as possible. This problem is also called the distribution problem. A statement of the algorithm follows. We work with the cost matrix D = (di.). In the course of the problem, we will distinguish certain lines of the matrix; we call them covered lines, and we will distinguish certain zero elements of the matrix by means of asterisks and primes (as in the algorithm for the assignment problem). In addition, we will assign to each element of the matrix a nonnegative quota xij, which may be changed in the course of the problem. Each element of the matrix whose quota is positive will be called essential. (These elements will always be zeros). At any stage of the problem, the number c - Ei xij will be called the discrepancy of the jth column at that stage, and the number ri - jl xij will be called the discrepancy of the ith row. These discrepancies will always be nonnegative; when all of them vanish, the corresponding quotas are a solution to the problem. Preliminaries. All quotas are zero; no lines are covered; no zeros are starred or primed. Subtract from each row of the matrix D its smallest entry; then subtract from each column of the resulting matrix its smallest entry. Step 1. Erase all asterisks and primes. Cover each row and column (if any) whose discrepancy is zero. Choose a non-covered zero element Z (if any); increase its quota until the discrepancy of either Z's row or column is zero (or both). Cover that line (or lines) whose discrepancy is zero. Repeat, until all zeros are covered. Step 2. Find a twice-covered, essential zero Z and apply the following tests to it: (I) If there is a once-covered zero C in Z's column and no once-covered zero in Z's row, star Z, prime C, and uncover Z's row (leaving C and Z covered). If there is such a once-covered zero which is already primed, let it serve as C rather than prime another once-covered zero.

-71 If there is a once-covered zero R in Z's row and none in Z's column, star Z, prime R, and uncover Z's column (leaving R and Z covered). If there is such an R which is already primed, do not prime another one. (II) If there are once-covered zeros C and R in Z's column and its row, respectively, star Z, and prime C and R. (Again, if there is a zero already primed in the column, let it serve as C. Similarly for R.) Go at once to Step 3. (III) If there is no once-covered zero in Z's row and none in Z's column, do nothing. Repeat these tests for the twice-covered essential zeros, until either test (II) holds, or there are no more twice-covered, essential zeros, or each twice-covered, essential zero has a once-covered zero in neither its row nor its column. In the last two cases, go to Step 4. Step 3. Let CO = Z. Let C1 denote the 0' in C0's column. Let C2 denote the 0* in Cl's row (if any). Repeat, using C2 in place of CO. Continue repeating until the sequence ends at a primed zero C2j+l which has no O* in its row. Let a > 0 denote the discrepancy of the row of C2j+l. (The discrepancy of its column is zero). Let R = O* in Rl's column. until the sequence column. Let P > 0 discrepancy of its primed and starred Z. Let R1 denote the 0' in R0's row. Let R2 denote the Repeat, using R2 in place of Ro. Continue repeating stops at a primed zero R2k+l, which has no 0* in its denote the discrepancy of the column of R2k+l. (The row is zero). We have a sequence of alternating zeros R2k+l, R2k, *., R1, Z, C1,..., C2j, C2j+l. We note that no uncovered line contains more than one 0*, and no covered line contains more than one 0', so that the construction of this sequence is uniquely specified. Let y denote the smallest quota assigned to any quence, and let 8 denote the minimum of a, 3, and y. Add of each O' of the sequence, and subtract 5 from the quota the sequence. Return to the beginning of Step 1. O* of this se5 to the quota of each 0* of Step 4. Find a twice-covered essential zero (if any); uncover its column. Repeat until there are no twice-covered essential zeros left. Let h be the smallest non-covered element of the matrix. Then h > 0. Add h to each covered row and column, and subtract h from the entire matrix. Return to Step 1.

SECTION IV SOLUTION OF ASSIGNMENT AND TRANSPORTATION PROBLEMS ON THE MITAB

SECTION IV SOLUTION OF ASSIGNMENT AND TRANSPORTATION PROBLEMS ON THE MITAB The Mechanical Blackboard We give here only the most elementary introduction to the mechanical blackboard. The face of the mechanical blackboard may seem rather complicated at first; this is due mainly to the extensive duplication of its basic elements. The main body of the mechanical blackboard is made up of 400 cells, arranged in a 20-by-20-square array. Each cell consists of a teleregister, two pilot lights (white and green), and two switches: W G teleregister >0 0 < lights switch - ( switch The lights are controlled by the switch just beneath them. When it is thrown to the left, the left (white) light glows; when it is thrown to the right, the right (green) light glows. When it is in the center position, both lights are off. These lights are turned on and off during the course of the problem; the white light, for example, corresponds to the asterisk we used in our discussion of the assignment problem. A teleregister is an electro-mechanical device which can position a vertically mounted drum in any one of eleven positions. One position is a yellow blank, which represents the number zero. The next nine positions display the numbers 1 to 9. The tenth position, which follows the ninth and precedes the zero, is painted black; it represents the number 10. The teleregister is seen from the front of the machine through a mask, so that one number is displayed at a time. The teleregister drum is electrically positioned. If one applies an electrical pulse to the teleregister, the face of the drum will move one position to the right. This is the equivalent of adding one to the displayed number. Since there are eleven positions, it can be seen that, -75

if we should do this eleven times, the teleregister would be back in the same position. If we should do it only ten times, the number displayed would be decreased by one. From this discussion, it is clear that addition is merely a matter of generating the exact number of electrical pulses one wishes to add and applying them to the teleregister. To subtract some number h, we generate 11 - h pulses and apply them to the teleregister. The teleregister is controlled by the switch just beneath it. When the switch is thrown to the left, the teleregister is connected to the "set-up circuit" of the entire matrix, and pulses which are fed into this circuit will reach the teleregister. When the switch is thrown to the right, the teleregister is connected to the "arithmetic circuit" of the row and column in which it lies. This is the normal position of the switch. In the center position, the teleregister is disconnected from both circuits, and no pulses will reach it. The teleregister is also provided with a "home" position; this is the position in which the zero appears. If one sends pulses to a teleregister which has an open clear circuit, the teleregister drum will rotate until it comes to the zero position and then will stop. The clear circuits are controlled by a switch on the control panel - the second switch from the top in the upper right-hand corner of the face of the mechanical blackboard. When this switch is flipped down, in "clear" position, the clear circuit of every teleregister is open, and no teleregister will cycle past the zero position. When it is flipped up, the teleregisters will cycle past zero just like any other number. Now let us consider the use of the push buttons which appear to the right of, and beneath, the array of teleregister cells. At the bottom of each column, there is a push button. If one pushes one of these buttons, 10 electrical pulses are fed into the "arithmetic circuit" of the column in which it lies. Hence, each teleregister in this column whose switch is to the right will receive 10 pulses, and its displayed number will be decreased by one. For this reason, the button is called a column-subtract button. Just to the right of each row are a pair of push buttons. If one pushes the left button of such a pair, 10 electrical pulses are fed into the arithmetic circuit of the row in which this button lies. Each teleregister in this row whose switch is to the right will receive 10 pulses, and its displayed number will be decreased by one. It is called a row-subtract button. If one pushes the right-hand button of this pair, a single pulse is fed into the arithmetic circuit of that row. Each teleregister in this row whose switch is to the right will receive one pulse, and its displayed number will be increased by one. This button is called a row-add button.

-77 Finally, let us consider the control panel, which is on the right side of the face of the computer. A diagram of it follows; stands for a switch and 0 for a pilot light. Assignment Problem O 0 Transportation Problem O Operate Q) (Clear switch) 0 Clear 0 (Dial) (Battery) 0 (Dial) Set-up switch Add switch (Battery) Telephone Dial O 0 Subtract in progress Ten-pulser reset The switch at the top is the Problem Switch. Its use will be explained later. The second switch controls the clear circuits of all the teleregisters. Its use was already explained. The two switches just below, labelled Set-up and Add, control the set-up circuit and the add operations, respectively. In our solution procedures, the Set-up switch is left in the up position. In this case, when one dials a number on the telephone dial attached to the mechanical blackboard, that number of pulses are fed into the set-up circuit of the matrix, so they will affect each teleregister whose switch is to the

-78 left. This is used in setting up a matrix on the mechanical blackboard. If the Set-up switch should be flipped down, the dial will not feed pulses into the set-up circuit. However, in this case, if one flips a teleregister switch to the left and back again, the teleregister will receive one pulse. In our solution procedure, the Add switch is always down. Possible uses for the up position are given in the Appendix. The pair of lights just beneath the telephone dial have a supervisory function. When a subtract button is pushed, the left light of this pair goes on and stays on until the subtraction is completed. During this time one must be careful not to push another subtract button. When the subtraction is completed, this light goes off and the right-hand light of the pair goes on. At the bottom of the control panel is the power switch, along with four fuses and two pilot lights. The power is on when the switch is flipped up. Finally, stretched across the array vertically and horizontally are 40 metal rods painted different colors on different sides. They may be rotated so that one or another of their colored sides is exposed. This is used during the course of the problem to mark certain rows and columns. A vertical rod belongs to the column of numbers just to the right of it, and a horizontal rod corresponds to the row just beneath it. Instructions for Setting Up a Problem On the Mechanical Blackboard All switches should be in their normal positions as follows: Problem switch to the left (Assignment problem) Clear switch in Operate position Set-up switch up Add switch down Power switch on Each teleregister switch to the right (arithmetic position) Each light switch off (center position) If not all the numbers of the matrix are zero, we first clear them to zero. We do this as follows: Flip the Clear switch to Clear position Push the Subtract button for each row Flip the Clear switch back to Operate position

-79 Then we are ready to set up the matrix. One should limit oneself to matrices containing only numbers between 0 and 9. For an assignment problem, we have just a square matrix of numbers to set up. We insert a number in a teleregister as follows: Flip the teleregister switch to the left Dial the desired number on the telephone dial. (If the desired number is 0, do not dial anything. Dialing 0 would set up the number 10 on the teleregister.) Flip the teleregister switch back to the right This must be done for each element of the matrix. The set-up can be done more rapidly if one person dials the numbers while another flips the switches. If the assignment matrix is smaller than 20-by-20, it will not fill the entire board. It should be set into the upper left-hand corner of the face of the mechanical blackboard, and then it should be "set off" from the remaining part of the face by turning the rods corresponding to the first unused row and the first unused column so that their red sides are exposed. Since only the black and silver sides of the other rods will be used in the problem, these red lines will serve to set off the matrix you will be working with. Incidentally, it is a very good idea to limit oneself to a small matrix, say 10-by-10, until one is thoroughly familiar with the particular solution procedure one is trying to learn. If one wishes to work a transportation problem he has a more complicated set of numbers to enter into the board. One should proceed as follows: First clear all entries to zero. Set the covering rod corresponding to every even-numbered row so that the red side is exposed. Do the same for the rod corresponding to the first column. Subtract one from every even-numbered row, leaving these rows filled with black blanks. Then you are ready to set up the matrix. The numbers ri are entered in the even-numbered rows of the first column; the other elements of the first column should be set to the black blank (by dialing 0). The numbers cj are set into the first row (beginning with the second column), and the cost matrix D = (dij) is set up in the remaining odd-numbered rows (also beginning with the second column). The even-numbered rows will be used to enter the quotas xij in the course of solving the problem. The red lines help to divide up the matrix, grouping neighboring rows together and associating the element dij with its corresponding quota xij just above it. The vertical red line will help to remind one that the first. column is not a part of the cost matrix.

-80 From this discussion, it is clear that the largest transportation matrix which the computer will handle is one of size 9 by 19. If the matrix is smaller than this, the unused rows and columns may be set off by red lines, as in the assignment problem. In solving the transportation problem, one wishes to add to, and subtract from, rows and columns of the cost matrix D only, without affecting the capacities and the quotas. How do we allow for this? This is the function of the Problem Switch at the top of the control panel. After the transportation matrix is set up on the board, this switch is flipped to the right. This automatically cuts off the first row and column and all the even-numbered rows from the arithmetic operations. Then the add and subtract buttons affect only the cost matrix, as is desired. Finally, how does one handle entries of oo in an assignment or transportation problem? In place of oo, enter the number 5 and then disable the teleregister by throwing its switch into the center position. This number will not change, no matter what additions or subtractions are carried out, so that it behaves like oo for all practical purposes. The reason we choose the number 5 rather than some other positive number (which would seem to work as well), will be explained later. Methods for Solving the Problems The covering rods have a black side, a silver-colored side, and a red side. The red side is used only to partition the matrix, or to set off a sub-matrix, as previously explained. The black and silver sides are used to distinguish certain rows and columns in the course of the problem. When the silver side is exposed, the corresponding row or column is said to be covered; when the black side is exposed, it is said to be non-covered. An element of the matrix is said to be covered if it lies in some covered row or column; otherwise it is non-covered. An element of the matrix may have one of the lights next to it turned on. Such elements will always be zeros; we shall speak of green zeros and white zeros, meaning zero elements whose green or white lights, respectively, are lighted. A. The Assignment Problem - First Method This method is an adaptation of one of the author's algorithm for the assignment problem, which appeared in the Journal of the Society for Industrial and Applied Mathematics ().

-81 Preliminaries. All lights should be off, and all rows and columns uncovered. Scan each column for its smallest element, h; if h is positive, subtract h from the column. After doing this for each column, do the same for each row. Step 1. Find a zero Z. If there is no white zero in its row and none in its column, turn on Z's white light. Repeat, until all the zeros in the matrix have been considered. Then cover each column which contains a white zero. Step 2. Find a non-covered zero; turn on its green light. If there is a white zero W in its row, cover W's row and uncover W's column. If there is no white zero in its row, go at once to Step 3. Otherwise, repeat this procedure until all zeros are covered. Then go to Step 4. Step 3. There is a chain of alternating green and white zeros, which may be found as follows: Begin with the uncovered green zero; denote it by Zo. Go to the white zero in its column (if there is any such white zero), denote this white zero by Z1. Go to the green zero Z2 in Z1 s row; then go to the white zero Z3 in Z2's column (if any). Continue until the chain ends at a green zero Z2k which has no white zero in its column. As you follow along this chain, turn off each white light and change each green light to white. If there are now n white lights (where n is the order of the matrix), the problem is solved. [Do not try to follow backward along the chain from its end to its beginning, because the chain may not be unique in this direction. Note also that the chain may contain only one element, that is, it may begin with a green zero which has no white zero in its row and none in its column.] Turn off all green lights, uncover every row, and cover every column which contains a white zero. (Those columns which are already covered will remain covered.) Return to Step 2. Step 4. Find the smallest non-covered entry h of the matrix; it will be greater than zero. Check for possible overflow (see Part B below). Then add h to every covered row, and subtract h from every uncovered column. Return to Step 2, without changing any lights or covering rods.

-82 Any error which is detected immediately can easily be corrected; mistakes in Step 4 must be detected immediately if they are to be corrected, so one should be especially careful to follow instructions in Step 4 exactly. Other mistakes can be handled as follows: Uncover all rows and columns. Turn off all green lights. Check to see that only zeros have white lights on, and that the set of white zeros are independent. (You may have to turn off some white lights). Cover every column containing a white zero, and begin Step 2 again. B. Overflow; Impossible Problems Certain difficulties arise from the fact that each teleregister has a rather small capacity. To allow for this, we will sometimes slip an eraser over the switch beneath a teleregister. This will indicate that 11 should be added to the number appearing on the face of the teleregister to obtain the number which actually belongs in that position of the matrix. Hence, a yellow blank on the teleregister together with an eraser on the switch stand for the number 11 in our matrix. Ordinarily, we should not attempt to solve matrices which contain elements larger than 9. But even with this restriction, elements larger than the capacity of the teleregister may arise in the solution of the problem. The effect of the transformations in Step 4 is to increase each twice-covered element by h and to decrease each non-covered element by h. (A twice-covered element is one whose row and column are both covered.) Hence, some elements may become larger than 10 after Step 4. We check for this as follows: Before carrying out the transformation, check each twice-covered element. If adding h to it will make it bigger than 10, slip an eraser over the switch beneath it. (For example, if h = 1, scan each covered line looking for a black blank which is twice-covered. For each such one you find, slip an eraser over its switch.) Then, if there is any non-covered element with an eraser on its switch, check to see whether subtracting h from the number will make it 10 or smaller; if so, remove the eraser from this switch. After doing this, you have checked for possible overflow, and you may go ahead with Step 4, carrying out the additions and subtractions. If too many elements of the assignment or transportation matrix are infinite, the problem may not have a solution. When this is the case, it may be recognized as follows:

-83 The number oo was entered as 5, and the teleregister was disabled. (Incidentally, the reason for using 5 rather than some other number is to avoid confusion in taking care of overflow.) In the course of solving the problem, one may come to the point where he begins Step 4, and finds that each non-covered entry is 5, and that none of them change when the transformation is carried out. This is precisely what happens when the problem has no solution, i.e., when it is impossible to assign every man to a job for which he is qualified. At this point, we have a "partial assignment" of men to jobs; this assignment is indicated by the white zeros. Suppose there are m of these white zeros. This indicated assignment is optimal in the following sense: m is the maximal number of men which may be assigned to jobs (assuming a man can be assigned only to a job for which he is qualified), and of all the possible admissible assignments of m men to m jobs, this assignment has minimal rating sum. C. The Assignment Problem - Second Method This method is due to H. W. Kuhn (adapted somewhat for our facility.) It differs essentially from the preceding method only in Steps 2 and 3. Preliminaries. Same as before. Step 1. Same as before, except do not cover any columns. Step 2. Uncover every row and column; turn off all green lights (if any). Attempt to construct a chain of alternating green and white zeros. Find the topmost row which contains no white zero; let Zo denote the zero farthest to the left in this row. Turn on Zo's green light. A zero is said to be eligible to be a green zero if there is no green zero already in its column. Let Z1 be the white zero in Zo's column; then find the eligible zero farthest to the left in Zl's row and turn on its green light. Continue similarly. The process will end in one of two ways: If it ends with a green zero which has no white zero in its column, the desired chain has been constructed. Go to Step 3. Otherwise, it ends with a white zero Zi which has no eligible zero left in its row. Cover the column of Zi, go back to the green zero Zi_1 in this column, and turn off its green light. Choose the next eligible zero in the row of this former green zero, turn on its green

light, and continue the chain. If there is no eligible zero left in the row, it means that the chain ends at the white zero in this row, so that this same procedure applies again. It may be that eventually this applies to the first white zero Z1 in the chain, i.e., there is no eligible zero left in Zl's row. Then the preceding paragraph applies again: we cover Zl's column, turn off Zo's green light, choose the next eligible zero in this row as the new Zo, and start the chain again. If there is no eligible zero in this row, we find the next row which contains no white zero and start again. If there is no such row left, there are no chains possible. Then cover the row of every non-covered white zero, and go to Step 4. Step 3. You now have a chain of alternating green and white zeros, which begins and ends with a green zero. Follow along the chain, turning off each white light and changing each green light to white. Return to Step 2. Step 4. Same as before. D. Alternate Solutions One solves the assignment problem by bringing the matrix into a form A' where there are n independent zeros, picked out by means of white lights. These zeros constitute an optimal assignment. One may ask whether there are other assignments which are optimal. Clearly, each choice of n independent zeros of A' defines an optimal assignment; conversely, these are all the optimal assignments. One can investigate the other optimal assignments as follows: Uncover all rows and columns. Turn off all green lights. If any white zero is the only non-covered zero in its row or in its column, the assignment is unique at that point. Cover the row and column of this white zero. Repeat this until every non-covered row and column contains at least two non-covered zeros. If all elements are covered at this point, there is only one optimal assignment. If not, there is at least one other optimal assignment. Proceed as follows, considering only the non-covered elements: Choose a white zero Zl; find an eligible zero Z2 in its row and turn on its green light. Find the white zero in Z2's column and continue the chain. The object is to construct a chain which comes back to Z1 eventually. If you are successful in doing this, the chain will be called a circuit. If one has a circuit, he may turn off all white lights in this circuit and change all the green lights to white, in which case he has an alternate optimal assignment.

-85 Assignment problems O* 3 4 7 4 3 7 3 8 6 9 7 7 4 2* 4 6 7 6 2 1 6 7 6 6 2* 2 7 6 6 1 2* 5 6 8 5 9 9 2 6 5 5 5 9 5 6 3* 5 6 4 1 6 2 2 7 7 9 4 3* 9 8 4 4 2 1 7 5 3 3 1* 6 3 O* 1 6 3 7 8 5 9 3 3 2 1* 1 2 3 4 2 9 5 7 6 0 8 6 3 2* 4 4 Rating sum is 16; assignment is not unique. Time of solution on MITAB is 5 minutes (after problem is set up). 4 o 9 8 6 3 7 1* 6 2 4 2 5 3 3 2 3 7 3 2* 3 2* 9 7 9 7 8 5 3 0 o 0 3 7 2 9 3 1* 5 3 1 6 2 4 oo0* 9 9 1* 7 3 7 9 co 2 3 7 8 7 7 oo 4 7 4* 4 7 6 7 9 8 1 0* 5 oo 7 1 7 5 5 2 4 2 0* 7 4 3 8 4 oo * 7 4 6 0 9 6 2 Rating sum is 12; assignment is unique. Solution time is 5 min. 3 6 9 6 4* 7 3 6 6 1 4 2* 8 1 1 4 5 7 2 0 5 6 5 0* 2 6 7 1 0 7 9 6 9 6 6 8 2 7 3 1* 3 8 5 4 8 2* 4 6 2 2 4 9 5 4 4 3 5 4* 8 2 5 7 2* 4 5 5 0 6 8 8 1 6 9 5 5 5 6 7 1* 9 7 8 6 4 5 6 0* 7 8 2 0* 9 4 7 2 7 9 6 5 4 Rating sum is 16; assignment is unique. 3 3 2 6 1* 6 8 0 4 5 2 7 0 7 3 6 0* 7 5 1 1* 3 5 5 3 8 5 8 5 9 5 7 1 2 1 0 1 4 2 1* 0 6 1* 8 4 4 3 2 5 3 8 7 3 5 2 0* 9 6 4 3 2 1 7 6 3 3 5 0* 2 5 1 2 8 6 7 3 5 8 0* 7 1 5 5 1* 0 0 1 3 4 2 9 0* 5 2 8 4 7 7 2 7 Rating sum is 5; assignment is unique.

7 O* 2 5 6 6 9 94 1 6 0 3 1 1 6 8 3 7 4 5 2 7 4 0* 0 3 2 9 9 1 6 9 1 1 2 3 5 2 3 8 2* 9 1 7 2 1* 8 9 5 7 8 1 5 6 9 3 4 3 0* 7 2 5 2* 3 7 9 6 8 4 9 8 0 8 2 7 9 4 4 1 0 3 1 6 -8612 1 3 4 0 3 3 7 3 5 9 6 8 2 2* 7 7 8 8 4 O* 4 7 2 3 3 2 3 2 4 3 5 O* 2 1 3 7 0 5 5 7 6 5 7 6 5 9 2* 8 6 5 3 4 8 5 2 9 6 1 6 6 3 9 4 2* 4 6 8 4 6 6 5 9 8 3 6 7 5 0 6 O* 6 0 1 6 2 0* 3 3 3 8 6 3 8 4 2 3 3 3 2 7 7 4 9 5 7 9 2* 9 2 8 Rating sum is 13; assignment is unique. 2 0 5 0 9 5 1 4 8 9 3 0 9 7 9 0* 3 2 6 9 6 4 1* 9 5 1 9 7 3 8 8 7 4 5 3 4 8 7 7 7 6 8 6 5 2 O* 1*0 1 1 7 4 2 6 0 1 2 6 1 3 8 9 5 1* 7 5 9 7 1*2 2 5 7 2 1* 6 6 4 3 6 O* 9 4 5 5 9 3 4 1 9 2 * 1 5 3 7 4 0* 4 4 2 2 7 8 6 0 7 1 9 1*3 8 7 2 9 6 5 7 5 9 3 0 7 7 8 4 5 7 8 2 5 3 7 5 9 1 1 2 6 7 1 9 0*0 6 6 0 2 9 4 3 7 3 8 7 9 7 8 4 5 5 0 8 7 7 5 6 6 0 3 9 3 1 6 6 8 0 0 8 4 6 7 3 6 0 3 9 3 7 1 3 4 O* 4 8 1* Rating sum is 7; assignment is unique.

-87 6 6 1 4 6 8 2 0 6 4 0 5 0 7 6 8 2 6 1 4 1 7 9 0* 4 1 6 0 9 1 3 4 8 5 0* 9 8 8 9 0 6 7 9 0 0 5 4 6 1* 9 2 6 9 7 7 1* 9 9 6 5 5 3 2 6 2 3 2 0 2 5 5 0 2 2 7 9 7 5 9 6 4 0 6 7 8 4 4 5 5 1 1 8 7 8 7 3 5 8 9 7 9 3 7 0* 1 0 8 8 8 6 8 5 6 1 6 5 5 2 6 8 7 7 5 8 5 9 2 1 5 2 5 5 5 0* 8 1 3 8 0 5 5 7 7 4 0* 4 3 9 1 3 7 7 8 0 1* 8 2 3 7 0 1 4 6 4 0 5 7 1* 9 5 1 1 7 5 7 3 8 8 0* 5 0 0 3 3 9 6 0* 2 7 5 9 0 9 7 5 1 4 0 1 4 7 9 1 5 0 6 1 5 9 3 60 2 23 5 8 5 1 5 2 3 * 9 9 8 4 2 9 9 8 5 5 4 8 7 6 6 4 7 5 3 5 8 3 7 7 8 8 0* 7 5 8 7 5 9 3 6 2 2 7 1 7 1* 4 1 4 1 5 0 1 9 2 3 5 2 2 3 3 3 9 9 3 1 0* 4 4 9 6 9 6 9 3 1 9 9 7 3 6 8 9 * 9 4 5 8 2 8 4 1 3 7 9 8 8 0* 3 3 0 0 4 3 7 3 8 1 5 3 9 4 4 8 7 3 8 2 9 7 2 2 14 2 2 9 5 7 5 4 2 8 6 9 0 1 9 0*2 2 0 1 3 6 4 5 4 7 0 4 1* 7 2 1 2 9 6 6 8 3 6 9 1 7 9 2 1 4 9 0* 0 3 9 0 0 0 3 0 6 9 0 Rating sum is 6; assignment is not unique. Solution time is 15 minutes.

-88 We shall not state precise procedures for finding all the alternate solutions, for these procedures are rather complicated. Besides, for the relatively small matrices we consider (at most 20-by-20) there are usually so few circuits which can be constructed that all the alternate solutions can easily be found. E. The Transportation Problem We assume the problem is set up as indicated on page 79. Flip the Problem Switch to the right (Transportation Problem). In the course of the problem, the matrix D will be transformed by additions to, and subtractions from, its rows and columns. The quotas xij will be changed individually during the course of the problem. Initially, they are all set at the black blank; in general, when a quota is zero, we will set it at the black blank rather than at the yellow blank. In this way we shall avoid confusing the zeros in the cost matrix with the quotas which are zero. Since we will alter the quotas individually, this will cause no trouble. To change a quota from the black blank to the number 3, for example, one will have to dial 4 rather than 3. Any element of the cost matrix whose associated quota is nonzero will be called an essential element of the cost matrix. (These elements will always be zeros.) The numbers which appear in the first row and column of the mechanical blackboard will also be changed in the course of the problem. Initially, the constants ri and cj are inserted there; as the xij are changed, m ai = ri - j=l ij will replace ri, and n Pj = cj - Zi= xij will replace cj. The notations xai and AB are called the discrepancies of the i row and jth column, respectively. They indicate how much factory capacity and warehouse capacity remain to be assigned. When all the discrepancies are zero, the corresponding xij give a solution to the problem. Preliminary. All lights should be off and no rows and columns covered. We work with the cost matrix D. Scan each column for its smallest entry; if it is positive, subtract it from the column. Then do the same for each row.

-89 Step 1. Scan the columns one by one for zero elements. Suppose you find such a zero Z at position i,j. Let h denote the smaller of ai and Pj. If h > 0, increase Z1s quota by h and decrease ai and Pj by h. [Z's quota is entered in the teleregister just above Z; A. appears at the top of this column and ai appears at the left end of the row in which this quota lies. If Z's quota is originally set at the black blank, flip its switch (the switch just above Z) to the left and dial h+l on the dial; then flip the switch back. To decrease ai and pj, flip their switches to the left and dial 11-h on the dial; then flip the switches back. The ai or pj may be the yellow blank; it is only the quotas xij which we set at the black blank when they are zero.] Repeat this procedure for each zero in the matrix. Then cover every column whose discrepancy Pj is zero. Step 2. Find a non-covered zero; turn on its green light. If the discrepancy ai of its row is positive, go at once to Step 3. If the discrepancy of its row is zero, cover this row; then for each essential twice-covered zero in this row, turn on its white light and uncover its column. (A twice-covered element is one whose column and row are both covered.) Repeat until all zeros are covered. Go to Step 4. Step 3. There is now a unique chain of alternating green and white zeros, beginning at the non-covered green zero, just as in the Assignment Problem. The first green zero of the chain lies in a row having positive discrepancy ai; each white zero of the chain has a positive quota; and the last green zero of the chain lies in a column having positive discrepancy Pj. Let h be the smallest of these numbers. [To find h, follow along the chain and keep track of the smallest of these numbers. Note that you are not concerned with the quotas of the green zeros at the moment.] Decrease ci by h, increase the quota of each green zero of the chain by h, decrease the quota of each white zero of the chain by h, and then decrease Pj by h. [Follow along the chain, changing these numbers as you go. Do not try to read backwards along the chain, for the chain may not be unique in this direction. Note also that the chain may contain only one element.] Turn off all green and white lights, uncover all rows, and cover every column whose discrepancy is zero. Return to Step 2.

-90 Step 4. Find the smallest non-covered entry h of the matrix; it will be positive. Check for overflow (see Part B above). Then add h to every covered row, and subtract h from every uncovered column. Go back to Step 2, without altering any lights or covering rods. One checks for overflow in the same way as one checks it in the assignment problem. In practice, overflow occurs more frequently in the Transportation Problem than in the Assignment Problem. If a problem has no solution, this is detected in the same way as in the assignment problem (see Part B above). If one makes a mistake in Step 4, he must detect and correct it immediately. If one makes a mistake in another step, he should proceed as follows: Turn off all lights; uncover every row and column. Check each row to be sure that the only essential elements are zeros. Check each row to be sure that the sum of the quotas in that row plus the discrepancy of that row equals the original capacity of the row. Do the same for each column. Then cover every column whose discrepancy is zero, and begin Step 2. Finally, how does one find alternate optimal solutions (if such exist)? We suppose the problem has been solved by the previous procedure. Turn off all lights; uncover all rows and columns. Check each row and column; it should contain at least two non-covered zeros, at least one of which is essential. If it does not, cover that row or column. (For in such a case, the choice of quotas for that row or column is unique.) Repeat until every non-covered row and column contains two non-covered zeros, at least one of which is essential. If all elements are covered, the solution is unique. Otherwise, there may be alternate solutions (but we cannot guarantee that there will be, as we could in the assignment problem). They may be found as follows: try to construct a circuit of alternating green and white non-covered zeros (as in the assignment problem), choosing only essential zeros as white zeros. Suppose that you find such a circuit. Let h be the smallest quota associated with a white zero of the circuit. If k is any number such that 0 < k < h, one can obtain an alternate solution by increasing the quota of every green zero in the circuit by k and decreasing the quota of every white zero in the circuit by k. It is usually a fairly complicated procedure to try to find all the optimal solutions.

Transportation problems 9 5 3 3 9 5 2 2 1 1* 8 4 3 7 9 0 6 1 8 6 1 1 3 6 6 7 1 0 0 8 7 6 1 0 7 2 8 5 9 0 7 43 1 1 0 1 5 8 3 8 7 7 3*1 2 1* 5 5 1 9 6 8 9 7 2 2* 5 3 8 1 2 9 1 3 9 4 1 4 5 1 8 6 3 2 6 8 Total cost is 56; assignment is not unique. 9 8 4 4 7 2 8 2 8 2 2* 4 5 4 7 0 1 0 2 3 4 4 2 3 9 8 9 3 3 5 9 5 4 4 8 8 9 6 4 5 8 7 4 2 1* 6 0 7 9 2 4 3 1 5 4* 1* 6 5 0 3 7 3 5 2 5 5* 3 9 3 5 0 1 2 0 6 4 2 9 2 3 3 9 8 7 4 Total cost is 77; assignment is not unique. I!D kO * indicates unique assignment

3 5 5 4 6 3 7 4 3 6 3 2 4 3 6 4 1 3 2 4 7 5 6 3 2 4 5 9 6 5 2 8 7 4 7 3 4 2 2 1 9 1 6 7 8 3* 0 3 9 3 7 8 1 2 3 5 1 7 6 8 6 5 8 4 3 6 2 7 5 9 4 5* 7 7 2 3 0 2 7 1 1* 4 3 6 6 7 1 6 2 3 2 8 2 8 2 6 0 3 3* 2 2 5 3 6 4 3 2 7 6 4 8 5 4 7 6 8 3 5 2 6 0 3* 4 6 2 6 1 7 0 1 2 8 7 1 9 0 4 9 6* 0 9 8 3 9 0 3 7 2 2 9 6 8 9 7 4 7 5 7 6 4* 2 6 7 7 4 6 3 7 3* 6 1 9 3 2 1 9 5 2 9 8 0 4 4 0 5 6 6 5 4 3 9 6 6* 2 0 13 5 3* 2 0 7 6 6 4 1* 2* 0 8 1 6 1 6 9 6 6 6 0 1 4 7 9 479 6 4 1 8 5 4 7 4 1 5 8 2 7 2 8 2 2 1 2* 4 5 2 9 1 3 6 4* 8 0 9 7 7 5 3 1* 8 6 6 3 5 2 5 3* 1* 4 0 7 3 4 1 8 2 3 2 9 9 1 1 2 0 1* 7 9 7 2 7 3 7 5* 1* 2* 0 3 7 8 4 3* 0 9 8 I! I 9 1 5 3 9 2 5 7 0 9 9 9 3 Total cost is 61; assignment is not unique. 7 8 6 2 1 7 8 7 3 1 0 6 5 8 Total cost is 61; assignment is not unique. * indicates unique assignments.

5 3 3 1 5 7 2 2 1 3 6 6 1 3 7 2 2 6 1 8 2* 4 2* 8 8 5 6 5 3 2 7 5 9 3 3 3 5 7 2 6 7 4 5 2 3* 0 9 7 2 9 5 8 4 2 9 4 9 4 1 3 1 0 6 7 6 1* 3* 2* 1 2 9 6 8 8 1 7 3 1 6 5 1 9 6 9 0 3 8 7 6 1* 8 5 9 4 5 7 2 4 1 6 9 2 0 9 8 4 3 8 7 9 1 7 1* 3 8 6 4 4 3 5 9 9 8 9 8 7 7 8 7 6 8 0 9 5* 2 2 5 3 4 4 0 9 4 2 7 2 0 0 4 1 8 6 7 9 7 8 2* 6* 4 0 6 7 6 6 2 6 8 4 5 7 9 9 9 9 9 0 3 9 3 3* 1 2 0 2 1 7 7 9 1 8 0 5 1 2 5 9 5 2 5 7 0 5 5* 9 5 1 7 8 2 0 6 4 2 3 1 5 1 1 0 9 6 4 Total cost is 87; assignment is not unique. * indicates unique assignments.

BIBLIOGRAPHY 1. Ball, W. W. R., Mathematical Recreations and Essays, as revised by H. S. M. Coxeter (llth ed.), pp. 262-266, Macmillan, New York, 1939. 2. Beckmann, M. and Koopmans, T. C., A Note on the Optimal Assignment Problem, Cowles CDP E-2053 (1952). 3. Beckmann, M. and Koopmans, T. C., On Some Assignment Problems, Cowles CDP E-2071 (1952). 4. Brogden, Hubert E., "An Approach to the Problem of Differential Prediction," Psychometrika, 11, 139-154 (1946). 5. Dantzig, G. B., Orden, A., and Wolfe, P., The Generalized Simplex Method of Minimizing a Linear Form Under Linear Inequality Restraints, RAND Corp. RM-1264 (1954). 6. Dantzig, G. B., Fulkerson, R., and Johnson, S., "Solution of a Large-Scale Traveling Salesman Problem," Operations Research, 2, 393-410 (1954). 7. Dantzig, G. B. and Orchard-Hays, W., Alternate Algorithm for the Revised Simplex Method, RAND Corp. RM-1268 (1953). 8.. Dantzig, G. B., Orchard-Hays, W., and Waters, G., Product-Form Tableau for Revised Simplex Method, RAND Corp. RM-1268-A (1954). 9. Dantzig, G. B., Comments on J. von Neumann's "The Problem of Optimal Assignment in a Two-Person Game," RAND Corp. RM-1019 (1952). 10. Dantzig, G. B., Computational Algorithm of the Revised Simplex Method, RAND Corp. RM-1266 (1953). 11. Dantzig, G. B., Upper Bounds, Secondary Constraints, and Block Triangulation in Linear Programming, RAND Corp. RM-1367 (1954). 12. Dantzig, G. B., "Maximization of a Linear Function of Variables Subject to Linear Inequalities," Activity Analysis of Production and Allocation, pp. 339-347, Wiley, New York, 1951. 13. Dantzig, G. B., "Application of the Simplex Method to a Transportation Problem," Activity Analysis of Production and Allocation, pp. 359-373, Wiley, New York, 1951. -95

-96 BIBLIOGRAPHY (Cont' d) 14. Dwyer, P. S., Basic Theory and Methods in Optimal Classification of Personnel, Personnel Research Branch, Department of the Army, 1953. 15. Dwyer, P. S., "Solution of the Personnel Classification Problem with the Method of Optimal Regions," Psychometrika, 19, 11-26 (1954). 16. Dwyer, P. S., The Solution of the Hitchcock Transportation Problem with a Method of Reduced Matrices, University of Michigan, Ann Arbor, December 1955 (hectographed). 17. Easterfield, T. E., "A Combinatorial Algorithm," J. Lond. Math. Soc., 21, 219-226 (1946). 18. Egervary, Jenb, "Matrixok Kombinatorius Tulajdonsagairol," Mat. Fiz. Lapok, 38, 16-28 (1931). Translated by H. W. Kuhn, "On Combinatorial Properties of Matrices," Logistics Papers (George Washington University), Issue 11, Paper 4 (1955). 19. Flood, Merrill M., "The Traveling-Salesman Problem," Operations Research for Management II, pp. 340-357, The Johns Hopkins Press, Baltimore, 1956. 20. Flood, Merrill M., "On the Hitchcock Distribution Problem," Pacific J. Math., 3, 369-386 (1953). 21. Flood, Merrill M., "Application of Transportation Theory to Scheduling a Military Tanker Fleet," Operations Research, 2, 150-162 (1954). 22. Flood, Merrill M., "On the Hitchcock Distribution Problem,"' Symposium on Linear Inequalities and Programming (Project SCOOP, 10), 74-99, (1952). 23. Ford, L. R. and Fulkerson, D. R., A Simple Algorithm for Finding Maximal Network Flows and An Application to the Hitchcock Problem, RAND Corp. RM-1604 (1955). 24. De Francesco, H. F., "The Optimal Assignment Problem," SCAMP Notes, Conf. 10, 1-13 (1953). 25. Frobenius, G., "Uber zerlagbare Determinanten," Preuss, Akad. Wiss., Sitzungsber., 274-277, (1917). 26. Gleyzal, A. N., "An Algorithm for Solving the Transportation Problem," J. Res. Nat. Bur. Stand., 54, 213-216 (1955).

-97 BIBLIOGRAPHY (Cont' d) 27. Heller, I., "On the Problem of Shortest Path Between Points," (Abstract), Bull. Am. Math. Soc., 59, 551 (1953). 28. Heller, I., The Traveling-Salesman's Problem, Part I: Basic Facts, The George Washington University Logistics Research Project, June 1954. 29. Hitchcock, Frank L., "The Distribution of a Product from Several Sources to Numerous Localities," J. Math. Phys., 20, 224-230 (1941). 30. Houthakker, H. S., "On the Numerical Solution of the Transportation Problem," Operations Research, 3, 210-214 (1955). 31. Kantorovitch, L., "On the Translocation of Masses," Doklady Akad. Nauk, SSSR, 37, 199-201 (1942). 32. Kbnig, D., Theorie der Graphen, Chelsea, New York, 1950. 33. K~nig, D., "Uber Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre," Math. Ann, 77, 453-465 (1916). 34. Koopmans, Tjalling C., "Optimum Utilization of the Transportation System," Econometrica, 17, Supplement, 136-146 (1949). 35. Koopmans, Tjalling C. and Reiter, Stanley, "A Model of Transportation," Activity Analysis of Production and Allocation, 222-259, Wiley, New York, 1951. 36. Kuhn, H. W., The Traveling-Salesman Problem, Manuscript (1953). 37. Kuhn, H. W., "The Hungarian Method for the Assignment Problem," Naval Research Logistics Quarterly, 2, 83-97 (1955). 38. Lord, Frederick M., "Notes on a Problem of Multiple Classification," Psychometrika, 17, 297-304 (1952). 39. Machol, Robert E., "The Mechanical Blackboard," Operations Research, 5, 422-428 (1957). 40. Motzkin, T. S., Basic Solutions of the Transportation Problem, Manuscript (1952). 41. Motzkin, T. S., "New Techniques for Linear Inequalities and Programming," Symposium on Linear Inequalities and Programming, (Project SCOOP, 10), 15-27 (1952).

-98 BIBLIOGRAPHY (Cont'd) 42. Motzkin, T. S., "The Multi-Index Transportation Problem," (Abstract), Bull. Amer. Math. Soc., 58, 494 (1952). 43. Motzkin, T. S., "The Assignment Problem," Proceedings of the Sixth Applied Mathematics Symposium, 109-125, McGraw-Hill, New York, 1955. 44. Munkres, James, "Algorithms for the Assignment and Transportation Problems," J. Soc. Ind. and App. Math., 5, 32-38 (1957). 45. Neumann, J. von, "A certain Zero-Sum Two-Person Game Equivalent to the Optimal Assignment Problem," Contributions to the Theory of Games II, 5-12, Princeton Univ. Press, Princeton, 1953. 46. Orden, A., "The Transhipment Problem," Management Science, 2, 276-285 (1956). 47. Orden, A., A Procedure for Handling Degeneracy in the Transportation Problem, U. S. Air Force, Unpublished (1951). 48. Rao, C. R., Advanced Statistical Methods in Biometric Research, Wiley, New York, 1952. 49. Robacker, J. T., Some Experiments on the Traveling Salesman Problem, RAND Corp. RM-1521 (1955). 50. Robinson, Julia, On the Hamiltonian Game (A Traveling-Salesman Problem), RAND Corp. RM-303 (1949). 51. Robinson, Julia, A Note on the Hitchcock-Koopmans Problem, RAND Corp. RM-407 (1950). 52. Smith, Robert B., Hand Computational Methods for the Classification Problem, Air Training Command, Human Resources Research Center, September 1951. 53. Thorndike, Robert L., "The Problem of Classification of Personnel," Psychometrika, 15, 215-235 (1950). 54. Tornqvist, L., How to Find Optimal Admissible Summation Ways, Cowles CDP M-422 (1953). 55. Tornqvist, L., How to Find Optimal Solutions to Assignment Problems, Cowles CDP M-424 (1953).

-99 BIBLIOGRAPHY (Cont' d) 56. Tutte, W. T., "On Hamiltonian Circuits," Lond. Math. Soc. J., 21, Part 2, No. 82, 98-101 (April 1946). 57. Verblunsky, S., "On the Shortest Path Through a Number of Points," Proc. Am. Math. Soc., 2, 904 (1951). 58. Vidale, M. L., "A Graphical Solution of the Transportation Problem," Operations Research, 4, 193-203 (1956). 59. Votaw, D. F. and Dailey, J. T., Assignment of Personnel to Jobs, Air Training Command, Human Resources Research Center, Research Bulletin 52-24 (1952). 60. Votaw Jr., D. F., "Methods of Solving Some Personnel-Classification Problems," Psychometrika, 17, 255-266 (1952). 61. Votaw, D. F. and Orden, A., "The Personnel Assignment Problem," Symposium on Linear Inequalities and Programming, (Project SCOOP, 10), 155-163 (1952).

APPENDIX SUGGESTIONS FOR PROGRAMMING AN ALGORITHM FOR THE TRANSPORTATION PROBLEM FOR A HIGH-SPEED DIGITAL COMPUTER The transportation problem is the following: Given an n-by-m matrix D = (dij) and positive integers ri (i=l,...,n) and cj (j=l,...,m) such that Zi ri = -j cj = N, choose values of the variables xij which minimize the form Zi, x idij subject to the following conditions: ij ij ii n m xij > 0, Xij = cj, and Z xi = r. i=l j=l There are a number of methods for attacking this problem. One which is especially adapted to solving such problems by hand has been given by one of the authors. This method may also be adapted to a high-speed digital computer. An adaptation of this method which is thought to be suitable for programming on such a computer is presented herewith. Included are flow diagrams for the programming of the method. A column may be covered or non-covered; a row may be uncovered, covered, or well-covered. Certain entries of the matrix will be distinguished by means of asterisks and primes. The number xij will stand for the number of units assigned "to be shipped" from i to j; it is called the quota assigned to dij. The numbers ai = ri - Z1 xij and. = c - xi; are called the discrepancies of the ith row and the jh column, respectively; when they vanish, the problem will be solved. Preliminaries. Subtract its smallest element from each column of D; then subtract its smallest element from each row of the resulting matrix. Step 1. Find a 0 in the matrix at position i,j. Increase the quota xij by the smaller of the two numbers al and Pj. Repeat for each 0 in the matrix. Step 2. Cover each row and column whose discrepancy is zero, and only those. If the discrepancy of every row is 0, go to Step 7. Step 3. Test each uncovered column as follows, and continue until there are no uncovered, untested columns remaining: (I) If Z's row is well-covered, do nothing. -101

-102 (II) If Z's row is covered, prime Z, "well-cover" Z's row, and consider the well-covered zeros in this row (if any). For each such zero whose quota is positive, star this zero and uncover its column. (III) If Z's row is non-covered, prime Z and go at once to Step 4. If alternative (III) does not occur at any time, go to Step 5. Step 4. You have just primed a non-covered zero Z at position pl,q1. Find the starred zero in Z's column, then find the primed zero in this starred zero's row. Let this new primed zero's indices be P2q2. Repeat until you finally obtain a primed zero at Pk,qk which has no starred zero in its column. Let h be the smallest of the numbers ap, Pqk' and Xpi+lqi (i=l,...,k-l). (The numbers Xpi+lqi are the quotas assigned to the starred zeros of the sequence). Add h to the quota of each 0' of the sequence, and subtract h from the quota of each 0* of the sequence. Go to Step 6. Step 5. Uncover each covered row (but not the well-covered rows). Let h be the smallest non-covered entry of the matrix. Add h to each well-covered row, and subtract h from each uncovered column. Go to Step 3. (Each uncovered column becomes an untested column now.) Step 6. Erase all asterisks and primes. Go to Step 2. Step 7. This step is necessary only if you wish to regain the original matrix. Let ui be the total amount subtracted from the ith row; let vj be the total amount subtracted from the jth column (since the beginning of the problem). Add ui to each row; add vj to each column. The xij are a solution to the problem, and the original matrix dij is back again. The original capacity ri is merely.j xij, and cj is Zi Xij. One needs the following storage positions in the memory of the computer: xij, Yij, zij, ai, pj, yi, 6j, ui, vj (i=l,...,n; j=l,...,m). Initially, the numbers di are read into positions zij, the numbers ri into positions ai, and t numbers c1 into positions 3j. The other numbers are set equal to zero. The meanings of the new symbols are as follows: zij is the cost matrix, modified by the additions and subtractions from revs and columns.

-103 The number yij has the meaning: if Yij = 1, the element zij is primed; = 2, the element z.j is starred. The number yi has the meaning: if i = 0, row i is uncovered, = 1, row i is covered, = 2, row i is well-covered. The number 5j has the meaning: if 6 = 0, column j is uncovered and untested, = 1, column j is uncovered and tested, = 2, column j is covered. Flow diagrams, showing the connections between the various steps, follow:

At the end of Step 7, the original matrix is back in the positions Zi, and the original capacities are back in positions ai and pj. If this is not desired, Step 7 may be omitted.

-105 PRELIMINARIES

-106 STEP 1. Yes

-107STEP 2.

STEP 3.

-109 STEP 4.

-110 STEP 5.

-111 STEP 6. STEP 7.

UNIVERSITY OF MICHIGAN II3 9011111 0367 72ll 3 9015 03627 7229