In Business Analytics and Linear Programming & Optimization, one of the most important geometric facts is that optimal solutions occur at corner points (also called extreme points or vertices). This idea appears constantly in graduate optimization courses and in tutoring sessions on simplex, feasibility, and model formulation.
This page explains what corner points are, why linear programs achieve optima there, and how to identify them in practice.
What Is a Corner Point in Linear Programming?
A corner point is a point in the feasible region where a set of constraints intersect to form a vertex of the polyhedron. In algebraic terms, it is a basic feasible solution (BFS).
Every corner point corresponds to:
- a unique basis of active (binding) constraints
- a solution obtained by setting n–m variables to zero and solving for the remaining m
- a feasible point that cannot be expressed as a convex combination of other feasible points
Corner points are the “edges” of the feasible region where simplex moves.
Why Do Optimal Solutions Occur at Corner Points?
1. The feasible region is a convex polyhedron
Linear constraints form a convex set. Convex sets have the property that any local optimum is a global optimum.
2. The objective function is linear
A linear objective has flat, parallel contour lines. Sliding these lines outward pushes the objective to the boundary of the feasible region.
3. The maximum or minimum occurs where a contour touches the feasible region
The first point of contact between a contour line and the feasible region is always a corner point or an edge containing corner points.
4. Fundamental Theorem of Linear Programming
If an LP has an optimal solution, then at least one optimal solution is a corner point.
5. Simplex exploits this geometry
Simplex moves from corner to corner along edges, improving the objective until no better adjacent corner exists.
How to Identify Corner Points
- Set n–m variables to zero and solve for the remaining m.
- Find intersections of binding constraints (solve pairs or sets of equations).
- Check feasibility — only feasible intersections count.
- Use simplex — each BFS corresponds to a corner point.
- Graphically (in 2D): look for vertices of the polygon.
In higher dimensions, algebraic methods or simplex tableau analysis are required.
Numerical Example
Consider the LP:
\[ \text{Max } z = 3x_1 + 2x_2 \]
\[ \begin{aligned} x_1 + x_2 &\le 6 \\ x_1 &\le 4 \\ x_2 &\le 5 \\ x_1, x_2 &\ge 0 \end{aligned} \]
Corner points:
- (0,0)
- (4,0)
- (4,2)
- (1,5)
- (0,5)
Evaluating the objective at each point shows the maximum occurs at (4,2). This is a corner point — confirming the theorem.
Common Mistakes
- Thinking optimal solutions can occur in the interior — not possible with a linear objective.
- Confusing feasible intersections with infeasible ones.
- Forgetting that multiple optimal solutions lie on an edge between two corner points.
- Assuming simplex “skips” corners — it never does.
- Believing degeneracy contradicts the theorem — it does not.
Why This Matters
Understanding corner points helps you:
- interpret simplex movement
- diagnose degeneracy and stalling
- understand multiple optimal solutions
- formulate LPs with correct geometry
- analyze binding constraints at optimality
It is foundational for all of linear programming and optimization.
Related Topics
This idea connects directly to:
Speak Directly to a Tutor — Send Your Message Below
No call centers. No delays. Your message goes straight to the tutor.
- Call/Text: 510-398-0006
- Email: tutor@californiagraduatetutor.com
- WhatsApp: Send Files