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!

  • $\begingroup$ The constraint (1) $\max\{2x_1+x_2,0\} \leq 3$ is redundant since it's satisfied by the current optimal solution. $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Dec 5 '15 at 16:56
  • $\begingroup$ The constraint (2) $\max\{2x_1+x_2,6\} \leq 3$ is meaningless because $\max\{2x_1+x_2,6\} \geq 6 > 3$, so the feasible region will become empty. $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Dec 5 '15 at 17:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.