# How to solve a system of linear inequalities?

I am working on the following exercise:

Find a solution to the following system or prove that none exists:

\begin{align} x_1-x_2 &\le 4\\ x_1-x_5 &\le 2\\ x_2-x_4 &\le -6 \\ x_3-x_2 &\le 1 \\ x_4-x_1 &\le 3 \\ x_4-x_3 &\le 5\\ x_4-x_5 &\le 10 \\ x_4-x_3 &\le -4 \\ x_5-x_4 &\le -8 \end{align}

I do not know how to do that. Is there some algorithm? I can not find anything online. Could you help me?

• you might want to google "linear programming" – Francisco José Letterio Nov 26 '19 at 21:34

Suppose a solution exists. Then add up the third, fourth, and eighth constraints $$(x_2 - x_4) + (x_3 - x_2) + (x_4 - x_3) \le -6+1-4 \\$$ to obtain the contradiction $$0 \le -9$$.
You can add $$x_i - x_j \le a$$ and $$x_j - x_k \le b$$ to get $$x_i - x_k \le a+b$$ and if you have $$x_i - x_k$$ anywhere....
So $$x_1 - x_2 + x_2 - x_4=x_1-x_4 \le 4+(-6) = -2$$. And $$x_4 -x_1 \le 3$$ so $$-3 \le x_1 - x_4 \le -2$$.
And $$x_1 -x_5 + x_5 -x_4 = x_1 - x_4 \le 2+(-8) = -6$$. Which contradicts the above.
From the first inequality you have $$x_1 \leq 4+x_2.$$ Now from the second $$4+x_2-x_5 \leq 2$$ or $$x_2-x_5 \leq -2$$ or $$x_2 \leq -2+x_5.$$ Now from the third you get $$-2+x_5-x_4\leq -6$$ or $$x_5\leq -4+x_4.$$ This can be applied to the last inequality and you get $$-4+x_4-x_4\leq -8$$ and that gives $$-4 \leq -8.$$ So the system has no solution.