Question

In the Simplex method, what specific geometric property of the feasible region corresponds to an optimal solution found at a vertex?

Accepted Answer

In linear programming, the feasible region is the set of all possible points that satisfy every constraint in a problem. This region forms a geometric shape known as a convex polyhedron, where the boundary consists of flat sides called faces, edges, and corners known as vertices. A fundamental theorem in linear programming states that if an optimal solution exists, it must occur at one of these vertices. The specific geometric property at work here is the linearity of the objective function and the convexity of the feasible region. Because the objective function is linear, it represents a flat surface, such as a plane in three dimensions, that moves across the feasible region as you change the target value. As this plane moves to maximize or minimize the objective, it will eventually hit a boundary point before leaving the feasible region entirely. Since the region is convex, meaning any line segment connecting two points inside it stays entirely within it, the shape has no indentations. Consequently, the last points touched by the objective function are the extreme points, or vertices, of the polyhedron. If the objective function is parallel to an entire edge or face, the optimal solution is not just a single vertex but can be any point along that edge or face, yet at least one of those optimal points is guaranteed to be a vertex.

Home → All Courses → Science and Mathematics Courses → Decision Science and Optimization → Flashcard

In the Simplex method, what specific geometric property of the feasible region corresponds to an optimal solution found at a vertex?