A non improving simplex algorithm for transportation problems

A simplex type algorithm for the Transportation Problem (TP) is presented. TPs with total demand D, m supply and n demand nodes are shown to be solved at most O(μ(m+n)D) time and in at most μD-μ(μ-1)/2 iterations, where μ=min{m,n). The algorithm can be initialized with a solution that is neither primal nor dual feasible. The objective function decreases until a dual feasible solution is constructed and then it starts increasing.