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?
 A: 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:


*

*$\hat{c}$ are the slacks of the dual constraints;

*$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:


*

*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;

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