Consider the following true/false questions:
If an LP is unbounded, its feasible region must be unbounded.
If an LP has an unbounded feasible region, it must be unbounded.
If an LP has an optimal solution, there must be at least two binding constraint(s) at that optimal solution.
If an LP has two optimal solutions, there must be another optimal solution that is different from the first two.
An LP’s optimal solution is always an extreme point.
The Correct Answer and Explanation is :
Correct Answers:
- True: If an LP is unbounded, its feasible region must be unbounded.
- False: If an LP has an unbounded feasible region, it must be unbounded.
- False: If an LP has an optimal solution, there must be at least two binding constraints at that optimal solution.
- False: If an LP has two optimal solutions, there must be another optimal solution that is different from the first two.
- True: An LP’s optimal solution is always an extreme point.
Explanation:
- Unbounded LPs and feasible regions (True):
For an LP to be unbounded, its feasible region must extend infinitely in the direction that improves the objective function. Without an unbounded feasible region, the objective function cannot increase or decrease indefinitely. - Unbounded feasible region and LP unboundedness (False):
An unbounded feasible region does not guarantee an unbounded objective function. For example, constraints may limit the objective function’s value within finite bounds, despite the feasible region extending infinitely in certain directions. - Binding constraints at optimal solutions (False):
It is possible to have an optimal solution with fewer than two binding constraints. For instance, in a degenerate LP or at an extreme point of the feasible region, fewer than two constraints may bind the solution. - Multiple optimal solutions (False):
If an LP has two optimal solutions, all points along the line segment connecting them are also optimal solutions. However, these solutions are not distinct; they are linear combinations of the two given solutions, so they lie on the same segment. - Extreme points and optimal solutions (True):
In LPs, optimal solutions occur at extreme points (vertices) of the feasible region. If there are multiple optimal solutions, they exist along the line segment between two extreme points. The simplex method exploits this property by moving along extreme points to find the optimal solution.
Understanding these properties is critical for solving LP problems and interpreting their solutions accurately.