A Network Model: Minimum Cost Network Flow Problem (MCNFP)

There is a multitude of Operations Research (OR) situations that can be modeled and solved as networks. Some recent surveys report that as much as 70% of the real-world mathematical programming problems can be represented by network related models. Network models are one of the earliest branches of OR and the Minimum Cost Network Flow Problem (MCNFP) is the most fundamental of all network flow models. The MCNFP has a great importance in a number of familiar applications. In the last two decades, there are various fast and practical algorithms for the linear single-commodity minimum cost network flow problem have been proposed. It is well-known that the simplex method is statistically the most powerful method ever devised for linear programming and the network simplex method is useful to MCNFP. One of the nice features of this monograph is the Network Simplex Method (NSM) for the minimum cost network flow problem. A modified form of network simplex method which belongs to a special “exterior point simplex type” category for solving the MCNFP is developed here.The modified method is usually applied to an uncapacitated MCNFP.