0

Our strong duality theorem is:

If both the primal LP and the dual LP have feasible solutions, then they both have optimal solutions, and for any primal optimal solution $x$ and dual optimal solution $y$, we have $c^Tx=b^Ty$.

Can this be written as:

Both the primal LP and the dual LP have feasible solutions $\iff$ then they both have optimal solutions $\iff$ for any primal optimal solution $x$ and dual optimal solution $y$, we have $c^Tx=b^Ty$.

snowman
  • 3,733
  • 8
  • 42
  • 73

1 Answers1

0

No. While the first equivalence could be proven, the last equivalence does not hold. Given an appropriate formulation of the primal and dual linear program, the last statement: "for any primal optimal solution $x$ and dual optimal solution $y$, we have $c^Tx=b^Ty$" is always true, even if the primal linear program is infeasible. Indeed, it is a consequence of the strong duality theorem.