Math Models of Operations Research, MATP 4700/ DSES 4770.

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

$$M = \begin{array}{\vert c\vert cc\vert} \multicolumn{1}{c}{}... ...\ \hline -d & c^T & 0 \\ \hline b & A & I \\ \hline \end{array}$$

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

$$\begin{array}{lrcrcl} \min & c^Tx & + & 0 s & + & d\\ \mbox... ... + & Is & = & b \\ &\multicolumn{5}{c}{x,s \geq 0} \end{array}$$

which has a dual:

$$\begin{array}{lrcl} \max & b^T \bar{y}& + & d\\ \mbox{s.t.} & A^T \bar{y}& \leq & c \\ & \bar{y}& \leq & 0. \end{array}$$

Let $y:=-\bar{y}$. Then the dual problem can be rewritten equivalently as:

$$\begin{array}{lrcl} \min & b^T y & - & d\\ \mbox{s.t.} & -A^T y & \leq & c \\ & y & \geq & 0, \end{array}$$

which can be represented as the tableau:

$$T = \begin{array}{\vert c\vert cc\vert} \multicolumn{1}{c}{}... ...\hline d & b^T & 0 \\ \hline c & -A^T & I \\ \hline \end{array}$$