# What variable to choose with the dual algorithm of the Simplex for a $\max$ problem with negative variables

I have to solve the following linear program using the dual algorithm of the Simplex (the version with array): \begin{cases} \begin{aligned} \min z = \ & 2x_1&&+ x_3\\ &x_1&+x_2&-x_3&\geq 5\\ &x_1&-2x_2&+4x_3&\geq 8\\ \forall i, x_i \end{aligned} \end{cases}

After adding slack variables and transforming it into a $\max$ problem, it gives me:

\begin{cases} \begin{aligned} \max z = \ & -2x_1&& -x_3\\ &-x_1&-x_2&+x_3&+x_4&&= -5\\ &-x_1&+2x_2&-4x_3&&+x_5&= -8\\ \forall i, x_i \end{aligned} \end{cases}

\begin{array}{| l | l | l | l | l | l | l |} \hline & x_1 & x_2 & x_3 & x_4 & x_5 & b \\ \hline x_4 & -1 & -1 & 1 & 1 & 0 & -5\\ x_5 & -1 & 2 & -4 & 0 & 1 & -8 \\ \hline z & -2 & 0 & -1 & 0 & 0 & 0\\ \hline \end{array}

I don't know wether $x_1$ enters or $x_3$:

• as far as we are trying to $\max$, shouldn't we take the greter variable?
• Still, all variables are $<0$, and I'm not used to go further with such negative variables.

Or should I transform the array to turn it into a more classical view?

\begin{cases} \begin{aligned} \max z = \ & -2x_1&& -x_3\\ &x_1&+x_2&-x_3&+x_4&&= 5\\ &x_1&-2x_2&+4x_3&&-x_5&= 8\\ \forall i, x_i \end{aligned} \end{cases}

Or should I develop it's dual?

• In the primal simplex you always have basis that are primal-feasible ($b\geq 0$) but dual-unfeasible ($c_N^{\top} \geq 0$). Vice-versa in the dual simplex you work with primal-unfeasible but dual-feasible basis. So you have to repair the primal unfeasible solution but maintaining the dual feasibility. This means that first you have to choose the leaving variable (the row) and on that row the entering variable (the column). Commented Nov 10, 2016 at 1:05
• @MarcelloSammarra Therefore - do I have to take the $i$-th row variable such that $\min_i b_i$ or $\max_i b_i$? And as far as it is a $\max$ problem, should I take $\max$ coefficient on the column's $z$ variables? - Or should I turn it into a more classical way by multiplying my rows by $-1$? \begin{cases} \begin{aligned} \max z = \ & -2x_1&& -x_3\\ &x_1&+x_2&-x_3&+x_4&&= 5\\ &x_1&-2x_2&+4x_3&&-x_5&= 8\\ \forall i, x_i \end{aligned} \end{cases} Commented Nov 10, 2016 at 8:30
• @MarcelloSammarra The problem is that I'm not used to max when I have negative coefficient in the Simplex array... I used to stop when they become positive. Commented Nov 10, 2016 at 9:06
• your starting tableau is infeasible (e.g., $x_4 = -5 < 0$). You should start with two-phase simplex or the big-M method. Commented Nov 10, 2016 at 15:35

I try to elaborate a bit my first comment.

Let us consider an LP problem in minimum standard form with $n$ variables and $m$ constraints \begin{align} \min \ \ & c^{\top}x\\ &Ax=b\\ &x\geq 0 \end{align}

where $b\geq 0$. The corresponding dual is

\begin{align} \max \ & b^{\top}y\\ & A^{\top}y\leq c \end{align} Let $B$ a feasible basis of $A$, then the tableau of the primal problem with respect to the basis $B$ can be written as

\begin{align} \begin{array}{|c|cc|c|} \hline x_B & I & B^{-1}N & B^{-1}b\\ \hline z & 0^{\top}_m & \hat{c}^{\top}_N & -c_{B}^{\top}B^{-1}b\\ \hline \end{array} \end{align}

where $\hat{c}^{\top}=[\hat{c}_B^{\top},\hat{c}^{\top}_N]=[0_m^{\top},c_N^{\top}-c_B^{\top}B^{-1}N]$ are the reduced costs.

This form of the tableau directly comes by solving the equation system for $x_B$ e substituting $x_B$ in the objective function $$z=c^{\top}x=c^{\top}_Bx_B+c^{\top}_Nx_N=c^{\top}_B(B^{-1}b-B^{-1}Nx_N)+c^{\top}_Nx_N=c^{\top}_BB^{-1}b+(c^{\top}_N-c^{\top}_BB^{-1}N)x_N$$

Note that by taking for the dual vector $y^{\top}=c_B^{\top}B^{-1}$ we have:

1. $\hat{c}$ are the slacks of the dual constraints;
2. $x$ and $y$ satisfy the complementary slackness conditions, that is $$x_j\hat{c_j}=0 \ \ \ \forall j = 1,\ldots, n$$

Therefore when you work with the primal Simplex, you actually work with explicit primal feasible basic solutions ($x_B \geq 0$) and with implicit dual solutions, which possibly are unfeasible ($\hat{c} \leq 0$). Note that you do not calculate the vector $y$, but you just check if this vector is feasible looking at the reduced cost vector. At each iteration the primal simplex maintains the primal feasibility and try to reach the dual feasibility, that is a primal basis that yields $\hat{c}_N \geq 0$. When this basis is found you have two feasible vectors that satisfy the complementary slackness conditions and are, therefore, both optimal.

Sometimes, as in your example, it is difficult to have a feasible basis. In these cases you can use the Two Phases Simplex Algorithm, as suggested by LinAlg.

Alternatively you can work with a basis that is primal-unfeasible ($x_B \leq 0$) but dual-feasible ($\hat{c} \geq 0$). As before, the corresponding primal and dual vectors also in this case satisfy the complementary slackness conditions, and the pivoting operations are aimed at reaching the primal feasibility, maintaining the dual feasibility. This is the Dual Simplex Algorithm.

It first chooses a row $h$ whose basic variable is negative (this variable will leave the current base) and then a column $k$ (that is the entering variable) so that in the new basis it is still $\hat{c} \geq 0$.

The entering variable is selected by an analogous "primal ratio-test" $$k = arg\min_{1 \leq j\leq n} \big\{\dfrac{\hat{c}_j}{|\bar{a}_{hj}|}\ | \ \ \bar{a}_{hj}<0 \big\}$$

If such $k$ does not exist, because on the row $h$ it is $\bar{a}_{hj} \geq 0\ \ \ \forall j$, then the problem is unfeasible.

This stated, if you put you problem in standard form, maintaining the objective function in minimum form, the Dual Simplex can be applied. The iterations are as follows:

\begin{align} \begin{array}{|c|ccccc|c|} \hline x_4 & -1 & -1& 1& 1& 0&-5\\ x_5 & -1 & 2& -4& 0& 1&-8\\ \hline z & 2 & 0 & 1& 0&0&0\\ \hline \end{array} \end{align} A the first iteration we can choose $x_4$ as the leaving variable ($h=1$); this enforces $x_2$ to enter the basis. By pivoting on $\bar{a}_{12}=-1$ we get: \begin{align} \begin{array}{|c|ccccc|c|} \hline x_2 & 1 & 1& -1& -1& 0& 5\\ x_5 & -3 & 0& -2& 2& 1&-18\\ \hline z & 2 & 0 & 1& 0&0&0\\ \hline \end{array} \end{align} At the second iteration $x_5$ leaves the basis and $x_3$ is the entering variable; $\bar{a}_{23}=-2$ is the pivot. \begin{align} \begin{array}{|c|ccccc|c|} \hline x_2 & -\frac{5}{2} & 1& 0& -2& -\frac{1}{2} & 14\\ x_3 & \frac{3}{2} & 0& 1 &-1& -\frac{1}{2} &9\\ \hline z & \frac{1}{2} & 0 & 0& 1& \frac{1}{2} &-9\\ \hline \end{array} \end{align} The last table represents the optimal solution, as you have both primal and dual feasibility. This is how the tableau and the dual simplex algorithm is presented in Bertsimas and Tsitsiklis Introduction to linear optimization.

On the other hand in Bazaraa, Jarvis and Sherali Linear Programming and Network Flows, there is a little difference. They start from a minimum standard form problem, but when they substitute in the objective function the expression of $x_B$, they get $$z=c^{\top}x=c^{\top}_Bx_B+c^{\top}_Nx_N=c^{\top}_B(B^{-1}b-B^{-1}Nx_N)+c^{\top}_Nx_N=c^{\top}_BB^{-1}b-(c^{\top}_BB^{-1}N-c^{\top}_N)x_N$$ This means that, with respect to Bertsimas, in their tableau the last row is multiplied by $-1$, and then also the optimality conditions have to be reversed: in the Bazaraa development of the simplex algorithm a solution is optimal if $\hat{c}_N^{\top}=[c^{\top}_BB^{-1}N-c^{\top}_N] \leq 0$ and therefore a profitable non-basic variable is the one with a positive reduced cost. Note that now in the right-bottom element of the tableau there is $c_B^{\top}B^{-1}b$.

As far as it concerns the dual simplex algorithm, the only change is in the definition of the ratio-rule $$k = arg\min_{1\leq j\leq n} \big\{\dfrac{\hat{c}_j}{\bar{a}_{hj}}\ | \ \ \bar{a}_{hj}<0 \big \}$$

The starting table is \begin{align} \begin{array}{|c|ccccc|c|} \hline x_4 & -1 & -1& 1& 1& 0&-5\\ x_5 & -1 & 2& -4& 0& 1&-8\\ \hline z & -2 & 0 & -1& 0&0&0\\ \hline \end{array} \end{align} and we can perform the same sequence of pivot operations.

The first pivot is on $\bar{a}_{12}$

\begin{align} \begin{array}{|c|ccccc|c|} \hline x_2 & 1 & 1& -1& -1& 0& 5\\ x_5 & -3 & 0& -2& 2& 1&-18\\ \hline z & -2 & 0 & -1& 0&0&0\\ \hline \end{array} \end{align}

In the second iteration $x_5$ leaves the basis and $x_3$ enters

\begin{align} \begin{array}{|c|ccccc|c|} \hline x_2 & -\frac{5}{2} & 1& 0& -2& -\frac{1}{2} & 14\\ x_3 & \frac{3}{2} & 0& 1 &-1& -\frac{1}{2} &9\\ \hline z & -\frac{1}{2} & 0 & 0& 1&-\frac{1}{2} &9\\ \hline \end{array} \end{align}

The last table represents the optimal solution, on the basis of Bazaraa's statements.

I personally prefer the Bertsimas outline for two reasons:

1. In the reduced objective function it is clearly evident that if there is a negative reduced cost the current basis is not optimal, because by increasing the corresponding non basic variable the solution decreases;

2. There is a clear correspondence between the reduced costs and the dual slack variables. If the reduced costs are nonnegative with respect to the basis $B$, the slack variables are nonnegative too, denoting that the dual vector $y^{\top}=c_B^{\top}B^{-1}$ is feasible (slack variables are feasibility flags).