Results 1 to 2 of 2

Math Help - Lagrangian duality applied to lineair programs

  1. #1
    Newbie
    Joined
    Jun 2010
    Posts
    1

    Lagrangian duality applied to lineair programs

    Hi all,

    I'm trying to understand the connection between Lagrangian duality and the dual of a linear program.

    Let's say we want to maximize cx, subject to Ax<=b and x >= 0

    Now, the lagrangian dual would be:

    g(y) = Maximize cx + y(b-Ax) to x, subject to x>=0

    Or, after some rearranging:

    g(y) = Maximize yb +(c-Ay)x, subject to x >= 0

    Obviously, the only solution which is not infinity, is where (c-Ay)<=0
    In that case, g(y) = yb, and the optimal x(y) is 0

    If we then minimize this lagranguan dual, we actually get the dual of the linear program as expected:

    minimize g(y)=by, subject to y>=0 and Ac>=0

    However, what I don't understand is that the optimal x(y) of the lagranguan dual function g(y) is 0, because this would mean that the original linear program has its optimum at x=0, which off course is not necessarily the case.

    I'm probably forgetting something, and I have the feeling that my confusion has something to do with the fact that only non-basic variables will be zero in the optimal lineair program.

    Anyway who can help me out here?

    Tnx!
    Kind regards,
    Varno
    Follow Math Help Forum on Facebook and Google+

  2. #2
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    It seems to me this problem belongs more in the Discrete Math forum, as that's where linear programming usually falls.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Lagrangian Duality in Linear Programming
    Posted in the Advanced Applied Math Forum
    Replies: 7
    Last Post: May 17th 2011, 12:42 PM
  2. Pontryagin duality
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: May 3rd 2011, 07:58 PM
  3. Reflexive + lineair
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 10th 2009, 10:18 AM
  4. Strong Duality Theorem
    Posted in the Advanced Applied Math Forum
    Replies: 0
    Last Post: September 20th 2009, 07:36 PM
  5. optimization problem (duality etc)
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: March 20th 2007, 09:30 PM

Search Tags


/mathhelpforum @mathhelpforum