Dual Simplex Method: Linear Programming

The Dual Simplex method is used in situations where the optimality criterion (i.e., zj cj ≥ 0 in the maximization case and zj cj ≤ 0 in minimization case) is satisfied, but the basic solution is not feasible because under the XB 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.

Algorithm, Example

The dual simplex algorithm proceeds in this way:

Steps of Dual Simplex Algorithm Steps of Dual Simplex Algorithm

1. Formulate the Problem

Formulate the mathematical model of the given linear programming problem.

"The model is a vehicle for arriving at a well-structured view of reality." -Anonymous

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 XB 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 XB 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 XB 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 (zj cj), 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

Key column = Min

zj cj


aij < 0

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.

The rules for determining a key column and key row differentiate the dual simplex method from the standard simplex method.

Share this article with your friends