
\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, 1994)}
\date{}
\maketitle
\large
\pagestyle{headings}

\newpage
\noindent
\underline{Duals of general LPs:}

\vspace{.2in}
\noindent
\underline{Motivation:} We have seen how to define the dual of an LP in standard
form. Our definition was motivated by the consideration that the dual objective
function value computed at any dual feasible solution is to be  an upper
bound for
the values that the primal objective function can assume at any feasible
solution.
The actual defintion was based on  the following observation.
Suppose that, for
$1\leq i\leq m$,  we assign a coefficient $y_{i}$ to the constraint
\begin{equation}\label{eqn1}
\displaystyle\sum_{j=1}^{n}a_{ij}x_{j}\leq b_{i}.
\end{equation}
If each $y_{i}$
is non-negative, then
\begin{equation}\label{eqn2}
(\displaystyle\sum_{j=1}^{n}a_{ij}x_{j})y_{i}\leq
b_{i}y_{i}.\end{equation}
By summing over $i,~1\leq i\leq m$, and changing the order
of summation, we get
$$\displaystyle\sum_{j=1}^{n}(\displaystyle\sum_{i=1}^{m}a_{ij}y_{i})x_{j}
        \leq \sum
b_{i}y_{i}.$$ So, if $c_{j}\leq \sum_{i=1}^{m}a_{ij}y_{i}$, for all $j$, then,
using the fact that all $x_{j}$ are non-negative, we would have $\sum
c_{j}x_{j}\leq
\sum b_{i}y_{i}$. This led us to the definition of the dual of an LP in standard
form.

In the above argument, it was crucial for the $y_{i}$ to be non-negative;
otherwise, (\ref{eqn2}) would not follow from (\ref{eqn1}).

Now suppose we have an LP in which all constraints (apart from
non-negativity of the variables) are equality constraints, say,
\begin{equation}\label{eqn3}
\displaystyle\sum_{j=1}^{n}a_{ij}x_{j}= b_{i}.
\end{equation}
We may multiply both sides by $y_{i}$ and obtain:
\begin{equation}\label{eqn4}
(\displaystyle\sum_{j=1}^{n}a_{ij}x_{j})y_{i}=
b_{i}y_{i}.\end{equation}
Note that in this case, it is not necessary for the $y_{i}$ to be
non-negative in
order for (\ref{eqn4}) to follow from (\ref{eqn3}).
Thus, in defining the dual of a general  LP, we are led to the principle
that if a
primal constraint is an equation, then the corresponding dual variable is
free or
unrestricted in sign. (And, similarly, if a primal variable is free, then the
corresponding dual constraint is an equation.) With this motivation, we can now
define the dual of any LP.



\vspace{.15in}
\noindent
\underline{Definition:} The dual of a general maximization (primal) LP is
defined as follows:

\[
\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&

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

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

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

                  &x_{j}                    &\mbox{free}&&j\in F&
&&\displaystyle\sum_{i=1}^{m}a_{ij}y_{i}&= c_{j}&j\in F&
\end{array}
\]
\noindent
\underline{Explanation:} Consider a maximization LP in which some
constraints (those
indexed by
$I$) are
($\leq$) inequalities, some constraints (those indexed by $E$) are
equations, some
variables (those indexed by $R$) are restricted to be non-negative, and some
variables (those indexed by $F$) are free or unrestricted in sign. The {\em
dual} of
such an LP is a minimization LP. There is a one-to-one correspondence between
the  primal constraints (those of
type`$\leq$' and those of type `$=$') and the dual variables, and there is a
one-to-one correspondence between the primal variables and the dual constraints.
The cost coefficients in the dual are the same as the right-hand side constant
terms from the primal constraints. The dual variables which correspond to the
primal inequality constraints are required to be non-negative, and the dual
variables which correspond to the primal equality constraints are free.
The dual constraints which correspond to the
primal restricted variables  are inequalities of type `$\geq$', and the dual
constraints which correspond to the primal free variables are equations.

\vspace{.1in}\noindent
\underline{Example:}
\[
\begin{array}{lrccrrrrrrr}
\underline{Primal}&&&&~&\hspace{.5in}&\underline{Dual}&&&&\\

\mbox{max }       &2x_{1}+3x_{2}+x_{3}&~&~&

&&\mbox{min}&4y_{1}+y_{2}&&&\\

\mbox{s.t.}       &x_{1}+x_{2}+x_{3}&\leq &4&&

&\mbox{s.t.}&y_{1}&\geq 0&&\\

                  &2x_{1}+3x_{2}-3x_{3}&=    &1&&
&&y_{2}&\mbox{free} &&\\

                  &x_{1}                    &\geq &     0&&

&&y_{1}+2y_{2}&\geq 2&&\\

                  &x_{2}                    &\mbox{free}&&&
&&y_{1}+3y_{2}&= 3&&\\
                  &x_{3}                    &\mbox{free}&&&
&&y_{1}-3y_{2}&= 1&&

\end{array}
\]

\noindent
\underline{Complementary Slackness Conditions for Optimality:} Suppose that
we are
given a primal feasible solution $x^{\ast}$ which is proposed as an optimal
solution. We would be able to prove that it is optimal, if we could produce
a dual
feasible solution $y^{\ast}$ such that $\sum
b_{i}y^{\ast}_{i}=c_{j}x^{\ast}_{j}$.
The complementary slackness conditions give us systematic way of searching for
such a  $y^{\ast}$.

The derivation of these conditions is based on the following simple identity:
\begin{eqnarray*}
\displaystyle\sum_{i=1}^{m}b_{i}y_{i}-\displaystyle\sum_{j=1}^{n}c_{j}x_{j} &=&
\displaystyle\sum_{i=1}^{m}b_{i}y_{i}-
\displaystyle\sum_{i=1}^{m}(\displaystyle\sum_{j=1}^{n}a_{ij}x_{j})y_{i}+
\displaystyle\sum_{j=1}^{n}(\displaystyle\sum_{i=1}^{m}a_{ij}y_{i})x_{j}-
\displaystyle\sum_{j=1}^{n}c_{j}x_{j}
\end{eqnarray*}
or,
\begin{eqnarray*}
\displaystyle\sum_{i=1}^{m}b_{i}y_{i}-\displaystyle\sum_{j=1}^{n}c_{j}x_{j}
&=&\displaystyle\sum_{i=1}^{m}(b_{i}-\displaystyle\sum_{j=1}^{n}a_{ij}x_{j})
y_{i}+
\displaystyle\sum_{j=1}^{n}(\displaystyle\sum_{i=1}^{m}a_{ij}y_{i}-c_{j})x_{j}
\end{eqnarray*}

 If $x=x^{\ast}$ and $y=y^{\ast}$ are feasible solutions for  the  primal
and the
dual, respectively, then, it is easy, as explained in class, to see that
the above
expression is non-negative. The following conditions, known as the complementary
slackness conditions, are the necessary and sufficient for the
above expression is zero (which is precisely when we have $\sum
b_{i}y^{\ast}_{i}=\sum c_{j}x^{\ast}_{j}$).

\begin{eqnarray}
\displaystyle\sum_{j=1}^{n}a_{ij}x^{\ast}_{j}\leq
b_{i}&\Rightarrow&y^{\ast}_{i}=0\\
x^{\ast}_{j}>0&\Rightarrow&\displaystyle\sum_{i=1}^{m}a_{ij}y^{\ast}_{i}=c_{j}
\end{eqnarray}

If a given primal feasible solution $x^{\ast}$ were optimal, there would have to
exist a dual feasible solution $y^{\ast}$, such that $x^{\ast}$ and $y^{\ast}$
together satisfy the conditions (5) and (6).

\vspace{.2in}
\noindent
{\bf Exercises:}

\vspace{.1in}
\noindent
(1) Consider the LP:
\[\begin{array}{lrcrcrcr}
\mbox{max } & 2x_{1}&+& 3x_{2} &+& x_{3}&      &   \\
\mbox{s.t. }&  x_{1}&+&  x_{2} &+&  x_{3}& \leq & 4  \\
            &  x_{1}&+&  x_{2} &-&  x_{3}& \leq & 2 \\
            &  x_{1}&,&   x_{2}&,&  x_{3}& \geq & 0
\end{array}\]
\begin{enumerate}
\item[(a)]
Is there an optimal solution
$x^{\ast}=(x^{\ast}_{1},x^{\ast}_{2},x^{\ast}_{3})$ to
this LP in which both $x^{\ast}_{1}$ and $x^{\ast}_{2}$ are strictly positive?

\item[(b)]
Is $x^{\ast}=(3,0,1)$ an optimal solution to the LP?

\item[(c)]
Is $x^{\ast}=(0,3,1)$ an optimal solution to the LP?
\end{enumerate}

\vspace{.1in}
\noindent
(2) Consider the LP:
\[\begin{array}{lrcrcrcrcr}
\mbox{max } & 2x_{1}&+& 3x_{2} &+& 3x_{3}&+& x_{4}&      &   \\
\mbox{s.t. }&  x_{1}&+&  x_{2} &+& 2x_{3}&+& x_{4}& \leq & 5  \\
            &  x_{1}&+&  x_{2} &+& 2x_{3}&-& x_{4}& \leq & 4 \\
            & 2x_{1}&+&  x_{2} &+& 2x_{3}&+& x_{4}& \leq & 11 \\
            &  x_{1}&,&   x_{2}&,&  x_{3}&,& x_{4}&\geq & 0
\end{array}\]
\begin{enumerate}
\item[(a)]
Is $x^{\ast}=(1,0,1,2)$ an optimal solution to the LP?

\item[(b)]
Is $x^{\ast}=(0,\frac{9}{2},0,\frac{1}{2})$ an optimal solution to the LP?
\end{enumerate}

(3) Consider the LP:
\[\begin{array}{lrcrcrcr}
\mbox{max } & 2x_{1}&+& 3x_{2} &+& x_{3}&      &   \\
\mbox{s.t. }&  x_{1}&+&  x_{2} &+&  x_{3}& \leq & 4  \\
            &  x_{1}&+&  x_{2} &+&  x_{3}& \leq & 6 \\
            &       & &   x_{2}&,&  x_{3}& \geq & 0
\end{array}\]
($x_{1}$ free.) Is there an optimal solution $y^{\ast}$ to the of this LP
in which
both $y^{\ast}_{1}$ and $y^{\ast}_{2}$ are strictly positive?

~~\\
~~\\

{\bf About the midterm:} \underline{Computational skills:} Simplex method
(chapter 2). Phase 1, phase 2 (chapter 2)- you should know how to formulate
the auxiliary problem and solve it (phase 1), and should know how to obtain
the initial dictionary for phase 2 from the final dictionary of phase 1
(study the example on pages 39-41). Pivot rules for avoiding cycling.
Writing duals of LPs (for LPs in standard form as well as general LPs).
Reading  an optimal solution to the dual from the final dictionary.  Using
complementary slackness  (economic interpretation).

\underline{Definitions:} You should learn all important definitions.

\underline{Theorems:} You should be able to state all theorems, and have an
intutive grasp of their meaning, significance, and proof technique. You
should know how to derive simple consequences of theorems.







\end{document}




