The region of feasible solution of a linear programming problem has a _____…
2016
The region of feasible solution of a linear programming problem has a _____ property in geometry, provided the feasible solution of the problem exists.
- A.
concavity
- B.
convexity
- C.
quadratic
- D.
polyhedron
Attempted by 31 students.
Show answer & explanation
Correct answer: B
Answer: convexity
Why:
The feasible region of a linear programming problem is defined by a finite set of linear inequalities and equalities. Each linear inequality defines a half-space, and the feasible region is the intersection of these half-spaces. Intersections of convex sets are convex, so the feasible region is convex.
Consequence: any line segment joining two feasible points lies entirely inside the feasible region.
Geometric note: the feasible region is a convex polyhedron (or a polytope if bounded).
Implication for optimization: for a linear objective, if an optimal solution exists it can be found at an extreme point (vertex) of this convex feasible region.