Northwest Corner Method (Transportation Algorithm in Linear Programming)

Northwest Corner Model solution

The Northwest Corner Method (or upper left-hand corner) is a heuristic that is applied to a special type of Linear Programming problem structure called the Transportation Model, which ensures that there is an initial basic feasible solution (non artificial). Other methods for obtaining an initial basic solution are the Minimum Cell Cost Method and the Vogel Approximation Model. Generally, Vogel’s Model produces the best initial basic solution and the Northwest Corner the worst; nevertheless, the Northwest Corner Method involves the least number of calculations.

The Northwest Corner Method starts in the cell (route) corresponding to the northeast corner, or the upper left, of the tableau (variable x_{11}). Below is a description of the steps:

  1. Step 1: Allocate the maximum amount available to the selected cell and adjust the associated supply and demand quantities by subtracting the allocated quantity.
  2. Step 2: Exit the row or the column when the supply or demand reaches zero and cross it out, to show that you cannot make any more allocations to that row or column. If a row or a column simultaneously reach zero, only cross out one (the row or the column) and leave a zero supply (demand) in the row (column) that is not crossed out.
  3. Step 3: If exactly one row or column is left that is not crossed out, stop. Otherwise, advance to the cell to the right if a column has just been crossed out, or to the cell below if a row was crossed out. Continue with Step 1.

Northwest Corner Method Example

In order to illustrate how to apply the Northwest Corner Method we will consider the following balanced transportation model that takes into account 3 silos products (supply) that satisfy the needs of 4 mills (demand). The transportation algorithm is based on the hypothesis that the model is balanced, in other words, that the total demand is equal to the total supply (if the model is not balanced it can always be increased with a fictitious source or a fictitious destination to restore the equilibrium or balance).

Northwest Corner Method Example

The per unit transport costs from silo i to mill (c_{ij}) is represented in the upper right-hand corner of each box. For example the unit cost of sending one product unit from silo 1 to mill 1 is $10. Furthermore silos 1, 2 and 3 have a capacity and supply of 15, 25 and 10 units, respectively. On the other hand mills 1, 2, 3 and 4 have requirements or demands of 5, 15, 15 and 15 units, respectively. The model is balanced (sum of the supply = sum of the demand = 50 units). By applying the Northwest Corner Model to the previous example the following results are obtained. The arrows indicate the order in which the allocated quantities are generated:

Northwest Corner Model solution

  • The quantity allocated to cell x_{11} is 5 units, given that although silo 1 has a capacity of 15 units, mill 1 only needs (demand) 5 units (no more allocations are made to column 1 corresponding to mill 1).
  • Next we will move to the right and assign the maximum (10 remaining units) to cell x_{12} (thereby completing the capacity of silo 1 and as a result it is no longer possible to make allocations to row 1).
  • Then we allocate 5 units to cell x_{22}, which is actually less than the capacity of silo 2 but enough to satisfy the requirements of mill 2 (it is no longer possible to make additional allocations to column 2).We move to the right and allocate the maximum possible (5 units, which is the remaining capacity of silo 2, meaning that x_{24}=5), with which silo 2 operates at maximum capacity (new allocations to row 2 are no longer possible).
  • Finally 10 units are allocated from silo 3 to mill 4 (x_{34}=10) meeting the mill’s demand (and the capacity of the corresponding silo).

Therefore the initial basic feasible solution is: x_{11}=5, x_{12}=10, x_{22}=5, x_{23}=15, x_{24}=5, x_{34}=10, reporting a program cost (the objective function value) of: Z=5(10)+10(2)+5(7)+15*(9)+5(20)+10*(18)=$520. Note that if the above problem is implemented computationally using Solver from Excel and Simplex LP as a problem solver, the following optimal solution is found (yellow cells) with a minimum cost (optimal value) of $435.

Northwest Corner Model solver

Rating: 4.1/5. From 18 votes.
Please wait...

8 thoughts on “Northwest Corner Method (Transportation Algorithm in Linear Programming)”

  1. Your explanation with illustration diagrammatically made understanding of the topic easy. Thanks for the good work.

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.