OCR D2 2016 June — Question 3 13 marks

Exam BoardOCR
ModuleD2 (Decision Mathematics 2)
Year2016
SessionJune
Marks13
PaperDownload PDF ↗
Mark schemeDownload PDF ↗
TopicMatchings and Allocation
TypeHungarian algorithm with unequal sets
DifficultyStandard +0.8 This is a multi-part Hungarian algorithm question requiring modification for unequal sets (4 technicians, 3 tasks), systematic row/column reduction, line covering, and interpretation. While the algorithm is mechanical once learned, the unequal sets modification, multiple steps, and part (iii) requiring re-analysis make this substantially harder than routine D2 questions but still within standard A-level scope.
Spec7.04a Shortest path: Dijkstra's algorithm
3 A theatre company needs to employ three technicians for a performance. One will operate the lights, one the sound system and one the flying trapeze mechanism. Four technicians have applied for these tasks. The table shows how much it will cost the theatre company, in £, to employ each technician for each task.
\multirow{2}{*}{}Task
LightingSoundTrapeze
\multirow{4}{*}{Technician}Amir868890
Bex929495
Caz889294
Dee9810098
The theatre company wants to employ the three technicians for whom the total cost is least.
The Hungarian algorithm is to be used to find the minimum cost allocation, but before this can be done the table needs to be modified.
  1. Make the necessary modification to the table. Working from your modified table, construct a reduced cost matrix by first reducing rows and then reducing columns. You should show the amount by which each row has been reduced in the row reductions and the amount by which each column has been reduced in the column reductions. Cross through the 0 's in your reduced cost matrix using the least possible number of horizontal or vertical lines. [You must ensure that the values in your table can still be read.]
  2. Complete the application of the Hungarian algorithm to find a minimum cost allocation. Write a list showing which technician should be employed for each task. Calculate the total cost to the theatre company. Although Amir put in the lowest cost for operating the lighting, you should have found that he has not been allocated this task. Amir is particularly keen to be employed to operate the lights so is prepared to reduce his cost for this task.
  3. Find a way to use two of Bex, Caz and Dee to operate the sound effects and the flying trapeze mechanism at the lowest cost. Hence find what Amir's new cost should be for the minimum total cost to the theatre company to be exactly \(\pounds 1\) less than your answer from part (ii).
I appreciate you sharing this content, but what you've provided appears to be only a numerical table or matrix rather than a mark scheme with marking annotations (M1, A1, B1, etc.) and guidance notes.
Could you please provide the actual mark scheme text? It should include elements like:
- Marking points with codes (M1, A1, B1, DM1, etc.)
- Expected answers or solution steps
- Guidance notes for markers
- Unicode symbols that need conversion to LaTeX
Once you share the full mark scheme content, I'll be happy to clean it up according to your specifications.
I appreciate you sharing this content, but what you've provided appears to be only a numerical table or matrix rather than a mark scheme with marking annotations (M1, A1, B1, etc.) and guidance notes.

Could you please provide the actual mark scheme text? It should include elements like:
- Marking points with codes (M1, A1, B1, DM1, etc.)
- Expected answers or solution steps
- Guidance notes for markers
- Unicode symbols that need conversion to LaTeX

Once you share the full mark scheme content, I'll be happy to clean it up according to your specifications.
3 A theatre company needs to employ three technicians for a performance. One will operate the lights, one the sound system and one the flying trapeze mechanism. Four technicians have applied for these tasks. The table shows how much it will cost the theatre company, in £, to employ each technician for each task.

\begin{center}
\begin{tabular}{|l|l|l|l|l|}
\hline
\multicolumn{2}{|c|}{\multirow{2}{*}{}} & \multicolumn{3}{|c|}{Task} \\
\hline
 &  & Lighting & Sound & Trapeze \\
\hline
\multirow{4}{*}{Technician} & Amir & 86 & 88 & 90 \\
\hline
 & Bex & 92 & 94 & 95 \\
\hline
 & Caz & 88 & 92 & 94 \\
\hline
 & Dee & 98 & 100 & 98 \\
\hline
\end{tabular}
\end{center}

The theatre company wants to employ the three technicians for whom the total cost is least.\\
The Hungarian algorithm is to be used to find the minimum cost allocation, but before this can be done the table needs to be modified.\\
(i) Make the necessary modification to the table.

Working from your modified table, construct a reduced cost matrix by first reducing rows and then reducing columns. You should show the amount by which each row has been reduced in the row reductions and the amount by which each column has been reduced in the column reductions. Cross through the 0 's in your reduced cost matrix using the least possible number of horizontal or vertical lines. [You must ensure that the values in your table can still be read.]\\
(ii) Complete the application of the Hungarian algorithm to find a minimum cost allocation. Write a list showing which technician should be employed for each task. Calculate the total cost to the theatre company.

Although Amir put in the lowest cost for operating the lighting, you should have found that he has not been allocated this task. Amir is particularly keen to be employed to operate the lights so is prepared to reduce his cost for this task.\\
(iii) Find a way to use two of Bex, Caz and Dee to operate the sound effects and the flying trapeze mechanism at the lowest cost. Hence find what Amir's new cost should be for the minimum total cost to the theatre company to be exactly $\pounds 1$ less than your answer from part (ii).

\hfill \mbox{\textit{OCR D2 2016 Q3 [13]}}
This paper (6 questions)
View full paper
Q1 7 Q2 10 Q3 13 Q4 10 Q5 16 Q6 16