\baselineskip=15pt
\lineskip=1.5pt
\lineskiplimit=1pt
\nopagenumbers
\magnification=\magstep1
\hsize=6.1truein
\mathsurround=1pt
\vglue 0pt plus 1 fill
\tolerance=10000
\vskip -.5in
\centerline {\bf MATHEMATICAL PROGRAMMING}
\smallskip
\noindent
\centerline {\bf Depth Exam:  Answer any 6 of the following 8 questions}
\centerline {\bf Breadth Exam:  Answer any 3 of the following 8 questions}

\vskip 0.4in
\item{1.}
Solve by the simplex method the following Linear Programming Problem:
$$\matrix{ \hbox{\rm max}  & {\hskip -2cm }-4x_2 -2x_3-7x_4\cr \cr
 \hbox{\rm s.t.}          &
{\matrix{ 2x_1 & + & x_2 & + & x_3 & + & 3x_4 &= &3\cr
         x_1 &-  & x_2 &   &     & + &x_4  &\le & 1\cr
          2x_1& + & 2x_2&   &     & + &4x_4&\le & 3\cr}}\cr
               & x_i\ge 0\quad i=1,\ldots,4\cr}$$
\bigskip
\noindent
\item {}
\hangindent=49pt
\hangafter=1
Hint:  Start with $x_3$ as a basic variable even though it also occurs in the
objective function.
\bigskip
\bigskip
\item{3.}
Let $f: R^n\rightarrow R$ be a differentiable convex function on $R^n$
and let $x^1,\ldots,x^k$ be $k$ points in $R^n$ such that for some $\bar
u\in R^k:$
$$\sum_{i=1}^k\,\bar u_i\nabla f(x^i)=0,\;\,\sum_{i=1}^k\,\bar
u_i=1,\;\,\bar u\ge 0$$
Give a lower bound to $\displaystyle\inf_{x\in R^n}\,f(x)$ in terms of
$x^1,\ldots,x^k$ and
$\bar u$.
\vfill
\eject
\bye
\bigskip
\bigskip
\noindent
\item{6.}
Suppose that $G$ is a directed graph consisting of $n$ nodes and $K$
(connected) components.  Prove that the rank of the corresponding
node-arc incidence matrix is $n-K$.
\bigskip
\bigskip
\medskip
\item{7.}
Consider the integer program
$$\eqalign {{\min_{x}}\quad &cx\cr
\rm {s.t.}\quad&Ax=b\cr
&x_i=0\;{\rm or}\; 1\quad\;(i=1,\ldots,n)\cr}\leqno(IP)$$
Assuming (IP) is feasible, prove that for sufficiently large $M,$ every
optimal solution of (IP) is also an optimal solution of
$$\eqalign {{\min_{x}}\quad &cx +M\sum\,x_i(1-x_i)\cr
\rm {s.t.}\quad&Ax=b\cr
&0\le x_i\le1\quad\;(i=1,\ldots,n).\cr}\leqno(NLP)$$
\bigskip
\bigskip
\item{8.}
Consider the function $f:[0,2]\rightarrow{\rm I\!R}$ defined by
$$f(x):=\cases{0&if\quad $x=0$\cr a&if\quad $x\in (0,1]$\cr
bx+c&if\quad $x\in(1,2]$\cr}$$
where $a,b$ and $c$ are real numbers.  Determine conditions on $a,b$
and $c$ such that
\smallskip
\itemitem{(a)}
there exists a Linear Program Minimization Model for $f(x)$ on $[0,2]$;
\smallskip
\itemitem{(b)}
there exists a Mixed Integer Minimization Model for $f(x)$ on $[0,2]$.
\bigskip
\item{}
Write a Mixed Integer Minimization Model for $f(x)$ on $[0,2]$ (under
conditions found in (b)).
\def\br{{\bf R}}
\def\dom{\hbox{\rm dom}\,}
\def\inf{\hbox{\rm inf}\,} 
\def \endstate {\vrule height8pt width3pt depth0pt\medbreak}
\def\ri{\hbox{\rm ri}\,}
\def\subpar{\hfill\break\indent\indent}
\centerline {\bf Convex programming question Spring 90}
\bigskip
\bigskip
Suppose $f$ is a closed proper convex function on $\br^n$, and
let $K$ be a nonempty closed convex cone, also in $\br^n$. Consider the
primal problem of minimizing $f$ on $K$. Using the duality
structure given by
$$F(x,p)=\cases{f(x)&if $x\in K+p$,\cr +\infty&otherwise,\cr}$$
obtain the Lagrangian and the dual objective function for
this problem in the simplest practical form. Also prove that
the dual problem has a maximum (attained) if
$$\ri K\cap\ri\dom f\neq\emptyset.$$

\vfill \eject
\end

\vfill
\eject
\bye