Good morning, I'm preparing my exam first exam in linear programing and try to sharpen my skills over how to handle such programs.
I want to know when can we know that a linear program isn't feasible and what to do with it.
For instance this one
\begin{cases} \max_xf(x)=&x_1&+x_2\\ &x_1 &+x_2&\ge 2\\ &x_1 &+ x_2&\le 7\\ &3x_2 &-x_1&\le 9\\ &3x_1 &+2x_2&\le 18\\ &x\ge 0 \end{cases}
The vertice of the realisable area are
\begin{array}{lll} A=(2,0) \\ B=(0,2) \\ C=(0,3)\\ D=(3,4)\\ E=(4,3)\\ F=(6,0) \end{array}
The $(0,0)$ starting point seems not to be a feasible vertice. I have to determine one that could. I thus have to solve an auxiliary linear program.
But I don't know how to do it! Consequently I tried to solve it in the matrix form but, if my calculations are right, it lead me to a dead end.
The initial set of basic variables are:
$B=\{e_1,e_2,e_3,e_4\}$
The associated matrix is therefore:
$$A=\begin{pmatrix} -1 & -1 & 1 & 0 & 0 & 0 & -2\\ 1 & 1 & 0 & 1 & 0 & 0 & 7\\ 3 & -1 & 0 & 0 & 1 & 0 & 9\\ 3 & 2 & 0 & 0 & 0 & 1 & 18\\ 1 & 1 & 0 & 0 & 0 & 0 & 0\\ \end{pmatrix}$$
$x_1$ enters the basis $B$ and $e_1$ exits.
We multiply to find the new Simplex matrix:
$$B^{-1}= \begin{pmatrix} -1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0\\ 3 & 0 & 1 & 0 & 0\\ 3 & 0 & 0 &1 & 0\\ 1 & 0 & 0 & 0 & 1\\ \end{pmatrix}$$
\begin{align} AB^{-1}&=\begin{pmatrix} -1 & -1 & 1 & 0 & 0 & 0 & -2\\ 1 & 1 & 0 & 1 & 0 & 0 & 7\\ 3 & -1 & 0 & 0 & 1 & 0 & 9\\ 3 & 2 & 0 & 0 & 0 & 1 & 18\\ 1 & 1 & 0 & 0 & 0 & 0 & 0\\ \end{pmatrix} \begin{pmatrix} -1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0\\ 3 & 0 & 1 & 0 & 0\\ 3 & 0 & 0 &1 & 0\\ 1 & 0 & 0 & 0 & 1\\ \end{pmatrix}\\ &= \begin{pmatrix} 1 & 1 & -1 & 0 & 0 & 0 & 2\\ 0 & 0 & 0 & 1 & 0 & 0 & 5\\ 0 & -4 & 0 & 0 & 1 & 0 & 3\\ 0 & 1 & 0 & 0 & 0 & 1 & -6\\ 0 & 0 & 0 & 0 & 0 & 0 & -2\\ \end{pmatrix} \end{align}
Which is unexpected.
therefore, how to know in the matrix form when a linear program isn't feasible, at least from the original method, and what to do with it? If you have a method I would be very glad!