1. Not finding help here? Sign up for a free 30min 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!

Post-optimality analysis: Change in one of the constraints

  1. Apr 28, 2014 #1
    1. The problem statement, all variables and given/known data

    Consider the LP:

    max [itex]\, -3x_1-x_2[/itex]
    [itex]\,\,[/itex]s.t. [itex]\,\,\,\,[/itex] [itex]2x_1+x_2 \leq 3[/itex]
    [itex]\quad \quad \ -x_1+x_2 \geq 1[/itex]
    [itex]\quad \quad \quad \quad \ x_1,x_2 \geq 0[/itex]


    Suppose I have solved the above problem for the optimal solution. (I used dual simplex and get (0,1) as the optimal solution.)
    Now if the first constraint [itex](2x_1+x_2 \leq 3)[/itex] is either changed to

    (1) max [itex]\, (2x_1+x_2,0) \leq 3[/itex], or
    (2) max [itex]\, (2x_1+x_2,6)\leq 3[/itex],

    is it possible to obtain the new optimal solution without having to solve the entire problem from the scratch?



    2. Relevant equations



    3. The attempt at a solution


    I have tried introducing a new variable t to address the maximum and rewrite the constraints in linear form but it doesn't seem to help.

    Any hint or comment is greatly appreciated, thank you!
     
  2. jcsd
  3. Apr 28, 2014 #2

    Zondrina

    User Avatar
    Homework Helper

    Your optimal solution of ##(0,1)## is correct for the first part yielding a max of ##-1##. Could you elaborate on conditions (1) and (2) a bit more? I'm not quite sure what the ##', 0)'## and ##', 6)'## translate to.
     
  4. Apr 28, 2014 #3
    conditions (1) should read "the larger of [itex](2x_1+x_2)[/itex] and [itex]0[/itex] is smaller than 3", that is, if [itex]0 \leq 2x_1+x_2[/itex] then we also have [itex]0 \leq 2x_1+x_2 \leq 3[/itex], otherwise, if [itex]2x_1+x_2 \leq 0[/itex] then [itex]2x_1+x_2 \leq 0[/itex].
     
  5. Apr 28, 2014 #4

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Since 3 > 0 the constraint ##\max(2x_1+x_2,0) \leq 3## is the same as the simple constraint ##2x_1 + x_2 \leq 3##; can you see why? Anyway, the solution (1,0) satisfies it, so there would be no change in the solution.

    The second form ##\max(2x_1+x_2,6)\leq 3## is infeasible. Can you see why no ##x_1, x_2## can possibly satisfy that inequality? (If you changed '##\max##' to '##\min##' you could satisfy it. Again, can you see why?)
     
  6. Apr 28, 2014 #5

    Zondrina

    User Avatar
    Homework Helper

    If ##2x_1 + x_2 ≤ 0##, there is no maximum.

    You simply can't use the second condition.
     
  7. Apr 28, 2014 #6
    Thank you all, I think I've got what you said,
    for (1) since it was given that [itex]x_1,x_2 \geq 0[/itex], [itex]2x_1+x_2 \geq 0[/itex] hence the constraint is equivalent to [itex]2x_1+x_2 \leq 3[/itex].

    for (2) whatever the larger is, the constraint makes no sense because 6 > 3, so the problem is infeasible. If 'max' were changed to 'min' then the constraint is nothing but [itex]2x_1+x_2 \leq 3[/itex].
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Post-optimality analysis: Change in one of the constraints
  1. Changed post (Replies: 12)

Loading...