% \documentstyle[12pt,fullpage]{article}
% \documentstyle[11pt]{siam}
% \setlength{\textheight}{9.20in}
% \setlength{\textwidth}{7.00in}

% from stoc-94.tex
\documentstyle[12pt,twocolumn]{article}
\clubpenalty 10000
\widowpenalty 10000
\topmargin -1.2cm
\oddsidemargin -0.4cm
% \textheight 8.625in
\textheight 8.800in
\textwidth 7.26in
\columnseprule .2mm
\columnsep .5in
% \parindent=0pt
\sloppy

% \setlength{\leftmargin}{1cm}
% from stoc-94.tex

\pagestyle{empty}

\input{mssymb}

\def\ov#1{\overline{#1}}
\def\wt#1{\widetilde{{#1}}}
\def\mbe{\mbox{\bf e}}
\def\noi{\noindent}
\newcommand{\alg}[1]{\newline\parbox{#1cm}{\ }}

\begin{document}

\begin{minipage}{\textwidth}
% \begin{center}
% {{\Large\bf C\&O 350~~~~~Linear Programming}}
% \end{center}
% \vspace{0.10in}
\vspace{-0.6in}
\begin{center}
{{\large\bf Sensitivity Analysis}}
\end{center}
\vspace{0.10in}
\end{minipage}

Suppose that the optimal solution of a given LP problem
\[ \mbox{(P) \quad\quad maximize~~} cx, \mbox{~subject to~} Ax=b,~~ x\ge 0,
\]
is available, and that {\it one} of the following modifications
is made to the problem data:
\begin{enumerate}
\item
The coefficient of a nonbasic variable in the objective function is changed.
\item
The coefficient of a basic variable in the objective function is changed.
\item
A new variable is added.
\item
A component $b_i$ of the right hand side $b$ is changed.
\item
A new constraint is added.
\end{enumerate}
%
The goal is to solve the new LP problem starting
from the optimal solution of the original LP problem,
{\it without} starting from scratch.

\medskip

Let $A$ be an $m \times n$ matrix, and let
the $j$th column of $A$ be denoted $A_j$.
Let $B$ denote the basis heading of  an optimal basic solution of (P),
and let $A_B$ be the basis matrix.
Let $N$ denote $\{1,\ldots,m\} \backslash B$, and
let $A_N$ be the matrix formed by $\{A_j : j\in N\}$.
Recall that
\[ x_B^*=A_B^{-1} b, \quad\quad y= c_B A_B^{-1}, \quad \mbox{~~and~~}
\]
\[ \ov{c}_N= c_N - c_B A_B^{-1} A_N.
\]

We assume that all variables are nonnegative;
free variables can be handled by an extension of the
methods given here.

\medskip

Two types of questions arise:
\\
(Q1)~~ Suppose that {\it one} item in the problem data is
chosen to be a (changeable) parameter.
What is the range of values for the changing parameter
such that the old optimal basis continues to be optimal
for the new LP?
\\ \\
(Q2)~~ Solve the new LP, i.e.,
either find an optimal solution for the new LP,
or report that the new LP is unbounded,
or report that the new LP is infeasible.

\bigskip
\hrule
\medskip

\noi
({\bf 1})
Changing the coefficient of a nonbasic variable in the objective
function.

Suppose that the coefficient of the nonbasic variable
$x_k$ in the objective function is changed
from $c_k$ to $\wt{c}_k$.

\smallskip

\noi
Answering (Q1):
\\
If the old optimal basis heading $B$ is to remain
optimal for the new LP,
then the new reduced cost of $x_k$,
which is given by the formula
\[ \ov{c}_k^{new} = \wt{c}_k - y A_{k},
\]
must be nonpositive.
Clearly, if $\wt{c}_k \le y A_k$,
then $\ov{c}_k^{new}$ is nonpositive,
and so the old optimal basis heading $B$ remains optimal
for the new LP.

\smallskip

\noi
Answering (Q2):
\\
If $\wt{c}_k > y A_k$,
then the old optimal basis heading $B$ is {\bf not} optimal
for the new LP.
In order to find a new optimal basis,
we do a simplex pivot
(this is the pivot introduced in Chapter~2)
with $x_k$ as the entering variable,
and continue doing simplex pivots
until either we find an optimal basis for the new LP
(i.e., until $\ov{c}_j \le 0$ for all nonbasic $j$)
or we find the new LP to be unbounded.

\bigskip
\hrule
\medskip

\noi
({\bf 2})
Changing the coefficient of a basic variable in the objective function.

Suppose that the coefficient of the basic variable
$x_h$ in the objective function is changed
from $c_h$ to $\wt{c}_h$.

\smallskip

\noi
Answering (Q1):
\\
If the old optimal basis heading $B$ is to remain
optimal for the new LP,
then the new reduced cost of each nonbasic variable
must remain nonpositive.
That is, we must have
\[ \ov{c}_N^{new}  = c_N - c_B^{new} A_B^{-1} A_N \le 0.
\]
The nonpositivity of each nonbasic variable $x_j$ may
impose a constraint on the value of $\wt{c}_h$, since we must have
\[ \ov{c}_j = c_j - c_B^{new} A_B^{-1} A_j \le 0.
\]
Taking the most stringent upper bound and lower bound on $\wt{c}_h$
from among all these constraints gives
a range of values for $\wt{c}_h$,
and this is the answer.

\smallskip

\noi
Answering (Q2):
\\
If $\wt{c}_h$ falls outside the above range,
then the old optimal basis heading $B$ is {\bf not} optimal
for the new LP since some $j\in N$ has $\ov{c}_j > 0$.
In order to find a new optimal basis,
we do a simplex pivot,
and continue doing simplex pivots
until either we find an optimal basis for the new LP
(i.e., until $\ov{c}_j \le 0$ for all nonbasic $j$)
or we find the new LP to be unbounded.

\bigskip
\hrule
\medskip

\noi
({\bf 3})
Adding a new variable.

Suppose that a new variable $x_{\ell}$, $x_{\ell} \ge 0$,
has to be added to the LP,
where $c_{\ell}$
(the coefficient of $x_{\ell}$ in the objective function)
and $A_{\ell}$ are given to us.

First, check whether the old optimal basis heading $B$
remains optimal for the new LP
by computing
\[ \ov{c}_{\ell} = c_{\ell} - y A_{\ell}.
\]
If $\ov{c}_{\ell}$ is nonpositive,
then the old optimal basis remains optimal for the new LP.
If $\ov{c}_{\ell}$ is positive,
then the old optimal basis is {\bf not} optimal for the new LP.
Therefore we do a simplex pivot
with $x_{\ell}$ as the entering variable,
and continue doing simplex pivots
until either we find an optimal basis for the new LP
% (i.e., until $\ov{c}_j \le 0$ for all nonbasic $j$)
or we find the new LP to be unbounded.

\bigskip
\hrule
\medskip

\noi
({\bf 4})
Changing $b$ to $\wt{b}$ by changing $b_i$ to $\wt{b}_i$.

The new basic solution given by the old optimal basis heading $B$ is
\[ x_B^{*~new} = A_B^{-1} \wt{b}.
\]

\noi
{\sc Exercise}.
If $\wt{b}_i = b_i + \Delta$, then shown that
the new basic solution is given by
\[ x_B^{*~new} = x_B^{*~old} + \Delta (\mbox{$i$~th col in~} A_B^{-1}).
\]

\noi
Answering (Q1):
\\
If the old optimal basis heading $B$ is to stay optimal
after changing $b_i$ to $\wt{b}_i$,
then we must have $x_B^{*~new} \ge 0$.
The nonnegativity of each component of $x_B^{*~new}$ may impose
a constraint on $\wt{b}_i$.
Taking the most stringent upper bound and lower bound on $\wt{b}_i$
from among these $m$ (or fewer) constraints gives
a range of values for $\wt{b}_i$,
and this is the answer.

\smallskip

\noi
Answering (Q2):
\\
If $\wt{b}_i$ falls outside the above range,
then $x_B^{*~new}$ is not a {\it feasible} solution and
the old optimal basis heading $B$ is {\bf not} optimal
for the new LP.
We need the {\bf dual} simplex method to proceed.
We do a {\bf dual} simplex pivot,
and continue doing {\bf dual} simplex pivots
until either we find an optimal basis for the new LP
(i.e., until $x_h^{*} \ge 0$ for all basic $h$)
or we find the new LP to be infeasible.

\bigskip
\hrule
\medskip

\noi
({\bf 5})
Adding a new constraint.

Suppose that the constraint
\[ \sum_{j=1}^{n} a_{gj} x_j \le b_g
\]
has to be added to the LP.
First, we introduce a slack variable
$x_{n+1}$, $x_{n+1} \ge 0$,
and obtain the equality constraint
\[ x_{n+1} = b_g - \sum_{j=1}^{n} a_{gj} x_j.
\]
In order to add this equality constraint
to the optimal dictionary (or basis) of our example LP,
we substitute the basic variables $x_h$, $h\in B$,
by their equations in the old optimal dictionary
to get an  equivalent constraint.
Then, we add the new equality constraint
as a new row in the old optimal dictionary.

The resulting dictionary is dual feasible.
If the resulting dictionary is {\bf not} feasible, then
we do {\bf dual} simplex pivots until either
we find an optimal dictionary for the new LP
or we find that the new LP is infeasible.

\bigskip
\hrule
\end{document}