Hard Further Maths Allocation (assignment) Questions

Challenging, exam-style Further Maths Allocation (assignment) questions with worked solutions. Stretch yourself on the hardest allocation, hungarian, optimal-assignment, maximisation problems.

allocationhungarianoptimal-assignmentmaximisationunbalancedforbidden
Further Maths34 questionsStep-by-step solutions
Question 1
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
Question 2
9 markschallenging
The table shows the profit (in pounds) from assigning each worker WiW_i to each job JjJ_j:   J1J2J3J4J5W177157W254157W382362W471529\begin{array}{c|ccccc} \; & J_{1} & J_{2} & J_{3} & J_{4} & J_{5} \\ \hline W_{1} & 7 & 7 & 1 & 5 & 7 \\ W_{2} & 5 & 4 & 1 & 5 & 7 \\ W_{3} & 8 & 2 & 3 & 6 & 2 \\ W_{4} & 7 & 1 & 5 & 2 & 9 \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:  J1J2J3J4J5W122842W245842W317637W428470W599999M=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} & 2 & 2 & 8 & 4 & 2 \\ W_{2} & 4 & 5 & 8 & 4 & 2 \\ W_{3} & 1 & 7 & 6 & 3 & 7 \\ W_{4} & 2 & 8 & 4 & 7 & 0 \\ 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

      J1J2J3J4J5W100620W223620W306526W428470W500000\begin{array}{c|ccccc} \; & J_{1} & J_{2} & J_{3} & J_{4} & J_{5} \\ \hline W_{1} & 0 & 0 & 6 & 2 & 0 \\ W_{2} & 2 & 3 & 6 & 2 & 0 \\ W_{3} & 0 & 6 & 5 & 2 & 6 \\ W_{4} & 2 & 8 & 4 & 7 & 0 \\ 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,3,5}, cols {5}, lines=4<5\text{rows }\{1,3,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:  J1J2J3J4J5W100622W201400W306528W406250W500002\theta=2:\quad \begin{array}{c|ccccc} \; & J_{1} & J_{2} & J_{3} & J_{4} & J_{5} \\ \hline W_{1} & 0 & 0 & 6 & 2 & 2 \\ W_{2} & 0 & 1 & 4 & 0 & 0 \\ W_{3} & 0 & 6 & 5 & 2 & 8 \\ W_{4} & 0 & 6 & 2 & 5 & 0 \\ 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→J2, W2→J4, W3→J1, W4→J5, W5→J3W_{1} \to J_{2},\ W_{2} \to J_{4},\ W_{3} \to J_{1},\ W_{4} \to J_{5},\ W_{5} \to J_{3}

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

  9. Confirm no assignment does better

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

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

  10. Compute the total from the original table

    7+5+8+9+0=297+5+8+9+0=29

    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. Recall the augmenting step

    subtract θ from uncovered, add θ at intersections\text{subtract }\theta\text{ from uncovered},\ \text{add }\theta\text{ at intersections}

    Here theta is the smallest uncovered entry; this creates a new zero while keeping every entry non-negative.

  16. State the maximum total profit

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

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

Answer
maximum total profit=29\text{maximum total profit}=29
Question 3
9 markschallenging
The table shows the cost of assigning each worker WiW_i to each job JjJ_j:   J1J2J3J4W15896W23592W36852W42769\begin{array}{c|cccc} \; & J_{1} & J_{2} & J_{3} & J_{4} \\ \hline W_{1} & 5 & 8 & 9 & 6 \\ W_{2} & 3 & 5 & 9 & 2 \\ W_{3} & 6 & 8 & 5 & 2 \\ W_{4} & 2 & 7 & 6 & 9 \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

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

    Each worker must be assigned to exactly one job.

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

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

    This creates at least one zero in every row.

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

      J1J2J3J4W10011W21040W34300W40217\begin{array}{c|cccc} \; & J_{1} & J_{2} & J_{3} & J_{4} \\ \hline W_{1} & 0 & 0 & 1 & 1 \\ W_{2} & 1 & 0 & 4 & 0 \\ W_{3} & 4 & 3 & 0 & 0 \\ W_{4} & 0 & 2 & 1 & 7 \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→J2, W3→J4, W4→J3: 18 ≥ 17W_{1} \to J_{1},\ W_{2} \to J_{2},\ W_{3} \to J_{4},\ W_{4} \to J_{3}:\ 18\ \ge\ 17

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

  7. Compute the total from the original table

    8+2+5+2=178+2+5+2=17

    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. 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.

  11. 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.

  12. Recall the augmenting step

    subtract θ from uncovered, add θ at intersections\text{subtract }\theta\text{ from uncovered},\ \text{add }\theta\text{ at intersections}

    Here theta is the smallest uncovered entry; this creates a new zero while keeping every entry non-negative.

  13. Note that reducing a row or column does not change the optimal assignment

    arg⁡min⁡ is unchanged by subtracting a constant from a row or column\arg\min\text{ is unchanged by subtracting a constant from a row or column}

    Subtracting a constant from a whole row or column changes every total by the same amount.

  14. Note that each worker is assigned to exactly one job

    assignment=a permutation of the jobs\text{assignment}=\text{a permutation of the jobs}

    A valid allocation matches workers to jobs one-to-one, so it is a permutation.

  15. 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 4
9 markschallenging
The table shows the profit (in pounds) from assigning each worker WiW_i to each job JjJ_j:   J1J2J3J4W19847W21172W36123W49651\begin{array}{c|cccc} \; & J_{1} & J_{2} & J_{3} & J_{4} \\ \hline W_{1} & 9 & 8 & 4 & 7 \\ W_{2} & 1 & 1 & 7 & 2 \\ W_{3} & 6 & 1 & 2 & 3 \\ W_{4} & 9 & 6 & 5 & 1 \end{array}. Use the Hungarian algorithm to allocate each worker to a different job. Which of the following is the maximum total profit?
Show worked solution

Worked solution

  1. Convert the maximisation to a minimisation

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

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

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

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

    This creates at least one zero in every row.

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

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

    This creates at least one zero in every column.

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

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

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

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

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

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

  6. 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.

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

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

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

  8. Confirm no assignment does better

    W1→J4, W2→J3, W3→J1, W4→J2: 26 ≤ 27W_{1} \to J_{4},\ W_{2} \to J_{3},\ W_{3} \to J_{1},\ W_{4} \to J_{2}:\ 26\ \le\ 27

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

  9. Compute the total from the original table

    8+7+3+9=278+7+3+9=27

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

  10. 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.

  11. 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.

  12. 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.

  13. 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.

  14. Recall the augmenting step

    subtract θ from uncovered, add θ at intersections\text{subtract }\theta\text{ from uncovered},\ \text{add }\theta\text{ at intersections}

    Here theta is the smallest uncovered entry; this creates a new zero while keeping every entry non-negative.

  15. Note that reducing a row or column does not change the optimal assignment

    arg⁡min⁡ is unchanged by subtracting a constant from a row or column\arg\min\text{ is unchanged by subtracting a constant from a row or column}

    Subtracting a constant from a whole row or column changes every total by the same amount.

  16. Select the maximum total profit

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

    This is the optimal value of the allocation.

Answer
maximum total profit=27\text{maximum total profit}=27
Question 5
9 markschallenging
The table shows the profit (in pounds) from assigning each worker WiW_i to each job JjJ_j:   J1J2J3J4J5W162481W233886W321488W462594W525629\begin{array}{c|ccccc} \; & J_{1} & J_{2} & J_{3} & J_{4} & J_{5} \\ \hline W_{1} & 6 & 2 & 4 & 8 & 1 \\ W_{2} & 3 & 3 & 8 & 8 & 6 \\ W_{3} & 2 & 1 & 4 & 8 & 8 \\ W_{4} & 6 & 2 & 5 & 9 & 4 \\ W_{5} & 2 & 5 & 6 & 2 & 9 \end{array}. Use the Hungarian algorithm to allocate each worker to a different job. Which of the following is the maximum total profit?
Show worked solution

Worked solution

  1. Convert the maximisation to a minimisation

    M=9,cij′=M−cij:  J1J2J3J4J5W137518W266113W378511W437405W574370M=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} & 3 & 7 & 5 & 1 & 8 \\ W_{2} & 6 & 6 & 1 & 1 & 3 \\ W_{3} & 7 & 8 & 5 & 1 & 1 \\ W_{4} & 3 & 7 & 4 & 0 & 5 \\ W_{5} & 7 & 4 & 3 & 7 & 0 \end{array}

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

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

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

    This creates at least one zero in every row.

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

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

    This creates at least one zero in every column.

  4. 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.

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

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

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

  6. Confirm no assignment does better

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

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

  7. Compute the total from the original table

    6+8+8+9+5=366+8+8+9+5=36

    The reductions found the assignment; its profit 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. 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.

  11. 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.

  12. Recall the augmenting step

    subtract θ from uncovered, add θ at intersections\text{subtract }\theta\text{ from uncovered},\ \text{add }\theta\text{ at intersections}

    Here theta is the smallest uncovered entry; this creates a new zero while keeping every entry non-negative.

  13. Note that reducing a row or column does not change the optimal assignment

    arg⁡min⁡ is unchanged by subtracting a constant from a row or column\arg\min\text{ is unchanged by subtracting a constant from a row or column}

    Subtracting a constant from a whole row or column changes every total by the same amount.

  14. Note that each worker is assigned to exactly one job

    assignment=a permutation of the jobs\text{assignment}=\text{a permutation of the jobs}

    A valid allocation matches workers to jobs one-to-one, so it is a permutation.

  15. Select the maximum total profit

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

    This is the optimal value of the allocation.

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

Unlock 29 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

Practice QuestionsWorked Solutions

Related Decision Maths topics

AlgorithmsCritical path analysisDecision analysisDynamic programmingFlows in networksGame theory