North West corner method

14/03/2023 0 By indiafreenotes

The North-West Corner Method is a basic heuristic algorithm used for solving transportation problems, a type of linear programming problem in operations research. The method gets its name from the fact that the first allocation of supply to demand is made in the north-west corner of the transportation table.

Steps involved in the North-West Corner Method:

  1. Set up the transportation table: This involves creating a table with the supply at the top and the demand on the left side. Each cell in the table represents the cost of transporting one unit of the product from the supplier to the demand location.
  2. Identify the north-west corner cell: Start by allocating the maximum possible amount to the first supply and demand location, which is the top-left cell of the table.
  3. Allocate as much as possible to the cell: Allocate as much product as possible to this cell, up to the smaller of the supply and demand values.
  4. Update the supply and demand: Subtract the allocated quantity from the supply and demand values for the respective rows and columns.
  5. Move to the next cell: Move to the next cell in the same row or column that has not been allocated, and repeat steps 3 and 4.
  6. Repeat the process: Continue the process until all cells in the table have been allocated.
  7. Optimize the solution: Once all cells have been allocated, check whether the solution obtained is optimal. If it’s not optimal, make adjustments by repeating the process until the optimal solution is obtained.

The North-West Corner Method is a simple and easy-to-use algorithm. However, it does not guarantee an optimal solution, especially for large and complex transportation problems. Therefore, it is often used as a starting point for more advanced methods of solving transportation problems.

North West corner method example

Suppose a company has three factories that produce goods and four warehouses that distribute the goods. The supply and demand of the goods are given in the following table:

Warehouse 1 Warehouse 2 Warehouse 3 Warehouse 4 Supply
F1 3 2 7 6 120
F2 5 4 9 8 200
F3 4 3 5 7 100
Demand 150 120 180 70

To apply the North-West Corner Method, we start with the top-left cell and allocate as much as possible. So, we allocate 3 units from Factory 1 to Warehouse 1.

Warehouse 1 Warehouse 2 Warehouse 3 Warehouse 4 Supply
F1 (3) 2 7 6 117
F2 4 9 8 200
F3 3 5 7 100
Demand 150 120 180 70

Next, we move to the next cell in the same row and allocate as much as possible. So, we allocate 2 units from Factory 1 to Warehouse 2.

Warehouse 1 Warehouse 2 Warehouse 3 Warehouse 4 Supply
F1 (3) (2) 7 6 115
F2 4 9 8 200
F3 3 5 7 100
Demand 150 120 180 70

Now we move to the next row and allocate as much as possible to the next cell. We allocate 5 units from Factory 2 to Warehouse 2.

Warehouse 1 Warehouse 2 Warehouse 3 Warehouse 4 Supply
F1 (3) (2) 7 6 115
F2 (4) 9 8 195
F3 3 5 7 100
Demand 150 118 180 70

Then we move to the next row and allocate as much as possible to the next cell. We allocate 9 units from Factory 2 to Warehouse 3.

Then we move to the next row and allocate as much as possible to the next cell. We allocate 9 units from Factory 2 to Warehouse 3.

Warehouse 1 Warehouse 2 Warehouse 3 Warehouse 4 Supply
F1 (3) (2) 7 6 115
F2 (4) (9) 8 186
F3 3 5 7 100
Demand 150 118 171 70

Next, we allocate 6 units from Factory 1 to Warehouse 4:

Warehouse 1 Warehouse 2 Warehouse 3 Warehouse 4 Supply
F1 (3) (2) 7 (6) 109
F2 (4) (9) 8 186
F3 3 5 7 100
Demand 150 118 171 64

We continue to allocate in the same way until all demands are satisfied. The final allocation table is:

Warehouse 1 Warehouse 2 Warehouse 3 Warehouse 4 Supply
F1 3 2 7 6 109
F2 5 4 9 0 191
F3 0 3 5 7 100
Demand 150 120 180 70

We can verify that the total cost of transportation for this allocation is:

3 x $1 + 2 x $3 + 7 x $2 + 6 x $2 + 5 x $3 + 4 x $2 + 9 x $1 + 3 x $2 + 5 x $3 + 7 x $4 = $156.

Thus, the North-West Corner Method provides us with an initial feasible solution to the transportation problem. However, we may need to apply the optimization techniques such as the MODI method to find the optimal solution.