I have that matrix named A:
\begin{bmatrix} 1 & 3 &1&0&0 \\ -2&-2&0&1&0 \\ 2&4&0&0&1 \end{bmatrix}
I need to solve the LP : $$ \min: -x_1 - x_2$$ and $$Ax = ( 2,2,4)^T$$
This matrix is not full rank. Then the only way to solve that problem is to create an equivalent problem with a full rank matrix ? Here for instance :
$$ \min \{ (c,-c) (x^+,x^-)^T : \begin{bmatrix} A & -A \\ -I& 0 \\ 0& -I \end{bmatrix} (x^+,x^-)^T \leq (b, 0,0)^T \} $$
but I don't know how to solve a problem with $x^+$ and $x^-$. Would you have an example ?
So my question is how to solve such a problem, and if you'd recommand my method, how do you use it, especially concerning the $x^+$ part.
I've asked that question on computer sciences also, but i was unsure if it is a computer science or math question. (cf https://cs.stackexchange.com/questions/111189/solving-a-linear-program-with-simplex-algorithm-matrix-not-full-rank)
Sure, you can do the simplex algorithm on it. After splitting your variables into their non-positive and non-negative parts, you get the following simplex tableau: \begin{array}{cccccccccc|c} \fbox{1} & 3 &1&0&0&-1&-3&-1&0&0&2\\ -2&-2&0&1&0&2&2&0&-1&0&2\\ 2&4&0&0&1&-2&-4&0&0&-1&4\\ \hline -1&-1&0&0&0&1&1&0&0&0&0 \end{array} This is in feasible canonical form with basic variables $\ x_3^+,x_4^+\ $ and $\ x_5^+\ $, so you're right about that. However, since there are negative entries in the objective row, you know the basic solution is not optimal. To proceed with the simplex algorithm You can choose to pivot on either first or second columns, and an appropriate row. If you choose the first row and first column, the new tableau is: \begin{array}{cccccccccc|c} 1 & 3 &1&0&0&-1&-3&-1&0&0&2\\ 0&4&2&1&0&0&-4&-2&-1&0&6\\ 0&-2&-2&0&1&0&\fbox{2}&2&0&-1&0\\ \hline 0&2&1&0&0&0&-2&-1&0&0&2 \end{array} Now pivoting on the third row and seventh column gives the following tableau: \begin{array}{cccccccccc|c} 1 & 0 &-2&0&\frac{3}{2}&-1&0&2&0&-\frac{3}{2}&2\\ 0&0&-2&1&2&0&0&2&-1&-2&6\\ 0&-1&-1&0&\frac{1}{2}&0&1&1&0&-\frac{1}{2}&0\\ \hline 0&0&-1&0&1&0&0&1&0&-1&2 \end{array} Since all the entries in the tenth column in this tableau are negative, this tells you that there are feasible solutions which can make the objective arbitrarily small. Indeed if you take $\ x_5^-\ $ to be the only non-basic variable with a non-zero value, the tableau tells you that the following values for the basic variables \begin{eqnarray} x_1^+&=& 2+\frac{3x_5^-}{2}\\ x_4^+&=& 6+2x_5^-\\ x_2^-&=&\frac{x_5^-}{2} \end{eqnarray} will give you a feasible solution for any value of $\ x_5^-\ $. But the objective has value $\ -x_1^+ + x_2^- = -2-x_5^- \ $, which can be made arbitrarily small by choosing $\ x_5^-\ $ sufficiently large.
In terms of the original variables, what this says is that $\ x_1=2-\frac{3x_5}{2}\ $, $\ x_2=\frac{x_5}{2}\ $, $\ x_3=0\ $, and $\ x_4=6-2x_5\ $ is a feasible solution for any value of $\ x_5\ $, which can easily be checked by substituting these values into the equation $$ \begin{bmatrix} 1& 3 &1&0&0\\ -2&-2&0&1&0\\ 2&4&0&0&1 \end{bmatrix}\begin{bmatrix}x_1\\ x_2\\ x_3\\ x_4\\ x_5\end{bmatrix}=\begin{bmatrix}2\\2\\4\end{bmatrix}\ ,$$ and the objective $-x_1-x_2 = -2 + x_5\ $ can be made arbitrarily small by choosing $\ x_5\ $ sufficiently small.
Explanation of edit: The discussion below—in particular the fact that shadow prices should be non-negative—alerted me to the fact that I had originally used the reverse of the usual convention for the signs of the entries in the objective row. While this did not affect the correctness of the solution, it could nevertheless have been confusing to anyone not fully aware of what equations are represented by the tableau. I have therefore now reversed all the signs of that row, and of the conditions required for optimality, so that the procedure now follows the more standard convention.