Accession Number : AD0717646

Title :   A One-Pass 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 poly-omega 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