North-west corner method

The north-west corner method is a heuristic method from Operations Research , which is intended to provide a valid initial solution for the transport problem. The optimization algorithm of the transport problem starts from this solution.

algorithm

Starting from the top left corner of the matrix, one looks to see whether a capacity can be exhausted or a need satisfied in the current field.

${\displaystyle c(i,j)=min(B(j),K(i))}$

When the requirements of this line are met, look in the downward column for the next field in which one of the two criteria can be met. If the capacity of the column has been exhausted, you continue to search in the row. If both are fully occupied, then you move one field diagonally to the bottom right.

Efficiency

The north-west corner method provides a starting table that often requires many more iterations of the solution algorithm until the optimal solution is found.

example

The procedure is shown using the example in the article on the transportation problem. The basis is the system of equations

${\displaystyle x_{11}+x_{12}+x_{13}=16}$

${\displaystyle x_{21}+x_{22}+x_{23}=14}$

${\displaystyle x_{11}+x_{21}=15}$

${\displaystyle x_{12}+x_{22}=5}$

${\displaystyle x_{13}+x_{23}=10}$

There are two offers A ₁ and A ₂ and three requests for applications B ₁ , B ₂ and B ₃ . Here x _ij denotes the set delivered from i to j. The system of equations can be summarized in a table as
${\displaystyle {\begin{array}{c|ccc|c}&B_{1}&B_{2}&B_{3}&\\\hline A_{1}&x_{11}&x_{12}&x_{13}&16\\A_{2}&x_{21}&x_{22}&x_{23}&14\\\hline &15&5&10&30\\\end{array}}}$

For the north-west corner solution, as much as possible is now first packed into the north-west corner. So A ₁ delivers 15 units to B ₁ . A ₁ still has one unit left, which is delivered to B ₂ . The remaining requirement of B ₂ covers A ₂ with 4 units. A ₂ has 10 units left, which go to B ₃ . One now receives
${\displaystyle {\begin{array}{c|ccc|c}&B_{1}&B_{2}&B_{3}&\\\hline A_{1}&15&1&0&16\\A_{2}&0&4&10&14\\\hline &15&5&10&30\\\end{array}}}$

A valid basic solution was achieved through the initial solution. The variables with positive quantities are the basic variables, variables with zero are non-basic variables. You can see that when you write down the above system of equations as a tableau:
${\displaystyle {\begin{array}{ccccccc}x_{11}&x_{12}&x_{13}&x_{21}&x_{22}&x_{23}&b\\\hline 1&1&1&0&0&0&16\\0&0&0&1&1&1&14\\1&0&0&1&0&0&15\\0&1&0&0&1&0&5\\0&0&1&0&0&1&10\\\end{array}}}$

If the vectors under x ₁₁ , x ₁₂ , x ₂₂ and x ₂₃ are transformed into base vectors, the result is the tableau
${\displaystyle {\begin{array}{ccccccc}x_{11}&x_{12}&x_{13}&x_{21}&x_{22}&x_{23}&b\\\hline 1&0&0&1&0&0&15\\0&0&-1&1&1&0&4\\0&1&1&-1&0&0&1\\0&0&1&0&0&1&10\\0&0&0&0&0&0&0\\\end{array}}}$

which reproduces the north-west corner solution.

literature

• Gert Heinrich : Operations Research , Oldenbourg, 2nd edition, pp. 59-61. web
• Bodo Runzheimer: Operations Research 1: Linear planning calculation and network planning technology , pp. 96–98. web