USA: +1-585-535-1023

UK: +44-208-133-5697

AUS: +61-280-07-5697

Solution of Assignment Problems

1. Complete Enumeration Method

In this method costs for all possible assignments are worked out and the one having the minimum cost is termed as the optimal solution. This method, for obvious reasons, can only be used for small problems. As the problems become complex, it is impractical to workout a very large number of alternatives and then pick up the optimal solution.

2. Simplex Method

In this method the simplex algorithm is used and we 

subject to constraints

(i) xij+xi2+ …. +xin=1                   i=1,2, …. n

(ii) xij+x2j+ …. +xnj=1                   j=1,2, …. n

(iii) xij= 0 or 1 for all values of i and j.

It can be seen there are n × n decision variables and n + n = 2n equalities. It means that for a problem involving 8 workers/jobs there will be 64 decision variables and 16 equalities to be solved. If is an extremely cumbersome method.

3. Transportation Method

We have earlier mentioned that assignment model is a special case of transportation model so it should be possible to solve it by transportation method. However, we know that optimality test in the transportation

Method requires that there should be n + n – 1 = 2n – I basic variables, the solution obtained by this method would be severaly degenerate. For an assignment made there would be only n basic variable in the solution, hence to proceed for solving an assignment model by using transportation model, a very large number of dummy allocations will have to be made, which will make this method very inefficient to compute.

4. Hungarian Assignment Method or HAM (Minimisation case). This method was developed by Hungarian mathematician D Koning and is also known as the Flood’s Technique or the reduced matrix method. It is a Simpler and more efficient method of solving the assignment problems. The following steps are involved while using the Hungarian method.

Step I. Formulate the opportunity cost table by the following method.

  1. Subtract the smallest number in each row of the original cost matrix from every number in that
  2. Subtract the smallest number in each column of the table obtained at (a) above from every number ill that column.

Step II. Make assignments in the following manner.

a)     Examine all the rows looking for a row with exactly one unmarked zero in a square (⎕) as assignment has to made there. Cross (×) all other zeros in the column as these will not get an assignment ill future. Proceed in this manner for all the rows.

b)    Now examine all the columns one by one until we find a column with exactly one marked zero is located. Make an assignment to this single zero and put a square (⎕) around it. Also crossout (×) all other zeroes appearing in the corresponding row as no assignment will be made in that row. Proceed in this
manner for all the columns.

c)     Operations (a) and (b) are repeated till.

(i)                           All the zeros in rows/columns are either put in the square (⎕) or are crossed out (×) and exactly one assignment is in each row and in each column. This is the optimal solution.

(ii)                        Some row or column may be left without assignment, if so proceed to step IV.

Step III. Revise the opportunity cost matrix by

i.      Marking (√) all rows that have no assignment.
ii.      Marking (√) all columns which have zeros but have not been marked earlier.
iii.      Marking (√) all rows that have assignments and have not been marked earlier.
iv.      Repeat step III (i) and (ii) until no more rows and columns can be marked.
v.      Draw straight lines through each unmarked row and each marked column.

Now check the total assignments indicated by number of lines drawn is equal to the number of rows or columns, the optimal solution has been reached. Otherwise proceed to step IV.

Step IV. Write the new revised opportunity cost matrix.

Initial opportunity cost matrix may never give the optimal solution, we are normally required to revise this table in order to move one or more zero costs from present location to new uncovered locations. This is done by subtracting the smallest number not covered by a line from all numbers not covered by a straight line. This number (smallest) is added to every number, including zeros available at the intersection of any two lines.

Step V. Repeat steps II to IV until an optimal solution is achieved.

The above steps are shown in the form of a flow chart in the foilPRACTICAL STEPS INVOLVED IN SOLVING MINIMISATION MAXIMISATION