The Dual Simplex method is used in situations where the optimality criterion (i.e., z_{j } c_{j} ≥ 0 in the maximization case and z_{j } c_{j} ≤ 0 in minimization case) is satisfied, but the basic solution is not feasible because under the X_{B} column of the simplex table there are one or more negative values.
The dual simplex algorithm proceeds in this way:
Formulate the mathematical model of the given linear programming problem.
Convert every inequality constraint in the LPP into an equality constraint, so that the problem can be written in a standard from.
Calculate the initial basic feasible solution by assigning zero value to the decision variables. This solution is shown in the initial dual simplex table.
If all the values under X_{B} column ≥
0, then don't apply dual simplex method because optimal solution can
be easily obtained by the simplex method.
On the contrary, if any value under X_{B} column < 0, then
the current solution is infeasible so move to step 4.
Select the smallest (most) negative value under the X_{B} column. The row that indicates the smallest negative value is the key row.
Key column = | Min | z_{j } c_{j} |
: | a_{ij} < 0 |