Question 2 - A-Level Maths

AQA D2 2012 June — Question 2 10 marks

Exam Board	AQA
Module	D2 (Decision Mathematics 2)
Year	2012
Session	June
Marks	10
Paper	Download PDF ↗
Mark scheme	Download PDF ↗
Topic	Matchings and Allocation
Type	Hungarian algorithm with restrictions
Difficulty	Standard +0.3 This is a standard Hungarian algorithm application with a minor complication (two forbidden assignments). The algorithm itself is mechanical and well-practiced in D2, and handling restrictions by using large dummy values is a routine technique explicitly taught for this scenario.
Spec	7.04a Shortest path: Dijkstra's algorithm 7.04b Minimum spanning tree: Prim's and Kruskal's algorithms

2 The times taken in minutes for five people, Ann, Baz, Cal, Di and Ez, to complete each of five different tasks are recorded in the table below. Neither Ann nor Di can do task 2, as indicated by the asterisks in the table.

Show mark scheme Show mark scheme source

Question 2:

Part (a)

Answer	Marks	Guidance
Answer	Marks	Guidance
Row reduction (subtract row minima): rows mins are 13, 18, 15, 16, 20	M1	Correct row reduction
Reduced matrix shown correctly	A1
Cover zeros with 4 lines	A1	Correct covering shown
Total:	3

Part (b)

Answer	Marks	Guidance
Answer	Marks	Guidance
Column reduction applied to uncovered elements	M1	Correct adjustment value identified
Adjustment made to produce table requiring 5 lines	A1 A1
Total:	3

Part (c)

Answer	Marks	Guidance
Answer	Marks	Guidance
Optimal allocations identified from zero positions	M1
e.g. Ann–Task1, Baz–Task4, Cal–Task2, Di–Task3, Ez–Task5	A1 A1	Award marks for valid complete allocations
Total:	3

Part (d)

Answer	Marks	Guidance
Answer	Marks	Guidance
Minimum total time = \(\mathbf{84}\) minutes	B1
Total:	1

# Question 2:

## Part (a)

| Answer | Marks | Guidance |
|--------|-------|----------|
| Row reduction (subtract row minima): rows mins are 13, 18, 15, 16, 20 | M1 | Correct row reduction |
| Reduced matrix shown correctly | A1 | |
| Cover zeros with 4 lines | A1 | Correct covering shown |
| Total: | **3** | |

## Part (b)

| Answer | Marks | Guidance |
|--------|-------|----------|
| Column reduction applied to uncovered elements | M1 | Correct adjustment value identified |
| Adjustment made to produce table requiring 5 lines | A1 A1 | |
| Total: | **3** | |

## Part (c)

| Answer | Marks | Guidance |
|--------|-------|----------|
| Optimal allocations identified from zero positions | M1 | |
| e.g. Ann–Task1, Baz–Task4, Cal–Task2, Di–Task3, Ez–Task5 | A1 A1 | Award marks for valid complete allocations |
| Total: | **3** | |

## Part (d)

| Answer | Marks | Guidance |
|--------|-------|----------|
| Minimum total time = $\mathbf{84}$ minutes | B1 | |
| Total: | **1** | |

---

Show LaTeX source

2 The times taken in minutes for five people, Ann, Baz, Cal, Di and Ez, to complete each of five different tasks are recorded in the table below. Neither Ann nor Di can do task 2, as indicated by the asterisks in the table.

\hfill \mbox{\textit{AQA D2 2012 Q2 [10]}}

This paper (6 questions)

View full paper

Q1 14 Q2 10 Q3 14 Q4 11 Q5 10 Q6 16