Why are corner points of feasible region candidates in solving linear programming problem? In a linear programming problem, when the goal is to optimize a linear combination of variables with some constraints, it is said that the corners of feasible solution (the Polyhedron determined by constraints) are candidates for optimization problem. More description is here. It seems obvious that one of the corners should be the solution (as simplex algorithm uses this fact). But is there any proof for showing this?

Here are a few pictures that might help. If we are working with a system that has three constraints such that our feasible space is inside this triangle.

Then, if we look at any point on the interior of our space 

We see that we can improve (get a more extreme value of) our function by moving closer to one of the boundaries of our feasible space. For example:

But then we still have another degree (coordinate) of freedom, so we still can't do any worse if we go to one of the extremes in that dimension (along the constraint we are currently on:

Then we land on a corner point and we can't go any farther. This must be the best we can do in this direction. Then we reason, that we only need to check the other corners of our feasible space.
