Lecture_13_Computational Procedure of Dual Simplex Method

13.1 Introduction
Lecture 13
Linear programming :
Computational Procedure of Dual Simplex Method
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.
13.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.
1
Repeat the entire procedure until either an optimum feasible solution has been attained in a finite
number of steps.