One alternative to the minimum cost selection rule for the transportation algorithm is the Northwest Corner Rule. In this approach, the chosen sequence of basic variables is simpler. Display the variables \(x_{i j}\) in an array as shown below:

First let \(x_{11}\) be basic (i.e., begin in the northwest corner of the array) and let all other variables in the binding constraint be non-basic. If the supply constraint was binding, then \(x_{1 j}\) are declared non-basic for all \(j=1, \ldots, n\),and we may effectively delete the first row of the array. If the binding constraint was the demand constraint, then the first column may be deleted. Choose as the next entering basic variable the entry in the northwest corner of the reduced array. In the first case above, the next basic variable would be \(x_{21}\), and in the second case it would be \(x_{12}\). Continue in this manner until there are \(m+n-1\) basic variables.

(a) Why should you expect that in general this approach will not lead as quickly to an optimal solution as the minimum cost algorithm?

(b) (Mathematica) Redo Example 1 using the Northwest Corner Algorithm.

Transcribed Image Text:

X11 12 X12 X13 13 Xin X21 X22 x22 X23 X2n Xm1 Xm2 Xm3. Xmn