Accession Number : AD0470834


Title :   ONE-PASS ALGORITHMS FOR SOME GENERALIZED NETWORK PROBLEMS


Descriptive Note : Research memo.


Corporate Author : NORTHWESTERN UNIV EVANSTON IL TECHNOLOGICAL INST


Personal Author(s) : Charnes, Abraham ; Raike, William M


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/470834.pdf


Report Date : Aug 1965


Pagination or Media Count : 20


Abstract : The generalized network problem and the closely related restricted dyadic problem are two special model types which occur frequently in applications of linear programming. Although they are next in order after pure network or distribution problems with respect to ease of computation, the jump in degree of difficulty is such that, in the most general problem, there exist no algorithms for them comparable in speed or efficiency to those for pure network or distribution problems. There are, however, numerous examples in which some additional special structure leads one to anticipate the existence of algorithms which compare favorably with the efficiency of those for the corresponding pure cases. Also, these more special structures may be encountered as part of larger or more complicated models. In this paper topological properties designate two special structures which permit evolution of efficient algorithms. These follow by extensions of methods of Charnes and Cooper and of Dijkstra for the corresponding pure network problems. Easily implemented algorithms are obtained which provide an optimum in one pass through the network. The proofs provided for these extended theorems differ in character from those provided (or not provided) in the more special pure problem algorithms published.


Descriptors :   *NETWORKS , DECISION THEORY , INFORMATION THEORY , LINEAR PROGRAMMING , MANAGEMENT , MATHEMATICS , OPTIMIZATION , SYSTEMS ENGINEERING , TOPOLOGY


Subject Categories : Computer Systems


Distribution Statement : APPROVED FOR PUBLIC RELEASE