Prove linear program is unbounded

Question

So I need help on my homework (I feel like a 10 year old). The exercise goes like this:

Prove algebraically that the following program is unbounded:

Max:

$x_1 - x_2$

Constraints:

$-2x_1 + x_2 \leq -1$

$-x_1 - 2x_2 \leq -2$

Now geometrically it is easy to see:

But how do I go about it proving it more formally?

Answer 1

I want to put my answer for anyone who comes across this post and wants to use @copper-hat 's suggestion. What I did was to transfer the problem over to terms of $\lambda$ and then prove that $\lambda$ is unbounded which is sort of what MargG did.

So let us choose $x_0 = (2, 0)^T$ for our feasible solution point. Then we can clearly see (from the picture above) that in the direction parallel, to the $x-axis$ the problem is unbounded. Therefore we choose the direction $d_0 = (1,0)^T$ and so we can build a parametric line going to the right parallel to the x-axis. In other words we map the problem to the parametric line for which $\lambda$ should be bounded:

$\Rightarrow (x_1,x_2)^T \mapsto x_0 + \lambda d_0$

$\Rightarrow (x_1,x_2)^T \mapsto (2,0)^T + \lambda (1,0)^T$

Therefore

$x_1 = 2 + \lambda$

$x_2 = 0$

Substituing into our original problem we are left with:

Max:

$2 + \lambda$

Constraints:

$−2(2+\lambda ) \leq −1$

$−(2+\lambda) \leq −2$

After we pass $\lambda$ on one side we get:

$\lambda \geq -3/2$

$\lambda \geq 0$

which of course means the problem is unbounded from above.

Answer 2

One way to see it is to set $x_2=0$. Then the system has a solution for all $x_1 \ge 2$. So $\max x_1-x_2$ is unbounded.