Sensitivity Analysis

Sensitivity analysis studies how the optimal solution reacts to changes in the LP data, without solving the LP again from the start.

Current Cost

The current cost $c_j$ of a variable $x_j$ is its coefficient in the original objective function, before any pivoting.

• Slack and surplus variables
  Cost 0 always, since they track unused capacity or excess, not a produced quantity. $x_1 \le 4$ becomes $x_1 + s_1 = 4$, and $c_{s_1} = 0$.
• Artificial variables
  Added only to satisfy a $\ge$ or $=$ constraint, and carry a penalty cost so the simplex method drives them out of the basis. $x_1 + x_2 \ge 4$ becomes $x_1 + x_2 - s_1 + a_1 = 4$, with $c_{a_1} = -M$ in the Big-M method for a maximization problem, or $c_{a_1} = 1$ in phase 1 of the two-phase method.

Reduced Cost

The reduced cost of a variable $x_j$ is its entry in the objective row of the current tableau. It is the amount $z$ would change per unit of $x_j$ brought into the basis.

A basic variable always has reduced cost 0 in its own column. Only non-basic variables have a reduced cost worth tracking.

Shadow Price

The shadow price of constraint $i$ is $s_i$‘s own entry in the objective row, the amount $z$ changes per unit increase in $b_i$.

Example

Take the LP solved in the simplex worked example:

Converting to standard form adds a slack $s_1, s_2, s_3$ to each constraint, one per row, with cost 0 in the objective, since a slack represents unused capacity rather than a produced quantity: $z = 3x_1 + 5x_2 + 0s_1 + 0s_2 + 0s_3$.

Its optimal tableau has basis $(s_1, x_2, x_1)$, solution $x_1 = 2$, $x_2 = 6$, $z = 36$:

The current costs are $c_1 = 3$, $c_2 = 5$, and $c_{s_1} = c_{s_2} = c_{s_3} = 0$, read straight off the objective function above. The reduced costs are the objective row of the tableau: 0 for the basic variables ($s_1, x_2, x_1$) and $3/2$ for $s_2$ and $1$ for $s_3$.

Every case below reuses this tableau. A change to the LP keeps the basis $(s_1, x_2, x_1)$ optimal as long as 2 conditions still hold:

• Feasibility
  Every basic variable’s value in the RHS column stays $\ge 0$.
• Optimality
  Every reduced cost, the objective row entry of every non-basic variable, stays $\ge 0$.

$s_2$ and $s_3$ already satisfy optimality ($3/2 \ge 0$ and $1 \ge 0$), and all 3 basic values already satisfy feasibility ($2, 6, 2 \ge 0$). If a change breaks either condition, the tableau is repaired with primal or dual simplex instead of restarting.

Change in the Right Hand Side

Changing constraint $i$‘s RHS $b_i$ by $\Delta$ shifts every basic variable’s value by $\Delta$ times that variable’s entry in $s_i$‘s column of the tableau. $s_i$’s column is the right thing to use here because $s_i$ started as the only variable with a coefficient in row $i$, before any pivoting.

Underutilized Constraint

Constraint 1 is $x_1 \le 4$. Its slack $s_1$ is basic at value 2, so constraint 1 has 2 units of unused capacity.

$s_1$’s column is $(1, 0, 0)$ for rows $s_1, x_2, x_1$. Only the $s_1$ row has a non-zero entry there, so only $s_1$ moves when $b_1$ changes by $\Delta$:

$x_1$ and $x_2$ do not move, because constraint 1 was not binding to begin with. Feasibility only fails once the spare capacity runs out, at $\Delta = -2$:

There is no upper bound, since only the $s_1$ row changes. So $b_1$, originally 4, can range over $[2, \infty)$ without disturbing $x_1 = 2$, $x_2 = 6$, or $z = 36$. Drag $\Delta$ below $-2$ to see the basis break down:

The objective moves by $s_1$‘s own objective row entry, its shadow price, times $\Delta$. That entry is 0, confirming constraint 1 is non-binding: changing its unused capacity, within the range above, does not change $z$ at all.

Fully Utilized Constraint

Constraint 3 is $3x_1 + 2x_2 \le 18$. At $x_1 = 2$, $x_2 = 6$ it reads $3(2) + 2(6) = 18$, exactly the limit, so its slack $s_3$ is non-basic at 0 with no spare capacity to give.

$s_3$ has no row of its own in the tableau, since it is non-basic, but its column is still read straight off the tableau: $(-1/3, 0, 1/3)$ for rows $s_1, x_2, x_1$. Both $s_1$ and $x_1$ have non-zero entries there, so both move when $b_3$ changes by $\Delta$:

Unlike the underutilized case, $x_1$ itself moves this time, because constraint 3 was binding. Feasibility needs both altered rows to stay $\ge 0$:

So $b_3$, originally 18, can range over $[12, 24]$. Drag $\Delta$ past either edge to see the basis break down:

The objective moves by $s_3$‘s own objective row entry, its shadow price, times $\Delta$. That entry is 1, so $z$ changes 1-for-1 with $\Delta$ inside the range above, confirming constraint 3 is binding: its capacity is worth exactly 1 unit of $z$ per unit.

Change in a Cost Coefficient

Non-Basic Variable

$s_2$ is non-basic, with reduced cost $3/2$ and current cost $c_{s_2} = 0$, its coefficient in $z = 3x_1 + 5x_2 + 0s_1 + 0s_2 + 0s_3$.

Changing $c_{s_2}$ only changes $s_2$‘s own reduced cost, by the same amount in the opposite direction. If $c_{s_2}$ increases by $\Delta$, the reduced cost drops to $3/2 - \Delta$, needing

So $c_{s_2}$ can range over $(-\infty, 3/2]$ before $s_2$ becomes attractive enough to enter the basis. Drag $\Delta$ past $3/2$ to see the basis break down:

Basic Variable

$x_1$ is basic with $c_1 = 3$. $x_1$’s row runs through every column of the tableau, so changing $c_1$ changes every non-basic reduced cost, not just its own.

Set $c_1 = 3 + \Delta$. $x_1$’s row gives entry $-1/3$ under $s_2$ and $1/3$ under $s_3$, so each reduced cost changes by $\Delta$ times that entry:

Both together give $-3 \le \Delta \le 9/2$, so $c_1$ can range over $[0, 7.5]$.

On paper this is the row operation $z\text{-row} \leftarrow z\text{-row} + \Delta \cdot x_1\text{'s row}$: scale $x_1$‘s row by $\Delta$ and add it into the objective row, the same mechanical step a pivot uses. The highlighted row below is the one being scaled, the highlighted cells are where it lands. Drag $\Delta$ past either edge to see which reduced cost breaks first:

Addition of a Variable

Suppose a new activity $x_3$ becomes available, with cost $c_3 = 4$ and column $(1, 1, 1)$, one unit of each resource per unit produced.

Transform its column with the basis inverse read off the $s_1, s_2, s_3$ columns above:

Its reduced cost, using $c_B = (0, 5, 3)$ for the current basis $(s_1, x_2, x_1)$:

• Reduced cost $\ge 0$
  The current solution stays optimal. The new variable stays non-basic at value 0.
• Reduced cost $< 0$
  Optimality is violated, as it is here. $x_3$ can enter the basis and improve $z$ beyond 36.

Drag $c_{\text{new}}$ past $5/2$ to see the reduced cost flip sign:

Addition of a Constraint

Suppose a new limit $x_1 + x_2 \le k$ is imposed. The current optimum gives $x_1 + x_2 = 2 + 6 = 8$.

If current optimal solution satisfies the new constraint, the solution stays optimal.

Otherwise, the constraint is added to the optimal tableau with a slack, surplus, or artificial variable, and row-reduced against the current basis. The new basic variable gets a negative value, so the tableau is optimal but infeasible. Continue with the dual simplex method.

At $k = 5$, $8 > 5$ violates it, falling into the second case. Drag $k$ below 8 to see the constraint start to bind:

Continued with the dual simplex method in the dual simplex worked example, reaching the new optimum $x_1 = 0$, $x_2 = 5$, $z = 25$ for $k = 5$.