Consider the following statements : (a) If primal (dual) problem has a finite…
2016
Consider the following statements :
(a) If primal (dual) problem has a finite optimal solution, then its dual (primal) problem has a finite optimal solution.
(b) If primal (dual) problem has an unbounded optimum solution, then its dual (primal) has no feasible solution at all.
(c) Both primal and dual problems may be infeasible. Which of the following is correct ?
- A.
(a) and (b) only
- B.
(a) and (c) only
- C.
(b) and (c) only
- D.
(a), (b) and (c)
Attempted by 16 students.
Show answer & explanation
Correct answer: D
Answer: All three statements are true.
Statement (a): If the primal (or dual) problem has a finite optimal solution, then the dual (or primal) problem has a finite optimal solution.
Reason: Strong duality for linear programs states that when a primal (or dual) is feasible and attains a finite optimum, the corresponding dual (or primal) is also feasible and attains the same finite optimum value.
Statement (b): If the primal (or dual) problem has an unbounded optimum, then the dual (or primal) has no feasible solution.
Reason: Weak duality implies any feasible dual objective value is a bound on the primal objective. If the primal objective can be made arbitrarily good (unbounded), there cannot exist any feasible dual solution (otherwise the bound would be finite), so the dual is infeasible.
Statement (c): Both primal and dual problems may be infeasible.
Reason: It is possible to construct LPs whose constraint systems are mutually inconsistent so that neither the primal nor the dual has any feasible point. This is a standard possibility in LP theory (see consequences of Farkas' lemma).
Conclusion: All three statements are correct.