Experimental studies of the transportation problem

The study investigates the Transportation Problem. Specifically, it considers the interaction of four initial solution algorithms, Northwest Corner, Column minimization, Vogel Approximation Method, and Matrix Minimization methods with the Balinski- Gomory and MODI final solution techniques. The experiments consider problem matrix sizes from 25 elements (5 x 5) to 2500 elements (50 x 50) with five intermediate points. Data is presented and analyzed considering the frequency of a) matrix searching, b) non-breakthrough, c) degeneracy, and d) labeling. Time data is also presented. The theoretical aspects of both final solution algorithms are discussed, as well as the machine logic. The actual computer programs are presented in the appendices. The results of this investigation show that the Matrix Minimum initial solution algorithm is superior to the others studied. It also shows that the popular notion of the Vogel Approximation method being superior is not true. The Balinski-Gomory algorithm proved to be slightly superior to the MODI in problem sizes up to 2500 elements; above this point, Balinski-Gomory was far superior. A new and superior algorithm was developed to simplify the Matrix Minimum method. This algorithm is discussed in detail.