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?
[Math] Why are corner points of feasible region candidates in solving linear programming problem
convex optimizationlinear programmingoptimization
Related Solutions
The only way I think you can use a quickly solvable linear programming formulation to find something close to a center would be to take your "truly free" inequalities in the form $Ax \leq b$, i.e. after all the implicit equations $Cx = d$ have been identified and removed from the inequalities and expressed separately, and then add one extra variable $\epsilon$ and solve the LP: $\max \epsilon$ subject to $Ax + \epsilon \leq b$ and $Cx = d$. Then whatever solution $(x,\epsilon)$ you get, you will have that $x$ will be toward the center of your original feasible region.
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.
Best Answer
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.