Assignment Problem - Hungarian Method

What is an Assignment Problem?

• A problem to assign time slots to lectures

• A problem to allocate limited resources over unlimited tasks

• A special type of Linear Programming Problem used to assign jobs to resources at minimum cost

• A method to maximize production using available labour

The objective of the Assignment Problem is

• To assign jobs at maximum cost

• To assign jobs only to minimize cost

• To eliminate all cost

• To assign jobs to persons at minimum cost

The Assignment Problem is solved by

• Simplex method

• Hungarian method

• Vector method

• Graphical method

For solving an assignment problem, the matrix must be a

• Singular matrix

• Unit matrix

• Triangular matrix

• Square matrix

The Assignment Problem is said to be balanced when

• Number of rows = Number of columns

• Number of rows is greater than number of columns

• Number of rows is less than number of columns

• Entry of a row is zero

The Assignment Problem is said to be unbalanced when

• Number of rows is greater than number of columns

• Number of rows is less than number of columns

• Both (a) and (b)

• Number of rows = Number of columns

The Hungarian method operates on

• Cost maximization

• Substitution method

• Graphical approach

• Matrix reduction

In Hungarian method, optimal assignment is made

• On the diagonal elements

• To the cells containing zero

• To the first row elements

• To the cell with the least cost

In the Hungarian method, optimal solution is found when

• Matrix becomes a zero matrix

• Maximum number of zeros are assigned

• Minimum number of lines to cover all zeros equals the order of matrix

• All rows contain one zero

Using Hungarian method the optimal assignment for the following cost matrix is

• 1 — C, 2 — B ,
  3 — D, 4 — A

• 1 — B, 2 — C,
  3 — A, 4 — D

• 1 — A, 2 — B,
  3 — C, 4 — D

• 1 — D, 2 — A,
  3 — B, 4 — C