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

Ozel M., Safak S., Bulut H.

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, vol.82, no.5, pp.609-616, 2005 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 82 Issue: 5
  • Publication Date: 2005
  • Doi Number: 10.1080/00207160512331331192
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.609-616
  • Keywords: minimum cost network flow problem, transportation problem, singular value decomposition, generalized inverses, CONSTRUCTION, PLANAR
  • Dokuz Eylül University Affiliated: Yes


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 x m x n x 1. Several algebraic characterizations of this problem of order 1 x m x n x 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 [5]. 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 x m matrix, all of whose entries are 1.