Scribd
Upload
27 views5 pages

Assignment Problem Solutions Overview

The document discusses different methods for solving assignment problems, which involve assigning machines to mechanics to minimize total time and cost. It focuses on explaining the Hungarian method, which is the most popular approach. The Hungarian method involves developing a cost table, subtracting minimum costs from rows and columns, using lines to cover zeros to test for optimality, and repeating the process until an optimal assignment can be made by examining single zeros. It also addresses extensions like maximization problems, unbalanced assignments using dummy values, and prohibiting impossible assignments using infinite costs.

Uploaded by

parul
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
27 views5 pages

Assignment Problem Solutions Overview

The document discusses different methods for solving assignment problems, which involve assigning machines to mechanics to minimize total time and cost. It focuses on explaining the Hungarian method, which is the most popular approach. The Hungarian method involves developing a cost table, subtracting minimum costs from rows and columns, using lines to cover zeros to test for optimality, and repeating the process until an optimal assignment can be made by examining single zeros. It also addresses extensions like maximization problems, unbalanced assignments using dummy values, and prohibiting impossible assignments using infinite costs.

Uploaded by

parul
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Assignment Problems

Assignment problem is a special case of general linear programming problem,


just as the transportation problem. For example a departmental head may have
four machines to be assigned to different mechanics (which differ in efficiency
while working on different machines) available for assignment. He is willing to
know that which machine should be assigned to which mechanic so that total
work can be completed in minimum time and minimum cost.

Solution methods of an Assignment Problem

ENUMERATIVE SIMPLEX METHOD TRANSPORTATION METHOD HUNGARIAN METHOD


METHOD

Most preferred and popular


method.

Structure

 The Hungarian Method(Minimization)


 Maximizing Case
 Unbalanced Assignment Problems
 Prohibited Routes(A Problem with Impossible Assignments)
1 Page
The Hungarian Method (Minimization)

Step 1. Develop the cost table for the given problem.

Step 2. If the no. of rows is not equal to no. of columns or vice-versa, dummy
rows or dummy columns must be added. The assignment cost of dummy rows
or columns is always zero.

Step 3. Select smallest element from each row and subtract it from each
element of corresponding row.

Repeat step 3 for each column.

Step 4. Optimality test: - to check the optimality of given cost matrix draw
minimum number of straight lines to cover all the zeros.

Step 5.
No. of covering lines = No. of rows (or columns)

Optimum assignment can be obtained.

If number of straight lines drawn is exactly equal to the number of rows(or


columns) in the matrix, an optimal assignment can be obtained.

If the no of covering lines is less than no of rows (or columns) optimal


assignment cannot be made. In such cases, least element out of uncovered
elements is to be subtracted from the uncovered elements and added to the
elements which are at intersection. And all the entries covered by one straight
line remain unchanged.

Step [Link] step 4 and step 5 until no of covering lines become equal to no
of rows or no of columns.

Step7. If No. of covering lines = No. of rows (or columns) assignment can be
made by following procedure-

Examine those rows which have exactly single zero and make assignment( )
around it and cross all other zeros of corresponding column.

Examine row having a single unmarked zero, make assignment ( ) around it


and cross all other zeros of corresponding column.
2
Page

After rows repeat the same steps for columns.


Maximizing Case

To transform maximizing problem into minimizing problem, we subtract all the


entries of the original matrix from the maximum entry of that matrix.

Maximization problem Minimization Problem

(Pay-off Matrix) (Loss Matrix)

Maximum element – each element

Unbalanced Assignment Problem

Balanced No of persons (no of rows) = No of jobs (no of columns)


Assignment
Problem

Unbalanced
Assignment
No of persons ≠No of job
problem
3
Page
For solving the problem, unbalanced assignment problem should be converted
into balanced one with the help of dummy jobs or dummy persons.

Convert
With the help of ‘dummy rows’ or
‘dummy columns’.

Unbalanced Balanced

Further procedure would be the same.

Prohibited Routes ( a problem with impossible assignments)-

In some cases a certain worker cannot be assigned a particular job. The


reasons for impossible assignments are numerous. Lack of required skills,
deficiency in technical know-how improper training and physical inability are
only a few among many reasons. For solving such type of assignment problems
we put infinite cost (∞) in the cell where no assignment is possible. The
remaining procedure is exactly the same as the ordinary assignment problem.

4 Page
Page 5

You might also like