If the primal Linear Programming problem has unbounded solution, then it’s…
2013
If the primal Linear Programming problem has unbounded solution, then it’s dual problem will have
- A.
feasible solution
- B.
alternative solution
- C.
no feasible solution at all
- D.
no bounded solution at all
Attempted by 31 students.
Show answer & explanation
Correct answer: C
Answer: The dual has no feasible solution (it is infeasible).
Explanation:
Assume the primal is a maximization problem and is unbounded: there exist feasible primal solutions with arbitrarily large objective values.
Suppose, for contradiction, that the dual has at least one feasible solution. Let y be any feasible dual solution.
By weak duality, for every feasible primal x and feasible dual y we have c^T x ≤ b^T y, so the primal objective is bounded above by the fixed number b^T y.
This contradicts the assumption that the primal objective can grow without bound. Therefore the dual cannot have any feasible solution; the dual is infeasible.
Note: The conclusion is the same in the symmetrical case (a minimization primal unbounded below implies the dual is infeasible).