Example 10

EXAMPLE 10 Applying the Stepping Stone Method

We will work out another small example to illustrate the technique of applying the Northwest Corner Rule to get an initial solution, and then improving this solution if it is not optimal. Again, we do so by computing the indicator values of the cells and improving the current solution by shipping using a cell with a negative indicator value.

We start with an initial tableau where there are two mines that can supply ore to three companies that extract ore. There are 10 units of ore being mined and the extractors need 10 units to run at full capacity. The initial tableau for the problem is displayed in Figure 4.25.

Figure 4.25: Figure 4.25 A transportation problem where two mines supply ore to three companies that extract metal from the ore. The shipping costs are indicated.

158

Using the Northwest Corner Rule, we find an initial feasible solution as shown in Figure 4.26. When applying the Northwest Corner Rule, we eliminate a row or column as follows: first column 1, then column 2, then row I, and we are now left with a single cell. The cost of the feasible solution shown is

Figure 4.26: Figure 4.26 The Northwest Corner Rule has been used to find a possible way to meet the demands from the supplies for the tableau in Figure 4.25.

The two empty cells we have are (II, 1) and (II, 2). We compute the indicator value for each of these cells:

Because cell (II, 1) has a more negative indicator value, we can reduce the cost more by using that cell. increasing by 2 (because this is the minimum of circled numbers with negative signs in the computation of the indicator) the amount of metal shipped via cell (II, 1) and cell (I, 3) and reducing by 2 the amount in cells (I, 1) and (II, 3), we obtain the new tableau in Figure 4.27. This has cost

Figure 4.27: Figure 4.27 An improved solution based on the negative indicator value for cell (II, 1) in Figure 4.26.

Note that as a partial check on our work, if we multiply the indicator (−7) by 2, this is −14 and , so we reduced the cost of our first solution by 14, as expected.

We now repeat this procedure for this new tableau. We must compute the indicator value of cells (I, 1) and (II, 2).

159

Thus, it turns out that we can increase by 1 the amount shipped by (II, 2) and get the tableau in Figure 4.28.

From this tableau, we need to compute the indicator values for the cells (I, 1) and (II, 3). We obtain

Figure 4.28: Figure 4.28 An improved solution, which turns out to be optimal, based on the negative indicator value for cell (ii, 2) in Figure 4.27.

Not surprisingly, the cell (II, 2) has a positive indicator value because in the previous tableau, that cell was the one that, when we shipped less via it, enabled us to reduce the cost. The fact that both of these indicator values are positive means that the current shipping schedule is an optimal one; that is, using a shipping schedule that ships via only four cells, we cannot find any other solution with the same value.