Vertices
Vertices
A vertex is a corner point of a polyhedron. In graphical LP, finite optima are found at vertices when they exist.
Geometric Meaning
In two dimensions, a vertex is where boundary lines meet and the feasible region changes direction.
Example: the intersection of
\[x_1+2x_2=10,\qquad 2x_1+x_2=16\]is
\[\left(\frac{22}{3},\frac{4}{3}\right).\]It is a vertex only if it satisfies all constraints.
Active-Constraint View
A vertex is usually determined by enough linearly independent active constraints.
In standard form, $Ax=b$ is always active, and the zero variables add active nonnegativity constraints.
Connection to BFS
For
\[P=\{x\mid Ax=b,\ x\ge 0\},\]vertices correspond to basic feasible solutions under the usual full-rank assumptions:
\[\text{vertex}\Longleftrightarrow\text{basic feasible solution}.\]Finding Vertices Graphically
- Draw all boundary lines.
- Find intersections of pairs of boundaries.
- Test each candidate against all constraints.
- Keep only feasible intersections.
Checklist
You should be able to compute candidate intersections, test feasibility, and connect each feasible vertex to active constraints.
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.