Skip to content

Strategic Cost Management · Assignment

Maximization and Unbalanced Assignment Problems Explained

Updated 11 October 2026 · Fact-checked

For a maximization assignment problem, subtract every entry from the largest entry in the matrix, then solve it as a minimization using the Hungarian method. For an unbalanced problem, add dummy rows or columns with zero entries to make the matrix square. Then solve as usual and read the result.

Understand Maximization and Unbalanced Assignment Problems

The Hungarian method only knows how to minimize, and it only works on a square matrix. Two common exam twists break these conditions. The matrix may show profit, sales or efficiency (you want the maximum), or the number of persons may not equal the number of jobs.

Maximization. To maximize profit, you can minimize the opportunity loss instead. Take the largest value in the whole matrix and subtract each entry from it. Each new entry shows how much profit you lose compared with the best possible cell. Minimizing total loss gives the same assignment as maximizing total profit. The answer must then be read from the original profit matrix, not the loss matrix.

Unbalanced problems. If there are 3 workers and 4 jobs, the matrix is 3 × 4. Add one dummy row (an imaginary worker) with all zero entries to make it 4 × 4. If workers exceed jobs, add a dummy column. A zero is used because a dummy assignment has no real cost or profit. Whoever is paired with a dummy is simply not assigned, or the job stays undone.

Multiple optimal solutions. After the final step, you may find more than one way to choose a full set of independent zeros. Each such set gives the same total cost or profit. So the problem has alternative optimal solutions. The total is the same, but the pairings differ. This lets management choose on other grounds, such as preference or convenience.

A problem can combine both twists: unbalanced and maximization. Convert to loss first, then add the dummy with zeros. Always check the order of steps in the question.

Key rules to remember

Conversion of maximization to minimization
Opportunity loss = (Largest value in the matrix) − (Given value)
Apply to every cell. Then use the Hungarian method. Read the final total from the original profit matrix.
Balancing rule
Number of rows = Number of columns
If rows < columns, add (columns − rows) dummy rows. If columns < rows, add (rows − columns) dummy columns.
Dummy entries
All entries of a dummy row or column = 0
In a maximization problem, add the dummy zeros after converting to loss, or use zero profit in the original matrix. Both give the same assignment.
Optimality condition
Minimum number of lines covering all zeros = order of the square matrix
If fewer lines, subtract the smallest uncovered value from uncovered cells and add it to cells at line intersections.
Multiple optima
More than one complete set of independent zeros ⇒ alternative optimal solutions
All such sets give the same optimal total.

How to solve Maximization and Unbalanced Assignment Problems questions

Use this order for any question on maximization or unbalanced assignment. Do not skip the check of the matrix shape and the objective.

  1. 1Read the objective. If it is profit, sales or efficiency, you maximize. If it is cost, time or distance, you minimize.
  2. 2Count rows and columns. If unequal, add dummy rows or columns with zero entries to make the matrix square.
  3. 3For maximization, find the largest entry in the matrix. Subtract every entry from it to get the opportunity loss matrix. Dummy cells stay 0 in the original profit matrix, so they become the largest value minus 0 in the loss matrix, or you may add the dummy after conversion with zeros.
  4. 4Row reduction: subtract the smallest entry of each row from all entries in that row. Then column reduction: subtract the smallest entry of each column from that column.
  5. 5Cover all zeros with the minimum number of horizontal and vertical lines. If the number of lines equals the order of the matrix, go to step 6. Otherwise take the smallest uncovered value, subtract it from uncovered cells, add it to intersection cells, and repeat.
  6. 6Make assignments. Start with rows or columns that have a single zero, strike out the rest of that row and column, and continue. If every row has more than one zero, you have alternative solutions. Pick one set and mention that others exist.
  7. 7Write the pairings. Ignore pairings with a dummy and note the unassigned person or job.
  8. 8Compute the total from the original matrix (profit or cost), not from the reduced matrix.

Quickest way: Dummy first, then convert, then reduce

When to use it: Use this in the exam when the question is a numerical of 14 marks and you must save time on a 4 × 4 or 5 × 5 matrix.

  1. Circle the objective word in the question before you touch the matrix.
  2. Make the matrix square first. A wrong shape wastes the whole working.
  3. For maximization, write the largest value on the side and fill the loss matrix in a single pass.
  4. Row-reduce and column-reduce, then look for assignments directly. In small matrices the zeros often give a full assignment without drawing lines.
  5. Before finalising, test one row for a second zero. If found, mention alternative solutions and show the total is unchanged.
  6. Add the actual values from the original matrix to confirm the total. This catches arithmetic slips.

Common mistakes in Maximization and Unbalanced Assignment Problems

  • Subtracting from the row maximum or column maximum instead of the largest value in the whole matrix.

    Students mix this up with row reduction, where each row uses its own minimum.

    Fix: For conversion, use one number only: the single largest entry in the matrix. Row and column minima come later.

  • Reporting the total from the loss matrix as the maximum profit.

    The last working shows only zeros and small numbers, so the student stops there.

    Fix: After choosing the pairs, go back to the original profit matrix and add the actual profits.

  • Adding a dummy row when a dummy column is needed, or the wrong number of dummies.

    Students do not compare rows with columns carefully.

    Fix: Count both. Add dummies on the side with fewer lines, and add exactly the difference.

  • Treating a pairing with a dummy as a real cost or profit.

    The dummy zero is carried into the total by habit.

    Fix: A dummy pairing adds nothing. State clearly which real job or person remains unassigned.

  • Stopping at one solution without noticing alternatives, or claiming alternatives when none exist.

    Students do not test for a second complete set of independent zeros.

    Fix: After assigning, check if any other full set of zeros exists. Say so only if it does, and confirm the total is the same.

  • Using fewer lines than the matrix order and still making assignments.

    Students rush and draw lines poorly.

    Fix: Draw lines through rows or columns with the most zeros first. If lines are fewer than the order, revise the matrix before assigning.

Worked examples

Example 1

A firm has four salesmen (A, B, C, D) and four territories (1, 2, 3, 4). The expected monthly profit (₹ in thousands) for each salesman in each territory is: A: 16, 10, 14, 11; B: 14, 11, 15, 15; C: 15, 15, 13, 12; D: 13, 12, 14, 15. Assign salesmen to territories to maximize total profit.

Show the solution
  1. The objective is maximization. The matrix is 4 × 4, so no dummy is needed.
  2. The largest entry is 16. Subtract each entry from 16 to get the loss matrix. A: 0, 6, 2, 5. B: 2, 5, 1, 1. C: 1, 1, 3, 4. D: 3, 4, 2, 1.
  3. Row reduction: the row minima are 0, 1, 1, 1. The matrix becomes A: 0, 6, 2, 5. B: 1, 4, 0, 0. C: 0, 0, 2, 3. D: 2, 3, 1, 0.
  4. Column reduction: each column already has a zero, so nothing changes.
  5. Assign. Row D has a single zero, in territory 4. So D to 4. Row A has a single zero, in territory 1. So A to 1. Then B has zeros in 3 and 4, but 4 is taken, so B to 3. C then goes to 2, where it has a zero.
  6. Check that four independent zeros exist, so the solution is optimal. It is unique, since D, A, B and C each had one choice after the earlier assignments.
  7. Total profit from the original matrix: A–1 = 16, B–3 = 15, C–2 = 15, D–4 = 15. Sum = 61.

Answer: A to territory 1, B to territory 3, C to territory 2, D to territory 4. Maximum profit = ₹61,000 per month.

Example 2

A workshop has three workers (W1, W2, W3) and four jobs (J1 to J4). The cost of each worker doing each job (₹ in hundreds) is: W1: 12, 10, 15, 13; W2: 14, 11, 12, 16; W3: 13, 14, 10, 12. Each worker does one job only and each job needs one worker. Find the assignment with minimum cost and say which job stays unassigned.

Show the solution
  1. The matrix is 3 × 4, so it is unbalanced. Add a dummy worker D with cost 0 for all jobs. The matrix is now 4 × 4.
  2. Row reduction: the row minima are 10, 11, 10, 0. The matrix becomes W1: 2, 0, 5, 3. W2: 3, 0, 1, 5. W3: 3, 4, 0, 2. D: 0, 0, 0, 0.
  3. Column reduction: every column already has a zero, so nothing changes.
  4. Cover the zeros: the column of J2, the column of J3 and the row of D. That is 3 lines, less than 4, so the matrix is not yet optimal.
  5. The smallest uncovered value is 2. Subtract 2 from uncovered cells. Add 2 to the two cells where lines cross (D under J2 and D under J3). The matrix becomes W1: 0, 0, 5, 1. W2: 1, 0, 1, 3. W3: 1, 4, 0, 0. D: 0, 2, 2, 0.
  6. Assign. W2 has a single zero, in J2. So W2 to J2. W1 then takes J1, and D takes J4. W3 takes J3.
  7. Job J4 is paired with the dummy, so J4 stays unassigned.
  8. Cost from the original matrix: W1–J1 = 12, W2–J2 = 11, W3–J3 = 10. Sum = 33.

Answer: W1 to J1, W2 to J2, W3 to J3. Job J4 remains unassigned. Minimum cost = ₹3,300.

Exam tips

  • Write down the objective and the matrix size first. Marks are often lost on a missed dummy or a missed conversion, not on the Hungarian steps.
  • Always show the loss matrix in a maximization answer. Examiners award marks for the conversion step.
  • Quote the final total from the original matrix. State it in the unit given, such as ₹ in thousands.
  • If the problem gives a condition such as a worker who cannot do a job, treat that cell as a very large cost. This links to restricted assignments.
  • In MCQs, check whether the question asks for the total, the pairing, or the unassigned job. They need different readings of the same final matrix.

Practice questions from Assignment

Maximization and Unbalanced Assignment Problems in other exams

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

Maximization and Unbalanced Assignment Problems: frequently asked questions

How do I solve a maximization assignment problem using the Hungarian method?

Subtract every entry from the largest entry in the matrix to get the opportunity loss matrix. Then solve it as a minimization problem using row and column reduction and covering lines. Finally, compute the total profit from the original matrix.

Why do we add a dummy row or column with zeros in an unbalanced assignment problem?

The Hungarian method needs a square matrix. A dummy row or column makes the matrix square. Zero entries are used because a dummy pairing means no real work is done, so it has no cost or profit.

How do I know if an assignment problem has multiple optimal solutions?

After the final matrix, look for more than one complete set of independent zeros. If you can choose different pairings and still cover every row and column, there are alternative optimal solutions. All of them give the same total.

What if the problem is both unbalanced and a maximization?

Make the matrix square with a dummy of zero profit. Then convert to opportunity loss using the largest value in the matrix, and solve. Whoever is paired with the dummy is not assigned.