Why interior point of feasible region of linear programming problem can't be optimal solution?

Question

Solution set will be null or singular or infinite. Optimal solution set if not null has at least one extreme point. I have feeling that optimal solution will be on boundary only but don't know how to show it mathematically that interior point can't be optimal solution.

Answer 1

Consider the linear programming problem

$$\min_{x \in F} c^Tx$$

where $F$ is a polyhedral.

If $c=0$, then every point, including any interior point is indeed an optimal solution.

However, if $c \neq 0$, by definition of an interior point, $y$, we can find a small neighborhood $N$ around $y$ such that $N \subset F$. we consider the point $y-\epsilon c$ where $\epsilon>0$ is chosen to be small enough such that $y-\epsilon c \in N$. hence $y-\epsilon c$ is feasible and we have $$c^T(y-\epsilon c^T)=c^Ty-\epsilon c^Tc=c^Ty-\epsilon\|c\|^2 < c^Ty,$$ hence the interior point $y$ is not optimal.