GATE 2022 MA – Question 55
For the primal min cᵀx subject to Ax=b,x≥0, let x⁰,y⁰ be primal and dual feasible. Which hold?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (A) cᵀx⁰≥bᵀy⁰; (C) If equality holds, x⁰ is primal optimal.; (D) If equality holds, y⁰ is dual optimal.
Explanation
The dual is max bᵀy subject to Aᵀy≤c. Feasibility gives cᵀx⁰−bᵀy⁰=(c−Aᵀy⁰)ᵀx⁰≥0, proving weak duality A. Equality is not automatic. When equality occurs the common value bounds every feasible primal/dual objective in the appropriate direction, proving optimality of both. **A,C,D**.