I have been given the following LP problem and asked to use the two phase simplex method to solve it.
I believe there isn't a solution, but would anyone be able to confirm this for me? Thanks.
max
$ -x_1 + 2x_2 -3x_3 – x_4 $
s.t.
$ 2x_1 – x_2 – 3x_3 + 4x_4 = -2$
$ 2x_1 + 3x_2 + 4x_3 – x_4 = 1 $
$ x_1,x_2,x_3,x_4 ≥ 0 $
Thanks.
Best Answer
The feasible set is empty.
A rather clumsy way of showing this is as follows:
Write the equality constraints as $A \pmatrix{x_1 \\ x_2} - B \pmatrix{x_3 \\ x_4} =\pmatrix{-2 \\ 1} $, where $A=\pmatrix{ 2 & -1 \\ 2 & 3}$, $B=\pmatrix{3 & -4 \\ -4 & 1}$. Since $A^{-1} = \frac{1}{8}\pmatrix{ 3 & 1 \\ -2 &2}$, we can write the equality constraints as $\pmatrix{x_1 \\ x_2} = A^{-1}(B \pmatrix{x_3 \\ x_4} + \pmatrix{-2 \\ 1}) =\frac{1}{8}(\pmatrix{ 5 & -11 \\ -14 & 10} \pmatrix{x_3 \\ x_4} +\pmatrix{-5 \\ 6} )$.
Consequently, the feasible set can be described by the constraints $$x_3 \geq 0 \\ x_4 \geq 0 \\ x_1 =5 x_3-11 x_4 -5 \geq 0 \\ x_2 = -14 x_3 + 10 x_4 +6 \geq 0$$ Consider the equation $14 x_1+5 x_2$ (which must be non-negative), this gives $-104 x_4 -40 \geq 0$, which is impossible.