A condition for an LP to be unbounded

Question

Let $(P)$ be an LP of the form

$$min \ c^tx \text{ with } Ax \le b,x \ge 0.$$

Show that if there is a vector $d$ such that $Ad=0,d \ge 0$ and $c^td<0$ $(P)$ is unbounded .

Could you help me?

Answer 1

The stated condition doesn't prove that there is a feasible solution to the original problem.

If there is a feasible solution to the original problem, call it $x^*$, then for any $m > 0$, $x^* + md$ is feasible for the original problem, and has objective value $c^tx^* + mc^td$. Because $mc^td < 0$, as $m$ goes to $\infty$, the objective value goes to $-\infty$. Hence the original problem is unbounded.