An Example of the Dual Simplex Method

John Mitchell

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

|----|x---s-| M = |- d |cT 0 | |-b--|A---I-| -------------

where c ≥ 0 but b has some negative components. We want to find the optimal solution. This tableau represents the problem

T min c x + 0s + d s.t. Ax + Is = b x,s ≥ 0

which has a dual:

max bT Ży + d s.t. AT Ży ≤ c Ży ≤ 0.

Let y := -Ży . Then the dual problem can be rewritten equivalently as:

min bTy - d T s.t. - A y ≤ c y ≥ 0,

which can be represented as the tableau:

y z |--|---T-----| T = |d-|--b-T--0-| -c----A----I-|

1 Using the dual simplex method directly

Consider the following tableau, and solve it using the dual simplex method:

|----|x1--x2---x3--x4--x5-| M = |--3-|-1---0----2---1---0-| | 1 | 1 1 0 2 0 | |- 2 |- 1 0 - 1 0 1 | ---------------------------

Making the indicated dual simplex pivot gives:

x1 x2 x3 x4 x5 |----|--------------------| M = |--5-|-0---0----1---1---1-| |- 1 | 0 1 - 1 2 1 | ---2---1---0----1---0--- 1-

Making the indicated dual simplex pivot gives the optimal tableau:

|----|x1---x2--x3---x4---x5-| |- 6 | 0 1 0 3 2 | M = |--1-|-0----1---1----2----1-| | | | |--1---1----1---0----2----0--

2 Applying the simplex method to the dual problem

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.

|--|y1---y2--y3--y4--y5-| |----|-x1--x3---x4--x2--x5-| 3 | 1 - 2 0 0 0 | M = |--3-|--1---2----1---0---0-| T = 1--|- 1---1---1---0---0-| | 1 | 1 0 2 1 0 | | | | |- 2 |- 1 - 1 0 0 1 | 2 | 0 1 0 1 0 | --------------------------- 1---- 2---0---0---0---1-- y1 y3 y2 y4 y5 |----|-x5--x3---x4--x2--x1-| |--|--------------------| ---5----1---1----1---0---0-| 5--|- 1---2---0---0---0-| M = |- 1 | 1 - 1 2 1 0 | T = 1 |- 1 1 1 0 0 | | | | 1 | 1 - 1 0 1 0 | ---2----1---1----0---0---1-| 1 |- 2 0 0 0 1 | ------------------------- x5 x2 x4 x3 x1 |--|y4---y3--y2--y1--y5-| |--6-|-2----1----3---0---0-| |6-|-1----1---0---0---0-| M = |----|---------------------| T = |2 | 1 0 1 0 0 | | 1 |- 1 - 1 - 2 1 0 | |1 | 1 - 1 0 1 0 | ---1---0----1----2---0---1-- | | | -3---2----2---0---0---1-|

These tableaus are optimal for the primal and dual problems.