Learning Curve…

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 on: October 20, 2011

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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Author

Learning days (Calendar)

October 2011
M T W T F S S
« Sep   Nov »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

Knowledge Bank (Archives)

I am on Twitter

Error: Twitter did not respond. Please wait a few minutes and refresh this page.

Blog Stats

  • 510,129 hits

Enter your email address to subscribe to this blog and receive notifications of new posts by email.

Join 43 other followers

%d bloggers like this: