Transportation problem: stepping-stone method

3. Table 1 below shows the cost, in pounds, of transporting one unit of stock from each of four supply points, \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D , to four demand points \(1,2,3\) and 4 . It also shows the stock held at each supply point and the stock required at each demand point. A minimum cost solution is required. \begin{table}[h] \end{table} Table 2 shows an initial solution given by the north-west corner method.
Table 3 shows some of the improvement indices for this solution. \begin{table}[h] \end{table} \begin{table}[h] \end{table}

1. Explain why a zero has been placed in cell B3 in Table 2.
   (1)
2. Calculate the shadow costs and the missing improvement indices and enter them into Table 3 in your answer book.
3. Taking the most negative improvement index to indicate the entering cell, state the steppingstone route that should be used to obtain the next solution. You must state your entering cell and exiting cell.

2. The table shows the cost, in pounds, of transporting one unit of stock from each of four supply points, \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D , to each of three demand points, 1, 2 and 3 . It also shows the stock held at each supply point and the stock required at each demand point. A minimum cost solution is required.

1. Use the north-west corner method to obtain an initial solution.
   (1)
2. Taking D1 as the entering cell, use the stepping stone method to find an improved solution. Make your route clear.
   (2)
3. Perform one further iteration of the stepping stone method to obtain an improved solution. You must make your method clear by stating your shadow costs, improvement indices, route, entering cell and exiting cell.
4. Determine whether your current solution is optimal, giving a reason for your answer.

1. Four bakeries, \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D , supply bread to four supermarkets, \(\mathrm { P } , \mathrm { Q } , \mathrm { R }\) and S . The table gives the cost, in pounds, of transporting one lorry load of bread from each bakery to each supermarket. It also shows the number of lorry loads of bread at each bakery and the number of lorry loads of bread required at each supermarket. The total cost of transportation is to be minimised.

1. Use the north-west corner method to obtain a possible solution. A partly completed table of improvement indices is given in Table 1 in the answer book.
2. Complete Table 1.
3. Taking the most negative improvement index to indicate the entering cell, use the steppingstone method once to obtain an improved solution. You must make your route clear and state your entering cell and exiting cell.
4. State the cost of your improved solution.
   

5. The table shows the cost, in pounds, of transporting one unit of stock from each of four supply points, \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D , to each of three sales points, \(\mathrm { P } , \mathrm { Q }\) and R . It also shows the stock held at each supply point and the amount required at each sales point. A minimum cost solution is required. The north-west corner method gives the following initial solution.

1. Taking AQ as the entering cell, use the stepping stone method to find an improved solution. Make your route clear.
2. Perform one further iteration of the stepping stone method to obtain an improved solution. You must make your method clear by stating your shadow costs, improvement indices, route, entering cell and exiting cell.
3. Determine whether your current solution is optimal. Justify your answer.
4. State the cost of the solution you found in (b).
5. Formulate this problem as a linear programming problem. You must define your decision variables and make the objective function and constraints clear.

2. The following transportation problem is to be solved. A possible north-west corner solution is:

1. Use the stepping-stone method once to obtain an improved solution. You must make your shadow costs, improvement indices, entering cell, exiting cell and stepping-stone route clear.
2. Demonstrate that your solution is optimal.
   (3)

1. Table 1 shows the cost, in pounds, of transporting one unit of stock from each of four supply points, \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D , to each of four demand points, \(\mathrm { P } , \mathrm { Q } , \mathrm { R }\) and S . It also shows the stock held at each supply point and the stock required at each demand point. A minimum cost solution is required.

\begin{table}[h] \end{table} Table 2 shows an initial solution given by the north-west corner method. \begin{table}[h] \end{table}

1. Taking DQ as the entering cell, use the stepping-stone method to find an improved solution. Make your method clear.
2. Perform one further iteration of the stepping-stone method to obtain an improved solution. You must make your method clear by stating the
   • shadow costs
   • improvement indices
   • route
   • entering cell and exiting cell.
   • Determine whether the solution obtained from this second iteration is optimal, giving a reason for your answer.
   • State the cost of the solution found in (b).

3. The table below shows the cost, in pounds, of transporting one unit of stock from each of four supply points, \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D , to four sales points, \(\mathrm { P } , \mathrm { Q } , \mathrm { R }\) and S . It also shows the number of units held at each supply point and the number of units required at each sales point. A minimum cost solution is required.

1. Use the north-west corner method to obtain an initial solution.
2. Taking AS as the entering cell, use the stepping-stone method to find an improved solution. Make your method clear.
3. 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 stating the

2. The table shows the cost, in pounds, of transporting one unit of stock from each of three supply points, \(\mathrm { A } , \mathrm { B }\) and C , to each of four demand points, \(1,2,3\) and 4 . It also shows the stock held at each supply point and the stock required at each demand point. A minimum cost solution is required.

1. Use the north-west corner method to obtain an initial solution.
   (1)
2. Taking A4 as the entering cell, use the stepping-stone method to find an improved solution. Make your route clear.
   (2)
3. Taking the most negative improvement index to indicate the entering cell, use the stepping-stone method once to obtain an improved solution. You must make your method clear by stating your shadow costs, improvement indices, route, entering cell and exiting cell.
4. Determine whether your current solution is optimal, giving a reason for your answer.

1. Table 1 shows the cost, in pounds, of transporting one unit of stock from each of four supply points, \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D , to each of four demand points, \(1,2,3\) and 4 . It also shows the stock held at each supply point and the stock required at each demand point. A minimum cost solution to this transportation problem is required.

\begin{table}[h] \end{table} Table 2 shows an initial solution given by the north-west corner method. \begin{table}[h] \end{table}

1. Explain why a zero has been placed in cell C 2 in Table 2. State the other cell in Table 2 in which the zero could have been placed.
2. State the shadow costs clearly and enter the improvement indices into Table 3 in your answer book. Taking the most negative improvement index to indicate the entering cell,
   [0pt]
3. list the stepping-stone route that should be used to obtain the next solution. You should make clear the cells that are included in your route and state your entering and exiting cells. [You do not need to state the next solution. You do not need to solve this problem.]
   

2. Table 1 shows the cost, in pounds, of transporting one unit of stock from each of three supply points, \(\mathrm { A } , \mathrm { B }\) and C , to each of four demand points, 1, 2, 3 and 4 . It also shows the stock held at each supply point and the stock required at each demand point. A minimum cost solution is required. \begin{table}[h] \end{table} Table 2 shows an initial solution given by the north-west corner method. \begin{table}[h] \end{table}

1. Taking A4 as the entering cell, use the stepping-stone method to find an improved solution. Make your route clear.
2. Taking the most negative improvement index to indicate the entering cell, use the stepping-stone method once to obtain an improved solution. You must make your method clear by stating your shadow costs, improvement indices, route, entering cell and exiting cell.
3. Determine whether your current solution is optimal, giving a reason for your answer.
4. State the cost of your current solution.

3. Table 1 shows the cost, in pounds, of transporting one unit of stock from each of four supply points, \(\mathrm { A } , \mathrm { B } , \mathrm { C }\) and D , to three sales points, \(\mathrm { P } , \mathrm { Q }\) and R . It also shows the number of units held at each supply point and the number of units required at each sales point. A minimum cost solution is required. \begin{table}[h] \end{table} Table 2 shows an initial solution given by the north-west corner method. \begin{table}[h] \end{table}

1. Taking AR as the entering cell, use the stepping-stone method to find an improved solution. Make your method clear.
2. Perform one further iteration of the stepping-stone method to obtain an improved solution. You must make your method clear by stating

A transportation problem has costs, in pounds, and supply and demand, in appropriate units, as given in the transportation tableau below.

	D	E	F	Supply
A	13	11	14	20
B	10	9	12	15
C	15	6	8	25
Demand	30	5	25

1. Find the initial solution given by the north-west corner rule and state why it is degenerate. [3 marks]
2. Use the stepping-stone method to obtain an optimal solution minimising total cost. State the resulting transportation pattern and its total cost. [15 marks]