will the feasible region of a linear programming problem with linear mathematical relations and linear constraints, always be a convex polygon?
will concave feasible regions have optimal value at corner points?
[Math] feasible region of a linear programming problem convex and concave
linear programming
Related Solutions
Suppose your feasible region looks as shown below :
Lets assume we're maximizing the objective function $C=ax+by$
Notice that, for different values of C, you get different straight lines of varying y intercepts but they will have same slope :
Only the lines that cut through the feasible region satisfy all the given constraints because you can cookup x,y values such that they fall in both feasible region and the objective function.
From the second picture it is obvious that the the maximum value of $ax+by=C$ occurs when the y intercept of these feasible lines is maximum. Consequently the vertex A gives the maximum value for the objective function.
The function you optimise is linear, so along a line it necessarily grows at constant rate in one direction. That means that a point $p$ along the line that is feasible but not a corner will always be worse (or at best equal) to one of the two corners on that line. If one corner is worse than $p$, then the other corner will be better.
And if you have a feasible point that is not even on an edge, then if you walk in any direction, the payoff / function to be optimised either increases or decreases. If it increases, walk until you meet an edge, and if it decreases, turn around and walk until you meet an edge. Then use the paragraph above.
Best Answer
Let's get the feel of this in 2-D (so with 2 variables). When you add a constraint, you add a line in the plane and forbid the solution to be in one of the two sides, and only allow it to be in the remaining side. It is noticeable that it gives a convex feasable solution region. With n constraints, it's the same : for each line (from each constraint), you have to be in one side, so you have to be in the intersection of all the "half" spaces. The intersection of convex regions being convex, you have your answer.
The same idea can be used with k dimensions, but "lines" are replaced by "hyperplans" (for example a plane in 3-D).