Question

Let \( A \in \mathbb{R}^{m \times n}, c \in \mathbb{R}^n \) and \( b \in \mathbb{R}^m \). Consider the linear programming primal problem
\[ \text{Minimize: } c^T x \] \[ \text{subject to: } A x = b, \quad x \geq 0. \] Let \( x^0 \) and \( y^0 \) be feasible solutions of the primal and its dual, respectively. Which of the following statements are TRUE?

• A. \( c^T x^0 \geq b^T y^0 \)
• B. \( c^T x^0 = b^T y^0 \)
• C. If \( c^T x^0 = b^T y^0 \), then \( x^0 \) is optimal for the primal
• D. If \( c^T x^0 = b^T y^0 \), then \( y^0 \) is optimal for the dual

Hint:

In linear programming, weak duality ensures that \( c^T x^0 \geq b^T y^0 \) for feasible solutions. Strong duality ensures that if the equality holds, both the primal and dual solutions are optimal.

Answer 1

The Correct Option is A, C, D

We are given a linear programming primal problem with feasible solutions \( x^0 \) and \( y^0 \) for the primal and dual problems, respectively. We need to analyze the truth of the given statements. Option (A) \( c^T x^0 \geq b^T y^0 \): This statement is true. In linear programming, for any feasible solutions \( x^0 \) of the primal and \( y^0 \) of the dual, the weak duality theorem holds, which states that the objective value of the primal is always greater than or equal to the objective value of the dual. Hence, we have: \[ c^T x^0 \geq b^T y^0. \] Thus, option (A) is correct. Option (B) \( c^T x^0 = b^T y^0 \): This statement is false. While it is true that \( c^T x^0 \geq b^T y^0 \) due to weak duality, the equality \( c^T x^0 = b^T y^0 \) only holds if both \( x^0 \) and \( y^0 \) are optimal solutions for the primal and dual problems, respectively. Hence, this equality is not always true for feasible solutions but holds when both solutions are optimal. Thus, option (B) is incorrect. Option (C) If \( c^T x^0 = b^T y^0 \), then \( x^0 \) is optimal for the primal: This statement is true. If the equality \( c^T x^0 = b^T y^0 \) holds, it implies that both \( x^0 \) and \( y^0 \) are optimal solutions for the primal and dual problems, respectively, due to the strong duality theorem. Therefore, \( x^0 \) is optimal for the primal problem. Thus, option (C) is correct. Option (D) If \( c^T x^0 = b^T y^0 \), then \( y^0 \) is optimal for the dual: This statement is true. Similar to option (C), if \( c^T x^0 = b^T y^0 \), this implies that both \( x^0 \) and \( y^0 \) are optimal solutions for the primal and dual problems, respectively, as per the strong duality theorem. Hence, \( y^0 \) is optimal for the dual problem. Thus, option (D) is correct. Therefore, the correct answers are (A), (C), and (D).