Question 2
A sales manager will assign each of four sales representatives, Ruby, Tom, Isla and Kai, to a different region. The table shows each representative’s expected monthly sales ($ thousand) in each region.
| North | South | East | West | |
|---|---|---|---|---|
| Ruby | 27 | 15 | 12 | 23 |
| Tom | 18 | 20 | 13 | 18 |
| Isla | 23 | 18 | 26 | 26 |
| Kai | 24 | 28 | 24 | 15 |
Use the Hungarian algorithm to determine the allocation of representatives to regions that maximises the total expected monthly sales, and the maximum total expected monthly sales.
Turn sales into shortfalls, then let the zeros choose
The table converts, reduces and adjusts until four lines are needed to cover the zeros. Then the zeros give the allocation, and the original table gives the total.
Try your own allocation
Give each representative one region, one per region. The total comes from the original sales table. There are 24 possible allocations.
($ thousand).
Lines through row Isla and columns North and South also cover every zero after the reductions. The adjusted matrix is different, but it still needs 4 lines and gives the same allocation and the same total, 99.
Work through the solution one mark at a time
Try each step yourself before you reveal it.
Convert to a minimisation problem by subtracting each value from the largest value, 28.
$$\begin{array}{l|cccc} & \text{North} & \text{South} & \text{East} & \text{West}\\\hline \text{Ruby} & 1 & 13 & 16 & 5\\\text{Tom} & 10 & 8 & 15 & 10\\\text{Isla} & 5 & 10 & 2 & 2\\\text{Kai} & 4 & 0 & 4 & 13\end{array}$$
The Hungarian algorithm finds a minimum, so turn each sale into its shortfall from the largest value in the table, 28. For example, Ruby, North is $28-27=1$.
Subtracting each value from the largest value in its row is an alternative method. Method 2 shows that route.
Marker: converts the table to a minimisation matrix
Row reduction: subtract the smallest value in each row (Ruby 1, Tom 8, Isla 2, Kai 0). Each column then already contains a 0, so column reduction leaves the matrix unchanged.
$$\begin{array}{l|cccc} & \text{North} & \text{South} & \text{East} & \text{West}\\\hline \text{Ruby} & 0 & 12 & 15 & 4\\\text{Tom} & 2 & 0 & 7 & 2\\\text{Isla} & 3 & 8 & 0 & 0\\\text{Kai} & 4 & 0 & 4 & 13\end{array}$$
Row reduction makes a zero in every row without changing which allocation is best. Column reduction makes a zero in every column, and here every column already has one.
This mark may be implied by subsequent working.
Marker: correctly reduces rows and columns
Zeros covered by 3 lines (rows Ruby and Isla, column South) $<4$. The smallest uncovered value is 2: subtract 2 from the uncovered values and add 2 where the lines cross.
$$\begin{array}{l|cccc} & \text{North} & \text{South} & \text{East} & \text{West}\\\hline \text{Ruby} & 0 & 14 & 15 & 4\\\text{Tom} & 0 & 0 & 5 & 0\\\text{Isla} & 3 & 10 & 0 & 0\\\text{Kai} & 2 & 0 & 2 & 11\end{array}$$
The minimum number of lines to cover the zeros is now 4, so an optimal allocation exists.
An allocation can be read off only when the minimum number of lines covering the zeros equals 4. Subtracting the smallest uncovered value creates a new zero, and adding it where lines cross keeps the covered entries balanced.
Follow-through applies from an error in earlier working.
Marker: applies the Hungarian algorithm until the minimum number of lines to cover the zeros equals 4
Choose one zero in each row and each column. Ruby’s only zero is North and Kai’s only zero is South, so Tom takes West and Isla takes East.
$$\begin{array}{l|cccc} & \text{North} & \text{South} & \text{East} & \text{West}\\\hline \text{Ruby} & [0] & 14 & 15 & 4\\\text{Tom} & 0 & 0 & 5 & [0]\\\text{Isla} & 3 & 10 & [0] & 0\\\text{Kai} & 2 & [0] & 2 & 11\end{array}$$
Ruby to North, Tom to West, Isla to East, Kai to South
Each representative takes a zero, with exactly one zero chosen in each row and each column. Start with the rows that have only one zero.
An allocation clearly shown on a matrix or bipartite graph also earns this mark.
Marker: determines the optimal allocation
Total the allocated values from the original sales table.
$$\text{Maximum total}=27+18+26+28=99$$
The total comes from the original sales table, not from the reduced matrix.
An equivalent value, for example 99 ($ thousand), also earns this mark.
Marker: determines the maximum total expected monthly sales
Subtract each value from the largest value in its own row: Ruby 27, Tom 20, Isla 26, Kai 28.
$$\begin{array}{l|cccc} & \text{North} & \text{South} & \text{East} & \text{West}\\\hline \text{Ruby} & 0 & 12 & 15 & 4\\\text{Tom} & 2 & 0 & 7 & 2\\\text{Isla} & 3 & 8 & 0 & 0\\\text{Kai} & 4 & 0 & 4 & 13\end{array}$$
Subtracting from the largest value in each row converts to a minimisation and reduces the rows in one move.
Marker: converts the table to a minimisation matrix
Every row already has a zero, so only the columns remain to reduce. Each column’s smallest value is 0, so the matrix is unchanged.
Column reduction makes a zero in every column, and here every column already has one.
Marker: correctly reduces rows and columns
Continue exactly as in Method 1, Steps 3 to 5: 3 lines, adjust by 2, 4 lines, then the same allocation and total.
$$\begin{array}{l|cccc} & \text{North} & \text{South} & \text{East} & \text{West}\\\hline \text{Ruby} & [0] & 14 & 15 & 4\\\text{Tom} & 0 & 0 & 5 & [0]\\\text{Isla} & 3 & 10 & [0] & 0\\\text{Kai} & 2 & [0] & 2 & 11\end{array}$$
$$\text{Maximum total}=27+18+26+28=99$$
Marker: applies the Hungarian algorithm until the minimum number of lines to cover the zeros equals 4
Marker: determines the optimal allocation
Marker: determines the maximum total expected monthly sales
If I had to guess where you might lose marks…
- Running the algorithm on the sales table without converting it. That finds the smallest total (Ruby to East, Tom to North, Isla to South, Kai to West, $12+18+18+15=63$) and loses Mark 1.
- Giving Tom his best region, South, before running the algorithm. The best allocation left is Ruby to North, Tom to South, Isla to West, Kai to East, $27+20+26+24=97$, which loses Marks 4 and 5.
- Adding 2 to every covered value instead of only where lines cross. Ruby’s row becomes 2, 14, 17, 6, with no zero, and the adjustment loses Mark 3.
- Adding the allocated values from the converted matrix ($1+10+2+0=13$) instead of the original table. This loses Mark 5.
- Writing the total as $99 instead of $99 000 or 99 ($ thousand). This loses Mark 5.
Only mark this done when you could do it without help. Reading the solution does not count.
A Tangent Tuition mock exam question. It is not a past QCAA question, and Tangent Tuition is not affiliated with the QCAA.
Spot a mistake on this page? Report it