Allocation (assignment) Worked Solutions — Further Maths Maths

Fully worked, step-by-step solutions to Further Maths Allocation (assignment) questions. See exactly how to solve problems on allocation, hungarian, row-reduction, column-reduction.

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.

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:   J1J2J3W1326W2921W3324\begin{array}{c|ccc} \; & J_{1} & J_{2} & J_{3} \\ \hline W_{1} & 3 & 2 & 6 \\ W_{2} & 9 & 2 & 1 \\ W_{3} & 3 & 2 & 4 \end{array}. After row reduction (subtracting the smallest entry in each row from that row), write down the entry in row 22 and column 11 of the row-reduced matrix.

Worked solution

  1. Find the smallest entry in row 22

    min⁡(9,2,1)=1\min(9,2,1)=1

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

  2. Subtract the row minimum throughout the matrix

      J1J2J3W1104W2810W3102\begin{array}{c|ccc} \; & J_{1} & J_{2} & J_{3} \\ \hline W_{1} & 1 & 0 & 4 \\ W_{2} & 8 & 1 & 0 \\ W_{3} & 1 & 0 & 2 \end{array}

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

  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. State the required entry

    row 2, column 1: 8\text{row }2,\ \text{column }1:\ 8

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

Answer
88
Question 3
2 markseasy
The table shows the cost of assigning each worker WiW_i to each job JjJ_j:   J1J2J3J4W18785W22873W36897W48369\begin{array}{c|cccc} \; & J_{1} & J_{2} & J_{3} & J_{4} \\ \hline W_{1} & 8 & 7 & 8 & 5 \\ W_{2} & 2 & 8 & 7 & 3 \\ W_{3} & 6 & 8 & 9 & 7 \\ W_{4} & 8 & 3 & 6 & 9 \end{array}. After row reduction (subtracting the smallest entry in each row from that row), write down the entry in row 33 and column 44 of the row-reduced matrix.

Worked solution

  1. Find the smallest entry in row 33

    min⁡(6,8,9,7)=6\min(6,8,9,7)=6

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

  2. Subtract the row minimum throughout the matrix

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

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

  3. State the required entry

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

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

Answer
11
Question 4
2 markseasy
The table shows the cost of assigning each worker WiW_i to each job JjJ_j:   J1J2J3W1797W2586W3651\begin{array}{c|ccc} \; & J_{1} & J_{2} & J_{3} \\ \hline W_{1} & 7 & 9 & 7 \\ W_{2} & 5 & 8 & 6 \\ W_{3} & 6 & 5 & 1 \end{array}. After row reduction followed by column reduction, write down the entry in row 22 and column 22 of the fully reduced matrix.

Worked solution

  1. Carry out row reduction

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

    Subtract the smallest entry of each row from that row.

  2. Carry out column reduction on the result

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

    Subtract the smallest entry of each column from that column.

  3. Locate the required position

    row 2, column 2\text{row }2,\ \text{column }2

    The fully reduced matrix is what the covering lines are drawn on.

  4. State the required entry

    c22′=1c'_{22}=1

    This is the entry after both reduction stages.

Answer
11
Question 5
2 markseasy
The table shows the cost of assigning each worker WiW_i to each job JjJ_j:   J1J2J3W1815W2315W3263\begin{array}{c|ccc} \; & J_{1} & J_{2} & J_{3} \\ \hline W_{1} & 8 & 1 & 5 \\ W_{2} & 3 & 1 & 5 \\ W_{3} & 2 & 6 & 3 \end{array}. After row reduction followed by column reduction, write down the entry in row 33 and column 11 of the fully reduced matrix.

Worked solution

  1. Carry out row reduction

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

    Subtract the smallest entry of each row from that row.

  2. Carry out column reduction on the result

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

    Subtract the smallest entry of each column from that column.

  3. State the required entry

    c31′=0c'_{31}=0

    This is the entry after both reduction stages.

Answer
00

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 QuestionsPractice Questions

Related Decision Maths topics

AlgorithmsCritical path analysisDecision analysisDynamic programmingFlows in networksGame theory