# How to solve Assignment Problems?

ASSIGNMENT PROBLEMS

Introduction: An Assignment problem involves assignment or matching of two things. E. g. matching of workers and jobs or matching of salesmen and areas etc.

The basic principle in Assignment problem is that the matching is on a one to one basis.

i. e. One worker can do only one job or one salesman can operate in only one area.

The method used for solving Assignment problem is called “Hungarian method”.

Concepts:

1. The Assignment problem can be Balanced or Unbalanced problem.

A Balanced problem means the no. of rows and no. of columns in the problem are equal. E. g. if the problem contains 4 workers and 4 jobs, then it is balanced.

Where as, an Unbalanced problem means the no. of rows and no. of columns are not equal. E. g. if the problem contains 4 workers and 3 jobs it is not balanced. Then first we need to balance the problem by taking a Dummy job (imaginary job).

2. Dummy: A Dummy is an imaginary entity. The purpose of Dummy is to balance the problem. Since the Dummy is imaginary, all values for Dummy are always zero. Dummy can come as row or column, depending on problem.

3. The Assignment problem can be of Minimization type or Maximization type.

A Minimization Assignment problem involves cost, time or distance data. The objective of solution is to minimize the final answer.

A Maximization Assignment problem involves sales, revenue or profit data. The objective of solution is maximization of the final answer. We need to first convert the Maximization problem in Minimization problem. This conversion is called Regret matrix.  From the original profit values, we find out the highest profit value. From this highest profit, we subtract all profit values. The resulting matrix is Regret matrix.

4. Prohibited or Restricted problem: A Prohibited problem is the one in which there are one or more restrictions. E. g. say there are 4 contractors – C1, C2, C3 & C4. And there are 4 roads to be repaired – R1, R2, R3 & R4. But contractor C2 cannot or is not allowed to work on R3. This is a prohibited problem

Then we assign a very high or infinite value (represented by M) to C2-R3 and proceed with solution. Throughout the solution steps, M does not change. Since M is infinity, no assignment is possible in M.

————————————————————————————————————————–

Steps –

1. Take Dummy (if required) & then convert in Regret matrix (if required)
2. Do Row minimization and Column minimization.
3. Cover all Zeroes in the Table with Minimum possible lines. (Start from maximum zeroes, either row-wise or column-wise).
4. If optimal, find assignment.
5. If not optimal, write next table, change values & check again with Minimum possible lines.
6. Continue the iterations till optimal solution is reached.
The following two tabs change content below.

#### Score Tutorial

S’COrE Education is a professional coaching institute to coach for new generation courses. S’COrE has highly experienced faculty with enormous experience and achievement in teaching and industry. We teach each subject in such a manner that even complicated subject feels simple. This helps student to S’COrE-the-Max. Since 1998 S’COrE had university toppers accross courses and subjects. Once you are our student you will also believe S’COrE - the - Best !!

## One Comment

Choose A Format
Personality quiz
Series of questions that intends to reveal something about the personality
Trivia quiz
Series of questions with right and wrong answers that intends to check knowledge
Poll
Voting to make decisions or determine opinions
Story
Formatted Text with Embeds and Visuals
List
The Classic Internet Listicles
Countdown
The Classic Internet Countdowns
Open List
Submit your own item and vote up for the best submission
Ranked List
Upvote or downvote to decide the best list item
Meme
Upload your own images to make custom memes
Video
Youtube, Vimeo or Vine Embeds
Audio
Soundcloud or Mixcloud Embeds
Image
Photo or GIF
Gif
GIF format