$\max 2x_1 +x_2$ unbounded or unfeasible with the constraint $sx_1 +tx_2\le-1$

Question

\begin{cases} \max & 2x_1 &{}+x_2\\ & sx_1 &{}+tx_2&\le-1\\ & x_1,x_2&&\ge 0 \end{cases}

Find out when this program is not feasible, bounded

Feasibility

It is not feasible when $s\ge0$ and $t\le0$

Because

• $\Rightarrow $if $s<0$ then $\forall M\ge \frac{-1}{s}: x_1=M,x_2=0$ is feasible.

• $\Leftarrow $if $t>0$ then $\forall M\ge \frac{1}{t}: x_1=M,x_2=0$ is feasible.

  I think the second line of the demonstration is inaccurate. Why should the teacher used a $\Leftarrow$? This is not demonstrating the reverse, isn't it?

Unbounded

The program is unbounded if $s<0$ or $t>0$

$\Rightarrow$

• if $s<0$ then $\forall M\ge \frac{-1}{s}, x_1=M, x_2 =0$ is feasible
• if $t>0$ then $\forall M\ge \frac{1}{t}, x_1=M, x_2 =0$ is feasible

I don't know why the teacher wrote that, indeed we aren't looking for feasibility.

$\Leftarrow$

$2x_1+x_2\le \mu(sx_1-tx_2)\le-\mu$

$\exists \mu >0$, if

• $\mu\times s\ge 2$
• $-\mu\times t \ge 1$

Therfore the program is bounded for $\mu =\max\{\frac{2}{s};\frac{-1}{t}\}$

I don't understand this part of the demonstration, where does $2x_1+x_2\le \mu(sx_1-tx_2)\le-\mu$ comes from?

Optimal?

According to my teacher, it has an optimal solution when ($s<0$ or $t>0$) and ($s\ge0$ and $t\le0$), I understand it as when it is unbounded and not feasible, which I found rather strange. Shouldn't a program with an optimal solution be bounded and feasible?

Nevertheless I understand that given the fact that it is bounded when we don't have ($s<0$ or $t>0$) and feasible when we don't have ($s\ge0$ and $t\le0$), it should never have solution.

Can you help me provide a readable solution?

Answer 1

After two weeks, I tried again to solve this problem:

First part of the bounded demonstration

if:

$$(s<0 \mbox{ or } t>0)$$

• if $s<0$ then $\forall M \le \frac{-1}{s}, x_1=M$ is feasible. Yet, $x_1\ge 0$, does it creates a problem?
• if $t>0 \forall M\ge \frac{1}{t},x_2=M$ is feasible.

Second part of the bounded demonstration

The problem is bounded if $2x_1+x_2\le \mu(sx_1-tx_2)\le-\mu$

$\exists \mu >0$, if

• $\mu\times s\ge 2$
• $-\mu\times t \ge 1$

Therfore the program is bounded for $\mu =\max\{\frac{2}{s};\frac{-1}{t}\}$

Answer 2

I've no idea what's going on for the feasibility part. If it is feasible, then either $s$ or $t$ must be negative, otherwise $s x_1 + t x_2 \ge 0$. Conversely, if either $s$ or $t$ is negative, then it is feasible because you just need to make $x_1$ or $x_2$ (depending on which of $s,t$ is negative) sufficiently large and it would make $s x_1 + t x_2 \le -1$.

So the given criterion for feasibility is simply wrong. I suspect there is something wrong with the question and there is little point solving the other parts right now.