Explain why for an extreme point some inequalities in the constraints become equalities Suppose we have a linear program
$$
\max_x c^Tx\\
\text{subject to } Ax \leq b
$$
where $\leq$ denotes pairwise inequality, i.e. $a^T_i x \leq b_i, i = 1,..., n$.
If $y$ is an extreme point, why is it that $Ay_i = b_i$ for several $i$'s?
 A: Suppose on the contrary that $y$ is an extreme point and we have $$Ay<b.$$
Let $e$ denotes the all one vector.
We can choose a small $\epsilon>0$ such that 
$$A(y+\epsilon e)<b$$
and $$A(y-\epsilon e)<b.$$
We see that $y+\epsilon e$ and $y-\epsilon e$ are both in the polyhedral and we have $$y=0.5(y+\epsilon e)+0.5 (y-\epsilon e)$$ 
which contradicts that $y$ is an extreme point.
A: The set of points $S$ in which the restriction holds forms a convex polytope.
Assume this polytope is finite: since the objective function is linear, the gradient is $\mathbf{c}$, which is a constant vector. 
Now assume that $\mathbf{y}$ is a maximum but it is not in the border of $S$; then we can find a suitable $\epsilon>0$ such that $\mathbf{y}'=\mathbf{y}+ \epsilon \mathbf{c}$ is still inside $S$, but yields a greater value of the objective function (remember $\mathbf{c}$ points in the direction of maximum increase).
Therefore, by contradiction, if $\mathbf{y}$ is a maximum it must lie in the border of $S$. That means at least one restriction will hold with equality (you could have various equalities if the maximum is at a vertex of the convex polytope)
If the polytope is not finite, actually the statement holds unchanged. You just add the possibility of not having a solution to the problem, since if $\mathbf{c}$ points in a direction that, starting from a point $\mathbf{x_0}$ inside $S$,  $\mathbf{x}+ \epsilon \mathbf{c}$ always stays inside $S$ for all $\epsilon>0$, you have no maximum.
