v9 2. Simplex Method 3. Transportation Method and 4. Hungarian Method Hungarian Method: The following are the steps involved in the minimization of an assignment problem under this method: Step 1: Row Operation Locate the smallest cost element in each row of the given cost table. Now subtract this smallest element from each element in that row. As a result, there shall be at least one zero in each row of this new table, called the reduced cost table. Step 2: Column Operation In the reduced cost table obtained, consider each column and locate the smallest element in it. Subtract the smallest value from every entry in the column. As a consequence of this action, there would be at least one zero in each of the rows and columns of the second reduced cost table. Step 3: Optimality Draw the minimum no. of horizontal and vertical lines (not the diagonal ones) that are required to cover all the zero elements. If the no. of lines drawn is equal to 'n' (the no. of rows/columns of the given Cost Matrix) the solution is optimal and proceed to step 6. If the no. of lines drawn is smaller than 'n' go to step 4. Step 4: Improved Matrix Select the smallest uncovered by the lines) cost element. Subtract this element from all uncovered elements including itself and add this element to each value located at the intersection of any two lines. The cost elements through which only one line passes remain unaltered. Step 5: Repeat step 3 and 4 until an optimal solution is obtained. Step 6: Given the optimal solution, make the job assignments as indicated by the 'zero' elements. This is done as follows: (a) Locate a row which contains only one zero element. Assign the job corresponding to this element to its corresponding person. Cross out the zero's if any in the column corresponding to the element, which is indicative of the fact that the particular job and person are no more available. (b) Repeat (a) for each of such rows which contain only one zero. Similarly, perform the same operation in respect of each column containing only one 'zero' element, crossing out the zero(s), if any, in the row in which the elements lies. (c) If there is no row or column with only a single 'zero' element left, then select a row/column arbitrarily and choose one of the jobs (or persons) and make the assignment. Thus in such a case, alternative solutions exist. Illustration 1. Six men are available for different jobs. From past records the time in hours taken by different persons for different jobs are given below. Jobs 1 4 5 1 2 7 9 6 2 9 8 6 2 6 14 2 3 4 Men 4 4 3 2 7 5 7 9 12 3 3 8 10 6 1 1 1 1 1 1 5 5 9 3 8 5 13 12 9 6 Find out an allocation of men to different jobs which will lead to minimum operation time