Question

Let 𝑆 be a feasible set of a linear programming problem (𝑃). If the dual problem of (𝑃) is unbounded then

• A. (P) is unbounded
• B. S is empty
• C. S is unbounded
• D. (P) has multiple optimal solutions

Answer 1

The Correct Option is B

The given problem involves a concept from linear programming, specifically relating to the duality of a linear programming problem. To solve this problem, we need to understand the nature of dual problems and their relationship to the primal problem.

In a linear programming problem, there is a primal problem (P) and a corresponding dual problem. According to duality theory, if the dual problem is unbounded, it generally implies the primal problem has no feasible solution. This relationship is crucial in determining the status of the feasible set 𝑆 of the primal problem.

The options given are:

1. (P) is unbounded
2. 𝑆 is empty
3. 𝑆 is unbounded
4. (P) has multiple optimal solutions

Let's analyze each option:

1. (P) is unbounded: If a dual problem is unbounded, it does not necessarily mean the primal problem is unbounded. In fact, the lack of bounds in the dual usually indicates issues with the feasibility of the primal rather than its boundedness.
2. 𝑆 is empty: When a dual problem is unbounded, it typically indicates that the primal problem does not have any feasible solutions. Hence, the feasible set 𝑆 is empty.
3. 𝑆 is unbounded: As previously explained, an unbounded dual problem does not mean the feasible set of the primal is unbounded. It usually implies no feasible solutions exist, which means 𝑆 is empty, not unbounded.
4. (P) has multiple optimal solutions: Having multiple optimal solutions indicates that the problem is feasible and possibly has a bounded optimal point, but since the dual is unbounded, the primal doesn't have feasible solutions at all.

Based on duality theory and the options provided, the correct answer is that the feasible set 𝑆 is empty. The unbounded nature of the dual indicates that the primal does not present a consistent set of constraints that can be satisfied, leading to an empty feasible set.