\section{Sensitivity Analysis}\label{S:Sensitivity}
\setcounter{progress_ck_counter}{0}

\noi Discussion of LPs thus far has focused primarily on solving them. Sensitivity analysis takes place after an LP has been solved and seeks to determine the extent to which changing model
parameters affects the solution.

\newpar
Recall the \LPC LP, given by
\begin{align}\label{E:Sensitivity_LP_long}
 \mbox{maximize } z &=4x_1+3x_2  \\
	\mbox{ subject to} \notag\\
	x_1 \phantom{ +20x_2} &\leq 8 \notag\\
	2x_1+2x_2 &\leq 28  \notag\\
	3x_1+2x_2 &\leq 32 \notag \\
	x_1,x_2 &\geq 0,\notag
	\end{align}

\noindent whose final tableau is provided in Table \ref{Ta:Sensitivity_LPC_final_tableau}.
	
\begin{table}[h]
\caption{\emph{FuelPro Petroleum Company} final tableau,
($\ds\BV=\left\{x_1,x_2,s_1 \right\}$)}\label{Ta:Sensitivity_LPC_final_tableau}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
$z$ & $x_1$ & $x_2$ & $s_1$ & $s_2$ & $s_3$ & RHS \\
\hline \hline
1 & 0 & 0 & 0 & $\frac{1}{2}$ & 1 & 46 \\ \hline
0 &  1 & 0 & 0 & -1 & 1 & 4 \\ \hline
0 &  0 & 0 & 1 & 1 & -1 & 4 \\ \hline
0 &  0 & 1 & 0 & $\frac{3}{2}$ & -1 & 10 \\ \hline
\end{tabular}
\end{table}

\newpar The feasible region and
the contour corresponding to the optimal solution $z=46$ are shown in Figure \ref{Fi:SensitivityLPC}.

\begin{figure}[h]
\centering
\includegraphics[width=.7\linewidth]{images/f05x02x01.eps}
\caption{Feasible region for \LP LP along with contour $z=46$.}\label{Fi:SensitivityLPC}
\end{figure}

\newpar
There are many ways in which the original LP can be modified. Examples include the introduction of an additional
variable, e.g.,  fuel type, a change in an objective coefficient, an increase or decrease in a
constraint bound, or a modification in the amount of particular stock required to produce a given
gallon of fuel type.

\newpar
There is an important initial observation to make before undertaking a study of sensitivity analysis. Changes in the model may preserve the set of basic variables in the solution yet change their actual values and, hence, possibly change the objective function value as well. For example, Figure \ref{Fi:SensitivityLPC} illustrates
how the second and third constraints of (\ref{E:Sensitivity_LP_long}) are binding at the optimal solution, $(x_1,x_2)=(4,10)$. Sufficiently small changes in the right-hand sides of either of these constraints will change the actual values of
the current optimal solution. But these alterations will not change the fact that in the optimal
solution, the basic variables are $x_1$, $s_1$, and $x_2$. On the other hand, the amount
of available premium fuel can decrease by up to four units and increase as large as one likes without affecting the actual values of the current optimal solution $(x_1,x_2)=(4,10)$. This is a very different type of outcome, one that we wish to account for in our analysis.

\newpar
Ideally, we wish to conduct sensitivity analysis in as efficient a manner as possible
without actually resolving the LP.
Crucial for doing so is the result of Theorem
\ref{Th:Paritioned_Matrix_View_Simplex} from Section \ref{S:Partitioned_Matrix_View_Simplex}. It states that
if the matrix corresponding to the initial tableau of
a standard maximization LP is given by

\begin{equation}\label{E:Sensitivity_initial_partitioned}
\begin{bmatrix}
1 & -\vecc & \zerovec & 0 \\
\zerovec & A & I_m & \vecb
\end{bmatrix}
\end{equation}
and if the LP is feasible and bounded, then the tableau matrix after the final
iteration can be written as

\begin{equation}\label{E:Duality_final_partitioned}
\begin{bmatrix} 1 & \vecy \\ \zerovec & M \end{bmatrix} \cdot \begin{bmatrix} 1 & -\vecc & \zerovec_{1\times m} & 0 \\
\zerovec & A & I_3 & \vecb
\end{bmatrix}
=
\begin{bmatrix} 1 & -\vecc+\vecy A & \vecy & \vecy\vecb \\ \zerovec & MA & M
& M \vecb \end{bmatrix},
\end{equation}
for some suitable 1 by $m$ vector $\vecy$ (the solution to the dual!) and some $m$-by-$m$
matrix $M$. In particular, all steps of the simplex algorithm used to achieve the
final tableau are completely determined by the entries of $\vecy$ and $M$.

\subsection{Sensitivity to an Objective Coefficient}\label{S:Sensitivity_objective_change}\index{sensitivity analysis!sensitivity to an objective coefficient}

\noi Suppose the objective coefficients in our initial LP are represented by the vector
$\vecc$ and we wish to change them by some vector quantity $\vecc_{\delta}$. Then the new tableau matrix becomes

\begin{equation}\label{E:Sensitivity_initial_partitioned_objec_coeff_modified}
\begin{bmatrix}
1 & -\vecc -\vecc_{\delta} & \zerovec & 0 \\
\zerovec & A & I_m & \vecb
\end{bmatrix}.
\end{equation}
If we apply to (\ref{E:Sensitivity_initial_partitioned_objec_coeff_modified}) the same steps of the simplex algorithm as we did
to obtain (\ref{E:Duality_final_partitioned}), then we have

\begin{multline}\label{E:Sensitivity_objective_changed2}
\begin{bmatrix} 1 & \vecy \\  \zerovec & M \end{bmatrix}
\cdot
\begin{bmatrix}
1 & -\vecc-\vecc_{\delta} & \zerovec & 0 \\
\zerovec & A & I_m &  \vecb
\end{bmatrix}  \\
= \begin{bmatrix} 1 & \vecy \\  \zerovec & M \end{bmatrix}
\cdot
\left(
\begin{bmatrix}
1 & -\vecc & \zerovec & 0 \\
\zerovec & A & I_m & \vecb
\end{bmatrix}
+
\begin{bmatrix}
0 & -\vecc_{\delta} & \zerovec & 0 \\
\zerovec & 0_{m \times n} & 0_{m \times m} & \zerovec
\end{bmatrix}
\right) \\
=\begin{bmatrix}
1 & -\vecc +\vecy A & \vecy & \vecy \vecb \\
\zerovec & MA & M & M\vecb
\end{bmatrix}
+
\begin{bmatrix}
0 & -\vecc_{\delta} & \zerovec & 0 \\
\zerovec & 0_{m \times n} & 0_{m \times m} & \zerovec
\end{bmatrix}\\
=\begin{bmatrix}
1 & -\vecc -\vecc_{\delta} +\vecy A & \vecy & \vecy \vecb \\
\zerovec & MA & M & M\vecb
\end{bmatrix} .
\end{multline}

\noindent By comparing
(\ref{E:Sensitivity_objective_changed2}) to
(\ref{E:Duality_final_partitioned}), we see that the only changes that result from applying
the same steps of the algorithm to the new LP occur
in the top
row of the tableau. In particular, the tableau corresponding to (\ref{E:Sensitivity_objective_changed2}) reflects
the need for additional iterations only if at least one entry of
$\ds -\vecc -\vecc_{\delta} +\vecy A $ is negative.

\newpar
The \LP example illustrates an application of this principle. Suppose that the premium profit increases from
4 to $4+\delta$. By (\ref{E:Sensitivity_objective_changed2}) and
Table \ref{Ta:Sensitivity_LPC_final_tableau}, we obtain the tableau shown
in Table \ref{Ta:Sensitivity_objective_changed1}.

\begin{table}[h]
\caption{\LP tableau under changed premium cost}\label{Ta:Sensitivity_objective_changed1}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
$z$ & $x_1$ & $x_2$ & $s_1$ & $s_2$ & $s_3$ & RHS \\
\hline \hline
1 & $-\delta$ & 0 & 0 & $\frac{1}{2}$ & 1 & 46 \\ \hline
0 &  \fbox{1} & 0 & 0 & -1 & 1 & 4 \\ \hline
0 &  0 & 0 & 1 & 1 & -1 & 4 \\ \hline
0 &  0 & 1 & 0 & $\frac{3}{2}$ & -1 & 10 \\ \hline
\end{tabular}
\end{table}

\newpar
Recall that in the
original LP, the basic variables at the final iteration were given by $x_1$, $x_2$, and $s_1$. To update the values of $x_1$ and the objective, we must pivot on the highlighted entry
in Table \ref{Ta:Sensitivity_objective_changed1}. Doing so yields the tableau in Table \ref{Ta:Sensitivity_objective_changed2}.

\begin{table}[h]
\caption{\textit{FuelPro} tableau under changed premium cost and after additional pivot}\label{Ta:Sensitivity_objective_changed2}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
$z$ & $x_1$ & $x_2$ & $s_1$ & $s_2$ & $s_3$ & RHS \\
\hline \hline
1 & 0 & 0 & 0 & $\frac{1}{2}-\delta$ & $1+\delta$ & $46+4\delta$ \\ \hline
0 &  1 & 0 & 0 & -1 & 1 & 4 \\ \hline
0 &  0 & 0 & 1 & 1 & -1 & 4 \\ \hline
0 &  0 & 1 & 0 & $\frac{3}{2}$ & -1 & 10 \\ \hline
\end{tabular}
\end{table}

\newpar
From this tableau, we see that an additional iteration of the simplex algorithm is required only if
one of $\frac{1}{2}-\delta$ or $1+\delta$
is strictly negative. Hence
if $\ds -1 \leq \delta \leq \frac{1}{2}$
(meaning the premium cost stays between 3 and 4.5), then the values
of the decision variables remain at $(x_1,x_2)=(4,10)$. However, the corresponding objective
function changes to $z=46+4\delta$.

\newpar
A slightly different type of example is given by the three-variable LP
\begin{align}\label{E:Sensitivity_3_var}
 \mbox{maximize } z &=4x_1+3x_2 +6x_3  \\
	\mbox{ subject to} \notag\\
	3x_1 +x_2+3x_3&\leq 30 \notag\\
	2x_1+2x_2 +3x_3&\leq 40  \notag\\
	x_1,x_2,x_3 &\geq 0.\notag
	\end{align}
%See simplex_three_variable_example.mws	
The final tableau corresponding to this LP is given in Table \ref{Ta:Sensitivity3var}. 	

\begin{table}[h]
\caption{Final tableau for three-variable LP (\ref{E:Sensitivity_3_var})}
\label{Ta:Sensitivity3var}
\begin{tabular}{|c||c|c|c|c|c||c|}
\hline
$z$ & $x_1$ & $x_2$ & $x_3$ & $s_1$ & $s_2$ &  RHS \\
\hline \hline
1 &  1 & 0 & 0 & 1 & 1 & 70 \\ \hline
0 &   $\frac{4}{3}$ & 0 & 1 & $\frac{2}{3}$ & $-\frac{1}{3}$ & $\frac{20}{3}$ \\ \hline
0 &   -1 & 1 & 0 & -1 & 1 & 10 \\ \hline
\end{tabular}
\end{table}

\newpar
The basic variables at the final iteration are given by $x_2=10$ and $\ds x_3=\frac{20}{3}$.
Suppose in this case that the first objective coefficient increases from 4 to $4+\delta$. Then
applying to the new LP the same steps of the simplex algorithm that led to Table \ref{Ta:Sensitivity3var},
we obtain the tableau given in Table \ref{Ta:Sensitivity_3_var_2}.

\begin{table}[h]
\caption{Final tableau for modification of three-variable LP (\ref{E:Sensitivity_3_var})}
\label{Ta:Sensitivity_3_var_2}
\begin{tabular}{|c||c|c|c|c|c||c|}
\hline
$z$ & $x_1$ & $x_2$ & $x_3$ & $s_1$ & $s_2$ &  RHS \\
\hline \hline
1 &  $1-\delta$ & 0 & 0 & 1 & 1 & 70 \\ \hline
0 &   $\frac{4}{3}$ & 0 & 1 & $\frac{2}{3}$ & $-\frac{1}{3}$ & $\frac{20}{3}$ \\ \hline
0 &   -1 & 1 & 0 & -1 & 1 & 10 \\ \hline
\end{tabular}
\end{table} 	

\newpar
The current solution remains optimal provided $\delta < 1$. In this case, no additional pivots are
necessary in order to update the objective value. This stems from the fact that we elected to increase the objective coefficient of a decision variable that was nonbasic in the optimal
solution of the original LP. In the case of the \LP LP, both decision variables were basic in the
optimal solution of the original LP.

\newpar
Duality provides an additional means of handling this situation in which the objective coefficient of a nonbasic
variable is permitted to increase. From Table \ref{Ta:Sensitivity_3_var_2}, we
see that the solution of the dual of (\ref{E:Sensitivity_3_var}) is given by
$\ds \vecy=[1,1]$. To say that the current solution of
(\ref{E:Sensitivity_3_var}) remains optimal is to say that
$\ds \vecy=[1,1]$ remains a feasible solution of the corresponding dual LP. In other words,
	\begin{equation}\label{E:Sensitivity_dual}
	\vecy A = \vecy \begin{bmatrix} 3 & 1 & 3 \\ 2 & 2 & 3 \end{bmatrix}=[5,3,6] \geq [4+\delta, 3, 6],
	\end{equation}
which implies  $\delta <1$.

\newpar
In summary, when performing a sensitivity
analysis that focuses on the effect of changing a coefficient in the objective function
by some value $\delta$, we start with (\ref{E:Sensitivity_objective_changed2}).
	\be
	\item If the coefficient corresponds to a nonbasic variable in the solution of the
	original LP, then the range of values $\delta$ for which the optimal solution
	values remain unchanged is straightforward to determine. We can subtract $\delta$ from the coefficient
	of the corresponding variable in the top row of the original final tableau or use duality.
	\item If the coefficient corresponds to a basic variable, we should pivot to update the value
	of the objective function and to determine whether another iteration of the simplex
	algorithm is necessary. For values of $\delta$ not leading to an additional iteration,
	the decision variable values in the optimal solution are the same as in the original LP.
    However, the objective function value will now depend upon $\delta$, in a manner determined
    by the pivots.
	\ee

\begin{progress_ck}\label{Th:SensitivityAnalysisWaypoint1}
Solve the LP
\begin{align}
		 \mbox{maximize } z &=4x_1 + x_2 +5x_3  \\
		\mbox{ subject to} \notag\\
		2x_1+x_2+3x_3 &\leq 14 \notag\\
		6x_1+3x_2 +3x_3 &\leq 22  \notag\\
		2x_1+3x_2  \x &\leq 14 \notag \\
		x_1,x_2,x_3 &\geq 0\notag.
		\end{align}	
Then perform a sensitivity analysis on each of the objective function coefficients.
\end{progress_ck}

\subsection{Sensitivity to Constraint Bounds}\label{S:Sensitivity_constraint_change}\index{sensitivity analysis!sensitivity to constraint bounds}

\noi We now consider the effect of changing one or more constants that bound the right-hand sides of an LP's constraints. In terms of
the matrix form (\ref{E:Sensitivity_initial_partitioned}), we are concerned with the outcome
of increasing or decreasing one or more entries of $\vecb$.
Initially, our focus will be on perturbing a single entry of the ``constraint vector''
$\vecb$ in (\ref{E:Sensitivity_initial_partitioned}), one that corresponds to a binding constraint.

\newpar
Suppose we wish to increase the right-hand side of such a constraint by $\delta$ units, where $\delta<0$ is
interpreted as a decrease. Thus, the new constraint vector may be denoted as
	\[ \vecb + \delta \vecu.\]
Here $\vecu$ is an $m$-by-1 column vector consisting of all zeros, except in the entry corresponding
to the constraint being changed, where a 1 is present instead.

\newpar
The partitioned matrix form corresponding to the initial tableau is given by
\begin{equation}\label{E:Sensitivity_constraint_change_1}
 \begin{bmatrix}
1 & -\vecc & \zerovec & 0 \\
\zerovec & A & I_m & \vecb+ \delta \vecu.
\end{bmatrix}
\end{equation}

\noi Applying the same steps of the simplex algorithm that were used to
solve the original LP, we have
\begin{multline}\label{E:Sensitivity_constraint_change_2}
\begin{bmatrix} 1 & \vecy \\  \zerovec & M \end{bmatrix}
\cdot
\begin{bmatrix}
1 & -\vecc & \zerovec & 0 \\
\zerovec & A & I_m &  \vecb+\delta \vecu
\end{bmatrix}  \\
= \begin{bmatrix} 1 & \vecy \\  \zerovec & M \end{bmatrix}
\cdot
\left(
\begin{bmatrix}
1 & -\vecc & \zerovec & 0 \\
\zerovec & A & I_m & \vecb
\end{bmatrix}
+
\begin{bmatrix}
0 & \zerovec & \zerovec & 0 \\
\zerovec & 0_{m \times n} & 0_{m \times m} & \delta \vecu
\end{bmatrix}
\right) \\
=\begin{bmatrix}
1 & -\vecc +\vecy A & \vecy & \vecy \vecb \\
\zerovec & MA & M & M\vecb
\end{bmatrix}
+
\begin{bmatrix}
0 & \zerovec & \zerovec & \vecy \delta \vecu \\
\zerovec & 0_{m \times n} & 0_{m \times m} & M\delta \vecu
\end{bmatrix}\\
=\begin{bmatrix}
1 & -\vecc +\vecy A & \vecy & \vecy \left( \vecb + \delta \vecu \right) \\
\zerovec & MA & M & M\vecb+M\delta \vecu
\end{bmatrix} .
\end{multline}

\newpar
Note that the top row of this matrix, with the exception of
 the rightmost entry, is identical to that obtained applying the simplex
algorithm to the original, unmodified LP. Thus, on first inspection,
(\ref{E:Sensitivity_constraint_change_2}) corresponds
to the final tableau of the modified LP, and the set of basic variables is the same as in the original LP. However, care must be taken to ensure that all basic variables are nonnegative.

\newpar
Let $\ds \mbox{BV}_j$, where $1 \leq j \leq m$ denote the basic variable corresponding
to row $j$ of the final tableau. Then
\begin{align}\label{E:Sensitivity_BV_equation}
\mbox{BV}_j &= \left[M\vecb + M \delta \vecu\right]_j \\
&= \left[M\vecb\right]_j
 + \left[M\delta \vecu\right]_j \notag \\
&=  \left[M\vecb\right]_j
 + \delta\left[M\vecu\right]_j. \notag
\end{align}

\newpar
Each basic variable is currently positive in the original LP (when $\delta=0$),
unless the LP is degenerate, a case we will omit from discussion. By setting positive
each of the $m$ expressions comprising the right-hand side of (\ref{E:Sensitivity_BV_equation}) and solving for $\delta$,
we can determine the maximum and minimum allowable range of $\delta$ values that result in positive
basic variable values. In general this range can be computed as
\begin{equation}\label{E:Sensitivity_delta_range}
	\max
		\left\{ \left. -\frac{\left[ M\vecb \right]_j}{\left[M\vecu\right]_j} \right\bracevert \quad \left[M\vecu\right]_j	>0 \right\}		
		< \delta <
	\min
		\left\{ \left. -\frac{\left[ M\vecb \right]_j}{\left[M\vecu\right]_j} \right\bracevert \quad \left[M\vecu\right]_j	<0 \right\}.
	\end{equation}

\newpar
For example, suppose that in the \LP LP, an additional $\delta$ units of stock A becomes available,
in which case the right-hand side of the second constraint in (\ref{E:Sensitivity_LP_long})
increases from 28 to $28+\delta$. The final tableau for the original LP is given in Table
\ref{Ta:Sensitivity_LP_original_final_tableau}.

\begin{table}[h]
\caption{Final tableau for
original \textit{FuelPro} LP}\label{Ta:Sensitivity_LP_original_final_tableau}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
$z$ & $x_1$ & $x_2$ & $s_1$ & $s_2$ & $s_3$ & RHS \\
\hline \hline
1 & 0 & 0 & 0 & $\frac{1}{2}$ & 1 & 46 \\ \hline
0 &  1 & 0 & 0 & -1 & 1 & 4 \\ \hline
0 &  0 & 0 & 1 & 1 & -1 & 4 \\ \hline
0 &  0 & 1 & 0 & $\frac{3}{2}$ & -1 & 10 \\ \hline
\end{tabular}
\end{table}

\newpar
In this situation, the basic variables corresponding to rows 1-3 are given by $x_1$, $s_1$,
and $x_2$, respectively. Since $\ds M=\begin{bmatrix} 0 & -1 & 1 \\ 1 & 1 & -1 \\ 0 & \frac{3}{2} & -1 \end{bmatrix}$ and
$\ds \vecu=\begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix}$, an increase
in the right-hand side of the second constraint by $\delta$ yields
\begin{align*}
 \begin{bmatrix} x_1 \\ s_1 \\ x_2 \end{bmatrix} &= M\vecb+\delta M\vecu \\
            &= \begin{bmatrix} 4-\delta \\ 4+ \delta \\ 10 + \frac{3}{2}\delta
\end{bmatrix}.
\end{align*}

\newpar
For basic variables $x_1$, $s_1$,
and $x_2$ to all remain positive, it must be the case that
 $-4 < \delta < 4$, or, in other words, the amount of available
stock A stays between 24 and 32 gallons. For values of $\delta$ in this range, the corresponding
objective value is given by
\[ z_0=\vecy \left( \vecb + \delta \vecu \right)=46+\frac{1}{2}\delta.\]

\newpar
A close inspection of the preceding example, together
with the general objective formula $\ds z=\vecy \left( \vecb + \delta \vecu \right)$ in
(\ref{E:Sensitivity_constraint_change_2}), illustrates
a fundamental role played by slack variables in sensitivity analysis.
The increase in the objective value in this particular example
is
\[\frac{1}{2}\delta=y_2 \delta=\vecy \delta \vecu.\]
Thus, slack variable
coefficient values in the top row of the final tableau, which are represented by
$\vecy$, can be used
to determine a change in objective
value when a constraint bound is changed. This outcome is true even when the previously discussed sensitivity analysis
is not performed, provided the set of basic variables remains intact under such a change. This gives slack variables an extremely useful role in sensitivity analysis and leads us to the following definition.
\newpage
\begin{definition}
Suppose that the optimal solution to a standard maximization LP is given by
\begin{equation*}
 z_0= \vecy \vecb = \sum_{j=1}^{m} y_jb_j.
 \end{equation*}
Then the instantaneous rate of change, $\ds \frac{\partial z_0}{\partial b_j} = y_j$, the $j$th slack variable
coefficient value in the top row of the LP's final tableau,
is called the \emph{shadow price}\index{shadow price} of the objective function $z$ with respect to constraint $j$.
For a small amount of change in $b_j$, small enough so that the set of basic variables in the solution
of the new LP is identical to that in the solution of the original LP, this shadow price
can be used to compute the amount of increase or decrease in
the objective function.
\end{definition}

\newpar
For example, consider a maximization LP in two decision variables whose final tableau is given
by Table \ref{Ta:Sensitivity_shadow_price_example}:
\begin{table}[h]
\caption{Final tableau for sample maximization LP}\label{Ta:Sensitivity_shadow_price_example}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
$z$ & $x_1$ & $x_2$ & $s_1$ & $s_2$ & $s_3$ & RHS \\
\hline \hline
1 & 0 & 0 & 3 & 0 & 2 & 20 \\ \hline
\end{tabular}
\end{table}

\newpar
Since $y_j \ne 0$ for $j=1$ and $j=3$, the Complementary Slackness Property (Theorem \ref{Th:Duality_complementary_slackness})
dictates that the first and third
constraints of the LP are binding and that the shadow price of $z$ with respect to the
first constraint is
\[ \frac{\partial z_0}{\partial b_1} = y_1=3.\]
Assume that increasing the right-hand side of the first constraint by
.01 does not change the set of basic variables in the new solution from that in the solution of the original
LP. Then the objective $z$ increases by $\ds \Delta z = 3 (.01) =.03$.


\newpar
In summary, when performing a sensitivity
analysis that focuses on the effect of changing the right-hand side of a binding
constraint in a standard maximization problem, we do the following:
	\be
	\item To find the permissible range of increase or decrease in the right-hand side of
a constraint, we use formula
	\ref{E:Sensitivity_delta_range} and/or the derivation that led to it. This formula provides a means
	for determining the updated basic variable and objective values.
	\item To determine the magnitude of change solely in the objective function
	value caused by the change in a constraint bound, we use the shadow price of the corresponding constraint. This is given by the corresponding slack variable coefficient in the top row
	of the LP's final tableau. The shadow
	price must be used with caution, however, as its ability to predict change in the objective value assumes that the set of basic variables remains unchanged from that in the solution of the original LP.
	\ee

\begin{progress_ck}
Consider the three-variable LP from Waypoint \ref{Th:SensitivityAnalysisWaypoint1}.
\be
\item Suppose that the right-hand side
of a particular constraint increases by $\Delta b$ and that the set of basic variables in the solution
of the new LP is identical to that obtained in the original LP. Use the definition of shadow price to
determine how much the objective function will increase or decrease. Perform this analysis for each
constraint that is binding in the original LP.
\item By how much may the right-hand side of each binding constraint change
and the set of basic variables in the solution to the resulting LP equal that from the solution to the original
LP? For this range, what are the corresponding values of the basic variables and the objective function?
\ee
\end{progress_ck}

\newpar
In the preceding example, we modified the right-hand side of only one constraint. Yet the
underlying principles can be easily modified to situations involving more than
one constraint bound. In this case, the constraint vector $\vecb$ is adjusted by the vector
$\ds \deltavec=\begin{bmatrix} \delta_1 \\ \delta_2 \\ \delta_3 \end{bmatrix}$, where
$\delta_i$, for $i=1,2,3$, denotes the change in the bound on constraint $i$. Now the final matrix corresponding to that in (\ref{E:Sensitivity_constraint_change_2}) becomes
\begin{equation}\label{E:Sensitivity_constraint_change_2_sides}
\begin{bmatrix}
1 & -\vecc +\vecy A & \vecy & \vecy \left( \vecb + \deltavec \right) \\
\zerovec & MA & M & M\vecb+M\deltavec
\end{bmatrix}.
\end{equation}

\newpar
For example, in the \LP LP, if the available premium increases by $\delta_1$ and the available
stock A increases by $\delta_2$, then
$\ds \deltavec=\begin{bmatrix} \delta_1 \\ \delta_2 \\ 0 \end{bmatrix}$ so that
\begin{align}\label{sensitivity_two_variable_change}
\begin{bmatrix} x_1 \\ s_1 \\ x_2 \end{bmatrix}
            &= M\vecb+M \deltavec \\
            &= \begin{bmatrix} 4-\delta_2 \\ 4+ \delta_1+\delta_2 \\ 10 + \frac{3}{2}\delta_2 \end{bmatrix}.
\end{align}

The set of ordered pairs,
$\ds (\delta_1,\delta_2)$, for which $x_1$, $s_1$, and $s_2$ are all nonnegative is shown in Figure \ref{Fi:Sensitivity_LP_delta_region}.
For ordered pairs in this shaded region, the new objective value is given by
$\ds z=\vecy \left( \vecb +\deltavec \right)$.

\begin{figure}[h]
\centering
\psfrag{horizontal_axis}[Bc][Bc]{$\delta_1$}
\psfrag{vertical_axis}[Bc][Bc]{$\delta_2$}
\includegraphics[width=.7\linewidth]{images/f05x02x02.eps}
\caption{Ordered pairs $(\delta_1,\delta_2)$ for which changes in the
first two constraints of
\LP LP leave the basic variables,
$\left\{x_1,s_1,x_2\right\}$, unchanged.}

\label{Fi:Sensitivity_LP_delta_region}
\end{figure}

\subsection{Sensitivity to Entries in the Coefficient Matrix $A$}\index{sensitivity analysis!sensitivity to a coefficient matrix entry}

\noi Performing sensitivity analysis when entries of the coefficient matrix $A$
are changed can be complicated and tedious for reasons to be outlined
momentarily. One situation in which the analysis is rather straightforward occurs when the matrix entry corresponds
to a decision variable that is nonbasic in the solution of the original LP. Suppose first that we add some matrix $A_{\delta}$ to $A$, where the only
nonzero entries of $A_{\delta}$ are those corresponding to such nonbasic variables. We
leave it as an exercise to show that by applying the same elementary row operations that resulted in the final tableau for the original LP, we obtain the matrix

\begin{equation}\label{E:Sensitivity_A_adjusted_delta}
\begin{bmatrix}
1 & -\vecc +\vecy (A +A_{\delta}) & \vecy & \vecy \vecb  \\
\zerovec & M(A+A_{\delta}) & M & M\vecb
\end{bmatrix}.
\end{equation}

\newpar
In Section \ref{S:Sensitivity_constraint_change}, we considered sensitivity of an LP to
a coefficient in its objective function. We observed that when we applied the same simplex algorithm steps
that were used to solve the original LP, we obtained a tableau matrix whose decision variable
coefficients were represented by the vector $\ds -\vecc -\vecc_{\delta} +\vecy A$. We also
observed that duality could be used to determine the permissible range of $\delta$ values
for which the optimal solution remained unchanged. Here, the use of duality is crucial.

\newpar
The reason for this fact becomes apparent if we contrast
the two vectors,
\begin{equation*} -\vecc -\vecc_{\delta} +\vecy A \mbox{ and }
-\vecc +\vecy (A +A_{\delta}),
\end{equation*}
which
appear in the top rows of the respective tableau matrices  (\ref{E:Sensitivity_objective_changed2}) and
(\ref{E:Sensitivity_A_adjusted_delta}).
Changing an objective coefficient of a single decision variable in an LP only changes
the coefficient of the same variable in the top row
when the simplex algorithm is performed. But when an entry of $A$ is modified, the presence
of the vector-matrix product $ \vecy (A +A_{\delta})$ in the top row
of (\ref{E:Sensitivity_A_adjusted_delta}) introduces the possibility that more than
one coefficient in the top row of the tableau is altered.

\newpar
Duality provides a convenient means of addressing this problem. If the vector $\vecy$ in
(\ref{E:Sensitivity_A_adjusted_delta}), which is nonnegative, satisfies
	\begin{equation*}
	\vecy (A +A_{\delta}) \geq \vecc,
	\end{equation*}
then the solution to the LP whose final tableau matrix is given in
(\ref{E:Sensitivity_A_adjusted_delta}) remains optimal. Moreover, no additional pivots are needed
to update any of the basic variable values. This second fact follows from noting that entries of
$\ds-\vecc +\vecy A$ corresponding to basic variables are all zero (in the solution
of the original LP), as are those in
$\vecy A_{\delta}$. (Recall in our choice of $A_{\delta}$ that column entries of $A_{\delta}$ corresponding
to basic variables must equal zero.)

\newpar
For example, in the solution to the three variable LP (\ref{E:Sensitivity_3_var}),
the variable $x_1$ was nonbasic. Suppose the coefficient of $x_1$ changes from
2 to $2+\delta$ in the second constraint. Referring to the slack variable coefficients
in Table \ref{Ta:Sensitivity_3_var}, we note that the current solution remains optimal
if
$\ds \vecy=[1,1]$ satisfies
	\begin{align}\label{E:Sensitivity_dual}
	\vecy (A+A_{\delta})&= \vecy \begin{bmatrix} 3 & 1 & 3 \\ 2+\delta & 2 & 3 \end{bmatrix}
    \notag \\
	&=[5+\delta,3,6] \notag \\
    &\geq [4, 3, 6] , \notag
	\end{align}
that is, if $-1 \leq \delta$.

\newpar
Now we consider the case when the nonzero entry of $A_{\delta}$ corresponds to a basic variable in the LP's
solution. For example, suppose in the \LP
LP that an additional $\delta$ gallons of stock B is required to produce each gallon of regular
unleaded, in which case the coefficient of $x_2$ in the third constraint of the LP increases from
2 to $2+\delta$.
The tableau corresponding to
(\ref{E:Sensitivity_A_adjusted_delta}) then becomes that shown in Table \ref{Ta:Sensitivity_A_adjusted_1}.

\begin{table}[h]
\caption{\textit{Fuelpro} tableau after adjustment to coefficient of $A$
corresponding to a basic variable}
\label{Ta:Sensitivity_A_adjusted_1}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
$z$ & $x_1$ & $x_2$ & $s_1$ & $s_2$ & $s_3$ & RHS \\
\hline \hline
1 & 0 & $\delta$ & 0 & $\frac{1}{2}$ & 1 & 46 \\ \hline
0 &  1 & $\delta$ & 0 & -1 & 1 & 4 \\ \hline
0 &  0 & $-\delta$ & 1 & 1 & -1 & 4 \\ \hline
0 &  0 & $1-\delta$ & 0 & $\frac{3}{2}$ & -1 & 10 \\ \hline
\end{tabular}
\end{table}

\newpar
To begin the analysis in this situation, we first perform a pivot
to update the values of the basic variables and
the objective. This pivot leads to the result in Table \ref{Ta:Sensitivity_A_adjusted_2}.

\begin{table}[h]
\caption{Updated \textit{Fuelpro} final tableau after adjusting coefficient of $x_2$ in third constraint}
\label{Ta:Sensitivity_A_adjusted_2}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
$z$ & $x_1$ & $x_2$ & $s_1$ & $s_2$ & $s_3$ & RHS \\
\hline \hline
1 & 0 & 0 &  0 & $\frac{4\delta-1}{2(\delta-1)}$
& $\frac{1}{1-\delta}$ & $\frac{2(28\delta-23)}{\delta-1}$ \\ \hline

0 &  1 & 0 & 0 & $\frac{2+\delta}{2(\delta-1)}$
& $\frac{1}{1-\delta}$ & $\frac{2(7\delta-2)}{\delta-1}$ \\ \hline

0 &  0 & 0 & 1 & $\frac{2+\delta}{2(1-\delta)}$
& $\frac{1}{\delta-1}$ & $\frac{2(3\delta+2)}{1-\delta}$ \\ \hline

0 &  0 & 1 & 0 & $\frac{-3}{2(\delta-1)}$
& $\frac{1}{\delta-1}$ & $\frac{10}{1-\delta}$ \\ \hline
\end{tabular}
\end{table}

\newpar
We now make two important observations regarding this tableau. First, in order for the basic variables $x_1$, $x_2$ and $s_1$ to remain nonnegative, it must be the case that
$\ds \frac{2(7\delta-2)}{\delta-1}$, $\ds \frac{2(3\delta+2)}{1-\delta}$, and $\ds \frac{10}{1-\delta}$ are all nonnegative. Hence $\ds -\frac{2}{3} \leq \delta \leq \frac{2}{7}$. Second, another iteration of the simplex algorithm is unnecessary provided
the nonbasic variable coefficients in the top row of the tableau,
$\ds \frac{4\delta-1}{2(\delta-1)}$ and $\ds \frac{1}{1-\delta}$, are nonnegative, i.e., provided
$\delta \leq \frac{1}{4}$. Combining these results we conclude that
for $\ds -\frac{2}{3} \leq \delta \leq \frac{1}{4}$, the set of basic variables in
the solution of the modified is the same as that in the solution of the original. The updated values of the basic variables are given in Table \ref{Ta:Sensitivity_A_adjusted_2}. Note in particular that
when $\delta=0$, the solution reduces precisely to that of the original \LP LP.

\newpar
In summary, when changing an entry in the coefficient matrix $A$ of a standard maximization LP, begin
with (\ref{E:Sensitivity_A_adjusted_delta}).
	\be
	\item If the entry of $A$ that is changed corresponds to a nonbasic variable in the final solution
	to the original LP, then duality provides a straightforward means of determining the range of values
	for which the current solution remains optimal. No additional pivots are necessary.
	\item If the entry of $A$ being changed does correspond to a basic variable, then a pivot is necessary to determine conditions under which all basic variables remain nonnegative and no further
simplex algorithm iterations are necessary. This process can be quite tedious.
	\ee

\subsection{Performing Sensitivity Analysis with Maple}\label{SS:Maple_Implementation_Sensitivity}\index{sensitivity analysis!performing with Maple}

\noi Sensitivity analysis can be performed with Maple through the use of basic matrix operations. The following worksheet, \textbf{Sensitivity Analysis.mw},
illustrates an example, using methods discussed in this section as applied to the \LP model. In the interest of avoiding redundancy, calculations leading to
the original optimal tableau have been omitted. They may be found in the sample
worksheet, \textbf{Simplex Algorithm.mw}, given at the end of Section \ref{SS:Maple_Implementation_Simplex}. This
worksheet begins with the final tableau matrix from
\textbf{Simplex Algorithm.mw}, denoted by \mf{LP\_Matrix}. Recall that $\vecc$, $A$,
$\vecb$, $n$, and $m$ are all defined at the start of \textbf{Simplex Algorithm.mw}
and
that column 0 and row 0 denote the leftmost column and top row, respectively, of
the tableau matrix.

{\small{
\begin{maplelist}
\item \mf{Tableau(LPMatrix); \newline \# Display final tableau matrix for FuelPro LP.}
\mo{\begin{bmatrix}
z & x_1 & x_2 & s_1 & s_2 & s_3 & RHS \\
1 & 0 & 0 & 0 & \frac{1}{2} & 1 & 46 \\
0 & 1 & 0 & 0 & -1 & 1 & 4 \\
0 & 0 & 0 & 1 & 1 & -1 & 4 \\
0 & 0 & 1 & 0 & \frac{3}{2} & -1 & 10
\end{bmatrix}}
\item \mf{y:=SubMatrix(LPMatrix,1..1, (m+1)..(m+1+n));
\newline \# Extract from final tableau the slack variable coefficients
\newline  as a vector.}
\mo{y=\begin{bmatrix} 0 & \frac{1}{2} & 1 \end{bmatrix} }
\item \mf{M:=SubMatrix(LPMatrix,2..(m+1),(m+1)..(m+1+n));
\newline \# Extract from final tableau the submatrix M corresponding to portion of tableau below
slack variable coefficients.}
\mo{M=\begin{bmatrix} 0 & -1 & 1 \\ 1 & 1 & -1 \\ 0 & \frac{3}{2} & -1 \end{bmatrix} }
\item \mf{ObjectiveCoefficient:=1; \newline \# Assess sensitivity to first objective coefficient.}
\mo{ObjectiveCoefficient=1}
\item \mf{e:=UnitVector[row](ObjectiveCoefficient,2);}
\mo{e=\begin{bmatrix} 1 & 0 \end{bmatrix}}
\item \mf{LPMatrixNew:=<UnitVector(1,m+1)|<convert(-c-delta*e,Matrix)+y.A,M.A>|
<y,M>|<y.b,M.b>>; \newline \# Create new tableau matrix obtained by perturbing first objective
coefficient.}
\mo{LPMatrixNew=\begin{bmatrix} 1 & -\delta & 0 & 0 & \frac{1}{2} & 1 & 46 \\
0 & 1 & 0 & 0 & -1 & 1 & 46 \\
0 & 0 & 0 & 1 & 1 & -1 & 4 \\
0 & 0 & 1 & 0 & \frac{3}{2} & -1 & 10 \end{bmatrix}
}
\item \mf{Iterate(LPMatrixNew,1,1);
\newline \# Update tableau entries.}
\mo{ \begin{bmatrix} z & x1 & x2 & s1 & s2 & s3 & RHS \\
1 & 0 & 0 & 0 & \frac{1}{2}-\delta & 1+\delta & 46 + 4\delta \\
0 & 1 & 0 & 0 & -1 & 1 & 4 \\
0 & 0 & 0 & 1 & 1 & -1 & 4 \\
0 & 0 & 1 & 0 & \frac{3}{2} & -1  & 10 \end{bmatrix}
}
\item \mf{solve(LPMatrixNew[1,5]>=0 and LPMatrixNew[1,6]>=0, delta); \newline \# Determine delta values under which nonbasic variable coefficients in top row remain nonnegative.}
\mo{RealRange=\left(-1,\frac{1}{2}\right)}
\item \mf{ConstraintNumber:=2; \newline \# Assess sensitivity to second constraint bound.}
\mo{ConstraintNumber=2}

\item \mf{e:=UnitVector(ConstraintNumber,m);}
\mo{e=\begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix}}

\item \mf{LPMatrixNew:=<UnitVector(1,m+1)|<convert(-c,Matrix)+y.A,M.A>|
\newline <y,M>|<y.(b+delta*e),M.(b+delta*e)>>;
\newline \# Create new tableau matrix obtained by perturbing first objective coefficient.}

\mo{LPMatrixNew=\begin{bmatrix} 1 & 0 & 0 & 0 & \frac{1}{2} & 1 & 46+\frac{1}{2}\delta \\
0 & 1 & 0 & 0 & -1 & 1 & 46 \\
0 & 0 & 0 & 1 & 1 & -1 & 4-\delta \\
0 & 0 & 1 & 0 & \frac{3}{2} & -1 & 10+\frac{3}{2}\delta \end{bmatrix}
}

\item \mf{solve(LPMatrixNew[2,7]>=0 and LPMatrixNew[3,7]>=0 and 
\newline LPMatrixNew[4,7]>=0, delta);
\newline \# Determine conditions under which basic variables remain nonnegative.}
\mo{RealRange=\left(-4,4\right)}

\item \mf{RowNumber:=3:ColumnNumber:=2:
\newline \# Assess sensitivity to entry in
\newline row 3, column 2 of coefficient matrix.}
\item \mf{Adelta:=Matrix(m,n,\{(RowNumber,ColumnNumber)=delta \});
\newline \# Create an m by n perturbation matrix.}
\mo{A_{delta}=\begin{bmatrix} 0 & 0 \\ 0 & 0 \\ 0 & \delta \end{bmatrix}}

\item \mf{LPMatrixNew:= \newline <UnitVector(1,m+1)|<convert(-c,Matrix)+y.(A+Adelta),M.(A+Adelta)>|
<y,M>|<y.b,M.b>>;
\newline \# Create new tableau matrix that results from perturbing assigned
\newline  entry of A.}
\mo{LPMatrixNew=\begin{bmatrix} 1 & 0 & \delta & 0 & \frac{1}{2} & 1 & 46 \\
0 & 1 & \delta & 0 & -1 & 1 & 4 \\
0 & 0 & -\delta & 1 & 1 & -1 & 4 \\
0 & 0 & 1 -\delta & 0 & \frac{3}{2} & -1 & 10 \end{bmatrix}
}
\item \mf{Iterate(LPMatrixNew, 3,2);}
\mo{ \begin{bmatrix} z & x1 & x2 & s1 & s2 & s3 & RHS \\
1 & 0 & 0 & 0 & \frac{1}{2}-\frac{3}{2}\frac{\delta}{1-\delta} & 1+\frac{\delta}{1-\delta} & 46-\frac{10 \delta}{1-\delta} \\
0 & 1 & 0 & 0 & -1-\frac{3}{2}\frac{\delta}{1-\delta} & 1+\frac{\delta}{1-\delta} & 4-\frac{10 \delta}{1-\delta} \\
0 & 0 & 0 & 1 & 1+\frac{3}{2}\frac{\delta}{1-\delta} & -1-\frac{\delta}{1-\delta} & 4+\frac{10 \delta}{1-\delta} \\
0 & 0 & 1 & 0 & 1+\frac{3}{2}\frac{1}{1-\delta} & -\frac{1}{1-\delta} & \frac{10}{1-\delta} \end{bmatrix}
}
\item \mf{solve( LPMatrixNew[1,5]>=0 and LPMatrixNew[1,6]>=0 and 
\newline LPMatrixNew[2,7]>=0 and LPMatrixNew[3,7]>=0 and 
\newline LPMatrixNew[4,7]>=0,delta);
    \newline \# Determine conditions under which no further pivots are necessary and basic variables are all nonnegative.}
\mo{RealRange\left(\frac{-2}{3},\frac{1}{4}\right)
}

\end{maplelist}
}}

\section*{Exercises Section \protect\ref{S:Sensitivity}}

\addcontentsline{toc}{subsection}{Exercises}

\input{Exercises/Exercises_Sensitivity}	
	
\endinput
	
	