Results 1 to 2 of 2

Math Help - NonNegative Bounds in Linear Programming problem

  1. #1
    Newbie
    Joined
    Mar 2011
    Posts
    1

    NonNegative Bounds in Linear Programming problem

    Hello everyone,

    I am not really sure where to post about Linear Programming. I am trying to program an LP problem using PuLP, as I am very familiar with Python.

    I faced the issue of having decision variables which can take negative value,
    i.e. they are bound between -k1 and K2. I have seen the advice of introducing
    a new variable into the problem, so the original cosntraint is shifted in
    order for the new variable to be non-negative only. I'd guess that the
    substitution has to be carried out throughout the problem, i.e anywhere the
    original variable appears (including objective function) but I would be
    grateful if someone could confirm this.

    Below I have written a simple problem and the reformulated proble.

    I would like to know:
    - is what I am doing correct?
    - is there a better approach to this problem?

    Many Thanks in advance

    Paolo

    Original problem,

    Max -p1x1 - p2x2
    x1 >= -10
    x1 <= 20
    x2 >= -30
    x2 <= 40
    Inv + x1 >= 0
    Inv + x1 + x2 >= 0
    Inv + x1 <= TC
    Inv + x1 + x2 <= TC

    with TC and Inv being positive constants

    Reformulated Problem:

    Given L1 = -10, y1 = x1 - L1 x1 = y1 + L1
    x1 >= -10 y1 + L1 >= -10 y1 >= 0 (change var and subtract L1)
    x1 <= 20 y1 + L1 <= 20 y1 <= 20 + 10 (change var and subtract L1)
    Inv + x1 >= 0 Inv + y1 + L1 >= 0 Inv + y1 >= 10 (change var and
    subtract L1)
    Inv + x1 <= TC Inv + y1 + L1 <= TC Inv + y1 <= TC + 10 (change var and
    subtract L1)

    Given L2 = -30, y2 = x2 - L2 x2 = y2+ L2
    x2 >= -30 y2 + L2 >= -30 y2 >= 0 (change var and subtract L2)
    x2 <= 40 y1 + L2 <= 40 y1 <= 40 + 30 (change var and subtract L2)

    Given L1 = -10 and L2 = -30
    Inv + x1 + x2 >= 0 Inv + y1 + L1 + y2 + L2

    >= 0
    Inv + y1 + y2 >= -(L1 + L2) Inv + y1 + y2 >= 40
    Inv + x1 + x2 <= TC Inv + y1 + L1 + y2 + L2
    <= TC
    Inv + y1 + y2 >= -(L1+L2) + TC Inv + y1 + y2 <= 40 + TC

    Finally, Max -p1x1 - p2x2 Max -p1(y1+L1) - p2(y2+L2)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by LutherBlissett View Post
    Hello everyone,

    I am not really sure where to post about Linear Programming. I am trying to program an LP problem using PuLP, as I am very familiar with Python.

    I faced the issue of having decision variables which can take negative value,
    i.e. they are bound between -k1 and K2. I have seen the advice of introducing
    a new variable into the problem, so the original cosntraint is shifted in
    order for the new variable to be non-negative only. I'd guess that the
    substitution has to be carried out throughout the problem, i.e anywhere the
    original variable appears (including objective function) but I would be
    grateful if someone could confirm this.

    Below I have written a simple problem and the reformulated proble.

    I would like to know:
    - is what I am doing correct?
    - is there a better approach to this problem?

    Many Thanks in advance

    Paolo

    Original problem,

    Max -p1x1 - p2x2
    x1 >= -10
    x1 <= 20
    x2 >= -30
    x2 <= 40
    Inv + x1 >= 0
    Inv + x1 + x2 >= 0
    Inv + x1 <= TC
    Inv + x1 + x2 <= TC

    with TC and Inv being positive constants
    Put:

    y1=x1+10
    y2=x2+30

    now rewrite the problem replacing x1 by (y1-10) and x2 by (y2-30) throughout.

    CB
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Linear Programming problem
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: November 29th 2011, 04:45 PM
  2. Linear Programming Problem
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: January 5th 2010, 05:29 AM
  3. Linear Programming Problem
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: December 6th 2009, 05:15 PM
  4. linear programming problem
    Posted in the Advanced Applied Math Forum
    Replies: 0
    Last Post: January 29th 2009, 09:36 PM
  5. Linear Programming-Need help with one problem
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: November 17th 2007, 05:44 AM

Search Tags


/mathhelpforum @mathhelpforum