%  Midterm examination: 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

% MetaPost stuff
\input supp-pdf
\def\fig#1{\convertMPtoPDF{#1}{1}{1}}
\def\midfig#1{{%
	\setbox0=\hbox{\fig{#1}}%
	\dimen0=0.5\ht0%
	\advance\dimen0 by-0.3\ht\strutbox
	\lower\dimen0\box0%
}}

% 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\Q{{\mathord{\Bbb Q}}}
\def\Z{{\mathord{\Bbb Z}}}  \def\N{{\mathord{\Bbb N}}}
\def\transpose{{\raise0.5pt\hbox{\transposefont T}}}
\def\labs{\mathopen|}  \def\rabs{\mathclose|}  \def\abs#1{\labs#1\rabs}
\def\implies{\Longrightarrow}

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

\centerline{\titlefont Combinatorial Optimization}
\smallskip
\centerline{\bf Midterm examination: solutions}

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

\problem Solve the following linear program. You may not use Maple for this
problem.
$$\eqalign{
	{\rm minimize}\quad 3x_1+2x_2-\phantom1x_3-4x_4&\cr
	{\rm subject\ to}\quad\phantom1x_1+\phantom1x_2+\phantom1x_3+\phantom1x_4&=\phantom+\llap10\cr
	2x_1\phantom{{}+0x_2}+\phantom1x_3-2x_4&\ge\phantom+6\cr
	x_1\phantom{{}+0x_2+0x3}+3x_4&\le\phantom+\llap30\cr
	3x_1+\phantom1x_2\phantom{{}+0x_3+0x_4}&\ge-8\cr
	x_2+3x_3\phantom{{}+0x_4}&\ge\phantom+3\cr
	&\phantom{{}=+0}\llap{$x_1\ge0$,\quad$x_2$ unrestricted,\quad$x_3\le0$,\quad$x_4\ge0$}.\cr
}$$

\solution There are several possible approaches. One approach begins by
writing the dual:
$$\eqalign{
	{\rm maximize}\quad10y_1+6y_2+30y_3-8y_4+3y_5&\cr
	{\rm subject\ to}\quad\phantom{01}y_1+2y_2+\phantom{01}y_3+3y_4\phantom{{}+0y_5}&\le\phantom+3\cr
	y_1\phantom{{}+0y_2+00y_3}+\phantom1y_4+\phantom1y_5&=\phantom+2\cr
	y_1+\phantom1y_2\phantom{{}+00y_3+0y_4}+3y_5&\ge-1\cr
	y_1-2y_2+\phantom03y_3\phantom{{}+0y_4+0y_5}&\le-4\cr
	&\phantom{{}=+0}\llap{$y_1$~unrestricted, $y_2\ge0$, $y_3\le0$, $y_4\ge0$, $y_5\ge0$}.\cr
}$$
In order to make the right-hand sides nonnegative, we multiply the last two
constraints by~$-1$. Then we convert to standard variable domains by making the
substitutions $y_1=y_1^+-y_1^-$ and $y_3=-\bar y_3$ with $y_1^+\ge0$,
$y_1^-\ge0$, and $\bar y_3\ge0$:
$$\eqalign{
	{\rm maximize}\quad10y_1^+-10y_1^-+6y_2-30\bar y_3-8y_4+3y_5&\cr
	{\rm subject\ to}\quad\phantom{01}y_1^+-\phantom{01}y_1^-+2y_2-\phantom{01}\bar y_3+3y_4\phantom{{}+0y_5}&\le3\cr
	y_1^+-\phantom{01}y_1^-\phantom{{}+0y_2+00y_3}+\phantom1y_4+\phantom1y_5&=2\cr
	-y_1^++\phantom{01}y_1^--\phantom1y_2\phantom{{}+00y_3+0y_4}-3y_5&\le1\cr
	-y_1^++\phantom{01}y_1^-+2y_2+\phantom03\bar y_3\phantom{{}+0y_4+0y_5}&\ge4\cr
	&\phantom{{}=0}\llap{$y_1^+\ge0$, $y_1^-\ge0$, $y_2\ge0$, $\bar y_3\ge0$, $y_4\ge0$, $y_5\ge0$}.\cr
}$$
Next we insert slack, surplus, and artificial variables:
$$\displaylines{
\openup-1\jot \eqalign{
	{\rm maximize}\quad10y_1^+-10y_1^-+6y_2-30\bar y_3-8y_4+3y_5\phantom{{}+s_1+a_2+s_3+p_4+a_4}&\cr
	{\rm subject\ to}\quad\phantom{01}y_1^+-\phantom{01}y_1^-+2y_2-\phantom{01}\bar y_3+3y_4\phantom{{}+0y_5}+s_1\phantom{{}+a_2+s_3+p_4+a_4}&=3\cr
	y_1^+-\phantom{01}y_1^-\phantom{{}+0y_2+00y_3}+\phantom1y_4+\phantom1y_5\phantom{{}+s_1}+a_2\phantom{{}+s_3+p_4+a_4}&=2\cr
	-y_1^++\phantom{01}y_1^--\phantom1y_2\phantom{{}+00y_3+0y_4}-3y_5\phantom{{}+s_1+a_2}+s_3\phantom{{}+p_4+a_4}&=1\cr
	-y_1^++\phantom{01}y_1^-+2y_2+\phantom03\bar y_3\phantom{{}+0y_4+0y_5}\phantom{{}+s_1+a_2+s_3}-p_4+a_4&=4\cr
}\cr
\hbox{$y_1^+\ge0$, $y_1^-\ge0$, $y_2\ge0$, $\bar y_3\ge0$, $y_4\ge0$, $y_5\ge0$, $s_1\ge0$, $a_2\ge0$, $s_3\ge0$, $p_4\ge0$, $a_4\ge0$.}\cr
}$$

\noindent We form the initial tableau for the two-phase simplex algorithm:
$$\vbox{\offinterlineskip
\halign{&\enspace\hfil\strut$#$\enspace\cr
y_1^+&y_1^-&y_2&\bar y_3&y_4&y_5&s_1&a_2&s_3&p_4&a_4&z&-\xi&\omit&\hbox{\smfont RHS}\cr
\noalign{\vskip2pt}
-10&10&-6&30&8&-3&0&0&0&0&0&1&0&\omit\vrule&0\cr
0&0&-2&-3&-1&-1&0&0&0&1&0&0&1&\omit\vrule&-6\cr
\multispan{13}&\omit\vrule height2pt&\omit\cr
\noalign{\hrule}
\multispan{13}&\omit\vrule height2pt&\omit\cr
1&-1&2&-1&3&0&1&0&0&0&0&0&0&\omit\vrule&3\cr
1&-1&0&0&1&1&0&1&0&0&0&0&0&\omit\vrule&2\cr
-1&1&-1&0&0&-3&0&0&1&0&0&0&0&\omit\vrule&1\cr
-1&1&2&\pivot3&0&0&0&0&0&-1&1&0&0&\omit\vrule&4\cr
}}$$

\noindent Pivot on the~3 in the $\bar y_3$~column:
$$\vbox{\offinterlineskip
\halign{&\enspace\hfil\strut$#$\enspace\cr
y_1^+&y_1^-&y_2&\bar y_3&y_4&y_5&s_1&a_2&s_3&p_4&a_4&z&-\xi&\omit&\hbox{\smfont RHS}\cr
\noalign{\vskip2pt}
0&0&-26&0&8&-3&0&0&0&10&-10&1&0&\omit\vrule&-40\cr
-1&1&0&0&-1&-1&0&0&0&0&1&0&1&\omit\vrule&-2\cr
\multispan{13}&\omit\vrule height2pt&\omit\cr
\noalign{\hrule}
\multispan{13}&\omit\vrule height2pt&\omit\cr
2/3&-2/3&8/3&0&3&0&1&0&0&-1/3&1/3&0&0&\omit\vrule&13/3\cr
1&-1&0&0&1&\pivot1&0&1&0&0&0&0&0&\omit\vrule&2\cr
-1&1&-1&0&0&-3&0&0&1&0&0&0&0&\omit\vrule&1\cr
-1/3&1/3&2/3&1&0&0&0&0&0&-1/3&1/3&0&0&\omit\vrule&4/3\cr
}}$$

\noindent Pivot on the~1 in the $y_5$~column:
$$\vbox{\offinterlineskip
\halign{&\enspace\hfil\strut$#$\enspace\cr
y_1^+&y_1^-&y_2&\bar y_3&y_4&y_5&s_1&a_2&s_3&p_4&a_4&z&-\xi&\omit&\hbox{\smfont RHS}\cr
\noalign{\vskip2pt}
3&-3&-26&0&11&0&0&3&0&10&-10&1&0&\omit\vrule&-34\cr
0&0&0&0&0&0&0&1&0&0&1&0&1&\omit\vrule&0\cr
\multispan{13}&\omit\vrule height2pt&\omit\cr
\noalign{\hrule}
\multispan{13}&\omit\vrule height2pt&\omit\cr
2/3&-2/3&8/3&0&3&0&1&0&0&-1/3&1/3&0&0&\omit\vrule&13/3\cr
1&-1&0&0&1&1&0&1&0&0&0&0&0&\omit\vrule&2\cr
2&-2&-1&0&3&0&0&3&1&0&0&0&0&\omit\vrule&7\cr
-1/3&1/3&2/3&1&0&0&0&0&0&-1/3&1/3&0&0&\omit\vrule&4/3\cr
}}$$

\noindent All entries in the artificial objective row are nonnegative, so
Phase~I is complete. The artificial objective value is~0, so Phase~I was
successful. All artificial variables are nonbasic, so we can continue to
Phase~II. We delete the artificial objective row and the $-\xi$~column, but we
will keep the artificial variable columns because we want the optimal solution
to the minimizing linear program (we are applying the simplex algorithm to the
dual).
$$\vbox{\offinterlineskip
\halign{&\enspace\hfil\strut$#$\enspace\cr
y_1^+&y_1^-&y_2&\bar y_3&y_4&y_5&s_1&a_2&s_3&p_4&a_4&z&\omit&\hbox{\smfont RHS}\cr
\noalign{\vskip2pt}
3&-3&-26&0&11&0&0&3&0&10&-10&1&\omit\vrule&-34\cr
\multispan{12}&\omit\vrule height2pt&\omit\cr
\noalign{\hrule}
\multispan{12}&\omit\vrule height2pt&\omit\cr
2/3&-2/3&\pivot{8/3}&0&3&0&1&0&0&-1/3&1/3&0&\omit\vrule&13/3\cr
1&-1&0&0&1&1&0&1&0&0&0&0&\omit\vrule&2\cr
2&-2&-1&0&3&0&0&3&1&0&0&0&\omit\vrule&7\cr
-1/3&1/3&2/3&1&0&0&0&0&0&-1/3&1/3&0&\omit\vrule&4/3\cr
}}$$

\noindent Pivot on the~8/3 in the $y_2$~column:
$$\vbox{\offinterlineskip
\halign{&\enspace\hfil\strut$#$\enspace\cr
y_1^+&y_1^-&y_2&\bar y_3&y_4&y_5&s_1&a_2&s_3&p_4&a_4&z&\omit&\hbox{\smfont RHS}\cr
\noalign{\vskip2pt}
19/2&-19/2&0&0&161/4&0&39/4&3&0&27/4&-27/4&1&\omit\vrule&33/4\cr
\multispan{12}&\omit\vrule height2pt&\omit\cr
\noalign{\hrule}
\multispan{12}&\omit\vrule height2pt&\omit\cr
1/4&-1/4&1&0&9/8&0&3/8&0&0&-1/8&1/8&0&\omit\vrule&13/8\cr
1&-1&0&0&1&1&0&1&0&0&0&0&\omit\vrule&2\cr
9/4&-9/4&0&0&33/8&0&3/8&3&1&-1/8&1/8&0&\omit\vrule&69/8\cr
-1/2&\pivot{1/2}&0&1&-3/4&0&-1/4&0&0&-1/4&1/4&0&\omit\vrule&1/4\cr
}}$$

\noindent Pivot on the~1/2 in the $y_1^-$~column:
$$\vbox{\offinterlineskip
\halign{&\enspace\hfil\strut$#$\enspace\cr
y_1^+&y_1^-&y_2&\bar y_3&y_4&y_5&s_1&a_2&s_3&p_4&a_4&z&\omit&\hbox{\smfont RHS}\cr
\noalign{\vskip2pt}
0&0&0&19&26&0&5&3&0&2&-2&1&\omit\vrule&13\cr
\multispan{12}&\omit\vrule height2pt&\omit\cr
\noalign{\hrule}
\multispan{12}&\omit\vrule height2pt&\omit\cr
0&0&1&1/2&3/4&0&1/4&0&0&-1/4&1/4&0&\omit\vrule&7/4\cr
0&0&0&2&-1/2&1&-1/2&1&0&-1/2&1/2&0&\omit\vrule&5/2\cr
0&0&0&9/2&3/4&0&-3/4&3&1&-5/4&5/4&0&\omit\vrule&39/4\cr
-1&1&0&2&-3/2&0&-1/2&0&0&-1/2&1/2&0&\omit\vrule&1/2\cr
}}$$

\noindent All entries in the objective row are nonnegative, so this tableau is
optimal. But this is the optimal tableau for the {\it dual}, so the optimal
solution to the {\it primal\/} is found in the objective row in columns
corresponding to slack and artificial variables (i.e., $s_1$,~$a_2$, $s_3$,
and~$a_4$)---except that we negated the third and fourth constraints in the
dual, so we need to negate the values at the top of the $s_3$~and~$a_4$
columns. Therefore, the optimal solution to the primal is $x_1=5$, $x_2=3$,
$x_3=0$, $x_4=2$, which yields the objective value~13.

\goodbreak

Another approach is to negate the objective function in the original linear
program and maximize. Multiply the fourth constraint by~$-1$ in order to make
the right-hand side nonnegative, and then convert to standard variable domains
by making the substitutions $x_2=x_2^+-x_2^-$ and $x_3=-\bar x_3$ with
$x_2^+\ge0$, $x_2^-\ge0$, and $\bar x_3\ge0$. The result is the following
linear program.
$$\eqalign{
	{\rm maximize}\quad{-}3x_1-2x_2^++2x_2^--\phantom1\bar x_3+4x_4&\cr
	{\rm subject\ to}\quad\phantom{+1}x_1+\phantom1x_2^+-\phantom1x_2^--\phantom1\bar x_3+\phantom1x_4&=10\cr
	2x_1\phantom{{}+0x_2^++0x_2^-}-\phantom1\bar x_3-2x_4&\ge\phantom06\cr
	x_1\phantom{{}+0x_2^++0x_2^-+0\bar x_3}+3x_4&\le30\cr
	-3x_1-\phantom1x_2^++\phantom1x_2^-\phantom{{}+0\bar x_3+0x_4}&\le\phantom08\cr
	x_2^+-\phantom1x_2^--3\bar x_3\phantom{{}+0x_4}&\ge\phantom03\cr
	&\phantom{{}=00}\llap{$x_1\ge0$, $x_2^+\ge0$, $x_2^-\ge0$, $\bar x_3\ge0$, $x_4\ge0$}.\cr
}\eqno(1)$$

\noindent Insert slack, surplus, and artificial variables:
$$\displaylines{
\openup-1\jot \eqalign{
	{\rm maximize}\quad{-}3x_1-2x_2^++2x_2^--\phantom1\bar x_3+4x_4\phantom{{}+a_1+p_2+a_2+s_3+s_4+p_5+a_5}&\cr
	{\rm subject\ to}\quad\phantom{+1}x_1+\phantom1x_2^+-\phantom1x_2^--\phantom1\bar x_3+\phantom1x_4+a_1\phantom{{}+p_2+a_2+s_3+s_4+p_5+a_5}&=10\cr
	2x_1\phantom{{}+0x_2^++0x_2^-}-\phantom1\bar x_3-2x_4\phantom{{}+a_1}-p_2+a_2\phantom{{}+s_3+s_4+p_5+a_5}&=\phantom06\cr
	x_1\phantom{{}+0x_2^++0x_2^-+0\bar x_3}+3x_4\phantom{{}+a_1+p_2+a_2}+s_3\phantom{{}+s_4+p_5+a_5}&=30\cr
	-3x_1-\phantom1x_2^++\phantom1x_2^-\phantom{{}+0\bar x_3+0x_4+a_1+p_2+a_2+s_3}+s_4\phantom{{}+p_5+a_5}&=\phantom08\cr
	x_2^+-\phantom1x_2^--3\bar x_3\phantom{{}+0x_4+a_1+p_2+a_2+s_3+s_4}-p_5+a_5&=\phantom03\cr
}\cr
\hbox to\hsize{\hss$x_1\ge0$, $x_2^+\ge0$, $x_2^-\ge0$, $\bar x_3\ge0$, $x_4\ge0$, $a_1\ge0$, $p_2\ge0$, $a_2\ge0$, $s_3\ge0$, $s_4\ge0$, $p_5\ge0$, $a_5\ge0$.\hss}\cr
}$$

\noindent Next we form the initial tableau for the two-phase simplex algorithm:
$$\vbox{\offinterlineskip
\halign{&\enspace\hfil\strut$#$\enspace\cr
x_1&x_2^+&x_2^-&\bar x_3&x_4&a_1&p_2&a_2&s_3&s_4&p_5&a_5&z&-\xi&\omit&\hbox{\smfont RHS}\cr
\noalign{\vskip2pt}
3&2&-2&1&-4&0&0&0&0&0&0&0&1&0&\omit\vrule&0\cr
-3&-2&2&5&1&0&1&0&0&0&1&0&0&1&\omit\vrule&-19\cr
\multispan{14}&\omit\vrule height2pt&\omit\cr
\noalign{\hrule}
\multispan{14}&\omit\vrule height2pt&\omit\cr
1&1&-1&-1&1&1&0&0&0&0&0&0&0&0&\omit\vrule&10\cr
\pivot2&0&0&-1&-2&0&-1&1&0&0&0&0&0&0&\omit\vrule&6\cr
1&0&0&0&3&0&0&0&1&0&0&0&0&0&\omit\vrule&30\cr
-3&-1&1&0&0&0&0&0&0&1&0&0&0&0&\omit\vrule&8\cr
0&1&-1&-3&0&0&0&0&0&0&-1&1&0&0&\omit\vrule&3\cr
}}$$

\noindent Pivot on the~2 in the $x_1$~column:
$$\vbox{\offinterlineskip
\halign{&\enspace\hfil\strut$#$\enspace\cr
x_1&x_2^+&x_2^-&\bar x_3&x_4&a_1&p_2&a_2&s_3&s_4&p_5&a_5&z&-\xi&\omit&\hbox{\smfont RHS}\cr
\noalign{\vskip2pt}
0&2&-2&5/2&-1&0&3/2&-3/2&0&0&0&0&1&0&\omit\vrule&-9\cr
0&-2&2&7/2&-2&0&-1/2&3/2&0&0&1&0&0&1&\omit\vrule&-10\cr
\multispan{14}&\omit\vrule height2pt&\omit\cr
\noalign{\hrule}
\multispan{14}&\omit\vrule height2pt&\omit\cr
0&1&-1&-1/2&2&1&1/2&-1/2&0&0&0&0&0&0&\omit\vrule&7\cr
1&0&0&-1/2&-1&0&-1/2&1/2&0&0&0&0&0&0&\omit\vrule&3\cr
0&0&0&1/2&4&0&1/2&-1/2&1&0&0&0&0&0&\omit\vrule&27\cr
0&-1&1&-3/2&-3&0&-3/2&3/2&0&1&0&0&0&0&\omit\vrule&17\cr
0&\pivot1&-1&-3&0&0&0&0&0&0&-1&1&0&0&\omit\vrule&3\cr
}}$$

\filbreak

\noindent Pivot on the~1 in the bottom row in the $x_2^+$~column:
$$\vbox{\offinterlineskip
\halign{&\enspace\hfil\strut$#$\enspace\cr
x_1&x_2^+&x_2^-&\bar x_3&x_4&a_1&p_2&a_2&s_3&s_4&p_5&a_5&z&-\xi&\omit&\hbox{\smfont RHS}\cr
\noalign{\vskip2pt}
0&0&0&17/2&-1&0&3/2&-3/2&0&0&2&-2&1&0&\omit\vrule&-15\cr
0&0&0&-5/2&-2&0&-1/2&3/2&0&0&-1&2&0&1&\omit\vrule&-4\cr
\multispan{14}&\omit\vrule height2pt&\omit\cr
\noalign{\hrule}
\multispan{14}&\omit\vrule height2pt&\omit\cr
0&0&0&\pivot{5/2}&2&1&1/2&-1/2&0&0&1&-1&0&0&\omit\vrule&4\cr
1&0&0&-1/2&-1&0&-1/2&1/2&0&0&0&0&0&0&\omit\vrule&3\cr
0&0&0&1/2&4&0&1/2&-1/2&1&0&0&0&0&0&\omit\vrule&27\cr
0&0&0&-9/2&-3&0&-3/2&3/2&0&1&-1&1&0&0&\omit\vrule&20\cr
0&1&-1&-3&0&0&0&0&0&0&-1&1&0&0&\omit\vrule&3\cr
}}$$

\filbreak

\noindent Pivot on the~5/2 in the $\bar x_3$~column:
$$\hss\vbox{\offinterlineskip
\halign{&\enspace\hfil\strut$#$\enspace\cr
x_1&x_2^+&x_2^-&\bar x_3&x_4&a_1&p_2&a_2&s_3&s_4&p_5&a_5&z&-\xi&\omit&\hbox{\smfont RHS}\cr
\noalign{\vskip2pt}
0&0&0&0&-39/5&-17/5&-1/5&1/5&0&0&-7/5&7/5&1&0&\omit\vrule&-143/5\cr
0&0&0&0&0&1&0&1&0&0&0&1&0&1&\omit\vrule&0\cr
\multispan{14}&\omit\vrule height2pt&\omit\cr
\noalign{\hrule}
\multispan{14}&\omit\vrule height2pt&\omit\cr
0&0&0&1&4/5&2/5&1/5&-1/5&0&0&2/5&-2/5&0&0&\omit\vrule&8/5\cr
1&0&0&0&-3/5&1/5&-2/5&2/5&0&0&1/5&-1/5&0&0&\omit\vrule&19/5\cr
0&0&0&0&18/5&-1/5&2/5&-2/5&1&0&-1/5&1/5&0&0&\omit\vrule&131/5\cr
0&0&0&0&3/5&9/5&-3/5&3/5&0&1&4/5&-4/5&0&0&\omit\vrule&136/5\cr
0&1&-1&0&12/5&6/5&3/5&-3/5&0&0&1/5&-1/5&0&0&\omit\vrule&39/5\cr
}}\hss$$

\noindent All entries in the artificial objective row are nonnegative, so
Phase~I is complete. The artificial objective value is~0, so Phase~I was
successful. All artificial variables are nonbasic, so we can continue to
Phase~II. We delete the artificial objective row, the artificial variable
columns, and the $-\xi$~column.
$$\vbox{\offinterlineskip
\halign{&\enspace\hfil\strut$#$\enspace\cr
x_1&x_2^+&x_2^-&\bar x_3&x_4&p_2&s_3&s_4&p_5&z&\omit&\hbox{\smfont RHS}\cr
\noalign{\vskip2pt}
0&0&0&0&-39/5&-1/5&0&0&-7/5&1&\omit\vrule&-143/5\cr
\multispan{10}&\omit\vrule height2pt&\omit\cr
\noalign{\hrule}
\multispan{10}&\omit\vrule height2pt&\omit\cr
0&0&0&1&\pivot{4/5}&1/5&0&0&2/5&0&\omit\vrule&8/5\cr
1&0&0&0&-3/5&-2/5&0&0&1/5&0&\omit\vrule&19/5\cr
0&0&0&0&18/5&2/5&1&0&-1/5&0&\omit\vrule&131/5\cr
0&0&0&0&3/5&-3/5&0&1&4/5&0&\omit\vrule&136/5\cr
0&1&-1&0&12/5&3/5&0&0&1/5&0&\omit\vrule&39/5\cr
}}$$

\filbreak

\noindent Pivot on the~4/5 in the $x_4$~column:
$$\vbox{\offinterlineskip
\halign{&\enspace\hfil\strut$#$\enspace\cr
x_1&x_2^+&x_2^-&\bar x_3&x_4&p_2&s_3&s_4&p_5&z&\omit&\hbox{\smfont RHS}\cr
\noalign{\vskip2pt}
0&0&0&39/4&0&7/4&0&0&5/2&1&\omit\vrule&-13\cr
\multispan{10}&\omit\vrule height2pt&\omit\cr
\noalign{\hrule}
\multispan{10}&\omit\vrule height2pt&\omit\cr
0&0&0&5/4&1&1/4&0&0&1/2&0&\omit\vrule&2\cr
1&0&0&3/4&0&-1/4&0&0&1/2&0&\omit\vrule&5\cr
0&0&0&-9/2&0&-1/2&1&0&-2&0&\omit\vrule&19\cr
0&0&0&-3/4&0&-3/4&0&1&1/2&0&\omit\vrule&26\cr
0&1&-1&-3&0&0&0&0&-1&0&\omit\vrule&3\cr
}}$$
All entries in the objective row are nonnegative, so this tableau is optimal.
So the optimal solution to the linear program~(1) is $x_1=5$, $x_2^+=3$,
$x_2^-=0$, $\bar x_3=0$, $x_4=2$, which yields the objective value~$-13$. This
means that the optimal solution to the original linear program is $x_1=5$,
$x_2=3$, $x_3=0$, $x_4=2$, with objective value~13. \qed

\filbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Formulate a linear program for the following scenario. Then solve the
linear program and interpret your results.

{\medskip\narrower

\noindent Leisure Furniture, Inc.\ (LFI) makes outdoor chairs, tables, lounges,
and benches. The main resources required for production are plastic webbing,
metal tubing, and wood. The number of units of each resource required per item
and the per-item profit are given below.
$$\vbox{\offinterlineskip
\halign{\quad\strut#\hfil\quad&\vrule#&\quad\hfil\strut#\hfil\quad
	&\quad\hfil\strut#\hfil\quad&\quad\hfil\strut#\hfil\quad&\vrule#
	&\quad\hfil\strut#\hfil\quad\cr
&&Tubing&Webbing&Wood&&Per-unit\cr
&&(feet)&(yards)&(board feet)&&profit\cr
\omit&height2pt&\omit&\omit&\omit&height2pt\cr
\noalign{\hrule}
\omit&height2pt&\omit&\omit&\omit&height2pt\cr
Chair&&18&28&&&\$11\cr
Table&&18&&10&&\$18\cr
Lounge&&24&35&&&\$14\cr
Bench&&20&&14&&\$\phantom09\cr}}$$

\goodbreak

\noindent The main activities in production are tube bending and assembly. The
number of hours of each activity required per unit of each product are given
in the table below.
$$\vbox{\offinterlineskip
\halign{\quad\strut#\hfil\quad&\vrule#&&\quad\hfil\strut#\hfil\quad\cr
&&Chair&Table&Lounge&Bench\cr
\omit&height2pt\cr
\noalign{\hrule}
\omit&height2pt\cr
Tube bending&&1/3&1/8&1/4&1/8\cr
Assembly&&1/2&1/2&1/3&1/3\cr}}$$

\goodbreak

\noindent LFI is planning its first week's production for the spring. Available
during that week are 120~hours of bending time, 160~hours of assembly time,
6,000~feet of tubing, 5,000~yards of webbing, and 1,000~board feet of wood. The
lounge is the most popular product, so LFI wants to make at least 100 of them.
Tables and chairs are commonly sold in sets of two chairs and a table, so they
want to make at least twice as many chairs as tables. Otherwise they want to
make the products that will maximize their profit if sold.

\par}

\solution Let $C$,~$T$, $L$, and~$B$ be the numbers of chairs, tables, lounges,
and benches to be made, respectively. All of these variables are nonnegative.
The linear program below represents the problem of maximizing profit subject to
the constraints in the problem.

$$\eqalignno{
	{\rm maximize}\quad 11C+18T+14L+\phantom09B&&\hbox{[profit]}\cr
	{\rm subject\ to}\quad 18C+18T+24L+20B&\le6000&\hbox{[tubing]}\cr
	28C\phantom{{}+00T}+35L\phantom{{}+00B}&\le5000&\hbox{[webbing]}\cr
	10T\phantom{{}+00L}+14B&\le1000&\hbox{[wood]}\cr
	\frac13C+\phantom{00}\llap{$\frac18$}T+\phantom{00}\llap{$\frac14$}L+\phantom{00}\llap{$\frac18$}B&\le\phantom0120&\hbox{[bending]}\cr
	\frac12C+\phantom{00}\llap{$\frac12$}T+\phantom{00}\llap{$\frac13$}L+\phantom{00}\llap{$\frac13$}B&\le\phantom0160&\hbox{[assembly]}\cr
	L\phantom{{}+00B}&\ge\phantom0100&\hbox{[lounge production]}\cr
	C-\phantom02T\phantom{{}+00L+00B}&\ge\phantom{000}0&\hbox{[chairs \& tables]}\cr
	&\phantom{{}=0000}\llap{$C\ge0$,\quad$T\ge0$,\quad$L\ge0$,\quad$B\ge0$}.\cr
}$$

\goodbreak

\noindent The following Maple worksheet solves this linear program.

{\smallskip
\raggedright \advance\hsize by-\parindent \hangindent=\parindent
		\hangafter=0  \noindent\tt
> restart;\hfil\break
> with(Optimization);
$$\displaylines{
	[\it ImportMPS,Interactive,LPSolve,LSSolve,Maximize,Minimize,NLPSolve,\hfill\cr
	\qquad\it QPSolve]\hfill\cr
}$$
> profit:=(C,T,L,B)->11*C+18*T+14*L+9*B;
$${\it profit}:=(C,T,L,B)\to11\,C+18\,T+14\,L+9\,B$$
> constraints:=[18*C+18*T+24*L+20*B<=6000,28*C+35*L<=5000,\hfil\break
	\strut\qquad 10*T+14*B<=1000,C/3+T/8+L/4+B/8<=120,C/2+T/2+L/3+B/3<=160,\hfil\break
	\strut\qquad L>=100,C-2*T>=0];
$$\displaylines{
	{\it constraints}:=\biggl[18\,C+18\,T+24\,L+20\,B\le6000,28\,C+35\,L\le5000,\hfill\cr
	\qquad10\,T+14\,B\le1000,{1\over3}\,C+{1\over8}\,T+{1\over4}\,L+{1\over8}\,B\le120,{1\over2}\,C+{1\over2}\,T+{1\over3}\,L+{1\over3}\,B\le160,\hfill\cr
	\qquad100\le L,0\le C-2\,T\biggr]\hfill\cr
}$$
> LPSolve(profit(C,T,L,B),constraints,'maximize',\hfil\break
	\strut\qquad assume=nonnegative);
$$\displaylines{
	\bigl[2942.09183674067,[B=52.2959183669781,C=53.5714285714286,L=100.,\hfill\cr
	\qquad T=26.7857142862306]\bigr]\hfill\cr
}$$

\smallskip}

Unfortunately, the optimal solution to the linear program is not an integer
solution, and a fractional solution doesn't really make sense in the context of
the problem. (Sorry---I didn't intend for this to happen.) We can ask Maple to
find the optimal {\it integer\/} solution by using {\tt assume=nonnegint}
instead of {\tt assume=nonnegative} as an option to {\tt LPSolve}. It turns out
that we also have to increase the default depth limit for the search process.
When we do this, we get the following result:

{\smallskip
\raggedright \advance\hsize by-\parindent \hangindent=\parindent
		\hangafter=0  \noindent\tt
> LPSolve(profit(C,T,L,B),constraints,'maximize',\hfil\break
	\strut\qquad assume=nonnegint,depthlimit=7);
$$\bigl[2922,[B=52,C=52,L=101,T=26]\bigr]$$

}

\noindent Hence, in order to maximize profit, LFI should produce 52~benches,
52~chairs, 101~lounges, and 26~tables, which will produce a profit of \$2922.
\qed

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

\problem Find an extreme point of the feasible region of the following linear
program.
$$\eqalign{
	{\rm maximize}\quad\phantom{+1}x_1-2x_2+\phantom1x_3\phantom{{}+0x_4}&\cr
	{\rm subject\ to}\quad\phantom+3x_1+3x_2-\phantom1x_3-2x_4&\le90\cr
	x_1\phantom{{}+0x_2}+5x_3\phantom{{}+0x_4}&\ge20\cr
	-4x_1-\phantom1x_2+\phantom1x_3-\phantom1x_4&=\phantom06\cr
	x_2-2x_3+\phantom1x_4&\le40\cr
	&\phantom{{}=00}\llap{$x_1\ge0$,\quad$x_2\ge0$,\quad$x_3\ge0$,\quad$x_4\ge0$}.\cr
}$$

\solution An extreme point of the feasible region is a basic feasible solution,
so that is what we are after in this problem. One approach is to perform
Phase~I of the two-phase simplex algorithm in order to get a basic feasible
solution. We don't care about the objective function, so we don't need an
objective row in our tableau (only the artificial objective row).
$$\vbox{\offinterlineskip
\halign{&\enspace\hfil\strut$#$\enspace\cr
x_1&x_2&x_3&x_4&s_1&p_2&a_2&a_3&s_4&-\xi&\omit&\hbox{\smfont RHS}\cr
\noalign{\vskip2pt}
3&1&-6&1&0&1&0&0&0&1&\omit\vrule&-26\cr
\multispan{10}&\omit\vrule height2pt&\omit\cr
\noalign{\hrule}
\multispan{10}&\omit\vrule height2pt&\omit\cr
3&3&-1&-2&1&0&0&0&0&0&\omit\vrule&90\cr
1&0&\pivot5&0&0&-1&1&0&0&0&\omit\vrule&20\cr
-4&-1&1&-1&0&0&0&1&0&0&\omit\vrule&6\cr
0&1&-2&1&0&0&0&0&1&0&\omit\vrule&40\cr
}}$$

\noindent Pivot on the~5 in the $x_3$~column:
$$\vbox{\offinterlineskip
\halign{&\enspace\hfil\strut$#$\enspace\cr
x_1&x_2&x_3&x_4&s_1&p_2&a_2&a_3&s_4&-\xi&\omit&\hbox{\smfont RHS}\cr
\noalign{\vskip2pt}
21/5&1&0&1&0&-1/5&6/5&0&0&1&\omit\vrule&-2\cr
\multispan{10}&\omit\vrule height2pt&\omit\cr
\noalign{\hrule}
\multispan{10}&\omit\vrule height2pt&\omit\cr
16/5&3&0&-2&1&-1/5&1/5&0&0&0&\omit\vrule&94\cr
1/5&0&1&0&0&-1/5&1/5&0&0&0&\omit\vrule&4\cr
-21/5&-1&0&-1&0&\pivot{1/5}&-1/5&1&0&0&\omit\vrule&2\cr
2/5&1&0&1&0&-2/5&2/5&0&1&0&\omit\vrule&48\cr
}}$$

\noindent Pivot on the~1/5 in the $p_2$~column:
$$\vbox{\offinterlineskip
\halign{&\enspace\hfil\strut$#$\enspace\cr
x_1&x_2&x_3&x_4&s_1&p_2&a_2&a_3&s_4&-\xi&\omit&\hbox{\smfont RHS}\cr
\noalign{\vskip2pt}
0&0&0&0&0&0&1&1&0&1&\omit\vrule&0\cr
\multispan{10}&\omit\vrule height2pt&\omit\cr
\noalign{\hrule}
\multispan{10}&\omit\vrule height2pt&\omit\cr
-1&2&0&-3&1&0&0&1&0&0&\omit\vrule&96\cr
-4&-1&1&-1&0&0&0&1&0&0&\omit\vrule&6\cr
-21&-5&0&-5&0&1&-1&5&0&0&\omit\vrule&10\cr
-8&-1&0&-1&0&0&0&2&1&0&\omit\vrule&52\cr
}}$$
All entries in the artificial objective row are nonnegative, so Phase~I is
complete. The artificial objective value is~0, so Phase~I was successful. All
artificial variables are nonbasic, so we have a basic feasible solution, which
is $x_1=0$, $x_2=0$, $x_3=6$, $x_4=0$.

\goodbreak

Another approach is to ask Maple to optimize the constant function~0 subject
to the given constraints.

{\smallskip
\raggedright \advance\hsize by-\parindent \hangindent=\parindent
		\hangafter=0  \noindent\tt
> restart;\hfil\break
> with(Optimization);
$$\displaylines{
	[\it ImportMPS,Interactive,LPSolve,LSSolve,Maximize,Minimize,NLPSolve,\hfill\cr
	\qquad\it QPSolve]\hfill\cr
}$$
> constraints:=[3*x1+3*x2-x3-2*x4<=90,x1+5*x3>=20,-4*x1-x2+x3-x4=6,\hfil\break
	\strut\qquad x2-2*x3+x4<=40];
$$\displaylines{
	{\it constraints}:=[3\,{\it x1}+3\,{\it x2}-{\it x3}-2\,{\it x4}\le90,20\le{\it x1}+5\,{\it x3},-4\,{\it x1}-{\it x2}+{\it x3}-{\it x4}=6,\hfill\cr
	\qquad{\it x2}-2{\it x3}+{\it x4}\le40]\hfill\cr
}$$
> LPSolve(0,constraints,assume=nonnegative);
$$\bigl[0.,[{\it x1}=0.,{\it x2}=0.,{\it x3}=6.,{\it x4}=0.]\bigr]$$

\smallskip}

\noindent So Maple also produces the basic feasible solution $x_1=0$, $x_2=0$,
$x_3=6$, $x_4=0$.

Look at the $x_2$~column in the tableau at the end of Phase~I\null: it is a
nonbasic column with a zero in the artificial objective row and a positive
entry below. This means that we can pivot on that column to get another basic
feasible solution. If we do this, we find the other extreme point of the
feasible region, which is $x_1=0$, $x_2=48$, $x_3=54$, $x_4=0$. \qed

\filbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Consider a project consisting of several activities, each having a
usual time and a set of immediate prerequisites. Some of the activities can be
sped up; these activities additionally have a crash time and a per-unit speedup
cost. (This is the kind of problem we considered when we discussed the critical
path method.) Suppose that the overall project needs to be sped up to meet a
deadline, and it is desired to do so at minimum total speedup cost. Is it true
that only the critical activities (under the usual times) are candidates to be
sped up? If so, explain why. If not, give a counterexample.

\solution No, activities that are not critical under the usual times may also
be candidates to be sped up. For example:
$$\vbox{\offinterlineskip
\halign{\quad\hfil\strut#\hfil\quad&&\hfil\strut#\hfil\quad\cr
&Immediate&Usual time&Crash time\cr
Activity&prerequisites&(days)&(days)\cr
\noalign{\vskip2pt\hrule\vskip2pt}
A&---&2&1\cr
B&---&3&1\cr
}}$$
The CPM network for this project is shown below, along with values calculated
from the usual times: earliest times (written in green above the nodes), latest
times (written in red below the nodes), and floats (written in blue below the
arcs). The critical path under the usual times is highlighted in yellow.
$$\fig{midterm-solns-cpm.mps}$$
In this project, only activity~B is critical under the usual times. But if the
project is to be sped up to meet a deadline of 1~day, then both A~and~B must be
sped up. \qed

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

\problem An important communications line is to be built between locations
$s$~and~$t$ in a dangerous, disaster-prone area. The line cannot be built
directly; it will need to be built as a sequence of links joining intermediate
points $a$,~$b$, \dots,~$g$. The following table shows the estimated
probabilities of {\it failure\/} of a link built between pairs of points. (Not
all pairs of points are possible locations for a communications link;
impossible locations are indicated with a dash.) If any link fails, then the
entire communications line fails. Determine a route for the line that minimizes
the probability of failure.
$$\vbox{\offinterlineskip
\halign{\quad\hfil\strut#\hfil\quad&\vrule#&\quad\hfil\strut#\hfil\quad&&\hfil\strut#\hfil\quad\cr
&&$s$&$a$&$b$&$c$&$d$&$e$&$f$&$g$&$t$\cr
\omit&height2pt\cr
\noalign{\hrule}
\omit&height2pt\cr
$s$&&---&1.5\%&---&---&---&---&3.0\%&4.0\%&---\cr
$a$&&1.5\%&---&---&---&5.0\%&---&2.0\%&---&---\cr
$b$&&---&---&---&6.0\%&8.0\%&---&---&---&0.5\%\cr
$c$&&---&---&6.0\%&---&---&2.0\%&3.5\%&7.0\%&---\cr
$d$&&---&5.0\%&8.0\%&---&---&---&2.5\%&---&---\cr
$e$&&---&---&---&2.0\%&---&---&---&5.5\%&5.0\%\cr
$f$&&3.0\%&2.0\%&---&3.5\%&2.5\%&---&---&1.0\%&---\cr
$g$&&4.0\%&---&---&7.0\%&---&5.5\%&1.0\%&---&---\cr
$t$&&---&---&0.5\%&---&---&5.0\%&---&---&---\cr
}}$$

\solution If the communications line is built using $k$~links, and the
probabilities of failure of those links are $p_1$,~$p_2$, \dots,~$p_k$,
respectively, then the probability that the line does {\it not\/} fail is
$$\prod_{i=1}^k(1-p_i),$$
assuming that the events of link failure are mutually independent. We aim to
maximize this quantity, which we can do by maximizing its {\it logarithm\/}:
$$\log\biggl[\,\prod_{i=1}^k(1-p_i)\biggr]=\sum_{i=1}^k\log(1-p_i).$$
Since $0<p_i<1$ for all~$i$, the value of $\log(1-p_i)$ will be negative, so
equivalently we aim to {\it minimize\/} the positive sum
$$\sum_{i=1}^k[-{\log}(1-p_i)].$$
Therefore, what we are seeking is a minimum-cost path (i.e., a ``shortest''
path) from $s$ to~$t$, where the cost of each arc~$(i,j)$ is
$-{\log}(1-p_{ij})$.

So we modify the cost table, replacing each probability~$p$ with (a rational
approximation of) $-{\log}(1-p)$:
$$\hss\vbox{\offinterlineskip
\halign{\quad\hfil\strut#\hfil\quad&\vrule#&&\enspace\hfil\strut#\hfil\enspace\cr
&&$s$&$a$&$b$&$c$&$d$&$e$&$f$&$g$&$t$\cr
\omit&height2pt\cr
\noalign{\hrule}
\omit&height2pt\cr
$s$&&---&0.01511&---&---&---&---&0.03046&0.04082&---\cr
$a$&&0.01511&---&---&---&0.05129&---&0.02020&---&---\cr
$b$&&---&---&---&0.06188&0.08338&---&---&---&0.00501\cr
$c$&&---&---&0.06188&---&---&0.02020&0.03563&0.07257&---\cr
$d$&&---&0.05129&0.08338&---&---&---&0.02532&---&---\cr
$e$&&---&---&---&0.02020&---&---&---&0.05657&0.05129\cr
$f$&&0.03046&0.02020&---&0.03563&0.02532&---&---&0.01005&---\cr
$g$&&0.04082&---&---&0.07257&---&0.05657&0.01005&---&---\cr
$t$&&---&---&0.00501&---&---&0.05129&---&---&---\cr
}}\hss$$
Note that because these probabilities are rather close to zero, these costs are
not too far from the probabilities themselves. This is a consequence of the
fact that $\log(1+x)\approx x$ for $x\approx0$, which comes from the Maclaurin
series for $\log(1+x)$. So it's not totally invalid to use the probabilities
themselves as the costs.

Our goal, then, is to find a shortest path from $s$ to~$t$ in the following
graph.
$$\fig{midterm-solns-graph.mps}$$

\goodbreak

\def\figuregap{\vskip0pt plus12pt}

One approach is to use Dijkstra's algorithm. The iterations of Dijkstra's
algorithm are shown in the figures below. In each figure, the edge weights are
circled, the vertex labels (denoting the tentative distance from~$s$) are shown
in red, the current set~$W$ of vertices whose distances from~$s$ have
definitely been determined is outlined in light blue, and the vertex~$x$
outside~$W$ with the smallest vertex label is boxed in green.

\figuregap

$$\fig{midterm-solns-dijkstra-1.mps}$$

\figuregap

$$\fig{midterm-solns-dijkstra-2.mps}$$

\figuregap

$$\fig{midterm-solns-dijkstra-3.mps}$$

\figuregap

$$\fig{midterm-solns-dijkstra-4.mps}$$

\figuregap

$$\fig{midterm-solns-dijkstra-5.mps}$$

\figuregap

$$\fig{midterm-solns-dijkstra-6.mps}$$

\figuregap

$$\fig{midterm-solns-dijkstra-7.mps}$$

\figuregap

$$\fig{midterm-solns-dijkstra-8.mps}$$

\figuregap

$$\fig{midterm-solns-dijkstra-9.mps}$$

Now all vertices are included in~$W$, so the labels give the shortest distance
from~$s$ for each vertex. To find a shortest path from~$s$ to any vertex, we
identify the admissible edges, which are those edges whose weight equals the
difference of the vertex labels at their endpoints. The admissible edges are
shown as double green lines in the figure below.
$$\fig{midterm-solns-dijkstra-10.mps}$$
From this figure, we see that the shortest path from $s$ to~$t$ is
$s$--$f$--$c$--$b$--$t$. The cost of this path in the graph is 0.13298, which
is the negative of the logarithm of the probability that the corresponding
communications line does {\it not\/} fail; so the probability of failure of
this line is $1-e^{-0.13298}\approx12.45\%$.

\goodbreak

Another approach is to formulate a linear program to find the shortest path
from $s$ to~$t$ in the graph. The node-arc LP formulation is shown below. For
each edge~$(i,j)$ in the graph, there are two variables $f_{ij}$~and~$f_{ji}$
denoting the flow from $i$ to~$j$ and from $j$ to~$i$, respectively. (Recall
that the node-arc LP formulation for the shortest path is based on a
{\it directed\/} graph. The graph here is undirected, so flow can pass through
an edge in either direction.) The flow-balance constraints enforce the
conditions that the net outflow at every node must be~0, except at node~$s$
where it is~1 and at node~$t$ where it is~$-1$. The objective function is the
cost of the flow.
$$\eqalign{
	{\rm minimize}\quad\rlap{$\displaystyle\sum_{{\rm edges}\ (i,j)}[-{\log}(1-p_{ij})](f_{ij}+f_{ji})$}
		\phantom{f_{fs}+f_{fa}+f_{fc}+f_{fd}+f_{fg}-f_{sf}-f_{af}-f_{cf}-f_{df}-f_{gf}}&\cr
	{\rm subject\ to}\quad\phantom{f_{fs}+f_{fa}+f_{fc}+f_{fd}+f_{fg}-f_{sf}-f_{af}-f_{cf}-f_{df}-f_{gf}}
		\llap{$f_{sa}+f_{sf}+f_{sg}-f_{as}-f_{fs}-f_{gs}$}&=\phantom+1\cr
	f_{as}+f_{ad}+f_{af}-f_{sa}-f_{da}-f_{fa}&=\phantom+0\cr
	f_{bc}+f_{bd}+f_{bt}-f_{cb}-f_{db}-f_{tb}&=\phantom+0\cr
	f_{cb}+f_{ce}+f_{cf}+f_{cg}-f_{bc}-f_{ec}-f_{fc}-f_{gc}&=\phantom+0\cr
	f_{da}+f_{db}+f_{df}-f_{ad}-f_{bd}-f_{ad}&=\phantom+0\cr
	f_{ec}+f_{eg}+f_{et}-f_{ce}-f_{ge}-f_{te}&=\phantom+0\cr
	f_{fs}+f_{fa}+f_{fc}+f_{fd}+f_{fg}-f_{sf}-f_{af}-f_{cf}-f_{df}-f_{gf}&=\phantom+0\cr
	f_{gs}+f_{gc}+f_{ge}+f_{gf}-f_{sg}-f_{cg}-f_{eg}-f_{fg}&=\phantom+0\cr
	f_{tb}+f_{te}-f_{bt}-f_{et}&=-1\cr
	\rlap{all variables nonnegative.}
		\phantom{f_{fs}+f_{fa}+f_{fc}+f_{fd}+f_{fg}-f_{sf}-f_{af}-f_{cf}-f_{df}-f_{gf}}&\cr
}$$

\goodbreak

\noindent The following Maple worksheet solves this linear program.

{\smallskip
\raggedright \advance\hsize by-\parindent \hangindent=\parindent
		\hangafter=0  \noindent\tt
> restart;\hfil\break
> with(Optimization);
$$\displaylines{
	[\it ImportMPS,Interactive,LPSolve,LSSolve,Maximize,Minimize,NLPSolve,\hfill\cr
	\qquad\it QPSolve]\hfill\cr
}$$

\goodbreak

\hangindent=\parindent  \hangafter=0  \noindent
> cost:=(sa,sf,sg,as,ad,af,bc,bd,bt,cb,ce,cf,cg,da,db,df,ec,eg,et,\hfil\break
	\strut\qquad fs,fa,fc,fd,fg,gs,gc,ge,gf,tb,te)->-log(1-0.015)*(sa+as)\hfil\break
	\strut\qquad-log(1-0.03)*(sf+fs)-log(1-0.04)*(sg+gs)-log(1-0.05)*(ad+da)\hfil\break
	\strut\qquad-log(1-0.02)*(af+fa)-log(1-0.06)*(bc+cb)-log(1-0.08)*(bd+db)\hfil\break
	\strut\qquad-log(1-0.005)*(bt+tb)-log(1-0.02)*(ce+ec)-log(1-0.035)*(cf+fc)\hfil\break
	\strut\qquad-log(1-0.07)*(cg+gc)-log(1-0.025)*(df+fd)-log(1-0.055)*(eg+ge)\hfil\break
	\strut\qquad-log(1-0.05)*(et+te)-log(1-0.01)*(fg+gf);
$$\displaylines{
	{\it cost}:=({\it sa,sf,sg,as,ad,af,bc,bd,bt,cb,ce,cf,cg,da,db,df,ec,eg,et,fs,fa,fc,}\hfill\cr
	\qquad{\it fd,fg,gs,gc,ge,gf,tb,te})\to-{\log}(0.985)\,({\it sa}+{\it as})-\log(0.97)\,({\it sf}+{\it fs})\hfill\cr
	\qquad-\log(0.96)\,({\it sg}+{\it gs})-\log(0.95)\,({\it ad}+{\it da})-\log(0.98)\,({\it af}+{\it fa})-\log(0.94)\,({\it bc}+{\it cb})\hfill\cr
	\qquad-\log(0.92)\,({\it bd}+{\it db})-\log(0.995)\,({\it bt}+{\it tb})-\log(0.98)\,({\it ce}+{\it ec})\hfill\cr
	\qquad-\log(0.965)\,({\it cf}+{\it fc})-\log(0.93)\,({\it cg}+{\it gc})-\log(0.975)\,({\it df}+{\it fd})\hfill\cr
	\qquad-\log(0.945)\,({\it eg}+{\it ge})-\log(0.95)\,({\it et}+{\it te})-\log(0.99)\,({\it fg}+{\it gf})\hfill\cr
}$$
> flow:=[sa+sf+sg-as-fs-gs=1,as+ad+af-sa-da-fa=0,\hfil\break
	\strut\qquad bc+bd+bt-cb-db-tb=0,cb+ce+cf+cg-bc-ec-fc-gc=0,\hfil\break
	\strut\qquad da+db+df-ad-bd-fd=0,ec+eg+et-ce-ge-te=0,\hfil\break
	\strut\qquad fs+fa+fc+fd+fg-sf-af-cf-df-gf=0,gs+gc+ge+gf-sg-cg-eg-fg=0,\hfil\break
	\strut\qquad tb+te-bt-et=-1];
$$\displaylines{
	{\it flow}:=[{\it sa}+{\it sf}+{\it sg}-{\it as}-{\it fs}-{\it gs}=1,{\it as}+{\it ad}+{\it af}-{\it sa}-{\it da}-{\it fa}=0,\hfill\cr
	\qquad{\it bc}+{\it bd}+{\it bt}-{\it cb}-{\it db}-{\it tb}=0,{\it cb}+{\it ce}+{\it cf}+{\it cg}-{\it bc}-{\it ec}-{\it fc}-{\it gc}=0,\hfill\cr
	\qquad{\it da}+{\it db}+{\it df}-{\it ad}-{\it bd}-{\it fd}=0,{\it ec}+{\it eg}+{\it et}-{\it ce}-{\it ge}-{\it te}=0,\hfill\cr
	\qquad{\it fs}+{\it fa}+{\it fc}+{\it fd}+{\it fg}-{\it sf}-{\it af}-{\it cf}-{\it df}-{\it gf}=0,\hfill\cr
	\qquad{\it gs}+{\it gc}+{\it ge}+{\it gf}-{\it sg}-{\it cg}-{\it eg}-{\it fg}=0,{\it tb}+{\it te}-{\it bt}-{\it et}=-1]\hfill\cr
}$$
> LPSolve(cost(sa,sf,sg,as,ad,af,bc,bd,bt,cb,ce,cf,cg,da,db,df,ec,\hfil\break
	\strut\qquad eg,et,fs,fa,fc,fd,fg,gs,gc,ge,gf,tb,te),flow,\hfil\break
	\strut\qquad assume=nonnegative);
$$\displaylines{
	\bigl[0.132974330420616,[{\it ad}=0.,{\it af}=1.37679669262847\;10^{-9},{\it as}=0.,{\it bc}=0.,\hfill\cr
	\qquad{\it bd}=0.,{\it bt}=0.999999998623202,{\it cb}=0.999999995525409,{\it ce}=0.,{\it cf}=0.,\hfill\cr
	\qquad{\it cg}=0.,{\it da}=0.,{\it db}=0.,{\it df}=0.,{\it ec}=0.,{\it eg}=0.,\hfill\cr
	\qquad{\it et}=3.44199262913333\;10^{-10},{\it fa}=0.,{\it fc}=0.999999997934804,\hfill\cr
	\qquad{\it fd}=2.40939493661442\;10^{-9},{\it fg}=0.,{\it fs}=0.,{\it gc}=0.,\hfill\cr
	\qquad{\it ge}=6.88398525826666\;10^{-10},{\it gf}=0.,{\it gs}=0.,{\it sa}=0.,\hfill\cr
	\qquad{\it sf}=0.999999998967403,{\it sg}=0.,{\it tb}=0.,{\it te}=0.]\bigr]\hfill\cr
}$$

\smallskip}

\noindent The optimal values of all variables are either 0~or~1 (although
floating-point roundoff error is evident in the Maple output), and the
shortest path is indicated by the variables that have the value~1 in the
optimal solution: $f_{sf}$,~$f_{fc}$, $f_{cb}$, and~$f_{bt}$, which correspond
to the route $s$--$f$--$c$--$b$--$t$. The optimal objective value reported by
Maple agrees with the value we determined via Dijkstra's algorithm. \qed

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

\bye
