Stepping Stone Method Examples: Transportation Problem

In the previous section, we used the Stepping Stone Method to find the optimal solution of a transportation problem. In this section, we provide another example to boost your understanding. Let's concentrate on the following example:

exampleExample 2: Stepping Stone Method

Consider the following transportation problem (cost in rupees)

Distributor
Factory D E F Supply
A 2 1 5 10
B 7 3 4 25
C 6 5 3 20
Requirement 15 22 18 55

Find out the minimum cost of the given transportation problem.

Solution.

We compute an initial basic feasible solution of the problem by Matrix Minimum Method as shown in table 1.

Table 1

Use Horizontal Scrollbar to View Full Table Calculation.

Distributor
Factory D E F Supply
A 2 5 10
B 4 25
C 5 20
Requirement 15 22 18 55

Here, m + n - 1 = 5. So the solution is not degenerate.

Initial basic feasible solution

1 X 10 + 7 X 13 + 3 X 12 + 6 X 2 + 3 X 18 = 203

The cell AD (2) is empty so allocate one unit to it. Now draw a closed path.

Table 2

The increase in the transportation cost per unit quantity of reallocation is:
+ 2 – 1 + 3 – 7 = - 3.

The allocations for other unoccupied cells are following:

Unoccupied cells Increase in cost per unit of reallocation Remarks
AF +5 – 1 + 3 – 7 + 6 – 3 = 3 Cost Increases
CE +5 – 3 + 7 – 6 = 3 Cost Increases
BF +4 – 7 + 6 – 3 = 0 Neither increase nor decrease

This indicates that the route through AD would be beneficial to the company. The maximum amount that can be allocated to AD is 10 and this will make the current basic variable corresponding to cell AE non basic.

Table 3 shows the transportation table after reallocation.

Table 3

Distributor
Factory D E F Supply
A 1 5 10
B 4 25
C 5 20
Requirement 15 22 18 55

Since the reallocation in any other unoccupied cell cannot decrease the transportation cost, the minimum transportation cost is:
2 X 10 + 7 X 3 + 3 X 22 + 6 X 2 + 3 X 18 = Rs.173

Share this article with your friends