| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2007 |
| Session | June |
| Marks | 16 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Linear programming formulation for assignment |
| Difficulty | Moderate -0.8 This is a standard transportation problem application requiring routine completion of a table, explanation of dummy variables, and mechanical application of north-west corner and stepping stone methods. While multi-part with several marks, these are algorithmic procedures taught directly in D2 with no novel problem-solving or insight required—students follow learned algorithms step-by-step. |
| Spec | 7.04f Network problems: choosing appropriate algorithm |
| Adult | Student | |
| Performance 1 | \(\pounds 5.00\) | \(\pounds 4.50\) |
| Performance 2 | \(\pounds 4.20\) | \(\pounds 3.80\) |
| Performance 3 | \(\pounds 4.60\) | \(\pounds 4.00\) |
| Adult | Student | Dummy | Seats available | |
| Performance 1 | £5.00 | £4.50 | ||
| Performance 2 | £4.20 | £3.80 | ||
| Performance 3 | £4.60 | £4.00 | ||
| Tickets needed |
| Adult | Student | Dummy | |
| Performance 1 | 73 | 21 | |
| Performance 2 | 18 | 47 | |
| Performance 3 | 80 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Table with \(D\) column all \(0\), supplies \(94, 65, 80\), demands \(18, 200, 21\) | B2,1,0 | 2 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Total supply \(>\) total demand | B1 | 1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Initial solution: Row 1: \(A=18, S=76\); Row 2: \(S=65\); Row 3: \(S=59, D=21\) | B1 | |
| \(S(1)=0\), \(D(A)=5\) | M1A1ft | |
| \(S(2)=-0.7\), \(D(S)=4.5\); \(S(3)=-0.5\), \(D(D)=0.5\) | ||
| \(I_{1D}=0-0-0.5=-0.5^*\); \(I_{2A}=4.2+0.7-5=-0.1\); \(I_{2D}=0+0.7-0.5=0.2\); \(I_{3A}=4.6+0.5-5=0.1\) | A1 | |
| Entering \(1D\), Exiting \(3D\), \(\theta=21\) | M1A1ft | |
| New solution: Row 1: \(A=18, S=55, D=21\); Row 2: \(S=65\); Row 3: \(S=80\) | A1 | 7 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| \(S(1)=0\), \(S(2)=-0.7\), \(S(3)=-0.5\); \(D(A)=4.9\), \(D(B)=4.5\), \(D(B)=0\) | M1, A1 | |
| \(I_{1A}=5-0-4.9=0.1\); \(I_{2D}=0+0.7-0=0.7\); \(I_{3A}=4.6+0.5-4.9=0.2\); \(I_{3D}=0+0.5-0=0.5\) | A1 | |
| Optimal since all \(I\)'s \(\geq 0\) | A1 | |
| Cost £902.70 | M1A1 | 6 |
# Question 4:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Table with $D$ column all $0$, supplies $94, 65, 80$, demands $18, 200, 21$ | B2,1,0 | 2 |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Total supply $>$ total demand | B1 | 1 |
## Parts (c)(d)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Initial solution: Row 1: $A=18, S=76$; Row 2: $S=65$; Row 3: $S=59, D=21$ | B1 | |
| $S(1)=0$, $D(A)=5$ | M1A1ft | |
| $S(2)=-0.7$, $D(S)=4.5$; $S(3)=-0.5$, $D(D)=0.5$ | | |
| $I_{1D}=0-0-0.5=-0.5^*$; $I_{2A}=4.2+0.7-5=-0.1$; $I_{2D}=0+0.7-0.5=0.2$; $I_{3A}=4.6+0.5-5=0.1$ | A1 | |
| Entering $1D$, Exiting $3D$, $\theta=21$ | M1A1ft | |
| New solution: Row 1: $A=18, S=55, D=21$; Row 2: $S=65$; Row 3: $S=80$ | A1 | 7 |
## Part (e)
| Answer | Marks | Guidance |
|--------|-------|----------|
| $S(1)=0$, $S(2)=-0.7$, $S(3)=-0.5$; $D(A)=4.9$, $D(B)=4.5$, $D(B)=0$ | M1, A1 | |
| $I_{1A}=5-0-4.9=0.1$; $I_{2D}=0+0.7-0=0.7$; $I_{3A}=4.6+0.5-4.9=0.2$; $I_{3D}=0+0.5-0=0.5$ | A1 | |
| Optimal since all $I$'s $\geq 0$ | A1 | |
| Cost £902.70 | M1A1 | 6 |
---4. A group of students and teachers from a performing arts college are attending the Glasenburgh drama festival. All of the group want to see an innovative modern production of the play 'The Decision is Final'. Unfortunately there are not enough seats left for them all to see the same performance.
There are three performances of the play, 1,2 , and 3 . There
\begin{center}
\begin{tabular}{ | c | c | c | }
\hline
& Adult & Student \\
\hline
Performance 1 & $\pounds 5.00$ & $\pounds 4.50$ \\
\hline
Performance 2 & $\pounds 4.20$ & $\pounds 3.80$ \\
\hline
Performance 3 & $\pounds 4.60$ & $\pounds 4.00$ \\
\hline
\end{tabular}
\end{center}
are two types of ticket, Adult and Student. Student tickets will be purchased for the students and Adult tickets for the teachers.
The table below shows the price of tickets for each performance of the play. There are 18 teachers and 200 students requiring tickets. There are 94,65 and 80 seats available for performances 1,2 , and 3 espectively.
\begin{enumerate}[label=(\alph*)]
\item Complete the table below.
\begin{center}
\begin{tabular}{|l|l|l|l|l|}
\hline
& Adult & Student & Dummy & Seats available \\
\hline
Performance 1 & £5.00 & £4.50 & & \\
\hline
Performance 2 & £4.20 & £3.80 & & \\
\hline
Performance 3 & £4.60 & £4.00 & & \\
\hline
Tickets needed & & & & \\
\hline
\end{tabular}
\end{center}
\item Explain why a dummy column was added to the table above.
\item Use the north-west corner method to obtain a possible solution.
\item Taking the most negative improvement index to indicate the entering square, use the stepping stone method once to obtain an improved solution. You must make your shadow costs and improvement indices clear.
After a further iteration the table becomes:
\begin{center}
\begin{tabular}{ | c | c | c | c | }
\hline
& Adult & Student & Dummy \\
\hline
Performance 1 & & 73 & 21 \\
\hline
Performance 2 & 18 & 47 & \\
\hline
Performance 3 & & 80 & \\
\hline
\end{tabular}
\end{center}
\item Demonstrate that this solution gives the minimum cost, and find its value.\\
(Total 16 marks)
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2007 Q4 [16]}}