Transportation problem: north-west corner

7. A steel manufacturer has 3 factories \(F _ { 1 } , F _ { 2 }\) and \(F _ { 3 }\) which can produce 35,25 and 15 kilotonnes of steel per year, respectively. Three businesses \(B _ { 1 } , B _ { 2 }\) and \(B _ { 3 }\) have annual requirements of 20,25 and 30 kilotonnes respectively. The table below shows the cost \(C _ { i j }\) in appropriate units, of transporting one kilotonne of steel from factory \(F _ { i }\) to business \(B _ { j }\). The manufacturer wishes to transport the steel to the businesses at minimum total cost.

1. Write down the transportation pattern obtained by using the North-West corner rule.
2. Calculate all of the improvement indices \(I _ { i j }\), and hence show that this pattern is not optimal.
3. Use the stepping-stone method to obtain an improved solution.
4. Show that the transportation pattern obtained in part (c) is optimal and find its cost.

1. Freezy Co. has three factories \(A , B\) and \(C\). It supplies freezers to three shops \(D , E\) and \(F\). The table shows the transportation cost in pounds of moving one freezer from each factory to each outlet. It also shows the number of freezers available for delivery at each factory and the number of freezers required at each shop. The total number of freezers required is equal to the total number of freezers available.

1. Use the north-west corner rule to find an initial solution.
2. Obtain improvement indices for each unused route.
3. Use the stepping-stone method once to obtain a better solution and state its cost.

3. Freezy Co. has three factories \(A , B\) and \(C\). It supplies freezers to three shops \(D , E\) and \(F\). The table shows the transportation cost in pounds of moving one freezer from each factory to each outlet. It also shows the number of freezers available for delivery at each factory and the number of freezers required at each shop. The total number of freezers required is equal to the total number of freezers available.

1. Use the north-west corner rule to find an initial solution.
2. Obtain improvement indices for each unused route.
3. Use the stepping-stone method once to obtain a better solution and state its cost.

A steel manufacturer has 3 factories \(F_1\), \(F_2\) and \(F_3\) which can produce 35, 25 and 15 kilotomnes of steel per year, respectively. Three businesses \(B_1\), \(B_2\) and \(B_3\) have annual requirements of 20, 25 and 30 kilotomnes respectively. The table below shows the cost \(C_{ij}\) in appropriate units, of transporting one kilotome of steel from factory \(F_i\) to business \(B_j\).

		Business
	\(B_1\)	\(B_2\)	\(B_3\)
\(F_1\)	10	4	11
Factory \(F_2\)	12	5	8
\(F_3\)	9	6	7

The manufacturer wishes to transport the steel to the businesses at minimum total cost.

1. Write down the transportation pattern obtained by using the North-West corner rule. [2]
2. Calculate all of the improvement indices \(I_{ij}\) and hence show that this pattern is not optimal. [5]
3. Use the stepping-stone method to obtain an improved solution. [3]
4. Show that the transportation pattern obtained in part (c) is optimal and find its cost. [4]

1. Explain briefly the circumstances under which a degenerate feasible solution may occur to a transportation problem. [2]
2. Explain why a dummy location may be needed when solving a transportation problem. [1]

The table below shows the cost of transporting one unit of stock from each of three supply points \(A\), \(B\) and \(C\) to each of two demand points 1 and 2. It also shows the stock held at each supply point and the stock required at each demand point.

	1	2	Supply
\(A\)	62	47	15
\(B\)	61	48	12
\(C\)	68	58	17
Demand	16	11

1. Complete the table below to show a possible initial feasible solution generated by the north-west corner method.

   	1	2	3
   \(A\)
   \(B\)			0
   \(C\)

   [1]
2. Use the stepping-stone method to obtain an optimal solution and state its cost. You should make your method clear by stating shadow costs, improvement indices, stepping-stone route, and the entering and exiting squares at each stage. [10]

(Total 14 marks)