Duality & Sensitivity Testing

Dual Simplex Method

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.

• 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:

Algorithm - Steps

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 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,
  

  Key column =

  Min

  zj – cj -------- aij

  :

  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.