The Dual Simplex Method

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.

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.

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². 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).