Edexcel D2 2010 June — Question 3 11 marks

Exam BoardEdexcel
ModuleD2 (Decision Mathematics 2)
Year2010
SessionJune
Marks11
PaperDownload PDF ↗
Mark schemeDownload PDF ↗
TopicMatchings and Allocation
TypeTransportation problem: stepping-stone method
DifficultyModerate -0.5 This is a standard algorithmic application of the north-west corner method and stepping-stone method with clear instructions. While it requires careful bookkeeping across multiple iterations, it follows a mechanical procedure taught directly in D2 with no novel problem-solving or insight required—making it slightly easier than average for A-level.
Spec7.07a Simplex tableau: initial setup in standard format
3. The table below shows the cost of transporting one block of staging from each of two supply points, X and Y , to each of four concert venues, \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D . It also shows the number of blocks held at each supply point and the number of blocks required at each concert venue. A minimal cost solution is required.
ABCDSupply
X2820191653
Y1512141747
Demand18312229
  1. Use the north-west corner method to obtain a possible solution.
    (1)
  2. Taking the most negative improvement index to indicate the entering square, use the stepping stone method twice to obtain an improved solution. You must make your method clear by stating your shadow costs, improvement indices, routes, entering cells and exiting cells.
  3. Is your current solution optimal? Give a reason for your answer.
    (1)
Question 3:
Part (a)
AnswerMarks Guidance
AnswerMarks Guidance
Initial basic feasible solution stated1B1 cao
Part (b)
AnswerMarks Guidance
AnswerMarks Guidance
6 shadow costs and precisely 3 improvement indices stated1M1 No extra zeros
Correct shadow costs and improvement indices1A1 cao
Valid route chosen using negative II, only one empty square used, \(\theta\)'s balance2M1
Improved solution2A1ft No extra zeros
6 shadow costs and precisely 3 improvement indices stated3M1ft No extra zeros
Correct values3A1 cao
Valid route chosen using negative II, only one empty square used, \(\theta\)'s balance4M1ft
Improved solution4A1ft No extra zeros
6 shadow costs and precisely 3 improvement indices (or 1 negative improvement index) stated5A1=5M1 No extra zeros
Misread working (not choosing most negative):
*Entering cell XD:*
- Route: \(X\): \(18, 31, 4-\theta, \theta\); \(Y\): \(18+\theta, 29-\theta\)
- Exiting cell XC, \(\theta=4\)
- Improved solution: \(X\): \(18, 31, -, 4\); \(Y\): \(-, -, 22, 25\)
- Shadow costs: \(28, 20, 13, 16\); IIs: \(XC=6\), \(YA=-14\), \(YB=-9\)
*Or entering cell YB:*
- Route: \(X\): \(18, 31-\theta, 4+\theta\); \(Y\): \(\theta, 18-\theta, 29\)
- Exiting cell YC, \(\theta=18\)
- Improved solution: \(X\): \(18, 13, 22\); \(Y\): \(18, -, 29\)
- Shadow costs: \(28, 20, 19, 25\); IIs: \(XD=-9\), \(YA=-5\), \(YC=3\)
Candidates can get: 2M1 2A1 for first route and improved solution; 3M1 3A0 for 6 shadow costs and 3 IIs; 4M1 for valid route, 4A1 if route leads to improved solution [A0 for 6 shadow costs and 3 IIs as CAO]
Part (c)
AnswerMarks Guidance
AnswerMarks Guidance
Conclusion that solution is optimal1B1ft = 1A1ft cao; must follow from at least one negative II in a third 'set' of IIs 
# Question 3:

## Part (a)

| Answer | Marks | Guidance |
|--------|-------|----------|
| Initial basic feasible solution stated | 1B1 | cao |

## Part (b)

| Answer | Marks | Guidance |
|--------|-------|----------|
| 6 shadow costs and precisely 3 improvement indices stated | 1M1 | No extra zeros |
| Correct shadow costs and improvement indices | 1A1 | cao |
| Valid route chosen using negative II, only one empty square used, $\theta$'s balance | 2M1 | |
| Improved solution | 2A1ft | No extra zeros |
| 6 shadow costs and precisely 3 improvement indices stated | 3M1ft | No extra zeros |
| Correct values | 3A1 | cao |
| Valid route chosen using negative II, only one empty square used, $\theta$'s balance | 4M1ft | |
| Improved solution | 4A1ft | No extra zeros |
| 6 shadow costs and precisely 3 improvement indices (or 1 negative improvement index) stated | 5A1=5M1 | No extra zeros |

**Misread working (not choosing most negative):**

*Entering cell XD:*
- Route: $X$: $18, 31, 4-\theta, \theta$; $Y$: $18+\theta, 29-\theta$
- Exiting cell XC, $\theta=4$
- Improved solution: $X$: $18, 31, -, 4$; $Y$: $-, -, 22, 25$
- Shadow costs: $28, 20, 13, 16$; IIs: $XC=6$, $YA=-14$, $YB=-9$

*Or entering cell YB:*
- Route: $X$: $18, 31-\theta, 4+\theta$; $Y$: $\theta, 18-\theta, 29$
- Exiting cell YC, $\theta=18$
- Improved solution: $X$: $18, 13, 22$; $Y$: $18, -, 29$
- Shadow costs: $28, 20, 19, 25$; IIs: $XD=-9$, $YA=-5$, $YC=3$

Candidates can get: 2M1 2A1 for first route and improved solution; 3M1 3A0 for 6 shadow costs and 3 IIs; 4M1 for valid route, 4A1 if route leads to improved solution [A0 for 6 shadow costs and 3 IIs as CAO]

## Part (c)

| Answer | Marks | Guidance |
|--------|-------|----------|
| Conclusion that solution is optimal | 1B1ft = 1A1ft | cao; must follow from at least one negative II in a third 'set' of IIs |

---
3. The table below shows the cost of transporting one block of staging from each of two supply points, X and Y , to each of four concert venues, $\mathrm { A } , \mathrm { B } , \mathrm { C }$ and D . It also shows the number of blocks held at each supply point and the number of blocks required at each concert venue. A minimal cost solution is required.

\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | }
\hline
 & A & B & C & D & Supply \\
\hline
X & 28 & 20 & 19 & 16 & 53 \\
\hline
Y & 15 & 12 & 14 & 17 & 47 \\
\hline
Demand & 18 & 31 & 22 & 29 &  \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Use the north-west corner method to obtain a possible solution.\\
(1)
\item Taking the most negative improvement index to indicate the entering square, use the stepping stone method twice to obtain an improved solution. You must make your method clear by stating your shadow costs, improvement indices, routes, entering cells and exiting cells.
\item Is your current solution optimal? Give a reason for your answer.\\
(1)
\end{enumerate}

\hfill \mbox{\textit{Edexcel D2 2010 Q3 [11]}}
This paper (7 questions)
View full paper
Q1 11 Q2 10 Q3 11 Q4 13 Q5 10 Q6 13 Q7 7