Post-optimality analysis: Change in one of the constraints

[drawar]

Homework Statement

Consider the LP:

max \, -3x_1-x_2
\,\,s.t. \,\,\,\, 2x_1+x_2 \leq 3
\quad \quad \ -x_1+x_2 \geq 1
\quad \quad \quad \quad \ x_1,x_2 \geq 0Suppose 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 (2x_1+x_2 \leq 3) is either changed to

(1) max \, (2x_1+x_2,0) \leq 3, or
(2) max \, (2x_1+x_2,6)\leq 3,

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

Homework Equations

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!

 

[STEMucator]

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.

 

[drawar]

conditions (1) should read "the larger of (2x_1+x_2) and 0 is smaller than 3", that is, if 0 \leq 2x_1+x_2 then we also have 0 \leq 2x_1+x_2 \leq 3, otherwise, if 2x_1+x_2 \leq 0 then 2x_1+x_2 \leq 0.

 

[Ray Vickson]

Homework Statement

Consider the LP:

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


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 (2x_1+x_2 \leq 3) is either changed to

(1) max \, (2x_1+x_2,0) \leq 3, or
(2) max \, (2x_1+x_2,6)\leq 3,

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

Homework Equations

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!

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?)

 

[STEMucator]

conditions (1) should read "the larger of (2x_1+x_2) and 0 is smaller than 3", that is, if 0 \leq 2x_1+x_2 then we also have 0 \leq 2x_1+x_2 \leq 3, otherwise, if 2x_1+x_2 \leq 0 then 2x_1+x_2 \leq 0.

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

You simply can't use the second condition.

 

[drawar]

Thank you all, I think I've got what you said,
for (1) since it was given that x_1,x_2 \geq 0, 2x_1+x_2 \geq 0 hence the constraint is equivalent to 2x_1+x_2 \leq 3.

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 2x_1+x_2 \leq 3.