NW Corner Rule

The North-West Corner Rule is a method used to find an initial feasible solution for transportation problems in linear programming. The algorithm starts at the "north-west corner" (top-left cell) of the cost matrix and proceeds step by step until all the supply and demand requirements are met.

Steps to Apply the North-West Corner Rule

1. Start at the top-left cell (north-west corner) of the cost matrix.
2. Allocate as much as possible to this cell without exceeding the supply or demand.
3. Adjust the supply and demand based on the allocation:
   • Subtract the allocated amount from both the supply and demand.
4. Move to the next cell:
   • If the supply for the current row is exhausted, move down to the next row.
   • If the demand for the current column is exhausted, move right to the next column.
5. Repeat steps 2-4 until all supplies and demands are met.

Example Problem

Suppose we have three factories (A, B, C) that need to supply goods to three warehouses (X, Y, Z). The supplies, demands, and transportation costs per unit are as follows:

Step 1: Start at the top-left cell (A-X).

• The supply at A is 30, and the demand at X is 20.
• Allocate 20 units to A-X (minimum of 30 and 20).
• Update the remaining supply at A to 30 - 20 = 10, and the remaining demand at X to 20 - 20 = 0.

Step 2: Move right to the next column (A-Y).

• The supply at A is now 10, and the demand at Y is 50.
• Allocate 10 units to A-Y (minimum of 10 and 50).
• Update the remaining supply at A to 10 - 10 = 0, and the remaining demand at Y to 50 - 10 = 40.
• Since the supply at A is now exhausted, move down to the next row (B).

Step 3: Allocate from B-Y.

• The supply at B is 40, and the demand at Y is 40.
• Allocate 40 units to B-Y (minimum of 40 and 40).
• Update the remaining supply at B to 40 - 40 = 0, and the remaining demand at Y to 40 - 40 = 0.
• Move to the next column (Z).

Step 4: Move to the next row (C) and allocate to C-Z.

• The supply at C is 20, and the demand at Z is 20.
• Allocate 20 units to C-Z (minimum of 20 and 20).
• Update the remaining supply at C to 20 - 20 = 0, and the remaining demand at Z to 20 - 20 = 0.

Final Allocation

The allocations are as follows:

Summary

• The North-West Corner Rule provides an initial feasible solution but does not guarantee an optimal solution. Further optimization methods, such as the stepping-stone method or the MODI (Modified Distribution) method, may be needed to find the optimal solution.