| Exam Board | OCR |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2007 |
| Session | June |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Hungarian algorithm with unequal sets |
| Difficulty | Moderate -0.8 This is a straightforward application of the Hungarian algorithm with a standard dummy row addition for unequal sets. The algorithm steps are routine and mechanical (row reduction, column reduction, covering lines, adjusting), requiring only careful arithmetic and following a prescribed procedure with no problem-solving insight or novel reasoning needed. |
| Spec | 7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin7.03m Packing extensions: 2D/3D packing and knapsack problems |
| House 1 | House 2 | House 3 | House 4 | |
| Allclean | \(\pounds 500\) | \(\pounds 400\) | \(\pounds 700\) | \(\pounds 600\) |
| Brightenupp | \(\pounds 300\) | \(\pounds 200\) | \(\pounds 400\) | \(\pounds 350\) |
| Clean4U | \(\pounds 500\) | \(\pounds 300\) | \(\pounds 750\) | \(\pounds 680\) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Table copied with row/column headings and values for A(500,400,700,600), B(300,200,400,350), C(500,300,750,680), D(0,0,0,0) | B1 | For copying the table, with row and column headings (accept consistent scalings) |
| Dummy row D with all equal values | B1 | For dummy row (Daniel) with all equal values |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Reduced matrix: rows give 100,0,300,200 / 100,0,200,150 / 200,0,450,380 / 0,0,0,0 | M1 | For a substantially correct attempt at reducing rows and columns |
| Correct reduced cost matrix | A1 | For correct reduced cost matrix (ft scalings). Do not treat as MR |
| Columns are already reduced | 2 marks total | |
| Cover zeros using two lines | M1 | For covering zeros using minimum number of lines, clearly seen or implied from augmenting |
| Augment by 100 | M1 dep | For a single augmentation by 100 (ft their matrix) (accept either way of augmenting by 100) |
| Augmented matrix: 0,0,200,100 / 0,0,100,50 / 100,0,350,280 / 0,100,0,0 | A1 ft | For a correct augmented matrix (ft their matrix) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Cover zeros using three lines | M1 | For covering zeros using minimum number of lines a second time, clearly seen or implied from augmenting |
| Augment by 50 | M1 dep | For a single augmentation by 50 (ft their matrix) (accept either way of augmenting by 50) |
| Augmented matrix: 0,0,150,50 / 0,0,50,0 / 100,0,300,230 / 50,150,0,0 | A1 ft | For a correct augmented matrix (ft their matrix) |
| Complete matching identified with zeros at positions giving optimal assignment | B1 | For a complete matching achieved, must follow from an attempt at reducing or augmenting a matrix, not just implied from a list of the matching |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Allclean → house 1, Brightenupp → house 4, Clean4U → house 2 | B1 | For \(A=1, B=4, C=2\) (may also list \(D=3\)) cao |
| Cost = £1150 | B1 | For 1150 cao |
# Question 1:
## Part (i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Table copied with row/column headings and values for A(500,400,700,600), B(300,200,400,350), C(500,300,750,680), D(0,0,0,0) | B1 | For copying the table, with row and column headings (accept consistent scalings) |
| Dummy row D with all equal values | B1 | For dummy row (Daniel) with all equal values |
## Part (ii) - First augmentation
| Answer | Marks | Guidance |
|--------|-------|----------|
| Reduced matrix: rows give 100,0,300,200 / 100,0,200,150 / 200,0,450,380 / 0,0,0,0 | M1 | For a substantially correct attempt at reducing rows and columns |
| Correct reduced cost matrix | A1 | For correct reduced cost matrix (ft scalings). Do not treat as MR |
| Columns are already reduced | | 2 marks total |
| Cover zeros using two lines | M1 | For covering zeros using minimum number of lines, clearly seen or implied from augmenting |
| Augment by 100 | M1 dep | For a single augmentation by 100 (ft their matrix) (accept either way of augmenting by 100) |
| Augmented matrix: 0,0,200,100 / 0,0,100,50 / 100,0,350,280 / 0,100,0,0 | A1 ft | For a correct augmented matrix (ft their matrix) |
## Part (ii) - Second augmentation
| Answer | Marks | Guidance |
|--------|-------|----------|
| Cover zeros using three lines | M1 | For covering zeros using minimum number of lines a second time, clearly seen or implied from augmenting |
| Augment by 50 | M1 dep | For a single augmentation by 50 (ft their matrix) (accept either way of augmenting by 50) |
| Augmented matrix: 0,0,150,50 / 0,0,50,0 / 100,0,300,230 / 50,150,0,0 | A1 ft | For a correct augmented matrix (ft their matrix) |
| Complete matching identified with zeros at positions giving optimal assignment | B1 | For a complete matching achieved, must follow from an attempt at reducing or augmenting a matrix, not just implied from a list of the matching |
## Part (iii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Allclean → house 1, Brightenupp → house 4, Clean4U → house 2 | B1 | For $A=1, B=4, C=2$ (may also list $D=3$) cao |
| Cost = £1150 | B1 | For 1150 cao |
---1 D aniel needs to clean four houses but only has one day in which to do it. He estimates that each house will take one day and so he has asked three professional cleaning companies to give him a quotation for cleaning each house. He intends to hire the three companies to clean one house each and he will clean the fourth house himself. The table below shows the quotations that Daniel was given by the three companies.
\begin{center}
\begin{tabular}{ | l | c c c c | }
\hline
& House 1 & House 2 & House 3 & House 4 \\
\hline
Allclean & $\pounds 500$ & $\pounds 400$ & $\pounds 700$ & $\pounds 600$ \\
Brightenupp & $\pounds 300$ & $\pounds 200$ & $\pounds 400$ & $\pounds 350$ \\
Clean4U & $\pounds 500$ & $\pounds 300$ & $\pounds 750$ & $\pounds 680$ \\
\hline
\end{tabular}
\end{center}
(i) Copy the table and add a dummy row to represent D aniel.\\
(ii) A pply the Hungarian algorithm, reducing rows first, to find a minimum cost matching. You must show your working and say how each matrix was formed.\\
(iii) Which house should Daniel ask each company to clean? Find the total cost of hiring the three companies.
\hfill \mbox{\textit{OCR D2 2007 Q1 [13]}}