Lecture_12_Computational Procedure of Dual Simplex Method

12.1 Introduction


Any LPP for which it is possible to find infeasible but better than optimal initial basic solution can be solved by using dual simplex method. Such a situation can be recognized by first expressing the constraints in ‘?’ form and the objective function in the maximization form. After adding slack variables, if any right hand side element is negative and the optimality condition is satisfied then the problem can be solved by dual simplex method.

Negative element on the right hand side suggests that the corresponding slack variable is negative. This means that the problem starts with optimal but infeasible basic solution and we proceed towards its feasibility.

The dual simplex method is similar to the standard simplex method except that in the latter the starting initial basic solution is feasible but not optimum while in the former it is infeasible but optimum or better than optimum. The dual simplex method works towards feasibility while simplex method works towards optimality.

12.2 Computational Procedure of Dual Simplex Method

The iterative procedure is as follows

Step 1 - First convert the minimization LPP into maximization form, if it is given in the minimization form.

Step 2 - Convert the ‘?’ type inequalities of given LPP, if any, into those of ‘?’ type by
multiplying the corresponding constraints by -1.

Step 3 – Introduce slack variables in the constraints of the given problem and obtain an initial basic solution.

Step 4 – Test the nature of ?j in the starting table
• If all ?j and XB are non-negative, then an optimum basic feasible solution has been attained.
• If all ?j are non-negative and at least one basic variable XB is negative, then go to step 5.
• If at least ?j one is negative, the method is not appropriate.

Step 5 – Select the most negative XB. The corresponding basis vector then leaves the basis set B. Let Xr be the most negative basic variable.

Step 6 – Test the nature of Xr
• If all Xr are non-negative, then there does not exist any feasible solution to the given problem.
• If at least one Xr is negative, then compute Max (?j / Xr ) and determine the least negative for incoming vector.
Step 7 – Test the new iterated dual simplex table for optimality.

Repeat the entire procedure until either an optimum feasible solution has been attained in a finite number of steps.