# Solving a linear program with simplex algorithm, matrix not full rank

I need to solve the following LP

$$\begin{array}{ll} \text{minimize} & c^T x\\ \text{subject to} & A x = b\end{array}$$

where

$$A = \begin{bmatrix} 1 & 3 &1&0&0 \\ -2&-2&0&1&0 \\ 2&4&0&0&1 \end{bmatrix}, \qquad b = \begin{bmatrix} 2 \\2\\ 4\end{bmatrix}, \qquad c = \begin{bmatrix} -1\\ -1\end{bmatrix}$$

Matrix $$A$$ 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.

• Please clarify what you mean by "full rank". – Rodrigo de Azevedo Jun 27 '19 at 7:41
• Does the LP require $\boldsymbol x\ge \boldsymbol 0$? Also, the standard form only assumes the rank of $A$ equals to the number of its rows, which is exactly your case. – xskxzr Jun 29 '19 at 8:36