0

I attend a lecture about linear optimization where we had the following two Theorems. But I somehow cannot spot the difference:

Theorem 1:

Let $P$ be a polyhedron with an extreme Point and $c \in \mathbb{R}^n$ an objective function. Suppose that $\max_{x \in P} c^T x$ is finite. Then there exists an extreme point solution (thus an extreme point in $P$ that attains the maximum).

Theorem 2:

Let $P$ be a non-empty polyhedron not containing a line. Then for every $c \in \mathbb{R}^n$, either $\max_{x \in P} c^T x = \infty$ or there exists an extreme point solution.

We already proved that having no line is equivalent to having an extreme Point. So somehow, it seems to me that Theorem 2 directly follows from Theorem 1, as either the value is unbounded or otherwise directly Theorem 1 applies which gives the result.

But we had a very nasty proof of Theorem 2, so I am a little bit confused. Mainly, we proved in the proof of Theorem 2 that for every $x \in P$ there exists an extreme point $x^* \in P$ such that $c^Tx^* \geq c^Tx$, for any $c$. Why do we Need that?

user146358
  • 309
  • What exactly do you mean by a polyhedron containing a line? What is $c^T$? – Marc Bogaerts Oct 15 '14 at 14:38
  • With polyhedron I mean a finite number of intersections of halfspaces, thus ${ x \in \mathbb{R}_n \mid Ax \leq b}$, and a polyhedron $P$ constains a line iff there exists a point $x \in P$ and a direction $d \in \mathbb{R}^n, d \neq 0$, such that $x + \lambda d \in P $ for all $ \lambda \in \mathbb{R}$.

    $c$ is the linear objective function in the linear optimization problem, given as a vector. $c^T x$ denotes the scalar product of the vector $c$ with the vector $x$. $c^T$ is the transposed vector of $c$.

     – user146358 Oct 20 '14 at 05:47

0 Answers0