Sensitivity analysis: Removing one decision variable or constraint from the previous problem.

Question

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.

Answer 1

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.

Answer 2

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.