Post-optimality analysis: Change in one of the constraints

278 Views Asked by At

Consider the LP:

\begin{array}{rccc} \max& \quad -3x_1&-x_2& & \\ \text{s.t.}& \quad 2x_1&+x_2 &\leq 3 \\ & -x_1&+x_2 &\geq 1 \\ &&x_1,x_2 &\geq 0 \end{array}

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?

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!