A Study Of Some New Problems Arising From The Field Of Minimum Cost Network Flows

Everywhere we look in our daily lives, networks are apparent. Network flows areof growing interest over the last few decades from the point of view of both applica-tions and theory. The topic of network flows has applications in such wide fields aschemistry and physics, computer networking, most branches of engineering, manufac-turing, public policy, and social systems, scheduling and routing, telecommunications,and transportation. It is classical, dating from the work of Gustav Kirchhoff and othereminent physical scientists of last century, and yet vibrant and current, bursting withnew results and new approaches.The minimum cost flow model is the most fundamental of all network flow prob-lems. It has been extensively studied and fruitful results have been developed. In thisthesis, we focus on some new problems arising from the field minimum cost networkflow problems, propose some generalized models based these new problems, and de-velop a series of results.There are totally seven chapters in this thesis. In Chapter 1, we introduce theproblems that we will work on, and make a brief history overview of related existingresults in the literature.In Chapter 2, we make a brief introduction to the basic concepts and necessaryknowledge about network flows.Chapter 3 firstly gives a brief overview of the main problem and results presentedby Profs. Fang and Qi. Next, with regard to the network simplex method proposed byFang and Qi for solving MDCF, a method for finding an initial basic feasible solutionof MDCF is proposed After that, we generalize the definition of the so-called pivot-ing cycle resulted from applying network simplex method, and consequently developa more combinatorial method for computing the reduced cost for nonbasic variables,which works directly on the network.In Chapter 4, we extend and presents some further results of a previous work stud-ied by Fang and Qi on a MDCF network model with special side constraints requiringproportional distribution at some nodes. This extension allows us to model a largervariety of practical network flow problems where some nodes may not necessarily pre- serve the flow conservation constraints. The network structure and properties of thebasic feasible solution are extensively investigated, and a variant of network simplexalgorithm is proposed for solving several types of generalized MDCF problems. Theproposed variant of the network simplex algorithm allows us to take advantage of thepractical computational capabilities of the network structure of the basic feasible graph.In Chapter 5, we firstly extend the manufacturing network flow (MNF) problemby Fang and Qi to generalized network model, and then, motivated by their work, wefocus on investigating the network structure of the bases of simplified version of thegeneralized MNF model, called generalized minimum distributed cost flow (GMDCF)problem. Each basis of the GMDCF problem is characterized as the union of a goodaugmented forest (containing a root arc at the S-node and some exiting arcs at T-nodes)and some additional arcs, this structure plays a key role in designing and developingour generalized distribution network simplex algorithm. The proposed network ap-proach provides some insight into designing combinatorial approach for solving othergeneralized manufacturing network flow problems.Equal flow problem is one of the widely studied network flow problems with addi-tional side constraints. In Chapter 7, on the one hand, we extend the equal flow problemto generalized flow model. On the other hand, we extend the equal flow constraints toproportionate flow constraints, thus making the equal flow problem a special case of ourproblem, which we refer to as generalized minimum cost proportionate flow (GMCPF)problem. After characterizing the network structure of GMCPF problem, we proposea generalized network simplex algorithm which exploits the network structure of theGMPCF problem. Moreover, we present in detail the main steps of the proposed net-work simplex algorithm. And numerical example is given to illustrate the efficiency ofthe algorithm.Finally in Chapter 7 conclusions are made and some interesting open problems aregiven for further research.