1
$\begingroup$

I'm studying linear optimization from Hillier's book and it teach us how to perform sensitivity analysis regarding several changes in respect to the initial problem. One of these changes are adding a new constraint or variable. However, I didnt find any reference teaching how to proceed if one wants to remove one decision variable from the initial problem or remove one constraint.

I think that if the decision variable is non-basic in the previous optimal solution, then you can remove it without changing anything. But what if the decision variable is basic??

Similarly, if the constraint is unactive, I think you can remove it just fine, but what if it's active?

I appreciate any reference and guidances about this problem.

$\endgroup$

2 Answers 2

1
$\begingroup$

To remove a variable that is basic, I multiply $-1$ to the simplex row that corresponds to that variable.

This will make the current solution dual feasible but primal infeasible.

We then proceed to perform dual simplex to drive out the variable that you want to remove to make it nonbasic.

$\endgroup$
4
  • $\begingroup$ I didnt understand the ''removing a constraint''' part, could you explain better, please? $\endgroup$ Oct 9, 2016 at 19:27
  • 1
    $\begingroup$ I just realized what I wrote doesn't make sense too. Back to thinking... $\endgroup$ Oct 9, 2016 at 19:40
  • $\begingroup$ Hello, sorry for bothering you again, but I have a test tomorrow at 10 am (now is 10:30 pm) and I have one more question here, math.stackexchange.com/questions/1961583/… Please, help me.. $\endgroup$ Oct 10, 2016 at 1:29
  • $\begingroup$ answered based on muscle memory, hopefully it makes sense. Good luck. $\endgroup$ Oct 10, 2016 at 6:32
0
$\begingroup$

You can simulate removing constraints and variables by adding them in specific ways.

  • Removing a constraint is the same as adding a free variable to only that constraint, which in practice means two new variables: $$\cdots=b\to\cdots+x_0^+-x_0^-=b$$ If the associated reduced costs indicate non-optimality, perform primal simplex iterations.
  • Removing a nonbasic variable, as you said, is as simple as removing it from the optimal solution.
  • To remove a basic variable $x_i$, for every constraint that features it: $$\cdots+a_{ji}x_i+\cdots=b_j$$ add a new variable $x_0$ with a negated coefficient: $$\cdots+a_{ji}x_i+\cdots-a_{ji}x_0=b_j$$ Then add a new constraint $x_i-x_0=0$ with associated variable $x_0$, performing row operations on it to get back an identity matrix. If the solution for $x_0$ is negative, perform dual simplex iterations to reach the new optimal solution.
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.