The Hesse-Woolsey-Stern Algorithm for the Transportation Problem: An Explication

Hesse and Woolsey [Hesse, Rick, Gene Woolsey. 1980. Applied Management Science: A Quick and Dirty Approach. SRA, Chicago, 177.], following Stern [Stern, M. E. 1963. Mathematics for Management. Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 396–400.], present an attractive way of modifying the Hungarian method for assignment problems so as to apply it to transportation problems in general. Their method consists in reducing the costs matrix by row and column reductions so as to identify the cells with zero relative/opportunity cost, and if necessary generating more zeros at later stages (by using the method of finding the smallest element not covered by a line when covering the zeros by using the minimum number of lines). It is shown here that it is not a sufficient condition for making an all-zero-cost allocation.