Minimum Cost Network Flow Problem and Network Simplex Method
No Thumbnail Available
Date
2015-07
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Addis Ababa University
Abstract
The Minimum Cost Network Flow (MCNF) Problem is to send flow from a set of supply or source nodes, through the arcs of a network, to a set of demand or destination nodes, at minimum total cost, and without violating the lower and upper bounds on flows through the arcs. The MCNF framework is particularly broad, and may be used to model a number of more specialized network problems including Assignment, Transportation, Trans-shipment problems, the Shortest Path Problem and the Maximum Flow problem.
The Network Simplex Method (NSM) is a part of the bounded variable primal simplex al-gorithm, specifically for the MCF problem. The basis is represented as a rooted spanning tree of the underlying network, in which arcs represent variables. The method iterates towards an optimal solution by exchanging basic and non-basic arcs. At each interaction, an entering arc is selected by some pricing strategy, and an arc to leave the basis is as-certained. The construction of a new basis tree is called the pivot. There are many strat-egies for selecting the entering arc, and these determine the speed of solution.
This seminar report contains three chapters. In the first chapter I tried to discuss some basic idea of network systems such as their mathematical character, modeling the mini-mum cost network flow problem in standard linear programming form, graphical repre-sentation and matrices representation of the minimum cost network flow. Moreover the general minimum cost network flow problems and Application of the modeling in the se-cond chapter and one of the solutions methodologies (network simplex method) is dis-cussed in the third chapter, I apply the concepts of the first and the second chapter for the generating optimum solution for minimum cost Network flow problems using sim-plex algorism
Description
Keywords
Minimum Cost Network Flow Problem