# 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 $$, 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(\mathrm{\u25b3}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 $$ 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 |