\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}

\newpage
\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 cosntraint in the
primal.

\end{document}

