Accession Number : AD0749716

Title :   On Solving Constrained Transportation Problems,

Corporate Author : TEXAS UNIV AUSTIN CENTER FOR CYBERNETIC STUDIES

Personal Author(s) : Klingman,D. ; Russell,R.

Report Date : AUG 1972

Pagination or Media Count : 39

Abstract : The paper presents a computationally efficient method for solving transportation problems with several additional constraints. The method is basically the primal simplex method specialized to fully exploit the topological structure embedded in the problem. It couples the Poly-omega technique of Charnes and Cooper with the Row-Column Sum Method to yield an 'inverse compactification' which minimizes the basis information that has to be stored between successive iterations, and in addition minimizes the arithmetic calculations required in pivoting. In particular the solution procedure only requires the storage of a spanning tree and a (q + 1) x q matrix (where q is the number of additional constraints) for each basis. The steps of updating costs and finding representations reduce to a sequence of simpler operations which fully utilize the triangularity of the spanning tree. Procedures for obtaining basic primal 'feasible' starts are also presented. (Author)

Descriptors :   (*LINEAR PROGRAMMING, ALGORITHMS), (*TRANSPORTATION, MATHEMATICAL MODELS), SIMPLEX METHOD, MATRICES(MATHEMATICS), GRAPHICS, THEOREMS

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE