# The Dual Simplex Method

## Table of Contents

The Simplex Method^{1} pivots from *feasible* dictionary to
*feasible* dictionary attempting to reach a dictionary whose \(z\)-row
has all of its coefficients non-positive. In sensitivity analysis
certain modifications of an LP will lead to dictionaries whose
\(z\)-row “looks optimal” but that are not feasible. To take advantage
of those those dictionaries, we will develop a dual version of the
Simplex Method. Call a dictionary **dual feasible** if all the
coefficients in its \(z\)-row are non-positive. The **Dual Simplex
Method** will pivot from *dual* feasible dictionary to *dual* feasible
dictionary working towards *feasibility*.

This new pivoting strategy is called the Dual Simplex Method because it really is the same as performing the usual Simplex Method on the dual linear problem. This also explains the term “dual feasible”: each dictionary for the primal has a corresponding dictionary for the dual and a primal dictionary is dual feasible exactly when the corresponding dictionary for the dual is feasible (in the usual sense). We won’t really take advantage of this correspondence, though: we won’t directly talk about the dual LP instead explaining how to perform these dual pivots directly on a dual feasible dictionary for the primal.

But before that, let’s show how certain kinds of sensitivity analysis naturally lead to dual feasible dictionaries.

## Change of right-hand sides

Let’s start, as usual, with the linear program:

\((\mathsf{P})\) Maximize \( \mathbf{c} \cdot \mathbf{x} \)

subject to \(\left\{\begin{aligned} A \mathbf{x} & \le \mathbf{b} \\ \mathbf{x} & \ge 0 \\ \end{aligned}\right.\)

Now consider changing \(\mathbf{b}\) to \(\hat{\mathbf{b}} = \mathbf{b} + \Delta \mathbf{b}\) in the problem \((\mathsf{P})\) to get a problem \((\hat{\mathsf{P}})\). Say \(\mathbf{x}_B\) is an optimal basis for \((\mathsf{P})\). The matrix formulas say the dictionary is given by:

\[\begin{aligned} \mathbf{x}_B & = A_B^{-1} \mathbf{b} - A_B^{-1} A_N \mathbf{x}_N \\ z & = \mathbf{c}_B^\top A_B^{-1} \mathbf{b} + \left(\mathbf{c}_N^\top - \mathbf{c}_B^\top A_B^{-1} A_N \right) \mathbf{x}_N \end{aligned}\]

Let’s try to use the same basis for the new problem. The dictionary would be:

\[\begin{aligned} \mathbf{x}_B & = A_B^{-1} \hat{\mathbf{b}} - A_B^{-1} A_N \mathbf{x}_N \\ z & = \mathbf{c}_B^\top A_B^{-1} \hat{\mathbf{b}} + \left(\mathbf{c}_N^\top - \mathbf{c}_B^\top A_B^{-1} A_N \right) \mathbf{x}_N \end{aligned}\]

Notice the coefficients of \(\mathbf{x}_{N}\) in the \(z\)-row are
unchanged, so this dictionary is automatically *dual* feasible. But
this dictionary is not necessarily *feasible*: it is feasible
precisely when \(A_B^{-1} \hat{\mathbf{b}} \ge 0\). So we recover what
we knew from the marginal values theorem: when \(A_B^{-1}
\hat{\mathbf{b}} \ge 0\) the same basis is still optimal for the
modified primal \((\hat{\mathsf{P}})\).

And when that condition does not hold, we are left with a dictionary that is dual feasible but infeasible. The Dual Simplex Method will let us solve the modified LP using this as starting dictionary.

## Adding a constraint

Now consider instead adding a new constraint to \((\mathsf{P})\). The
new constraint will require adding a new slack variable, say
\(x_{m+n+1}\). We need to add this new variable to the final
dictionary as either a basic or non-basic. Once again we take our
inspiration from the way one writes an initial dictionary: we’ll guess
this new slack variable should be *basic*.

We can easily express the new slack variable in terms of the original (i.e., non-slack) variable of \((\mathsf{P})\), indeed, if the new constraint is \(a_{m+1, 1} x_1 + a_{m+1, 2} x_2 + \cdots + a_{m+1, n} x_n \le b_{m+1}\), then the new slack variable is simply \(x_{m+n+1} = b_{m+1} - a_{m+1, 1} x_1 - a_{m+1, 2} x_2 - \cdots - a_{m+1, n} x_n\). But to add a row to the dictionary for \(x_{m+n+1}\) we’ll need a formula for it in terms of the basic variables. That’s both easy and familiar: it’s just like the step in the 2-phase Simplex Method right after phase 1 is over and we need to find a formula for the objective function in terms of the current basis variables. Here we do the same thing: in the formula for \(x_{m+n+1}\) above we plug in whatever the dictionary says for each basic variable occuring, to obtain a formula in terms of only non-basics.

The resulting dictionary for \((\hat{\mathsf{P}})\) just has an extra row compared to the final dictionary for \(\mathsf{P}\); in particular, it has exactly the same \(z\)-row, so it is automatically dual feasible. And it is “mostly feasible” too: all the basic variables except for the new one, namely \(x_{m+n+1}\), have the same values as before, so they are all non-negative.

So, if the resulting value for \(x_{m+n+1}\) in the new row is non-negative, then the new dictionary is optimal. If not, it is at least dual feasible and the Dual Simplex Method can take it from there.

## Performing dual pivots

OK, so now we have to explain how to perform a dual pivot. Remember we will start from a dictionary that is dual feasible and must maintain dual feasibility. For example, say we have the dictionary:

\[\begin{array}{rrrrr} x_2 = & 5 & - 2x_1 & - x_3 & + 2x_6 \\ x_3 = & -3 & + 2x_1 & + 4x_3 & - 3x_6 \\ x_5 = & -4 & + 2x_1 & - 3x_3 & + x_6 \\ z = & 2 & - x_1 & - 3x_3 & - 2x_6 \\ \end{array}\]

We first pick the *exiting* variable, for which we should take one of
the variables with a negative value in the associated solution. We’ll
pick \(x_5\) to exit, because it has the most negative
value^{2}. Now let’s pick the entering variable, keeping in
mind that we want to preserve dual feasibility.

Once we decide on which variable \(x_j\) enters, the \(z\)-row in the next dictionary is obtained as follows: solve the \(x_5\) equation for \(x_j\) and plug that into the equation for \(z\). Another way to get the same effect is to add a multiple of the \(x_5\)-row to the \(z\)-row so that \(x_j\) cancels. If we just use an unknown coefficient \(t\), we can do this calculation even before deciding which variable enters! Namely, the next \(z\)-row will come from the following equation: \[z + t x_5 = (2 - x_1 - 3x_3 - 2x_6) + t(-4 + 2x_1 - 3x_3 + x_6),\] so the next \(z\)-row will be \[z = (2 - 4t) + (-1+2t) x_1 + (-3-3t) x_3 + (-2+t) x_6 -t x_5,\] where we need to choose the value of \(t\) so that all the coefficients are non-positive (to maintain dual feasibility), and so one of the variables \(x_1, x_3, x_6\) disappears from the \(z\)-row —that variable will be the entering variable.

Since by design the coefficient of the exiting variable \(x_5\) is \(-t\), we see that \(t \ge 0\). So then we need to choose the largest non-negative value of \(t\) so that \(-1+2t, -3-3t, -2+t \le 0\). Let’s see how each inequality constrains \(t \ge 0\):

- From \(-1+2t \le 0\), we see \(t \le 1/2\).
- The second inequality, \(-3-3t \le 0\), is true for all \(t \ge 0\) so it does not impose any restriction on \(t\).
- From \(-2+t \le 0\), we see \(t \le 2\).

For all three inequalities to hold we need \(t \le 1/2\) (i.e., that is the strong restriction). So we pick \(t=1/2\) and \(x_1\) will be the entering variable. Now we can perform the pivot. As a small shortcut, to get the new \(z\)-row we can just plug \(t=1/2\) into the equation we obtained for \(z\). The next dictionary works out to be:

\[\begin{array}{rrrrr} x_2 = & 1 & - 4 x_3 & + 3 x_6 & - x_5 \\ x_3 = & 1 & + 7 x_3 & - 4 x_6 & + x_5 \\ x_1 = & 2 & + \frac{3}{2} x_3 & - \frac{1}{2} x_6 & + \frac{1}{2} x_5 \\ z = & 0 & - \frac{9}{2} x_3 & - \frac{5}{2} x_6 & - \frac{1}{2} x_5 \end{array}\]

We got lucky! This new dictionary turns out to be feasible, so we have reached optimality after only one dual pivot. Of course, in general, since we only worried about preserving dual feasibility, the dictionary we get after pivoting will be dual feasible, but not necessarily feasible. If it’s not feasible, we just do more dual pivots.

We only described Dual Phase 2. We won’t need the Dual version of Phase 1 because we will only use the Dual Simplex Method for some cases of sensitivity analysis, which provide us a dual feasible dictionary.

Also, notice that the step in dual pivoting where we pick the entering
variable is very much like the step in the Revised Simplex Method
where we pick the *exiting* variable by finding the maximum \(t \ge
0\) such that \(\mathbf{x}_B^{*} - t \mathbf{d} \ge 0\). There,
\(\mathbf{x}_B^{*}\) was the vector of values of the basic variables,
and \(-\mathbf{d}\) was the vector of coefficients of the entering
variable in the top part of the dictionary. We can make the dual
pivoting step look even more similar to (a transposed version of) this
by writing it in terms of row vectors. In the example above, we were
looking for \(\max \{ t \ge 0 :
\begin{pmatrix} -1 & -3 & -2 \end{pmatrix} + t
\begin{pmatrix} 2 & -3 & 1 \end{pmatrix} \le 0\}\). Both row vectors
are vectors of coefficients of the non-basic variables \(x_1, x_3,
x_6\): \(\begin{pmatrix} -1 & -3 & -2 \end{pmatrix}\) is the vector of
coefficients in the \(z\)-row, and \(\begin{pmatrix} 2 & -3 & 1
\end{pmatrix}\) is the vector of coefficients in the \(x_5\)-row (and
\(x_5\) is the variable selected to exit the basis).

^{1}

More precisely, we’re talking about Phase 2 —and the portion of Phase 1 after the first special pivot to feasibility.

^{2}

This is in analogy with the standard pivoting rule. Recall that for the (usual) Simplex Method we can pick the entering variable to be any of the non-basic variables whose coefficient in the \(z\)-row is positive (all of those choices serve to increase the objective function), but specific pivoting rules tell you exactly which one to pick: the standard rule says to pick one with the largest positive coefficient, while Bland’s rule says to pick among the variables with positive coefficient the one with the smallest index. For the Dual Simplex Method we won’t insist on always following a standard pivoting rule as much as we did for the regular Simplex Method (since we’ll typically use it in cases where only one pivot suffices).