Questions on allocation and the Hungarian algorithm

Question 1

Explain why subtracting the smallest entry of a row from every entry in that row cannot change which allocation is cheapest.

Accepted Answer

Every complete allocation uses exactly one cell from each row. Subtracting the same amount from a whole row therefore reduces the total of every allocation by that same amount, so their order is unchanged and the cheapest one before the subtraction is still the cheapest after it. M1 for the observation that every allocation uses one cell from each row, A1 for the conclusion that the ordering is unchanged. The same argument applies to columns, since every allocation uses one cell from each column too.

Question 2

A 5 by 5 reduced matrix needs only 4 lines to cover its zeros. State the next step.

Accepted Answer

Four is fewer than five, so no allocation using only zeros exists yet. Find the smallest uncovered entry, subtract it from every uncovered element, and add it to every element covered by two lines. Then count the minimum covering lines again. M1 for the smallest uncovered entry, A1 for the augmenting step described in full.

Question 3

Explain why, after a cost matrix has been reduced by rows and then by columns, every row and every column contains at least one zero.

Accepted Answer

The row reduction takes each row's smallest entry off that whole row, so every row ends with a zero where its smallest entry was. B1 for a zero in every row. The column reduction then takes each column's smallest entry off that column, and every column ends with a zero for the same reason. A column that already held one of those row zeros has smallest entry 0, so nothing is taken off it and the row zeros in it survive; a column with no zero yet is given one. B1 for a zero in every column with the row zeros surviving.

Question 4

In a 3 by 3 problem the row minima are 7, 5 and 6, and after the row reduction the column minima are 0, 2 and 0. An allocation of zeros is then found in the reduced matrix. State the cost of that allocation in the original table.

Accepted Answer

Every complete allocation uses one cell from each row and one from each column, so the two reductions take the same total off all of them: 7 + 5 + 6 + 0 + 2 + 0 = 20. M1 for adding all six minima. An allocation costing 0 in the reduced matrix therefore costs 20 in the original. A1 for 20.

Question 5

Workers P, Q and R are each to be given one of the jobs 1, 2 and 3. The cost of P doing the three jobs is 14, 9, 12; the cost of Q is 11, 8, 15; the cost of R is 13, 10, 9. Use the Hungarian algorithm to find the allocation of least total cost, showing each reduced matrix.

Accepted Answer

Row minima are 9, 8 and 9, so the row-reduced matrix is 5, 0, 3; 3, 0, 7; 4, 1, 0.
Its column minima are 3, 0 and 0, so the column-reduced matrix is 2, 0, 3; 0, 0, 7; 1, 1, 0. Record the row-reduced and column-reduced matrices before giving the allocation. These intermediate matrices show that the Hungarian algorithm has been applied.
The zeros need 3 lines to cover, which matches the size of the matrix, so a complete allocation of zeros exists: P to 2, Q to 1, R to 3.
Read the cost off the original table, never the reduced one: 9 + 11 + 9 = 29.
M1 A1 for the row reduction, M1 A1 for the column reduction, A1 for the allocation, A1 for the cost.

Question 6

A table gives the profit made when each of P, Q and R does each of the jobs 1, 2 and 3. For P the profits are 14, 9, 12; for Q they are 11, 8, 15; for R they are 13, 10, 9. Find the allocation of greatest total profit.

Accepted Answer

For a maximisation problem, first convert profits to opportunity costs by subtracting each entry from a value at least as large as the greatest entry. The greatest entry is 15, so subtract every entry from 15 to get 1, 6, 3; 4, 7, 0; 2, 5, 6. Subtracting from a smaller value leaves negative entries.
Row minima 1, 0, 2 then column minima 0, 3, 0 give 0, 2, 2; 4, 4, 0; 0, 0, 4, whose zeros need 3 lines.
The allocation is P to 1, Q to 3, R to 2, with profit 14 + 15 + 10 = 39.
M1 A1 for turning the profits into costs, M1 for the row and column reduction, A1 for the allocation, A1 for the profit.
As a check, the opportunity cost lost is 1 + 0 + 5 = 6 and 3(15) − 39 = 6.

Question 7

A firm has 4 workers and only 3 jobs, and one worker refuses job 2. Describe the two adjustments needed before the algorithm is applied.

Accepted Answer

Add a dummy job, a fourth column of zeros, so the matrix is square. Whoever is allocated the dummy is the worker left idle, at no cost. For the refusal, give that one cell a cost large enough that the algorithm will never choose it, and say in your working that you have done so. The rest of the method runs unchanged. B1 for the dummy column of zeros, M1 A1 for the prohibitive cost in the refused cell.

Question 8

Each of the workers P, Q and R must be given exactly one of the jobs 1, 2 and 3, and the cost of worker i doing job j is c_ij. Formulate the problem of finding the least cost allocation as a linear programming problem, defining your decision variables.

Accepted Answer

Define x_ij = 1 if worker i is given job j, and x_ij = 0 otherwise. The objective is to minimise C = Σ c_ijx_ij, the sum running over all nine cells.
The constraints say that each worker gets exactly one job and each job exactly one worker: x_i1 + x_i2 + x_i3 = 1 for each worker i, and x_1j + x_2j + x_3j = 1 for each job j, where each x_ij is 0 or 1.
B1 for defining the indicator variables in words, B1 for the objective, M1 for one equation per worker and one per job, A1 for all six constraints with the variables restricted to 0 or 1. They are equations rather than inequalities because an allocation uses each row and each column exactly once, the same observation that makes the reduction argument safe.

Question 9

Workers P, Q and R are each to be given one of the jobs 1, 2 and 3. P costs 7, 5, 8 for the three jobs; Q costs 6, 7, 9; R cannot do job 1, and costs 4 and 6 for jobs 2 and 3. Use the Hungarian algorithm to find the least cost allocation.

Accepted Answer

Give the forbidden cell a cost so large that the algorithm can never choose it, and say in your working that you have done so.
Row minima are then 5, 6 and 4, giving 2, 0, 3; 0, 1, 3; and for R the large entry, 0, 2. Column minima 0, 0 and 2 give 2, 0, 1; 0, 1, 1; and for R the large entry, 0, 0. The large entry survives every subtraction.
Three lines are needed to cover the zeros, matching the size of the matrix, so an allocation of zeros exists: P to 2, Q to 1, R to 3, avoiding the forbidden cell as it must.
The cost, read from the original table, is 5 + 6 + 6 = 17. M1 for the prohibitive cost in the forbidden cell, M1 A1 for the two reductions, A1 for the allocation, A1 for the cost.

Question 10

A student reduces the cost matrix with rows P (14, 9, 12), Q (11, 8, 15) and R (13, 10, 9) by subtracting 8, the smallest entry in the whole matrix, from every element. State the matrix this produces, say whether the cheapest allocation has changed, and explain why the step is of no use.

Accepted Answer

Subtracting 8 from every entry gives 6, 1, 4; 3, 0, 7; 5, 2, 1. B1. Every complete allocation uses three cells, so every one of them falls by 3 × 8 = 24 and the six totals keep their order: the cheapest allocation has not changed. B1 for the ranking surviving, with the reason. The step is still useless. It creates exactly one zero, where the smallest entry was, so one line covers every zero in the matrix against a size of 3, and the line test has nothing to act on. B1 for the single zero, B1 for the line test being unusable.

Question 11

A 4 by 4 allocation problem has been reduced to the matrix with rows W (0, 3, 0, 5), X (2, 0, 4, 0), Y (0, 6, 3, 2) and Z (4, 0, 1, 0), the four columns being jobs 1, 2, 3 and 4. Show that four lines are needed to cover the zeros, and find every complete allocation of zeros, saying which cell has to be chosen first and why.

Accepted Answer

Column 1, column 2, column 4 and row W cover every zero, so four lines are enough. Three cannot do it: the zeros of W in job 3, X in job 4, Y in job 1 and Z in job 2 sit in four different rows and four different columns, so no single line covers two of them and at least four are needed. M1 for a covering set of four, A1 for four being the minimum, which matches the size of the matrix.
Start where there is no choice. Y has a single zero, at job 1, so Y takes job 1 and column 1 is closed. B1 for starting at the row with one zero.
W's zeros were at jobs 1 and 3, and job 1 has gone, so W takes job 3. A1 for Y to 1 and W to 3.
X and Z are both left with zeros at jobs 2 and 4, and neither is forced, so there are two complete allocations: Y to 1, W to 3, X to 2, Z to 4, and Y to 1, W to 3, X to 4, Z to 2. A1 for both.
Two allocations of zeros mean two plans of equal total cost, and either may be given so long as the working says so.

Question 12

Workers P, Q and R are each to be given one of the jobs 1, 2 and 3. The cost of P doing the three jobs is 6, 11, 11; the cost of Q is 9, 17, 13; the cost of R is 12, 7, 5. Reduce the matrix, show that the line test fails, augment, and give the allocation and its cost.

Accepted Answer

Row minima 6, 9, 5 give 0, 5, 5; 0, 8, 4; 7, 2, 0. Column minima 0, 2, 0 then give 0, 3, 5; 0, 6, 4; 7, 0, 0.
Every zero is covered by column 1 together with row 3, so only 2 lines are needed against a size of 3, and the test fails. State the number of lines explicitly, since it decides whether a complete allocation exists yet.
The uncovered entries are 3, 5, 6 and 4, so the smallest is 3. Subtract 3 from every uncovered entry and add 3 to the entry covered twice, which is the 7 at the foot of column 1, giving 0, 0, 2; 0, 3, 1; 10, 0, 0. Add the smallest uncovered entry at every crossing point; omitting it changes the problem, so the allocation found need not be the cheapest.
Three lines are now needed, so an allocation exists: P to 2, Q to 1, R to 3, costing 11 + 9 + 5 = 25.
M1 A1 for the row and column reduction, B1 for stating that only two lines are needed, M1 for subtracting the smallest uncovered entry and adding it at the crossing, A1 for the augmented matrix, A1 for the allocation, A1 for the cost.
Checking all six allocations confirms 25 is the least.

Question 13

A firm has four workers, W, X, Y and Z, and only three jobs. For jobs 1, 2 and 3, W costs 10, 12, 9; X costs 8, 13, 11; Y costs 9, 14, 12; Z costs 11, 10, 13. Use the Hungarian algorithm to find the least cost allocation, and state which worker is left without a job.

Accepted Answer

Add a dummy job, a fourth column of zeros, so the matrix is square; whoever receives it is the worker left idle, at no cost. Every row now contains a zero, so the row reduction changes nothing and only the columns do any work. Column minima 8, 10, 9 and 0 give 2, 2, 0, 0; 0, 3, 2, 0; 1, 4, 3, 0; 3, 0, 4, 0. Four lines are needed to cover the zeros, matching the size of the matrix, so an allocation of zeros exists. Y's only zero is in the dummy column, so Y is left without a job, and the rest follows: X to 1, W to 3, Z to 2. The cost, read from the original table, is 8 + 9 + 10 = 27. B1 for the dummy column of zeros, M1 for reducing, A1 for the reduced matrix, B1 for stating that four lines are needed, A1 for the allocation with Y idle, A1 for the cost. Leaving X idle instead would cost 28.

Question 14

When the line test fails on an n by n reduced matrix covered by r rows and k columns, with r + k less than n, the smallest uncovered entry e is subtracted from every uncovered element and added to every element covered twice. Show that this leaves the cheapest allocation unchanged and no entry negative, and explain why the step cannot be repeated for ever.

Accepted Answer

Take the same e off every element of each of the n − r uncovered rows, then add e to every element of each of the k covered columns. An element covered by neither line loses e and has nothing added back; one covered by a column line only gains e and loses e, so it is unchanged; one covered by a row line only is unchanged; one covered twice gains e. That is exactly the step described. M1 A1 for rewriting it as whole-row and whole-column operations.
Every complete allocation uses one cell from each row and each column, so each of those operations changes every allocation's total by the same amount: the ordering is untouched and the cheapest allocation is the same one it was. B1 for the ordering surviving.
No entry goes negative, because the only elements reduced are the uncovered ones and e is the smallest of those. B1.
Counting the entries, (n − r)(n − k) of them fall by e and rk of them rise by e, so the total of the matrix changes by e[rk − (n − r)(n − k)]. Writing n − r − k for the shortfall, (n − r)(n − k) − rk = n(n − r − k), which is positive because r + k is below n. M1 for the change in the total, A1 for it being a strict fall.
The entries stay whole and never go negative, so the total cannot fall for ever and the step must eventually leave a matrix the test passes.

Question 15

Four salespeople W, X, Y and Z are to be sent to three regions 1, 2 and 3, one each, and one salesperson will stay behind. The profit made by W in the three regions is 12, 15, 9; by X it is 14, 11, 13; by Y it is 10, 16, 12; by Z it is 13, 12, 15. Find the allocation of greatest total profit, stating who stays behind, and explain why the dummy column must be added after the profits have been converted and not before.

Accepted Answer

Convert profits to costs first by subtracting every entry from the largest entry, 16: the rows become 4, 1, 7; 2, 5, 3; 6, 0, 4; 3, 4, 1. B1 for the conversion with 16 named.
Now square the table up with a fourth column of zeros for the region nobody is sent to: 4, 1, 7, 0; 2, 5, 3, 0; 6, 0, 4, 0; 3, 4, 1, 0. Added before the conversion, that column of zeros would have been subtracted from 16 like everything else and would have arrived as a column of 16s, the dearest cells in the table, which is the opposite of a free option. B1 for the dummy column with the reason for its place in the order.
Every row now holds a zero, so the row reduction does nothing. Column minima 2, 0, 1, 0 give 2, 1, 6, 0; 0, 5, 2, 0; 4, 0, 3, 0; 1, 4, 0, 0. M1 A1 for the reduction.
Four lines are needed to cover the zeros, matching the size, so an allocation of zeros exists. W's only zero is in the dummy column, so W stays behind, and the rest follows: X to region 1, Y to region 2, Z to region 3. A1 for the allocation with W named.
The profit, read from the original table, is 14 + 16 + 15 = 45. A1. Any other choice of three salespeople does worse, the next best being 44.