Operations research
Explainer
Why LP Optima Sit at Corners
The best answer to a linear program is always hiding at a corner.
Quick check · tap an answer to continue
Lesson notes
Key points
- The feasible region of a linear program is a convex polygon, whose corners are called extreme points or vertices.
- Because the objective is linear, sliding its line across the region, the last point touched is a vertex.
- So the graphical method simply evaluates the objective at each vertex and picks the best value.
Definitions
- Extreme point
- A corner of the feasible region where constraint boundary lines intersect.
Takeaway: Check the corners: an LP optimum is always at a vertex.
Quick check: Where does a bounded LP's optimum always occur?
- At the origin
- At the region's centre
- At a vertex
Extreme pointsIso-profit lineGraphical method
Lessons like this, for your syllabus.
Short narrated study videos written for your course, level and exam. Free to start.
Get lessons for your own syllabus