How to check if a primal optimisation problem is feasible and bounded?

Question

Consider the following Primal LP

$$ \min_{x_1,x_2,x_3} x_1+x_2+x_3 $$ subject to constraints, $$ x_1+x_2 \ge a \\ x_1+x_3 \ge b \\ x_2+x_3 \ge c\\ x_1 \ge d \\ x_2 \ge e \\ x_3 \ge f $$

Here $$a,b,c,d,e,f \quad \text{are constants} $$ There is no restrcition on variables $x_1$, $x_2$, $x_3$ (free variables). How do I establish that this primal problem is feasible and bounded? Could someone please help?

Also, in general, how does one establish an optimisation problem is feasible and bounded?

Answer 1

For your particular problem,

We have $x_1+x_2+x_3 \ge a + f$. Hence it must be bounded and can't to go $-\infty$.

To construct a feasible solution, we just need the variables to be large enough to be feasible. $(|a|+|b|+|d|, |a|+|c|+|e|, |b|+|c|+|f|)$ is a feasible solution.

For general linear programming problem, we know how to solve it, we can convert it to a standard form and use simplex algorithm.

Theoretically, for linear programming problem, we can also use duality theorem and shows that the primal and dual share the same objective value.

Answer 2

Add the first 3 inequalities, then add the last 3 ones : you get

$$x_1+x_2+x_3 \ge M \ \ \ \ \text{with} \ \ \ \ M:=\max((a+b+c)/2,d+e+f)$$

Therefore, taking all $x_k$ equal to $M$ gives a feasible solution to the primal problem.

Answer 3

Can check if LP is bounded by seeing if primal has a feasible solution and dual has a feasible solution, then primal is bounded.