1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Strong Duality Theorem in Linear Programming

  1. Feb 12, 2012 #1
    If a linear Program (P) has a feasible solution [itex]x_{o}[/itex], ( [itex]x_{o}[/itex] not necessarily optimal),does it follow that there exists a feasible solution to the dual problem (D) as well? If yes, why?

    I know that the Strong Duality Theorem guarantees an optimal finite solution to the dual problem if the primal problem has an optimal finite solution. But I cannot see why this would be the case if the feasible solution to the primal is not necessarily optimal.
  2. jcsd
  3. Feb 13, 2012 #2

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    If P is the primal and D is the dual, the possibilities are: (i) P and D are both feasible (in which case they both have finite optimal solutions with equal objectives); (ii) P is feasible and D is infeasible (in which case P has no finite optimum); (iii) D is feasible and P is infeasible (in which case D has no finite optimum); (iv) both P and D are infeasible.

  4. Feb 13, 2012 #3
    Thanks :). That helps!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook