Accession Number : AD0774031

Title :   A Computational Study of the Effects of Problem Dimensions on Solution Times for Transportation Problems.

Descriptive Note : Research rept.,


Personal Author(s) : Klingman,D. ; Napier,A. ; Ross,G. Terry

Report Date : OCT 1973

Pagination or Media Count : 24

Abstract : The paper presents an indepth study of the influence of problem structure on the computational efficiency of the primal simplex transportation algorithm. The input for the study included over 1000 randomly generated problems with 185 different combinations of the number of sources, the number of destinations and the number of variables. Objective function coefficients were generated using three different probability distributions to study the effects of variance and skewness in these parameters. Every problem was solved using three different starting procedures, and the following data were collected for each problem: (1) Time required to obtain an optimal solution; (2) time required to obtain an initial basic solution; (3) number of artificial variables in the initial basic solution; (4) number of basis changes; (5) average time to perform a change of basis; (6) average number of basic variables in the 'stepping stone path' in each change of basis; (7) average number of variables considered before selecting one to enter the basis. (Modified author abstract)

Descriptors :   *Network flows, *Linear programming, Transportation, Simplex method, Algorithms, Probability density functions

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE