% Problem set 3
% Combinatorial Optimization, SUAMI, summer 2015
% Brian Kell
\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~3}
\smallskip
\centerline{Assigned Thursday, June~4, 2015. Due Monday, June~8, 2015.}
\bigskip
\noindent For your convenience, a tool to help with pivoting simplex tableaux
is available online at {\tt http://www.math.cmu.edu/\char`~bkell/pivot.html}.
\medskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem In class (and on the ``Analysis of a simplex tableau'' handout), I
claimed that if a simplex tableau (for a non-degenerate linear program)
contains a column having a negative entry in the objective row and no positive
entries below, then the linear program is unbounded. Prove this claim.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem Here is a shortcut for determining the entries in the artificial
objective row in an initial (two-phase) simplex tableau:
\smallskip
\item{1.} Fill in the entries in the objective row and the rows that come from
the constraints.
\smallskip
\item{2.} In the columns for artificial variables, enter zeroes in the
artificial objective row. (Also, if you are including the $-\xi$~column, enter
1 in that column in the artificial objective row.)
\smallskip
\item{3.} In every other column, compute the sum of the entries in the rows
that come from constraints having artificial variables (i.e., the rows that
come from $\ge$~and~$=$ constraints). Negate this sum and enter it in the
artificial objective row.
\smallskip
\noindent Justify this shortcut.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem Solve the following linear program by hand, using the two-phase
simplex algorithm.
$$\eqalign{
{\rm maximize}\quad3x_1-8x_2+10x_3&\cr
{\rm subject\ to}\quad\phantom2x_1+\phantom1x_2+\phantom03x_3&\le40\cr
5x_1\phantom{{}+0x_2}-\phantom{01}x_3&\ge10\cr
2x_1-\phantom1x_2+\phantom{01}x_3&=12\cr
&\phantom{{}=00}\llap{$x_1\ge0$,\quad$x_2\le0$,\quad$x_3$ unrestricted}.\cr
}$$
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem In the description of the two-phase simplex algorithm in class, I
omitted one possibility that may occur at the end of Phase~I: the value
of~$\xi$ is~0, but at least one artificial variable remains in the basis
(having the value~0). If this happens, then we need to ``drive the artificial
variable out of the basis'' in order to get a basis consisting solely of
non-artificial variables, so that we can begin Phase~II\null. Papadimitriou and
Steiglitz discuss this case (which they call ``Case~3'') in Section~2.8, on
page~56. Give an example of a linear program for which this case occurs, and go
through the full two-phase simplex algorithm to solve your example.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem Write the dual of the following linear program.
$$\eqalign{
{\rm maximize}\quad\phantom+x_1-2x_2\phantom{{}+0x_3+0x_4}&\cr
{\rm subject\ to}\quad\phantom+x_1+2x_2+\phantom1x_3+\phantom1x_4&\ge0\cr
4x_1+3x_2-4x_3-2x_4&\le3\cr
-x_1-\phantom1x_2-2x_3+\phantom1x_4&=1\cr
&\phantom{{}=0}\llap{$x_1$ unrestricted,\quad$x_2\ge0$,\quad$x_3\le0$,\quad$x_4$ unrestricted}.\cr
}$$
The optimal solution of the linear program above has $x_1=5/2$, $x_2=0$,
$x_3=0$, and $x_4=7/2$. Use complementary slackness to determine the optimal
solution to the dual. Verify that the two solutions are both feasible for their
respective linear programs and that they have the same objective value.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem Describe (at least) two essentially different ways to use the
(maximizing) simplex algorithm to solve a minimization linear program. What are
the comparative advantages and disadvantages of each? Given a minimization
linear program, what characteristics would indicate that one method or the
other may be a better approach?
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bye