Consider a linear program {max cᵀx | Ax ≤ b}. Which of the following statements is true?

Explanation

By the LP duality rules, a '≤' constraint in a max primal corresponds to a non-negative dual variable (y ≥ 0), and an unrestricted (free) primal variable x corresponds to an equality constraint in the dual. Here x carries no sign restriction in the primal {max cᵀx | Ax ≤ b}, so the dual must have Aᵀy = c with y ≥ 0, and since the primal is a maximization with ≤ constraints the dual is a minimization: {min bᵀy | Aᵀy = c, y ≥ 0}, which is option (3).