A Noniterative Algorithm for Tridiagonal Transportation Problems and Its Generalization

Abstract

Some transportation problems are such that, when origins and destinations are suitably indexed, the cost matrix contains elements along the main diagonal, a band above it, and a band below it, while the other elements of the cost matrix are infinite. We present here a procedure that yields optimal solution to such tridiagonal problems in n steps for an n-origin, n-destination problem. We also suggest a method for solving any other model that is “close” to a tridiagonal one by Bender's Algorithm. The algorithm presented here works by eliminating all off-diagonal variables in terms of the diagonal ones, and then specifying values for the diagonal variables. The extension with Bender's Algorithm involves solution of a sequence of tridiagonal models and small linear programming problems.