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

Maximisation and Unbalanced Assignment Problems

Q: How do you solve a maximisation assignment problem with the Hungarian method?

Subtract every cell from the largest value in the matrix to get a regret matrix. Solve this as a normal minimisation problem using row and column reduction and the line test. Finally, add the values of the chosen cells from the original profit matrix.

Q: What is a dummy row or column in an assignment problem?

It is an imaginary row or column of zeros added to make an unbalanced matrix square. Whoever is matched to it is actually not assigned. It adds no cost or profit to the total.

Q: How many dummies should I add if the matrix is not square?

Add as many as the difference between the number of rows and columns. If there are 5 jobs and 3 machines, add 2 dummy machine columns. In most exam questions the difference is one.

Q: Do I need to subtract from the largest value, or can I just negate the profits?

Subtracting from the largest value is the standard method and keeps all entries non-negative. Negating the profits gives the same optimal assignment, but it is less common in ICMAI answers and is easier to get wrong.

Updated 10 October 2026 · Fact-checked

A maximisation assignment problem is solved by converting profits into regrets: subtract every value from the largest value in the matrix, then apply the Hungarian method. An unbalanced problem has unequal rows and columns, so you add dummy rows or columns with zero entries to make the matrix square before solving.

Understand Maximisation and Unbalanced Assignment Problems

The Hungarian method is built to minimise. It works on a square matrix, where the number of persons equals the number of jobs, and it picks exactly one cell in each row and column. Two situations break this: the objective is to maximise (profit, sales, output), or the matrix is not square.

For maximisation, you turn the problem into a minimisation one. Find the largest value in the whole matrix and subtract every entry from it. The new entries are called opportunity losses or regrets. Minimising total regret is the same as maximising total profit. You then solve normally. At the end, read the answer from the original profit matrix, not the regret matrix.

An unbalanced problem has, for example, 4 jobs but 3 machines. One job must go unassigned. To handle this, add a dummy row or column with all zero entries so the matrix becomes square. Whoever or whatever gets matched to the dummy is left out. It adds no cost and no profit.

Some questions combine both: unbalanced and maximisation. Add the dummy first with zero profit, then convert. Be careful here: if you convert first, the dummy zeros must still be treated as zero profit. The safest order is to add the dummy with zeros, find the largest value, and subtract all cells including the dummy ones from it.

Key rules to remember

Maximisation to minimisation: Regret = (largest value in the matrix) − (cell value); Apply to every cell, then run the Hungarian method on the regret matrix. Total profit is read from the original matrix.
Balancing rule: Number of rows = number of columns; If rows < columns, add dummy rows. If columns < rows, add dummy columns. Add as many as the difference.
Dummy entries: Dummy row or column cells = 0; A dummy has zero cost or zero profit. Add it before converting a maximisation problem.
Optimality test: Minimum lines covering all zeros = order of the matrix (n); If lines are fewer than n, revise the matrix. If equal to n, an assignment on zeros exists.
Revision step: Subtract the smallest uncovered value from uncovered cells; add it to cells at line intersections; Cells covered by one line stay unchanged.

How to solve Maximisation and Unbalanced Assignment Problems questions

Use this order for any maximisation or unbalanced assignment question.

1Check the matrix size. If rows and columns differ, add dummy rows or columns with zero entries to make it square.
2Check the objective. If it asks for maximum profit, sales or output, find the largest value in the full matrix, including dummy zeros.
3Subtract every cell from that largest value to build the regret matrix. If the objective is minimisation, skip this step.
4Do row reduction: subtract the smallest value of each row from that row. Then do column reduction in the same way.
5Cover all zeros with the minimum number of horizontal and vertical lines. If the number of lines equals n, go to the next step. Otherwise subtract the smallest uncovered value from uncovered cells, add it at intersections, and repeat.
6Make the assignment on zeros. Start with rows or columns having a single zero, tick that cell, and strike out other zeros in its row and column.
7Write the pairs, take their values from the ORIGINAL matrix, and add them up. State which person or job is matched to the dummy, which means it is left unassigned.

Quickest way: Dummy first, regret second, original values last

When to use it: Use it for any 3x3 to 5x5 problem where time is tight and you want to avoid conversion errors.

Count rows and columns. Add a zero dummy at once if they differ.
For maximisation, circle the largest number and subtract each cell from it. Write the new matrix neatly.
Do row and column reduction. Often a full set of independent zeros appears and no line drawing is needed.
Mark the assignment, then go back to the original table and add the real values. Do not add values from the regret matrix.
Write the total with unit and rupee sign, and name the unassigned item if there is a dummy.

Common mistakes in Maximisation and Unbalanced Assignment Problems

Subtracting from the wrong number, such as each row's largest value.
Students mix this with row reduction, where each row has its own minimum.
Fix: For conversion, use one single largest value from the whole matrix. Use row minimums only in the reduction step.
Reporting the total from the regret matrix.
The last table on the page is the regret one, so students add values from it.
Fix: Always return to the original profit matrix and sum the cells at the chosen positions.
Adding the wrong number of dummies, or not squaring the matrix.
Students add one dummy automatically or forget the difference in size.
Fix: Add exactly (larger count − smaller count) dummies, so rows equal columns.
Giving the dummy a non-zero cost or profit.
Students copy values from another row or column.
Fix: Fill the dummy entirely with zeros. It stands for 'not assigned', which costs or earns nothing.
Stopping the Hungarian method before the line test is satisfied.
Students see many zeros and assume an assignment is possible.
Fix: Count the minimum covering lines. Only when lines equal n can you assign one zero per row and column.
Forgetting to say which job or person is unassigned.
The dummy pair looks like a working step, not an answer.
Fix: State clearly, for example, 'Job J2 is not assigned', as the question usually asks for it.

Worked examples

Example 1

A firm has four salesmen A, B, C, D and four territories 1 to 4. The expected monthly profit (₹ in thousands) of 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 one salesman to each territory to maximise total profit.

Show the solution

The matrix is 4x4, so no dummy is needed. The objective is maximisation, so convert.
The largest value in the matrix is 16. Subtract each cell from 16.
Regret matrix: A: 0, 6, 2, 5; B: 2, 5, 1, 1; C: 1, 1, 3, 4; D: 3, 4, 2, 1.
Row minima are 0, 1, 1, 1. After row reduction: A: 0, 6, 2, 5; B: 1, 4, 0, 0; C: 0, 0, 2, 3; D: 2, 3, 1, 0.
Each column already has a zero, so column reduction changes nothing.
Look for independent zeros. Row A has a zero only in column 1. Row D has a zero only in column 4. Row C then takes column 2, and B takes column 3. Four independent zeros exist, so the solution is optimal.
Assignment: A to 1, C to 2, B to 3, D to 4.
Read from the original matrix: 16 + 15 + 15 + 15 = 61.

Answer: A–1, B–3, C–2, D–4. Maximum total profit = ₹61,000.

Example 2

A workshop has four jobs J1 to J4 and three machines M1, M2, M3. Each machine can take only one job. Cost in ₹: J1: 12, 10, 15; J2: 14, 11, 13; J3: 9, 12, 14; J4: 10, 13, 11 (columns are M1, M2, M3). Find the assignment with minimum total cost and state which job is left out.

Show the solution

There are 4 rows and 3 columns, so add one dummy machine column D with zero cost in every row. The matrix is now 4x4. The objective is minimisation, so no conversion is needed.
Row minima are all 0 because of the dummy column, so row reduction changes nothing.
Column minima are 9 (M1), 10 (M2), 11 (M3) and 0 (D). Subtract them from each column.
Reduced matrix: J1: 3, 0, 4, 0; J2: 5, 1, 2, 0; J3: 0, 2, 3, 0; J4: 1, 3, 0, 0.
J2 has a zero only in column D, so J2 goes to the dummy, which means it is not assigned.
Then J1 has a zero only at M2 once D is taken. J3 has a zero only at M1. J4 has a zero only at M3. Four independent zeros exist, so this is optimal.
Cost from the original matrix: J1–M2 = 10, J3–M1 = 9, J4–M3 = 11. Total = 10 + 9 + 11 = 30.

Answer: J1 to M2, J3 to M1, J4 to M3. Job J2 is left unassigned. Minimum total cost = ₹30.

Exam tips

In Section A, a single MCQ may ask only what to do first: add a dummy, or subtract from the largest value. Know both rules by heart. There is no negative marking, so always attempt every MCQ.
In written answers, show the dummy addition, the regret matrix and the final pairing as separate labelled steps. Step marks are given for each stage.
Always end with a statement of the pairs and the total from the original matrix, with rupee units. Mention the unassigned job or person if a dummy was used.
If both unbalanced and maximisation are present, write the dummy zeros before you find the largest value, and say so in your answer.

Practice questions from Job Evaluation, Job Allocation - Assignment