Optimal solutions at vertices
Find optimal solutions at vertices of the feasible region: the maximum or minimum of a linear objective function always occurs at a corner point when the region is bounded.
Key Concepts
The minimum or maximum value of the objective function always occurs at a vertex of the feasible region. Why check the whole playground when the treasure is always buried in the corners? The best and worst outcomes are always at the vertices. Just test those points to find the optimal solution efficiently.
Example 1: To maximize P = 5x + 3y with vertices at (0,0), (0,10), (5,5), and (8,0), we test each point. The maximum profit of 40 occurs at the vertex (8,0). Example 2: To minimize C = 2x + 4y with vertices at (0,20), (10,5), and (30,0), we check each vertex. The minimum cost of 40 is found at the vertex (10,5).
This is the ultimate shortcut in linear programming! Instead of checking infinite points in the feasible region, you only need to check the corner points (vertices). Plug the coordinates of each vertex into your objective function, and the biggest or smallest result is your answer.
Common Questions
Why do optimal solutions in linear programming occur at vertices?
The Vertex Theorem states that if a linear objective function has an optimal value over a convex feasible region, it must occur at a vertex (corner point). This is because linear functions achieve their extremes at the boundary, not the interior.
How do you find the optimal solution using vertices?
Identify all vertices of the feasible region by solving pairs of boundary equations. Evaluate the objective function at each vertex. The vertex that produces the largest or smallest value (depending on whether you are maximizing or minimizing) is the optimal solution.
What happens if the feasible region is unbounded?
If the feasible region extends infinitely, there may be no maximum (for a maximization problem) or no minimum (for a minimization problem). However, if the objective function has an optimal value, it still occurs at a vertex of the bounded portion of the region.