Dual Simplex Method: Linear Programming

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.

What are the reasons for studying the dual simplex method?

• Sometimes it allows to easily select an initial basis without having to add any artificial variable.
• It aids in certain types of sensitivity testing.
• It helps in solving integer programming problems.

The dual simplex algorithm proceeds in this way:

Steps of Dual Simplex Algorithm

1. Formulate the Problem

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.

2. Find out the Initial Solution

Calculate the initial basic feasible solution by assigning zero value to the decision variables. This solution is shown in the initial dual simplex table.

3. Determine an improved solution

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.

4. Determine the key row

Select the smallest (most) negative value under the X_B column. The row that indicates the smallest negative value is the key row.

5. Determine the key column

Select the values of the non basic variables in the index row (z_j c_j), and divide these values by the corresponding values of the key row determined in the previous step. Specifically,

Use Horizontal Scrollbar to View Full Formula

7. Revise the Solution

If all basic variables have non-negative values, an optimal solution has been obtained. If there are basic variables having negative values, then go to step 3.