Hungarian Method of Assignment Problem minimization case

An efficient method for solving an assignment problem known as Hungarian of assignment is based upon the following two important properties;

1.      In an assignment problem if a constant quantity is added or subtracted from every element of any row or column in the given cost matrix an assignment minimizes the total cost in one matrix also minimizes the total cost in the other.

2.      In an assignment problem, a solution having zero total cost is an optimum solution.

Hungarian method of assignment problem (minimization case) can be summarised in the following steps:

Step 1. In the given matrix subtract the smallest element in each row from every element of that row.

Step 2. In the reduced matrix obtained from step 1. Subtract the smallest element in each column from every element of that column.

Step 3. Make the assignment for the reduced matrix obtained from step 1 and 2 in the following way:

(a)    Examine the rows successively until a row with exactly one unmarked zero is found. Enclose this zero in a box as an assignment will be made there and cross (x) all other zeros appearing in the corresponding column as they will not be considered for future assignment. Proceed in this way until all the rows have been examined.

(b)   After examining all the rows completely examine the columns successively until a column with exactly one unmarked zero is found. Make as assignment to this single zero by putting square around it and cross out (x) all other zeros appearing in the corresponding row proceed in this manner until all columns have been examined.

(c)    Repeat the operatins (a) and (b) successively until one of the following situations arises:

(i)                 All zeros in rows/columns are either marked or crossed (x) and there is exactly one assignment in each row and in each column. In such a case optimum assignment policy for the given problem is obtained.

(ii)               There may be some row (or column) without assignment, i.e., the total number of marked zeros is less than the order the matrix. In such a case proceed to nest step 4.

Step 4. Draw the minimum number of vertical horizontal lines necessary to cover all the zeros in the reduced matrix obtained from step 3 by adopting the following procedure.

(i)                 Mark (√) all rows that do not have assignments.

(ii)               Mark (√) all columns (not already marked) which have zeros in the marked rows [step 4 (ii)]

(iii)             Mark (√) all rows (not already marked) that have assignment in marked columns [step4(iii)]

(iv)             Repeat step 4 (ii) and (iii) until no more rows or columns can be marked.

(v)               Draw straight lines through all unmarked rows and marked columns.

It may be pointed out here that one may also draw the minimum of lines to cover all zeros by inspection.

Step 5. If the number of lines drawn [step 4 (iii)] are equal to the number of rows or columns then it is an optimum solution otherwise go to step 6.

Step 6. Select the smallest element among all the uncovered elements, subtract this smallest element form all the uncovered elements and add it to the element lies at the intersection of two lines. Thus, we obtain another reduced matrix for fresh assignments.

Step 7. Go to step 3 and repeat the procedure until the number of assignments become equal to the number of rows or columns. In such a case we shall observe that row/column has an assignment. Thus, the current solution is an optimum solution.

ExpertsMind.com - Hungarian Method Assignment Help, Hungarian Method Homework Help, Hungarian Method Assignment Tutors, Hungarian Method Solutions, Hungarian Method Answers, Assignment Problems Assignment Tutors