corner point theorem

Let P be a primal linear programming problem with f the objective function and polyhedron R as its feasible region. A corner point, or extreme point of P is a of R.

Corner Point Theorem. If P has an optimal solution a<, then there is a corner point p of P such that f(p)=a. If another corner point q also satisfies f(x)=a, then f(pq¯)={a}. If r is a third corner point such that f(r)=a, then f(pqr)={a}.

Note that the line segmentMathworldPlanetmath and triangleMathworldPlanetmath mentioned above are necessarily subsets of R.

A cousin of the above theorem is the following:

Theorem. If P has an optimal solution a< occurring at an interior pointPlanetmathPlanetmath of an edge E (or a face F) on the boundary of the feasible region R, then f(E)={a} (or f(F)={a}). In fact, if the solution occurs at an interior point of R, then the solution is satisfied by all points of R: f(R)={a}. In other words, the objective function f is constant on R.

On way to visualize the above theorems is to simplify them into the case when the objective function is a line f(x)=mx+b on the “x-y plane” and the feasible region is a line segment I=[x0,x1] on the x-axis. It is easy to see now that the maximum (or minimum) of f occurs at either x0 or x1. If the optimal value occurs either at both end pointsPlanetmathPlanetmath, or at an interior point x2(x0,x1), then f is a horizontal line segment on I.

An application of the above theorems can be demonstrated by the following example: If the feasible region R is a unit square and if corner points (0,0),(1,1) satisfy the optimal solution of P, then all points on {(x,y)x=y}R satisfy the solution. In particular, (12,12), an interior point of R, satisfies the solution. As a result, all points of R satisfy the solution.

Title corner point theorem
Canonical name CornerPointTheorem
Date of creation 2013-03-22 15:39:16
Last modified on 2013-03-22 15:39:16
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 12
Author CWoo (3771)
Entry type Theorem
Classification msc 90C05
Synonym fundamental theorem of linear programming
Defines corner point