Transportation Problem: North-west Corner Method

In a transportation model, an initial feasible solution can be found by several alternative methods, including the northwest corner method, the minimum cell cost method, and Vogel’s approximation model.

After finding feasible solution the two methods for solving a transportation model are the stepping-stone method and the modified distribution method (also known as MODI).

 

Problem 1. Wheat is harvested in the Midwest and stored in grain elevators in three different cities—Kansas City, Omaha, and Des Moines. These grain elevators sup- ply three flour mills, located in Chicago, St. Louis, and Cincinnati. Grain is shipped to the mills in railroad cars, each car capable of holding one ton of wheat. Each grain elevator is able to supply the following number of tons (i.e., railroad cars) of wheat to the mills on a monthly basis.

Grain Elevator

Supply

1.

Kansas City

150

2.

Omaha

175

3.

Des Moines

275

Total

600 ton

Each mill demands the following number of tons of wheat per month.

Mill

Demand

A. Chicago

200

B. St. Louis

100

C. Cincinnati

300

Total

600 tons

The cost of transporting one ton of wheat from each grain elevator (source) to each mill (destination) differs according to the distance and rail system. These costs are shown in the following table. For example, the cost of shipping one ton of wheat from the grain elevator at Omaha to the mill at Chicago is $7.

The problem is to determine how many tons of wheat to transport from each grain elevator to each mill on a monthly basis in order to minimize the total cost of transportation.

Trasnportation-Problem

Solution:

Each cell in a transportation tableau is analogous to a decision variable that indicates the amount allocated from a source to a destination.

The supply and demand values along the outside rim of a tableau are called rim requirements.

Trasnportation-initial-table

The Northwest Corner Method

In the northwest corner method the largest possible allocation is made to the cell in the upper left-hand corner of the tableau, followed by allocations to adjacent feasible cells.

With the northwest corner method, an initial allocation is made to the cell in the upper left- hand corner of the tableau. The amount allocated is the most possible, subject to the supply and demand constraints for that cell. In our example, we first allocate as much as possible to cell 1A (the northwest corner). This amount is 150 tons, since that is the maximum that can be supplied by grain elevator 1 at Kansas City, even though 200 tons are demanded by mill A at Chicago. This initial allocation is shown in Table B-2.

We next allocate to a cell adjacent to cell 1A, in this case either cell 2A or cell 1B. However, cell 1B no longer represents a feasible allocation, because the total tonnage of wheat available at source 1 (i.e., 150 tons) has already been allocated. Thus, cell 2A repre- sents the only feasible alternative, and as much as possible is allocated to this cell. The amount allocated at 2A can be either 175 tons, the supply available from source 2 (Omaha), or 50 tons, the amount now demanded at destination A. (Recall that 150 of the 200 tons demanded at A have already been supplied.) Because 50 tons is the most constrained amount, it is allocated to cell 2A, as shown in Table B-2.

Trasnportation-table-North-west-corner

The third allocation is made in the same way as the second allocation. The only feasible cell adjacent to cell 2A is cell 2B. The most that can be allocated is either 100 tons (the amount demanded at mill B) or 125 tons (175 tons minus the 50 tons allocated to cell 2A). The smaller (most constrained) amount, 100 tons, is allocated to cell 2B, as shown in Table B-2.

The fourth allocation is 25 tons to cell 2C, and the fifth allocation is 275 tons to cell 3C, both of which are shown in Table B-2. Notice that all of the row and column allocations add up to the appropriate rim requirements.

“The initial solution is complete when all rim requirements are satisfied.”

The steps of the northwest corner method are summarized here.

1.Allocate as much as possible to the cell in the upper left-hand corner, subject to the supply and demand constraints.

2.Allocate as much as possible to the next adjacent feasible cell.

3.Repeat step 2 until all rim requirements have been met.

 

6(150) + 8(0) + 10(0) +7(50) + 11(100) +11(25) + 4(0) + 5(0) + 12(275)

=$5,925