ABSTRACT
Many of the more practical linear programming problems can be expressed as network flow problems. In this chapter, the authors discuss the constraints of such problems possess an especially simple structure which allows very efficient algorithms to be designed for these problems. The authors modify the primal simiplex procedure for the uncapacitated minimal cost network flow problem. They develop the maximal flow algorithm independently from graph theory. Several specializations of the primal-dual algorithm are presented for various types of network flow problems. The authors describe several types of network flow problems and present some material from graph theory. In a network flow problem, a commodity is to flow through the network in such a way that certain supply and demand requirements are satisfied. He authors examine the maximal flow problem can be solved as a minimal cost network flow problem by using the network simplex procedure.
