\documentstyle[11pt]{article}
\oddsidemargin 0.0in
\evensidemargin 0.0in
\textwidth 6.75in
\addtolength{\topmargin}{-.5in}
\addtolength{\textheight}{1in}
\newtheorem{thm}{\mbox{}}

\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}
\begin{center}
\underline{{\bf C \& O 350 \hspace{1.6in} Assignment 1 \hspace{1.6in} Due
28th September}}
\end{center}

\vspace{.2in}
\noindent
(1) Formulate  problem 1.6 in Chv\'{a}tal as an LP.

\vspace{.2in}
\noindent
(2) Picture the feasible region of the following LP:
\[\begin{array}{lrcrcrcr}
\mbox{max } & 3x_{1}&+&4x_{2}&+&6x_{3} &      &   \\
\mbox{s.t. }& x_{1}&+&2x_{2}&+&4x_{3} &= &24  \\

            &x_{1}  &,&   x_{2}&,& x_{3}& \geq & 0
\end{array}\]
Guess the optimal solution without doing any elaborate calculations. (Hint:
the optimal
solution is at one of the `corners' of the feasible region.)

\vspace{.2in}
\noindent
(3) (a) Define precisely what it means to say that an LP is unbounded.

    (b) Show that the following LP is unbounded as per your definition.

\[\begin{array}{lrcrcrcrcr}
\mbox{max } &      & &        & &4x_{3} &-&x_{4} &      &   \\
\mbox{s.t. }& x_{1}& &        &-&  x_{3}&+& 9x_{4}& = & 4  \\
            &      &+&  x_{2} &-&  x_{3}&+& 3x_{4}& = & 3 \\
            &x_{1}  &,&  x_{2} &,& x_{3} &,&  x_{4}& \geq & 0
\end{array}\]
Hint: Note that $x_{1}$ and $x_{2}$ may be expressed in terms of $x_{3}$
and $x_{4}$.
Find suitable feasible solutions by choosing appropriate values for $x_{3}$ and
$x_{4}$, and computing the values of $x_{1}$ and $x_{2}$ based on them.

\vspace{.2in}
\noindent
(4) Solve the LP in problem 2.1 (a) of Chv\'{a}tal by the simplex method.


\vspace{.2in}
\noindent
(5) Do problem 2 on page 12 of the handout.

\vspace{.2in}
\noindent
(6) If ${\bf x}_{1}$ and ${\bf x}_{2}$ are two feasible solutions to an LP, and
$\lambda$ is any real number such that $0\leq\lambda\leq1$, then ${\bf
x}=\lambda{\bf
x}_{1}+(1-\lambda){\bf x}_{2}$ is also a feasible solution to the LP. (You
may, if you
like, assume that the given LP is an equality LP.)


\vspace{.2in}
\noindent
(7)$^{\ast}$ For each of the following statements, either give a proof of
the  statement,
or give a counter-example to show that the statement is false.
\begin{enumerate}
\item
An LP is  has no optimal solution, or has exactly one optimal solution, or has
infinitely many different optimal solutions.
\item
If the feasible region of an LP is unbounded, then the LP is unbounded.
\end{enumerate}







\end{document}




--========================_24179756==_--


