How to add a constraint to the final phase of simplex tableau?

Question

How does one go about adding a new constraint in the final phase of the simplex tableau?

In the case where our optimal solution satisfies the constraint, we can conclude that the optimal solution stays the same.

But what if the constraint is not satisfied? Do we have to start over again?

Answer 1

If the previously optimal basic feasible solution violates the new constraint, then the basis (adjusted to include a basic variable in the new constraint) is "superoptimal" (at least as good as, and possible better, than optimal) but infeasible. In that case, you can use the dual simplex algorithm. Whereas the primal simplex algorithm starts with a feasible basis and works toward optimality while maintaining feasibility, the dual simplex algorithm starts with a superoptimal but infeasible basis and works toward feasibility while maintaining superoptimality. Most (all?) text books that discuss the simplex method also discuss the dual simplex method. Dual simplex is the most common way that solvers handle cuts being added to an LP tableau.

Answer 2

In order to add a new constraint into the optimal Simplex Tableau, we'll need to do two things to the tableau:

• Add a new row
• Add a new slack column

In addition, we'll have a new $B^{-1}$ under the slack columns from the addition of the new slack variable, thus we'll have to recalculate the Reduced Cost of all the non-basic variables, and recalculate all the $\bar{A}_j$ (their columns) of each non-basic variable (which is calculated from $B^{-1}A_j$ where $A_j$ is the column of the variable $j$ in which it appeared in the original constraints of the model). From here, if the tableau is violated in some way that's irrecoverable, then the addition of the new constraint made the model infeasible.

Two things to keep in mind about adding new constraints in terms of the Objective Solution:

• It can make the existing solution worse, as adding a new constraint could cut off a section of the feasible region.
• It'll leave the existing solution alone as the new constraint was redundant and did nothing for the model.

Under no circumstance does adding a new constraint makes the model better in terms of increasing the objective function output (maximization) or reducing it (minimization), as at best it'll do nothing to the existing model, and at worst it cuts off more of the feasible region.