Obtaining Optimal Solution by Using Very Good Non-Basic Feasible Solution of the Transportation and Linear Programming Problem ()
1. Introduction
1.1. For Transportation Problem
Sharma and Prasad [2] gave a very good non-basic primal solution to the transportation problem. We give a procedure (named as PNP-1) here to make use of this (this non-basic feasible solution to get a good basic feasible solution). This enables Network Simplex to lead to optimality by making use of advanced start.
1.2. For Linear Program
Similarly, Karmarkar [3] gives a very good interior point solution to Linear Program in polynomial time. We give a procedure (PNP 2) to get very good BFS for Linear program (by using solution given in [3] ). And this enables Simplex Procedure to lead to optimality by making use of this advanced start.
2. Formulation of Transportation Problem
Problem P1.
s.t.
(1)
(2)
(3)
For the balanced transportation problem, method due to Sharma and Prasad [2] gives a very good feasible solution with exactly “p” Xik > 0. It is to be noted that in a BFS exactly K + I − 1, Xik need to be greater than zero.
3. The Proposed New Procedure PNP 1
PNP 1
Step 1: Prepare a list L of “p” Cik such that Xik’s > 0.
Then sort (“p”) Cik’s with Xik’s > 0 in increasing order. Put first K + I − 1 items of L in list L1 and remaining Cik’s with Xik’s > 0 in list L2. It is to be noted that the associated cells in L1 form a basis.
Step 2: Then we take first item from L2. It can be easily seen that cells of L1 + first cell (CE*) taken out of L2 has a unique cycle. Perform the pivot operation to determine the leaving cell (by using Cik’s as relative cost co-efficients. It can be seen that resulting partial solution may increase or decrease.
Step 3: Remove the cell CE* from the list L2. If L2 is not empty, then go to Step 2, else stop.
Step 4: We have good BFS for the balanced transportation problem (P1). Now network simplex for the transportation problem can take over.
4. Formulation of Linear Program
Problem P2.
s.t.
(4)
(5)
Matrices A, X and b are matrices of conformable dimensions (A is of the size m × n; X is of size n × 1; and b is of size m × 1). It is to be noted that a BFS to problem P2 is associated with a matrix B of size m × m. Optimal BFS has at most “m” positive entries in X (that is of size n × 1; such that m < n).
It is to be noted that Karmarkar’s algorithm [3] to solve problem P2 gives a very good interior (feasible) point that has exactly “p” positive entries in X1 such that p > m.
5. The Proposed New Procedure PNP 2
PNP 2
Step 1: It is to be noted that there are exactly p C m bases associated with the solution given to problem P2 by methods of [3] . Get one feasible basis (B1) with exactly “m” columns in X1. Intuitively it is felt that this would be a good BFS.
Step 2: Choose other column (a2) in A that is not included in B1 such that a2 belongs to X1. Set an = a2.
Step 3: Perform pivot with an as entering variable. It can be seen that an will enter the basis only if its relative cost co-efficient is strictly negative. It can be seen that the solution will improve or remain the same.
Step 4: If all columns associated with X1 belonging to (p-m) are considered for entering variable, then stop; we have a good BFS and usual simplex can proceed further to get optimal solution; else choose other column in X1 not considered earlier and call it an. Go to step 3.
We now have the optimal BFS to problem P2. It can be seen that this approach is different than the one given in [4] .
6. Conclusion
Algorithms (that give very good solutions (non-BFS in general) in competitive times: transportation problem (O(n3) & simplex (for linear program) in O(n5.5)) are available. We give a procedure that makes use for above; and gives very good BFS. Then control is given over to optimizing procedures (like Network Simplex (for transportation runs in O(n3*log(n) time) & ordinary simplex procedure for linear program (exponential time complexity) to get optimal solutions. But since we start from a very good solution, it is hoped that the optimizing procedure will take significantly less time (compared to its worst case complexity given above). An empirical investigation has been undertaken and we will submit results as early as possible.