Skip to content

Operations Management and Strategic Management · Job Evaluation, Job Allocation - Assignment

Hungarian Method for Minimisation Assignment Problems

Updated 10 October 2026 · Fact-checked

The Hungarian method finds the lowest-cost one-to-one allocation of jobs to workers in a balanced square cost matrix. Subtract the row minimum from each row, then the column minimum from each column. Cover all zeros with the fewest lines. If the lines equal n, assign on zeros; otherwise adjust the matrix and repeat.

Understand Hungarian Method for Minimisation Problems

An assignment problem asks you to allot n jobs to n workers (or machines) so that each worker gets exactly one job and each job goes to exactly one worker. The aim in a minimisation problem is the lowest total cost or time. The matrix is balanced when the number of rows equals the number of columns.

The method works because of one fact. If you subtract the same number from every cell of a row or a column, the best assignment does not change. Every complete assignment uses exactly one cell from each row and one from each column, so each assignment's total falls by the same amount.

So you keep subtracting until zeros appear. A zero in the reduced matrix means that worker-job pair costs nothing extra over the minimum. If you can pick n zeros, with one in each row and one in each column, that is the cheapest assignment. You then read the actual cost from the original matrix.

Sometimes you cannot pick n such zeros. Then you use the covering-line test to find out how far you are from the answer. You create new zeros by a fixed adjustment and test again. You repeat until you reach the optimum.

Key rules to remember

Row reduction
New cell = cell − (smallest value in its row)
Do this for every row first. Every row now has at least one zero.
Column reduction
New cell = cell − (smallest value in its column)
Do this on the row-reduced matrix. Skip any column that already has a zero.
Optimality test
Minimum number of lines covering all zeros = n ⇒ optimal
Lines are horizontal or vertical only. If the count is less than n, the solution is not yet optimal.
Matrix adjustment
Uncovered cells: subtract k. Cells at line intersections: add k. Singly covered cells: unchanged. Here k = smallest uncovered value.
This creates at least one new zero. Then redo the line test.
Total cost
Total cost = Σ original cost of the assigned cells
Always add from the original matrix, not the reduced one.

How to solve Hungarian Method for Minimisation Problems questions

Use this order for any balanced minimisation problem. If the matrix is not square, balance it first with a dummy row or column of zeros.

  1. 1Check that the matrix is square. If not, add a dummy row or column of zero costs.
  2. 2Row reduction: subtract the smallest number in each row from every number in that row.
  3. 3Column reduction: subtract the smallest number in each column from every number in that column. Skip columns that already contain a zero.
  4. 4Cover all zeros with the minimum number of horizontal and vertical lines. If the number of lines equals n, go to step 6.
  5. 5If the lines are fewer than n, find the smallest uncovered number k. Subtract k from all uncovered cells and add k to cells where two lines cross. Leave other cells as they are. Return to step 4.
  6. 6Make the assignment. Start with a row or column that has a single zero, allot that pair, and strike out its row and column. Repeat until all n are assigned.
  7. 7Write the assignment pairs and add their costs from the original matrix. State the total with its unit.

Quickest way: Single-zero shortcut with a lower-bound check

When to use it: Use it in the exam for 3×3 and 4×4 matrices, which are the usual sizes.

  1. Write the row minima beside the matrix and column minima below it as you reduce. This saves redrawing the matrix.
  2. Before drawing lines, try to assign directly. Pick any row or column with exactly one zero, tick that pair, and cross out its row and column. If you finish n pairs, you do not need lines.
  3. If you get stuck, draw lines. Fewer lines than n means the assignment is not complete.
  4. Check your answer. Sum of row minima + column minima + each adjustment k × (n − number of lines used) should equal the final cost. If it does not, recheck your arithmetic.

Common mistakes in Hungarian Method for Minimisation Problems

  • Doing column reduction first or skipping row reduction.

    Students see a small number in a column and subtract it straight away.

    Fix: Always reduce rows first, then columns. Reducing columns that already contain a zero changes nothing, so skip those.

  • Adding the cost from the reduced matrix.

    The zeros make the sum look like zero, so students add reduced numbers.

    Fix: Mark your chosen cells and go back to the original matrix to add the costs.

  • Drawing diagonal lines or more lines than needed.

    Students cover zeros one by one without checking the minimum.

    Fix: Use only horizontal and vertical lines. Start with the row or column holding the most zeros. Check that no smaller set of lines also covers every zero.

  • Wrong adjustment at intersections.

    Students subtract k from all uncovered cells but forget to add it where two lines cross.

    Fix: Uncovered: minus k. Crossing: plus k. Singly covered: no change. Check that the total of the matrix changes as expected.

  • Assigning zeros carelessly and getting two jobs for one worker.

    Students pick the first zero in each row.

    Fix: Begin with rows or columns that have a single zero. After each assignment, strike out its row and column.

  • Not balancing a non-square matrix.

    Students start reducing straight away.

    Fix: Count rows and columns first. Add a dummy row or column of zeros so that the matrix is square.

Worked examples

Example 1

A firm has four operators (A, B, C, D) and four jobs (1, 2, 3, 4). The cost of each operator doing each job (₹ '000) is:

A: 12, 30, 21, 15
B: 18, 33, 9, 31
C: 44, 25, 24, 21
D: 23, 30, 28, 14

Find the assignment that minimises total cost.

Show the solution
  1. The matrix is 4×4, so it is balanced.
  2. Row minima: A 12, B 9, C 21, D 14. After row reduction: A: 0, 18, 9, 3. B: 9, 24, 0, 22. C: 23, 4, 3, 0. D: 9, 16, 14, 0.
  3. Column minima: job 1 = 0, job 2 = 4, job 3 = 0, job 4 = 0. Only column 2 changes. Reduced matrix: A: 0, 14, 9, 3. B: 9, 20, 0, 22. C: 23, 0, 3, 0. D: 9, 12, 14, 0.
  4. Assign by single zeros. Row A has only one zero, in job 1, so A→1. Row B has only one zero, in job 3, so B→3. Row D has only one zero, in job 4, so D→4. That leaves C→2, which is a zero.
  5. Four assignments are made, so the solution is optimal (4 lines would be needed, equal to n).
  6. Cost from the original matrix: A→1 = 12, B→3 = 9, C→2 = 25, D→4 = 14. Total = 12 + 9 + 25 + 14 = 60.
  7. Check: row minima total 56, plus column reduction 4, equals 60.

Answer: A→Job 1, B→Job 3, C→Job 2, D→Job 4. Minimum total cost = ₹60,000.

Example 2

Four machines (M1 to M4) must each be given one of four jobs (A, B, C, D). The cost (₹) of each job on each machine is:

A: 10, 16, 17, 13
B: 12, 19, 15, 19
C: 9, 14, 18, 10
D: 13, 9, 8, 7

(columns are M1, M2, M3, M4). Find the minimum-cost assignment.

Show the solution
  1. Row minima: A 10, B 12, C 9, D 7. Row-reduced matrix: A: 0, 6, 7, 3. B: 0, 7, 3, 7. C: 0, 5, 9, 1. D: 6, 2, 1, 0.
  2. Column minima: M1 = 0, M2 = 2, M3 = 1, M4 = 0. Column-reduced matrix: A: 0, 4, 6, 3. B: 0, 5, 2, 7. C: 0, 3, 8, 1. D: 6, 0, 0, 0.
  3. Cover the zeros: column M1 and row D. That is 2 lines, fewer than 4, so it is not yet optimal.
  4. Smallest uncovered value k = 1. Subtract 1 from uncovered cells (rows A, B, C under M2 to M4). Add 1 at the crossing cell (D, M1). New matrix: A: 0, 3, 5, 2. B: 0, 4, 1, 6. C: 0, 2, 7, 0. D: 7, 0, 0, 0.
  5. Cover the zeros again: column M1, row D and row C. Minimum is 3 lines, still less than 4.
  6. Smallest uncovered value is 1 (rows A and B, M2 to M4: 3, 5, 2, 4, 1, 6). Subtract 1 from these cells. Add 1 where lines cross: (C, M1) and (D, M1). New matrix: A: 0, 2, 4, 1. B: 0, 3, 0, 5. C: 1, 2, 7, 0. D: 8, 0, 0, 0.
  7. Assign: A has only one zero, at M1, so A→M1. Then B's remaining zero is M3, so B→M3. C's remaining zero is M4, so C→M4. D→M2.
  8. Cost from the original matrix: A on M1 = 10, B on M3 = 15, C on M4 = 10, D on M2 = 9. Total = 44.
  9. Check: row minima 38 + column minima 3 = 41. First adjustment adds 1 × (4 − 2) = 2. Second adds 1 × (4 − 3) = 1. 41 + 2 + 1 = 44.

Answer: Job A→M1, B→M3, C→M4, D→M2. Minimum total cost = ₹44.

Exam tips

  • Show every matrix in the answer: after row reduction, after column reduction, and after each adjustment. Step marks go to these.
  • Mention the line count against n each time, for example '2 lines < 4, so not optimal'. This earns marks for the optimality test.
  • Write the final assignment as a list of pairs with their original costs and the total. Do not stop at the zeros.
  • For MCQs with a 3×3 matrix, row and column reduction plus a single-zero assignment usually gives the answer in under two minutes. There is no negative marking, so always mark an option.
  • If the question gives an unequal number of workers and jobs, add the dummy row or column first and state that you did it.

Practice questions from Job Evaluation, Job Allocation - Assignment

Hungarian Method for Minimisation Problems in other exams

The same ground in other exams, if you are preparing for more than one or want another angle on it.

Hungarian Method for Minimisation Problems: frequently asked questions

What are the steps of the Hungarian method?

Balance the matrix, reduce each row by its minimum, then reduce each column by its minimum. Cover all zeros with the fewest lines. If the lines equal n, assign on zeros. Otherwise subtract the smallest uncovered value from uncovered cells, add it at crossings, and repeat.

How do I know the solution is optimal?

It is optimal when you can choose n zeros with one in each row and one in each column. That happens exactly when the minimum number of covering lines equals n.

What if the matrix is not square?

Add a dummy row or column with all zero costs to make it square. A worker or job assigned to the dummy is left unassigned. The Hungarian steps then run as usual.

Do I add the cost from the reduced or the original matrix?

Always the original matrix. The reduced matrix is only a tool for finding which pairs to choose.