Polyhedra
Polyhedra
A polyhedron is a set described by finitely many linear equalities and inequalities. Linear programming feasible regions are polyhedra.
Definition
A set $P\subseteq\mathbb{R}^n$ is a polyhedron if it can be written as
\[P=\{x\in\mathbb{R}^n\mid Ax\le b,\ Cx=d\}.\]The inequalities give half-spaces. The equalities give hyperplanes.
Standard-Form Polyhedron
For standard form,
\[P=\{x\mid Ax=b,\ x\ge 0\}.\]The equality $Ax=b$ gives an affine set. The inequalities $x\ge 0$ restrict it to the nonnegative orthant.
Convexity
Every polyhedron is convex. If $x,y\in P$, then
\[\lambda x+(1-\lambda)y\in P,\qquad 0\le\lambda\le 1.\]This is because half-spaces and hyperplanes are convex, and intersections of convex sets are convex.
Possible Shapes
In two dimensions, a polyhedron may be a polygon, ray, strip, wedge, line segment, single point, unbounded region, or the empty set.
A bounded polyhedron is often called a polytope.
Role in LP
An LP optimizes a linear function over a polyhedron:
\[\min c^Tx\quad \text{subject to }x\in P.\]The shape of $P$ determines feasibility, boundedness, vertices, and simplex movement.
Checklist
You should be able to distinguish nonempty, empty, bounded, and unbounded polyhedra, and explain why LP feasible regions are convex.
See Also
Exam checkpoint
For BFS questions, convert to standard form before checking the point. A candidate in original variables must be lifted with slack and surplus variables before testing basis columns.