Obtaining Optimal Solution by Using Very Good Non-Basic Feasible Solution of the Transportation and Linear Programming Problem

Abstract

For the transportation problem, Sharma and Sharma [ 1 ] have given a very computationally efficient heuristic (runs in O(c*n 2 ) time) to give very good dual solution to transportation problem. Sharma and Prasad [ 2 ] have given an efficient heuristic (complexity O(n 3 ) procedure to give a very good primal solution (that is generally non-basic feasible solution) to transportation problem by using the very good dual solution given by Sharma and Sharma [ 2 ]. In this paper we use the solution given by Sharma and Prasad [ 2 ] to get a very good Basic Feasible Solution to transportation problem, so that network simplex (worst case complexity (O(n 3 *(log(n))) can be used to reach the optimal solution to transportation problem. In the second part of this paper, we give a simple heuristic procedure to get a very good BFS to linear programming problem from the solution given by Karmarkar [ 3 ] (that generally produces a very good non-basic feasible solution in polynomial time (O(n 5.5 )). We give a procedure to obtain a good BFS for LP by starting from the solution given by Karmarkar [ 3 ]. We note that this procedure (given here) is significantly different from the procedure given in [ 4 ].