# MB0048 : State and discuss the methods for solving an assignment problem. How is Hungarian method better than other methods for solving an assignment problem?

Posted October 20, 2011

on:**MB0048 :State and discuss the methods for solving an assignment problem. How is Hungarian method better than other methods for solving an assignment problem?**

**Answer** : Assignment becomes a problem because each job requires different skills and the capacity or efficiency of each person with respect to these jobs can be different. This gives rise to cost differences. If each person is able to do all jobs with same efficiency then all costs will be the same and each job can be assigned to any person. When assignment is a problem it becomes a typical optimisation problem. Therefore, you can compare an assignment problem to a transportation problem.

** **

**Solution Methods **

The assignment problem can be solved by the following four methods :

- Enumeration method
- Simplex method
- Transportation method
- Hungarian method

**Enumeration method: **

In this method, a list of all possible assignments among the given resources and activities is prepared. Then an assignment involving the minimum cost, time or distance or maximum profits is selected. If two or more assignments have the same minimum cost, time or distance, the problem has multiple optimal solutions. This method can be used only if the number of assignments is less. It becomes unsuitable for manual calculations if number of assignments is large

**Simplex method: **

The simplex method focuses on solving LPP of any enormity involving two or more decision variables.

The simplex algorithm is an iterative procedure for finding the optimal solution to a linear programming problem. The objective function controls the development and evaluation of each feasible solution to the problem. If a feasible solution exists, it is located at a corner point of the feasible region determined by the constraints of the system.

The simplex method simply selects the optimal solution amongst the set of feasible solutions of the problem. The efficiency of this algorithm is because it considers only those feasible solutions which are provided by the corner points, and that too not all of them. You can consider obtaining an optimal solution based on a minimum number of feasible solutions.

** **

**Transportation method **

Transportation model is an important class of linear programs. For a given supply at each source and a given demand at each destination, the model studies the minimisation of the cost of transporting a commodity from a number of sources to several destinations.

As assignment is a special case of transportation problem it can also be solved using transportation model. But the degeneracy problem of solution makes the transportation method computationally inefficient for solving the assignment problem.

**Hungarian method **

There are various ways to solve assignment problems. Certainly it can be formulated as a linear program (as we saw above), and the simplex method can be used to solve it. In addition, since it can be formulated as a network problem, the network simplex method may solve it quickly.

However, sometimes the simplex method is inefficient for assignment problems (particularly problems with a high degree of degeneracy). The Hungarian Algorithm developed by Kuhn has been used with a good deal of success on these problems and is summarized as follows.

**Step 1. **Determine the cost table from the given problem.

- If the no. of sources is equal to no. of destinations, go to step 3.
- If the no. of sources is not equal to the no. of destination, go to step2.

**Step 2. **Add a dummy source or dummy destination, so that the cost table becomes a square matrix. The cost entries of the dummy source/destinations are always zero.

**Step 3. **Locate the smallest element in each row of the given cost matrix and then subtract the same from each element of the row.

**Step 4. **In the reduced matrix obtained in the step 3, locate the smallest element of each column and then subtract the same from each element of that column. Each column and row now have at least one zero.

**Step 5. **In the modified matrix obtained in the step 4, search for the optimal assignment as follows:

(a) Examine the rows successively until a row with a single zero is found. Enrectangle this row ()and cross off (X) all other zeros in its column. Continue in this manner until all the rows have been taken care of.

(b) Repeat the procedure for each column of the reduced matrix.

(c) If a row and/or column has two or more zeros and one cannot be chosen by inspection then assign arbitrary any one of these zeros and cross off all other zeros of that row / column.

(d) Repeat (a) through (c) above successively until the chain of assigning () or cross (X) ends.

**Step 6**. If the number of assignment () is equal to n (the order of the cost matrix), an optimum solution is reached.

If the number of assignment is less than n(the order of the matrix), go to the next step.

**Step7. **Draw the **minimum number **of horizontal and/or vertical lines to cover all the zeros of the reduced matrix.

**Step 8. **Develop the new revised cost matrix as follows:

(a)Find the smallest element of the reduced matrix not covered by any of the lines.

(b)Subtract this element from all uncovered elements and add the same to all the elements laying at the intersection of any two lines.

**Step 9. **Go to step 6 and repeat the procedure until an optimum solution is attained.

## Leave a Reply