0

I am working on the following exercise:

Consider the LP

$max \ c \cdot x$ with $Ax \le 0$ and $x \ge 0$

Show that either $x=0$ is an optimal solution or the LP is unbounded.

My idea for a proof goes as follows:

We assume that $0$ is not an optimal solution. Now for the sake of contradiction we suppose that $\overline{x}$ is an optimal solution. Now we need to show that we can find a feasible $y$ sucht that $c \cdot y \ge c \cdot x$, but I do not see how to do this. Could you help me?

Community
  • 1
3nondatur
  • 4,178
  • 1
    The feasible region defined by $Ax\leq0$ and $x\geq0$ is a pointed, polyhedral cone. For any LP, if the LP has an optimal solution, then it has an optimal solution which occurs at a vertex. The only vertex of a pointed polyhedral cone is $x=0$. – David M. Apr 03 '19 at 03:06
  • 1
    You can also approach this problem using duality theory. – Brian Borchers Apr 03 '19 at 04:07

1 Answers1

1

Clearly $x=0$ is a solution. Assume that the maximum is finite, then it must be greater than $0$. Assume $\overline{x}$ is the optimal solution. Then for all $\lambda > 0$, $\lambda \overline{x}$ is also a solution but then $c\overline{x} \geq \lambda c\overline{x}$, but this can only be true if $c\overline{x} = 0$. Hence, $x=0$ is an optimal solution.

user605486
  • 1,062