\documentstyle[12pt]{article}
%
\def\baselinestretch {1.3}
\oddsidemargin 0.5cm
\textwidth 6in
\topmargin -0.5cm
\textheight 8.5in
\pagestyle{empty}
%
\pagestyle{empty}
\newtheorem{prop}{Proposition}[section]
\newtheorem{theorem}[prop]{Theorem}
\newtheorem{cor}[prop]{Corollary}
\newtheorem{lemma}[prop]{Lemma}
\newcommand{\myline}{\noindent \rule{\textwidth}{.02in} \medskip}
\newcommand{\matchings}{\noindent {\bf Matching Polyhedra} \medskip}
%
\newcommand\blackslug{\hbox{\hskip 1pt \vrule width 4pt height 8pt depth 1.5pt
        \hskip 1pt}}
  
\newenvironment{proof}{{\bf Proof:\ }}{{\quad\blackslug\medbreak}}
\newcommand{\oofx}{{\quad\blackslug\medbreak}}
\newcounter{ex}[section]
\newcommand{\ex}[1]{\refstepcounter{ex}\item[\thesection.\theex.]\label{#1}}
%
\def\minimize{\rm minimize}
\def\maximize{\rm maximize}
\def\R{{\bf R}}
\def\Z{{\bf Z}}
\def\bs{\backslash}
\newcommand{\ssp}{\renewcommand{\baselinestretch}{1}\large\normalsize}
\newcommand{\dsp}{\renewcommand{\baselinestretch}{1.5}\large\normalsize}
\begin{document}
                                                           
\centerline{\bf C\&O 350 Assignment 1, due Thursday, January 18, 1996}
\bigskip
\begin{enumerate}
\item
Later in the course, we will show that every l.p. problem has exactly one of the
following properties: it has an optimal solution, it has no
feasible solution, or it is unbounded. For each of the following problems, explain
why it is not an l.p. problem, and show that it has
none of the  above	properties:
\begin{enumerate}
\item [(a)] minimize $x_1$ subject to $x_1>0$
\item[(b)] minimize $e^{-x_1}$ subject to $x_1\geq 0$
\end{enumerate}
\item 
\begin{enumerate}
\item[(a)] Convert to standard form:
\begin{eqnarray*}
\mbox{minimize } -x_1+x_2&&\\
\mbox{subject to}&&\\
2x_1+x_2&=&2\\
x_1&\geq& 0
\end{eqnarray*}
\item [(b)] Convert to standard equality form:
\begin{eqnarray*}
\mbox{minimize } -x_1+x_2&&\\
\mbox{subject to}&&\\
x_1+x_2&\geq& 3\\
2x_1+x_2&\leq& 5\\
x_1, x_2& \geq& 0
\end{eqnarray*}
\end{enumerate}
\item
Given $(a_{ij})$, ($i=1,\ldots,m$), ($j=1,\ldots,n$), and $b_i$,
($i=1,\ldots,m$), we want to find $x_j$, ($j=1,\ldots,n$), so that
$$\max_{i=1,\ldots,m} |\sum_{j=1}^na_{ij}x_j-b_i|$$
is as small as possible. Why is this not (as it stands)
a linear programming problem?
Formulate an l.p. problem whose solution does solve the problem.
\item
Where $s$ is a parameter, consider the l.p. problem
\begin{eqnarray*}
\mbox{maximize } x_1-2x_2&&\\
\mbox{subject to}&&\\
-x_1+x_2&\leq& -2\\
sx_1-x_2&\leq& 0\\
x_1, x_2& \geq& 0
\end{eqnarray*}
\begin{enumerate}
\item [(a)] For what values of $s$ does the problem have a feasible solution?
You may use geometry, but give an algebraic explanation too.
\item [(b)] For what values of $s$ is the problem unbounded? You may use
geometry, but try to give an algebraic explanation too.
\end{enumerate}
\item Solve problem 2.1(a) of Chv\'atal by the simplex method.

% For problem 2.1(a) of Chv\'atal, add slack variables $x_4,x_5,x_6$
%to put it into equality
%form. Then use elementary row operations to find the tableau for each of the
%following bases: (i) $\{4,5,6\}$, (ii) $\{1,2,5\}$, (iii) $\{1,3,6\}$,
%(iv) $\{3,4,5\}$. For each, write the corresponding
%dictionary, state the basic solution, and tell whether the solution is
%feasible. Is any of the solutions optimal? Explain.
\end{enumerate}
\end{document}

