%  Problem set 2
%  Combinatorial Optimization, SUAMI, summer 2015
%  Brian Kell <bkell@cmu.edu>

\pdfpagewidth=8.5truein \pdfpageheight=11truein
\hsize=5.5truein \vsize=9truein
\pdfhorigin=1.5truein \pdfvorigin=1truein

% AMSFonts
\input amssym.tex

\font\titlefont=cmbx12  \font\smfont=cmr8

\headline={\hfil}
\footline={\hfil}

\newcount\pno \pno=0
\def\problem{\global\advance\pno by1%
	\medbreak\noindent{\llap{\bf\the\pno.\enspace}}\ignorespaces}
\def\solution{\medskip\noindent{\bf Solution.}\enspace\ignorespaces}

\def\R{{\mathord{\Bbb R}}}
\def\transpose{{\rm T}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\centerline{\titlefont Combinatorial Optimization}
\smallskip
\centerline{\bf Problem set~2}
\smallskip
\centerline{Assigned Monday, June~1, 2015. Due Thursday, June~4, 2015.}

\medskip

\problem Consider the following two linear programs in standard form:
$$\eqalign{
	{\rm maximize}\quad c^\transpose x&\cr
	{\rm subject\ to}\quad\phantom{c^\transpose}\llap{$A$}x&=b\cr
	x&\ge0\cr
}\qquad\qquad\qquad\qquad\eqalign{
	{\rm maximize}\quad{-}c^\transpose x&\cr
	{\rm subject\ to}\quad\phantom{-c^\transpose}\llap{$A$}x&=b\cr
	x&\ge0\cr
}$$
Can both of these linear programs have feasible solutions with arbitrarily
large objective value? If yes, give an example; if not, prove so.

\problem In class we saw an example that served as a sketch of a proof of the
following theorem:

{\medskip\narrower\proclaim Theorem. Let $x$ be a feasible solution to a
maximizing linear program (in standard form). Then either there exists a basic
feasible solution whose objective value is at least as large as that of~$x$, or
else the linear program is unbounded.\par}

\noindent Using the example as a guide, prove this theorem.

\problem Convert the following linear program to standard form. Write the
initial simplex tableau and give the initial basic feasible solution. Do a
pivot to bring $x_2$ into the basis and give the resulting basic feasible
solution.
$$\eqalign{
	{\rm maximize}\quad5x_1+3x_2-2x_3&\cr
	{\rm subject\ to}\quad\phantom1x_1+2x_2+\phantom1x_3&\le10\cr
	4x_1+5x_2\phantom{{}+0x_3}&\le20\cr
	2x_1-3x_2+2x_3&\le\phantom06\cr
	&\phantom{{}=00}\llap{$x_1\ge0$,\quad$x_2\ge0$,\quad$x_3\ge0$}.\cr
}$$

\problem Answer yes or no and prove your answer: Can a pivot move the
corresponding basic feasible solution a positive distance in~$\R^n$ while
leaving the objective value unchanged?

\problem Solve the following linear program by hand, using the simplex
algorithm.
$$\eqalign{
	{\rm maximize}\quad20x_1+6x_2+8x_3&\cr
	{\rm subject\ to}\quad\phantom06x_1+2x_2+3x_3&\le420\cr
	4x_1+3x_2\phantom{{}+0x_3}&\le200\cr
	x_3&\le\phantom050\cr
	&\phantom{{}=000}\llap{$x_1\ge0,\quad x_2\ge0,\quad x_3\ge0$}.\cr
}$$

\vfill\eject

\problem Consider the following simplex tableau (for the maximizing simplex
algorithm).
$$\vbox{\offinterlineskip
\halign{\quad\hfil\strut$#$&\quad\hfil\strut$#$&\quad\hfil\strut$#$%
	&\quad\hfil\strut$#$&\quad\hfil\strut$#$&\quad\hfil\strut$#$%
	&\quad\hfil\strut$#$&\quad\hfil\strut$#$\quad&\vrule#%
	&\quad\hfil\strut$#$\quad\cr
x_1&x_2&x_3&s_1&s_2&s_3&s_4&z&\omit&\hbox{\smfont RHS}\cr
\noalign{\vskip2pt}
a_1&0&0&0&40&0&25&1&&700\cr
\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&height2pt\cr
\noalign{\hrule}
\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&height2pt\cr
a_2&0&0&1&1/2&0&-2&0&&84\cr
a_3&1&0&0&-2&0&5/2&0&&225\cr
a_4&0&1&0&3/2&0&1/2&0&&125\cr
a_5&0&0&0&-5/2&1&-3/2&0&&65\cr}}$$
For each part below, describe conditions on the entries $a_1$,~\dots,~$a_5$ in
the first column so that the tableau satisfies the stated condition. Try to
make your answers as general as possible.

\smallskip

\item{(a)} The corresponding basic feasible solution is optimal and unique.

\smallskip

\item{(b)} The corresponding basic feasible solution is optimal but not
unique, and $x_1=13$ in the alternative optimal basic feasible solution.

\smallskip

\item{(c)} The corresponding basic feasible solution is not optimal, and in the
next basic feasible solution (that~is, the basic feasible solution
corresponding to the tableau after the next pivot in the simplex algorithm),
$s_1=0$ and the value of the objective function is~742.

\smallskip

\item{(d)} The corresponding basic feasible solution is not optimal, and in the
next basic feasible solution $x_3=0$ and $s_3=40$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bye
