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<\infty$ , 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(\overline{pq})=\{a\}$ . If $r$ is a third corner point such that $f(r)=a$ , then $f(\triangle pqr)=\{a\}$ .

Note that the line segment and triangle mentioned above are necessarily subsets of $R$ .

A cousin of the above theorem is the following:

Theorem. If $P$ has an optimal solution $a<\infty$ occurring at an interior point 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=[x_{0},x_{1}]$ on the $x$ -axis. It is easy to see now that the maximum (or minimum) of $f$ occurs at either $x_{0}$ or $x_{1}$ . If the optimal value occurs either at both end points, or at an interior point $x_{2}\in(x_{0},x_{1})$ , 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)\mid x=y\}\cap R$ satisfy the solution. In particular, $(\frac{1}{2},\frac{1}{2})$ , 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