Question 1 - A-Level Maths

Edexcel FD2 AS 2023 June — Question 1 9 marks

Exam Board	Edexcel
Module	FD2 AS (Further Decision 2 AS)
Year	2023
Session	June
Marks	9
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 minor modifications for restrictions (replacing forbidden entries with large values) and handling unequal matrix dimensions (5 workers, 4 tasks). The algorithm itself is mechanical once set up, requiring only routine row/column reduction and covering lines. The conceptual demand is low—students follow a learned procedure with no novel problem-solving required.
Spec	7.03k Sorting: quick sort

Five workers, A, B, C, D and E, are available to complete four tasks, P, Q, R and S.

Each worker can only be assigned to at most one task, and each task must be done by at most one worker. Worker B cannot be assigned to task Q and worker E cannot be assigned to task S.
The time, in minutes, that each worker takes to complete each task is shown in the table below.

	P	Q	R	S
A	38	39	37	37
B	39	-	39	40
C	41	44	40	42
D	40	41	39	38
E	36	39	41	-

The Hungarian algorithm is to be used to find the least total time to complete all four tasks.

Explain how the table should be modified so that the Hungarian algorithm can be applied.
1. Use the Hungarian algorithm to obtain an allocation that minimises the total time.
2. Explain how you determined if the table was optimal at each stage.
Calculate the least total time to complete all four tasks.

Show mark scheme Show mark scheme source

Question 1:

Part 1(a):

Answer	Marks	Guidance
Answer/Working	Mark	Guidance
Add an additional dummy column with equal values (e.g. 0) to create a square array	B1	AO 3.5c
Input a suitable large number (e.g. 100 but \(> 44\)) in cells BQ and ES	B1	AO 1.1b
Total: (2)

Part 1(b):

Answer	Marks	Guidance
Answer/Working	Mark	Guidance
Example augmented matrix with dummy column X added; reducing rows and columns to give reduced matrix with zeros	B1	AO 1.1b — initial augmented matrix
Three lines required to cover zeros; solution not optimal; second reduction performed	M1	AO 1.1b
Four lines required to cover zeros; solution not optimal; third reduction performed	M1	AO 1.1b
Further reduction giving two possible matrices (or equivalent); five lines required to cover zeros	M1	AO 1.1b
Five lines required to cover zeros, hence solution is optimal	B1	AO 2.4
Allocation: A to Q, B to R, D to S, and E to P (C does no task)	A1	AO 2.2a
Total: (6)

Part 1(c):

Answer	Marks	Guidance
Answer/Working	Mark	Guidance
\(152\) (mins)	B1	AO 1.1b
Total: (1)

Overall Total: (9 marks)

Question 1:

Part (a)

Answer	Marks	Guidance
Answer	Mark	Guidance
Explain the need to add a dummy column to create a square array	B1	Must mention it is a column being added; ignore mention of values added
Input a large value in cells BQ and ES	B1	"Input a large value in the empty cells" is sufficient; do not need to know what 'large' means

Part (b)

Answer	Marks	Guidance
Answer	Mark	Guidance
Addition of extra column and large values (\(>44\)) in cells BQ and ES	B1	Both steps must be complete
Simplifying the initial matrix by reducing rows and columns	M1	Allow at most 2 slips
Develop improved solution: one double covered \(+e\); one uncovered \(-e\); one single covered unchanged. 3 lines to 4 lines	M1	—
Develop improved solution: 4 lines to 5 lines (reaching optimal table)	M1	—
Correct statement(s) regarding minimum number of lines to cover zeros at each stage, OR general statement covering all augmentations	B1	Must state number of lines, use word 'optimal', and mention 'zeros' at least once
Correct final table + deduction of correct allocation	A1	cso

Special case: If dashes not replaced with values \(>44\), only M marks available in (b).

Part (c)

Answer	Marks	Guidance
Answer	Mark	Guidance
Correct answer	B1	cao

# Question 1:

## Part 1(a):

| Answer/Working | Mark | Guidance |
|---|---|---|
| Add an additional dummy column with equal values (e.g. 0) to create a square array | B1 | AO 3.5c |
| Input a suitable large number (e.g. 100 but $> 44$) in cells BQ and ES | B1 | AO 1.1b |
| **Total: (2)** | | |

## Part 1(b):

| Answer/Working | Mark | Guidance |
|---|---|---|
| Example augmented matrix with dummy column X added; reducing rows and columns to give reduced matrix with zeros | B1 | AO 1.1b — initial augmented matrix |
| Three lines required to cover zeros; solution not optimal; second reduction performed | M1 | AO 1.1b |
| Four lines required to cover zeros; solution not optimal; third reduction performed | M1 | AO 1.1b |
| Further reduction giving two possible matrices (or equivalent); five lines required to cover zeros | M1 | AO 1.1b |
| Five lines required to cover zeros, hence solution is optimal | B1 | AO 2.4 |
| Allocation: A to Q, B to R, D to S, and E to P (C does no task) | A1 | AO 2.2a |
| **Total: (6)** | | |

## Part 1(c):

| Answer/Working | Mark | Guidance |
|---|---|---|
| $152$ (mins) | B1 | AO 1.1b |
| **Total: (1)** | | |

**Overall Total: (9 marks)**

# Question 1:

## Part (a)
| Answer | Mark | Guidance |
|--------|------|----------|
| Explain the need to add a dummy column to create a square array | B1 | Must mention it is a column being added; ignore mention of values added |
| Input a large value in cells BQ and ES | B1 | "Input a large value in the empty cells" is sufficient; do not need to know what 'large' means |

## Part (b)
| Answer | Mark | Guidance |
|--------|------|----------|
| Addition of extra column and large values ($>44$) in cells BQ and ES | B1 | Both steps must be complete |
| Simplifying the initial matrix by reducing rows and columns | M1 | Allow at most 2 slips |
| Develop improved solution: one double covered $+e$; one uncovered $-e$; one single covered unchanged. 3 lines to 4 lines | M1 | — |
| Develop improved solution: 4 lines to 5 lines (reaching optimal table) | M1 | — |
| Correct statement(s) regarding minimum number of lines to cover zeros at each stage, OR general statement covering all augmentations | B1 | Must state number of lines, use word 'optimal', and mention 'zeros' at least once |
| Correct final table + deduction of correct allocation | A1 | cso |

**Special case:** If dashes not replaced with values $>44$, only M marks available in (b).

## Part (c)
| Answer | Mark | Guidance |
|--------|------|----------|
| Correct answer | B1 | cao |

---

Show LaTeX source

\begin{enumerate}
  \item Five workers, A, B, C, D and E, are available to complete four tasks, P, Q, R and S.
\end{enumerate}

Each worker can only be assigned to at most one task, and each task must be done by at most one worker.

Worker B cannot be assigned to task Q and worker E cannot be assigned to task S.\\
The time, in minutes, that each worker takes to complete each task is shown in the table below.

\begin{center}
\begin{tabular}{|l|l|l|l|l|}
\hline
 & P & Q & R & S \\
\hline
A & 38 & 39 & 37 & 37 \\
\hline
B & 39 & - & 39 & 40 \\
\hline
C & 41 & 44 & 40 & 42 \\
\hline
D & 40 & 41 & 39 & 38 \\
\hline
E & 36 & 39 & 41 & - \\
\hline
\end{tabular}
\end{center}

The Hungarian algorithm is to be used to find the least total time to complete all four tasks.\\
(a) Explain how the table should be modified so that the Hungarian algorithm can be applied.\\
(b) (i) Use the Hungarian algorithm to obtain an allocation that minimises the total time.\\
(ii) Explain how you determined if the table was optimal at each stage.\\
(c) Calculate the least total time to complete all four tasks.\\

\hfill \mbox{\textit{Edexcel FD2 AS 2023 Q1 [9]}}

This paper (4 questions)

View full paper

Q1 9 Q2 9 Q3 14 Q4 8