An Example of the Dual Simplex Method
In this handout, we give an example demonstrating that the dual simplex method is equivalent to applying the simplex method to the dual problem. We have a tableau in the form
where c ≥ 0 but b has some negative components. We want to find the optimal solution. This tableau represents the problem
which has a dual:
Let y := - . Then the dual problem can be rewritten equivalently as:
which can be represented as the tableau:
Consider the following tableau, and solve it using the dual simplex method:
Making the indicated dual simplex pivot gives:
Making the indicated dual simplex pivot gives the optimal tableau:
We will now solve the dual of the example problem using the simplex method. The primal tableau will be called M and the dual tableau T. We will use the same sequence of dual simplex updates as previously, and apply the standard simplex method to the dual. It will be clear that the pivots in M and T are equivalent. We will rearrange the columns of the primal and dual simplex tableaus so that the identity matrix appears at the end, to make it obvious that the sequence of tableaus are duals to one another.
These tableaus are optimal for the primal and dual problems.