%  Problem set 3: solutions
%  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  \font\transposefont=cmss8 at6pt

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

% Pilfered from an example on page 106 of the TeXbook
\def\qed{{\unskip\nobreak\hfil\penalty50
	\hskip1em\hbox{}\nobreak\hfil\hbox{\vrule\vbox to6pt{\hrule\hbox to5.2pt{\hss}\vfil\hrule}\vrule}
	\parfillskip=0pt \finalhyphendemerits=0 \par}}
\def\subqed{{\unskip\nobreak\hfil\penalty50
	\hskip1em\hbox{}\nobreak\hfil\raise2pt\hbox{\vrule height4pt width4pt depth0pt}
	\parfillskip=0pt \finalhyphendemerits=0 \par}}

\newdimen\pivotwidth  \newdimen\pivotdepth
\def\pivot#1{%
	\setbox0=\hbox{\vphantom/$#1$}
	\pivotdepth=\dp0
	\setbox0=\hbox{\vbox{\vskip1pt\hbox{\hskip2pt\box0\hskip2pt}\vskip1pt}}%
	\pivotwidth=\wd0  \advance\pivotwidth by0.8pt
	\lower\pivotdepth\hbox{\vbox{%
		\vskip-1.4pt
		\hrule width\pivotwidth height0.4pt depth0.0pt
		\hbox{%
			\vrule height\ht0 depth\dp0 width0.4pt
			\copy0
			\vrule height\ht0 depth\dp0 width0.4pt
		}%
		\hrule width\pivotwidth height0.4pt depth0.0pt
		\vskip-1.4pt
	}\hskip-2.4pt}%
}

\def\frac#1#2{{\textstyle{{#1}\over{#2}}}}
\def\R{{\mathord{\Bbb R}}}
\def\transpose{{\raise0.5pt\hbox{\transposefont T}}}

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

\centerline{\titlefont Combinatorial Optimization}
\smallskip
\centerline{\bf Problem set~3: solutions}

\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.

\def\ctt{\tilde c\mskip2mu^\transpose}

\solution Consider a simplex tableau with the variables $x_1$,~\dots,~$x_n$ and
objective function~$z$. Let

\smallskip

\item{$\bullet$} $\tilde A=[\tilde a_{ij}]$ be the matrix of entries in the
body of the tableau, below the objective row and to the left of the RHS column,
not including the $z$~column;

\smallskip

\item{$\bullet$} $\tilde b=[\tilde b_1,\ldots,\tilde b_m]^\transpose$ be the
column vector of entries in the RHS column below the objective row;

\smallskip

\item{$\bullet$} $\ctt=[\tilde c_1,\ldots,\tilde c_n]$ be the row vector of
entries in the objective row to the left of the RHS column, not including the
$z$~column;

\smallskip

\item{$\bullet$} $x$ be the column vector $x=[x_1,\ldots,x_n]^\transpose$; and

\smallskip

\item{$\bullet$} $\zeta$ be the entry in the objective row and the RHS column.

\smallskip

\noindent Without loss of generality, we may assume that the basis consists of
the variables $x_1$,~\dots,~$x_m$, that the columns
$\tilde A_1$,~\dots,~$\tilde A_m$ form the $m\times m$ identity matrix, and
that the $x_{m+1}$~column is the one referred to in the problem, having a
negative entry in the objective row with no positive entries below it; if not,
we can rearrange the columns and relabel the variables to make this true.

So the tableau looks like this:
$$\vbox{\offinterlineskip
\halign{\quad\hfil\strut$#$\hfil\quad&\hfil\strut$#$\hfil\quad
	&\hfil\strut$#$\hfil\quad&\hfil\strut$#$\hfil\quad&\hfil\strut$#$\hfil\quad
	&\hfil\strut$#$\hfil\quad&\hfil\strut$#$\hfil\quad&\hfil\strut$#$\hfil\quad
	&\hfil\strut$#$\hfil\quad&\hfil\strut$#$\hfil\quad&\hfil\strut$#$\hfil\quad
	&\vrule#&\quad\hfil\strut$#$\hfil\quad\cr
x_1&x_2&x_3&\ldots&x_m&x_{m+1}&x_{m+2}&x_{m+3}&\ldots&x_n&z&\omit&\hbox{\smfont RHS}\cr
\noalign{\vskip2pt}
0&0&0&\ldots&0&\tilde c_{m+1}<0&\tilde c_{m+2}&\tilde c_{m+3}&\ldots&\tilde c_n&1&&\zeta\cr
\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&height2pt\cr
\noalign{\hrule}
\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&height2pt\cr
1&0&0&\ldots&0&\tilde a_{1(m+1)}\le0&\tilde a_{1(m+2)}&\tilde a_{1(m+3)}&\ldots&\tilde a_{1n}&0&&\tilde b_1\cr
0&1&0&\ldots&0&\tilde a_{2(m+1)}\le0&\tilde a_{2(m+2)}&\tilde a_{2(m+3)}&\ldots&\tilde a_{2n}&0&&\tilde b_2\cr
0&0&1&\ldots&0&\tilde a_{3(m+1)}\le0&\tilde a_{3(m+2)}&\tilde a_{3(m+3)}&\ldots&\tilde a_{3n}&0&&\tilde b_3\cr
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&&\vdots\cr
0&0&0&\ldots&1&\tilde a_{m(m+1)}\le0&\tilde a_{m(m+2)}&\tilde a_{m(m+3)}&\ldots&\tilde a_{mn}&0&&\tilde b_m\cr
}}$$
This tableau represents the system of equations
$$\eqalign{
	\ctt x+z&=\zeta,\cr
	\tilde Ax\phantom{{}+z}&=\tilde b,\cr
}$$
and the system $\tilde Ax=\tilde b$ is equivalent to the original set of
constraints in the linear program.

From the equation $\ctt x+z=\zeta$ represented by the objective row, we see
that
$$z=\zeta-\sum_{i=1}^n\tilde c_ix_i.\eqno(1)$$
From the system of equations $\tilde Ax=\tilde b$ represented by the body of
the tableau, and from the assumption that the columns
$\tilde A_1$,~\dots,~$\tilde A_m$ form the identity matrix, we see that
$$x_i=\tilde b-\sum_{j=m+1}^n\tilde a_{ij}x_j\qquad\hbox{for $1\le i\le m$}.\eqno(2)$$

The value of~$x_{m+1}$ in the basic feasible solution corresponding to this
tableau is zero, because $x_{m+1}$ is nonbasic. Suppose we change the value
of~$x_{m+1}$ to $t>0$. Then, by equation~(2), in order to satisfy the
constraints of the linear program, the value of~$x_i$ (for $1\le i\le m$) must
increase by $-\tilde a_{i(m+1)}t$, which is nonnegative because $\tilde
a_{i(m+1)}\le0$. So the resulting solution will have all nonnegative entries,
and therefore it will be feasible. Moreover, by equation~(1), the objective
value will increase by $-\tilde c_{m+1}t$, which is strictly positive because
$\tilde c_{m+1}<0$ and can be made arbitrarily large by making $t$ sufficiently
large. Hence the linear program has feasible solutions with arbitrarily large
objective value, i.e., it is unbounded. \qed

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

\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.

\solution There's really nothing to justify in step~1, because clearly those
rows have to be filled in anyway.

The artificial columns are to be basic in the initial tableau (that is their
entire purpose), so the entries in the artificial objective row in columns
corresponding to artificial variables must be zero. Likewise, $-\xi$ is to be
basic, associated with the artificial objective row, so its column must have 1
in the artificial objective row. This justifies step~2.

Let $G$ denote the set of indices of rows that come from $\ge$~constraints, and
let $E$ be those that come from $=$~constraints. So step~3 says that each entry
in the initial artificial objective row, except the entries in columns
corresponding to artificial variables and to~$-\xi$, should be the negation of
the sum of the entries in that column in rows $G\cup E$.

The initial artificial objective row represents an equation that is equivalent
to
$$\sum_{i\in G\cup E}a_i+(-\xi)=0,\eqno(3)$$
but with $\sum_{i\in G\cup E}a_i$ expressed in terms of nonbasic variables
(i.e., variables other than slack and artificial variables).

For $g\in G$, the $g$th row of the body of the initial tableau represents the
equation
$$\sum_{j=1}^na_{gj}x_j-p_g+a_g=b_g.$$
For $e\in E$, the $e$th row of the body of the initial tableau represents the
equation
$$\sum_{j=1}^na_{ej}x_j+a_e=b_e.$$
Solving these equations for $a_g$~and~$a_e$, respectively, yields
$$\eqalign{
	a_g&=b_g-\sum_{j=1}^na_{gj}x_j+p_g\qquad\hbox{for $g\in G$},\cr
	a_e&=\rlap{$\displaystyle b_e-\sum_{j=1}^na_{ej}x_j$}
		\phantom{b_g-\sum_{j=1}^na_{gj}x_j+p_g}\qquad\hbox{for $e\in E$}.\cr
}$$
So
$$\sum_{i\in G\cup E}a_i=\sum_{i\in G\cup E}b_i
	-\sum_{j=1}^n\sum_{i\in G\cup E}a_{ij}x_j+\sum_{g\in G}p_g,$$
and hence equation~(3) becomes
$$-\sum_{j=1}^n\sum_{i\in G\cup E}a_{ij}x_j+\sum_{g\in G}p_g+(-\xi)
	=-\sum_{i\in G\cup E}b_i.\eqno(4)$$

\noindent In this equation:

\smallskip

\item{$\bullet$} The coefficient of~$x_j$, $-\sum_{i\in G\cup E}a_{ij}$, is the
negation of the sum of the entries in the $x_j$~column of the initial tableau
in the rows $G\cup E$.

\smallskip

\item{$\bullet$} The coefficient of any slack variable~$s_j$ is zero, and the
entries in the $s_j$~column in the $s_j$~column of the initial tableau in the
rows $G\cup E$ are all zero (because $\ge$~and~$=$ constraints do not have
slack variables).

\smallskip

\item{$\bullet$} The coefficient of any surplus variable~$p_j$ is~1, and the
entries in the $p_j$~column in the $p_j$~column of the initial tableau in the
rows $G\cup E$ are all zero except for a single $-1$~entry in the row that
comes from the $\ge$~constraint containing~$p_j$.

\smallskip

\item{$\bullet$} The coefficient of every artificial variable is zero.

\smallskip

\item{$\bullet$} The coefficient of~$-\xi$ is~1.

\smallskip

\item{$\bullet$} The right-hand side is $-\sum_{i\in G\cup E}b_i$, which is the
negation of the sum of the entries in the RHS column of the initial tableau in
the rows $G\cup E$.

\smallskip

\noindent So equation~(4) expresses equation~(3) in terms of nonbasic variables
(all slack and artificial variables have coefficient zero), and each
coefficient other than those for artificial variables and~$-\xi$ is the
negation of the sum of the entries in that column in the initial tableau in the
rows $G\cup E$, which justifies step~3. \qed

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

\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
}$$

\solution First we convert to standard variable domains. Let $\bar x_2=-x_2$
and let $x_3=x_3^+-x_3^-$, where $x_3^+\ge0$ and $x_3^-\ge0$. After we make
these substitutions, the linear program becomes
$$\eqalign{
	{\rm maximize}\quad3x_1+8\bar x_2+10x_3^+-10x_3^-&\cr
	{\rm subject\ to}\quad\phantom2x_1-\phantom1\bar x_2+\phantom03x_3^+
		-\phantom03x_3^-&\le40\cr
	5x_1\phantom{{}+0\bar x_2}-\phantom{01}x_3^++\phantom{01}x_3^-&\ge10\cr
	2x_1+\phantom1\bar x_2+\phantom{01}x_3^+-\phantom{01}x_3^-&=12\cr
	&\phantom{{}=00}\llap{$x_1\ge0$,\quad$\bar x_2\ge0$,\quad$x_3^+\ge0$,%
		\quad$x_3^-\ge0$}.\cr
}$$

\noindent Now we insert slack, surplus, and artificial variables:
$$\eqalign{
	{\rm maximize}\quad3x_1+8\bar x_2+10x_3^+-10x_3^-
		\phantom{{}+s_1+p_2+a_2+a_3}&\cr
	\qquad\qquad{\rm subject\ to}\quad\phantom2x_1-\phantom1\bar x_2
		+\phantom03x_3^+-\phantom03x_3^-+s_1\phantom{{}+p_2+a_2+a_3}&=40\cr
	5x_1\phantom{{}+0\bar x_2}-\phantom{01}x_3^++\phantom{01}x_3^-
		\phantom{{}+s_1}-p_2+a_2\phantom{{}+a_3}&=10\cr
	2x_1+\phantom1\bar x_2+\phantom{01}x_3^+-\phantom{01}x_3^-
		\phantom{{}+s_1+p_2+a_2}+a_3&=12\cr
	&\phantom{{}=00}\llap{$x_1\ge0$,\quad$\bar x_2\ge0$,\quad$x_3^+\ge0$,%
		\quad$x_3^-\ge0$,\quad$s_1\ge0$,\quad$p_2\ge0$,\quad$a_2\ge0$,%
		\quad$a_3\ge0$}.\cr
}$$

\noindent We begin Phase~I, using the artificial objective row to guide our
pivots. The sequence of simplex tableaux for Phase~I appears below. The pivot
entry is indicated in each tableau.
$$\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\hfil\strut$#$%
	&\quad\hfil\strut$#$\quad&\vrule#&\quad\hfil\strut$#$\quad\cr
x_1&\bar x_2&x_3^+&x_3^-&s_1&p_2&a_2&a_3&z&-\xi&\omit&\hbox{\smfont RHS}\cr
\noalign{\vskip2pt}
     -3 & -8 & -10 & 10 & 0 &  0 & 0 & 0 & 1 & 0 &&   0 \cr
     -7 & -1 &   0 &  0 & 0 &  1 & 0 & 0 & 0 & 1 && -22 \cr
\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&height2pt\cr
\noalign{\hrule}
\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&height2pt\cr
      1 & -1 &   3 & -3 & 1 &  0 & 0 & 0 & 0 & 0 &&  40 \cr
\pivot5 &  0 &  -1 &  1 & 0 & -1 & 1 & 0 & 0 & 0 &&  10 \cr
      2 &  1 &   1 & -1 & 0 &  0 & 0 & 1 & 0 & 0 &&  12 \cr}}$$
%
$$\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\hfil\strut$#$%
	&\quad\hfil\strut$#$\quad&\vrule#&\quad\hfil\strut$#$\quad\cr
x_1&\bar x_2&x_3^+&x_3^-&s_1&p_2&a_2&a_3&z&-\xi&\omit&\hbox{\smfont RHS}\cr
\noalign{\vskip2pt}
0 & -8 &      -53/5  &  53/5 & 0 & -3/5 &  3/5 & 0 & 1 & 0 &&  6 \cr
0 & -1 &       -7/5  &   7/5 & 0 & -2/5 &  7/5 & 0 & 0 & 1 && -8 \cr
\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&height2pt\cr
\noalign{\hrule}
\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&height2pt\cr
0 & -1 &       16/5  & -16/5 & 1 &  1/5 & -1/5 & 0 & 0 & 0 && 38 \cr
1 &  0 &       -1/5  &   1/5 & 0 & -1/5 &  1/5 & 0 & 0 & 0 &&  2 \cr
0 &  1 & \pivot{7/5} &  -7/5 & 0 &  2/5 & -2/5 & 1 & 0 & 0 &&  8 \cr}}$$
%
$$\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\hfil\strut$#$%
	&\quad\hfil\strut$#$\quad&\vrule#&\quad\hfil\strut$#$\quad\cr
x_1&\bar x_2&x_3^+&x_3^-&s_1&p_2&a_2&a_3&z&-\xi&\omit&\hbox{\smfont RHS}\cr
\noalign{\vskip2pt}
0 &  -3/7 & 0 &  0 & 0 & 17/7 & -17/7 &  53/7 & 1 & 0 && 466/7 \cr
0 &     0 & 0 &  0 & 0 &    0 &     1 &     1 & 0 & 1 &&     0 \cr
\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&height2pt\cr
\noalign{\hrule}
\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&height2pt\cr
0 & -23/7 & 0 &  0 & 1 & -5/7 &   5/7 & -16/7 & 0 & 0 && 138/7 \cr
1 &   1/7 & 0 &  0 & 0 & -1/7 &   1/7 &   1/7 & 0 & 0 &&  22/7 \cr
0 &   5/7 & 1 & -1 & 0 &  2/7 &  -2/7 &   5/7 & 0 & 0 &&  40/7 \cr}}$$

\noindent After two pivots, we reach a tableau that has no negative entries in
the artificial objective row to the left of the RHS column, so Phase~I is
complete. The value of~$\xi$ in this tableau is~0, so Phase~I was successful.
All artificial variables are nonbasic, so we can delete the artificial
objective row and the columns for the artificial variables and~$-\xi$ and go on
to Phase~II. The sequence of simplex tableaux for Phase~II appears below.
$$\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&\vrule#&\quad\hfil\strut$#$\quad\cr
x_1&\bar x_2&x_3^+&x_3^-&s_1&p_2&z&\omit&\hbox{\smfont RHS}\cr
\noalign{\vskip2pt}
0 &       -3/7  & 0 &  0 & 0 & 17/7 & 1 && 466/7 \cr
\omit&\omit&\omit&\omit&\omit&\omit&\omit&height2pt\cr
\noalign{\hrule}
\omit&\omit&\omit&\omit&\omit&\omit&\omit&height2pt\cr
0 &      -23/7  & 0 &  0 & 1 & -5/7 & 0 && 138/7 \cr
1 &        1/7  & 0 &  0 & 0 & -1/7 & 0 &&  22/7 \cr
0 & \pivot{5/7} & 1 & -1 & 0 &  2/7 & 0 &&  40/7 \cr}}$$
%
$$\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&\vrule#&\quad\hfil\strut$#$\quad\cr
x_1&\bar x_2&x_3^+&x_3^-&s_1&p_2&z&\omit&\hbox{\smfont RHS}\cr
\noalign{\vskip2pt}
0 & 0 &  3/5 &       -3/5  & 0 & 13/5 & 1 && 70 \cr
\omit&\omit&\omit&\omit&\omit&\omit&\omit&height2pt\cr
\noalign{\hrule}
\omit&\omit&\omit&\omit&\omit&\omit&\omit&height2pt\cr
0 & 0 & 23/5 &      -23/5  & 1 &  3/5 & 0 && 46 \cr
1 & 0 & -1/5 & \pivot{1/5} & 0 & -1/5 & 0 &&  2 \cr
0 & 1 &  7/5 &       -7/5  & 0 &  2/5 & 0 &&  8 \cr}}$$
%
$$\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&\vrule#&\quad\hfil\strut$#$\quad\cr
x_1&\bar x_2&x_3^+&x_3^-&s_1&p_2&z&\omit&\hbox{\smfont RHS}\cr
\noalign{\vskip2pt}
 3 & 0 &  0 & 0 & 0 &  2 & 1 && 76 \cr
\omit&\omit&\omit&\omit&\omit&\omit&\omit&height2pt\cr
\noalign{\hrule}
\omit&\omit&\omit&\omit&\omit&\omit&\omit&height2pt\cr
23 & 0 &  0 & 0 & 1 & -4 & 0 && 92 \cr
 5 & 0 & -1 & 1 & 0 & -1 & 0 && 10 \cr
 7 & 1 &  0 & 0 & 0 & -1 & 0 && 22 \cr}}$$

\noindent After two more pivots, we reach a tableau that has no negative
entries in the objective row to the left of the RHS column, so the
corresponding basic basic feasible solution is optimal. This optimal solution
is $x_1=0$, $\bar x_2=22$, $x_3^+=0$, $x_3^-=10$, $s_1=92$, $p_2=0$. In terms
of the original variables, we have
$$x_1=0,\quad x_2=-22,\quad x_3=-10$$
(and $s_1=92$, $p_2=0$). The optimal objective value is~76. \qed

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

\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.

\solution A very simple (and therefore pretty stupid) example is the linear
program
$$\eqalign{
	{\rm maximize}\quad\phantom+x&\cr
	{\rm subject\ to}\quad{-}x&=0\cr
	x&\ge0.\cr
}$$

\noindent When we insert an artificial variable into the $=$~constraint, we get
$$\eqalign{
	{\rm maximize}\quad\phantom+x\phantom{{}+a_1}&\cr
	{\rm subject\ to}\quad{-}x+a_1&=0\cr
	&\phantom{{}=0}\llap{$x\ge0$,\quad$a_1\ge0$}.\cr
}$$

\noindent The initial (two-phase) simplex tableau is
$$\vbox{\offinterlineskip
\halign{\quad\hfil\strut$#$&\quad\hfil\strut$#$&\quad\hfil\strut$#$%
	&\quad\hfil\strut$#$\quad&\vrule#&\quad\hfil\strut$#$\quad\cr
x&a_1&z&-\xi&\omit&\hbox{\smfont RHS}\cr
\noalign{\vskip2pt}
-1 & 0 & 1 & 0 && 0 \cr
 1 & 0 & 0 & 1 && 0 \cr
\omit&\omit&\omit&\omit&height2pt\cr
\noalign{\hrule}
\omit&\omit&\omit&\omit&height2pt\cr
-1 & 1 & 0 & 0 && 0 \cr}}$$

\noindent Phase~I is done already. The value of~$\xi$ is~0, so Phase~I was
successful. However, the artificial variable~$a_1$ is still basic. So we need
to drive the artificial variable out of the basis. We do this by pivoting on
any nonzero (not necessarily positive) entry in the row corresponding to~$a_1$
and in a column corresponding to a non-artificial variable:
$$\vbox{\offinterlineskip
\halign{\quad\hfil\strut$#$&\quad\hfil\strut$#$&\quad\hfil\strut$#$%
	&\quad\hfil\strut$#$\quad&\vrule#&\quad\hfil\strut$#$\quad\cr
x&a_1&z&-\xi&\omit&\hbox{\smfont RHS}\cr
\noalign{\vskip2pt}
       -1  & 0 & 1 & 0 && 0 \cr
        1  & 0 & 0 & 1 && 0 \cr
\omit&\omit&\omit&\omit&height2pt\cr
\noalign{\hrule}
\omit&\omit&\omit&\omit&height2pt\cr
\pivot{-1} & 1 & 0 & 0 && 0 \cr}}$$
%
$$\vbox{\offinterlineskip
\halign{\quad\hfil\strut$#$&\quad\hfil\strut$#$&\quad\hfil\strut$#$%
	&\quad\hfil\strut$#$\quad&\vrule#&\quad\hfil\strut$#$\quad\cr
x&a_1&z&-\xi&\omit&\hbox{\smfont RHS}\cr
\noalign{\vskip2pt}
0 & -1 & 1 & 0 && 0 \cr
0 &  1 & 0 & 1 && 0 \cr
\omit&\omit&\omit&\omit&height2pt\cr
\noalign{\hrule}
\omit&\omit&\omit&\omit&height2pt\cr
1 & -1 & 0 & 0 && 0 \cr}}$$

\noindent Now $a_1$ is nonbasic, so we can delete the artificial objective row
and the columns for $a_1$~and~$-\xi$ and continue with Phase~II:
$$\vbox{\offinterlineskip
\halign{\quad\hfil\strut$#$&\quad\hfil\strut$#$\quad&\vrule#%
	&\quad\hfil\strut$#$\quad\cr
x&z&\omit&\hbox{\smfont RHS}\cr
\noalign{\vskip2pt}
0 & 1 && 0 \cr
\omit&\omit&height2pt\cr
\noalign{\hrule}
\omit&\omit&height2pt\cr
1 & 0 && 0 \cr}}$$
Phase~II is done immediately, and the optimal solution is (unsurprisingly)
$x=0$, with an optimal objective value of~0. \qed

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

\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.

\solution The dual linear program is
$$\eqalign{
	{\rm minimize}\quad\phantom{0y_1+{}}3y_2+\phantom1y_3&\cr
	{\rm subject\ to}\quad\phantom1y_1+4y_2-\phantom1y_3&=\phantom+1\cr
	2y_1+3y_2-\phantom1y_3&\ge-2\cr
	y_1-4y_2-2y_3&\le\phantom+0\cr
	y_1-2y_2+\phantom1y_3&=\phantom+0\cr
	&\phantom{{}=+0}\llap{$y_1\le0$,\quad$y_2\ge0$,\quad$y_3$ unrestricted}.\cr
}$$

\goodbreak

\noindent First we apply complementary slackness to the primal constraints and
the dual variables.

\smallskip

\item{1.} Either $x_1+2x_2+x_3+x_4=0$ or $y_1=0$ (or both). The first equation
is false, because $5/2+2(0)+0+7/2=6\not=0$, so we can conclude that $y_1=0$.

\smallskip

\item{2.} Either $4x_1+3x_2-4x_3-2x_4=3$ or $y_2=0$ (or both). The first
equation is true, because $4(5/2)+3(0)-4(0)-2(7/2)=3$, so we cannot conclude
anything about~$y_2$.

\smallskip

\item{3.} Either $-x_1-x_2-2x_3+x_4=1$ or $y_3=0$ (or both). The first equation
is true, because $-(5/2)-0-2(0)+7/2=1$, so we cannot conclude anything
about~$y_3$.

\smallbreak

\noindent Then we apply complementary slackness to the dual constraints and the
primal variables.

\smallskip

\item{1.} Either $y_1+4y_2-y_3=1$ or $x_1=0$ (or both). The second equation is
false, because $x_1=5/2\not=0$, so we can conclude that $y_1+4y_2-y_3=1$.

\smallskip

\item{2.} Either $2y_1+3y_2-y_3=-2$ or $x_2=0$ (or both). The second equation
is true, because $x_2=0$, so we cannot conclude anything else.

\smallskip

\item{3.} Either $y_1-4y_2-2y_3=0$ or $x_3=0$ (or both). The second equation is
true, because $x_3=0$, so we cannot conclude anything else.

\smallskip

\item{4.} Either $y_1-2y_2+y_3=0$ or $x_4=0$ (or both). The second equation is
false, because $x_4=7/2\not=0$, so we can conclude that $y_1-2y_2+y_3=0$.

\smallbreak

\noindent Therefore we know
$$\left\{\eqalign{
	y_1\phantom{{}+0y_2+y_3}&=0,\cr
	y_1+4y_2-y_3&=1,\cr
	y_1-2y_2+y_3&=0.\cr
}\right.$$
The solution to this system gives us the values of the dual variables: $y_1=0$,
$y_2=1/2$, and $y_3=1$.

\goodbreak

We verify that the given solution ($x_1=5/2$, $x_2=0$, $x_3=0$, $x_4=7/2$) is
feasible in the primal linear program:

\smallskip

\item{$\bullet$} It satisfies the constraints, because
$$\eqalign{
	5/2+2(0)+0+7/2=6&\ge0,\cr
	4(5/2)+3(0)-4(0)-2(7/2)=3&\le3,\quad\hbox{and}\cr
	-5/2-0-2(0)+7/2=1&=1.\cr
}$$

\item{$\bullet$} It satisfies the variable domains, because $x_2=0\ge0$ and
$x_3=0\le0$. (The values of $x_1$~and~$x_4$ are unrestricted.)

\smallbreak

\noindent We also verify that the solution we found to the dual linear program
($y_1=0$, $y_2=1/2$, $y_3=1$) is feasible:

\smallskip

\item{$\bullet$} It satisfies the constraints, because
$$\eqalign{
	0+4(1/2)-1=1&=\phantom+1,\cr
	2(0)+3(1/2)-1=1/2&\ge-2,\cr
	0-4(1/2)-2(1)=-4&\le\phantom+0,\quad\hbox{and}\cr
	0-2(1/2)+1=0&=\phantom+0.\cr
}$$

\item{$\bullet$} It satisfies the variable domains, because $y_1=0\le0$ and
$y_2=1/2\ge0$. (The value of~$y_3$ is unrestricted.)

\smallbreak

\noindent The objective value of the primal solution is
$x_1-2x_2=5/2-2(0)=5/2$, and the objective value of the dual solution is
$3y_2+y_3=3(1/2)+1=5/2$, so the two solutions have the same objective value.
\qed

\medbreak

\noindent This wasn't part of the assigned problem, but perhaps it should have
been:

Note that the optimal values of the dual variables are the coefficients in a
linear combination of the constraints in the primal linear program that proves
the optimality of the primal solution:
$$\eqalign{
	0(\phantom+x_1+\phantom{\frac00}\llap2x_2+\phantom1x_3+\phantom1x_4\phantom)&\ge0)\cr
	\frac12(\phantom+\llap4x_1+\phantom{\frac00}\llap3x_2-4x_3-2x_4\phantom)&\le3)\cr
	{}+1(-x_1-\phantom{\frac00}x_2-2x_3+\phantom1x_4\phantom)&=1)\cr
	\noalign{\vskip2pt\hrule\vskip2pt}
	0(\phantom+x_1+\phantom{\frac00}\llap2x_2+\phantom1x_3+\phantom1x_4)&\le0(0)\cr
	\frac12(\phantom+\llap4x_1+\phantom{\frac00}\llap3x_2-4x_3-2x_4)&\le\frac12(3)\cr
	{}+1(-x_1-\phantom{\frac00}x_2-2x_3+\phantom1x_4)&=1(1)\cr
	\noalign{\vskip2pt\hrule\vskip2pt}
	x_1+\frac12x_2\phantom{{}+0x_3+0x_4)}&\le\frac52\cr
}$$
Since $x_2\ge0$, we conclude from this inequality that every feasible value of
the primal objective function~$z$ must satisfy
$$z=x_1-2x_2\le x_1+\frac12x_2\le\frac52.$$
Therefore, the feasible solution $x=[5/2,0,0,7/2]^\transpose$, which yields the
objective value~$5/2$, must be optimal.

\goodbreak

Likewise, the optimal values of the primal variables are the coefficients in a
linear combination of the constraints in the dual linear program that proves
the optimality of the dual solution:
$$\eqalign{
	\frac52(\phantom1y_1+4y_2-\phantom1y_3\phantom)&=\phantom+1)\cr
	0(2y_1+3y_2-\phantom1y_3\phantom)&\ge-2)\cr
	0(\phantom1y_1-4y_2-2y_3\phantom)&\le\phantom+0)\cr
	{}+\frac72(\phantom1y_1-2y_2+\phantom1y_3\phantom)&=\phantom+0\cr
	\noalign{\vskip2pt\hrule\vskip2pt}
	\frac52(\phantom1y_1+4y_2-\phantom1y_3)&=\frac52(1)\cr
	0(2y_1+3y_2-\phantom1y_3)&\ge0(-2)\cr
	0(\phantom1y_1-4y_2-2y_3)&\ge0(0)\cr
	{}+\frac72(\phantom1y_1-2y_2+\phantom1y_3)&=\frac72(0)\cr
	\noalign{\vskip2pt\hrule\vskip2pt}
	3y_1+3y_2+\phantom1y_3\phantom)&\ge\frac52\cr
}$$
Since $y_1\le0$, we conclude from this inequality that every feasible value of
the dual objective function~$w$ must satisfy
$$w=3y_2+y_3\ge3y_1+3y_2+y_3\ge\frac52.$$
Therefore, the feasible solution $y=[0,1/2,1]^\transpose$, which yields the
objective value~$5/2$, must be optimal.

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

\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?

\solution One method is simply to negate the objective function. Maximizing the
negation is equivalent to minimizing the original function. The main advantage
of this method is that it is simple and direct to understand and implement. One
disadvantage is that minimization LPs canonically have $\ge$~constraints, which
will require the use of the two-phase simplex algorithm.

Another method is to solve the {\it dual\/} maximization LP and then use
complementary slackness to solve for the optimal primal solution. One advantage
of this approach is that the dual of a minimization LP in canonical form is a
maximization LP in canonical form, which does not require the two-phase simplex
algorithm (as long as the right-hand sides of the constraints are nonnegative,
i.e., if the primal minimization LP has nonnegative coefficients in the
objective function). A disadvantage of this method is that it requires the
computation of the dual LP; in addition to requiring additional time to write
the dual, this may introduce the complications of nonstandard variable domains
if the constraints in the primal LP are not in canonical form. Another
disadvantage is the need to go through the reasoning of complementary slackness
and to solve a system of equations to obtain the primal solution.

A third method is to solve the dual maximization LP using the simplex
algorithm, keeping the artificial variable columns (if any) through Phase~II,
and then read off the solution to the primal minimization LP from the optimal
tableau as the entries in the objective row in the columns corresponding to
slack and artificial variables. This method shares with the second method the
advantage that the dual of a minimization LP in canonical form is a
maximization LP in canonical form and the disadvantage that the dual must be
computed. However, an additional advantage is that we get the optimal primal
solution immediately upon solving the dual; no further work is necessary. On
the other hand, an additional disadvantage is the need to carry the artificial
variable columns through Phase~II (and to remember not to pivot on them!).

If the minimization LP has many $\le$~constraints (with nonnegative right-hand
sides), then simply negating the objective function might be a good approach,
because such constraints in a maximization LP are easily handled directly by
the simplex algorithm. If the minimization LP is in canonical form and has
nonnegative objective function coefficients, then one of the two approaches
using the dual LP is probably best, because it will not be necessary to use the
two-phase simplex algorithm to solve the dual. The third approach is likely to
be computationally better than the second, because carrying the artificial
variable columns through the pivots really is equivalent to solving the system
obtained from complementary slackness using row operations, so these steps
might as well be done together. On the other hand, the sequence of pivots taken
in the simplex algorithm may not be the most {\it efficient\/} sequence of row
operations to solve that system, in which case the second approach may be
better (but this is not something that can be easily predicted ahead of time).
\qed

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

\bye
