\documentstyle[12pt]{article}
\oddsidemargin 0.0in
\evensidemargin 0.0in
\textwidth 6.5in
\addtolength{\topmargin}{-.5in}
\addtolength{\textheight}{1in}

\newcommand{\A}{\mbox{\bf A}}
\newcommand{\B}{\mbox{\bf B}}
\newcommand{\C}{\mbox{\bf C}}
\newcommand{\Q}{\mbox{\bf Q}}
\newcommand{\R}{\mbox{\bf R}}
\newcommand{\Z}{\mbox{\bf Z}}
\newcommand{\qed}{\hfill\rule{2.5mm}{2.5mm}}

\begin{document}
\title{C and O 350}
\author{(11 October, 1995)}
\date{}
\maketitle
\large
\pagestyle{headings}

\noindent
\underline{Sensible Rules for Remembering Duals - The S-O-B Method}

\vspace{.2in}

This is motivated by the paper by Arthur T. Benjamin, in SIAM Review,
Vol 37, No 1, 1995. He presents ``a natural motivation and simple
mnemonic for creating the dual LP of any linear programming problem.''



Consider the following general primal and dual LP.

\[
\begin{array}{lccccccrrrr}
\underline{Primal}&&&&~&\hspace{.5in}&\underline{Dual}&&&&\\

\mbox{max }       &\displaystyle\sum_{j=1}^{n}c_{j}x_{j}&~&~&

&&\mbox{min}&\displaystyle\sum_{i=1}^{m}b_{i}y_{i}&&&\\

\mbox{s.t.}       &\displaystyle\sum_{j=1}^{n}a_{ij}x_{j}&\leq &b_{i}&i\in I_L&

&\mbox{s.t.}&y_{i}&\geq 0&i\in I_L&\\

       &\displaystyle\sum_{j=1}^{n}a_{ij}x_{j}&\geq &b_{i}&i\in I_G&

&&y_{i}&\leq 0&i\in I_G&\\

                  &\displaystyle\sum_{j=1}^{n}a_{ij}x_{j}&=    &b_{i}&i\in E&
&&y_{i}&\mbox{free} &i\in E&\\

                  &x_{j}                    &\geq &     0&j\in R_G&

&&\displaystyle\sum_{i=1}^{m}a_{ij}y_{i}&\geq c_{j}&j\in R_G&\\

                  &x_{j}                    &\leq &     0&j\in R_L&

&&\displaystyle\sum_{i=1}^{m}a_{ij}y_{i}&\leq c_{j}&j\in R_L&\\

                  &x_{j}                    &\mbox{free}&&j\in F&
&&\displaystyle\sum_{i=1}^{m}a_{ij}y_{i}&= c_{j}&j\in F&
\end{array}
\]

To remember the above rules for constructing the dual, we begin by
labelling each variable of the LP as {\em Sensible, Odd}, or {\em Bizarre},
depending on whether it is non-negative, unrestricted, or non-positive.
Next we label the constraints of the LP. A problem of minimizing costs
is typically constrained by meeting or exceeding stipulated demands.
Thus
we define 
$\geq$ constraints as sensible,
$=$ constraints as odd,
$\leq$ constraints as bizarre.
Similarly, a problem of maximizing some objective (like profit) is
typically constrained by upper bounds on available resources. Thus, for
a maximization problem, we define
$\leq$ constraints as sensible,
$=$ constraints as odd,
$\geq$ constraints as bizarre.

Now one has to remember that a constraint in the dual is sensible (S),
odd (O), or bizarre (B), if the corresponding variable in the primal is
sensible, odd, or bizarre. Likewise, the ``sensible-ness'' of each dual
variable is the same as that of its corresponding constraint in the
primal.

Another way to remember is to check the shadow price interpretation of
the variables. Recall that the variables in the primal are shadow prices
for the constraints in the dual; while the variables in the dual are
shadow prices for the constraints in the primal.
\begin{enumerate}
\item
$x_j \geq 0, ~j \in R_G,$ indicates that the objective value of the dual
cannot decrease if $c_j,  ~j \in R_G,$ increases (marginally). This is in
fact true, since the feasible set does not get larger for the $\geq$
constraint.
\item
$x_j \leq 0, ~j \in R_L,$ indicates that the objective value of the dual
cannot increase if $c_j,  ~j \in R_L,$ increases (marginally). This is in
fact true, since the feasible set does not get smaller for the $\leq$
constraint.
\item
Freedom and equality go together, i.e. free variables correspond to
equality constraints. Note that for equality constraints, changes in the
right-hand-side can result in an increase or decrease of the size of the
feasible set.
\end{enumerate}
Similar arguments can be stated for the variables in the dual and the
constraints in the primal. Note that the objective function in the
primal cannot increase if the feasible set gets smaller, while the
objective function in the dual behaves in the opposite way.


\end{document}

