0
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ you might want to google "linear programming" $\endgroup$ – Francisco José Letterio Nov 26 at 21:34
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

Oh, just hit it with a hammer until it stops bleeding.

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.