A One-Pass Algorithm to Determine a Dual Feasible Basic Solution for a Class of Capacitated Generalized Networks

摘要

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)