Linear programming solution in vertex I want to prove that if linear programming problem
$$\max \{\langle c,x\rangle \ \colon Ax\leqslant b, \ x\geqslant 0\}$$
has a solution, then atleast one of the solutions is in the vertex of 
$$\Omega=\{x\  \colon Ax\leqslant b, \ x\geqslant 0\}.$$
Any ideas on how to approach this problem?
 A: This is actually the main theorem of LP theory:
Given a problem in standard form
\begin{align}
\max\ &c^{\top}x\\
&Ax=b\\
&x\geq 0
\end{align}
let $\Omega =\{x\in \mathbb{R}^n\ |\ Ax=b,\ x \geq 0\}$ be the feasible set. Assume that $rank(k)=m$. Then


*

*If $\Omega \neq \emptyset$ then there exists at least a basic feasible solution to the problem (i.e. $\Omega$ has at least a vertex).

*If the problem is not unbounded then there exists an optimal basic solution. 
Proof of statement 1
Let $x$ be a feasible solution. WLOG assume that $x_1, x_2,\ldots, x_p > 0$ and $x_{p+1},\ldots, x_n =0$. If $A_1,\ldots,A_p$ are linearly independent columns of $A$ then $x$ is a basic feasible solution. Otherwise $A_1,\ldots,A_p$ are linearly dependent and $$\sum_{i=1}^p\lambda_iA_i=0$$
holds with at least one coefficient $\lambda_i \neq 0$. Observe that the equation system can be written as
 $$\sum_{i=1}^px_iA_i=b$$
Multiplying the first equation by $\epsilon \in \mathbb{R}$ and subtracting it from the last one we get
$$\sum_{i=1}^px_iA_i - \epsilon\sum_{i=1}^p\lambda_iA_i=\sum_{i=1}^p(x_i - \epsilon\lambda_i)A_i=b$$
Therefore the vector
$$x-\epsilon \lambda=[x_1-\epsilon \lambda_1,\ldots,x_p-\epsilon\lambda_p,0,\ldots,0]^{\top}$$
will be feasible if
$$x_i-\epsilon\lambda_i \geq 0 \ \ \  i=1,\ldots,p$$
The solution of this system of inequalities is $\epsilon=\min \{\epsilon_1, \epsilon_2\}$ where
$$\epsilon_1 = \max_{1\leq i\leq p}\Big\{\dfrac{x_i}{\lambda_i}\ |\ \lambda_i < 0\Big\}$$
and
$$\epsilon_2 = \min_{1\leq i\leq p}\Big\{\dfrac{x_i}{\lambda_i}\ |\ \lambda_i > 0\Big\}$$
Taking $\epsilon=\epsilon_1$ or $\epsilon=\epsilon_2$ the vector $\bar{x}=x-\epsilon \lambda$ has at least one more null component. Now check if the columns of $A$ related to the non null components of $\bar{x}$ are linearly independent. If they are linearly independent $\bar{x}$ is a basic feasible solution; otherwise repeat the whole procedure starting from $\bar{x}$.
Proof of statement 2
Let $x$ an optimal solution. If it is a basic feasible solution then we get the proof. If it is not basic, as in the statement 1, we can always construct a new vector $\bar{x}=x-\epsilon \lambda$ which is basic.
The objective function value at $\bar{x}$ is
$$c^{\top}\bar{x}=c^{\top}x-\epsilon c^{\top}\lambda$$
All we need to show for $\bar{x}$ to be optimal is that $c^{\top}\lambda=0$. Observe that


*

*if $c^{\top}\lambda>0$, taking $\epsilon=\epsilon_1<0$ we get
$$c^{\top}\bar{x} > c^{\top}x $$

*if $c^{\top}\lambda<0$
taking $\epsilon=\epsilon_2>0$ we get
$$c^{\top}\bar{x} > c^{\top}x $$
In both cases we get a contradiction. Therefore it is $c^{\top}\lambda=0$, $c^{\top}\bar{x} = c^{\top}x $  and $\bar{x}$ is an optimal basic solution.
QED
REMARKS


*

*The theorem refers to problems with equality constraints (standard form problems). As you well know every LP problem can be transformed in standard form, so the theorem applies to all LP problems.

*The feasible sets of a generic LP problem and the corresponding standard form problem have the same shape, although they lie in different spaces. Thus there is a one-to-one correspondence between the vertexes of the two feasible sets.

*The theorem uses the concept of basic solution, but a well-known theorem states that $x$ is a vertex of $\Omega$ if and only if $x$ is a basic feasible solution of the system $Ax=b$.
A: Let $x^* \in \mathbb{R}^n$ denote an optimal solution. By Carathéodory's theorem, $x^*$ is the convex combination of at most $n+1$ vertices:
$$x^* = \sum_{i=1}^{n+1} \lambda_i x^i,$$
with $\sum_{i=1}^{n+1} \lambda_i = 1$ and $\lambda_i \geq 0$. When all objective values at the vertices ($c^T x^i$) are strictly smaller than $c^Tx^*$ we arrive at a contradiction:
$$c^Tx^* = \sum_{i=1}^{n+1} \lambda_i c^T x^i < \sum_{i=1}^{n+1} \lambda_i c^T x^* = c^T x^* \sum_{i=1}^{n+1} \lambda_i = c^T x^*.$$
I "cheated" a little bit by assuming that the feasible region is bounded. However, if an optimal solution exists, you can always box constraints to make the feasible set bounded without affecting this proof.
A: This is a consequence of the Extreme Value Theorem. 
I think the best way to understand it is by looking at what happens in the $1$-dimensional case (obviously this is not a proof, but it gives you the intuition as to why it holds). 
An example, assume you are dealing with 
$$
\max\limits_{x \in \mathbb{R}}\{2x\; |\; x\le 2,\; x \ge 0 \}
$$
So here, $\Omega = [0,2]$. Since $y=2x$ is linear, it is clear from a quick drawing that the maximum is in $x=2$, a vertex of $\Omega$.
Try doing the same thing in $2$-D to convince yourself a little more.
