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 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!

 

[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$.