OCR D2 2006 January — Question 4 13 marks

Exam BoardOCR
ModuleD2 (Decision Mathematics 2)
Year2006
SessionJanuary
Marks13
PaperDownload PDF ↗
Mark schemeDownload PDF ↗
TopicMatchings and Allocation
TypeHungarian algorithm for minimisation
DifficultyModerate -0.8 This is a straightforward application of the Hungarian algorithm with clear instructions to reduce rows first. Part (i) is trivial arithmetic, part (ii) follows a standard algorithmic procedure taught in D2, and part (iii) tests basic recall. The 4×4 table is small and the algorithm is mechanical with no problem-solving insight required.
Spec7.06a LP formulation: variables, constraints, objective function7.06b Slack variables: converting inequalities to equations7.06c Working with constraints: algebra and ad hoc methods7.06d Graphical solution: feasible region, two variables
4 Four workers, \(A , B , C\) and \(D\), are to be allocated, one to each of the four jobs, \(W , X , Y\) and \(Z\). The table shows how much each worker would charge for each job. \includegraphics[max width=\textwidth, alt={}, center]{9c9b1a42-8d16-446a-85a1-4c08e5e368be-3_401_846_1745_642}
  1. What is the total cost of the four jobs if \(A\) does \(W , B\) does \(X , C\) does \(Y\) and \(D\) does \(Z\) ?
  2. Apply the Hungarian algorithm to the table, reducing rows first. Show all your working and explain each step. Give the resulting allocation and the total cost of the four jobs with this allocation.
  3. What problem does the Hungarian algorithm solve?
(i)
AnswerMarks Guidance
£260B1 For correct answer with units, or scaled throughout by 10
(ii)
Reduce rows:
```
0 60 30 10
0 90 90 60
0 80 70 40
10 10 20 0
```
AnswerMarks
M1For correct method for reducing rows
Reduce columns:
```
0 50 10 10
0 80 70 60
0 70 50 40
10 0 0 0
```
AnswerMarks
M1For correct method for reducing columns
A1For a correct reduced cost matrix
Cross through 0's using as few lines as possible:
```
0 50 10 10
0 80 70 60
0 70 50 40
10 0 0 0
```
AnswerMarks
M1For correct crossing out for their reduced cost matrix. Likely to be shown on reduced cost matrix.
Augment by 10:
```
0 40 0 0
0 70 60 50
0 60 40 30
20 0 0 0
```
AnswerMarks
M1For correct augmenting from their reduced cost matrix and their crossing out
A1For a correct solution after first augmenting
Cross through 0's using as few lines as possible:
```
0 40 0 0
0 70 60 50
0 60 40 30
20 0 0 0
```
AnswerMarks
M1For correct crossing out for their augmented matrix. Likely to be shown on matrix.
Augment by 30:
```
30 40 0 0
0 40 30 20
0 30 10 0
50 0 0 0
```
AnswerMarks
M1For correctly augmenting their matrix in one step by an amount greater than 10 (or greater than 1 if scaling has been used)
A1For correct final matrix from completely correct method
Allocation:
\(A = Y\); \(B = W\); \(C = Z\); \(D = X\); Cost \(= £180\)
AnswerMarks
B1For this allocation
B1For £180
(iii)
AnswerMarks Guidance
Hungarian algorithm finds the minimum cost complete matchingB1 For 'minimum cost' or equivalent 
**(i)**
£260 | B1 | For correct answer with units, or scaled throughout by 10

**(ii)**
Reduce rows:
```
0  60  30  10
0  90  90  60
0  80  70  40
10 10  20  0
```
| M1 | For correct method for reducing rows

Reduce columns:
```
0  50  10  10
0  80  70  60
0  70  50  40
10  0   0   0
```
| M1 | For correct method for reducing columns

| A1 | For a correct reduced cost matrix

Cross through 0's using as few lines as possible:
```
0  50  10  10
0  80  70  60
0  70  50  40
10  0   0   0
```
| M1 | For correct crossing out for their reduced cost matrix. Likely to be shown on reduced cost matrix.

Augment by 10:
```
0  40   0   0
0  70  60  50
0  60  40  30
20  0   0   0
```
| M1 | For correct augmenting from their reduced cost matrix and their crossing out

| A1 | For a correct solution after first augmenting

---

Cross through 0's using as few lines as possible:
```
0  40   0   0
0  70  60  50
0  60  40  30
20  0   0   0
```
| M1 | For correct crossing out for their augmented matrix. Likely to be shown on matrix.

Augment by 30:
```
30  40   0   0
0  40  30  20
0  30  10   0
50   0   0   0
```
| M1 | For correctly augmenting their matrix in one step by an amount greater than 10 (or greater than 1 if scaling has been used)

| A1 | For correct final matrix from completely correct method

---

**Allocation:**
$A = Y$; $B = W$; $C = Z$; $D = X$; Cost $= £180$

| B1 | For this allocation
| B1 | For £180

**(iii)**
Hungarian algorithm finds the minimum cost complete matching | B1 | For 'minimum cost' or equivalent

---
4 Four workers, $A , B , C$ and $D$, are to be allocated, one to each of the four jobs, $W , X , Y$ and $Z$. The table shows how much each worker would charge for each job.\\
\includegraphics[max width=\textwidth, alt={}, center]{9c9b1a42-8d16-446a-85a1-4c08e5e368be-3_401_846_1745_642}\\
(i) What is the total cost of the four jobs if $A$ does $W , B$ does $X , C$ does $Y$ and $D$ does $Z$ ?\\
(ii) Apply the Hungarian algorithm to the table, reducing rows first. Show all your working and explain each step. Give the resulting allocation and the total cost of the four jobs with this allocation.\\
(iii) What problem does the Hungarian algorithm solve?

\hfill \mbox{\textit{OCR D2 2006 Q4 [13]}}
This paper (6 questions)
View full paper
Q1 7 Q2 6 Q3 12 Q4 13 Q5 19 Q6 15