# Post-optimality analysis: Change in one of the constraints

1. Apr 28, 2014

### drawar

1. The problem statement, all variables and given/known data

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?

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. Apr 28, 2014

### Zondrina

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.

3. Apr 28, 2014

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

4. Apr 28, 2014

### Ray Vickson

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

5. Apr 28, 2014

### Zondrina

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

You simply can't use the second condition.

6. Apr 28, 2014

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