
Accession Number : AD0717646
Title : A OnePass Algorithm to Determine a Dual Feasible Basic Solution for a Class of Capacitated Generalized Networks.
Descriptive Note : Research rept.,
Corporate Author : TEXAS UNIV AUSTIN CENTER FOR CYBERNETIC STUDIES
Personal Author(s) : Glover,Fred W. ; Klingman,Darwin D. ; Napier,H. Albert
Report Date : OCT 1970
Pagination or Media Count : 30
Abstract : The generalized network problem and the closely related restricted dyadic problem occur frequently in applications of linear programming. Although they are next in order of computational complexity after pure network or distribution problems, the jump in degree of difficulty is such that, in the most general problem, there exist no algorithms comparable in speed to those for pure networks. In the paper, one characterizes the topological properties of a special class of generalized network problems that permit a dual feasible basic solution to be determined in one pass through the network. In particular, this class includes the class of pure network problems for which no such procedure previously existed. Our algorithm also makes it possible to efficiently apply Lemke's dual method and the polyomega technique of Charnes and Cooper to solve capacitated (pure) network problems. (Author)
Descriptors : (*LINEAR PROGRAMMING, ALGORITHMS), TRANSPORTATION, TOPOLOGY, MATRICES(MATHEMATICS), HILBERT SPACE, SET THEORY
Subject Categories : Operations Research
Distribution Statement : APPROVED FOR PUBLIC RELEASE