corner point theorem
Corner Point Theorem. If has an optimal solution , then there is a corner point of such that . If another corner point also satisfies , then . If is a third corner point such that , then .
A cousin of the above theorem is the following:
Theorem. If has an optimal solution occurring at an interior point of an edge (or a face ) on the boundary of the feasible region , then (or ). In fact, if the solution occurs at an interior point of , then the solution is satisfied by all points of : . In other words, the objective function is constant on .
On way to visualize the above theorems is to simplify them into the case when the objective function is a line on the “ plane” and the feasible region is a line segment on the -axis. It is easy to see now that the maximum (or minimum) of occurs at either or . If the optimal value occurs either at both end points, or at an interior point , then is a horizontal line segment on .
An application of the above theorems can be demonstrated by the following example: If the feasible region is a unit square and if corner points satisfy the optimal solution of , then all points on satisfy the solution. In particular, , an interior point of , satisfies the solution. As a result, all points of satisfy the solution.
|Title||corner point theorem|
|Date of creation||2013-03-22 15:39:16|
|Last modified on||2013-03-22 15:39:16|
|Last modified by||CWoo (3771)|
|Synonym||fundamental theorem of linear programming|