Further Maths Allocation (assignment) Practice Questions

Free Further Maths Allocation (assignment) practice questions with full step-by-step worked solutions. Covers allocation, hungarian, row-reduction, column-reduction. Practise exam-style problems and check your method.

allocationhungarianrow-reductioncolumn-reductionassignmenttotal-cost
Further Maths70 questionsStep-by-step solutions
Question 1
2 markseasy
The table shows the cost of assigning each worker WiW_i to each job JjJ_j:   J1J2J3W1225W2163W3811\begin{array}{c|ccc} \; & J_{1} & J_{2} & J_{3} \\ \hline W_{1} & 2 & 2 & 5 \\ W_{2} & 1 & 6 & 3 \\ W_{3} & 8 & 1 & 1 \end{array}. After row reduction (subtracting the smallest entry in each row from that row), write down the entry in row 11 and column 33 of the row-reduced matrix.
Show worked solution

Worked solution

  1. Find the smallest entry in row 11

    min⁡(2,2,5)=2\min(2,2,5)=2

    Row reduction subtracts the smallest entry of a row from every entry of that row.

  2. Subtract the row minimum throughout the matrix

      J1J2J3W1003W2052W3700\begin{array}{c|ccc} \; & J_{1} & J_{2} & J_{3} \\ \hline W_{1} & 0 & 0 & 3 \\ W_{2} & 0 & 5 & 2 \\ W_{3} & 7 & 0 & 0 \end{array}

    Doing this for every row is the first stage of the Hungarian algorithm.

  3. State the required entry

    row 1, column 3: 3\text{row }1,\ \text{column }3:\ 3

    This is the entry of the row-reduced matrix in that position.

Answer
33
Question 2
2 markseasy
The table shows the cost of assigning each worker WiW_i to each job JjJ_j:   J1J2J3J4W11582W27175W39516W44138\begin{array}{c|cccc} \; & J_{1} & J_{2} & J_{3} & J_{4} \\ \hline W_{1} & 1 & 5 & 8 & 2 \\ W_{2} & 7 & 1 & 7 & 5 \\ W_{3} & 9 & 5 & 1 & 6 \\ W_{4} & 4 & 1 & 3 & 8 \end{array}. A proposed assignment is W1→J4, W2→J3, W3→J2, W4→J1W_{1} \to J_{4},\ W_{2} \to J_{3},\ W_{3} \to J_{2},\ W_{4} \to J_{1}. Which of the following is the total cost of this assignment?
Show worked solution

Worked solution

  1. Read off the cost of each pairing

    W1→J4: 2, W2→J3: 7, W3→J2: 5, W4→J1: 4W_{1}\to J_{4}:\ 2,\ W_{2}\to J_{3}:\ 7,\ W_{3}\to J_{2}:\ 5,\ W_{4}\to J_{1}:\ 4

    Each worker contributes the entry in their own row and assigned column.

  2. Add the individual costs

    2+7+5+4=182+7+5+4=18

    The total cost is the sum of the chosen entries.

  3. Recall what the Hungarian algorithm does

    Hungarian algorithm⇒minimum-cost assignment\text{Hungarian algorithm}\Rightarrow\text{minimum-cost assignment}

    It finds an assignment of each worker to exactly one job that minimises the total cost.

  4. Select the total cost

    total cost=18\text{total cost}=18

    This is the cost of the stated assignment.

Answer
total cost=18\text{total cost}=18
Question 3
4 marksintermediate
The table shows the profit (in pounds) from assigning each worker WiW_i to each job JjJ_j:   J1J2J3J4W18845W25656W34646W47529\begin{array}{c|cccc} \; & J_{1} & J_{2} & J_{3} & J_{4} \\ \hline W_{1} & 8 & 8 & 4 & 5 \\ W_{2} & 5 & 6 & 5 & 6 \\ W_{3} & 4 & 6 & 4 & 6 \\ W_{4} & 7 & 5 & 2 & 9 \end{array}. A proposed assignment is W1→J4, W2→J2, W3→J3, W4→J1W_{1} \to J_{4},\ W_{2} \to J_{2},\ W_{3} \to J_{3},\ W_{4} \to J_{1}. Which of the following is the total profit of this assignment?
Show worked solution

Worked solution

  1. Read off the profit of each pairing

    W1→J4: 5, W2→J2: 6, W3→J3: 4, W4→J1: 7W_{1}\to J_{4}:\ 5,\ W_{2}\to J_{2}:\ 6,\ W_{3}\to J_{3}:\ 4,\ W_{4}\to J_{1}:\ 7

    Each worker contributes the entry in their own row and assigned column.

  2. Add the individual profits

    5+6+4+7=225+6+4+7=22

    The total profit is the sum of the chosen entries.

  3. Recall what the Hungarian algorithm does

    Hungarian algorithm⇒minimum-cost assignment\text{Hungarian algorithm}\Rightarrow\text{minimum-cost assignment}

    It finds an assignment of each worker to exactly one job that minimises the total cost.

  4. Recall the row-reduction step

    cij→cij−min⁡jcijc_{ij}\to c_{ij}-\min_j c_{ij}

    Subtracting the smallest entry of each row from that row creates a zero in every row.

  5. Recall the column-reduction step

    cij→cij−min⁡icijc_{ij}\to c_{ij}-\min_i c_{ij}

    Subtracting the smallest entry of each column from that column creates a zero in every column.

  6. Recall the optimality test

    minimum covering lines=n  ⟺  optimal assignment exists\text{minimum covering lines}=n\iff\text{optimal assignment exists}

    An assignment of zero reduced cost exists exactly when n lines are needed to cover the zeros.

  7. Select the total profit

    total profit=22\text{total profit}=22

    This is the profit of the stated assignment.

Answer
total profit=22\text{total profit}=22
Question 4
6 markshard
The table shows the cost of assigning each worker WiW_i to each job JjJ_j:   J1J2J3J4W11157W22461W36885W41395\begin{array}{c|cccc} \; & J_{1} & J_{2} & J_{3} & J_{4} \\ \hline W_{1} & 1 & 1 & 5 & 7 \\ W_{2} & 2 & 4 & 6 & 1 \\ W_{3} & 6 & 8 & 8 & 5 \\ W_{4} & 1 & 3 & 9 & 5 \end{array}. Use the Hungarian algorithm to allocate each worker to a different job so as to minimise the total cost. Which of the following is the optimal assignment?
Show worked solution

Worked solution

  1. Write down the cost matrix to be minimised

      J1J2J3J4W11157W22461W36885W41395\begin{array}{c|cccc} \; & J_{1} & J_{2} & J_{3} & J_{4} \\ \hline W_{1} & 1 & 1 & 5 & 7 \\ W_{2} & 2 & 4 & 6 & 1 \\ W_{3} & 6 & 8 & 8 & 5 \\ W_{4} & 1 & 3 & 9 & 5 \end{array}

    Each worker must be assigned to exactly one job.

  2. Row reduction: subtract the smallest entry of each row

      J1J2J3J4W10046W21350W31330W40284\begin{array}{c|cccc} \; & J_{1} & J_{2} & J_{3} & J_{4} \\ \hline W_{1} & 0 & 0 & 4 & 6 \\ W_{2} & 1 & 3 & 5 & 0 \\ W_{3} & 1 & 3 & 3 & 0 \\ W_{4} & 0 & 2 & 8 & 4 \end{array}

    This creates at least one zero in every row.

  3. Column reduction: subtract the smallest entry of each column

      J1J2J3J4W10016W21320W31300W40254\begin{array}{c|cccc} \; & J_{1} & J_{2} & J_{3} & J_{4} \\ \hline W_{1} & 0 & 0 & 1 & 6 \\ W_{2} & 1 & 3 & 2 & 0 \\ W_{3} & 1 & 3 & 0 & 0 \\ W_{4} & 0 & 2 & 5 & 4 \end{array}

    This creates at least one zero in every column.

  4. Check optimality: nn lines are now needed

    minimum covering lines=4=n\text{minimum covering lines}=4=n

    When the minimum number of covering lines equals nn, a complete assignment of zeros exists.

  5. Select a complete set of zeros, one in each row and column

    W1→J2, W2→J4, W3→J3, W4→J1W_{1} \to J_{2},\ W_{2} \to J_{4},\ W_{3} \to J_{3},\ W_{4} \to J_{1}

    These zeros give an assignment of zero reduced cost, which is optimal.

  6. Confirm no assignment does better

    W1→J1, W2→J4, W3→J3, W4→J2: 13 ≥ 11W_{1} \to J_{1},\ W_{2} \to J_{4},\ W_{3} \to J_{3},\ W_{4} \to J_{2}:\ 13\ \ge\ 11

    The next best assignment is strictly worse, so the optimum is unique.

  7. Compute the total from the original table

    1+1+8+1=111+1+8+1=11

    The reductions found the assignment; its cost is the sum of the original entries.

  8. Recall what the Hungarian algorithm does

    Hungarian algorithm⇒minimum-cost assignment\text{Hungarian algorithm}\Rightarrow\text{minimum-cost assignment}

    It finds an assignment of each worker to exactly one job that minimises the total cost.

  9. Recall the row-reduction step

    cij→cij−min⁡jcijc_{ij}\to c_{ij}-\min_j c_{ij}

    Subtracting the smallest entry of each row from that row creates a zero in every row.

  10. Select the optimal assignment

    W1→J2, W2→J4, W3→J3, W4→J1W_{1} \to J_{2},\ W_{2} \to J_{4},\ W_{3} \to J_{3},\ W_{4} \to J_{1}

    This assignment attains the minimum total cost.

Answer
W1→J2, W2→J4, W3→J3, W4→J1W_{1} \to J_{2},\ W_{2} \to J_{4},\ W_{3} \to J_{3},\ W_{4} \to J_{1}
Question 5
9 markschallenging
The table shows the profit (in pounds) from assigning each worker WiW_i to each job JjJ_j:   J1J2J3J4J5W197278W225338W336468W431176\begin{array}{c|ccccc} \; & J_{1} & J_{2} & J_{3} & J_{4} & J_{5} \\ \hline W_{1} & 9 & 7 & 2 & 7 & 8 \\ W_{2} & 2 & 5 & 3 & 3 & 8 \\ W_{3} & 3 & 6 & 4 & 6 & 8 \\ W_{4} & 3 & 1 & 1 & 7 & 6 \end{array}. There are more jobs than workers, so a dummy row (a dummy worker) of equal costs is added to square the matrix. Use the Hungarian algorithm to find the maximum total profit.
Show worked solution

Worked solution

  1. Convert the maximisation to a minimisation

    M=9,cij′=M−cij:  J1J2J3J4J5W102721W274661W363531W468823W599999M=9,\quad c'_{ij}=M-c_{ij}:\quad \begin{array}{c|ccccc} \; & J_{1} & J_{2} & J_{3} & J_{4} & J_{5} \\ \hline W_{1} & 0 & 2 & 7 & 2 & 1 \\ W_{2} & 7 & 4 & 6 & 6 & 1 \\ W_{3} & 6 & 3 & 5 & 3 & 1 \\ W_{4} & 6 & 8 & 8 & 2 & 3 \\ W_{5} & 9 & 9 & 9 & 9 & 9 \end{array}

    Subtracting every profit from the largest profit MM makes the problem a minimisation.

  2. Add a dummy row/column of equal costs

    add 1 dummy rows of 0 cost\text{add }1\text{ dummy rows of }0\text{ cost}

    The dummy has equal (zero) costs and squares the matrix without affecting the real assignment.

  3. Row reduction: subtract the smallest entry of each row

      J1J2J3J4J5W102721W263550W352420W446601W500000\begin{array}{c|ccccc} \; & J_{1} & J_{2} & J_{3} & J_{4} & J_{5} \\ \hline W_{1} & 0 & 2 & 7 & 2 & 1 \\ W_{2} & 6 & 3 & 5 & 5 & 0 \\ W_{3} & 5 & 2 & 4 & 2 & 0 \\ W_{4} & 4 & 6 & 6 & 0 & 1 \\ W_{5} & 0 & 0 & 0 & 0 & 0 \end{array}

    This creates at least one zero in every row.

  4. Column reduction leaves the matrix unchanged

    each column already contains a 0\text{each column already contains a }0

    Every column already has a zero, so nothing is subtracted.

  5. Cover the zeros with the fewest lines (iteration 1)

    rows {1,4,5}, cols {5}, lines=4<5\text{rows }\{1,4,5\},\ \text{cols }\{5\},\ \text{lines}=4<5

    Fewer than nn lines means the matrix is not yet optimal.

  6. Augment: subtract θ\theta from uncovered entries, add at intersections

    θ=2:  J1J2J3J4J5W102723W241330W330200W446603W500002\theta=2:\quad \begin{array}{c|ccccc} \; & J_{1} & J_{2} & J_{3} & J_{4} & J_{5} \\ \hline W_{1} & 0 & 2 & 7 & 2 & 3 \\ W_{2} & 4 & 1 & 3 & 3 & 0 \\ W_{3} & 3 & 0 & 2 & 0 & 0 \\ W_{4} & 4 & 6 & 6 & 0 & 3 \\ W_{5} & 0 & 0 & 0 & 0 & 2 \end{array}

    This creates a new zero while keeping every entry non-negative.

  7. Check optimality: nn lines are now needed

    minimum covering lines=5=n\text{minimum covering lines}=5=n

    When the minimum number of covering lines equals nn, a complete assignment of zeros exists.

  8. Select a complete set of zeros, one in each row and column

    W1→J1, W2→J5, W3→J2, W4→J4, W5→J3W_{1} \to J_{1},\ W_{2} \to J_{5},\ W_{3} \to J_{2},\ W_{4} \to J_{4},\ W_{5} \to J_{3}

    These zeros give an assignment of zero reduced cost, which is optimal.

  9. Confirm no assignment does better

    W1→J1, W2→J2, W3→J5, W4→J4, W5→J3: 29 ≤ 30W_{1} \to J_{1},\ W_{2} \to J_{2},\ W_{3} \to J_{5},\ W_{4} \to J_{4},\ W_{5} \to J_{3}:\ 29\ \le\ 30

    The next best assignment is strictly worse, so the optimum is unique.

  10. Compute the total from the original table

    9+8+6+7+0=309+8+6+7+0=30

    The reductions found the assignment; its profit is the sum of the original entries.

  11. Recall what the Hungarian algorithm does

    Hungarian algorithm⇒minimum-cost assignment\text{Hungarian algorithm}\Rightarrow\text{minimum-cost assignment}

    It finds an assignment of each worker to exactly one job that minimises the total cost.

  12. Recall the row-reduction step

    cij→cij−min⁡jcijc_{ij}\to c_{ij}-\min_j c_{ij}

    Subtracting the smallest entry of each row from that row creates a zero in every row.

  13. Recall the column-reduction step

    cij→cij−min⁡icijc_{ij}\to c_{ij}-\min_i c_{ij}

    Subtracting the smallest entry of each column from that column creates a zero in every column.

  14. Recall the optimality test

    minimum covering lines=n  ⟺  optimal assignment exists\text{minimum covering lines}=n\iff\text{optimal assignment exists}

    An assignment of zero reduced cost exists exactly when n lines are needed to cover the zeros.

  15. State the maximum total profit

    maximum total profit=30\text{maximum total profit}=30

    The dummy assignments cost nothing, so this is the real optimum.

Answer
maximum total profit=30\text{maximum total profit}=30

Unlock 65 more Allocation (assignment) questions

Create a free account to work through every Further Maths Allocation (assignment) question with instant step-by-step worked solutions, progress tracking and interactive lessons.

  • Full worked solutions for every question
  • Interactive lessons and instant feedback
  • Track your mastery across every topic
Create a Free Account

No card required · Free forever

More Allocation (assignment) practice

Hard QuestionsWorked Solutions

Related Decision Maths topics

AlgorithmsCritical path analysisDecision analysisDynamic programmingFlows in networksGame theory