Further results on the algebraic characterizations of a minimum cost network flow problem equivalent to the transportation problem

Abstract

In this study a minimum cost network flow problem with m+n+2 nodes and mn arcs, which is equivalent to the transportation problem with m sources and n destinations, is described as an axial four-index transportation problem of order 1×m×n×1. Several algebraic characterizations of this problem of order 1×m×n×1 are investigated using the singular value decomposition and generalized inverses of its coefficient matrix. The results are compared with some results on the planar four-index transportation problem. It is shown that these problems have common algebraic characterizations and can be solved in terms of eigenvectors of the matrices J _m and J _n where J _m is an m×m matrix, all of whose entries are 1.

Keywords:

• Minimum cost network flow problem
• Transportation problem
• Singular value decomposition
• Generalized inverses