Which of the following statements is true with respect to the optimal solution of an LP problem?
a) Every LP problem has an optimal solution b) Optimal solution of an LP problem always occur at an extreme point c) At optimal solution, all resources are completely used d) If an optimal solution exists, there will always be at least one at a corner
The correct answer and explanation is :
Correct Answer: d) If an optimal solution exists, there will always be at least one at a corner
Explanation:
Linear Programming (LP) is a mathematical method used for optimizing a linear objective function, subject to a set of linear inequality or equality constraints. It is widely used in resource allocation, production planning, transportation, and other operational areas.
Among the given options, option d is the correct statement: “If an optimal solution exists, there will always be at least one at a corner.”
This is a fundamental result in linear programming. The feasible region formed by the constraints of an LP problem is a convex polyhedron (in two dimensions, this looks like a polygon). The optimal solution to an LP problem—if it exists—will always be found at one of the extreme points (also known as corner points) of the feasible region. These are the points where the constraint boundaries intersect.
This property is what allows algorithms like the Simplex method to work efficiently. Rather than checking infinitely many points within the feasible region, the algorithm can simply move from one corner to another, improving the objective function, until it reaches an optimal corner.
Now, let’s briefly examine why the other options are incorrect:
- a) Every LP problem has an optimal solution – Incorrect. Some LP problems may be infeasible (no solution satisfies all constraints) or unbounded (the objective function can increase indefinitely), in which case no optimal solution exists.
- b) Optimal solution of an LP problem always occur at an extreme point – Incorrect as stated. If there are multiple optimal solutions, some of them may lie along an edge or line segment between two extreme points, not just at a single extreme point.
- c) At optimal solution, all resources are completely used – Incorrect. Sometimes not all constraints (resources) are binding at the optimal solution. Some may have slack.
Hence, option d is the most accurate and foundational statement in the context of LP problems.
