Discussion
If the set of feasible solutions of the system AX = B, \(X \ge 0\), is a convex polyhedron, then at least one of the extreme points gives a/an :
Answer: C
At least one extreme point gives an optimal solution.
This is the fundamental theorem of linear programming. When the feasible set of \(AX = B, X \ge 0\) is a convex polyhedron (bounded and non-empty), the linear objective is continuous on a compact set and so attains its optimum. Every point of a polytope is a convex combination of its extreme points, and a linear function on such a combination cannot exceed its largest value at those vertices, so an optimum is reached at an extreme point.
That is why the simplex method searches only basic feasible solutions. An unbounded solution cannot occur on a bounded polyhedron, an infeasible solution contradicts the set being non-empty, and 'bounded but not optimal' is not a property the theorem gives.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development