Show that either $(x_1,\dots,x_n) = (0,\dots,0)$ is the optimal solution or the LP is unbounded.

$$\begin{array}{llclccclcl} \text{maximize} & c_1x_1 & + & c_2x_2 & + & \dots & + & c_nx_n \\\text{subject to} & a_{11}x_1 & + & a_{12}x_2 & + & \dots & + & a_{1n}x_n & \le & 0\\ & a_{21}x_1 & + & a_{22}x_2 & + & \dots & + & a_{2n}x_n & \le & 0\\ & & \vdots & & \vdots & & \vdots & & \vdots & \\ & a_{m1}x_1 & + & a_{m2}x_2 & + & \dots & + & a_{mn}x_n & \le & 0\\ & & & & & x_1, & \dots, & x_n & \ge & 0 \\ \end{array}$$

Show that either $$(x_1,\dots,x_n) = (0,\dots,0)$$ is the optimal solution or the LP is unbounded.

• In all the constraints (except the last one), the coefficients $a_{ij} \leq 0$. If $a_{ij} = 0 \forall \ I, j$ then the LP is unbounded. Commented Feb 3, 2021 at 4:30
• @P.J. the coefficients do not need to be negative for the statement to hold Commented Feb 3, 2021 at 16:47
• @LinAlg I was trying to explain the case for $a_{ij} = 0$, certainly not the negative case Commented Feb 4, 2021 at 6:02
• could you mark the question as answered? Commented Feb 23, 2021 at 15:07

If $$x=0$$ is not optimal, that means that there is an $$x \geq 0$$ for which $$c^Tx > 0$$ and $$Ax \leq 0$$. Then $$\alpha x$$ ($$\alpha \geq 0$$) is also feasible, and by $$\alpha \to \infty$$ the objective can be made arbitrarily large.