\pdfpagewidth=8.5truein  \pdfpageheight=11truein
\hsize=6truein  \vsize=9truein
\pdfhorigin=1.25truein  \pdfvorigin=1truein

\def\itemitemitem{\par\indent \hangindent3\parindent \hskip\parindent \textindent}

\headline={\hfil}  \footline={\hfil Page~\folio\hfil}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\centerline{\bf Sensitivity analysis}

\medskip

\noindent{\bf Big picture}

\medskip

\item{$\bullet$} {\it The setting:\/} You have solved a linear program with the
simplex method, and you have an optimal tableau.

\smallskip

\item{$\bullet$} {\it The question:\/} If one of the numbers in the LP were
changed slightly, how would that change affect the optimal solution?

\smallskip

\item{$\bullet$} {\it The answer:\/} Sensitivity analysis provides two kinds of
information.

\smallskip

\itemitem{--} A maximum increase and a maximum decrease that can be made to the
number in the LP before the change becomes a ``major'' change. (A change within
these limits is a ``minor'' change.)

\smallskip

\itemitem{--} If the change is a ``minor'' change, sensitivity analysis gives
the optimal solution and the optimal objective value for the changed LP.

\bigbreak

\noindent{\bf Correspondences}

\medskip

\item{$\bullet$} Every {\bf constraint} has a corresponding slack, surplus,
and/or artificial variable:

\smallskip

\itemitem{--} A $\le$~constraint has a corresponding {\bf slack variable}.

\smallskip

\itemitem{--} An $=$~constraint has a corresponding {\bf artificial variable}.

\smallskip

\itemitem{--} A $\ge$~constraint has a corresponding {\bf surplus variable} and
a corresponding {\bf artificial variable}.

\smallskip

\item{$\bullet$} Every {\bf constraint} also has a corresponding {\bf dual
variable}.

\smallskip

\item{$\bullet$} Every {\bf variable} has a corresponding {\bf column} in the
simplex tableau.

\smallskip

\item{$\bullet$} Every {\bf basic variable} has a corresponding {\bf row} in
the simplex tableau.

\smallskip

\item{$\bullet$} Note: Rows in the simplex tableau do {\it not\/} correspond to
constraints!

\bigbreak

\noindent{\bf Meanings of the numbers in the objective row}

\medskip

\noindent The numbers in the objective row of a simplex tableau can be
interpreted in two different ways:

\smallskip

\item{$\bullet$} In {\it any\/} tableau, a number in the objective row in a
nonbasic column indicates how much the value of the objective function will
change if the value of the corresponding variable is increased by~1, but the
sign is flipped: a {\it negative\/} entry indicates an {\it increase\/} in the
objective value, and a {\it positive\/} entry indicates a {\it decrease}.

\smallskip

\itemitem{--} This is why, in the simplex algorithm, we pivot on columns with
negative entries in the objective row. A negative number means that giving the
corresponding variable a positive value (i.e., making that column basic) will
{\it increase\/} the value of the objective function.

\smallskip

\itemitem{--} Note: This interpretation of the entries in the objective row
gives information about the effects of a {\it change to the basis\/} of the
current solution, without changing the LP itself; it gives information about
what would happen if you move from the current corner of the feasible region to
a neighboring corner of the feasible region by changing which variables are
basic (and thereby changing the values of the variables).

\smallskip

\item{$\bullet$} In an {\it optimal\/} tableau, the numbers in the objective
row in columns corresponding to {\it slack\/} and {\it artificial\/} variables
({\it not\/} surplus variables) are the optimal values of the corresponding
{\bf dual variables.}

\smallskip

\itemitem{--} The optimal value of a dual variable is the amount that the
optimal objective value would change if the right-hand side of the
corresponding constraint were {\it increased\/} by~1. (There is no sign flip
here: a {\it positive\/} dual variable indicates an {\it increase\/} in the
objective value, and a {\it negative\/} dual variable indicates a {\it
decrease}.)

\smallskip

\itemitem{--} Note: This interpretation gives information about the effects of
a {\it change to the LP itself}.

\bigbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\noindent{\bf Right-hand side sensitivity analysis}

\medskip

\noindent When the proposed change to the LP is to the {\it right-hand side of
a constraint}.

\medskip

\item{$\bullet$} If the constraint is {\bf tight} in the optimal solution:

\smallskip

\itemitem{1.} Look at the column for the corresponding {\it slack\/} or
{\it artificial\/} variable ({\it not\/} the surplus variable). Call this
column the ``working column.''

\smallskip

\itemitem{2.} Form quotients by dividing the entries in the {\it right-hand
column\/} of the optimal tableau by the entries in the working column (not
including the entries in the objective row). [Mnemonic: Use the {\it right-hand
column\/} for {\it right-hand side sensitivity analysis}.]

\smallskip

\itemitem{3.} To find the {\bf maximum increase}: Consider the quotients from
step~2 that use {\it negative\/} entries from the working column. Flip the
signs of those quotients to make them positive, and then choose the smallest.

\smallskip

\itemitemitem{--} If the working column has no negative entries, then there is
no maximum increase, i.e., there is no limit to the amount the right-hand side
of the constraint can be increased.

\smallskip

\itemitem{4.} To find the {\bf maximum decrease}: Consider the quotients from
step~2 that use {\it positive\/} entries from the working column. Choose the
smallest such quotient.

\smallskip

\itemitemitem{--} If the working column has no positive entries, then there is
no maximum decrease, i.e., there is no limit to the amount the right-hand side
of the constraint can be decreased.

\smallskip

\itemitem{5.} Within the limits identified in steps 3~and~4, every unit {\it
increase\/} in the right-hand side of the constraint will change the right-hand
column of the optimal tableau by the corresponding value in the working column.
(This includes the value of the objective function, for which the per-unit
change is given by the value of the optimal dual variable, found at the bottom
of the working column.) Every unit {\it decrease\/} in the right-hand side of
the constraint will have the opposite effect.

\smallskip

\itemitemitem{--} So to get the entries in the right-hand column of the new
optimal tableau, multiply the {\it change\/} in the right-hand side of the
constraint by each entry in the working column, and add those products to the
corresponding entries in the right-hand side of the original optimal tableau.
(Do this for the objective row too, to get the new optimal objective value.)
Now you can easily read off the values of the basic variables in the optimal
solution to the changed LP.

\medskip

\item{$\bullet$} If the constraint is {\bf not tight} in the optimal solution:

\smallskip

\itemitem{--} For a $\le$~constraint, the corresponding {\it slack variable\/}
will be positive. The value of this slack variable is the {\bf maximum
decrease} for the right-hand side of the constrant. There is {\bf no maximum
increase} (i.e., there is no limit to the amount the right-hand side of the
constraint can be increased).

\smallskip

\itemitem{--} For a $\ge$~constraint, the corresponding {\it surplus
variable\/} will be positive. The value of this surplus variable is the {\bf
maximum increase} for the right-hand side of the constrant. There is {\bf no
maximum decrease} (i.e., there is no limit to the amount the right-hand side of
the constraint can be decreased).

\smallskip

\itemitem{--} Within the limits identified above, any change to the right-hand
side of the constraint will have {\it no effect\/} to the objective value or
the optimal solution (except the value of the corresponding slack or surplus
variable).

\medskip

\noindent If the right-hand side of a constraint is changed by the maximum
amount indicated by sensitivity analysis, the optimal solution for the changed
LP will be {\bf degenerate}. (One of the numbers in the {\it right-hand
column\/} of the optimal tableau will be~0.)

\vfill\eject %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\noindent{\bf Objective function coefficient sensitivity analysis}

\medskip

\noindent When the proposed change to the LP is to a {\it coefficient of a
variable in the objective function}. (Suppose the variable is~$x_i$.)

\medskip

\item{$\bullet$} If the variable~$x_i$ is {\bf basic} in the optimal solution:

\smallskip

\itemitem{1.} Look at the row corresponding to~$x_i$. Call this row the
``working row.''

\smallskip

\itemitem{2.} Form quotients by dividing the entries in the {\it objective
row\/} of the optimal tableau by the entries in the working row, but {\it
ignore\/} the following columns:

\smallskip

\itemitemitem{--} the basic columns, including the column for~$x_i$;

\smallskip

\itemitemitem{--} any columns for {\it artificial variables\/}; and

\smallskip

\itemitemitem{--} the right-hand column.

\smallskip

\itemitem{} [Mnemonic: Use the {\it objective row\/} for {\it objective
function coefficient sensitivity analysis}.]

\smallskip

\itemitem{3.} To find the {\bf maximum increase}: Consider the quotients from
step~2 that use {\it negative\/} entries from the working row. Flip the signs
of those quotients to make them positive, and then choose the smallest.

\smallskip

\itemitemitem{--} If the working row has no negative entries, then there is no
maximum increase, i.e., there is no limit to the amount the coefficient can be
increased.

\smallskip

\itemitem{4.} To find the {\bf maximum decrease}: Consider the quotients from
step~2 that use {\it positive\/} entries from the working row. Choose the
smallest such quotient.

\smallskip

\itemitemitem{--} If the working row has no positive entries, then there is no
maximum decrease, i.e., there is no limit to the amount the coefficient can be
decreased.

\smallskip

\itemitem{5.} Within the limits identified in steps 3~and~4, every unit {\it
increase\/} in the objective function coefficient of~$x_i$ will increase the
value of the objective function by the optimal value of~$x_i$. Every unit {\it
decrease\/} in the coefficient will have the opposite effect. The optimal {\it
solution\/} will not change.

\smallskip

\itemitemitem{--} For example, if the optimal value of~$x_3$ is~57 and its
objective function coefficient is increased by~1, then the optimal objective
value will increase by~57 (because every unit of~$x_3$ is now making \$1~more
profit). If its objective function coefficient is increased by~2, then the
optimal objective value will increase by $2\times57=114$.

\medskip

\item{$\bullet$} If the variable~$x_i$ is {\bf nonbasic} in the optimal
solution:

\smallskip

\itemitem{--} The variable~$x_i$ does not have a positive value because it is
not profitable enough. The entry in the objective row in the $x_i$~column,
which must be nonnegative (because the tableau is optimal), indicates the
amount that the objective value would {\it decrease\/} for each unit increase
to the value of~$x_i$. So the per-unit profit for~$x_i$ (i.e., the objective
function coefficient of~$x_i$) would need to {\it increase\/} by this amount in
order to make $x_i$ profitable enough to produce. Until the per-unit profit
increases this much, $x_i$~will still not be profitable enough, so the optimal
solution will not change.

\smallskip

\itemitem{--} Therefore, the {\bf maximum increase} to the objective function
coefficient of~$x_i$ (before the optimal solution changes) is given by the
value in the objective row in the $x_i$~column. There is {\bf no maximum
decrease}, i.e., there is no limit to the amount the coefficient can be
decreased.

\smallskip

\itemitem{--} Any change to the objective function coefficient of~$x_i$ that
does not exceed the maximum increase identified above will have {\it no
effect\/} on the optimal objective value or the optimal solution.

\medskip

\noindent If an objective function coefficient is changed by the maximum amount
indicated by sensitivity analysis, the optimal solution for the changed LP will
be {\bf non-unique}. (One of the numbers in the {\it objective row\/} of the
optimal tableau, in a nonbasic column, will be~0.)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bye
