Learning Outcomes

• Understand what happens to the optimal solution as we slightly vary the parameters

• Calculate the range of parameters where the optimal solution (or optimal basis) remains optimal.

• Understand the change of objective function value as parameters are changed.

Try it out visually!

Three kinds of data appear in a linear program: the objective coefficients $c$, the right-hand sides $b$, and the constraint matrix $A$. Before computing exact ranges, it is worth understanding qualitatively how each one enters the final dictionary.

The objective row of the revised dictionary is

where the coefficients of $x_N$, namely $c_N^{\top }-c_B^{\top }{A}_B^{-1}{A}_N$, are the reduced costs. A change in $c_i$ lands in one of two places. If $i$ is a basic variable, then $c_i$ sits inside $c_B$, so it moves the constant term $c_B^{\top }{A}_B^{-1}b$: the optimal value changes linearly in $c_i$ for as long as the basis stays optimal. If $i$ is a nonbasic variable, then $c_i$ appears only in its own reduced cost: the current solution and objective value do not move at all until the change is large enough to flip the sign of that reduced cost, at which point variable $i$ wants to enter the basis and the current dictionary is no longer optimal.

The basic solution is $x_B=A_B^{-1}b$, so a change in $b$ moves the basic variables directly. Small changes rescale $x_B$ while keeping it nonnegative, and the objective value $z^{\ast }=c_B^{\top }{A}_B^{-1}b$ moves linearly along with it. A large enough change drives some basic variable negative: the dictionary becomes infeasible, and restoring feasibility requires a pivot to a different basis (or reveals that the problem has become infeasible altogether).

Geometrically, changing $a_{ij}$ tilts the corresponding constraint, reshaping the feasible region. Algebraically, the effect depends on which column is touched. If column $j$ is nonbasic, then $A_B^{-1}$ is untouched; only the reduced cost of variable $j$ changes, and the current solution survives unless that reduced cost changes sign. If column $j$ is basic, the change alters $A_B$ itself, and since the entire dictionary is built from $A_B^{-1}$, even a small change can move the basic solution, every reduced cost, and the optimal value all at once.

In the remainder of the chapter we make these statements quantitative for the running example: for each parameter we compute the exact range of values over which the current basis $B=\{x,y,s_2\}$ remains optimal, and how $z$ moves inside that range. We treat the right-hand sides first, then the objective coefficients, then redo both computations in matrix notation.

In standard form, a linear program is written as $Ax=b,x\ge 0$. We perturb one entry of $b$ at a time, holding the objective coefficients and constraint matrix fixed, and answer three questions:

1.

For which changes in the RHS does the current basis remain optimal?

2.

How does the optimal solution vary with these changes?

3.

How does the objective value change?

Each case follows the same three moves: perturb the standard form, adapt the final dictionary, and read off the range.

The second constraint (corresponding to slack variable $s_2$) originally has RHS value $b_2=16$. We now perturb this to $16+\mathrm{\Delta }$, where $\mathrm{\Delta }\in ℝ$, and investigate the effect.

Perturbed Standard Form (RHS of Constraint 2)

To isolate the effect of $\mathrm{\Delta }$, define a new variable:

Substituting into the system yields:

➤ Adapt the final dictionary.  Since the structure of the problem remains the same in terms of the new variable $s_2^{\prime }$, we can substitute into the final dictionary:

$$\begin{array}{ccc}\hfill \max & z=23-s_1-s_3\hfill & \hfill \\ \hfill \text{ s.t. }& x=4-2s_1+s_3\hfill \\ \hfill & y=5+s_1-s_3\hfill \\ \hfill & s_2^{\prime }=3+3s_1-s_3\Rightarrow s_2-\mathrm{\Delta }=3+3s_1-s_3\hfill \\ \hfill & x,y,s_1,s_2^{\prime },s_3\ge 0\hfill \end{array}$$

Only the row of $s_2$ is affected: $s_2=(3+\mathrm{\Delta })+3s_1-s_3$.

➤ Read off the range.  To remain optimal, the dictionary must still satisfy feasibility: all basic variables must remain nonnegative when $s_1=s_3=0$. Only $s_2$ depends on $\mathrm{\Delta }$, so:

$$s_2=3+\mathrm{\Delta }\ge 0\iff \mathrm{\Delta }\ge -3\iff b_2\ge 13.$$

Since $s_2$ is a slack variable, the objective value $z=23$ does not move at all inside this range. Beyond it, $s_2<0$ and the current dictionary becomes infeasible, triggering a new pivot in the simplex method.

The first constraint corresponds to slack variable $s_1$, which is currently nonbasic and set to 0 in the optimal solution. Its original right-hand side is $b_1=9$. We now perturb it to $9+\mathrm{\Delta }$, where $\mathrm{\Delta }\in ℝ$, and examine how this affects the dictionary.

Perturbed Standard Form (RHS of Constraint 1)

To isolate the effect of $\mathrm{\Delta }$, define a new variable:

Substituting into the system yields:

So the perturbed system is equivalent to the original, but now expressed in terms of $s_1^{\prime }$.

➤ Adapt the final dictionary.  We substitute $s_1=s_1^{\prime }-\mathrm{\Delta }$ into the optimal dictionary:

$$\begin{array}{ccc}\hfill \max z& =23-s_1-s_3=23-(s_1^{\prime }-\mathrm{\Delta })-s_3=(23+\mathrm{\Delta })-s_1^{\prime }-s_3\hfill & \hfill \\ \hfill x& =4-2s_1+s_3=4-2(s_1^{\prime }-\mathrm{\Delta })+s_3=(4+2\mathrm{\Delta })-2s_1^{\prime }+s_3\hfill \\ \hfill y& =5+s_1-s_3=5+(s_1^{\prime }-\mathrm{\Delta })-s_3=(5-\mathrm{\Delta })+s_1^{\prime }-s_3\hfill \\ \hfill s_2& =3+3s_1-s_3=3+3(s_1^{\prime }-\mathrm{\Delta })-s_3=(3-3\mathrm{\Delta })+3s_1^{\prime }-s_3\hfill \end{array}$$

➤ Read off the range.  To ensure the basis remains feasible, set $s_1^{\prime }=s_3=0$ and check that the basic variables remain nonnegative:

$$x=4+2\mathrm{\Delta },y=5-\mathrm{\Delta },s_2=3-3\mathrm{\Delta }.$$

Feasibility conditions:

$$\begin{array}{ccc}\hfill x\ge 0& \Rightarrow \mathrm{\Delta }\ge -2\hfill & \hfill \\ \hfill y\ge 0& \Rightarrow \mathrm{\Delta }\le 5\hfill \\ \hfill s_2\ge 0& \Rightarrow \mathrm{\Delta }\le 1\hfill \end{array}$$

Thus, all conditions are satisfied when:

$$-2\le \mathrm{\Delta }\le 1\iff 7\le b_1\le 10.$$

Within this range, the objective value changes linearly as $z=23+\mathrm{\Delta }$. Outside this range, one or more basic variables becomes negative, and the current solution becomes infeasible, prompting a new pivot in the simplex method.

The third constraint corresponds to slack variable $s_3$, which is currently nonbasic and equal to 0 in the optimal solution. Its original right-hand side is $b_3=14$. We now perturb it to $14+\mathrm{\Delta }$, where $\mathrm{\Delta }\in ℝ$, and examine how this affects the dictionary.

Perturbed Standard Form (RHS of Constraint 3)

To isolate the effect of $\mathrm{\Delta }$, define a new variable:

Substituting into the system yields:

So the perturbed system returns to the original structure but in terms of $s_3^{\prime }$.

➤ Adapt the final dictionary.  Substitute $s_3=s_3^{\prime }-\mathrm{\Delta }$ into the optimal dictionary:

$$\begin{array}{ccc}\hfill \max z& =23-s_1-s_3=23-s_1-(s_3^{\prime }-\mathrm{\Delta })=(23+\mathrm{\Delta })-s_1-s_3^{\prime }\hfill & \hfill \\ \hfill x& =4-2s_1+s_3=4-2s_1+(s_3^{\prime }-\mathrm{\Delta })=(4-\mathrm{\Delta })-2s_1+s_3^{\prime }\hfill \\ \hfill y& =5+s_1-s_3=5+s_1-(s_3^{\prime }-\mathrm{\Delta })=(5+\mathrm{\Delta })+s_1-s_3^{\prime }\hfill \\ \hfill s_2& =3+3s_1-s_3=3+3s_1-(s_3^{\prime }-\mathrm{\Delta })=(3+\mathrm{\Delta })+3s_1-s_3^{\prime }\hfill \end{array}$$

➤ Read off the range.  Now test feasibility at the basic solution $s_1=s_3^{\prime }=0$:

$$x=4-\mathrm{\Delta },y=5+\mathrm{\Delta },s_2=3+\mathrm{\Delta }.$$

Feasibility requires:

$$\begin{array}{ccc}\hfill x\ge 0& \Rightarrow \mathrm{\Delta }\le 4\hfill & \hfill \\ \hfill s_2\ge 0& \Rightarrow \mathrm{\Delta }\ge -3\hfill \end{array}$$

Thus, the allowable range for $\mathrm{\Delta }$ is:

$$-3\le \mathrm{\Delta }\le 4\iff 11\le b_3\le 18.$$

Within this range, the objective value changes linearly as $z=23+\mathrm{\Delta }$. Outside this range, $x<0$ or $s_2<0$, and the dictionary becomes infeasible.

Recipe: RHS Ranging in the Dictionary

➤ Perturb Replace $b_i$ by $b_i+\mathrm{\Delta }$ and absorb $\mathrm{\Delta }$ into the constraint’s slack variable: $s_i^{\prime }=s_i+\mathrm{\Delta }$ restores the original right-hand side.

➤ Substitute Rewrite the optimal dictionary in terms of $s_i^{\prime }$; only the constant column changes, each constant shifting by a multiple of $\mathrm{\Delta }$.

➤ Impose feasibility Require every basic variable $\ge 0$ at $x_N=0$; each row gives one linear inequality in $\mathrm{\Delta }$.

✔ Read the range Intersect the inequalities. Inside the range, $z$ changes linearly in $\mathrm{\Delta }$; at an endpoint a basic variable hits $0$, and any further change triggers a pivot.

Learning Checkpoint 10.2.1

The optimal dictionary gives $z=23+\mathrm{\Delta }$ when $b_1=9+\mathrm{\Delta }$. What is the shadow price of constraint 1, and over what range of $b_1$ is that price valid? What happens to the shadow price at $b_1=10$?

We now examine how changes to the objective function coefficients affect the optimality of the current basis. In the original problem, the objective is:

We now perturb these coefficients to:

where ${\delta }_1,{\delta }_2\in ℝ$. Recall the final dictionary:

with basis $B=\{x,y,s_2\}$ and nonbasic variables $N=\{s_1,s_3\}$. Unlike an RHS change, a cost change never threatens feasibility (the solution stays where it is), but it can destroy optimality by making a reduced cost positive.

➤ Adapt the final dictionary.  Let $c_1=2+{\delta }_1$. Since $x$ is basic, we express the extra term ${\delta }_{1}x$ in terms of the nonbasic variables using the dictionary row for $x$:

$$z=23+{\delta }_1\cdot x=23+{\delta }_1(4-2s_1+s_3)=(23+4{\delta }_1)+(-2{\delta }_1)s_1+{\delta }_1{s}_3.$$

Adding to the original dictionary $z=23-s_1-s_3$, we obtain:

$$z=(23+4{\delta }_1)+(-1-2{\delta }_1)s_1+(-1+{\delta }_1)s_3.$$

➤ Read off the range.  To maintain optimality, the reduced costs of nonbasic variables $s_1$ and $s_3$ must remain $\le 0$. Thus:

$$\begin{array}{ccc}\hfill -1-2{\delta }_1& \le 0\Rightarrow {\delta }_1\ge -\frac{1}{2},\hfill & \hfill \\ \hfill -1+{\delta }_1& \le 0\Rightarrow {\delta }_1\le 1.\hfill \end{array}$$

So the allowable range for ${\delta }_1$ is:

$$-\frac{1}{2}\le {\delta }_1\le 1\iff 1.5\le c_1\le 3.$$

Within this range, the objective value changes linearly as $z=23+4{\delta }_1$.

➤ Adapt the final dictionary.  Let $c_2=3+{\delta }_2$. Since $y$ is also basic, the perturbed objective becomes:

$$z=23+{\delta }_2\cdot y=23+{\delta }_2(5+s_1-s_3)=(23+5{\delta }_2)+{\delta }_2{s}_1-{\delta }_2{s}_3.$$

Adding to the original dictionary $z=23-s_1-s_3$, we obtain:

$$z=(23+5{\delta }_2)+(-1+{\delta }_2)s_1+(-1-{\delta }_2)s_3.$$

➤ Read off the range.  To maintain optimality:

$$\begin{array}{ccc}\hfill -1+{\delta }_2& \le 0\Rightarrow {\delta }_2\le 1,\hfill & \hfill \\ \hfill -1-{\delta }_2& \le 0\Rightarrow {\delta }_2\ge -1.\hfill \end{array}$$

So the allowable range for ${\delta }_2$ is:

$$-1\le {\delta }_2\le 1\iff 2\le c_2\le 4.$$

Within this range, the objective value changes linearly as $z=23+5{\delta }_2$.

Outside these ranges, the reduced costs of nonbasic variables become positive, violating optimality. In such cases, the simplex method would require a new pivot.

Recipe: Objective-Coefficient Ranging in the Dictionary

➤ Perturb Replace $c_i$ by $c_i+\delta$. If variable $i$ is nonbasic, only its own reduced cost shifts by $\delta$; skip to the last step.

➤ Substitute If variable $i$ is basic, express the extra term $\delta x_i$ in terms of the nonbasic variables using the dictionary row for $x_i$, and add it to the objective row.

➤ Impose optimality Require every reduced cost $\le 0$ (for a maximization problem); each nonbasic variable gives one linear inequality in $\delta$.

Learning Checkpoint 10.3.1

Changing the objective coefficient of a nonbasic variable never changes the current optimal solution, but changing it enough can still change the optimal basis. Reconcile these two statements.

The dictionary manipulations above can be organized with matrices, which is how software carries them out. Writing the running example in standard form,

Let the basic variables be $x_B=\left[\begin{array}{c}\hfill x\hfill \\ \hfill y\hfill \\ \hfill s_2\hfill \end{array}\right]$, and the non-basic variables be $x_N=\left[\begin{array}{c}\hfill s_1\hfill \\ \hfill s_3\hfill \end{array}\right]$. Then the dictionary can be written as:

$$x_B=b^{\prime }-A_N^{\prime }{x}_N,$$

where:

$$b^{\prime }=\left[\begin{array}{c}\hfill 4\hfill \\ \hfill 5\hfill \\ \hfill 3\hfill \end{array}\right],A_N^{\prime }=\left[\begin{array}{cc}\hfill -2\hfill & \hfill 1\hfill \\ \hfill 1\hfill & \hfill -1\hfill \\ \hfill 3\hfill & \hfill -1\hfill \end{array}\right].$$

Thus, explicitly:

$$\left[\begin{array}{c}\hfill x\hfill \\ \hfill y\hfill \\ \hfill s_2\hfill \end{array}\right]=\left[\begin{array}{c}\hfill 4\hfill \\ \hfill 5\hfill \\ \hfill 3\hfill \end{array}\right]-\left[\begin{array}{cc}\hfill -2\hfill & \hfill 1\hfill \\ \hfill 1\hfill & \hfill -1\hfill \\ \hfill 3\hfill & \hfill -1\hfill \end{array}\right]\left[\begin{array}{c}\hfill s_1\hfill \\ \hfill s_3\hfill \end{array}\right].$$

or equivalently

$$\left[\begin{array}{c}\hfill x\hfill \\ \hfill y\hfill \\ \hfill s_2\hfill \end{array}\right]=\left[\begin{array}{c}\hfill 4\hfill \\ \hfill 5\hfill \\ \hfill 3\hfill \end{array}\right]+s_1\left[\begin{array}{c}\hfill 2\hfill \\ \hfill -1\hfill \\ \hfill -3\hfill \end{array}\right]+s_3\left[\begin{array}{c}\hfill -1\hfill \\ \hfill 1\hfill \\ \hfill 1\hfill \end{array}\right].$$

The basis matrix is

We modify the right-hand side of the first constraint and analyze its impact on feasibility:

Step 1 — Update the basic solution.  Using the inverse basis matrix $A_B^{-1}$, the basic solution is $x_B=A_B^{-1}b$:

$$A_B^{-1}b=\left[\begin{array}{ccc}\hfill 2\hfill & \hfill 0\hfill & \hfill -1\hfill \\ \hfill -1\hfill & \hfill 0\hfill & \hfill 1\hfill \\ \hfill -3\hfill & \hfill 1\hfill & \hfill 1\hfill \end{array}\right]\left[\begin{array}{c}\hfill b_1\hfill \\ \hfill 16\hfill \\ \hfill 14\hfill \end{array}\right]=\left[\begin{array}{c}\hfill 2b_1-14\hfill \\ \hfill -b_1+14\hfill \\ \hfill -3b_1+30\hfill \end{array}\right].$$

Step 2 — Impose feasibility.  Ensuring that all basic variables remain non-negative:

$$\left[\begin{array}{c}\hfill 2b_1-14\hfill \\ \hfill -b_1+14\hfill \\ \hfill -3b_1+30\hfill \end{array}\right]\ge \left[\begin{array}{c}\hfill 0\hfill \\ \hfill 0\hfill \\ \hfill 0\hfill \end{array}\right]\iff \left[\begin{array}{c}\hfill b_1\hfill \\ \hfill 14\hfill \\ \hfill 10\hfill \end{array}\right]\ge \left[\begin{array}{c}\hfill 7\hfill \\ \hfill b_1\hfill \\ \hfill b_1\hfill \end{array}\right].$$

To determine the range of values for $c_x$ (the coefficient of $x$ in the objective function) such that the current basis remains optimal, we analyze the simplex optimality conditions.

Step 1 — Set up the reduced costs.  The objective function is initially:

$$z=2x+3y.$$

The cost vector for all variables is:

$$c=\left[\begin{array}{c}\hfill c_x\hfill \\ \hfill 3\hfill \\ \hfill 0\hfill \\ \hfill 0\hfill \\ \hfill 0\hfill \end{array}\right].$$

The cost vector corresponding to the basic variables $x,y,s_2$ (i.e., the basis) is:

$$c_B=\left[\begin{array}{ccc}\hfill c_x\hfill & \hfill 3\hfill & \hfill 0\hfill \end{array}\right].$$

The reduced cost for any non-basic variable $j$ is given by:

$${\overline{c}}_j=c_j-c_B{A}_B^{-1}{A}_j.$$

The non-basic variables are $s_1$ and $s_3$. We need to ensure that their reduced costs remain non-positive.

Step 2 — Compute the reduced costs for $s_1$ and $s_3$.  The constraint matrix is:

$$A=\left[\begin{array}{ccccc}\hfill 1\hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 2\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill \\ \hfill 1\hfill & \hfill 2\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill \end{array}\right].$$

Extracting the columns corresponding to $s_1$ and $s_3$:

$$A_{s_1}=\left[\begin{array}{c}\hfill 1\hfill \\ \hfill 0\hfill \\ \hfill 0\hfill \end{array}\right],A_{s_3}=\left[\begin{array}{c}\hfill 0\hfill \\ \hfill 0\hfill \\ \hfill 1\hfill \end{array}\right].$$

Using the inverse basis matrix:

$$A_B^{-1}{A}_{s_1}=\left[\begin{array}{ccc}\hfill 2\hfill & \hfill 0\hfill & \hfill -1\hfill \\ \hfill -1\hfill & \hfill 0\hfill & \hfill 1\hfill \\ \hfill -3\hfill & \hfill 1\hfill & \hfill 1\hfill \end{array}\right]\left[\begin{array}{c}\hfill 1\hfill \\ \hfill 0\hfill \\ \hfill 0\hfill \end{array}\right]=\left[\begin{array}{c}\hfill 2\hfill \\ \hfill -1\hfill \\ \hfill -3\hfill \end{array}\right].$$

$$A_B^{-1}{A}_{s_3}=\left[\begin{array}{ccc}\hfill 2\hfill & \hfill 0\hfill & \hfill -1\hfill \\ \hfill -1\hfill & \hfill 0\hfill & \hfill 1\hfill \\ \hfill -3\hfill & \hfill 1\hfill & \hfill 1\hfill \end{array}\right]\left[\begin{array}{c}\hfill 0\hfill \\ \hfill 0\hfill \\ \hfill 1\hfill \end{array}\right]=\left[\begin{array}{c}\hfill -1\hfill \\ \hfill 1\hfill \\ \hfill 1\hfill \end{array}\right].$$

Thus, the reduced costs are:

$${\overline{c}}_{s_1}=0-\left[\begin{array}{ccc}\hfill c_x\hfill & \hfill 3\hfill & \hfill 0\hfill \end{array}\right]\cdot \left[\begin{array}{c}\hfill 2\hfill \\ \hfill -1\hfill \\ \hfill -3\hfill \end{array}\right]=0-(2c_x-3).$$

$${\overline{c}}_{s_3}=0-\left[\begin{array}{ccc}\hfill c_x\hfill & \hfill 3\hfill & \hfill 0\hfill \end{array}\right]\cdot \left[\begin{array}{c}\hfill -1\hfill \\ \hfill 1\hfill \\ \hfill 1\hfill \end{array}\right]=0-(-c_x+3).$$

When solving a problem in Excel, you can ask for a sensitivity analysis.

This will generate a report that will show the following:

• Allowable Increase/Decrease: For each decision variable’s coefficient in the objective function, the report provides the range (allowable increase and allowable decrease) within which the coefficient can change without altering the current optimal basis. This range indicates the stability of the optimal solution with respect to changes in that coefficient.

• Right-Hand Side (RHS) Values: For each constraint, the sensitivity report lists the shadow price (or dual value), which represents the rate of change in the objective function per unit increase in the RHS of that constraint. It also provides the allowable increase and allowable decrease for the RHS. These values indicate how robust the constraints are; small allowable changes might imply that the solution is sensitive to fluctuations in available resources or demand levels.

• Constraint Status: The report shows which constraints are binding (active) and which are non-binding. A binding constraint has a positive shadow price and restricts the optimal solution, while a non-binding constraint has a shadow price of zero.

Exercise 10.1: Shadow Prices from the Final Dictionary

$\star$  Recall the final dictionary of the running example of this chapter:

1.

Read off the shadow price of each of the three constraints (hours, flour, sugar) directly from the objective row.

2.

Which constraint is not binding at the optimum? How can you see this in the dictionary, and how is it reflected in that constraint’s shadow price?

3.

The bakery is offered one extra unit of sugar for $0.75. Should it accept? What is the most it should pay?

Exercise 10.2: RHS Sensitivity Range

$\star$  Consider the following linear program and its optimal dictionary:

The optimal dictionary is:

with basis $B=\{x_1,x_2\}$ and nonbasic variables $N=\{s_1,s_2\}$.

Determine the range of values for $b_1$ (the RHS of the first constraint) for which the current basis remains optimal.

Exercise 10.3: Objective Coefficient Sensitivity

Exercise 10.4: Full Sensitivity Workup

$\star \star$  A shop assembles two products with profits $5 and $6 per unit:

1.

Solve the LP (graphically or by the simplex method) and report the optimal solution and objective value.

2.

Compute the shadow price of each constraint.

3.

Find the allowable range of $b_1$ and of $b_2$ over which the current basis remains optimal, and state how $z$ changes inside each range.

4.

Find the allowable range of $c_1$ and of $c_2$ over which the current basis remains optimal.

5.

Check your answers with software (for example scipy.optimize.linprog or Excel Solver).

Exercise 10.5: Ranging a Basic and a Nonbasic Coefficient

$\star \star$  Consider the LP

whose optimal solution is $(x_1,x_2)=(5,0)$ with $z^{\ast }=25$ and basis $B=\{x_1,s_2\}$.

1.

Verify that $(5,0)$ is optimal by computing the reduced costs of the nonbasic variables $x_2$ and $s_1$.

2.

Find the range of the coefficient $c_2$ of the nonbasic variable $x_2$ for which the current basis remains optimal. How does $z^{\ast }$ change as $c_2$ moves inside this range?

3.

Find the range of the coefficient $c_1$ of the basic variable $x_1$ for which the current basis remains optimal. How does $z^{\ast }$ change inside this range?

4.

Explain the structural difference between the two cases: why does one range have a single finite endpoint driven by one reduced cost, while the other involves every reduced cost?

Exercise 10.6: Sensitivity from the Basis Inverse

$\star \star$  Consider the LP:

The optimal basis is $B=\{x_1,x_2\}$ with basis matrix and its inverse:

1.

Compute $x_B=A_B^{-1}b$ and verify this gives a feasible basic solution.

2.

For the RHS vector $b=\left[\begin{array}{c}\hfill 6\hfill \\ \hfill 15\hfill \end{array}\right]$, find the range of $b_1$ for which the current basis remains feasible.

3.

Compute the reduced costs of the nonbasic variables. For what range of $c_1$ does the current basis remain optimal?

Exercise 10.7: Reading a Sensitivity Report

$\star \star$  The following is a sensitivity report from Excel Solver for a maximization LP with two decision variables $x_1$ and $x_2$ and three constraints:

1.

What is the current optimal objective value?

2.

If the objective coefficient of $x_1$ changes from 6 to 7.5, does the optimal basis change?

3.

Which constraint is non-binding? How can you tell from the report?

4.

If 2 additional units of the first resource become available (RHS increases from 20 to 22), what is the new approximate optimal objective value?

Exercise 10.8: Shadow Price Interpretation

$\star \star$  A furniture workshop produces tables and chairs. The linear program is:

The optimal solution is $x_1=7.5$, $x_2=5$, with optimal profit $z^{\ast }=525$. The dual solution is $y_1=11.25$, $y_2=2.50$.

1.

Interpret each shadow price in terms of the resources (wood and labor).

2.

If the workshop could acquire 2 additional board-feet of wood, by approximately how much would the optimal profit increase?

3.

Which resource is more valuable at the margin? Explain.

Exercise 10.9: Why a Slack Constraint Has Price Zero

$\star \star$  Explain, in your own words, why a constraint that is not binding at the optimal solution must have shadow price $0$. Give two arguments:

Exercise 10.10: Why Ranges Exist at All

$\star \star$  Every quantity in a sensitivity report comes with an allowable range. Explain why.

1.

What single object stays fixed throughout a sensitivity computation, and what two kinds of conditions (one for RHS changes, one for cost changes) must it continue to satisfy?

2.

Why is the effect of a data change on $z^{\ast }$ linear inside the range?

3.

What happens, in terms of the simplex method, the moment a perturbation crosses an endpoint of its range?

Exercise 10.11: When the Shadow Price Prediction Breaks

$\star \star$  Consider the LP

whose optimal solution is $(1,1)$ with $z^{\ast }=2$. Note that all three constraints are tight there, but only two of them are needed to define the vertex: the optimal solution is degenerate.

1.

Show that increasing $b_3$ from $2$ to $3$ does not change $z^{\ast }$, while decreasing $b_3$ from $2$ to $1$ decreases $z^{\ast }$ by $1$.

2.

What, then, is “the” shadow price of the third constraint? Explain informally why a single number cannot describe both directions here.

3.

Why should you be cautious when reading the shadow price of a degenerate LP from a solver report?

Exercise 10.12: Pushing Past the Range

$\star \star \star$  Construct a linear program with a constraint whose shadow price is some $p>0$ such that increasing the right-hand side of that constraint by $1$ increases the optimal value by exactly $p$, but increasing it by $5$ increases the optimal value by strictly less than $5p$. Explain what happens at the boundary of the allowable range that makes the prediction fail, and verify your construction by solving the perturbed LPs. (Hint: the running example of this chapter already contains such a constraint.)

Solution