EXAMPLE 9 Using the Northwest Corner Rule

Applying the Northwest Corner Rule to our original tableau (see Figure 4.18), we get the sequence of tableaux in Figure 4.21 as we cross out the rows or columns, where for clarity the costs associated with the cells are suppressed. The last diagram in the sequence shows the results on the original tableau, with the cost restored. Note that, at the steps in between, the costs played no role. it is a good idea to check that the circled numbers in each row and column really add up to the rim value for that row and column and that exactly cells are filled.

We can now compute the cost of the associated solution that we have found (feasible solution), which obeys the rim conditions. As we did previously, we add up the cost multiplied by the amount shipped for each cell with a circled entry. We get the following calculation:

154

This shows a cost that is smaller than the solution we found earlier. That solution involved a cost of 93. But is this solution the cheapest one? The fact that this feasible solution was found without using the costs on the cells suggests that no, it is not very likely this solution is cheapest.