A2 June 2023 Q3

EdexcelCurrent spec9 marksTransportation Problems

3. The table below shows the stock held at each supply point and the stock required at each demand point in a standard transportation problem. The table also shows the cost, in pounds, of transporting the stock from each supply point to each demand point.

QRSSupply
A23181245
B8101427
C11142134
D19151150
Demand753744

The problem is partially described by the linear programming formulation below.

Let \(x_{ij}\) be the number of units transported from \(i\) to \(j\)

where \(\quad i \in \{\text{A, B, C, D}\}\)
\(\qquad\quad\ j \in \{\text{Q, R, S}\}\) and \(x_{ij} \geqslant 0\)

Minimise \(P = 23x_{\text{AQ}} + 18x_{\text{AR}} + 12x_{\text{AS}} + 8x_{\text{BQ}} + 10x_{\text{BR}} + 14x_{\text{BS}}\)
\(\qquad\qquad + 11x_{\text{CQ}} + 14x_{\text{CR}} + 21x_{\text{CS}} + 19x_{\text{DQ}} + 15x_{\text{DR}} + 11x_{\text{DS}}\)

(a) Write down, as inequalities, the constraints of the linear program. (2)
(b) Use the north-west corner method to obtain an initial solution to this transportation problem. (1)
(c) Taking AS as the entering cell, use the stepping-stone method to find an improved solution. Make your route clear. (2)
(d) Perform one further iteration of the stepping-stone method to obtain an improved solution. You must make your method clear by showing the route and the
  • shadow costs
  • improvement indices
  • entering cell and exiting cell
(4)
‹ Previous3 of 7 in Transportation ProblemsNext ›